REDES (FLUJO MAXIMO)

Modelo de Flujo Máximo

Se trata de enlazar un nodo fuente y un nodo destino a través de una 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:

1. Todo flujo a través de una red conexa dirigida se origina en un nodo, llamado fuente, y termina en otro nodo llamado destino.
2. Los nodos restantes son nodos de trasbordo.
3. 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á dad por la capacidad del arco. En la fuente, todos los arcos señalan hacia fuera. En el destino, todos señalan hacia el nodo.
4. 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 la fuente 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 símplex y usar cualquiersoftware. Sin embargo, se dispone de un algoritmo de trayectorias aumentadas mucho más eficientes. El algoritmo se basa en dos conceptos intuitivos, el de red residual y el de trayectoria aumentada.

Algoritmo de la trayectoria de aumento para el problema de flujo máximo:

1. 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).
2. Se identifica la capacidad residual c* de esta trayectoria de aumento encontrando el mínimo de las capacidades residuales de los arcos sobre esta trayectoria. Se aumenta en c* el flujo de esta trayectoria.
3. 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.

4. Flujo máximo.

   Al obtener una red, si se desea hallar su flujo máximo, lo que hay que hacer, es seleccionar un inicio, y un fin.

   Por ejemplo para la siguiente red, tomaremos como inicio u origen el nodo 1, y como fin el nodo 5.

   

    

   Al ubicarnos en el nodo 1, lo siguiente por hacer es realizar una etiquetarlo de forma [ ,--], y estando ubicados en este nodo, lo que haremos es escoger cual de las aristas es la que tiene el mayor valor e irnos por este, sabemos que se irá por la arista de valor 30, que se dirigirá al nodo 3, estando en el nodo 3, lo etiquetaremos de la siguiente manera, [valor de envió, de que nodo viene], es decir [30,1], posteriormente se buscara el flujo máximo que parte de 3, es decir 20, que se dirige a 5, estando en 5 se etiquetara de la misma forma, [20,3].

   

     

   Ahora se declarara k_min,    cuyos valores serán los valores de los nodos por los que se viajo, es decir [30,10], el valor de menor  valor es el de 10, por lo tanto k_min será igual a 10.

   Ahora recorriendo este camino, lo que haremos es lo siguiente;

   C_ij, C_ji = [i-k , j+k]

   Donde i sera el valor de salida en la arista, y j el valor de llegada de la misma.

   Ahora aplicando esto en nuestra red.

   C₁₃, C₃₁ = [30-10, 0+10]

   C₃₅, C₅₃ = [20-10, 0+10]

   De esta forma:

   C₁₃, C₃₁ = [20, 10]

   C₃₅, C₅₃ = [10, 10]

   Se reemplazan estos valores en los nodos indicados, el primer numero sera la salida, y el Segundo la llegada.

   Después de reemplazar los valores en la red.

   Posteriormente haremos el mismo procedimiento de escoger desde el nodo de inicio, el valor máximo, y realizar su respectiva etiquetada.

   

     

   Luego haremos el mismo procedimiento de

   C_ij, C_ji = [i-k , j+k]

   
   

   Y se hallara mos k_min

   k_min = 5;

   Haremos su respectiva etiquetada.

   

   Esta es la red obtenida.

   
   

   Ahora repetiremos este procedimiento hasta dejar las conexiones saturadas, el decir que su salida es de 0,

   Para así finalmente después de obtenidas todas las k_min  realizar su sumatoria, para así obtener su flujo máximo.