4.

2 El modelo de flujo máximo

El algoritmo de flujo máximo tiene como objetivo maximizar la cantidad del flujo del

origen al destino. Esta cantidad se mide en cualquiera de las dos maneras equivalentes, esto

es, la cantidad que sale del origen o la cantidad que entra al destino. El primer algoritmo

eficiente para encontrar el máximo flujo fue concebido por Ford y Fulkerson y es uno de los

algoritmos más famosos en el área de informática. En los últimos 50 años, se han hecho

muchas mejoras sobre este algoritmo, desde que se desarrolló se han descubierto muchas

aplicaciones, a continuación, mencionaremos algunas aplicaciones comunes:

1. Maximizar el flujo a través de la red de distribución de una compañía desde sus fábricas
hasta sus clientes.
2. Maximizar el flujo a través de la red de suministros de una compañía de proveedores a
las fábricas.
3. Maximizar el flujo de líquidos por un sistema de tuberías.
4. Maximizar el flujo de vehículos por una red de transporte.

En algunas de estas aplicaciones, el flujo a través de la red se puede originar en más de

un nodo y también puede terminar en más de uno, aunque el problema de flujo máximo debe

tener sólo un origen y un destino. Por ejemplo, una red de distribución de una compañía tiene

varias fábricas y múltiples clientes. En este caso se recurre a una reformulación ingeniosa

para ajustar esta situación al problema de flujo máximo. Se trata de aumentar la red original

para que incluya un origen ficticio, un destino ficticio y algunos arcos nuevos. El origen

ficticio se maneja como el nodo que a origen a todo flujo que en realidad se origina en algunos

otros nodos. En cada uno de estos otros nodos se inserta un nuevo arco que va desde el origen

ficticio hasta este nodo, donde la capacidad del arco es igual al flujo máximo que se puede

originar en este nodo. De manera similar, el destino ficticio se trata como el nodo que absorbe
todo el flujo, que en realidad, termina en algún otro nodo. Por lo tanto, se coloca un nuevo

arco desde cada uno de los otros nodos hasta el destino ficticio con capacidad igual al flujo

máximo que en realidad termina en este nodo. Debido a estos cambios, todos los nodos de la

red original se convierten en nodos de transbordo para que la red aumentada tenga un solo

origen (fuente ficticia) y un solo destino (destino ficticio) y se ajuste al problema de flujo

máximo.

Algoritmo de flujo máximo

Este algoritmo se fundamenta en el hallazgo de rutas de avance con flujo positivo

entre los nodos origen y destino. Cada ruta destina una parte de o todas las capacidades de

sus arcos al flujo total en la red. Como el problema del flujo máximo se puede formular como

un problema de programación lineal, se puede resolver con el método simplex. 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.

Una trayectoria de aumento es una trayectoria dirigida del nodo origen al nodo destino

en la red residual, tal que todos los arcos en 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 toda

la trayectoria. Por lo tanto, cada trayectoria de aumento proporciona una oportunidad de

aumentar más el 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 pueden 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

asignación de flujos. Para resumir, cada iteración del algoritmo consiste en tres pasos, que a

continuación se describen.

1. Identificar una trayectoria de aumento, esto se logra cuando se encuentra una trayectoria
dirigida del origen al destino en la red residual, tal que cada arco sobre ella tenga
capacidad mayor a cero. (Si no existe una, los flujos netos asignados constituyen un
patrón de flujo óptimo).
2. Encontrar la rama con el mínimo de las capacidades residuales de los arcos sobre esta
trayectoria de aumento e identificar la capacidad residual cr de esta trayectoria.
3. Disminuir en cr la capacidad residual de cada arco en esta trayectoria de aumento y
aumentar en cr la capacidad residual de cada arco en la dirección opuesta en la
trayectoria. Una vez que se han asignado flujos a los arcos de la red original, la red
residual muestra las capacidades restantes – llamadas capacidades residuales – para
asignar flujos adicionales. Regresar al paso 1 y repetir hasta finalizar la red.

