programacion lineal

Formulacion del problema de la rut a mas corta en programacion lineal
En est a secci´ n se describen dos formulaciones de programaci´ n lineal
o
o
para el problema de la rut a m´ s corta. Las formulaciones son generales, en
a
el sent ido que se pueden usar para det erminar la rut a m´ s cort a ent re dos
a
nodos cualquiera de la red.
Suponga que la red de rut a m´ s cort a t iene nnodos, y que se desea dea
t erminar la rut a m´ s cort a ent re dos nodos cualesquiera s y t de la red.
a
For mulaci´ n 1: En est a formulaci´ n se supone que ent ra a la red una unio
o
dad externa de flujo en el nodo s y sale en el nodo t, siendo s y t dos nodos
ent re los que se busca det erminarla rut a m´ s cort a.
a
Se definen
x i j = cant idad de flujo en el arco (i , j ) para t oda i y jfact ibles
ci j = longit ud del arco (i , j ) para t oda i y j fact ibles
Como s´ lo puede haber una unidad de flujo en alg´ n arco en cualquier moo
u
ment o, la variable x i j debe asumir solament e valores binarios (0 o 1). Ası, la
´
funci´ n objetivo del programa lineal se vuelve:
o
Minimizar z =

ci j x i j
t odos los arcos definidos (i ,j )

Hay una rest ricci´ n que represent a laconservaci´ n de flujo en cada nodo;
o
o
est o es, en cualquier nodo j ,
Flujo t ot al que entra = Flujo t ot al que sale
For mulaci´ n 2: La segunda formulaci´ n es en realidad el problema dual del
o
o
programa lineal en la formulaci´ n 1. Como la cant idad de rest ricciones en la
o
formulaci´ n 1 es igual a la cant idad de nodos, el problema dual t endr´ t ano
a
t as variables comocant idad de nodos haya en la red. Tambi´ n, las variables
e
duales no deben est ar rest ringidas, porque t odas las restricciones de la formulaci´ n 1 son ecuaciones. Sea
o

1

yj = la rest ricci´ n dual asociada al nodo j
o
Como s y t son los nodos inicial y t erminal de la red, el problema dual se
define como sigue:
Maximizar z = yt − ys
sujet a a
yj − yi ≤ ci j para t oda i y j factibles (yi , yj ∈ R , ∀i , j ).
Ej emplo 6.3-6
Se t iene la red de rut a de la figura 1. Suponer que se desea det erminar la rut a
m´ s corta del nodo 1 al nodo 2; est o es, s = 1 y t = 2. La figura 1 muest ra
a
c´ mo ent ra el flujo unit ario en el nodo 1 y sale en el nodo 2.
o

Figura 1: Inserci´ n de un flujo unit ario para det erminar la rut a m´ s cort a
o
a
ent re el nodo s = 1 y t =2. El n´ mero junt o a cada camino corresponde a
u
su largo respect ivo.

2

La list a del programa lineal asociado, usando la formulaci´ n 1, se ve a cono
t inuaci´ n:
o
Minimizar z =
Nodo 1
Nodo 2
Nodo 3
Nodo 4
Nodo 5

x 12 x 13 x 23 x 34 x 35 x 42 x 45
100 30 20 10 60 15 50
−1 −1
0
0
0
0
0
1
0 −1
0
0
1
0
0
1
1 −1 −1
0
0
0
0
0
1
0 −1 −1
0
0
0
0
1
01

=
=
=
=
=

−1
1
0
0
0

Las rest ricciones represent an la conservaci´ n de flujo en cada nodo. Por ejemo
plo, en el nodo 2 “ flujo que ent ra = flujo que sale” es x 12 + x 42 = 1 + x 23 .
N´ t ese que una de las rest ricciones siempre es redundant e. Por ejemplo, si se
o
suman las ult imas cuat ro rest ricciones er forma simult ´ nea se obt iene x 12 + x 13
´
a
= 1, que esigual que la rest ricci´ n 1.
o
La soluci´ n ´ pt ima es
o o
z = 55, x 13 = 1, x 34 = 1, x 42 = 1.
Est a soluci´ n expresa la rut a m´ s cort a del nodo 1 al nodo 2 como 1→3→4→2,
o
a
y la dist ancia asociada es z = 55 (millas).
Para aplicar la formulaci´ n 2, el problema dual asociado con el programa
o
lineal ant erior es
Maximizar z = y2 − y1
sujet a a
y2 −
y3 −
y3 −
y4 −
y5 −
y2−
y5 −

y1
y1
y2
y3
y3
y4
y4
yk

≤
≤
≤
≤
≤
≤
≤
∈ R,
3

100
30
20
10
60
15
50
∀k.

Aunque el problema dual ant erior es una definici´ n mat em´ t ica pura derivada
o
a
del problema primal, en realidad se puede int erpret ar el problema en una
forma l´ gica. Se define
o
yi = Dist ancia al nodo i .
Con est a definici´ n, la dist ancia m´ s cort a del nodo inicial...