Tipos de redes investigacion de operaciones

Miguel Fernando Herrera Morales
Investigación de operaciones II
Tipos de redes
Los problemas de redes surgen en una gran variedad de situaciones. Las redes de transporte, eléctricas y de comunicaciones predominan en la vida diaria. La representación de redes se utiliza de manera amplia en áreas tan diversas como producción, distribución, planeación de proyectos, localización de instalaciones,administración de recursos y planeación financiera, por mencionar sólo algunos ejemplos. En realidad, una representación de redes proporciona un poderoso apoyo visual y conceptual para mostrar las relaciones entre las componentes de los sistemas, de tal modo que se usa casi en todos los ámbitos científicos, sociales y económicos.
Uno de los mayores desarrollos recientes en investigación deoperaciones (IO) ha sido el rápido avance tanto en la metodología como en la aplicación de los modelos de optimización de redes. La aparición de algunos algoritmos ha tenido un efecto importante, al igual que las ideas de ciencias de la computación acerca de estructuras de datos y la manipulación eficiente de éstos. En la actualidad se dispone de algoritmos y paquetes de computadora que se usan en formarutinaria para resolver problemas muy grandes que no se habrían podido manejar hace dos o tres décadas.
Muchos modelos de optimización de redes son en realidad tipos especiales de problemas de programación lineal.
Hay una multitud de situaciones, en investigación de operaciones, que se pueden modelar y resolver como redes (nodos conectados por ramas). Algunas encuestas recientes informan que hastael 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 delgasoducto.
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.
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 deoleoductos.
5. Determinación del cronograma
La solución de esas situaciones y otras parecidas se logra con una variedad de algoritmos de optimización de redes:
1. Árbol de expansión mínima (situación 1).
2. Algoritmo de la ruta más corta (situación 2).
3. Algoritmo del flujo máximo (situación 3).
4. Algoritmo de red capacitada con costo mínimo (situación 4).
5. Algoritmo de la ruta crítica (situación 5).DEFINICIONES PARA REDES
Una red consiste en una 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. Por ejemplo, la red de la figura 6.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)}


Con cada red se asocia algún tipo de flujo (por ejemplo,flujo de productos petroleros en un oleoducto y flujos de tráfico de automóviles en carreteras). 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 en una dirección, y flujo cero en la dirección opuesta. Una red dirigida tiene todos sus arcos dirigidos.
Una ruta esuna sucesión de arcos distintos que unen dos nodos pasando por otros nodos, independientemente de la dirección de flujo en cada arco. Una ruta forma un ciclo si conecta un nodo consigo mismo, pasando por otros nodos. Por ejemplo, en la figura 6.1, los arcos (2,3),
(3,5) y (5,2) forman un bucle o circuito cerrado. Un ciclo es dirigido si consiste en una ruta dirigida, por ejemplo (2,3), (3,4) y...