redes de flujo

Redes de flujo
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.


Una red de flujo es un grafo dirigido donde existen dos vértices especiales, uno llamado fuente, otro llamado sumidero y en donde cadaarco   tiene una capacidad positiva.
En la figura el vértice s es el nodo 1 y t es el nodo 6 los nodos restantes son llamados trasbordo.
Fuente u origen: punto de partida del flujo total de una red y se denota con s.
Sumidero o destino: es el punto llegada de del flujo total de una red y se denota con t.
Se supone que cada vértice se encuentra en alguna ruta de s a t.
Las redes pueden serdirigidas y no dirigidas: dirigidas son cuando el flujo va en sentido como lo indique la flecha y no dirigidas son cuando el flujo tiene una trayectoria no dirigida.
Existen también modelos de redes entre ellos:
Modelo de la ruta más corta.
Modelo del flujo máximo.
Modelo del flujo del costo mínimo.


Modelo de Flujo Máximo
Se trata de enlazar un nodo fuente y un nodo destino a través deuna red de arcos dirigidos. Cada arco tiene una capacidad máxima de flujo admisible. El objetivo es el de obtener la máxima capacidad de flujo entre la fuente y el destino.
Características:
Todo flujo a través de una red conexa dirigida se origina en un nodo, llamado fuente, y termina en otro nodo llamado destino.
Los nodos restantes son nodos de trasbordo.
Se permite el flujo a través de unarco sólo en la dirección indicada por la flecha, donde la cantidad máxima de flujo está dada por la capacidad del arco. En la fuente, todos los arcos señalan hacia fuera, en el destino, todos señalan hacia el nodo.
El objetivo es maximizar la cantidad total de flujo de la fuente al destino. Esta cantidad se mide en cualquiera de las dos maneras equivalentes, esto es, la cantidad que sale de lafuente o la cantidad que entra al destino.
El problema de flujo máximo se puede formular como un problema de programación lineal, se puede resolver con el método simplex y usar cualquier software. Sin embargo, se dispone de un algoritmo de trayectorias aumentadas mucho más eficientes. Podemos, mediante el Algoritmo de Ford Fulkerson, encontrar el flujo máximo de una red.
Es un método genérico paraaumentar la capacidad de los flujos incrementalmente a lo largo de los caminos que van del origen al destino, que sirve como la base para un familia de algoritmos. Esta técnica es conocida como el método Ford-Fulkerson en la literatura clásica, aunque también puede encontrarse como el aumenting-path method. 

El algoritmo de Ford-Fulkerson propone buscar caminos en los que se pueda aumentar elflujo, hasta que se alcance el flujo máximo. Es aplicable a los Flujos maximales. La idea es encontrar una ruta de penetración con un flujo positivo neto que una los nodos origen y destino. Su nombre viene dado por sus creadores, L. R. Ford, Jr. y D. R. Fulkerson. 
El algoritmo se basa en dos conceptos intuitivos, el de red residual y el de trayectoria aumentada.



Trayectoria de aumento parael problema de flujo máximo:
Se identifica una trayectoria de aumento encontrando alguna trayectoria dirigida del origen al destino en la red residual, tal que cada arco sobre esta trayectoria tiene capacidad residual estrictamente positiva. (Si no existe una, los flujos netos asignados constituyen un patrón del flujo óptimo).
Se identifica la capacidad residual c* de esta trayectoria deaumento encontrando el mínimo de las capacidades residuales de los arcos sobre esta trayectoria. Se aumenta en c* el flujo de esta trayectoria.
Se disminuye en c* la capacidad residual de cada arco en esta trayectoria de aumento. Se aumenta en c* la capacidad residual de cada arco en la dirección opuesta en esta trayectoria. Se regresa la paso 1.

Modelo de la ruta más corta
Considere una red...