INVESTIGACIÓN DE
OPERACIONES 2
PROFESORA: PAULINA BERRÍOS ZAMORA
[Link]@[Link]
FLUJO MÁXIMO
FLUJO MÁXIMO
Todo flujo a través de una red dirigida se origina en un nodo (origen) y termina en otro
nodo (destino).
Los nodos restantes son nodos de trasbordo
El flujo a través de un arco se permite sólo en la dirección indicada por la flecha y la
cantidad máxima de flujo está dada por la capacidad del arco.
Objetivo Maximizar la cantidad total de flujo del origen al destino. Se puede medir como
la cantidad que sale del origen o la cantidad que entra al destino.
FLUJO MÁXIMO
Algunas aplicaciones
A continuación se mencionan algunos tipos de
aplicaciones comunes del problema del flujo máximo.
• 1. Maximizar el flujo a través de la red de
distribución de una compañía desde sus fábricas
hasta
• sus clientes.
• 2. Maximizar el flujo a través de la red de
suministros de una compañía de proveedores a
las
• fábricas.
• 3. Maximizar el flujo de petróleo por un sistema
de tuberías.
• 4. Maximizar el flujo de agua a través de un
sistema de acueductos.
• 5. Maximizar el flujo de vehículos por una red de
transporte.
ALGORITMO FORD- FULKERSON
1. Busque una ruta entre el nodo origen y el nodo destino, con la mayor capacidad positiva posible y
de sencilla visualización.
2. Busque la capacidad mínima en ésta ruta y aumente el flujo por ese valor.
3. Disminuya las capacidades en la dirección del flujo y auméntelas en la dirección contraria.
5
2
Iteración 1: = O-B –E- T . Capacidad de la ruta { 7, 5,6}
Cantidad enviada por la ruta = min { 7, 5,6} =5
ALGORITMO FORD- FULKERSON
4. Repita los pasos 1,2 y 3 hasta que no encuentre una ruta con capacidad positiva.
2 6 5 + 3 =8
2
Iteración 2: = O-A –D- T . Capacidad de la ruta { 5, 3,9}
Cantidad enviada por la ruta = min { 5, 3,9}=3
ALGORITMO FORD- FULKERSON
4. Repita los pasos 1,2 y 3 hasta que no encuentre una ruta con capacidad positiva.
0
4
2 6 8 + 2 =10
2 0
2
Iteración 3: = O-B –D- T . Capacidad de la ruta { 2, 4,6}
Cantidad enviada por la ruta = min { 2, 4,6}=2
ALGORITMO FORD- FULKERSON
4. Repita los pasos 1,2 y 3 hasta que no encuentre una ruta con capacidad positiva.
0
4
2 6 10 + 1 =11
2 0
2
0
3
1
0
3
Iteración 4: = O-C –E- T . Capacidad de la ruta { 4, 4,1}
Cantidad enviada por la ruta = min { 4, 4,1}=1
ALGORITMO FORD- FULKERSON
4. Repita los pasos 1,2 y 3 hasta que no encuentre una ruta con capacidad positiva.
0 3
4
2 6 11 + 1=12
2 0
2
0
3
0
2
1
0
3
2
Iteración 4: = O-C –E- D- T . Capacidad de la ruta { 3, 3,1,4}
Cantidad enviada por la ruta = min { 3, 3,1,4}=1
ALGORITMO FORD- FULKERSON
4. Repita los pasos 1,2 y 3 hasta que no encuentre una ruta con capacidad positiva.
2
0 3
1
0 4
2 6 12 + 1=13
2 0
2 1
0
3
0
2
1
0
3
2
Iteración 5: = O-A –B- D- T . Capacidad de la ruta { 2, 1,2,3}
Cantidad enviada por la ruta = min {2, 1,2,3}=1
5. Ya no existen trayectorias de aumento, por lo que el patrón de flujo actual es óptimo.
EJERCICIO 1
D 6
5
A
4
8
4
2 F T
O C
3 2
5
3
E 6
B
4
RESULTADO
• 0-A-D-T=5
D 1
• 0-B-E-T=4 0
• 0-A-C-F-T=2
A
• 0-A-C-E-F-I=1
FLUJO MÁXIMO= 12 1
0
1
0 F T
O C
3 1
1
2
E 2
B
0
EJERCICIO 2
E 2
6
B 8
7
10
8 3
A C T
1
5
F
9
D
10
RESULTADO
• A-B-C-D-F-T =4
E 0
• A-C-F-T =3 2
• A-B-E-T =2
B 5
• A-B-E-F-T=2
FLUJO MÁXIMO= 11 3
2
5 0
A C T
0
5
F 0
D
6
Fechas importantes
Taller 1 grupal 01 Octubre ( Ruta +corta)
Taller 2 grupal 15 de octubre
Prueba 1 22 de octubre
Taller 3 grupal 12 de noviembre
Taller 4 Grupal 26 de noviembre
Prueba 2 5 de enero
Presentación Proyecto ( Exposición) 07, 12, y 14 de Enero
