Modelo en Redes
Muchas situaciones de investigación de operaciones pueden modelarse y
resolverse como redes (nodos conectados por ramas), algunos ejemplos:
1. 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.
2. Determinar la ruta mas corta entre dos ciudades en una red existente de
carreteras.
3. Determinar el cronograma (fecha de inicio y terminación) para las
actividades de un proyecto en construcción.
4. Determinación del itinerario del flujo de costo mínimo desde campos
petroleros hasta las refinerías a través de una red de oleoductos.
Modelo en Redes
La solución de estas situaciones se logra por medio de
varios algoritmos de optimización de redes, como:
1. Arbol de mínima expansión.
2. Algoritmo de ruta mas corta.
3. Algoritmo de flujo máximo.
Modelo en Redes
Una red se compone de un conjunto de nodos unidos por 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 (aristas)
N ={1,2,3,4,5}
A = {(1,2),(1,3),(2,3),(2,5),(3,4),(3,5),(4,2),(4,5)}
Modelo en Redes
Una red se compone de un conjunto de nodos unidos por 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 (aristas)
N ={1,2,3,4,5}
A = {(1,2),(1,3),(2,3),(2,5),(3,4),(3,5),(4,2),(4,5)}
Modelo en Redes
Un arco esta dirigido si permite el flujo positivo solo en una dirección, una red dirigida tiene
todos los arcos dirigidos.
Una ruta es un conjunto de arcos que unen dos nodos distintos y que pasan a través de otros
nodos en la red. Por ejemplo en el siguiente grafo, los nodos (1,2), (2,3),(3,4) y (4,5), forman una
ruta entre los nodos 1 y 5. Una ruta forma un ciclo o un bucle si conecta un nodo de vuelta a sí
mismo a través de otros nodos. Por ejemplo los nodos (2,3), (3,4) y (4,2) forman un ciclo.
Se dice que una red esta conectada si cada dos nodos distintos están conectados en al
menos una ruta, la figura que se muestra es un ejemplo de red conectada.
Modelo en Redes
Un árbol es una red conectada libre de ciclos compuesta de un
subconjunto de todos los nodos, y un árbol de expansión es un árbol
que une todos los nodos de una red.
Modelo en Redes
Ejemplo:
La ciudad prusiana de Königsberg (actualmente Kaliningrado en Rusia) fue
fundada en 1254 en las riberas del río Pregel con siete puentes que conectan
sus cuatro secciones (designadas A, B, C, y D) como se muestra en la imagen.
Surgió una pregunta sobre si podría construirse un viaje redondo para visitar las
cuatro secciones de la ciudad, cruzando cada puente exactamente una vez. Una
sección podría ser visitada varias veces, si fuese necesario.
Modelo en Redes
A mediados del siglo XVIII, el afamado matemático Leonhard Euler desarrolló un
argumento de “construcción de rutas” para demostrar que sí era posible construir
semejante viaje. Más tarde, a principios del siglo XIX, el mismo problema se resolvió
presentando de nuevo la situación como una red con nodos que representan las
secciones y arcos (distintos) que representan los puentes, como se muestra en la figura.
La representación en forma de red implica el hallazgo de una respuesta a la pregunta
planteada. El número de arcos incidentes en cada nodo es impar. Esto hace posible entrar y
salir de todas las secciones utilizando puentes distintos. Por consiguiente, el viaje redondo
deseado no puede construirse.1
Modelo en Redes
Algoritmo de expansión mínima
Este árbol vincula los nodos de una red valiéndose de la longitud mínima total de
las ramas de conexión. Una aplicación común se presenta en la pavimentación de
carrete- ras que unen poblaciones, o de forma directa, o que pasan por otras
poblaciones. La solución del árbol de mínima expansión proporciona el diseño del
sistema de carreteras.
Modelo en Redes
Algoritmo de expansión mínima
Ejemplo
Midwest TV Cable Company va a proporcionar servicio de cable a cinco desarrollos
habitacionales. La figura ilustra las posibles conexiones de TV a las cinco áreas,
con las millas de cable anexadas a cada arco. El objetivo es determinar la red de
cables más económica.
Paso 0 : Se identifica
N = {1,2,3,4,5}
C0 = {}
Č0 = {1,2,3,4,5}
Modelo en Redes
Algoritmo de expansión mínima
Paso 1: Inicie con cualquier nodo i en el conjunto no conectado C0 y
establezca C1 = {1}, lo que produce Č1 = N - {1}. Establezca k = 2.
Se identifica:
N = {1,2,3,4,5,6}
C1 = {1}
Č1 = {2,3,4,5,6}
Modelo en Redes
Algoritmo de expansión mínima
Paso 1: Inicie con cualquier nodo i en el conjunto no conectado C0 y
establezca C1 = {1}, lo que produce Č1 = N - {1}. Establezca k = 2.
La ruta (1,2), es la mejor opción La ruta (2,5), es la mejor opción
Se identifica: Se identifica:
N = {1,2,3,4,5,6} N = {1,2,3,4,5,6}
C1 = {1,2} C1 = {1,2,5}
Č1 = {3,4,5,6} Č1 = {3,4,6}
Modelo en Redes
Algoritmo de expansión mínima
Paso 1: Inicie con cualquier nodo i en el conjunto no conectado C0 y
establezca C1 = {1}, lo que produce Č1 = N - {1}. Establezca k = 2.
La ruta (2,4), es la mejor opción La ruta (6,4), es la mejor opción
Se identifica: Se identifica:
N = {1,2,3,4,5,6} N = {1,2,3,4,5,6}
C1 = {1,2,5,4} C1 = {1,2,5,4,6}
Č1 = {3} Č1 = {3}
Modelo en Redes
Algoritmo de expansión mínima
Paso 1: Inicie con cualquier nodo i en el conjunto no conectado C0 y
establezca C1 = {1}, lo que produce Č1 = N - {1}. Establezca k = 2.
La ruta (3,1) y (3,4) es la mejor opción
Se identifica:
N = {1,2,3,4,5,6}
C1 = {1,2,5,4,6,3}
Č1 = {}
Modelo en Redes
El problema de la ruta más corta
Este problema determina la ruta más corta entre un origen y un destino en
una red de transporte.
Modelo en Redes
El problema de la ruta más corta
Ejemplo:
La administración de Seervada Park necesita encontrar la ruta más corta
desde la entrada del parque (nodo 0) hasta el mirador (nodo T), a través del
sistema de caminos que se presenta en la imagen. Las aristas tienen el
recorrido en km de un nodo a otro, por ejemplo del nodo (A,B) = 2KM
N= {0,A,B,C,D,E,T}
Modelo en Redes
El problema de la ruta más corta
Ejemplo:
Modelo en Redes
El problema de la ruta más corta
Ejemplo:
Modelo en Redes
El problema de la ruta más corta
Ejemplo:
Modelo en Redes
El problema de la ruta más corta
Ejemplo:
Modelo en Redes
El problema de la ruta más corta
Ejemplo:
Modelo en Redes
El problema de la ruta más corta
Modelo en Redes
El problema de la ruta más corta
Ejemplo
La red de la figura, da las rutas permisibles y sus longitudes en km entre la ciudad
1 (nodo 1) y las otras cuatro ciudades (nodos 2 a 5). Determine las rutas más
cortas entre la ciudad 1 y cada una de las cuatro ciudades restantes.
Modelo en Redes
Modelo en Redes
Modelo en Redes
Modelo en Redes
En el nodo 2, la nueva etiqueta
[55,4] reemplaza a la etiqueta
temporal [100,1] de la iteración 1
porque proporciona una ruta más
corta. Además, en la iteración 3 el
nodo 5 tiene dos etiquetas
alternativas con la misma distancia
(u5 5 90). La etiqueta temporal
[55,4] en el nodo 2 ahora es
permanente (u2 5 55).
Modelo en Redes
Iteración 4: Sólo el nodo 3
permanentemente etiquetado puede
ser alcanzado desde el nodo 2. Por
consiguiente el nodo 3 no puede ser
reetiquetado. La nueva lista de eti-
quetas permanece como estaba en la
iteración 3 excepto que la etiqueta en
el nodo 2 ahora es permanente. Esto
deja al nodo 5 como la única etiqueta
temporal. Como el nodo 5 no
conduce a otros nodos, su etiqueta se
hace permanente, y el proceso
termina.
Modelo en Redes
La ruta más corta entre el nodo
1 y cualquier otro nodo en la
red se determina partiendo del
nodo destino deseado y
retrocediendo hasta el nodo de
inicio utilizando la información
en las etiquetas permanentes.
Por ejemplo, la siguiente
secuencia determina la ruta
más corta del nodo 1 al nodo
2:
Modelo en Redes
Algoritmo de Floyd
Este algoritmo determina la distancia entre dos nodos cualesquiera en la red. El
algoritmo representa una red de n nodos como una matriz cuadrada con n filas y
n columnas. La entrada (i,j) de la matriz da la distancia dij del nodo i al nodo j, la
cual es finita si i esta directamente vinculado directamente a j e infinita en caso
contrario.
La idea del algoritmo de Floyd es simple. Dados tres nodos, i, j y k en la figura con las
distancias de conexión que se muestran en los tres arcos, es más corto llegar de j a i
pasando por k si
Modelo en Redes
Algoritmo de Floyd
En este caso es óptimo reemplazar la ruta directa de i → j , con la ruta indirecta i → k →j.
Este intercambio de operación triple se aplica a la matriz de distancias por medio de los
siguientes pasos:
Paso 0.
Defina la matriz de la distancia de inicio D0 y la matriz de secuencia de nodos S0 (todos los
elementos en las diagonales están bloqueados). Establezca k = 1.
Modelo en Redes
Algoritmo de Floyd
Paso general k.
Defina la fila k y la columna k como fila pivote y columna pivote. Aplique la operación triple a cada
elemento dij en Dk21, para todas las i y j. Si la condición
se satisface, realice los siguientes cambios:
a) Cree Dk reemplazando dij en Dk21 con dik 1 dkj
b) Cree Sk reemplazando sij en Sk-1 con k. Establezca k = k + 1. Si k = n +1, deténgase: de
lo contrario repita el paso k.
Modelo en Redes
Algoritmo de Floyd
Modelo en Redes
Algoritmo de Floyd
Modelo en Redes
Algoritmo de Floyd
Ejemplo
Para la red de la figura, encuentre las rutas más cortas entre cada dos
nodos. Las distancias (en millas) se dan en los arcos. El arco (3,5) es
direccional, es decir, no se permite el tráfico del nodo 5 al nodo 3. Todos los
demás arcos permiten el tráfico en dos direcciones.
Modelo en Redes
Algoritmo de Floyd
Modelo en Redes
Modelo en Redes
Modelo en Redes
Modelo en Redes
Modelo en Redes
Por ejemplo, desde D4, la distancia más corta del nodo 1 al nodo 5 es d15 = 12. Para determinar la ruta
asociada, recordemos que un segmento (i,j) representa un vínculo directo sólo si sij = j. De lo contrario, i y j están
vinculados por al menos otro nodo intermedio. Como s15 = 4 ≠ 5, la ruta inicialmente se da como 1 → 4 → 5.
Ahora, como s14 = 2 ≠ 4, el segmento (1,4) no es un vínculo directo, y 1 → 2 → 4 reemplaza a 1 → 4, y la ruta
1→4→5 ahora se vuelve 1 → 2 → 4 → 5. Luego, como s12= 2, s24 = 4, y s45 = 5, no se requieren más
“disecciones”, y 1 → 2 → 4 → 5 define la ruta más corta.
Modelo en Redes
1 Solución general: Existe un recorrido que se inicia y termina en un nodo si el número de
arcos incidentes en cada nodo es par. Hay un viaje que se inicia en un nodo y termina en
otro si el número de arcos incidentes en estos dos nodos es impar. De lo contrario, no hay
solución. Vea B. Hopkins y R. Wilson, “The Truth about Königsberg”, College Math Journal,
Vol. 35, núm. 3, págs. 198-207, 2004.