23-9-2016 Modelo del flujo
máximo
Heurístico aplicable a la resolución
de problemas de interdicción
determinística en redes (PIDR).
MODELOS MATEMÁTICOS
1
Modelo del flujo máximo: heurístico aplicable a la resolución de problemas
de interdicción determinística en redes (PIDR).
En el modelo de flujo máximo hay un solo nodo fuerte (el nodo de entrada) y un
solo nodo recipiente o destino (el nodo de salida). La meta consiste en encontrar
la máxima cantidad de flujo total (petróleo, dinero, mensajes de internet, tráfico de
vehículos, etc.) que puede circular a través de la red (desde la fuente hasta el
recipiente) en una unidad de tiempo. La cantidad de flujo por unidad de tiempo en
cada arco está limitada por restricciones de capacidad.
Resumiendo el modelo de flujo máximo se basa en determinar rutas de irrupción
que tengan flujo neto positivo entre los nodos fuerte y recipiente. Cada ruta
comunica parte o todas las capacidades de sus arcos al flujo total en la red. La
capacidad de los nodos no está especificada. El único requisito en este caso es
que para cada nodo (con excepción de la fuente o el recipiente) la ecuación de
balance de flujo debe satisfacerse.
𝐹𝑙𝑢𝑗𝑜 𝑞𝑢𝑒 𝑠𝑎𝑙𝑒 𝑑𝑒𝑙 𝑛𝑜𝑑𝑜 = 𝐹𝑙𝑢𝑗𝑜 𝑞𝑢𝑒 𝑒𝑛𝑡𝑟𝑎 𝑎𝑙 𝑛𝑜𝑑𝑜
Considérese el arco (𝑖, 𝑗) con capacidades iniciales(𝐶𝑖𝑗 , 𝐶𝑗𝑖 )A medida que partes de
esas capacidades contribuyen al flujo en el arco, se actualizan los residuales (o
capacidades remanentes). La red con los residuales actualizados se llama red
residual. Se usará la notación (𝑐𝑖𝑗 , 𝑐𝑗𝑖 ) para representar esos residuales.
Para un nodo j, se define una etiqueta [𝑎𝑗 , 𝑖] donde 𝑎𝑗 es el flujo del nodo i al nodo
j. los pasos para el modelo de flujo máximo se resumen a continuación:
1) Para todos los arcos (i, j) se iguala la capacidad residual con la capacidad
inicial; esto es, 𝑐𝑖𝑗 , 𝑐𝑗𝑖 = 𝐶𝑖𝑗 , 𝐶𝑗𝑖 . Sea 𝑎1 = ∞ y se etiqueta el nodo fuente
con ∞, − . Se iguala i = 1 y se prosigue el paso 2.
2) Determinar 𝑆𝑖 , el conjunto de nodos j no etiquetados que se pueden
alcanzar directamente desde el nodo i, con arcos con residuales positivos
(esto es,𝑐𝑖𝑗 > 0 para toda 𝑗 ∈ 𝑆𝑖 ). Si 𝑆𝑖 ≠ 0, ir al paso 3 en caso contrario ir
al paso 4.
3) Determinar 𝑘 ∈ 𝑆𝑖 tal que
𝑐𝑖𝑘 = max{𝐶𝑖𝑗 }
𝑗 ∈𝑆𝑖
Igualar 𝑎𝑘 = 𝑐𝑖𝑘 y etiquetar el nodo k con [𝑎𝑘 , 𝑖] si 𝑘 = 𝑛, el nodo residual se ha
etiquetado, y se ha encontrado una ruta de irrupción; ir al paso 5. En caso
contrario, igualar 𝑖 = 𝑘 y seguir en el paso 2.
4) (Retroceso), si i=1, no hay otras irrupciones posibles; ir al paso 6. En caso
contrario sea r el nodo que se ha etiquetado inmediatamente antes del
2
nodo actual i y quitar i del conjunto de nodos adyacentes a r. igualar i = r y
continuar en el paso 2.
5) (Determinación de la red residual). Sea 𝑁𝑝 = 1, 𝑘1 , 𝑘2 , … , 𝑛 ; se definen los
nodos de la p-ésima ruta de irrupción del nodo fuente 1 al nodo residual n.
entonces el flujo máximo por la ruta se calcula como
𝑓𝑝 = 𝑚í𝑛 {𝑎1 , 𝑎𝑘 1 , 𝑎𝑘 2 , … , 𝑎𝑛 }
La capacidad residual de cada arco a lo largo de la ruta de irrupción se disminuye
en𝑓𝑝 unidades en la dirección del flujo y se aumenta𝑓𝑝 unidades en la dirección
contraria; esto es, para los nodos i y j en la ruta, el flujo residual se cambia al
actual (𝑐𝑖𝑗 , 𝑐𝑗𝑖 ) a
a. (𝐶𝑖𝑗 − 𝑓𝑝 ′ , 𝑐𝑗𝑖 + 𝑓𝑝 ) si el flujo va de i a j
b. (𝑐𝑖𝑗 + 𝑓𝑝 ′ 𝑐𝑗𝑖 − 𝑓𝑝 ) si el flujo va de j a i
Se reinstalan todos los nodos que se hayan eliminado en el paso 4. Poner i = 1 y
regresar al paso 2 para intentar una nueva ruta de irrupción.
6) (Solución)
a. Si se han determinado m rutas de irrupción, el flujo máximo en la red es
𝐹 = 𝑓1 + 𝑓2 + ⋯ + 𝑓𝑚
b. Como los residuales inicial y final del arco (i, j) se obtienen con (𝐶𝑖𝑗 , 𝐶𝑗𝑖 ) y
𝑐𝑖𝑗 , 𝑐𝑗𝑖 , respectivamente el flujo óptimo en el arco (i, j) se calcula como
sigue: sea ∝, 𝛽 = (𝐶𝑖𝑗 − 𝑐𝑖𝑗 , 𝐶𝑗𝑖 − 𝑐𝑗𝑖 ). Si∝> 0, el flujo óptimo de i a j es ∝.
Si 𝛽 > 0, el flujo óptimo de i a j es 𝛽. (Es imposible que tanto ∝ como 𝛽 sean
positivos).
Se invoca el proceso de retroceso del paso 4 cuando el algoritmo llega a un“punto
ciego” por descuido, en un nodo intermedio, antes de poder realizar una irrupción.
El ajuste del flujo en el paso 5 se puede explicar con una red de flujo sencilla.
Ejemplo:
La red de la figura a. obtiene la primera ruta de irrupción 𝑁1 = {1,2,3,4} con su flujo
máximo 𝑓1 = 5. Así los residuales de cada uno de los arcos (1, 2), (2, 3) y (3, 4) se
cambian de (5, 0) a (0, 5), según el paso 5.
La red de la figura b. proporciona ahora la ruta de irrupción 𝑁2 = {1,3,2,4} con
𝑓2 = 5. Después de hacer los ajustes necesarios de flujo.
Se obtiene la red c. donde ya no son posibles más irrupciones. Lo que sucedió en
la transición de b. a c. no es más que una cancelación de un flujo antes
comprometido en la dirección 2 3 El algoritmo puede “recordar” que se había
3
comprometido antes un flujo de 2 a 3 sólo porque se ha aumentado la capacidad
en la dirección contraria de 0 a 5 (de acuerdo con el paso 5).
Ejercicio 1.
Gloria Stime está a cargo de la Comisión de Planeación del Desarrollo Urbano
(UDPC por sus siglas en inglés), un grupo de estudio ad hoc de interés especial.
La responsabilidad actual del grupo consiste en coordinar la construcción del
nuevo sistema de vías subterráneas con el departamento de mantenimiento de
caminos. En virtud de que el nuevo sistema de vía subterránea se construirá cerca
del circuito periférico de la ciudad, el tráfico de éste que se dirige al oriente deberá
4
ser desviado. La desviación planeada es en realidad una red de rutas alternas
propuestas por el departamento de mantenimiento de caminos. Los diferentes
límites de velocidad y los patrones de tráfico producen distintas capacidades de
flujo en los diferentes arcos de la red propuesta, como se aprecia en la siguiente
figura:
El nodo 1 indica el inicio de la desviación; es decir, en punto en el cual el tráfico
que se dirigía hacia el oriente sale de la vía periférica. El nodo 6 es el punto en el
cual el tráfico desviado entra de nuevo en la vía periférica. Además en la figura las
capacidades de flujo dependen de la dirección de éste. El símbolo 6 en el arco
(1,3) denota una capacidad de 6,000vehículos por hora en la dirección 1 →3. El
símbolo 0 en el mismo arco significa que existe unacapacidad cero en la dirección
3 → l. Es así porque el arco en cuestión (1,3) denota una vía de un solo sentido
desde 1 hasta 3.
El flujo máximo es 8,000 vehículos por hora, como muestra la siguiente figura:
5
Ejercicio 2.
Determinar el flujo máximo en la red
Iteración 1.
Paso 1. Igualar 𝑎1 = ∞ y etiquetar el nodo 1 con ∞, − . Poner i=1.
Paso 2. 𝑆1 = 2,3,4 (≠ ∅)
Paso 3. 𝑘 = 3Porque𝑐13 = 𝑚á𝑥 {𝑐12 , 𝑐13 , 𝑐14} = 𝑚á𝑥 20,30,10 = 30.
Tomar 𝑎3 = 𝑐13 = 30 y etiquetar el nodo 3 con [30, 1]. Igualar i =3 y repetir el paso
6
2.
Paso 2. 𝑆3 = (4, 5)
Paso 3. 𝑘 = 5y𝑎5 = 𝑐35 = 𝑚á𝑥 10,20 = 20. Etiquetar el nodo 5 con [20, 3]. Se
obtuvo una irrupción. Ir al paso 5.
Paso 5. La ruta de irrupción se determina con las etiquetas comenzando con el
nodo 5 y terminando en el nodo 1; esto es, (5) [20, 3](3)[30, 1](1). Así
𝑁1 = {1, 3, 5} y 𝑓1 = 𝑚í𝑛 𝑎1 , 𝑎3 , 𝑎5 = ∞, 30, 20 = 20. Las capacidades residuales
a lo largo de la ruta 𝑁1 son:
𝑐13 , 𝑐31 = 30 − 20, 0 + 20 = (10, 20)
𝑐35 , 𝑐53 = 20 − 20, 0 + 20 = (0, 20)
Iteración 2.
Paso 1. Poner 𝑎1 = ∞ y etiquetar el nodo 1 con ∞, − . Igualar i = 1.
Paso 2. 𝑆1 = 2,3,4 .
Paso 3. 𝑘 = 2y𝑎2 = 𝑐12 = 𝑚á𝑥 20,10,10 = 20. Poner i =2 y repetir el paso 2.
Paso 2. 𝑆2 = {3,5}
Paso 3.𝑘 = 3y𝑎3 = 𝑐23 = 40. Etiquetar el nodo 3 con [40, 2]. Poner i =3 y repetir el
paso 2.
Paso 2. 𝑆3 = {4} (Observe que 𝑐35 = 0; en consecuencia el nodo 5 no puede
incluirse en el 𝑆3 ).
Paso 3.𝑘 = 4y𝑎4 = 𝑐34 = 10. Etiquetar el nodo 4 con [10, 3]. Igualar i = 4 y repetir
el paso 2.
Paso 2.𝑆4 = {5} (Observe que los nodos 1 y 3 ya se han etiquetado y en
consecuencia no se pueden incluir en 𝑆4 ).
Paso 5. 𝑁2 = {1,2,3,4,5}y𝑓2 = 𝑚í𝑛 ∞, 20, 40, 10, 20 = 10. Los residuales a lo largo
de la ruta 𝑁2 son:
𝑐12 , 𝑐21 = 20 − 10, 0 + 10 = (10, 10)
𝑐23 , 𝑐32 = 40 − 10, 0 + 10 = (30, 10)
𝑐34 , 𝑐43 = 10 − 10, 5 + 10 = (0, 15)
𝑐45 , 𝑐54 = 20 − 10, 0 + 10 = (10, 10)
Iteración 3.
Paso 1. Poner 𝑎1 = ∞ y etiquetar el nodo 1 con ∞, − ; poner i =1.
Paso 2.𝑆1 = {2,3,4}
Paso 3.𝑘 = 2y𝑎2 = 𝑐12 = 𝑚á𝑥 10, 10, 10 = 10 (aunque los empates se rompen en
forma arbitraria). Etiquetar el nodo 2 con [10, 0]. Poner i =2 y repetir el paso 2.
Paso 2. 𝑆2 = 3,5 .
Paso 3. 𝑘 = 3y𝑎3 = 𝑐23 = 30. Etiquetar el nodo 3 con [30, 2]. Poner i =3 y repetir
el paso 2.
Paso 2. 𝑆3 = ∅ (Porque𝑐34 = 𝑐35 = 0). Ir al paso 4 para retroceder.
7
Paso 4. La etiqueta [30, 2] en el nodo 3 da el nodo inmediato anterior r = 2. Sacar
el nodo 3 de más consideraciones en esta iteración, tachándolo. Repetir el paso 2
con i = r =2.
Paso 2. 𝑆2 = {5}; nótese que el nodo 3 se ha eliminado en el paso de retroceso.
Paso 3. 𝑘 = 5y𝑎5 = 𝑐25 = 30. Etiquetar el nodo 5 con [30, 2]. Se ha logrado la
irrupción; proseguir con el paso 5.
Paso 5. 𝑁3 = {1,2,5}y𝑐5 = 𝑚í𝑛 ∞, 10, 30 = 10. Los residuales a lo largo de la
trayectoria de 𝑁3 son:
𝑐12 , 𝑐21 = 10 − 10, 10 + 10 = 0, 20
𝑐25 , 𝑐52 = 30 − 10, 0 + 10 = 20, 10
Iteración 4.
En esta iteración se obtiene 𝑁4 = {1,3,2,5} con 𝑓4 = 10.
Iteración 5.
En esta iteración se obtiene 𝑁5 = {1,4,5} con 𝑓5 = 10.
Iteración 6.
Todos los arcos que salen del nodo 1 tienen residuales cero. En consecuencia no
hay más irrupciones posibles. Pasaremos al paso 6 para determinar la solución.
Paso 6.
El flujo máximo en la red es 𝐹 = 𝑓1 + 𝑓2 + ⋯ + 𝑓5 = 20 + 10 + 10 + 10 + 10 = 60
unidades. El flujo en los distintos arcos se calcula restando los últimos
residuales(𝑐𝑖𝑗 , 𝑐𝑗𝑖 ) en las iteraciones 6 de las capacidades iniciales (𝐶𝑖𝑗 , 𝐶𝑗𝑖 ) como
se observa a continuación:
8
