introduccion

Flujo máximo en redes

En teoría de grafos, un grafo dirigido con pesos es también conocido como una red.
En los problemas de flujo en redes, las aristas representan canales por los que puede
circular cierta cosa: datos, agua, coches, corriente eléctrica, etc. Los pesos de las aristas
representan la capacidad máxima de un canal: velocidad de una conexión,volumen máximo de agua, cantidad máxima de trafico, voltaje de una línea eléctrica, etc.; aunque es posible que la cantidad real de flujo sea menor.

El problema del flujo máximo consiste en lo siguiente: dado un grafo dirigido con pesos, G = (V, A, W ), que representa las capacidades máximas de los canales, un nodo de inicio s y otro de fin t en V , encontrar la cantidad máxima de flujoque puede circular desde s hasta t.

Ejemplo:




El grafo de la izquierda, G, pintado con líneas continuas, representa las capacidades máximas; sería la entrada del problema. El grafo de la derecha, F , representado con líneas discontinuas,
indica los flujos reales; es una posible solución para el problema.

La solución del problema debe cumplir lassiguientes propiedades:

La suma de los pesos de las aristas que salen de s debe ser igual a la suma de las
aristas que llegan a t. Esta cantidad es el flujo total entre s y t.

Para cualquier nodo distinto de s y de t, la suma de las aristas que llegan al nodo debe ser igual a la suma de las aristas que salen al mismo.

Los pesos de las aristas en F no pueden superar lospesos máximos indicados en G. Es decir, si CG (a, b) es el peso de la arista de G y CF (a, b) es el peso de la misma arista en F , entonces CF (a, b) ≤ CG (a, b).

Una vez planteado el problema, vamos a estudiar la forma de resolverlo. En primer
lugar propondremos un algoritmo intuitivo, y a continuación analizaremos si garantiza la solución optima o no.



Un posible algoritmopara calcular el flujo máximo

La idea de los flujos, que van desde s hasta t, es muy próxima a la de un camino
por el que circula cierto fluido. Cada unidad de flujo que llega hasta un nodo, debe salir
por alguna de sus aristas. Por lo tanto, un posible algoritmo podría basarse en encontrar
caminos (s, v1 , v2 , ..., vk , t) en G.


Ejemplo: EN EL DIBUJO VA SOLO ELGRAFO “G” Y “F”




Si en el grafo G tomamos el camino (s, a, b, t), vemos que las aristas por las que pasa tienen pesos: 5, 2, 4. El máximo flujo que podemos mandar por ese camino está limitado por el mínimo de las capacidades por las que pasa el camino. De esta forma, el algoritmo iría encontrando
caminos en G, añadiendo los flujos correspondientes al grafo F y quitándolos de G. Y
asíseguiría hasta que no queden mas caminos de flujo por enviar.

El Método de las Dos Fases es una variante del Algoritmo simplex, que es usado como alternativa al Método de la Gran M, donde se evita el uso de la constante M para las variables artificiales .

La desventaja de la técnica M es el posible error de cómputo que podría resultar de asignar un valor muy grande a la constante M. Estasituación podría presentar errores de redondeo en las operaciones de la computadora digital. Para evitar esta dificultad el problema se puede resolver en 2 fases.
 
FASE 1. Formule un nuevo problema reemplazando la función objetivo por la suma de las variables artificiales.
La nueva función objetivo se minimiza sujeta a las restricciones del problema original. Si el problema tiene un espaciofactible el valor mínimo de la función objetivo óptima será cero, lo cual indica que todas las variables artificiales son cero. En este momento pasamos a la fase 2.
 
* Si el valor mínimo de la función objetivo óptima es mayor que cero, el problema no tiene solución y termina anotándose que no existen soluciones factibles
 
FASE 2. Utilice la solución óptima de la fase 1 como solución de inicio...