Capítulo 1_REDES

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.