La parte más difícil de este algoritmo, es encontrar una trayectoria de aumento idónea.

Esta tarea se puede simplificar con un procedimiento sistemático. Se comienza por

determinar todos los nodos que se pueden alcanzar desde el origen con un solo arco con

capacidad residual estrictamente positiva. Después, en el caso de cada uno de estos nodos

alcanzados, se determinan todos los nuevos nodos – entre los que no han sido alcanzados – a

los que se puede llegar desde este nodo con un solo arco con capacidad residual estrictamente

positiva. Este procedimiento se repite con los nuevos nodos a medida que se llega a ellos. El

resultado será la identificación de un árbol con todos los nodos a los que se puede llegar

desde el origen, a lo largo de una trayectoria con capacidad de flujo residual estrictamente
positiva. Este procedimiento de abanico siempre identificará una trayectoria de aumento, si

existe. Aunque el procedimiento es relativamente directo, es útil poder reconocer cuándo se

tiene un patrón óptimo sin tener que buscar de manera exhaustiva una ruta que no existe. A

veces es posible reconocer esto con el resultado de un teorema importante de teoría de redes,

conocido como teorema del-flujo máximo-corte mínimo. Un corte define un conjunto de

arcos cuya eliminación de la red interrumpe el flujo entre los nodos fuente y destino. La

capacidad del corte es igual a la suma de las capacidades de su conjunto de arcos. En general

hay muchas formas de dividir una red para formar un corte que ayude a analizarla. El

teorema del-flujo máximo-corte mínimo establece que para cualquier red con un solo nodo

origen y un solo nodo destino, el flujo máximo factible del origen al destino es igual al valor

del corte mínimo de todos los cortes de la red, en otras palabras, entre todos los cortes posibles

en la red, el corte con la capacidad mínima es el cuello de botella que determina el flujo

máximo en la red.

A continuación, con ayuda de un ejercicio dirigido, se exponen las particularidades y

funcionamiento del algoritmo de flujo máximo.

Ejemplo 2. La red de drenaje de una pequeña comunidad ha ido creciendo conforme las

colonias se han conurbado. En tiempos de lluvia la capacidad del drenaje se ve sobrepasada

y la comuna sufre inundaciones. Se ha propuesto la ampliación del colector principal para

desalojar de manera más eficiente las precipitaciones.

 0.7
2 4
1.0
0.5 0.4 1.4
1 ?
3 0.5 9
1.2 Colector Principal
1.0
6 8
1.2
1.0
5 0.5
7
Figura 1. Red de drenaje con gastos máximos (m3/seg)

La red muestra el gasto máximo em m3/seg de los colectores secundarios y la

dirección del flujo. Se desea determinar la capacidad del colector principal con base en el

flujo máximo de la red.

Solución. El algoritmo de flujo máximo requiere que exista un solo nodo origen y uno solo

de destino. Para nuestro ejemplo es necesario crear un nodo ficticio de origen, lo mismo

sucede cuando se tienen diversos destinos del flujo, se debe crear un nodo ficticio de destino

donde confluyan los flujos reales. El flujo de los arcos salientes del nodo ficticio origen

corresponden a la suma de los arcos salientes de los nodos de origen real.

0.7 4
2
1.0
0.5 0.4 1.4
1 ?
3 0.5 9
1.2 Colector Principal
1.0
1.0 8
6
0
1.2
1.7 1.0
5 0.5
7

Figura 2. Red modificada con nodo de origen ficticio

Primer paso. Identificar una trayectoria de aumento capaz de transportar algún flujo mayor

que cero desde el origen hasta el destino, probemos 0 → 1→ 2 → 4 → 9

Segundo paso. En esta ruta encontrar la rama con la menor capacidad, en este caso el arco 2

