trabajo

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
encuestión. De entre 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 dosnodos o vértices: uno denominado
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 delgrafo.
fij = el flujo que circula 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).
1

Ejemplo:
s = nodo fuente
n = nodo destino
1, 2 = nodos intermedios

s

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 kijsobre el flujo de cada arco (i,j) y que el
flujo se debe conservar.
Modelo de programación lineal:

Max

z =f

s.a.

∑f

j∈Γ + ( i )

ij

−

∑f

j∈Γ − ( i )

0 ≤ f ij ≤ k ij

ji

=0

∀(i, j) ∈ A

∀i ∈ V - {s, n}

(1.1)
(1.2)

Las ecuaciones (1.1) representan la conservación del flujo en los nodos. Mientras que
las restricciones (1.2) son sobre el flujo quecircula por cada arco, para que no sea
negativo y no supere 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áximodirectamente
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 delos
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 losnodos de S a los nodos en S*. Se denota K(S, S*). Esto es

K (S , S * ) =

∑k

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

En los cortes anteriores, sus capacidades son:
S = {s,1,2}, K(S,S*) = k1n + k2n
S = {s,2}, K(S,S*) = ks1 + k21 + k2n
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...