Antología de Investigación de Operaciones
Ingeniería en Sistemas Computacionales
Algoritmo de la trayectoria de aumento del problema de flujo máximo
1. Se identifica una trayectoria de aumento cuando se encuentra alguna trayectoria dirigida del
origen al destino en la red residual, tal que cada arco sobre ella tenga capacidad residual
estrictamente positiva. (si no existe una, los flujos netos asignados constituyen un patrón de
flujo óptimo)
2. Cuando se encuentra el mínimo de las capacidades residuales de los arcos sobre esta trayectoria
se identifica la capacidad residual c* de esta trayectoria de aumento. Se aumenta en c* el flujo
de esta trayectoria.
3. Se disminuye en c* la capacidad residual de cada arco en esta trayectoria de aumento. Se
aumenta en c* la capacidad residual de cada arco en la dirección opuesta en esta trayectoria. Se
regresa al paso 1.
Cuando se lleva a cabo el paso 1, con frecuencia habrá varias alternativas de trayectorias de
aumento entre las cuales se podrá escoger. Aunque la estrategia algorítmica para elegir es importante para
elevar la eficiencia de las aplicaciones a gran escala, no se profundizará en este tema relativamente
especializado. En consecuencia, en el siguiente ejemplo, la selección se hará en forma arbitraria.
Aplicación del algoritmo al problema de Flujo Máximo de Seervada park
La aplicación de este algoritmo al problema de Seervada Park conduce a los siguientes resultados. A
partir de la red residual inicial de la siguiente figura 2.4, se proporciona la nueva red residual después de
una o dos iteraciones, donde la cantidad total de flujo de O a T logrado hasta el momento se muestra en
negritas (junto a los nodos O y T).
Figura 2.4. Red residual del problema de Flujo Máximo de Seervada park
Iteración 1: en la figura 2.4, una trayectoria de aumento en O→B→E→T que tiene la capacidad
residual igual al min {7,5,6} = 5. Si se asigna un flujo de 5 a esta trayectoria, la red residual que resulta es:
51