Redes De Flujo

1. REDES DE FLUJOS

una red de flujo es un grafo dirigido donde existen dos vértices especiales, uno llamado fuente, al que se le asocia un flujo positivo y otro llamado sumidero que tiene un flujo negativo y a cada arista se le asocia cierta capacidad positiva. En cada vértice diferente a los dos especiales se mantiene la ley de corrientes de Kirchoff, en donde la suma de flujos entrantes a un vértice debe ser igual a la suma de flujos que salen de él. Puede ser utilizada para modelar el tráfico en un sistema de autopistas, fluidos viajando en tuberías, corrientes eléctricas en circuitos eléctricos o sistemas similares por lo que viaje algo entre nodos.

Las redes de flujo son modelos matemáticos aplicables a situaciones tales como: sistemas de tuberías (para fluidos como agua, petróleo o gas), redes de cableado eléctrico, sistemas de carreteras, sistemas de transporte de mercancías, etc.

2. FUENTE Y SUMIDERO

Fuente es el punto de partida del recorrido, donde no posee ninguna arista de salida, y el sumidero es el punto de llegada o punto deseado el cual no posee ninguna arista de salida.

3. TEOREMA DE FLUJO MÁXIMO Y CORTE MINIMO

Modelo del 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 origeno 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:

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.

• El siguiente grafo ilustra 3 cortes: el Corte 1 con capacidad 60, el Corte 2 con capacidad 110 y el Corte 3 con capacidad 70. Todo lo que podemos obtener de los 3 cortes es que el flujo máximo en la red no excede de 60 unidades. No podemos saber cuál es el flujo máximo hasta que se hayan enumerado todos los cortes en la red:

Las capacidades se identifican como sigue: por ejemplo, para el arco (3,4), el límite de flujo es de 10 unidades de 3 a 4 y de 5unidades de 4 a 3.

4. REDES DE FLUJO DE COSTO MINIMO

El modelo de Flujo de Costo Mínimo en una Red se plantea de la manera siguiente

bi>0 si i es un nodo origen

bi<0 si i es un nodo destino

bi=0 si i es un nodo de transbordo

Una condición necesaria para que el modelo tenga solución factible es que

 bi=0, es decir, que el flujo total generado en los nodos origen sea igual al flujo total absorbido por los nodos destino.

Cuando esta condición no se cumple (problemas de transporte no balanceado en los que la oferta es diferente a la demanda) se generan nodos ficticios que generen o que absorban flujo. Los costos asociados a los arcos que parten o llegan a estos nodos es cero.

Con frecuencia bi y uij son valores enteros. Las variables xij son variables enteras y no se requiere agregar esta condición al modelo (unimodularidad).

Con este modelo es posible plantear un problema de transporte, de transbordo, de flujo máximo y de camino más corto.

5. CADENA DE INCREMENTO DE FLUJO

supongamos que tenemos un camino de s a t un camino legal siguiendo las direcciones de las flechas, tal que en cada arco del camino el flujo existente no ocupa toda la capacidad del arco que hay margen en cada arco para aumentar el flujo (s=v0!v1!v2!v5=t).

Sumamos el mínimo de los márgenes m al flujo de cada arco del camino el nuevo flujo f0 así construido es válido y tiene mayor valor ,val(f0)=val(f)+m>val(f).

el camino de s a t que hemos tomado sera por tanto un camino aumentador del flujo. pero puede ocurrir que no dispongamos de estos caminos y sin embargo el flujo pueda aumentarse. Con el nuevo flujo obtenido sobre la red no podemos encontrar otro camino aumentador, pues no podemos aumentar yendo desde s por v1, y tampoco con el camino s!v3!v4! Existe otra posibilidad, que es considerar recorridos “sin tener en cuenta el sentido de las flechas (que serán caminos no legales, pero válidos para nuestros propósitos): supongamos que tenemos un recorrido de s a t, sin tener en cuenta las direcciones de las flechas, tal que cada arco de ese camino siguiendo la dirección de las flechas (hacia delante) el flujo existente no ocupa toda la capacidad del arco, y que cada arco del camino en dirección contraria de la flecha(hacia atrás) el flujo existente es mayor que cero, entonces si sumamos el mínimo de los márgenes m al flujo de cada arco hacia delante y se lo restamos por detrás, el nuevo flujo f0 así construido es valido y tiene mayor valor,val(f0)=val(f)+m.

6. ALGORITMO DE FORT-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

...