INVESTIGACION DE OPERACIONES 2
Páginas: 17 (4010 palabras)
Publicado: 23 de agosto de 2014
El problema del Flujo Maximizante
En una red con un nodo fuente (punto de entrada) y un nodo de salida (punto de salida), el problema del flujo maximizante busca encontrar el flujo máximo (sean carros, aviones, fluidos o electricidad) que puede entrar a la red en el nodo fuente, fluir a través de ella y salir por el nodo de salida en un periodo de tiempo. Usar a Durham, Carolina del norte,como ejemplo del problema de flujo maximizante. Normalmente, el trafico de norte a sur alrededor de Durham, usaría las carreteras interestatales 85, pero I-85 estará fuera de servicio por reparaciones extensas a la carretera durante 2 semanas y los ingenieros de la comisión de carreteras de Carolina del Norte necesitan encontrar rutas alternas (a través de la ciudad) pueden manejar con seguridadlos 6000 carros por hora que normalmente usan I-85en dirección al sur. En la siguiente figura 1, en las que sea ilustrado estas rutas de norte a sur a través de la ciudad.
0 4
37 2
6 4
Salida 5 2
deltráfico 3 9 0
5 Fuentede trafico
3 0
0
5
7
Figura 1. Red decalles citadinas de Durham, Carolina del norte con capacidades de flujo
Los números junto a los nodos indican el flujo de tráfico de las ramas (calles en este caso) en miles de carros por hora. El 6 sobre la rama 1-2 significa que la calle tiene una capacidad de 6000 carros por hora en dirección al nodo 2. El 0 en la rama 1-2 significa que los ingenieros de carreteras no quieren que carroalguno vaya hacia el nodo fuente 1. Ver rama 3-5; 5000 carros por hora se pueden mover en la dirección del nodo 5 y 4000 carros por hora por esta rama en dirección al nodo 3. Los ceros sobre las ramas 5-6 y 4-6, indican que los ingenieros de carretera no quieren que haya trafico en dirección del nodo 6 ni al nodo 5 ni al nodo 4 o simplemente que estas calles son de un solo sentido.
El Algoritmodel flujo maximizante
Se puede encontrar el flujo máximo con los siguientes pasos:
1.- Encuentre un camino de la fuente a la salida con capacidad de flujo en todas las ramas de este trayecto (capacidad de flujo sería designada por un número positivo en la rama junto al nodo del que se está saliendo). Si no puede encontrar tal trayecto, ya tiene la solución óptima.
2.- Encuentre la ramaen su camino con la capacidad de flujo más pequeña (llamémosla capacidad C); aumente el flujo en este camino de la siguiente forma:
a. Disminuya la capacidad en la dirección del flujo de todas las ramas en este camino en la cantidad C
b.- Aumente la capacidad en la dirección contraria de todas las ramas de este camino en la cantidad C.
El procedimiento parece mucho más difícil de...
En una red con un nodo fuente (punto de entrada) y un nodo de salida (punto de salida), el problema del flujo maximizante busca encontrar el flujo máximo (sean carros, aviones, fluidos o electricidad) que puede entrar a la red en el nodo fuente, fluir a través de ella y salir por el nodo de salida en un periodo de tiempo. Usar a Durham, Carolina del norte,como ejemplo del problema de flujo maximizante. Normalmente, el trafico de norte a sur alrededor de Durham, usaría las carreteras interestatales 85, pero I-85 estará fuera de servicio por reparaciones extensas a la carretera durante 2 semanas y los ingenieros de la comisión de carreteras de Carolina del Norte necesitan encontrar rutas alternas (a través de la ciudad) pueden manejar con seguridadlos 6000 carros por hora que normalmente usan I-85en dirección al sur. En la siguiente figura 1, en las que sea ilustrado estas rutas de norte a sur a través de la ciudad.
0 4
37 2
6 4
Salida 5 2
deltráfico 3 9 0
5 Fuentede trafico
3 0
0
5
7
Figura 1. Red decalles citadinas de Durham, Carolina del norte con capacidades de flujo
Los números junto a los nodos indican el flujo de tráfico de las ramas (calles en este caso) en miles de carros por hora. El 6 sobre la rama 1-2 significa que la calle tiene una capacidad de 6000 carros por hora en dirección al nodo 2. El 0 en la rama 1-2 significa que los ingenieros de carreteras no quieren que carroalguno vaya hacia el nodo fuente 1. Ver rama 3-5; 5000 carros por hora se pueden mover en la dirección del nodo 5 y 4000 carros por hora por esta rama en dirección al nodo 3. Los ceros sobre las ramas 5-6 y 4-6, indican que los ingenieros de carretera no quieren que haya trafico en dirección del nodo 6 ni al nodo 5 ni al nodo 4 o simplemente que estas calles son de un solo sentido.
El Algoritmodel flujo maximizante
Se puede encontrar el flujo máximo con los siguientes pasos:
1.- Encuentre un camino de la fuente a la salida con capacidad de flujo en todas las ramas de este trayecto (capacidad de flujo sería designada por un número positivo en la rama junto al nodo del que se está saliendo). Si no puede encontrar tal trayecto, ya tiene la solución óptima.
2.- Encuentre la ramaen su camino con la capacidad de flujo más pequeña (llamémosla capacidad C); aumente el flujo en este camino de la siguiente forma:
a. Disminuya la capacidad en la dirección del flujo de todas las ramas en este camino en la cantidad C
b.- Aumente la capacidad en la dirección contraria de todas las ramas de este camino en la cantidad C.
El procedimiento parece mucho más difícil de...
Leer documento completo
Regístrate para leer el documento completo.