TEORÍA DE LA DUABILIDAD

LA TEORÍA DE LA DUALIDAD

El método simplex además de resolver un problema de PL llegando a una solución óptima nos ofrece más y mejores elementos para la toma de decisiones.

La dualidad y el análisis de sensibilidad son potencialidades de éste método. El concepto de dualidad indica que para cada problema de PL hay una asociación y una relación muy importante con otro problema de programación lineal, llamado precisamente dual.

La relación entre el problema dual y su asociado, es decir el problema original llamado primal, presenta varias utilidades:

1. Aporta elementos que aumentan sustancialmente la compresión de la PL.

2. El análisis de dualidad es una herramienta útil en la solución de problemas de PL, por ejemplo: más restricciones que variables.

3. El problema dual tiene interpretaciones e informaciones importantes que muestran que los análisis marginales están siempre involucrados implícitamente al buscar la solución óptima a un problema de PL.

¿Cómo convertir un problema primal a dual?

Un problema dual se formula de un problema primal de la siguiente forma:

• Si el primal es un problema de maximización su dual será un problema de minimización y viceversa.

• Los coeficientes de la función objetivo del problema primal se convierten en los coeficientes del vector de disponibilidad en el problema dual.

• Los coeficientes del vector de disponibilidad del problema original se convierten en los coeficientes de la función objetivo (vector de costo o precio) en el problema dual.

• Los coeficientes de las restricciones en el problema primal, será la matriz de los coeficientes tecnológicos en el dual.

• Los signos de desigualdad del problema dual son contrarios a los del primal.

• Cada restricción en un problema corresponde a una variable en el otro problema. Si el primal tiene m restricciones y n variables, el dual 4 tendrá n restricciones y m variables. Así, las variables Xn del primal se convierte en nuevas variables Ym en el dual.

Dualidad:

MAX Z= 3X1 + 4X2 – 2X3

S. a: 4X1 – 12X2 + 3X3 < 12

–2X1 + 3X2 + X3 < 6

–5X1 + X2 – 6X3 < -40

3X1 – 4X2 – 2X3 < 10

Variables duales

Y1

Y2

Y3

Y4

Min Z´ = 12Y1 + 6Y2 – 40Y3 + 10Y4

S. a: X1 > 0, X2> 0, X3 >0 no restringida en signo

4Y1 – 2Y2 – 5Y3 + 3Y4 >= 3

–12Y1 + 3Y2 + Y3 – 4Y4 >= 4

3Y1 + Y2 – 6Y3 – 2Y4 >= -2

Y1 > 0, Y2 > 0, Y3 > 0, Y4 >0 no restringida en signo

EJEMPLOS:

SI EL PROBLEMA PRIMAL ES:

MAX Z= 45X1 + 17X2 + 55X3

Sujeto a:

X1 + X2 + X3 ≤ 200

9X1 + 8X2 + 10X3 ≤ 5000

10X1+ 7X2 + 21 X3 ≤ 4000

Xj ≥ 0

EL PROBLEMA DUAL SERA:

MAX Z= 45X1 + 17X2 + 55X3

Sujeto a:

X1 + X2 + X3 ≤ 200

9X1 + 8X2 + 10X3 ≤ 5000

10X1+ 7X2 + 21 X3 ≤ 4000

Xj ≥ 0

MIN Z= 200Y1 + 5000Y2 + 4000Y3

Sujeto

...