Problema del Flujo Máximo (II)

Para hacer que el problema de Seervada Park se ajuste formalmente a este formato con una red dirigida, cada ligadura 10.5 con 0 en un punto terminal se sustituirá por un arco dirigido en la dirección factible. Por ejemplo, la ligadura entre los nodos O y A se sustituye por un arco dirigido del nodo O al nodo A con una capacidad de 5. Las dos ligaduras con un 1 en los extremos (AB y DE) se sustituyen por un par de arcos dirigidos en direcciones opuestas, cada uno con capacidad de 1. Considerando que estos cambios se llevan a cabo, se seguirá operando sobre la red que se muestra en la figura 10.5

Como el problema de flujo máximo se puede formular como un problema de programación lineal (véase el problema 11),se puede resolver con el método símplex. Sin embargo, se dispone de un algoritmo de trayectorias aumentadas mucho más eficiente. Este algoritmo se basa en dos conceptos intuitivos, el de una red residual y el de una trayectoria aumentada.