Simplex Dual

CLase 24
El M´todo Simplex Dual.
e
• La versi´n del m´todo simplex que hemos estudiao
e
do, la cual llamaremos simplex primal, comienza
con una s.b.f. para el problema primal e itera hasta
que las condiciones de optimalidad primal se satisfagan.
• Es posible tambi´n aplicar el m´todo simplex al
e
e
problema dual, comenzando con una soluci´n factible
o
dual e iterando hasta que lascondiciones de optimalidad dual se satisfagan.
Algoritmo Simplex Dual.
• Las condiciones de optimalidad para el problema
primal corresponden a las condiciones de factibilidad para el dual.
• Este resultado se deduce como parte de la demostraci´n
o
del teorema de dualidad fuerte donde se demuestra
que la condici´n de optimalidad primal
o
c N t − c B t B −1 N ≥ 0
es equivalente a lacondici´n de factibilidad dual
o
A t y ≤ c,
y = B −tcB
siendo y el vector de multiplicadores del simplex
correspondiente a la base B.
1

Cont....
• En cada iteraci´n, el simplex primal se mueve a
o
trav´s de una sucesi´n de bases primal factibles,
e
o
pero dual infactibles, tratando de reducir la infactibilidad dual hasta alcanzar la condici´n de factibilidad
o
dual.
• El m´todosimplex dual trabaja de manera dual.
e
• Este se mueve a trav´s de una sucesi´n de bases
e
o
factibles dual pero infactible primal, tratando de reducir infactibilidad primal hasta que las condiciones
de factibilidad primal se satisfagan.
• Aunque el m´todo simplex dual puede verse como
e
e
e
el m´todo simplex aplicado al problema dual, ´ste
puede implementarse directamente en t´rminos dele
problema primal, si se dispone de una soluci´n factible
o
dual inicial.
• La importancia pr´ctica del simplex dual est´ en
a
a
relaci´n al tema de sensibilidad o an´lisis post optio
a
mal, cuesti´n que se discutir´ en la pr´xima secci´n.
o
a
o
o

2

Cont.....
• Suponemos que disponemos de una base dual-factible,
es decir, los costos reducidos son no negativos.
• Lainformaci´n necesaria para el algortimo es B −1 ,
o
−1 b, y los valores actuales de los costos
xB = ˆ = B
b
reducidos {cj }.
• El m´todo simplex dual termina cuando la base ace
ı
co
e
tual es factible primal, as´ una iterac¸i´n del m´todo
comienza verificando si xB ≥ 0. Si no, se utiliza
alg´n (xB )s < 0 como fila pivote.
u
• Describimos a continuaci´n una iteraci´n del m´todo
o
o
esimplex dual, usando un argumento similar al dado
para el caso simplex primal.
• Supongamos que una variable (xB )s es infactible de
modo que ˆs < 0.
b
• En t´rminos de la base actual la s-´sima restricci´n
e
e
o
tiene la forma
ˆs, j xj = ˆs < 0,
a
b

(xB )s +
j ∈N

donde N es el conjunto de ´
ındices de las variables
no b´sicas, y {ˆs, j } son las entradas de la fila s de
a
a
−1A.
B
3

Cont.....
• Si alg´n ˆs, j < 0 y una variable xj reemplaza (xB )s
ua
en la base, entonces el nuevo valor de xj ser´
ıa
ˆs
b
>0
ˆs, j
a
esto es, la nueva variable b´sica ser´ factible.
a
ıa
• No todas las variables no b´sicas pueden entrar a
a
la base ya que las condiciones de factibilidad dual
(optimalidad primal) deben permanecer satisfechas.
• Si xj es la variableque entra, los nuevos costos
reducidos satisfacen
ˆs, l
a
¯l = ˆl − ˆl
c
c
c
, l = 1 , 2, . . . , n
ˆs, j
a
• (Si l = j entonces ¯l = 0). Como cada ¯l debe ser
c
c
no negativo, la menor raz´n {|ˆs, j |}, con ˆs, j < 0
o
a
a
determina cual de los costos reducidos se hace cero
primero.
• Esta raz´n determina el elemento pivote ˆs, t .
o
a
• En nuestro ejemplo, que se ver´posteriormente, la
a
variable que deja la base es la m´s negativa.
a
4

Cont.....
• Cualquier variable negativa puede elgirse como variable de salida.
• El test de la raz´n requiere el c´lculo de
o
a
ˆj
c
ˆs, j
a
para cualquier variable no b´sica j con ˆs, j < 0.
a
a
• As´ es necesario conocer los elementos en la fila
ı,
pivote. Si se usa el tableau, esta informaci´n esta
o...