Dualidad

DUALIDAD (parte 1) Asociado a todo problema de programación lineal, existe otro problema lineal llamado dual. Por ejemplo, la solución óptima del problema dual es la que proporciona los precios sombra del problema primal. Una de las aplicaciones más importantes es la interpretación y realización del análisis de sensibilidad (variar las condiciones y ver qué pasa con la solución óptima. Primal
nDual
m

Max Z s.a.
n

∑c x
j =1 j

j

Min W s.a.

∑b y
i =1 i

i

∑a x
j =1 ij

j

≤ bi

∀i = 1, 2,..., m ∀j = 1, 2,..., n

m

∑a
i =1

ij

yi ≤ c j

∀j = 1, 2,..., n ∀i = 1, 2,..., m

xj ≥ 0

yi ≥ 0

Resumen de Condiciones:
1. Un problema primal de maximización es un problema dual de minimización. 2. Los coeficientes de la función objetivo del primalson los “lados derechos” de las restricciones funcionales del dual. 3. Los lados derechos de las restricciones funcionales del primal son los coeficientes de la función objetivo del dual. 4. Los coeficientes de una variable de las restricciones funcionales del primal son los coeficientes de una restricción funcional del dual. 5. En el dual habrá tantas variables como restricciones en el primal. 6.En el dual habrá tantas restricciones como variables en el primal. 7. Para saber si las restricciones duales son de ≤, =, ó ≥ se ve tabla de relaciones
Primal-Dual. 8. Para saber si las variables duales son ≤ 0, = 0, ó ≥ 0 se ve tabla de relaciones PrimalDual.

Profesor: PhD (c) Jorge Rosales Salas

Page 1

Min Re st ≥ = ≤ Var ≥0 Irrestricta ≤0 Ejemplo:

Max Var ≥0 Irrestricta ≤ Re st ≤= ≥

Primal Max Z 3 x1 + 5 x2 s.a. x1 ≤ 4
2 x2 ≤ 12 3x1 + 2 x2 ≤ 18

Dual
Min W 4 y1 + 12 y2 + 18 y3 s.a. y1 + 3 y3 ≥ 3 2 y2 + 2 y3 ≥ 5 y1 ≥ 0 y2 ≥ 0 y3 ≥ 0

x1 ≥ 0 x2 ≥ 0

Primal
¿Cuántas Variables? = 2 ¿Cuántas Restricciones? = 3 ¿Coeficientes F.O? = 3 y 5 ¿Coef. de variable x1? = 1,0,3 ¿Coef. de variable x2? = 0,2,2 Variables mayor o igual a 0 Restricciones menor o igual a 0 >>> >>>>>> >>> >>> >>> >>>

Dual
2 Restricciones 3 Variables Lados derechos de las restricciones (3 y 5) Coeficientes de 1° restricción = 1,0,3 Coeficientes de 2° restricción = 0,2,2 Restricciones mayor o igual a 0 Variables mayor o igual a 0

Profesor: PhD (c) Jorge Rosales Salas

Page 2

Así como el primal buscaba las Xi, el dual busca las Yi, que coinciden con el análisis de precios sombraen el primal. En el problema dual y su método simplex dual se permiten valores derechos negativos por lo que no es necesario introducir variables artificiales como variables básicas iniciales. Lo que se hace es convertir las restricciones ≥ a ≤ multiplicando por (-1) y se agregan las de holgura.
Min W 4 y1 + 12 y2 + 18 y3 s.a. y1 + 3 y3 ≥ 3 2 y2 + 2 y3 ≥ 5 y1 ≥ 0 y2 ≥ 0 y3 ≥ 0 Max − W − 4 y1 − 12y2 − 18 y3 s.a. − y1 − 3 y3 ≤ −3 −2 y2 − 2 y3 ≤ −5 y1 ≥ 0 y2 ≥ 0 y3 ≥ 0

Max Z ` − 4 y1 − 12 y2 − 18 y3 s.a. − y1 − 3 y3 ≤ −3 −2 y2 − 2 y3 ≤ −5 y1 ≥ 0 y2 ≥ 0 y3 ≥ 0

Luego de pasar la función objetivo al lado derecho Z´ + 4y1 + 12y2 + 18y3: Creando la tabla simplex DUAL inicial vemos-:
Paso Var Bás Ec z 0 0 y4 1 y5 2 Z 1 0 0 y1 4 -1 0 y2 12 0 -2 y3 18 -3 -2 y4 0 1 0 y5 0 0 1 LD 0 -3 -5

1°Se ve la variable que sale (LD más negativo) : sale y5. 2° Se ve la variable que entra (cuociente mínimo en valor absoluto) : entra y2
Paso Var Bás Ec z 0 0 y4 1 y5 2 Z 1 0 0 y1 4 -1 0 y2 12 0 -2 -6 y3 18 -3 -2 -9 y4 0 1 0 y5 0 0 1 LD 0 -3 -5

Con esto se trabaja de la misma manera que la tabla simplex normal, con operaciones fundamentales para hacer la celda pivote 1 y el resto de loscoeficientes de la columna hacerlos 0.

Profesor: PhD (c) Jorge Rosales Salas

Page 3

Paso Var Bás Ec z 0 1 y4 1 y2 2

Z 1 0 0

y1 4 -1 0

y2 0 0 1

y3 6 -3 1

y4 y5 0 6 1 0 0 -1/2

LD -30 -3 5/2

1° Se ve la variable que sale (LD más negativo) : sale y4. 2° Se ve la variable que entra (cuociente mínimo en valor absoluto) : entra y3
Paso Var Bás Ec z 0 1 y4 1 y2 2 Z 1 0 0 y1 4 -1...