→ 4 cuya capacidad residual es de cr = 0.7 m3/seg. Este es el máximo flujo que puede

transportarse por esta trayectoria.

Tercer paso. Disminuir en cr la capacidad residual de cada arco en esta trayectoria y aumentar

en cr la capacidad residual de cada arco en la dirección opuesta en la trayectoria.

0 0.7
0.7 2 4
0.7
0.3
0.5 0.4 0.7
1 ?
0.7 3 0.5 9
1.2 Colector Principal
0.3 1.0 8
6
0
1.2
1.7 1.0
5 0.5
7
Figura 3. Red residual de 1ra trayectoria

Una vez que se han asignado flujos a los arcos de la red original, la red residual

muestra las capacidades restantes para asignar flujos adicionales. Regresar al paso 1 y repetir

hasta finalizar la red.

Ahora se busca otra trayectoria que tenga capacidad residual para transportar un flujo

del origen al destino. La trayectoria 0 → 1 → 2 → 3 → 4 → 9 cumple con esta condición y

el menor flujo residual es cr = 0.3 m3/seg. Se resta este valor a los flujos residuales de los

arcos involucrados y se le suma a su flujo transportado.

0 0.7
1.0 2 4
0.2 0.3 0.4
0
0.3 0.1 1.0
1 ?
1.0 3 0.5 9
1.2 Colector Principal
0 1.0
6 8
0
1.2
1.7 1.0
5 0.5
7

Figura 4. Análisis de flujo residual nodo 2-3 y 3-4 en 2da trayectoria

 Podemos observar que los arcos 2→3 y 3→4 aún cuentan con flujo residual, pero

como se conectan al origen a través de los arcos 0→1 y 1→ 2 que están saturados, esta

capacidad residual no se aprovechará.

Buscando la tercera trayectoria se encuentra 0→5→6→8→4→9 con un flujo residual

mínimo en el arco 4→9 de magnitud cr = 0.4 m3/seg. Con este valor se calculan los nuevos

flujos residuales para los arcos de esta ruta.

0 0.7
1.0 2 4
0.2 0.3 0
0
0.3 0.1 0.4 1.4
1 ?
1.0 3 9
0.1 1.2 Colector Principal
0 0.4
6 8
0 0.4
1.3
0.6
0.4 0.8 1.0
5 0.5
7

Figura 5. Red residual de la 3era trayectoria

La cuarta trayectoria es 0 →5→6→8→9 con flujo residual de cr = 0.6 m3/seg. Se

calculan los flujos residuales y se registran en la red.

0 0.7
1.0 2 4
0.2 0.3 0
0
1 0.3 0.1 0.4 1.4
?
1.0 3 0.6 9
0.1 0.6 Colector Principal
0 0 1.0
6 8
0 0.7 1.0
1.0 0.2 1.0
5 0.5
7

Figura 6. Red residual de 4a trayectoria

Ahora solo queda una trayectoria con flujo residual, 0→5→7→8→9, el mínimo

corresponde al arco 5→7 por lo que se resta cr = 0.5 m3/seg a los flujos residuales de esta

trayectoria.
 0 0.7
1.0 2 4
0.2 0.3 0
0
0.3 0.1 0.4 1.4
1 ?
1.0 3 1.1 9
0.1 0.1 Colector Principal
0 0 1.0
6 8
0 1.0
0.2 0.5
1.5 0.2
0.5
5 0 0.5
7

Figura 7. Red residual de 5a trayectoria

Si bien, aún existen arcos con capacidad residual de 0.2 m3/seg en los arcos que salen del

origen y de 0.1 m3/seg en los que desembocan en el destino, es imposible encontrar una ruta

que los transporte.

Con esto concluye el algoritmo del flujo máximo y se calcula su valor sumando los flujos

que entran en el destino, 1.1 m3/seg + 1.4 m3/seg = 2.5 m3/seg. Por lo tanto el colector

principal deberá ser diseñado para captar este flujo.