Antología de Investigación de Operaciones
Ingeniería en Sistemas Computacionales
cambios, todos los nodos de la red original se convierten en nodos de trasbordo para que la red aumentada tenga un solo origen( la fuente ficticia) y un solo destino( el destino ficticio) y se ajuste al problema del flujo máximo.
Un Algoritmo
Como el problema de flujo máximo se puede formular como un problema de programación lineal, se puede resolver con el método símplex. Sin embargo s 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.
Una vez que se han asignado flujos a los arcos de la red original, la red residual muestra las capacidades restantes – llamados capacidades residuales – para asignar flujos adicionales. Por ejemplo, considere el arco O→B de la figura que tiene una capacidad de 7. Ahora suponga que los flujos asignados incluyen un flujo de 5 a través de este arco, lo que deja una capacidad residual de 7-5 = 2 para cualquier asignación de flujo adicional a través de O→B. Este estado se describe en la red residual de la siguiente manera
El número sobre el arco junto a u nodo señala la capacidad residual del flujo desde ese nodo hasta el otro. Por lo tanto, además de que la capacidad residual de 2 del flujo de O a B, el 5 de la derecha indica una capacidad residual de 5 para asignar un flujo desde B hasta O – es decir, para cancelar algún flujo asignado antes de O a B-.
De inicio, antes de asignar cualquier flujo, la red residual tiene la apariencia que se muestra en la figura 2.4. Todos los arcos de la red original se cambiaron de un arco dirigido a un arco no dirigido. No obstante, las capacidades en la dirección original son las mismas y las capacidades en la dirección opuesta son cero, de manera que las restricciones sobre los flujos no cambian.
Después, siempre que se asigna una capacidad de flujo a un arco, esa cantidad se resta de la capacidad residual en la misma dirección y se suma la capacidad residual en la dirección opuesta.
Una trayectoria de aumento es una trayectoria dirigida del nodo fuente al nodo destino en la red residual, tal que todos los arcos es esta trayectoria tienen capacidad residual estrictamente positiva. El mínimo de estas capacidades residuales se llama capacidad residual de la trayectoria de aumento porque representa la cantidad de flujo que es factible agregar en todo flujo a través de la red original.
El algoritmo de la trayectoria de aumento selecciona varias veces una trayectoria de aumento y agrega un flujo igual a su capacidad residual a la trayectoria en la red original. Este proceso continúa hasta que no hay trayectorias de aumento, con lo que el flujo del nodo fuente al nodo destino no puede crecer. La clave para asegurar que la solución final es óptima por necesidad es el hecho de que las trayectorias de aumento puedan cancelar flujos asignados con anterioridad en la red original; así, una selección indiscriminada de trayectorias para asignar flujos no puede evitar el uso de una combinación mejor de asignaciones de flujos.
50