03
REDES Y ALGORITMOS
Flujo máximo
[Link]@[Link]
FLUJO MÁXIMO
• Considere una red de oleoductos que transporta petróleo crudo desde pozos hasta refinerías.
• Se instalan estaciones intermedias de reforzamiento y bombeo a distancias apropiadas para mover el crudo en la red.
• Cada segmento de tubería tiene una velocidad de descarga finita (o capacidad) de flujo de crudo.
• Un segmento de tubería puede ser unidireccional o bidireccional, según su diseño.
• La figura muestra una red de oleoductos típica.
• El objetivo es determinar la capacidad de flujo máxima de la red.
• La solución del problema propuesto requiere agregar una sola fuente y un solo sumidero o vertedero, utilizando arcos de
capacidad infinita unidireccionales, como se muestra mediante los arcos de rayas en la figura.
( )
• Para el arco (i,j), la notación Cij , C ji proporciona las capacidades de flujo en las
dos direcciones i → j y j → i.
• Para eliminar la ambigüedad, colocamos Cij a junto al nodo i y a C ji junto al
nodo j, como se muestra en la figura siguiente.
Enumeración de cortes
• Un corte define un conjunto de arcos cuya eliminación de la red interrumpe el
flujo entre los nodos fuente y sumidero.
• La capacidad de corte es igual a la suma de las capacidades de su conjunto de
arcos.
• Entre todos los cortes posibles en la red, el corte con la capacidad mínima es el
cuello de botella que determina el flujo máximo en la red.
Ejemplo
• Considere la red de la figura. Las capacidades bidireccionales se muestran en los arcos
respectivos por medio de la convención utilizada en la figura anterior. Por ejemplo, el límite
de flujo para el arco (3,4) es de 10 unidades de 3 a 4, y de 5 unidades de 4 a 3. La figura
siguiente ilustra tres cortes con las siguientes capacidades:
• La única información de los tres cortes es que el flujo máximo en la red no puede exceder de
60 unidades. Para determinar el flujo máximo es necesario enumerar todos los cortes, una
tarea difícil para la red general. Por lo tanto, la necesidad de un algoritmo eficiente es
imperativa.
ALGORITMO DE FLUJO MÁXIMO
• Este algoritmo se basa en el hallazgo de rutas de avance con flujo positivo entre los nodos
fuente y sumidero.
• Cada ruta destina una parte de o todas las capacidades de sus arcos al flujo total en la red.
• Considere el arco (i, j) con las capacidades bidireccionales (de diseño)
• Como algunas partes de estas capacidades se destinan al flujo en el arco, los residuos
(capacidades no utilizadas, o flujo remanente) del arco se actualizan.
• Utilizamos la notación (cij, cji) para representar los residuos.
• Para un nodo j que recibe flujo del nodo i, anexamos la etiqueta [aj,i] donde aj es el flujo del
nodo i al nodo j.
• Paso 1. Para todos los arcos, iguale la capacidad residual a la capacidad de diseño, esto es
.
(cij , c ji ) = (Cij , C ji )
• Sea a1 = , y etiquete el nodo fuente con [ , -].
• Designe i = 1, y continúe con el paso 2.
• Paso 2. Determine Si, el conjunto de nodos no etiquetados j al que se puede llegar
directamente desde i por medio de arcos con residuos positivos (es decir, cij > 0 para todas
las j ϵ Si). Si ≠ , continúe con el paso 3. De lo contrario, una ruta parcial termina en el nodo
i. Continúe con el paso 4.
• Paso 3. Determine k ϵ Si de modo que
• Designe ak = cik y etiquete el nodo k con [ak, i]. Si k = n, el nodo sumidero ha sido etiquetado,
y se ha encontrado una ruta de avance, continúe con el paso 5. De lo contrario, designe i =k,
y vaya al paso 2.
• Paso 4. (Retroceso). Si i = 1, no es posible avanzar; continúe con el paso 6. De lo
contrario, sea r el nodo (en la ruta parcial) que se etiquetó inmediatamente antes
del nodo actual i, y elimine i del conjunto de nodos adyacentes a r. Designe i = r, y
regrese al paso 2.
• Paso 5. (Determinación de los residuos). Defina los nodos de la ruta de avance p-
ésima del nodo 1 al nodo n como Np = (1, k1, k2,…, n). Entonces el flujo máximo a
lo largo de la ruta se calcula como
• La capacidad residual de cada arco a lo largo de la ruta de avance se reduce en fp
en la dirección del flujo, y se incrementa en fp en la dirección inversa; es decir,
para los nodos i y j en la ruta, el flujo residual cambia del actual (cij, cji) a
a) (cij - fp, cji + fp) si el flujo es de i a j.
b) (cij + fp, cn - fp) si el flujo es de j a i.
• Restaure los nodos que se eliminaron en el paso 4.
• Designe i = 1, y regrese al paso 2.
• Paso 6. (Solución)
a) Dado que se determinaron m rutas de avance, el flujo máximo en la red es
b) Utilizando las capacidades de diseño (iniciales) y los residuos finales del arco (i,j)
(C , C ) y (c , c ) respectiva mente
ij ji ij ji
el flujo óptimo en el arco (i,j) se determina calculando
( , ) = (Cij − cij , C ji − c ji )
Si α > 0, el flujo óptimo de i a j es α.
Por otra parte, si > 0, el flujo óptimo de j a i es .
Es imposible que α y sean positivos al mismo tiempo.
• El proceso de retroceso del paso 4 se invoca cuando el algoritmo termina en un nodo intermedio.
• El ajuste del flujo en el paso 5 puede explicarse mediante la red de flujo simple de la figura siguiente.
• La red (a) proporciona la primera ruta de avance N1[1, 2,3, 4] con su flujo máximo f1 = 5. Por lo tanto, los
residuos de cada uno de los arcos (1, 2), (2, 3) y (3, 4) cambian de (5, 0) a (0, 5), de acuerdo con el paso 5.
• La red (b) da ahora la segunda ruta de avance N2 = [1, 3, 2, 4] con f2 = 5. Después de hacer los ajustes del flujo
necesarios, obtenemos la red (c), donde ya no son posibles más rutas de avance.
• Lo que sucedió en la transición de (b) a (c) no fue sino una cancelación del flujo
previamente comprometido en la dirección 2 → 3, y en esencia ello permite el
flujo sólo en las rutas 1 → 2 → 4 y 1 → 3 → 4 (flujo máximo = 5 + 5 = 10.)
• El algoritmo “recuerda” que un flujo de 2 a 3 se comprometió previamente debido
a un ajuste anterior de la capacidad en la dirección inversa (de acuerdo con el
paso 5.)
EJEMPLO
• Determinar el flujo máximo de la figura:
• El flujo máximo en la red es F = f1 + f2 +… + f5 = 20 + 10 + 10 + 10 + 10 = 60
unidades.
• El flujo en los arcos individuales se calcula restando los últimos residuos (cij, cji) en
la iteración 6 de las capacidades de diseño , como lo muestra la siguiente tabla.
Ejercicios
03
REDES Y ALGORITMOS
Flujo máximo
[Link]@[Link]
