Clases

Problemas de flujos.
Existen muchos problemas de flujos en redes. Una red es un sistema de líneas o canales que conectan diferentes puntos y trasmiten algún tipo de información. Algunos ejemplos de redes son las líneas de comunicación, redes de ferrocarril, redes de tuberías de agua, redes de carreteras, redes de aviación, etc. En todas estas redes estaremos interesados en enviar algunamercancía específica desde ciertos puntos de suministro a algunos puntos de demanda. Por ejemplo, en un sistema de tuberías podríamos enviar agua. Muchos de los problemas de flujos en redes se pueden formular como problemas de programación lineal y obtener su solución mediante el método del simplex. Sin embargo, se han desarrollado otras técnicas más eficientes que varían con el problema en cuestión. Deentre este tipo de problemas destacamos los siguientes:

-

Problema de flujo máximo. Problema de flujo a coste mínimo.

Problema de flujo Máximo.
Se considera el problema de trasladar una cierta mercancía desde un punto específico, llamado fuente a un punto de destino, denominado sumidero. Para ello se considera un grafo dirigido G = (V,A), en el que se consideran dos nodos o vértices: unodenominado nodo fuente y otro denominado nodo destino. Por supuesto, se considera que no existe un arco directo que conecte el nodo fuente con el nodo destino. Por supuesto, el grafo estará formado por unos nodos intermedios conocidos como puntos de transbordo a través de los cuales el flujo (la mercancía) es desviado. Sea V = conjunto de todos los vértices o nodos del grafo. fij = el flujo quecircula por el arco (i,j). f = cantidad total de flujo que se lleva desde el nodo fuente al nodo destino. kij = capacidad del arco (i,j). Ejemplo: s = nodo fuente n = nodo destino 1, 2 = nodos intermedios
s 1 n 2

Objetivo: Determinar el máximo flujo f que se puede enviar desde el nodo fuente s al nodo destino n, teniendo en cuenta las capacidades kij sobre el flujo de cada arco (i,j) y que elflujo se debe conservar. Modelo de programación lineal:

Max s.a.

z =f

j∈Γ + ( i )

∑f

ij

−

j∈Γ − ( i )

∑f

ji

=0

∀i ∈ V - {s, n}

(1.1) (1.2)

0 ≤ f ij ≤ k ij

∀(i, j) ∈ A

Las ecuaciones (1.1) representan la conservación del flujo en los nodos. Mientras que las restricciones (1.2) son sobre el flujo que circula por cada arco, para que no sea negativo y nosupere la capacidad del arco. En el ejemplo anterior se traduce en
Max s.a. z= f f s1 + f s 2 = f f12 + f 1n = f s1 + f 21 f 21 + f 2 n = f s 2 + f12 f1n + f 2 n = f 0 ≤ f s1 ≤ k s1 0 ≤ f s2 ≤ ks2 0 ≤ f 12 ≤ k12 0 ≤ f 21 ≤ k 21 0 ≤ f1n ≤ k1n 0 ≤ f 2n ≤ k 2n

Veamos un método eficiente para resolver el problema del flujo máximo directamente sin usar el método del simplex. Conceptos previos:Definición: Dado cualquier nodo i todos los arcos que salen del nodo i se denominan arcos hacia delante con respecto al nodo i. Definición: Dado cualquier nodo i todos los arcos que entran al nodo i se denominan arcos hacia atrás para el nodo i.

Definición: Un corte que separa el nodo fuente del nodo destino es una partición de los nodos de la red en dos subconjuntos S y S* tal que el nodo fuente estáen S y el nodo destino está en S*. Un ejemplo de corte en el ejemplo anterior podría ser (S, S*) dado por S = {s,1,2}.
1 s n 2

Corte Otro corte que separa s y n es el siguiente:

1 s n 2

Corte Definición: La capacidad de un corte es la suma de todas las capacidades de los arcos procedentes de los nodos de S a los nodos en S*. Se denota K(S, S*). Esto es

K (S , S * ) =
En los cortesanteriores, sus capacidades son: S = {s,1,2}, K(S,S*) = k1n + k2n S = {s,2}, K(S,S*) = ks1 + k21 + k2n

ij ( i , j )∈( S , S * )

∑k

Definición: El corte con la capacidad más pequeña se denomina corte mínimo.

A partir de los ejemplos anteriores de cortes se puede apreciar que si todos los arcos de un corte se eliminan de la red entonces no existe un camino que una el nodo fuente con el...