fgdfg

Republica Bolivariana de Venezuela
Ministerio del Poder Popular para la Defensa
Universidad Nacional Experimental Politécnica de las Fuerza Armada
UNEFA –Coro















Realizado por:



Santa Ana de coro; junio 2014
Introducción






























Redes de flujo
Una red de flujo es un grafo dirigido donde existendos 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 paramodelar 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 fluídos como agua, petróleo o gas), redes de cableado eléctrico, sistemas de carreteras, sistemas de transportede mercancías, etc.
Así como modelamos los enlaces de una red y sus nodos como un grafo dirigido, podemos interpretar el grafo como una red de flujo de algún material.
Una red de flujo es un digrafo G = (V;E) con una función de capacidad c : E ! R+ y dos vértices distinguidos, llamados fuente y sumidero.
Una fuente produce material en forma estacionaria y un sumidero lo consume.
Cada arcopuede ser considerado como un conducto de cierta capacidad.

Si hay múltiples fuentes y resumideros, el problema se puede reducir al caso simple previo de una fuente y un resumidero.
Supongamos que se tiene {s1,s2,s3,..sm} fabricas y {t1,t2,t3,..,tn} puntos de venta.

Una Red de Transporte es una grafica dirigida, simple, con pesos y que debe cumplir las siguientes:

Poseer una fuente o vérticefijo que no tiene aristas de entrada.
Poseer un sumidero o vértice fijo que no tiene arista de salida
El peso Cij de la arista dirigida de i a j llamado capacidad de “ij” es un numero no negativo.

Este es un ejemplo de una red que parte de un punto a que es un
Muelle y llega a un punto z que es una refinería.

En otras palabras fuente es el punto de partida del recorrido, donde no poseeninguna arista de salida, y el sumidero es el punto de llegada o punto deseado el cual no posee ninguna arista de salida. 




En esta imagen podemos observar que el vertice "19" es el punto de partida o vertice fuente, el cual no posee ninguna arista de entrada, recorriendo el camino mas corto aplicando el teorema del costo minimo (el cual veremos mas adelante), llegaremos al vertice "20" overtice sumidero

Características:

son dirigidos 
tiene una capacidad asociada al arco, c(v,w)
se puede hacer pasar un flujo, por esos arcos, un valor necesariamente inferior a la capacidad.
tiene necesariamente un vértice-fuente y un vértice-pozo (grado saliente nulo)t.


Algoritmo de  Ford Fulkerson:


El algoritmo de Ford-Fulkerson propone buscar caminos en los que se puedaaumentar 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 delarco 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...