Cap.
IV Flujo en Redes
Parte 3
4.- PROBLEMA DEL FLUJO MÁXIMO.-
La idea es encontrar una ruta de penetración con un flujo positivo neto que una
los puntos origen y vertedero.
Las capacidades del arco (i,j) se designan como
Las residuales (o capacidades restantes) del arco se cambian conforme
avanza el algoritmo.
Para un nodo j que recibe flujo del nodo i, se define una “clasificación” [aj , i]
donde aj es el flujo que va del nodo i al j
4.- PROBLEMA DEL FLUJO MÁXIMO.-
ALGORITMO
Paso 1.- Para todos los arcos (i,j) determinar la capacidad residual igual a la
capacidad inicial. Sea a1 = ∞ y clasificar el punto origen como [ ∞ ,-].
Determinar i = 1 y luego ir al paso 2.
Paso 2.- Si son los nodos “no clasificados” a los que se puede llegar desde el
nodo i. Si Si ≠ 0, ir al paso 3. De lo contrario al paso 4.
Paso
Paso 3.-
3.- Determinar
Determinar kk Є Є Si
Si ; tal que
Determinar ak = Cik y clasificar el nodo k con [ak , i]. Si se ha llegado al nodo
vertedero, ir al paso 5; de lo contrario, determinar i = k e ir al paso 2.
Paso 4.- (retroceso) Si i=1, y no son posibles otras penetraciones adicionales, ir
al paso 6;
de lo contrario, sea r el nodo clasificado inmediatamente antes del nodo actual i,
eliminar i del conjunto de nodos adyacentes a r. determinar i=r e ir al paso 2
4.- PROBLEMA DEL FLUJO MÁXIMO.-
Paso 5.- (determinación de la red residual). Np = {1, k1,k2, ….,kn}, define los
nodos de la ruta de penetración desde el origen al vertedero.
El flujo máximo a lo largo de la ruta es: fp = min{a1, ak1,ak2,...,an}
La capacidad residual de cada arco a lo largo de la ruta se disminuye por fp en
dirección del flujo y se incrementa por fp en dirección inversa; es decir, para los
nodos de la ruta el flujo residual cambia a: (Cij – fp, Cji + fp).
Determinar i=1 y regresar al paso 2.
Paso 6.- (solución)
a) Dado que se han determinado m rutas de penetración, el flujo máximo se
calcula como:
F= f1+f2+….+fm
b) El flujo óptimo se calcula como sigue:
Digamos que (α, β) =
Sea α > 0; el flujo óptimo de i a j es α, de lo contrario, si es β, el flujo es de j a i.
(es imposible que tanto α como β sean positivas).
4.- PROBLEMA DEL FLUJO MÁXIMO.-
Ejemplo Determinar el flujo máximo en la red de la figura.
4.- PROBLEMA DEL FLUJO MÁXIMO.-
1ra Iteración:
f1= min{30,20} = 20
[20,3]
30-20 0+20
[∞,-]
0+20
20-20
[30,1]
4.- PROBLEMA DEL FLUJO MÁXIMO.-
2da Iteración: [10, 3]
f2= min{20,40,10, 20} = 10 4
20-10
20
0
5
5+10
0+10
0
0 5
[20, 4]
10
[∞, -] 1 20
10
20
20-10 10-10
10
30 20
2 3
0+10
0 0
40
40-10 0
0+10
[20, [40, 2]
1]
4.- PROBLEMA DEL FLUJO MÁXIMO.-
3ra Iteración:
f3= min{10,30} = 10 0 4 10
15
10 [30,2]
00+10 5
10
[∞, -] 1
10
20
10-10
10 0
30
30-10 20
10
10+10 2 3 0
30 10
[10,1] [30,2]
retroceso
4.- PROBLEMA DEL FLUJO MÁXIMO.-
4ta Iteración:
f4= min{10, 10, 20} = 10
0 4 10
15
10 [20,2]
10
10+10 5
[∞, -] 10
1 20
10-10
10
0
20-10
20 20
20+10 0
20 2 3 0
30+10
30 10
10-10
[10,3] [10,1]
4.- PROBLEMA DEL FLUJO MÁXIMO.-
5ta Iteración:
f5= min{10, 10} = 10
[10,1]
00+10 4 10-10
10
15
10
10+10
10-10
10 20 5 [10,4]
20
[∞, -] 1
0
0
10 0
30
20 2 3 0
40 0
[15,4]
retroceso
4.- PROBLEMA DEL FLUJO MÁXIMO.-
5ta Iteración:
NO HAY 10 4 0
PENETRACION
15
20
20 5
0
1 20
0
0
0
10 30
20 2 3 0
40 0
Se ha llegado a la solución óptima.
El flujo máximo es: F = f1 + f2 + f3 + f4 + f5 = 20+10+10+10+10=60
4.- PROBLEMA DEL FLUJO MÁXIMO.-
Se encuentran los flujos óptimos en los arcos, restando las residuales
finales de las capacidades iniciales
0 4 20 10 4 0
5 15
0 20
0 5 20 5
0
10
1 30 0 1 20
0
20 0
10 0
30 0 10 30 FINAL
INICIAL 0 2
40 0
3 20 20 2
40 0
3 0
4.- PROBLEMA DEL FLUJO MÁXIMO.-
Ejemplo 2.- Encontrar el flujo máximo y los flujos óptimos en los
arcos de la red de la figura:
10
0 3
10 9
14
0
1 4 0
5
0
8
0
5 6 7
0 2 4 5
7
0
