Dualidad

Universidad Tec Milenio: Maestría HG05007 – Métodos cuantitativos para la toma de decisiones

El modelo Dual
Asociado a cada problema de programación lineal original (llamado problema primo) existe otro problema de programación lineal denominado problema dual. El problema dual aporta información importante acerca de la solución del problema original pues la solución Simplex óptima decualquiera de los dos problemas conduce en forma automática a la solución óptima del otro.

HG05007. Métodos cuantitativos para la toma de decisiones. Sesión 5. Dualidad.

1

2

Formulación del Dual
Para generar un modelo dual sigue estas reglas usando el ejemplo: El problema primo es Max z = 15000 x1 + 12000 x2 sujeto a: Proceso 1 3 x1 Proceso 2 5 x2 Proceso 3 4 x1 + 6 x2 Empaque 8 x1 + 8 x2 Nonegatividad x1, x2 ≥ 0 donde: x1 = Producto 1 x2 = Producto 2

Formulación del Dual
• El número de variables del problema dual es igual al número de restricciones del problema primo. Tenemos cuatro restricciones en el primo (Procesos 1 al 3 y Empaque) Entonces tendremos cuatro variables de decisión en el dual: y1, y2 , y3, y4 • El número de restricciones del problema dual es igual al número devariables del problema primo. Tenemos dos variables de decisión: x1 y x2 Entonces tendremos dos restricciones en el dual.

≤ 180 ≤ 200 ≤ 360 ≤ 800

3

4

Formulación del Dual
• Los coeficientes de la primera restricción del problema dual son los coeficientes de la columna de la primera variable de decisión en las restricciones del problema primo. Lo mismo sucede con el resto de lasrestricciones duales y variables del modelo primo. Restricción dual 1: 3 y1 + 0 y2 + 4 y3 + 8 y4 Restricción dual 2: 0 y1 + 5 y2 + 6 y3 + 8 y4

Formulación del Dual
• Los coeficientes de la función objetivo en el problema dual son los lados derechos de las ecuaciones de restricción del problema primo. w = 180 y1 +200 y2+360 y3+800 y4 • Si el problema primo es un modelo de maximizar, el dual es unmodelo de minimizar. Si por el contrario el problema primo es un modelo de minimizar, el dual es un modelo de maximizar. Minimizar w = 180 y1 +200 y2+360 y3+800 y4
5 6

D.R. © Universidad TecMilenio Lázaro Cárdenas #2610 Col. Del Paseo Residencial Monterrey, N.L., 2005.

1

Universidad Tec Milenio: Maestría HG05007 – Métodos cuantitativos para la toma de decisiones

Formulación del Dual
•Los lados derechos de las restricciones duales son los coeficientes de la función objetivo del problema primo. Restricción dual 1: 3 y1 + 0 y2 + 4 y3 + 8 y4 15000 Restricción dual 2: 0 y1 + 5 y2 + 6 y3 + 8 y4 12000

Formulación del Dual
• Si el problema primo es de maximizar, se asigna a las restricciones duales el mismo sentido de la variable de decisión correspondiente del problema primo. Siel problema primo es de minimizar se asigna a las restricciones duales el sentido opuesto de la variable de decisión correspondiente del problema primo. La restricción dual 1 está relacionada con la variable de decisión x1 del modelo primo y x1 ≥ 0. La restricción dual 2 está relacionada con la variable de decisión x2 del modelo primo y x2 ≥ 0.
7 8

Formulación del Dual
Por tanto tendremos:Restricción dual 1: 3 y1 + 0 y2 + 4 y3 + 8 y4 ≥ 15000 Restricción dual 2: 0 y1 + 5 y2 + 6 y3 + 8 y4 ≥ 12000 • Si el problema primo es de maximización asignar a las variables duales el signo contrario de la restricción correspondiente en el problema primo. Si el problema primo es de minimización se asigna el mismo signo.

Formulación del Dual
La restricción 1 del modelo primo (≤) está relacionadacon la variable dual 1 y1 del modelo dual, por tanto y1 ≥ 0 La restricción 2 del modelo primo (≤) está relacionada con la variable dual 2 y2 del modelo dual, por tanto y2 ≥ 0 La restricción 3 del modelo primo (≤) está relacionada con la variable dual 3 y3 del modelo dual, por tanto y3 ≥ 0 La restricción 4 del modelo primo (≤) está relacionada con la variable dual 4 y4 del modelo dual, por tanto...