En
algunas redes circula por los arcos un flujo (envío o
circulación de unidades homogéneas de algún producto: automóviles en una red de
carreteras, litros de petróleo en un oleoducto, bits por un cable de fibra
óptica) desde el origen o fuente al destino,
también denominado sumidero o vertedero. Los arcos
tienen una capacidad máxima de flujo, y se trata de enviar desde la fuente al
sumidero la mayor cantidad posible de flujo, de tal manera que:
- El flujo es siempre positivo y
con unidades enteras.
- El flujo a través de un arco es
menor o igual que la capacidad.
- El flujo que entra en un nodo es
igual al que sale de él.
En
el caso de que el origen o el destino no existan en el problema, se añaden
ficticiamente utilizando arcos unidireccionales de capacidad infinita, como en
grafo mostrado a continuación:
- Corte: Un corte define una serie de
arcos cuya supresión de la red causa una interrupción completa del flujo
entre el origen y el destino. La capacidad de corte es
igual a la suma de las capacidades de los arcos asociados. Entre todos
los cortes posibles en la red , el corte con la menor
capacidad proporciona el flujo máximo en la red.
El
siguiente grafo ilustra 3 cortes: el Corte 1 con capacidad 60, el Corte 2 con
capacidad 110 y el Corte 3 con capacidad 70. Todo lo que podemos obtener de los
3 cortes es que el flujo máximo en la red no excede de 60 unidades. No podemos
saber cuál es el flujo máximo hasta que se hayan enumerado todos los
cortes en la red:
Las
capacidades se identifican como sigue: por ejemplo, para el arco (3,4),
el límite de flujo es de 10 unidades de 3 a 4 y
de 5 unidades de 4 a 3.
ALGORITMO DE
FORD-FULKERSON
El
algoritmo de Ford-Fulkerson propone buscar caminos en los que se pueda aumentar
el flujo, hasta que se alcance el flujo máximo. La idea es encontrar una ruta
de penetración con un flujo positivo neto que una los nodos origen y
destino.
Consideraremos
las capacidades iniciales del arco que une el nodo i y el
nodo j como Cij y Cji.
Estas capacidades iniciales irán variando a medida que avanza el algoritmo,
denominaremos capacidades residuales a las capacidades
restantes del arco una vez pasa algún flujo por él, las representaremos como cij y cji.
Para un nodo j que recibe el flujo del nodo i,
definimos una clasificación [aj,i] donde aj es
el flujo del nodo i al nodo j.
Los pasos del
algoritmo se definen como sigue:
- Paso 1: Inicializamos las capacidades residuales a las capacidades iniciales, hacemos (cij,cji)=(Cij,Cji) para todo arco de la red. Suponiendo el nodo 1 como el nodo origen, hacemos a1=∞ y clasificamos el nodo origen con [∞,-]. Tomamosi=1 y vamos al paso 2.
- Paso
2: Determinamos Si como
un conjunto que contendrá los nodos a los que podemos acceder directamente
desde ipor medio de un arco con capacidad positiva, y que no
formen parte del camino en curso. Si Si contiene algún
nodo vamos al paso 3, en el caso de que el conjunto sea vacío saltamos al
paso 4.
- Paso
3: Obtenemos kЄSi como
el nodo destino del arco de mayor capacidad que salga de i hacia
un nodo perteneciente a Si. Es decir, cik =
max{cij} con jЄSi. Hacemos ak=cik y
clasificamos el nodo k con [ak,i].
Si k es igual al nodo destino o sumidero, entonces hemos
encontrado una ruta de penetración, vamos al paso 5. En caso contrario
continuamos con el camino, hacemos i=k y volvemos al paso
2.
- Paso
4 (retroceso): Si i=1,
estamos en el nodo origen, y como Si es vacío, entonces
no podemos acceder a ningún nodo, ni encontrar algún nuevo camino, hemos
terminado, vamos al paso 6.
En caso contrario, i≠1, le damos al valor i el del nodo que se ha clasificado inmediatamente antes, eliminamos i del conjunto Si actual y volvemos al paso 2. - Paso
5: Llegados
a este paso tenemos un nuevo camino: Np={1,k1,k2,…,n},
esta será la p-ésima ruta de penetración desde el nodo
origen al nodo destino. El flujo máximo a lo largo de esta ruta será la
capacidad mínima de las capacidades residuales de los arcos que forman el
camino, es decir: fp=min{a1,ak1,ak2,…,an}.
La capacidad residual de cada arco a lo largo de la ruta de penetración se disminuye por fp en dirección del flujo y se incrementa por fp en dirección inversa, es decir, para los nodos i y j en la ruta, el flujo residual se cambia de la (cij,cji)actual a (cij-fp,cji+fp) si el flujo es de i a j, o (cij+fp,cji-fp) si el flujo es de j a i
Inicializamos i=1 y volvemos al paso 2 para intentar una nueva ruta de penetración. - Paso
6 (solución): Una
vez aquí, hemos determinado m rutas de penetración. El flujo
máximo en la red será la suma de los flujos máximos en cada ruta obtenida,
es decir: F=f1+f2+…+fm. Teniendo en cuenta que las
capacidades residuales inicial y final del arco (i, j) las
dan (Cij,Cji) y (cij,cji) respectivamente,
el flujo máximo para cada arco se calcula como sigue: sea (α,
β)=(Cij-cij, Cji-cji), si α>0, el flujo óptimo de i a j es α,
de lo contrario, si β>0, el flujo óptimo de j a ies β.
Es imposible lograr que tanto α como β sean
positivas.
Ejemplo: Determinar
el flujo máximo en la red siguiente:
Iteración
1:
Determinamos
las residuales iniciales (cij,cji) iguales a las capacidades
iniciales (Cij,Cji).
- Paso 1: Hacemos ai=∞, y
clasificamos el nodo 1 con [a1,-]. Tomamos i=1.
- Paso 2: S1={2,3,4} (no
vacío).
- Paso 3: k=3 ya
que c13=max{c12,c13,c14}={20,30,10}=30. Hacemos a3=c13=30 y
clasificamos el nodo 3 con [30,1]. Tomamos i=3 y
repetimos el paso 2.
- Paso 2: S3={4,5}
- Paso 3: k=5 y a5=c35=max{10,20}=20.
Clasificamos el nodo 5 con [20,3]. Logramos la penetración,
vamos al paso 5.
- Paso 5: La ruta de la penetración
se determina de las clasificaciones empezando en el nodo 5 y terminando en
el nodo 1, es decir, 5→[20,3]→3→[30,1]→1.
Entonces la
ruta es N1={1,3,5} y f1=min{a1,a3,a5}={∞,30,20}=20.
Las capacidades residuales a lo largo de esta ruta son:
(c13,c31)=(30-20, 0+20)=(10,20)
(c35,c53)=(20-20, 0+20)=(0,20)
Iteración
2:
- Paso 1: Hacemos ai=∞, y
clasificamos el nodo 1 con [a1,-]. Tomamos i=1.
- Paso 2: S1={2,3,4}.
- Paso 3: k=2 y a2=c12=max{20,10,10}=20.
Clasificamos el nodo 2 con [20,1]. Tomamos i=2 y
repetimos el paso 2.
- Paso 2: S2={3,5}
- Paso 3: k=3 y a3=c23=max{30,40}=40.
Clasificamos el nodo 3 con [40,2]. Tomamos i=3 y
repetimos el paso 2.
- Paso 2: S3={4} (c35=0, el
nodo 1 ya ha sido clasificado y el nodo 2 cumple ambas condiciones, por
tanto los nodos 1, 2 y 5 no pueden ser incluidos en S3).
- Paso 3: k=4 y a4=c34=10.
Clasificamos el nodo 4 con [10,3]. Tomamos i=4 y
repetimos el paso 2.
- Paso 2: S4={5}
- Paso 3: k=5 y a5=c45=20.
Clasificamos el nodo 5 con [20,4]. Logramos la penetración,
vamos al paso 5.
- Paso 5: La ruta de la penetración
es: 5→[20,4]→4→[10,3]→3→[40,2]→2→[20,1]→1.
Entonces la
ruta es N2={1,2,3,4,5} y f2=min{∞,20,40,10,20}=10.
Las capacidades residuales a lo largo de esta ruta son:
(c12,c21)=(20-10, 0+10)=(10,10)
(c23,c32)=(40-10, 0+10)=(30,10)
(c34,c43)=(10-10, 5+10)=(0,15)
(c45,c54)=(20-10, 0+10)=(10,10)
Iteración
3:
- Paso 1: Hacemos ai=∞, y
clasificamos el nodo 1 con [a1,-]. Tomamos i=1.
- Paso 2: S1={2,3,4}.
- Paso 3: k=2 y a2=c12=max{10,10,10}=10,
rompemos el empate arbitrariamente. Clasificamos el nodo 2 con [10,1].
Tomamos i=2 y repetimos el paso 2.
- Paso 2: S2={3,5}
- Paso 3: k=3 y a3=c23=max{30,30}=30.
Clasificamos el nodo 3 con [30,2]. Tomamos i=3 y
repetimos el paso 2.
- Paso 2: S3 vacío ya
que c34=c35=0. Vamos al paso 4 para retroceder.
- Paso 4: La clasificación [30,2] nos
dice que el nodo inmediatamente precedente es el 2. Eliminamos el nodo 3
de una consideración posterior en esta iteración. Tomamos i=2 y
repetimos el paso 2.
- Paso 2: S2={5}
- Paso 3: k=5 y a5=c25=30.
Clasificamos el nodo 5 con [30,2]. Logramos la penetración,
vamos al paso 5.
- Paso 5: La ruta de la penetración
es: 5→[30,2]→2→[10,1]→1.
Entonces la
ruta es N2={1,2,5} y f3=min{∞,10,30}=10.
Las capacidades residuales a lo largo de esta ruta son:
(c12,c21)=(10-10, 10+10)=(0,20)
(c25,c52)=(30-10, 0+10)=(20,10)
Iteración 4:
- Paso 1: Hacemos ai=∞, y
clasificamos el nodo 1 con [a1,-]. Tomamos i=1.
- Paso 2: S1={3,4}.
- Paso 3: k=3 y a3=c13=max{10,10}=10.
Clasificamos el nodo 3 con [10,1]. Tomamos i=3 y
repetimos el paso 2.
- Paso 2: S3={2}
- Paso 3: k=2 y a2=c32=10.
Clasificamos el nodo 2 con [10,3]. Tomamos i=2 y
repetimos el paso 2.
- Paso 2: S2={5}
- Paso 3: k=5 y a5=c25=20.
Clasificamos el nodo 5 con [20,2]. Logramos la penetración,
vamos al paso 5.
- Paso 5: La ruta de la penetración
es: 5→[20,2]→2→[10,3]→3→[10,1]→1.
Entonces la
ruta es N4={1,3,2,5} y f4=min{∞,10,10,20}=10.
Las capacidades residuales a lo largo de esta ruta son:
(c13,c31)=(10-10, 20+10)=(0,30)
(c32,c23)=(10-10, 30+10)=(0,40)
(c25,c52)=(20-10, 10+10)=(10,20)
Iteración
5:
- Paso 1: Hacemos ai=∞, y
clasificamos el nodo 1 con [a1,-]. Tomamos i=1.
- Paso 2: S1={4}.
- Paso 3: k=4 y a4=c14=10.
Clasificamos el nodo 4 con [10,1]. Tomamos i=4 y
repetimos el paso 2.
- Paso 2: S4={3,5}
- Paso 3: k=3 y a3=c23=max{15,10}=15.
Clasificamos el nodo 3 con [15,4]. Tomamos i=3 y
repetimos el paso 2.
- Paso 2: S3 vacío ya
que c32=c34=c35=0. Vamos al paso 4 para retroceder.
- Paso 4: La clasificación [15,4] nos
dice que el nodo inmediatamente precedente es el 4. Eliminamos el nodo 3
de una consideración posterior en esta iteración. Tomamos i=4 y
repetimos el paso 2.
- Paso 2: S4={5}
- Paso 3: k=5 y a5=c45=10.
Clasificamos el nodo 5 con [10,4]. Logramos la penetración,
vamos al paso 5.
- Paso 5: La ruta de la penetración
es: 5→[10,4]→4→[10,1]→1.
Entonces la
ruta es N2={1,4,5} y f3=min{∞,10,10}=10.
Las capacidades residuales a lo largo de esta ruta son:
(c14,c41)=(10-10, 0+10)=(0,10)
(c45,c54)=(10-10, 10+10)=(0,20)
Iteración
6:
No son
posibles más penetraciones, debido a que todos los arcos fuera del nodo 1
tienen residuales cero. Vayamos al paso 6 para determinar la solución.
- Paso 6: El
flujo máximo en la red es F=f1+f2+…+f5=60
unidades. El flujo en los diferentes arcos se calcula restando las
últimas residuales obtenidas en la última iteración de las capacidades
iniciales: