MODELOS DE REDES
SEMANA IV
DEFINICIÓN DE MODELOS DE REDES
Muchas situaciones de investigación de operaciones pueden modelarse
y resolverse como redes (nodos conectados por ramas); a continuación
tenemos algunos ejemplos de aplicación:
• 1. Diseño de una red de oleoductos para gas natural a una
determinada distancia de la costa para conectar los cabezales de los
pozos en el Golfo de México a un punto de distribución costero con el
objetivo de minimizar el costo de construcción de los oleoductos.
• 2. Determinación de la ruta más corta entre dos ciudades en una red
existente de carreteras.
• 3. Determinación de la capacidad máxima (en toneladas por año) de
una red de oleoductos para lodos de carbón que unen minas de
carbón en Wyoming con plantas eléctricas en Houston (los oleoductos
para lodos transportan carbón al bombear agua a través de tuberías
especialmente diseñadas).
• 4. Determinación del cronograma (fechas de inicio y terminación)
para las actividades de un proyecto de construcción.
• 5. Determinación del itinerario de flujo de costo mínimo desde
campos petroleros hasta refinerías a través de una red de oleoductos.
La solución de estas situaciones se logra por medio de varios
algoritmos de optimización de redes. Este capítulo presenta cuatro de
estos algoritmos.
• 1. Árbol de mínima expansión (situación 1)
• 2. Algoritmo de la ruta más corta (situación 2)
• 3. Algoritmo de flujo máximo (situación 3)
• 4. Algoritmo de la ruta crítica (CPM) (situación 4)
• Para la quinta situación, el algoritmo de red capacitada de costo
mínimo se presenta en la sección 22.1 en el sitio web.
• Una red se compone de un conjunto de nodos unidos por arcos (o
ramas). La notación para describir una red es (N,A), donde N es el
conjunto de nodos, y A es el conjunto de arcos. la red de la figura 6.1,
se describe como
• Asociado con cada red hay un flujo (por ejemplo, los productos de petróleo
fluyen por un oleoducto y el tráfico de automóviles fluye por las
carreteras). El flujo máximo en una red puede ser finito o infinito, según la
capacidad de sus arcos.
• Se dice que un arco está dirigido u orientado si permite el flujo positivo
sólo en una dirección. Una red dirigida tiene todos los arcos dirigidos.
• Una ruta es un conjunto de arcos que unen dos nodos distintos, y que
pasan a través de otros nodos en la red. Por ejemplo, en la figura 6.1 los
arcos (1,2), (2,3), (3,4) y (4,5) forman una ruta entre los nodos 1 y 5. Una
ruta forma un ciclo o un bucle si conecta un nodo de vuelta a sí mismo a
través de otros nodos. En la figura 6.1, los arcos (2,3), (3,4) y (4,2) forman
un ciclo.
• Se dice que una red está conectada si cada dos nodos distintos están
conectados en al menos una ruta. La red en la figura 6.1 muestra este
tipo de red. Un árbol es una red conectada libre de ciclos compuesta
de un subconjunto de todos los nodos, y un árbol de expansión es un
árbol que une todos los nodos de la red. La figura 6.2 proporciona
ejemplos de un árbol y un árbol de expansión de la red de la figura
6.1.
ALGORITMO DEL ÁRBOL DE MÍNIMA
EXPANSIÓN
• Este árbol vincula los nodos de una red valiéndose de la longitud
mínima total de las ramas de conexión. Una aplicación común se
presenta en la pavimentación de carreteras que unen poblaciones, o
de forma directa, o que pasan por otras poblaciones. La solución del
árbol de mínima expansión proporciona el diseño del sistema de
carreteras.
Ejemplo 6.2-1
• Midwest TV Cable Company va a proporcionar servicio de cable a
cinco desarrollos habitacionales.
• La figura 6.6 ilustra las posibles conexiones de TV a las cinco áreas,
con las millas de cable anexadas a cada arco. El objetivo es
determinar la red de cables más económica.
• El algoritmo se inicia en el nodo 1 (en realidad, cualquier otro nodo
puede ser un punto de inicio), el cual da por resultado
• Las iteraciones del algoritmo se resumen en la figura 6.7. Los arcos
delgados proporcionan todos los candidatos entre C y C” . Los arcos
gruesos son los vínculos permanentes del conjunto conectado C, y el
arco de rayas es el nuevo vínculo (permanente) agregado en cada
iteración. Por ejemplo, en la iteración 1, la rama (1, 2) es el vínculo
más corto (5 1 milla) entre todas las ramas candidatas del nodo 1 a
los nodos 2, 3, 4, 5 y 6 en el conjunto no conectado De ahí que el
vínculo (1, 2) se hace permanente y j* 5 2, de lo cual resulta
• El árbol de mínima expansión que se muestra en la iteración 6 de la
figura 6.7 da la solución. Las millas de cable mínimas resultantes que
se necesitan para proporcionar el servicio de cable deseado son 1 +3
+1 4 + 3 + 5+ 5+ 16 millas.
• Comentarios. En teoría, un árbol de mínima expansión puede
formularse y resolverse como un programa lineal. Sin embargo, la PL
no es una opción práctica porque deben agregarse numerosas
restricciones para excluir todos los ciclos y el resultado es una PL
enorme, aun para redes pequeñas.
