unidad 5 problema flujo maximo

Problema de flujo máximo

Consiste en encontrar la cantidad máxima de flujo total que puede circular a través de la red en una unidad de tiempo. Paraencontrar el flujo máximo consideraremos un flujo inicial en cada arista igual a cero, después se determina un camino específico de la fuente al sumideroy se incrementa el flujo.
Paso para realizar en Flujo Máximo.

1. Encontrar un camino que vaya desde el origen hasta el destino y que sus arcos tengan deflujo mayor a cero.
2. Encontrar en arco de menor capacidad de flujo del camino seleccionado en el paso anterior.
3. Para el camino elegido, reducir lacapacidad de flujo del arco menor a cada arco involucrado en el camino.
4. Repetir o través los pasos desde el Nº 1.

En una red con flujo de capacidadesen los arcos, el problema es determinar el flujo máximo posible proveniente de los orígenes de forma tal de ahogar las capacidades de flujos de losarcos. Considere una red con m nodos y n arcos con un flujo simple de bienes. Denote el arco de flujo (i a j) como Xij. Asociamos cada arco a una capacidadde flujo, kij. En esta red, deseamos encontrar el flujo total máximo en la red, F, del nodo 1 al nodo m.

En la formulación de la programación lineal, elobjetivo es maximizar F. El monto que parte del origen por varias rutas. Para cada nodo intermedio, lo que entra debe ser igual a lo sale. En algunasrutas los flujos pueden tomar ambas direcciones. La capacidad que puede ser enviada a una dirección en particular también es mostrada en cada ruta