Antología de Investigación de Operaciones
Ingeniería en Sistemas Computacionales
2.3.Problemas de Asignación
Hay una multitud de situaciones, en investigación de operaciones, que se pueden modelar y
resolver como redes (nadas conectados por ramas). Algunas encuestas recientes informan 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 de las 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ón del 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
de carbó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 las actividades 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. Este capítulo presentará cinco de esos algoritmos:
1. Algoritmo de la ruta más corta (situación 2).
2. Algoritmo del flujo máximo (situación 3).
3. Algoritmo de la ruta crítica (situación 5).
Las situaciones en las que se pueden aplicar estos algoritmos también se pueden fallar y resolver
en forma de programas lineales explícitos. Sin embargo, los algoritmos puestos, basados en redes, son
más eficientes que el método símplex.
Definiciones para redes
Una red consiste en una serie de nodos enlazados con arcos (o ramas). La notación para des-
cribir una red es (N, A), donde N es el conjunto de nadas y A es el conjunto de arcos. Por ejemplo, la red
de la figura 2.2.1 se describe como sigue:
N = {1,2,3,4,5}
A = {(1,2), (1,3), (2,3), (2,5),(3,4), (3,5), (4,2), (4,5)}
41