Flujo Máximo
Al intentar optimizar el flujo dentro de una red, se enfrenta un problema
donde se tiene un nodo inicial, denominado fuente, y otro nodo final,
llamado destino. La meta es aumentar al máximo posible la cantidad de
flujo que se desplaza desde la fuente hasta el destino. Es importante
considerar que el flujo en cada arco de la red se dirige en una sola
dirección, tal como se especifica en el diagrama que representa la red. En
este contexto, el desafío consiste en encontrar la manera de maximizar el
flujo total que puede trasladarse desde el nodo de origen hasta el nodo de
llegada, respetando las capacidades y restricciones de cada arco. Este tipo
de problema se conoce comúnmente como problema de flujo máximo, y su
resolución implica la búsqueda de la configuración óptima de flujos que
permita transferir la mayor cantidad de recurso posible a través de la red
desde el punto de inicio hasta el punto final.
Este tipo de problema se aplica en múltiples áreas, incluyendo:
1. Optimización de la red de distribución en empresas
Se utiliza para aumentar al máximo el flujo de productos desde las
fábricas de una compañía hasta los clientes finales, garantizando una
distribución eficiente y oportuna.
2. Gestión de la cadena de suministro
Se enfoca en maximizar el flujo de materiales y recursos desde los
proveedores hasta las fábricas, mejorando la eficiencia en la producción
y reduciendo los costos de inventario y transporte.
3. Transporte de recursos naturales
Es crucial en la maximización del flujo de petróleo a través de sistemas
de tuberías, asegurando que el recurso se transporte de manera eficiente
y segura desde los pozos de extracción hasta las refinerías o puntos de
distribución.
4. Distribución de agua en infraestructuras urbanas
Se emplea para maximizar el flujo de agua en un sistema de acueductos,
optimizando la entrega de agua potable desde las fuentes hasta los
hogares y empresas, garantizando un suministro adecuado y
minimizando pérdidas.
5. Gestión del tráfico vehicular
Este enfoque es utilizado para maximizar el flujo de vehículos a través
de redes de transporte urbano, con el objetivo de mejorar la movilidad,
reducir los tiempos de viaje y disminuir la congestión en las calles y
avenidas de una ciudad.
Algoritmo de la trayectoria de aumento para resolver el problema de
flujo máximo:
1. Identificación de la trayectoria de aumento
Se busca una trayectoria en la red residual que conecte el nodo origen
con el nodo destino, asegurando que todos los arcos en esta trayectoria
tengan una capacidad residual estrictamente positiva. Si no se encuentra
ninguna trayectoria con estas características, significa que los flujos
netos actuales representan una solución óptima al problema de flujo
máximo.
2. Determinación de la capacidad residual mínima
Una vez identificada la trayectoria de aumento, se analiza cada uno de
los arcos que la componen para determinar cuál es la capacidad residual
mínima entre ellos. Esta capacidad residual mínima se designa como c*,
y representa la máxima cantidad de flujo que se puede aumentar a lo
largo de esta trayectoria.
3. Actualización del flujo y de la red residual
Se procede a incrementar en c* el flujo a lo largo de la trayectoria de
aumento. Como consecuencia, la capacidad residual de cada arco en
dicha trayectoria se reduce en c*. Adicionalmente, para cada arco de la
trayectoria, se incrementa en c* la capacidad residual de su arco en la
dirección opuesta (esto permite revertir parte del flujo si se descubre una
mejor solución en iteraciones posteriores).
4. Repetición del proceso
Se regresa al paso 1 para identificar una nueva trayectoria de aumento en
la red residual actualizada. Este proceso se repite hasta que no se puedan
encontrar más trayectorias de aumento con capacidad residual
estrictamente positiva, lo que indica que se ha alcanzado el flujo
máximo en la red.
Ejemplo
Considera los flujos de la siguiente red y determina la trayectoria
de aumento para el problema de flujo máximo.
1. Primero se determina una trayectoria de aumento desde el nodo
fuente hacia el destino de la red residual, para este caso la trayectoria
de aumento está dada por 0→B→C→D→F, que tiene una capacidad
residual igual al min (9,12,7,9) = 7, que corresponde a las
capacidades residuales de cada arco. Asignamos el flujo de 7 a esta
trayectoria para obtener:
2. Otra trayectoria de aumento desde el nodo fuente hacia el destino de
la red residual para esta segunda iteración es la trayectoria de
aumento por 0→ B→C→E→F, la cual tiene una capacidad residual
igual al min (2,5,6,6) = 2, que corresponde a las capacidades
residuales de cada arco. Asignamos el flujo de 2 a esta trayectoria
para obtener:
3. Iteración 3. Una trayectoria más será 0→A→C→E→F mín. (7, 7, 4,
4) = 4. Asignamos el flujo de 4 a esta trayectoria para obtener:
4. Como ya no existen trayectorias de aumento, el patrón de flujo actual
es óptimo. Entonces la solución óptima de este problema de flujo
máximo está dada por la siguiente red:
Esto quiere decir que el flujo máximo para esta red es de 13
unidades.
