Redes

Universidad de Chile
Facultad de Ciencias F´
ısicas y Matem´ticas
a
Departamento de Ingenier´ Industrial
ıa

IN34A: Clase Auxiliar

Flujo en Redes
Marcel Goic F.1

1

Esta es una versi´n bastante preliminar por lo que puede contar con numerosas faltas de ortograf´ y
o
ıa
errores no forzados. Si encuentran alguno favor de denunciarlo a mgoic@cec.uchile.cl

IN34A: Optimizaci´no

1.

Pag. 1

Una brev´
ısima introducci´n.
o

El tema de flujo en redes es muy amplio y tiene muchas aplicaciones: Redes de distribuci´n el´ctrica, de comunicaci´n , de regad´ etc. De entre los infinitos problemas posibles,
o
e
o
ıo,
podemos distinguir familias de problemas: Flujo a costo m´
ınimo, Flujo m´ximo por una red,
a
Ruta mas corta, etc.
En general, muchos de losproblemas de redes pueden verse como casos particulares de
programaci´n lineal. Sin embargo, aun para instancias peque˜as, los problemas de redes
o
n
tienen tener demasiadas variables y restricciones haciendo muy dificil su resoluci´n 2 . Es
o
por esto que se hace muy necesario aprovechar la estructura especial de cada problema para
encontrar algoritmos especializados a cada caso.

2.

Flujo aCosto M´
ınimo

Queremos buscar una forma de distribuir flujo por una red de modo de hacerlo al menor
costo posible.

2.1.

Simplex especializado a redes (Resum´n)
e

´
Soluci´n B´sica ⇔ Arbol Generador.
o
a
cij = cij − πi + πj

πi , πj variables duales.

Condici´n de optimalidad:
o
Sean:

fij = Flujo por el arco ij.

lij = Cota m´
ınima para el flujo por el arco ij.lij ≤ fij ≤ uij

uij = Cota m´xima para el flujo por el arco ij.
a
Con esto las condiciones de optimalidad pueden resumirse como:
(1) cij = 0 ∀(i, j)b´sico.
a
a
(2) cij ≥ 0 ∀(i, j) no b´sico tal quefij = lij .
(3) cij ≤ 0 ∀(i, j) no b´sico tal quefij = uij .
a
Luego, lo que tenemos que hacer es resolver (1) teniendo como inc´gnitas los π. Para
o
ello, requerimos asignar πr = 0 paraalg´n r arbitrario. Con estos valores de πi vemos
u
si se cumplen las condiciones (2) y (3).
Variable que entra: (p,q) con m´xima violaci´n de optimalidad.
a
o
2

Por ejemplo, hasta Abril de 1999, el cl´sico problema del vendedor viajero solo hab´ sido resuelto para
a
ıa
13509 ciudades, lo cual demor´ 4 meses en ser resuelto utilizando para ello 3 servidores, un total de 12
o
procesadoresy 32 PCs.

IN34A: Optimizaci´n
o

Pag. 2

Variable que sale: Al agregar el flujo (p,q) en el ´rbol generador formado por las
a
variables b´sicas, se formar´ un ciclo.
a
a
• Si fpq = lpq ⇒ Aumentamos el flujo por (p,q)
• Si fpq = upq ⇒ Disminuimos el flujo por (p,q)
Luego se env´ flujo hasta que:
ıa
i) Arco (r, s) en el sentido del flujo se satura en cota superior urs ⇒ (r, s) sale dela
base con valor urs .
ii) Arco (r, s) en el sentido contrario al flujo alcanza la cota inferior lrs ⇒ (r, s) sale
de la base con valor lrs .
iii) Arco (p, q) alcanza su otra cota ⇒ No hay cambio de base, solo cambian los valores
de los flujos.
Notar que en cada iteraci´n cambian todos los valores de los flujos que estaban involuo
crados en la formaci´n de un ciclo en el ´rbol generador(recordar que siempre debe
o
a
cumplirse la restricci´n de conservaci´n de flujo en cada nodo).
o
o

2.2.

Fase I en redes (Resum´n)
e

Simplex especializado a redes nos exige una solucin b´sica factible inicial. Si no disponemos
a
de ella, requeriremos de un algoritmo para buscarla.
1. Agregamos un nodo artificial µ con los respectivos arcos que lo unan a los nodos ya
existentes en elproblema original (cotas: (0, +∞)).
2. Definimos un flujo inicial factible para cada uno de los arcos:
Para los arcos del problema original fijamos el flujo en la cota inferior.
Para los nuevos asignamos el flujo tal que el problema sea factible.
3. Resolvemos el problema tomando como base inicial (arbol generador), los flujos asociados al nodo artificial µ y asignando la siguiente estructura de...