FLUJO MÁXIMO - ALGORITMO DE FORD-FULKERSON

Modelo del flujo máximo: 

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 cual 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 [∞,-]. Tomamos i=1 y vamos al paso 2.

• Paso 2: Determinamos Si como un conjunto que contendrá los nodos a los que podemos acceder directamente desde i por 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, hacemosi=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 Siactual 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 i es β. Es imposible lograr que tanto αcomo β sean positivas.

 EJEMPLOS:

1.- Hallar el flujo máximo del siguiente problema:

El nodo de origen como se puede observar es el numero 1 de color amarillo, y el nodo de destino es el numero 5 de color azul.

Se escoge desde el nodo de origen aquel flujo que sea el mayor, en este caso es 30, y va dirigido al nodo numero 3

Se identifica el nodo de transbordo como [30,1], 30 es la capacidad, y 1 es el nodo del cual proviene la capacidad y luego repetimos todo el proceso, como si el nodo intermediario fuese el nodo de origen. Se tiene como flujo mayor 20 del nodo numero 3 al nodo numero 5, con el nodo de transbordo como [20,5].

Ahora que hemos llegado al nodo de destino, procedemos a calcular "k" y las capacidades nuevas.

K=min(∞,30,20)

K=20

C13,31 =(30-20, 0+20)

C13,31 =(10, 20)

C35,53 =(20-20, 0+20)

C35,53 =(0, 20)

Luego de haber calculado las nuevas capacidades, es necesario reemplazarlas.

Se realiza el proceso otra vez, haciendo la ruta con los mayores flujos.

K=min(∞,20,40,10,20)

K=10

C12,21 =(20-10, 0+10)

C12,21 =(10, 10)

C23,32 =(40-10, 0+10)

C23,32 =(30, 10)

C34,43 =(10-10, 5+10)

C34,43 =(0, 15)

C45,54 =(20-10, 0+10)

C45,54 =(10, 10)

Volvemos a hacer el proceso y escogemos el camino 1,2. Como se puede observar si se tomara rumbo del nodo 2 al nodo 3 terminaría trancado, obligándose a volver al nodo origen, por lo que se toma el camino 2,5.

K=min(∞,10,20)

K=10

C12,21 =(10-10, 10+10)

C12,21 =(0, 20)

C25,52 =(20-10, 0+10)

C25,52 =(10, 10)

Se actualizan las capacidades y procedemos a resolver de nuevo. Esta vez agarraremos el camino de 1,3.

K=min(∞,10,10,10)

K=10

C13,31 =(10-10, 20+10)

C13,31 =(0, 30)

C32,23 =(10-10, 30+10)

C32,23 =(0, 40)

C25,52 =(10-10, 10+10)

C25,52 =(0, 20)

Y por ultimo escogemos el camino 1,4.

K=min(∞,10,10)

K=10

C14,41 =(10-10, 0+10)

C14,41 =(0, 10)

C45,54 =(10-10, 10+10)

C45,54 =(0, 40)

Reemplazando las nuevas capacidades, nos queda de la siguiente forma,   las capacidades del nodo de origen quedan como 0, por lo cual seguimos a sumar a todas las K y ahi conseguimos el flujo máximo.

Flujo Máximo = Σ K

Flujo Máximo = 20+10+10+10+10

Flujo Máximo = 60

El flujo máximo que puede pasar del nodo origen 1 hasta el nodo destino es de 60.