martes, 21 de junio de 2011

Flujo Máximo - Algoritmo de Ford-Fulkerson

Modelo del flujo máximoEn 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:


  • CorteUn 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 cual 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.
  • Algoritmo de Ford-FulkersonEl 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 destino del arco de mayor capacidad que salga de i hacia un nodo perteneciente a Si. Es decir, cik = max{cij} con jЄSi. Hacemos ak=cik y clasificamos el nodo con [ak,i]. Si es igual al nodo destino o sumidero, entonces hemos encontrado una ruta de penetración, vamos al paso 5. En caso contrario continuamos con el camino, hacemosi=k y volvemos al paso 2.
    • Paso 4 (retroceso): Si i=1, estamos en el nodo origen, y como Si es vacío, entonces no podemos acceder a ningún nodo, ni encontrar algún nuevo camino, hemos terminado, vamos al paso 6.
      En caso contrario, i≠1, le damos al valor i el del nodo que se ha clasificado inmediatamente antes, eliminamos i del conjunto Siactual y volvemos al paso 2.
    • Paso 5: Llegados a este paso tenemos un nuevo camino: Np={1,k1,k2,...,n}, esta será la p-ésima ruta de penetración desde el nodo origen al nodo destino. El flujo máximo a lo largo de esta ruta será la capacidad mínima de las capacidades residuales de los arcos que forman el camino, es decir: fp=min{a1,ak1,ak2,...,an}.
      La capacidad residual de cada arco a lo largo de la ruta de penetración se disminuye por fp en dirección del flujo y se incrementa por fp en dirección inversa, es decir, para los nodos i y j en la ruta, el flujo residual se cambia de la (cij,cji) actual a (cij-fp,cji+fp)si el flujo es de i a j, o (cij+fp,cji-fp) si el flujo es de j a i
      Inicializamos i=1 y volvemos al paso 2 para intentar una nueva ruta de penetración.
    • Paso 6 (solución): Una vez aquí, hemos determinado m rutas de penetración. El flujo máximo en la red será la suma de los flujos máximos en cada ruta obtenida, es decir: F=f1+f2+...+fm. Teniendo en cuenta que las capacidades residuales inicial y final del arco (i, j) las dan (Cij,Cji) y (cij,cji) respectivamente, el flujo máximo para cada arco se calcula como sigue: sea (α, β)=(Cij-cij, Cji-cji), si α>0, el flujo óptimo de i a j es α, de lo contrario, si β>0, el flujo óptimo de i es β. Es imposible lograr que tanto αcomo β sean positivas.
  • Ejemplo: Determinar el flujo máximo en la red siguiente:
Iteración 1:


      • Determinamos las residuales iniciales (cij,cji) iguales a las capacidades iniciales (Cij,Cji).
      • Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.
      • Paso 2: S1={2,3,4} (no vacío).
      • Paso 3: k=3 ya que c13=max{c12,c13,c14}={20,30,10}=30. Hacemos a3=c13=30 y clasificamos el nodo 3 con [30,1]. Tomamos i=3 y repetimos el paso 2.
      • Paso 2: S3={4,5}
      • Paso 3: k=5 y a5=c35=max{10,20}=20. Clasificamos el nodo 5 con [20,3]. Logramos la penetración, vamos al paso 5.
      • Paso 5: La ruta de la penetración se determina de las clasificaciones empezando en el nodo 5 y terminando en el nodo 1, es decir, 5[20,3]3[30,1]1.Entonces la ruta es N1={1,3,5} y f1=min{a1,a3,a5}={∞,30,20}=20. Las capacidades residuales a lo largo de esta ruta son:
