Modelos de redes
Algunos ejemplos de la aplicación de los modelos de redes son:
- Diseño de una red de tuberías de gas natural de transporte o distribución que tienen que ver con él envió de gas entre fuentes y destinos a costos de transporte mínimos, el objetivo es de minimizar el costo de construcción del ducto
- Determinación de la ruta más corta que une dos ciudades en una red de caminos existente
- Determinación de la capacidad anual máxima en toneladas de una red de conductos de agua que enlazan diferentes ciudades
- Determinación del programa de flujo de costo mínimo de los campos petrolíferos a refinerías y finalmente a centros de distribución tomando en cuenta la disponibilidad de la oferta máxima y los requisitos de demanda mínima en los centros de distribución
Tipos de redes a estudiar:
- Modelo de árbol de extensión mínima
- Modelo de ruta más corta
- Modelo de flujo máximo
Definiciones de red
Capacidad de rama
Es el flujo máximo que puede admitir una rama, este puede ser finito o infinito.
Rama dirigida
Si la rama permite un flujo positivo en una dirección y cero en dirección opuesta.
Red dirigida
Se llama así a una red que tiene todas sus ramas dirigidas.
Trayectoria
Se dice de ramas distintas que conectan los nodos sin considerar la orientación de las ramas individuales.
Lazos
Es una trayectoria que conecta al nodo consigo mismo.
Lazo dirigido
Es un lazo donde todas las ramas tienen la misma dirección.
Red conectada
Es una red donde cada dos nodos están conectados por una trayectoria.
Árbol
Es una red conectada que puede constar solo de un subconjunto de nodos.
Modelo de árbol de extensión mínima
Consideremos una red de caminos pavimentados para conectar un cierto número de poblaciones rurales debido a las limitaciones en presupuesto el número de kilómetros de camino por construirse debe ser el mínimo absoluto que permita la conexión directa o indirecta del tráfico entre las diferentes poblaciones. Esto se lograra con el árbol de extensión mínima que determinara el árbol extenso que proporciones la suma mínima de ramas conectoras. Encontrará las conexiones más eficientes entre todos los nodos de la red los cuales por definición no deben incluir ningún lazo.
Modelo de ruta más corta
El problema de ruta más corta tiene que ver con la determinación de las ramas conectadas a una red de transporte que constituyen en conjunto la distancia más corta entre fuente y destino.
Modelo de flujo máximo
El problema de flujo máximo considera la situación cuando se alzan un nodo fuente y un nodo destino a través de una red de ramas o arcos de capacidad finita. Una rama i, j puede tener dos capacidades distintas dependiendo si el flujo es de i a j o bien de j a i. Por ejemplo si la red trata con el flujo de tránsito en las calles de una ciudad, una calle de un solo sentido tendrá una capacidad positiva en una dirección y una capacidad cero en la otra. Por otra parte una calle de dos sentidos puede tener capacidades diferentes en las direcciones opuestas si ambas direcciones no incluyen el mismo número de carriles de circulación.