Casos especiales - Problema del flujo máximo

El último caso especial que se considerará es el problema del flujo máximo descrito en la sección 10.5. En este caso, la red ya tiene un nodo origen y un nodo destino y varios nodos de trasbordo, al igual que varios arcos y capacidades en los arcos. Sólo se necesitan tres ajustes para que este  problema quede en el formato del problema del flujo de costo mínimo. Uno es hacer cij = 0 para todos los arcos existentes para reflejar la ausencia de costos en el problema del flujo máximo. Otro es elegir una cantidad F que sea una cota superiro segura sobre el flujo factible máximo a través de la red y después asignar una cantidad  de recursos y de demanda a F en los nodos de recursos y de demanda, respectivamente. El tercero es agregar un arco que va directamente del nodo de recursos al nodo de demanda y asginarle un costo unitario arbitrariamente grande cij=M y una capacidad de arco ilimitado (uij = ∞ ). Debido a este costo tan alto, el problema del flujo de costo mínimo mandará el máximo flujo factible a través de los otros arcos, lo que logra el objetivo del problema de flujo máximo

La aplicación de esta formulación al problema del flujo máximo en Seervada Park que se muestra en la figura 10.5, conduce a la red dada en la figura 10.14.