FLUJO MAXIMO

Vista previa del material en texto

FLUJO MÁXIMO 
 
Existe un flujo que viaja desde un único lugar de origen hacia un único lugar de destino a 
través de arcos que conectan nodos intermediarios. Los arcos tienen una capacidad máxima 
de flujo y se trata de enviar desde la fuente al destina la mayor cantidad posible de flujo. 
 
 
Hay problemas donde lo importante es la cantidad de flujo que pasa a través de la red como 
por ejemplo: en las líneas de oleoductos, redes eléctricas o de transmisión de datos. Por 
esta razón en dichos problemas se determina el flujo máximo que pasa a través de una red. 
 
Definiciones básicas 
 
Flujo: Circulación de unidades homogéneas de un lugar a otro. 
 
Capacidad de flujo: es la capacidad de unidades que pueden entrar por el nodo fuente y 
salir por el nodo destino. 
 
Origen o fuente de flujo: nodo por el cual el flujo ingresa. 
 
Destino o Sumidero de flujo: nodo por el cual el flujo sale. 
 
Capacidades residuales: capacidades restantes unas vez que el flujo pasa el arco. 
 
Ford Fulkerson 
Para la resolución de problemas de flujo máximo se requiere el uso del método Ford 
Fulkerson. Este método 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 de origen y destino. 
 
 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. 
 
Resolución de problema 
Para resolver un problema de flujo máximo se debe seguir los siguientes pasos: 
1. Se identifica el nodo origen y destino. 
http://1.bp.blogspot.com/-EUVd1F9o1JY/UVi2aSET3LI/AAAAAAAAAGw/bvyFmq9fA0w/s1600/Picture15555.png
2. Se parte desde el nodo de origen y se escoge el arco que posea mayor flujo 
3. Se identifica los nodos de transbordo. 
4. Repetir como si el nodo intermediario fuera el nodo origen. 
5. Se calcula "k" y las capacidades nuevas. 
6. Dado el resultado se cambian las capacidades y se repite el mismo procedimiento desde el 
inicio. 
 
Formulario 
Cij,ji =(Ci-K, Cj+K), donde: 
 
C: capacidad 
Ij: índices de los nodos 
K: es el minimo flujo que pasa por el nodo, se calcula como k= min(capacidades de la ruta). 
 
 
Hallar el flujo máximo del siguiente problema: 
 
Método Ford Fulkerson 
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. 
http://2.bp.blogspot.com/-b5f9J1MNEe0/UVjAuR7_CWI/AAAAAAAAAG4/K2ANESmwRik/s1600/PROBLEM.png
http://2.bp.blogspot.com/-RsVs39Zezi0/UVjBmUiqI3I/AAAAAAAAAHA/21xVQ_Ji2oo/s1600/ssssss.png
 
 
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) 
http://2.bp.blogspot.com/-dw5oh_JAk10/UVjCf4SabYI/AAAAAAAAAHI/iX39BDVTlnI/s1600/Picture12222.png
http://2.bp.blogspot.com/-Vu7YqyTmVp0/UVjKuLLPWtI/AAAAAAAAAHY/fN13F5wK8D0/s1600/13.png
http://2.bp.blogspot.com/-qrI7LQcbnEk/UVjPh-nyECI/AAAAAAAAAHg/wojg5bR95f0/s1600/47.png
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) 
 
http://2.bp.blogspot.com/-oQHz3ePKG-k/UVjRmhThjpI/AAAAAAAAAHo/JFrBkT496sE/s1600/14.png
http://1.bp.blogspot.com/-MekODDaoprU/UVjTB4k550I/AAAAAAAAAH4/7sH5Xinjtv8/s1600/16.png
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 
http://3.bp.blogspot.com/-5oE6kOXLaIc/UVjZpi6fnbI/AAAAAAAAAIE/nYKBq93qD0U/s1600/17.png
http://3.bp.blogspot.com/-SHnDyYCfVVo/UVjbqTZM-ZI/AAAAAAAAAIM/SsWW7dm6LhA/s1600/18.png
 
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. 
 
http://4.bp.blogspot.com/-oWxITSthZcY/UVjdm0biccI/AAAAAAAAAIU/7Fvk4gcSn9s/s1600/40.png
 
 
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. 
 
http://3.bp.blogspot.com/-9w96UFPAIN8/UVje3a2ADcI/AAAAAAAAAIc/Po-PHqM1DxA/s1600/finl.png