Articulo Del Tema 2.4. Problema de Flujo Máximo.

2.4. PROBLEMA DE 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, 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 i es β. 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 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}
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].
 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 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 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 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 2: S1={3,4}.
 Paso 2: S3={2}
 Paso 2: S2={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

(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 2: S1={4}.
 Paso 2: S4={3,5}
 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 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

(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:

Articulo Del Tema 2.4. Problema de Flujo Máximo.

Cargado por

Copyright:

Formatos disponibles

Articulo Del Tema 2.4. Problema de Flujo Máximo.

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Articulo Del Tema 2.4. Problema de Flujo Máximo.

Cargado por

Copyright:

Formatos disponibles

2.4. PROBLEMA DE FLUJO MÁXIMO.

En algunas redes circula por los arcos un flujo (envío o circulación de

 El flujo es siempre positivo y con unidades enteras.

En el caso de que el origen o el destino no existan en el problema, se añaden

Las capacidades se identifican como sigue: por ejemplo, para el arco (3,4), el

El algoritmo de Ford-Fulkerson propone buscar caminos en los que se pueda

La idea es encontrar una ruta de penetración con un flujo positivo neto que

Consideraremos las capacidades iniciales del arco que une el nodo i y el

Para un nodo j que recibe el flujo del nodo i, definimos una

 Paso 1: Inicializamos las capacidades residuales a las capacidades

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

 Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.

Entonces la ruta es N1={1,3,5} y f1=min{a1,a3,a5}={∞,30,20}=20. Las

 Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.

Entonces la ruta es N2={1,2,3,4,5} y f2=min{∞,20,40,10,20}=10. Las

 Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.

Entonces la ruta es N2={1,2,5} y f3=min{∞,10,30}=10. Las capacidades

 Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.

Entonces la ruta es N4={1,3,2,5} y f4=min{∞,10,10,20}=10. Las capacidades

 Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.

Entonces la ruta es N2={1,4,5} y f3=min{∞,10,10}=10. Las capacidades

 Paso 6: El flujo máximo en la red es F=f1+f2+…+f5=60 unidades. El flujo

También podría gustarte