REDES DE OPTIMIZACIÓN

Redes de Optimización
Hay una multitud de situaciones, en investigación de operaciones, que se pueden modelar y resolver como redes (nodos conectados por ramas). Algunas encuestas recientesinforman que hasta el 70% de los problemas de programación matemática en el mundo real se pueden representar como modelos relacionados con redes. La lista siguiente ilustra algunas aplicaciones posibles delas redes:
1. Diseño de una red de gasoductos marinos para conectar bocas de pozos en el Golfo de México con un punto de entrega en tierra. El objetivo del modelo es minimizar el costo de construccióndel gasoducto
2. Determinación de la ruta más corta entre dos ciudades, en una red de carreteras.
3. Determinación de la capacidad máxima (en toneladas anuales) de una red de tubería para lodo decarbón que une las minas en Wyoming con las centrales eléctricas en Houston. (Las tuberías de lodo de carbón transportan el carbón suspendido en agua a través de tubos de diseño especial)
4.Determinación del programa de flujo con costo mínimo desde los campos petroleros hasta las refinerías a través de una red de oleoductos
5. Determinación del cronograma (fechas de inicio y terminación) de lasactividades en la construcción de un proyecto.
La solución de esas situaciones y otras parecidas se logra con una variedad de algoritmos de optimización de redes.
Definición
Una red consiste enuna serie de nodos enlazados con 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.

EJEMPLO DE UNA RED (Fig.1)
N = {1, 2, 3,4,5}
A= {(1,2),(1,3),(2,3)(2,5),(3,4),(3,5),(4,2),(4,5)}



Cada red asocia algún tipo de flujo (por ejemplo, flujo de productos petroleros en un oleoducto y flujos de tráfico de automóviles encarrera). En general, el flujo en una red está limitado por la capacidad de sus arcos, que pueden ser finitos o infinitos.
Se dice que un arco es dirigido u orientado si permite un flujo positivo...