Asociado a cada problema de Programación Lineal existe un problema de optimización llamado “Problema DUAL”

Dualidad

Asociado a cada problema de Programación Lineal existe un problema de optimización llamado “Problema DUAL”, mientras que el problema original recibe el nombre de “Problema PRIMAL”.

La solución DUAL presenta la siguiente importancia:

1. Con frecuencia es mas fácil resolver y encontrar soluciones óptimas de un PL encontrando primero la solución de su DUAL asociado, pues Si el Primal tiene mas restricciones que variables, es mas simple resolver el DUAL, ya que se necesitan menos iteraciones.

2. El problema DUAL entrega información sobre análisis marginales que es necesario tener en cuenta al buscar la solución óptima de un PL; por lo tanto, la solución DUAL corresponde a las valoraciones marginales de los recursos asociados a estas variables, que usualmente reciben el nombre de “Precios Sombra”.

Si un recurso no está siendo utilizado en su totalidad, es decir, no es escaso, dicho recurso estará asociado a un costo “Cero”, ya que, el hecho de llegar a contar con un unidad adicional NO generará un incremento del beneficio.

Por otra parte, un recurso escaso al que se adiciona un unidad extra generará un aumento en el valor de la función objetivo.

S = 0

S > 0

El recurso es escaso

El recurso es abundante

El DUAL se obtiene de acuerdo a las siguientes reglas:

Primero: Para toda restricción PRIMAL existe una variable DUAL.

Segundo: Para toda variable PRIMAL existe una restricción DUAL.

Tercero: Los coeficientes de las restricciones de una variable PRIMAL forman los coeficientes del primer miembro de la restricción DUAL correspondiente, y el coeficiente de la misma variable en la función objetivo se convierte en el segundo miembro de la restricción DUAL n(Lado Derecho)

Cuarto: Si el PRIMAL busca maximizar y el DUAL busca minimizar (y viceversa).

Quinto: El problema de Maximización tiene restricciones del tipo “Menor e igual qué…” y el problema de minimización tiene restricciones del tipo “Mayor e igual qué…”

Sexto: Las variables tanto del PRIMAL como del DUAL son no-negativas.

Séptimo: El DUAL se obtiene de acuerdo a la siguiente tabla:

PRIMAL DUAL

Ejemplo:

PRIMAL DUAL

Max Z = 4X1 + 3X2

Sujeto a: X1 + 2X2 ≤ 10

3X1 + X2 ≤ 10

X1 + ≤ 3

X1 ; X2 ≥ 0

Min D = 10W1 + 10W2 + 3W3

Sujeto a: W1 + 3W2 + W3 ≥ 4

2W1 + W2 ≥ 3

W1 ; W2 ; W3 ≥ 0

FORMA STANDARD

Min D = 10W1 + 10W2 + 3W3 + MA1 + MA2

Sujeto a: W1 + 3W2 + W3 - W4 + A1 = 4

2W1 + W2 - W5 + A2 = 3

W1 ; W2 ; W3 ; W4 ; W5 ; A1 ; A2 ≥ 0

A1 = 4 - W1 - 3W2 - W3 + W4

A2 = 3 - 2W1 - W2 + W5

Min

Min

Min

max

FORMA CANÓNICA

(3M - 10)W1 + (4M - 10)W2 + (M - 3)W3 - MW4 - MW5 + D = 7M

W1 + 3W2 + W3 - W4 + A1 = 4

2W1 + W2 - W5 + A2 = 3

Base LD W1 W2 W3 W4 W5 A1 A2

D 7M 3M - 10 4M - 10 M - 3 -M -M 0 0

A1 4 1 3 1 -1 0 1 0

A2 3 2 1 0 0 -1 0 1

D (5M+40) / 3 (5M-20) / 3 0 (1-M) / 3 (M-10) / 3 -M (10-4M) / 3 0

W2 4/3 1/3 1 1/3 - 1/3 0 1/3 0

A2 5/3 5/3 0 - 1/3 1/3 -1 - 1/3 1

D 20 0 0 -1 -2 -4 -M + 2 -M + 4

W2 1 0 1 2/5 - 2/5 1/5 2/5 - 1/5

W1 1 1 0 - 1/5 1/5 - 3/5 - 1/5 3/5

Solución Óptima

W1 = 1

W2 = 1

W3 = 0

D = 20

Precio Sombra de la Restricción #1

Precio Sombra de la Restricción #2

Precio Sombra de la Restricción #3

Interpretación de la Solución:

Si aumenta la disponibilidad de la 1ª Restricción en una unidad, es decir, de 10 a 11, el valor de la función objetivo aumentará en W1=1. Lo mismo ocurre con la 2ª restricción (W2=1); pero si se aumenta la disponibilidad de la 3ª restricción no cambiará el valor de la función objetivo (W3=0).

Solución PRIMAL v/s Solución DUAL

Solución PRIMAL

BASE LD X1 X2 S1 S2 S3

-Z -20 0 0 -1 -1 0

S3 1 0 0 1/5 -2/5 1

X2 4 0 1 3/5 -1/5 0

X1 2 1 0 -1/5 2/5 0

...