Investigacion De Operaciones

UNIDAD 5. OPTIMIZACIÓN DE REDES

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 hasta el 70% de los problemas de programación matemática en el mundo real se pueden re-presentar 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

5.1. TERMINOLOGÍA

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:

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 es una 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 (4,2) en la figura 6.1.

Una red conectada es aquella en que cada dos nodos distintos están enlazados al menos por una ruta. La red de la figura 6.1 es un ejemplo de este tipo.

Un árboles una red conectada que puede consistir sólo en un subconjunto de todos los nodos en ella, donde no se permiten ciclos.

Un árbol de expansión es un árbol que en laza todos los nodos de la red, también sin permitir ciclos. En la figura 6.2 se ven ejemplos de un árbol y de un árbol de expansión para la red de la figura 6.1.

5.2. PROBLEMA DE LA RUTA MÁS CORTA

El algoritmo de árbol de expansión mínima enlaza los nodos de una red, en forma directa o indirecta, con la mínima longitud de las ramas en lazantes. Una aplicación característica es en la construcción de carreteras pavimentadas que unen varias poblaciones. El camino entre dos poblaciones puede pasar por uno o más poblaciones adicionales. El diseño más económico del sistema de caminos indica que se minimice la distancia total de caminos pavimentados, resultado que se obtiene implementando el algoritmo de árbol de expansión mínima. Los pasos del procedimiento son los siguientes. Sea N {1, 2, ...,n} el conjunto de no-dos de la red, y se definen

Midwest TV Cable Company está en el proceso de proporcionar servicio de cable a cinco nuevas áreas habitacionales. La figura 6.4 representa los enlaces posibles de TV entre las cinco áreas. Las millas de cable se muestran en cada arco. Determine la red de cable más económica. El algoritmo comienza en el nodo 1 (cualquier otro nodo podría ser), con lo que se obtiene

Las iteraciones del algoritmo se resumen en la figura 6.5. Los arcos con línea delgada son todos los enlaces posibles entre C Y Ĉ. Las ramas gruesas representan los enlaces permanentes entre los nodos del conjunto conectado (o “conexo”) C, y la rama con línea interrumpida re-presenta el nuevo enlace (permanente) que se agrega en cada iteración. Por ejemplo, en la iteración 1, la rama (1,2) es la más corta (=1 milla) entre todas las ramas posibles del nodo 1 a los nodos 2, 3, 4 y 5 del conjunto no conectado C1Por consiguiente, el enlace (1,2) se vuelve permanente y j*=2, con lo que se obtiene

La solución se expresa con el árbol de expansión mínima que se ve en la iteración 6, de la figura 6.5. La cantidad mínima de millas necesarias para proporcionar el servicio de cable que se desea resulta ser 1+3+4+3+5=16 millas.

5.3. PROBLEMA DE ÁRBOL DE MÍNIMA EXPANSIÓN

El problema del árbol de expansión mínima tiene algunas similitudes con la versión principal del problema de la ruta más corta. En ambos casos se considera una red no dirigida y conexa, en la que la información dada incluye alguna medida de longitud positiva (distancia, costo, tiempo, etc.) asociada con cada ligadura. Los dos problemas involucran también el hecho de seleccionar un conjunto ligaduras de ligaduras que tiene la longitud total más corta entretodos los conjuntos de ligaduras que satisfacen cierta propiedad. Para elproblema de la ruta más corta esta propiedad es que la ligadura seleccionada debe proporcionar una trayectoria entre el origen y el destino. Para el árbol de expansión mínima la propiedad requerida es que las ligaduras seleccionadas deben proporcionar una trayectoria entre cada par de nodos. Una red con n nodos requiere sólo (n -1) ligaduras para proporcionar una trayectoria entre cada par de nodos. No deben usarse más ligaduras yaque esto aumentaría, sin necesidad, la longitud total de las ligadurasseleccionadas. Las (n -1) ligaduras deben elegirse de tal manera que la red resultante (con sólo las ligaduras seleccionadas) forme un árbol de expansión. Por lo tanto, el problema es encontrar el árbol de expansión con la longitud total mínima de sus ligaduras. Este problema tiene muchas aplicaciones prácticas importantes. Por ejemplo, puede ser útil en la planeación de redes de transporte que no se transitarán mucho

...