Ejemplo Arlgoritmo
  • Determinar el flujo máximo en la red siguiente:

Flujo1.png


Iteracion 1

Flujo2.png

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]. Tomamosi=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)

Iteracion 2

Flujo3.png

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)

Iteracion 3

Flujo4.png

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]. Tomamosi=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)

Iteracion 4

Flujo5.png

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)

Iteracion 5

Flujo6.png

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)

Iteracion 6


Flujo7.png
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:

Tabla.png