(c13,c31)=(30-20, 0+20)=(10,20)
(c35,c53)=(20-20, 0+20)=(0,20)
    • Iteración 2:


      • Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.
      • Paso 2: S1={2,3,4}.
      • Paso 3: k=2 y a2=c12=max{20,10,10}=20. Clasificamos el nodo 2 con [20,1]. Tomamos i=2 y repetimos el paso 2.
      • Paso 2: S2={3,5}
      • Paso 3: k=3 y a3=c23=max{30,40}=40. Clasificamos el nodo 3 con [40,2]. Tomamos i=3 y repetimos el paso 2.
      • Paso 2: S3={4} (c35=0, el nodo 1 ya ha sido clasificado y el nodo 2 cumple ambas condiciones, por tanto los nodos 1, 2 y 5 no pueden ser incluidos en S3).
      • Paso 3: k=4 y a4=c34=10. Clasificamos el nodo 4 con [10,3]. Tomamos i=4 y repetimos el paso 2.
      • Paso 2: S4={5}
      • Paso 3: k=5 y a5=c45=20. Clasificamos el nodo 5 con [20,4]. Logramos la penetración, vamos al paso 5.
      • Paso 5: La ruta de la penetración es: 5[20,4]4[10,3]3[40,2]2[20,1]1.Entonces la ruta es N2={1,2,3,4,5} y f2=min{∞,20,40,10,20}=10. Las capacidades residuales a lo largo de esta ruta son:
