Upload
joaquinarce
View
51
Download
5
Embed Size (px)
DESCRIPTION
Breve resumen del flujo maximo para redes en el ambito de la optimizacion, realizado por el profesor de la Universidad Adolfo Ibañez, Alonso Cubillos.
Citation preview
OPTIMIZACINFlujo en RedesEl Problema de Flujo Mximo
El Problema de Flujo Mximo Consideramos un grafo DIRIGIDO G = (N, A). Cada arco tiene una CAPACIDAD uij (eventualmente ). Existen dos nodos especiales: El problema consiste en enviar flujo en la mayor
cantidad posible desde r con destino s. El Problema de Flujo Mximo r N ser el origen s N ser el destino
Optimizacin 2015
El Problema de Flujo MximoOptimizacin 2015
El Problema de Flujo MximoOptimizacin 2015
El Problema de Flujo MximoOptimizacin 2015
El Problema de Flujo Mximo Problema: Dada una red con cotas de flujo en sus arcos,
determinar el mximo flujo posible de enviar entre dos nodos (s y t en el ejemplo)
Optimizacin 2015
El Problema de Flujo Mximo Otra forma de verlo
Optimizacin 2015
Propiedades Conjunto de corte C para G=(N, A) conexo C A tal que si se elimina de G G se desconecta
Optimizacin 2015
Propiedades Conjunto de corte C para G=(N, A) conexo C A tal que si se elimina de G G se desconecta
Optimizacin 2015
Propiedades Conjunto de corte C para G=(N, A) conexo C A tal que si se elimina de G G se desconecta
Optimizacin 2015
Propiedades Conjunto de corte C para G=(N, A) conexo C A tal que si se elimina de G G se desconecta
Optimizacin 2015
Teorema Flujo mximo-corte mnimo El flujo mximo entre el origen y el destino es igual a la
menor capacidad entre TODOS los conjuntos de corte que separan origen y destino
Optimizacin 2015
Ejemplo El flujo mximo entre el origen y el destino es iguala la menor capacidad entre TODOS los conjuntos de corte que separan origen y destino.
Optimizacin 2015
Algoritmo de Ford y Fulkerson 1) Determinar un flujo factible 2) construir un grafo auxiliar:
Los nodos del grafo auxiliar son los mismos que el grafo original Agregamos arcos
Si fij < uij el arco (i,j) se incorpora al grafo auxiliar. Se agrega el arco (i,j) a B1 = conjunto de arcos hacia adelante
Si fij > lij, el arco (j,i) se incorpora al grafo auxiliar. Se agrega el arco (j,i) a B2 = conjunto de arcos hacia atrs
Notar que si lij < fij < uij , debemos agregar 2 arcos: uno hacia delante y otro hacia atrs
Optimizacin 2015
Algoritmo de Ford y Fulkerson 3) Buscar un camino C desde el nodo de origen O al
nodo de destino D Si no existe camino C que una O con D Estamos en el ptimo. Si existe camino C que una O con D, debemos buscar la cantidad
de flujo que podemos aumentar por dicho camino.
4) Actualizamos los flujos (slo para aquellos arcos en C)
Optimizacin 2015
Ejemplo Cunto es el mximo flujo F que se puede enviar de 1 a
6?
Optimizacin 2015
uij
lij=0
Ejemplo Iteracin 1 Base Factible (G)
Optimizacin 2015
0/2
0/3
0/3
0/3
0/10/1
0/1
0/1
0/3
Flujo actual/ cap. superior
0 0
Ejemplo Iteracin 1 Grafo residual(G)
Optimizacin 2015
ij
Ejemplo Iteracin 2 Nuevo flujo Factible (G)
Optimizacin 2015
2/2
2/3
2/3
0/3
0/10/1
0/1
0/1
0/3
Flujo actual/ cap. superior
2 2
Ejemplo Iteracin 2 Grafo residual(G)
Optimizacin 2015
2
3
1
2
1
2
1
3
1 1
ij
1
Ejemplo Iteracin 3 Nuevo flujo Factible (G)
Optimizacin 2015
2/2
2/3
2/3
1/3
0/11/1
0/1
1/1
1/3
Flujo actual/ cap. superior
3 3
Ejemplo Iteracin 3 Grafo residual(G)
Optimizacin 2015
2
2
1
2
1
2
1
2
11
ij
1 1
1
Ejemplo Iteracin 4 Nuevo flujo Factible (G)
Optimizacin 2015
2/2
2/3
2/3
2/3
0/11/1
1/1
1/1
2/3
Flujo actual/ cap. superior
4 4
Ejemplo Iteracin 4 Grafo residual (G)
Optimizacin 2015
2
1
1
2
1
2
1
1
11
ij
2 2
1
Ya no existen rutas factibles en la red residual
Resumen
Optimizacin 2015
Iteracin 1 Camino de aumento de flujo
Flujo adicional
1 1-2-5-6 22 1-3-5-4-6 13 1-3-4-6 14 1.. 0