Modelado y Solución de Problemas de Capacidad Máxima en Redes de Transporte
El Problema de Flujo Máximo en Redes
El **problema de flujo máximo** consiste en desarrollar un programa de embarque que maximice la cantidad de material enviado entre dos puntos. Al punto de origen se le denomina fuente y al punto final se le llama destino. Existen varias vías de embarque que unen a la fuente con el destino, directamente o pasando por lugares intermedios denominados empalmes. Se considera que no es posible almacenar material en los empalmes, es decir, que cualquier material que llega a un empalme es embarcado inmediatamente a otro sitio.
Modelado de la Red
Una red puede ser el modelo para un problema de flujo máximo. La fuente, el destino y los empalmes se representan mediante nodos, mientras que las ramas representan los conductos a través de los cuales se transportan materiales. Asociados a cada nodo $N$ y a cada rama $NM$ que sale de $N$, hay un número no negativo, o capacidad, que representa la cantidad máxima de material que puede embarcarse de $N$ a través de $NM$.
Algoritmo para el Flujo Máximo
El proceso iterativo para encontrar el flujo máximo sigue los siguientes pasos:
- Paso 1: Encuéntrese una ruta que permita el flujo positivo de material de la fuente al destino. Si no existe alguna, continúese en el paso 5.
- Paso 2: Determine el flujo máximo que puede embarcarse a lo largo de esta ruta y denótese $k$.
- Paso 3: Disminúyase la capacidad directa (es decir, la capacidad en la dirección de flujo de las $k$ unidades) de cada rama de esta ruta en $k$ y auméntese la capacidad en sentido inverso en $k$. Agréguese $k$ unidades a la cantidad enviada al destino.
- Paso 4: Continúese en el paso 1.
- Paso 5: El flujo máximo es la cantidad de material entregado en el destino. El programa óptimo de embarque se determina comparando la red original con la red modificada. Cualquier reducción en capacidad significa un embarque realizado.
Determinación de una Ruta de Flujo Positivo
El aspecto difícil del algoritmo de flujo máximo es el Paso 1: identificación de una ruta de la fuente al destino que tenga una capacidad de flujo positiva (una ruta de aumento).
Procedimiento de Búsqueda
Para descubrir tal ruta, se aplica un proceso de expansión desde la fuente:
- Conéctense primero a la fuente todos los nodos que pueden ser alcanzados por una sola rama y que tengan capacidad de flujo positiva en la dirección de avance (dirección saliendo de la fuente).
- Conéctese estos nodos a todos los nuevos nodos que puedan ser alcanzados por ramas únicas que tengan capacidades positivas de avance.
- Continúese este proceso hasta que:
- o bien se haya llegado al destino (en cuyo caso se ha identificado la ruta apropiada),
- o bien no puedan alcanzarse nuevos nodos a partir de los ya existentes y no se haya alcanzado el destino (en cuyo caso no existe ruta apropiada).