(c12,c21)=(20-10, 0+10)=(10,10)
(c23,c32)=(40-10, 0+10)=(30,10)
(c34,c43)=(10-10, 5+10)=(0,15)
(c45,c54)=(20-10, 0+10)=(10,10)
    • Iteración 3:

      • Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.
      • Paso 2: S1={2,3,4}.
      • Paso 3: k=2 y a2=c12=max{10,10,10}=10, rompemos el empate arbitrariamente. Clasificamos el nodo 2 con [10,1]. Tomamos i=2 y repetimos el paso 2.
      • Paso 2: S2={3,5}
      • Paso 3: k=3 y a3=c23=max{30,30}=30. Clasificamos el nodo 3 con [30,2]. Tomamos i=3 y repetimos el paso 2.
      • Paso 2: S3 vacío ya que c34=c35=0. Vamos al paso 4 para retroceder.
      • Paso 4: La clasificación [30,2nos dice que el nodo inmediatamente precedente es el 2. Eliminamos el nodo 3 de una consideración posterior en esta iteración. Tomamos i=2 y repetimos el paso 2.
      • Paso 2: S2={5}
      • Paso 3: k=5 y a5=c25=30. Clasificamos el nodo 5 con [30,2]. Logramos la penetración, vamos al paso 5.
      • Paso 5: La ruta de la penetración es: 5[30,2]2[10,1]1.Entonces la ruta es N2={1,2,5} y f3=min{∞,10,30}=10. Las capacidades residuales a lo largo de esta ruta son:
(c12,c21)=(10-10, 10+10)=(0,20)
(c25,c52)=(30-10, 0+10)=(20,10)
    • Iteración 4:

      • Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.
      • Paso 2: S1={3,4}.
      • Paso 3: k=3 y a3=c13=max{10,10}=10. Clasificamos el nodo 3 con [10,1]. Tomamos i=3 y repetimos el paso 2.
      • Paso 2: S3={2}
      • Paso 3: k=2 y a2=c32=10. Clasificamos el nodo 2 con [10,3]. Tomamos i=2 y repetimos el paso 2.
      • Paso 2: S2={5}
      • Paso 3: k=5 y a5=c25=20. Clasificamos el nodo 5 con [20,2]. Logramos la penetración, vamos al paso 5.
      • Paso 5: La ruta de la penetración es: 5[20,2]2[10,3]3[10,1]1.Entonces la ruta es N4={1,3,2,5} y f4=min{∞,10,10,20}=10. Las capacidades residuales a lo largo de esta ruta son:
(c13,c31)=(10-10, 20+10)=(0,30)
(c32,c23)=(10-10, 30+10)=(0,40)
(c25,c52)=(20-10, 10+10)=(10,20)
    • Iteración 5:

      • Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.
      • Paso 2: S1={4}.
      • Paso 3: k=4 y a4=c14=10. Clasificamos el nodo 4 con [10,1]. Tomamos i=4 y repetimos el paso 2.
      • Paso 2: S4={3,5}
      • Paso 3: k=3 y a3=c23=max{15,10}=15. Clasificamos el nodo 3 con [15,4]. Tomamos i=3 y repetimos el paso 2.
      • Paso 2: S3 vacío ya que c32=c34=c35=0. Vamos al paso 4 para retroceder.
      • Paso 4: La clasificación [15,4nos dice que el nodo inmediatamente precedente es el 4. Eliminamos el nodo 3 de una consideración posterior en esta iteración. Tomamos i=4 y repetimos el paso 2.
      • Paso 2: S4={5}
      • Paso 3: k=5 y a5=c45=10. Clasificamos el nodo 5 con [10,4]. Logramos la penetración, vamos al paso 5.
      • Paso 5: La ruta de la penetración es: 5[10,4]4[10,1]1.Entonces la ruta es N2={1,4,5} y f3=min{∞,10,10}=10. Las capacidades residuales a lo largo de esta ruta son:
(c14,c41)=(10-10, 0+10)=(0,10)
(c45,c54)=(10-10, 10+10)=(0,20)
    • Iteración 6:

      • No son posibles más penetraciones, debido a que todos los arcos fuera del nodo 1 tienen residuales cero. Vayamos al paso 6 para determinar la solución.
    • Paso 6: El flujo máximo en la red es F=f1+f2+...+f5=60 unidades. El flujo en los diferentes arcos se calcula restando las últimas residuales obtenidas en la última iteración de las capacidades iniciales:
Arco
(Cij, Cji) - (cij, cji)en it. 6
Cantidad de flujo
Dirección
(1,2)
(20, 0) - (0, 20) = (20, -20)
20
1→2
(1,3)
(30, 0) - (0, 30) = (30, -30)
30
1→3
(1,4)
(10, 0) - (0, 10) = (10, -10)
10
1→4
(2,3)
(40, 0) - (40, 0) = (0, 0)
0
-
(2,5)
(30, 0) - (10, 20) = (20, -20)
20
2→5
(3,4)
(10, 5) - (0, 15) = (10, -10)
10
3→4
(3,5)
(20, 0) - (0, 20) = (20, -20)
20
3→5
(4,5)
(20, 0) - (0, 20) = (20, -20)
20
4→5



A continuacion Veremos un video con la alplicacion del algoritmo de Ford-Fullkerson







Redes De Flujo De Costo Minimo

Modelo de la ruta más corta
Considere una red conexa y no dirigida con dos nodos especiales llamados origen y destino. A cada ligadura (arco no dirigido) se asocia una distancia no negativa. El objetivo es encontrar la ruta más corta (la trayectoria con la mínima distancia total) del origen al destino.
Se dispone de un algoritmo bastante sencillo para este problema. La esencia del procedimiento es que analiza toda la red a partir del origen; identifica de manera sucesiva la ruta más corta a cada uno de los nodos en orden ascendente de sus distancias (más cortas), desde el origen; el problema queda resuelto en el momento de llegar al nodo destino.
Algoritmo de la ruta más corta:
  1. Objetivo de la n-ésima iteración: encontrar el n-ésimo nodo más cercano al origen. (Este paso se repetirá para n=1,2,… hasta que el n-ésimo nodo más cercano sea el nodo destino.)
  2. Datos para la n-ésima iteración: n-1 nodos más cercanos al origen (encontrados en las iteraciones previas), incluida su ruta más corta y la distancia desde el origen. (Estos nodos y el origen se llaman nodos resueltos, el resto son nodos no resueltos.)
  3. Candidatos para el n-ésimo nodo más cercano: Cada nodo resuelto que tiene conexión directa por una ligadura con uno o más nodos no resueltos proporciona un candidato, y éste es el nodo no resuelto que tiene la ligadura más corta. (Los empates proporcionan candidatos adicionales.)
  4. Cálculo del n-ésimo nodo más cercano: para cada nodo resuelto y sus candidatos, se suma la distancia entre ellos y la distancia de la ruta más corta desde el origen a este nodo resuelto. El candidato con la distancia total más pequeña es el n-ésimo nodo más cercano (los empates proporcionan nodos resueltos adicionales), y su ruta más corta es la que genera esta distancia.

PROBLEMA DEL FLUJO DE COSTO MÍNIMO
El problema de flujo de costo mínimo tiene una posición medular entre los problemas de optimización de redes; primero, abarca una clase amplia de aplicaciones y segundo, su solución es muy eficiente. Igual que el problema del flujo máximo, toma en cuenta un flujo en una red con capacidades limitadas en sus arcos. Igual que el problema de la ruta más corta, considera un costo (o distancia) para el flujo a través de un arco. Igual que el problema de transporte o el de asignación, puede manejar varios orígenes (nodos fuente) y varios destinos (nodos demandas) para el flujo, de nuevo con costos asociados. De hecho, estos cuatro problemas son casos especiales del problema de flujo de costo mínimo.
A continuación se describe el problema del flujo de costo mínimo:
  1. La red es una red dirigida conexa.
  2. Al menos uno de los nodos es nodo fuente.
  3. Al menos uno de los nodos es nodo demanda.
  4. El resto de los nodos son nodos de trasbordo.
  5. Se permite el flujo a través de un arco sólo en la dirección indicada por la flecha, donde la cantidad máxima de flujo está dada por la capacidad del arco. (Si el flujo puede ocurrir en ambas direcciones, debe representarse por un par de arcos con direcciones opuestas.)
  6. La red tiene suficientes arcos como suficiente capacidad para permitir que todos lo flujos generados por los nodos fuente lleguen a los nodos demanda.
  7. El costo del flujo a través del arco es proporcional a la cantidad de ese flujo, donde se conoce el costo por unidad.
  8. El objetivo es minimizar el costo total de enviar el suministro disponible a través de la red para satisfacer la demanda dada. (Un objetivo alternativo es maximizar la ganancia total del envío.)
FORMULACION DEL EJEMPLO
Problema del flujo de costo mínimo (Ejemplo)
La DISTRIBUTION UNLIMITED CO. Fabricará el mismo nuevo producto en dos plantas distintas y después tendrá que enviarlo a dos almacenes. La red de distribución disponible para el envío de este producto se muestra en la figura, donde A y B son las fábricas, D y E son los almacenes y C es el centro de distribución. Las cantidades que deben enviarse desde A y B se muestran a la izquierda, y las cantidades que deben recibirse en D y E se muestran a la derecha. Cada flecha representa un canal factible de envío. A puede enviar directamente a D y tiene tres rutas posibles (ACE, ABCE y ADE) para mandar bienes a E. La fábrica B tiene solo una ruta a E (BCE) y una a D (BCED). El costo por unidad enviada a través de cada canal se muestra al lado de la flecha. También, junto a AB y CE se muestran las cantidades máximas que se pueden enviar por estos canales. Los otros canales tienen suficiente capacidad para manejar todo lo que las fábricas pueden enviar.
La decisión que debe tomarse se refiere a cuánto enviar a través de cada canal de distribución. El objetivo es minimizar el costo total de envío.
Formulación:
Minimizar
Sujeto a:
APLICACIÓN PRÁCTICA DEL PROBLEMA DEL FLUJO DE COSTO MÍNIMO
El tipo más importante de aplicación del problema del flujo de costo mínimo es en la operación de la red de distribución de una compañía. En la siguiente tabla se muestran algunos tipos de aplicaciones comunes del problema de del flujo de costo mínimo:
Tipo de Aplicación
Nodos Fuentes
Nodos de Trasbordo
Nodos de Demanda
Operación de una red de distribución
Fuentes de bienes
Almacenes intermedios
Consumidores
Administración de desechos sólidos
Fuente de desechos sólidos
Instalaciones de procesamiento
Rellenos
Operación de una red de suministros
Agentes de ventas
Almacenes intermedios
Instalaciones de procesamiento
Coordinación de mezcla de productos en plantas
plantas
Producción de u artículo específico
Mercado del producto específico
Administración de flujo de efectivo
Fuentes de efectivo en tiempos específicos
Opciones de inversión a corto plazo
Necesidades de efectivo en tiempos específicos



En Los Siguientes Videos Veremos la Aplicacion Del flujo de costo minimo y del algoritmo de dijkstra


                                     





Algoritmo de flujo máximo

Tenemos el conocido problema de flujo máximo o maximal: ¿cuál es la tasa mayor a la cual el material puede ser transportado de la fuente al sumidero sin violar ninguna restricción de capacidad?
En otras palabras, el problema consiste en determinar la máxima capacidad de flujo que puede ingresar a través de la fuente y salir por el nodo de destino.
El procedimiento para obtener el flujo máximo de una red, consiste en seleccionar repetidas veces cualquier trayectoria de la fuente al destino y asignar el flujo máximo posible en esa trayectoria.
Capacidad residual: es la capacidad adicional de flujo que un arco puede llevar:
c_{f}(u,v)= c(u,v) - f(u,v) \,
§  Dada una red de flujo máximo, plantee la red residual asociada.
§  Encuentre la trayectoria de la fuente al destino con capacidad de flujo estrictamente positivo (si no existe alguno, es por que se ha encontrado el óptimo).
§  Examine estas trayectorias para encontrar la rama o arco con la menor capacidad de flujo restante e incremente en éste valor, la capacidad del flujo en sentido contrario.
§  Determine todas las trayectorias estrictamente positivas, hasta que no se permita flujo del nodo a un nodo destino.

Podemos, mediante el Algoritmo de Ford-Fulkerson, encontrar el flujo máximo de una red.
En el siguiente video podremos ver de manera mas detallada como funciona el algoritmo de flujo maximo.


Fuente y Sumidero

Una Red de Transporte es una grafica dirigida, simple, con pesos y que debe cumplir las siguientes:
  • Poseer una fuente o vértice fijo 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.
'Modelos de redes'
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 posee ninguna 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" o vertice sumidero

Algovidea - Método simplex para flujo en redes

TEORIA DE LAS REDES DE FLUJO

Entendiendo una red de flujo como un grafo dirigido, donde la fuente es quien produce o inicia el traspaso de algún material o producto por los arcos, estos últimos, vistos como caminos o conductos y tomando en cuenta la ley de corrientes de Kirchoff, donde, la suma de flujos entrantes a un vértice debe ser igual a la suma de flujos saliendo del vértice.




(L.C.) – línea de corriente o de flujo en la trayectoria seguida por las partículas de agua al fluir a través del suelo. 

(L.E.) – es aquella que une puntos en donde se tiene el mismo potencial hidráulico (h). 

(Tubo de Corriente) – es el espacio comprendido entre líneas de corriente vecinas. 

(Red de Flujo) – es el conjunto de líneas de corriente y de líneas equipotenciales. 

(Celda de Flujo) – es el espacio comprendido entre dos líneas equipotenciales vecinas y dos líneas de corriente vecinas. 

Una vez encontrada la ecuación diferencial, lo que sigue es integrarla y para ello existen diferentes caminos, uno de ellos es emplear métodos numéricos que finalmente permitan la generación de programas de computo para casos especiales, otro método es el gráfico mediante el trazo de redes de flujo; en clase se hará énfasis en este último por que es aplicable a todos los casos reales aun los más complejos; todo ello es para finalmente obtener gastos y presiones. 

En el caso del trazo de redes de flujo deben considerarse las siguientes condiciones:
1. Las líneas de corriente no deben intersectarse.
2. Las líneas equipotenciales no deben intersectarse.
3. La intersección de l.c. y l.e. debe ocurrir a 90°. 

Las razones de lo anterior son: en el caso 1 por que pasaría de flujo laminar a turbulento y en el caso 2 significaría que en el punto de intersección de dos líneas equipotenciales la partícula de agua tendría simultáneamente dos potenciales hidráulicos y se generaría un vórtice y el flujo dejaría de ser laminar.
Para demostrar que la intersección entre una línea de corriente y una equipotencial debe ocurrir a 90° es conveniente recordar: 

a) la dirección del vector velocidad de una partícula de agua debe ser en cada punto tangente a la trayectoria, o sea, a la línea de corriente. 

b) Para que haya flujo de agua, o sea, para que exista velocidad en el agua es necesario que se tenga una diferencia de potencial hidráulico. 

Con base en lo anotado en a y en b se puede demostrar lo solicitado de que si la intersección entre l.c. y l.e. no ocurre a 90° la velocidad tiene proyección sobre la tangente a la línea equipotencial en el punto de intersección y consecuentemente habría flujo de agua a lo largo de la l.c. lo que no puede ocurrir por que todos los potenciales hidráulicos en esa línea son iguales.