METODO DE FLUJO MAXIMO

Vista previa del material en texto

Luis Medina Aquino
CICLO 2014-1
INVESTIGACION DE OPERACIONES II
1
2
Modelo Flujo Máximo
Luis Medina Aquino
2
El problema de flujo máximo
	Considere una red con un nodo de entrada, o nodo fuente, y uno de salida o nodo sumidero. El problema de flujo máximo pregunta, ¿cuál es la cantidad máxima de flujo (es decir, vehículos, mensajes, líquidos, etc.) que puede entrar y salir del sistema de red en un período determinado de tiempo?
3
El problema de flujo máximo
	En este problema se intenta transmitir flujo sobre todas las ramas (arcos) de la red en la forma más eficiente posible. La cantidad de flujo está limitada debido a restricciones de capacidad en las diversas ramas de la red. Por ejemplo, los tipos de carreteras limitan el flujo de vehículos en un sistema de transporte. 
4
El problema de flujo máximo
	Al límite máximo o superior sobre el flujo de una rama se le denomina la capacidad de flujo de la rama. Aunque no se especifican cantidades para los nodos, se supone que el flujo que sale de un nodo es igual al flujo que ingresa. 
5
Problema
 Considere un sistema de pistas en la provincia del Callao. Debido a un programa de mantenimiento de pistas exige el cierre temporal de carriles y una reducción en los límites de la ciudad, un comité de planeación del transporte ha propuesto una red de rutas alternativas que cruzan la ciudad de norte a sur. En la siguiente figura se muestra la red que se propone: 
 
6
Problema 
2
4
3
5
7
6
5
5
3
3
0
0
0
6
0
1
Entrada al Callao
Capacidad de flujo de 80 vehículos por hora del nodo 5 al nodo 7
Red de pistas y capacidades de flujo (en decenas de vehículos por hora) para el problema del Callao
Salida del Callao
0
0
0
0
0
2
2
3
7
8
0
5
7
1
1
Nodo fuente
Nodo sumidero
7
Algoritmo
 El algoritmo que se presenta utiliza los siguientes pasos de sentido común:
Encontrar cualquier camino del nodo de entrada (fuente) al nodo de salida (sumidero) que tenga capacidades de flujo, en el sentido del flujo, mayores de cero, para todas las ramas del camino. Si no hay caminos disponibles, se habrá encontrado la solución óptima
 
8
Algoritmo 
2
4
3
5
7
6
5
5
3
3
0
0
0
6
0
1
0
0
0
0
0
2
2
3
7
8
0
5
7
1
1
Iteración # 1: El camino seleccionado es 1-3-6-7
9
Algoritmo
2. Sea Cmin la capacidad mínima de flujo de entre todos los arcos seleccionados en el paso 1. Se aumenta el flujo existente a través de la red al enviar un flujo adicional de Cmin sobre este camino.
 
10
Algoritmo 
2
4
3
5
7
6
5
5
3
3
0
0
0
6
0
1
0
0
0
0
0
2
2
3
7
8
0
5
7
1
1
Iteración # 1: CMin, se determina mediante la rama 1-3, siendo su valor 6
11
Algoritmo
3. Por este mismo camino, disminúyanse las capacidades en la dirección del flujo en cada arco, en la cantidad CMin. Auméntense las capacidades en la dirección opouesta en CMin, para todos los arcos del camino.
 
12
Algoritmo 
2
4
3
5
7
6
5
5
3
3
0
0
0
6
0
1
0
0
0
0
0
2
2
3
7
8
0
5
7
1
1
Iteración # 1: CMin, que se determina mediante la rama 1-3, es 6. La red modificada es la siguiente:
6
1
6
6
1
0
6
6
13
Algoritmo 
2
4
3
5
7
6
5
5
3
3
0
0
6
0
6
1
0
6
0
0
0
2
2
3
1
8
0
5
1
1
1
Iteración # 2: El camino seleccionado es 1-2-5-7
6
6
14
Algoritmo 
2
4
3
5
7
6
5
5
3
3
0
0
6
0
6
1
0
6
0
0
0
2
2
3
1
8
0
5
1
1
1
Iteración # 2: CMin, que se determina mediante la rama 2-5, es 3. La red modificada es la siguiente:
6
6
0
9
3
5
3
9
3
2
15
Algoritmo 
2
4
3
5
7
6
2
5
3
0
3
0
6
0
6
1
3
6
0
3
0
2
2
3
1
5
0
5
1
1
1
Iteración # 3: El camino seleccionado es 1-2-3-5-7
6
6
9
9
16
Algoritmo 
2
4
3
5
7
6
2
5
3
0
3
0
6
0
6
1
3
6
0
3
0
2
2
3
1
5
0
5
1
1
1
Iteración # 3: CMin, que se determina mediante la rama 1-2 (o 2-3), es 2. La red modificada es la siguiente:
6
6
9
9
0
5
3
5
11
11
0
4
1
2
17
Algoritmo 
2
4
3
5
7
6
0
5
3
0
5
2
6
0
6
1
5
6
0
3
0
4
0
1
1
3
0
5
1
1
1
Iteración # 4: El camino seleccionado es 1-4-6-7
6
6
9
9
11
11
18
Algoritmo 
2
4
3
5
7
6
0
5
3
0
5
2
6
0
6
1
5
6
0
3
0
4
0
1
1
3
0
5
1
1
1
Iteración # 4: CMin, que se determina mediante la rama 6-7, es 1. La red modificada es la siguiente:
6
6
9
9
11
11
12
12
4
1
4
1
0
7
19
Algoritmo 
2
4
3
5
7
6
0
4
3
0
5
2
6
0
7
1
5
6
1
3
0
4
0
1
1
3
1
4
0
1
1
Iteración # 5: El camino seleccionado es 1-4-6-5-7
6
6
9
9
11
11
12
12
20
Algoritmo 
2
4
3
5
7
6
0
4
3
0
5
2
6
0
7
1
5
6
1
3
0
4
0
1
1
3
1
4
0
1
1
Iteración # 5: CMin, que se determina mediante la rama 6-5, es 1. La red modificada es la siguiente:
6
6
9
9
11
11
12
12
3
2
3
2
13
13
0
2
2
6
21
Algoritmo 
2
4
3
5
7
6
0
3
3
0
6
2
6
0
7
1
5
6
2
3
0
4
0
1
1
2
2
3
0
2
0
Iteración # 6: El camino seleccionado es 1-4-6-3-5-7
6
6
9
9
11
11
12
12
13
13
22
Algoritmo 
2
4
3
5
7
6
0
3
3
0
6
2
6
0
7
1
5
6
2
3
0
4
0
1
1
2
2
3
0
2
0
Iteración # 6: CMin, que se determina mediante la rama 3-5, es 1. La red modificada es la siguiente:
6
6
9
9
11
11
12
12
2
3
2
3
13
13
1
7
14
14
5
2
0
3
23
Algoritmo 
2
4
3
5
7
6
0
2
3
0
7
3
5
0
7
1
5
6
3
3
0
4
0
0
2
1
3
2
0
2
0
Solución óptima: Flujo Máximo 140 vehículos por hora
6
6
9
9
11
11
12
12
13
13
14
14
24
Algoritmo 
2
4
3
5
7
6
5
5
3
3
0
0
0
6
0
1
0
0
0
0
0
2
2
3
7
8
0
5
7
1
1
Red Inicial:
25
Algoritmo 
2
4
3
5
7
6
7
3
5
7
1
5
6
3
3
2
3
1
Solución óptima: Flujo Máximo 140 vehículos por hora
14
14
26