Flujo Maximo

2.4 PROBLEMA DE FLUJO MÁXIMO.

En algunas redes circula por los arcos un flujo (envío o circulación de unidades homogéneas de algún producto: automóviles en una red de carreteras, litros de petróleo en un oleoducto, bits por un cable de fibra óptica) desde el origen o fuente al destino, también denominado sumidero o vertedero. Los arcos tienen una capacidad máxima de flujo, y se trata de enviar desde la fuente al sumidero la mayor cantidad posible de flujo, de tal manera que:

• El flujo es siempre positivo y con unidades enteras.

• El flujo a través de un arco es menor o igual que la capacidad.

• El flujo que entra en un nodo es igual al que sale de él.

En el caso de que el origen o el destino no existan en el problema, se añaden ficticiamente utilizando arcos unidireccionales de capacidad infinita, como en grafo mostrado a continuación:

Corte: Un corte define una serie de arcos cuya supresión de la red causa una interrupción completa del flujo entre el origen y el destino. La capacidad de corte es igual a la suma de las capacidades de los arcos asociados. Entre todos los cortes posibles en la red, el corte con la menor capacidad proporciona el flujo máximo en la red.

Algoritmo de Ford-Fulkerson

El algoritmo de Ford-Fulkerson propone buscar caminos en los que se pueda aumentar el flujo, hasta que se alcance el flujo máximo.

La idea es encontrar una ruta de penetración con un flujo positivo neto que una los nodos origen y destino.

Consideraremos las capacidades iniciales del arco que une el nodo i y el nodo j como Cij y Cji. Estas capacidades iniciales irán variando a medida que avanza el algoritmo, denominaremos capacidades residuales a las capacidades restantes del arco una vez pasa algún flujo por él, las representaremos como cij y cji.

Para un nodo j que recibe el flujo del nodo i, definimos una clasificación [aj,i] donde aj es el flujo del nodo i al nodo j.

Los pasos del algoritmo se definen como sigue:

Paso 1: Inicializamos las capacidades residuales a las capacidades iniciales, hacemos (cij,cji)=(Cij,Cji) para todo arco de la red. Suponiendo el nodo 1 como el nodo origen, hacemos a1=∞ y clasificamos el nodo origen con [∞,-]. Tomamos i=1 y vamos al paso 2.

Paso 2: Determinamos Si como un conjunto que contendrá los nodos a los que podemos acceder directamente desde i por medio de un arco con capacidad positiva, y que no formen parte del camino en curso. Si Si contiene algún nodo vamos al paso 3, en el caso de que el conjunto sea vacío saltamos al paso 4.

Paso 3: Obtenemos kЄSi como el nodo

...