Metodo dual

Programación Matemática para Economistas

132

4.- Dualidad. Método Dual del Símplex.
Como ya vimos en el capítulo primero, dado un problema de programación no lineal,

Max f (x) s.a g(x) ≤ b x∈D donde su lagrangiana toma la forma:
L(x, λ) = f(x) - λt (g(x) - b),

se denomina problema primal a:
Max Min L (x, λ )
x

λ

mientras que, su problema dual sería:
Min Max L (x, λ )
λ
xverificándose, bajo condiciones de convexidad, que:
Max Min L (x, λ ) = Min Max L (x, λ )
x

λ

λ

x

A partir de estas ideas vamos a determinar el problema dual asociado al programa lineal general:
Max ct x s.a Ax ≤ b

(18)

al cual denominaremos primal. La función Lagrangiana toma en este caso la forma
L(x, λ) = ctx - λt(Ax-b)

definida en Rn+ x

Rm+.

Dado que enprogramación lineal se verifican las condiciones de convexidad podemos definir como problema dual del anterior al:
Min L (x ,λ ) = c t x − λ t ( Ax − b) ∂L s. a (x ,λ ) = 0 ∂x λ≥0
R. Caballero, T. Gómez, M. González, M. Hernández, F. Miguel, J. Molina, M.M. Muñoz, L. Rey, F. Ruiz

Programación Matemática para Economistas

133

Si calculamos la derivada que aparece en este problema tenemos:∂L = ct − λt A = 0 ⇒ ct = λt A ∂x
y como L(x, λ) = ctx - λt(Ax-b)= (ct - λtA)x + λt b, obtenemos como función objetivo del problema dual L(x, λ) = λt b, puesto que, el primer sumando que aparecía en la lagrangiana vale cero. De esta forma, el problema dual del (18) es: Min λ t b s. a λ t A = c t λ≥0 observándose que, a diferencia de la Programación no Lineal, en los problemas duales de ProgramaciónLineal no aparecen las variables del primal y recíprocamente. En el problema (18) no hemos supuesto que estén explícitamente señaladas restricciones de no negatividad para las variables. Para ver cómo afecta este hecho al problema dual, supongamos un problema primal de la forma:
Max ( c 1  x1  c 2 )  x 2 

s.a A 11x 1 + A 12 x 2 ≤ b 1 A 21x 1 + A 22 x 2 = b 2 x1 ≥ 0

donde hemosconsiderado que existen algunas restricciones de igualdad. En este caso la lagrangiana asociada sería: L(x1, x2, λ1, λ2, λ3) = c1x1 + c2x2 - λ1t(A11x1 + A12x2 - b1) - λ2t(A21x1+A22x2-b2) - λ3t(-x1) la cual estará sujeta a lo siguiente:

∂L t t t = c 1 − λ1 A 11 − λ 2 A 21 + λ 3 = 0 ∂ x1 ∂L t t = c 2 − λ1 A 12 − λ 2 A 22 = 0 ∂ x2
λ 1 ≥ 0, λ 3 ≥ 0

R. Caballero, T. Gómez, M. González, M. Hernández,F. Miguel, J. Molina, M.M. Muñoz, L. Rey, F. Ruiz

Programación Matemática para Economistas

134

Al igual que antes, si sacamos factor común en la lagrangiana obtenemos: L(x1, x2, λ1, λ2, λ3) = (c1 - λ1tA11 - λ2tA21 + λ3t)x1 + (c2 - λ1tA12 - λ2tA22)x2 + +λ1tb1 + λ2tb2 con lo cual, si observamos las resticciones anteriores, nos queda: L(x1, x2, λ1, λ2, λ3) = λ1tb1 + λ2tb2 Por otra parte, sicombinamos la primera restricción con la última, es decir,

∂L t t t = c 1 − λ1 A 11 − λ 2 A 21 + λ 3 = 0 ∂ x1
λ3 ≥ 0

tendremos:
t t λ t3 = − c 1 + λ1 A 11 + λ 2 A 21 ≥ 0

con lo cual, podemos unir las dos en la siguiente:
t t λ1 A 11 + λ 2 A 21 ≥ c 1

Por consiguiente, el problema dual asociado al primal anterior será:
t t Min λ 1b 1 + λ 2 b 2 t t s.a λ 1 A 11 + λ 2 A 21 ≥ c 1 t t λ1 A 12 + λ 2 A 22 = c 2

λ1 ≥ 0

Asimismo se puede comprobar, fácilmente, que el dual del dual es el primal; esto nos lleva a considerar el proceso de paso al dual como una caja negra con la siguiente función: Maximizar Restricciones ≤
= sí no

Minimizar No negatividad Variables

No negatividad Variables

sí no

≥
=

Restricciones

R. Caballero, T. Gómez, M. González, M.Hernández, F. Miguel, J. Molina, M.M. Muñoz, L. Rey, F. Ruiz

Programación Matemática para Economistas

135

es decir, a un problema de Programación Lineal de maximización le corresponde un problema dual de minimización; si una restricción del primal es de desigualdad (≤), la variable dual correspondiente "sí" está restringida a ser no negativa; si la restricción es de igualdad, la variable...