En una red con flujo de capacidades en 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 los arcos. 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 capacidad de 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, el objetivo 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 algunas rutas 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.
Luego de resolver este problema de PL mediante el uso de LINDO (entre otros software), obtenemos los siguientes resultados: Enviar 10 unidades de 1 a 2 Enviar 7 unidades de 1 a 3 Enviar 3 unidades de 2 a 6 Enviar 7 unidades de 2 a 4 Enviar 4 unidades de 3 a 6 Enviar 6 unidades de 3 a 5 Enviar 7 unidades de 4 a 7 Enviar 8 unidades de 5 a 7 Enviar 3 unidades de 6 a 3 Enviar 2 unidades de 6 a 5 Enviar 2 unidades de 6 a 7 El flujo máximo es F= 17 unidades. El Problema Dual de Flujo Máximo: El problema dual para el ejemplo numérico anterior es: Min 10Y12 + 10Y13 + Y23 + Y32 + 6Y26 + 4Y36 + 4Y63 + 8Y24 3Y64 + 3Y46 + 12Y35 + 2Y65 + 2Y56 + 8Y75 + 7Y47 + 2Y67 sujeto a: X2 - X1 + Y12 0, X3 - X1 + Y13 0, X3 - X2 + Y23 0, X3 - X2 + Y32 0, X6 - X2 + Y26 0, X6 - X3 + Y36 0, X3 - X6 + Y63 0, X4 - X2 + Y24 0, X4 - X6 + Y64 0 X6 - X4 + Y46 0, X5 - X3 + Y35 0, X5 - X6 + Y65 0, X6 - X5 + Y56 0, X5 - X7 + Y75 0, X7 - X4 + Y47 0, X7 - X6 + Y67 0, X1 - X7 1, y
Yij 0, y todos los Xi son variables libres. La formulación dual sugiere que se intente asignar flujos a arcos de misma manera que para cada arco, la diferencia en valores en el nodo inicial y el nodo final excede el valor agregado. Para resolver el problema dual, a usted podría gustarle intentar el Método Algebraico .
