Vista previa del material en texto
Investigación Operativa II Ingeniería Comercial
EMI 1 Lic. Maritza Villa Cabero
Capítulo 1
MODELOS DE REDES
Uno de los problemas más frecuentes es la aplicación y análisis de redes que surgen a partir de diferentes
situaciones. Algunas de las aplicaciones más comunes de modelos de redes están en producción,
distribución, planeación de proyectos, localización de instalaciones, administración de recursos, planeación
financiera, redes de transporte, redes eléctricas y redes de comunicaciones. Esto es debido a que, una
representación de redes proporciona un panorama general y una ayuda conceptual para visualizar las
relaciones entre las componentes de los sistemas que se usan.
La metodología en la aplicación de los modelos de optimización de redes ha evolucionado últimamente el
desarrollo de la investigación de operaciones. La producción de algoritmos de cálculo y las aplicaciones en
el área de ciencias de la computación sobre estructuras de datos y la manipulación eficiente de los mismos,
han generado paquetes de computación que se están usando para resolver problemas muy grandes que no
se habrían podido manejar hace unas dos décadas.
Muchos modelos de optimización de redes son problemas especiales de programación lineal. El problema
de transporte y el problema de asignación, pueden considerarse problemas de optimización de redes y se
pueden resolver con la metodología de redes. Los principales modelos de optimización de redes son:
✓ Problema de la ruta más corta.
✓ Problema del árbol de mínima expansión.
✓ Problema del flujo máximo.
✓ Problema del flujo de costo mínimo.
✓ Problema de planeación y control de proyectos con PERT ("Program Evaluation and Review
Technique" O técnica de evaluación y revisión de programas) y CPM ("Critical Path Method" o método
de la ruta crítica).
En este capítulo se presentarán los cuatro primeros modelos, el problema PERT-CPM se trabajará en el
próximo capítulo.
1. TERMINOLOGÍA DE REDES. –
Una red consiste en un conjunto de puntos y líneas, éstas unen a los puntos por parejas. Los puntos se
llaman nodos (o vértices). La red de la figura 1 tiene siete nodos representados por siete círculos. Las líneas
se llaman arcos (o ligaduras, aristas o ramas). La red de la figura 1 tiene 13 arcos que corresponden a los
Investigación Operativa II Ingeniería Comercial
EMI 2 Lic. Maritza Villa Cabero
13 caminos de un sistema de transporte de una ciudad. Los arcos se definen con los nodos terminales; por
ejemplo, AB es el arco entre los nodos A y B en la figura 1.
Figura 1: Sistema de vías para el transporte en autobuses de una ciudad.
Los arcos de una red pueden tener un flujo de algún tipo que pasa por ellos, por ejemplo, el flujo de autobuses
sobre los caminos de la ciudad. Un arco dirigido sólo permite el flujo en una dirección. La dirección se indica
mediante una cabeza de flecha. La notación de un arco dirigido se hace con el nombre de los nodos que une,
colocando primero el nodo de donde viene y después el nodo a donde va, esto es, un arco dirigido del nodo
A al nodo B debe indicarse como AB ó A→B. Un arco de ligadura o no dirigido permite el flujo en ambas
direcciones.
1.1. Elementos que componen las redes. –
Una red que sólo tiene arcos dirigidos se llama red dirigida. Si todos sus arcos son ligados, se trata de una
red ligada. Si dos nodos no están unidos por un arco a veces resulta conveniente saber si están conectados
por una serie de arcos. Una trayectoria entre dos nodos es una sucesión de arcos distintos que conectan
estos nodos. Por ejemplo, la sucesión de arcos OB, BE Y EF conforman una de las trayectorias que conectan
a los nodos O y F en la figura 1. Pero otra trayectoria es O→C→E→F. Una trayectoria dirigida del nodo 1 al
nodo j es una sucesión de arcos con dirección hacia el nodo j, de manera que el flujo del nodo 1 al nodo j a
través de esta trayectoria es factible. Una trayectoria ligada del nodo 1 al nodo j es una sucesión de arcos
cuya dirección puede ser hacia o desde el nodo j. Un ciclo es una trayectoria que comienza y termina en el
mismo nodo. Dos nodos están conectados si en la red existe al menos una trayectoria entre ellos. Una red
Investigación Operativa II Ingeniería Comercial
EMI 3 Lic. Maritza Villa Cabero
es conexa si cada par de nodos están conectados; por lo tanto, la red de la figura 1, es conexa y dejará de
serlo si se suspenden los arcos A→B, A→D y A→F.
La capacidad del arco es la cantidad máxima de flujo que puede circular en éste. En los nodos fuentes, el
flujo que sale de ellos excede el flujo que entra. En los casos contrarios, esto es, el flujo que llega excede al
que sale, se tienen nodos demandas. En un nodo de transbordo o intermedio, el flujo que entra es igual al
que sale.
2. PROBLEMA DE LA RUTA MÁS CORTA. -
Para el análisis de este modelo se puede suponer una red conexa y no dirigida con dos nodos principales
llamados origen y destino. A cada uno de los arcos no dirigidos se asocia una distancia. El objetivo del
problema es encontrar la ruta más corta o trayectoria con la mínima distancia total, que va desde el origen al
destino. El algoritmo de solución para este problema se fundamenta en el análisis de toda la red, partiendo
del origen e identificando sucesivamente la ruta más corta desde el origen a cada uno de los nodos en orden
ascendente de sus distancias. Se obtiene la solución del problema al llegar al nodo destino.
2.1. Algoritmo de la ruta más corta. -
En cada una de las k-ésimas iteraciones se debe definir para el k-ésimo nodo, la distancia más corta desde
el origen hasta el k-ésimo nodo. Si 𝒅𝒊𝒌 define la distancia entre los nodos i, k; entonces se puede calcular la
distancia más corta desde el origen hasta el nodo k-ésimo con la siguiente expresión:
𝑇𝑘 = 𝑀𝑒𝑛𝑜𝑟{𝑇𝑖 + 𝑑𝑖𝑘}
Dónde:
i = cada nodo conectado con el nodo k
El procedimiento termina con el cálculo de 𝑇𝑘 para el nodo final.
3. PROBLEMA DEL ÁRBOL DE MÍNIMA EXPANSIÓN. -
Este problema tiene algunas similitudes con el problema de la ruta más corta. De manera general, en ambos
casos se considera una red no dirigida y conexa, en la que los datos dados incluyen medidas para cada
ligadura (distancia, costo, tiempo, etc.). Involucran también el hecho de seleccionar un conjunto de ligaduras
que tiene la longitud total más corta entre todas las ligaduras que cumplan determinada propiedad. En el
problema de la ruta más corta, la ligadura seleccionada debe generar una trayectoria entre el origen y el
destino, mientras que para el árbol de expansión mínima se requiere que las ligaduras seleccionadas generen
una trayectoria entre cada par de nodos, de tal manera que la suma de todas las trayectorias sea mínima.
Una red con n nodos sólo requiere n – 1 ligaduras para generar una trayectoria entre cada par de nodos. Por
lo tanto, el problema es encontrar el árbol de expansión con la longitud total mínima de sus ligaduras.
Investigación Operativa II Ingeniería Comercial
EMI 4Lic. Maritza Villa Cabero
El problema del árbol de mínima expansión se resuelve normalmente con el inicio en cualquier nodo. El
primer paso consiste en seleccionar la rama más corta posible a otro nodo desde el inicio, sin preocuparse
del efecto que esta elección pueda tener en las decisiones posteriores. El segundo paso consiste en
identificar el nodo no conectado más cercano a cualquiera de los dos que se acaban de conectar y después
agregar la ligadura correspondiente a la red. Este proceso se repite, según el resumen que se da a
continuación, hasta que se hayan conectado todos los nodos.
3.1. Algoritmo para el problema del árbol de expansión mínima. –
Paso 1. - Se selecciona, de manera arbitraria, cualquier nodo y se conecta al nodo más cercano distinto de
éste.
Paso 2. - Se identifica el nodo no conectado más cercano a un nodo conectado, y se unen estos dos nodos.
Este paso se repite hasta que se hayan conectado todos los nodos. Los empates para el nodo no conectado
más cercano, se rompen arbitrariamente y el algoritmo aún tiende a una solución óptima. Sin embargo, los
empates indican la posibilidad de soluciones óptimas múltiples. Todas esas soluciones, si existen, se pueden
encontrar si se buscan las demás formas de romper los empates hasta el final.
El problema del árbol de expansión tiene muchas aplicaciones prácticas. Un caso importante es la planeación
de redes de transporte aéreo que se usarán poco, pero que se requieren para proporcionar alguna trayectoria
entre todos los pares de nodos de la manera más económica. Los nodos son los aeropuertos que requieren
acceso a otros aeropuertos, las ligaduras son las rutas aéreas y las distancias (valores de las ligaduras) son
los costos de proporcionar la comunicación. En este caso, el objetivo es determinar las vías de comunicación
que darían servicio a todas las localidades con un costo total mínimo.
4. FLUJOS EN REDES. –
Los problemas de esta clase son aplicaciones de Programación Lineal con una característica especial,
siempre tienen una solución óptima con base en números enteros si los datos de entrada también son
enteros. Esto permite el diseño de algoritmos eficientes que pueden ser aplicados a la solución de una
variedad de problemas combinatorios. Entre estos se disponen, el algoritmo de flujo máximo, el cálculo de
flujos de costo mínimo.
4.1. Problema del flujo máximo. -
Se considera la situación en la que se enlazan un nodo fuente y un nodo destino mediante una red de arcos
de un solo sentido. Cada arco tiene una capacidad máxima de flujo admisible. El objetivo consiste en
obtener la máxima cantidad de flujo entre el nodo fuente y destino. Puede ser el caso donde un número
de refinerías se conectan a terminales de distribución mediante una red de oleoductos. En los oleoductos se
Investigación Operativa II Ingeniería Comercial
EMI 5 Lic. Maritza Villa Cabero
tienen unidades de bombeo que impulsan los productos derivados del petróleo hasta las terminales de
distribución. El objetivo consiste en maximizar el flujo entre las refinerías y las terminales de distribución
dentro de los límites de capacidad de las refinerías y los oleoductos. La figura 2 ilustra el problema del flujo
máximo de la refinería. En este caso hay una fuente conectada a todas las refinerías y un depósito que recibe
flujo de todas las terminales de distribución. Los nodos entre las refinerías y las terminales de distribución
son las estaciones de bombeo. Las capacidades de los arcos de la fuente única representan las salidas
máximas de las refinerías. Cada oleoducto tiene una capacidad máxima que determina el flujo máximo
admisible en la línea. En algunos casos, podrá necesitarse utilizar las demandas en las terminales como las
capacidades de los arcos al depósito.
Figura 2: Red de oleoductos.
Supóngase que cada arco (i, j) de una red dirigida tiene asociado un número no negativo 𝑪𝒊𝒋 denominado la
capacidad del arco, Si esta capacidad representa la máxima cantidad de algún artículo que pueda enviarse
a través del arco, la pregunta inmediata es, Cuál es la cantidad máxima del artículo que se puede enviar de
un nodo a otro, dentro de la red? Lo anterior obliga a considerar el problema de hallar el máximo flujo posible
desde un nodo fuente O, a un nodo depósito o terminal T.
4.1.1. Algoritmo de trayectorias de aumentos. -
El algoritmo basado en dos conceptos intuitivos: red residual y trayectoria aumentada. Una vez se han
asignado flujos a los arcos de la red original, las capacidades restantes o residuales conforman la red residual
que sirve para asignar flujos adicionales.
En una trayectoria de aumento desde el nodo fuente al destino a través de la red residual, todos los arcos
tienen capacidad residual positiva. El mínimo de estas capacidades residuales se llama capacidad residual
de trayectoria de aumento, pues proporciona la posibilidad de aumentar el flujo al través de la red.
Investigación Operativa II Ingeniería Comercial
EMI 6 Lic. Maritza Villa Cabero
Este algoritmo, selecciona trayectorias de aumento y agrega al flujo la capacidad residual de esa trayectoria.
Este proceso se repite hasta que ya no existan trayectorias de aumento, con lo que el flujo del nodo fuente
al nodo destino ya no puede crecer.
5. FLUJOS DE COSTO MÍNIMO. -
Es una solución muy eficiente que aborda un conjunto muy amplio de aplicaciones, tomando en cuenta un
flujo a través de una red con capacidades limitadas en sus arcos, Tal como se tiene para el problema de la
ruta más corta, considera un costo (o distancia) para el flujo a través de cada arco. E igual que para los
problemas del transporte y asignación, puede considerar el flujo desde varios orígenes (nodos fuente) hasta
varios destinos (nodos demanda).
El problema del flujo de costo mínimo se puede resolver de manera tan eficiente porque se puede formular
como un problema de programación lineal y resolver mediante una versión simplificada llamada método
Símplex de Redes. En la siguiente sección se describirá el uso del método Simplex.
5.1. Solución heurística. -
Consiste en recurrir iterativamente al concepto de ruta más corta o de mínimo costo de la siguiente forma:
1. Se define como camino por donde se trataría de enviar un cierto número de unidades a la ruta de mínimo
costo.
2. Una vez se tiene una ruta de mínimo costo, se examina el mayor número de unidades que se puede enviar
por esta ruta.
3. Saturada esta ruta, se busca otra ruta de mínimo costo (la segunda mejor), a través de la cual se enviará
correspondientemente el mayor número de unidades posibles.
4. El procedimiento del punto anterior se repetirá hasta realizar el programa completo de envíos.