Introducción
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 (Hillier, 2010).
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 (Hillier, 2010).
En esta unidad sólo serán planteadas las bases de la metodología de redes actual.
Los tres primeros tipos de problemas el de la ruta más corta, el del árbol de mínima expansión y el del flujo máximo tienen una estructura específica que surge con frecuencia en la práctica.
El cuarto tipo problema del flujo de costo mínimo proporciona un enfoque unificado de muchas otras aplicaciones debido a su estructura mucho más general.
EJEMPLO PROTOTÍPICO
En fecha reciente se reservó el área de SEERVADA PARK para paseos y campamentos. No se permite la entrada de automóviles, pero existe un sistema de caminos angostos y sinuosos para tranvías y para “jeeps” (Hillier, 2010).
En la figura de la siguiente diapositiva, se muestra este sistema de caminos, en donde O es la entrada al parque; las otras letras representan la localización de las casetas de los guardabosques y otras instalaciones de servicio. Los números son las distancias en millas de estos caminos.
En este momento la administración del parque se enfrenta a tres problemas. Uno consiste en determinar qué ruta, desde la entrada del parque a la estación T, es la que representa la distancia total más corta para la operación de los tranvías (Hillier, 2010).
ALCANCE Y DEFINICIÓN DE MODELOS DE REDES
Muchas situaciones de investigación de operaciones pueden modelarse y resolverse como redes (nodos conectados por rama) (Hamdy, 2012).
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 (Hamdy, 2012).
Determinación de la ruta más corta entre dos ciudades en una red existente de carreteras.
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) (Hamdy, 2012).
Determinación del cronograma (fechas de inicio y terminación) para las actividades de un proyecto de construcción (Hamdy, 2012).
Determinación del itinerario de flujo de costo mínimo desde campos petroleros hasta refinerías a través de una red de oleoductos (Hamdy, 2012).
La solución de estas situaciones se logra por medio de varios algoritmos de optimización de redes. Esta unidad presenta cuatro de estos algoritmos (Hamdy, 2012).
- Árbol de mínima expansión.
- Algoritmo de la ruta más corta.
- Algoritmo de flujo máximo.
- Algoritmo de la ruta crítica (CPM).
Terminología
▸Una red consiste en un conjunto de puntos y un conjunto de líneas que unen ciertos pares de puntos (Hillier, 2010).
▸Los puntos se llaman nodos (o vértices); por ejemplo, la red de la figura tiene siete nodos que son representados por siete círculos (Hillier, 2010).
▸Las líneas se llaman arcos (o ligaduras, aristas o ramas); por ejemplo, la red de la figura 1 tiene 12 arcos (Hillier, 2010).
Los arcos se etiquetan al dar el nombre de los nodos en sus puntos terminales; por ejemplo, en la figura 1, AB es el arco entre los nodos A y B (Hillier, 2010).
Los arcos de una red pueden tener un flujo de algún tipo que pase por ellos; por ejemplo, el flujo de tranvías sobre los caminos de Seervada Park en la figura 1. Si el flujo a través de un arco se permite sólo en una dirección, se dice que el arco es un arco dirigido. La dirección se indica al agregar una cabeza de flecha al final de la línea que representa el arco (Hillier, 2010).
Cuando se etiqueta un arco dirigido con el nombre de los nodos que unen, siempre se pone primero el nodo de donde viene y después el nodo hacia donde va, esto es, un arco dirigido del nodo A al nodo B debe etiquetarse como AB y no como BA. Otra manera de etiquetarlo es A → B.
Si el flujo a través de un arco se permite en ambas direcciones —como una tubería que se puede usar para bombear fluido en ambas direcciones—, se dice que el arco es un arco no dirigido (Hillier, 2010).
Una red que tiene sólo arcos dirigidos se llama red dirigida. De igual manera, si todos sus arcos son no dirigidos, se dice que se trata de una red no dirigida (Hillier, 2010).
Una trayectoria entre dos nodos es una sucesión de arcos distintos que conectan estos nodos. Por ejemplo, una de las trayectorias que conectan a los nodos O y T en la figura 1 es la sucesión de arcos OB–BD–DT (O → B → D → T ), y viceversa (Hillier, 2010).
Una trayectoria dirigida del nodo i al nodo j es una sucesión de arcos cuya dirección (si la tienen) es hacia el nodo j, de manera que el flujo del nodo i al nodo j a través de esta trayectoria es factible (Hillier, 2010).
Una trayectoria no dirigida del nodo i al nodo j es una sucesión de arcos cuya dirección (si la tiene) puede ser hacia o desde el nodo j. (Observe que una trayectoria dirigida también satisface la definición de trayectoria no dirigida, pero el inverso no se cumple.) Con frecuencia, una trayectoria no dirigida tendrá algunos arcos dirigidos hacia el nodo j y otros desde él, es decir, hacia el nodo i (Hillier, 2010).
Un ciclo es una trayectoria que comienza y termina en el mismo nodo. En una red dirigida, un ciclo puede ser dirigido o no dirigido, según la trayectoria en cuestión sea dirigida o no dirigida. Por ejemplo, en la figura 2, DE–ED es un ciclo dirigido. Por el contrario, AB–BC–AC no es un ciclo dirigido puesto que la dirección del arco AC es opuesta a la de los arcos AB y BC. Por otro lado, AB–BC–AC no es un ciclo dirigido porque A → B → C → A es una trayectoria no dirigida (Hillier, 2010).
La red de distribución de Distribution Unlimited Co. ilustra una red dirigida.
Componentes de redes representativas
La siguiente tabla proporciona varios ejemplos de flujos de redes
