Unidad Tres: Dualidad y Análisis de Sensibilidad



Teoría de Dualidad

A un programa lineal llamado primario en las variables X1, X2, X3, …, Xn, se le asocia otro programa lineal con las variables W1, W2, W3, …, Wm, dónde m es el número de restricciones en el programa original. Al nuevo programa lineal se le conoce como su dual.

El programa original llamado primario determina por completo la forma de su dual.

Duales simétricos

El dual de un programa lineal (primario), en la forma matricial (no estándar):

Min X0= CTX
Sujeto a:
                  AX ≥ B
                    X ≥ 0

Es el programa lineal
Max W0= BTW
Sujeto a:
                  ATW ≥ CT
                     W ≥ 0

Los problemas anteriores son simétricos en el sentido de que ambos involucran variables no negativas y restricciones de desigualdad, se conocen como duales simétricos uno del otro.

A las variables W1, W2, W3,…, Wm, a veces se les llama precios sombra.



Soluciones duales

Si existe una solución óptima para el programa primario o para el dual simétrico, entonces existe otro programa también con una solución óptima y en las dos funciones objetivo tienen el mismo valor óptimo. En tales situaciones la solución óptima al programa primario (dual), se encuentra en el último renglón, de la tabla simplex, para el programa dual primario, en aquellas columnas asociadas con las variables de holgura o superfluas. Ya que las soluciones a ambos problemas se obtienen al resolver cualquiera de ellos. Puede resultar ventajoso desde el punto de vista de los cálculos resolver el dual de un programa en vez de resolver el programa mismo.

Teorema

Dado un par de programas duales simétricos tiene soluciones óptimas, entonces la k-ésima restricción de un sistema se conserva como desigualdad, esto es la variable asociada de holgura o superflua es positiva, el k-ésimo componente de la solución óptima de su dual simétrico es cero.

Duales asimétricos

Para los programas primarios en forma estándar, los duales pueden definirse de la siguiente forma:


PRIMARIO

DUAL
Min X0= CTX
Sujeto a:
                      AX = B
                        X ≥ 0


Max W0= BTW
Sujeto a:
                      ATW ≤ CT
                         W ≥ 0

Max X0= CTX
Sujeto a:
                      AX = B
                        X ≥ 0


Min W0= BTW
Sujeto a:
                      ATW ≥ CT
                         W ≥ 0



Ya que dado un programa en forma estándar su dual no se encuentra en la forma estándar, estos duales son asimétricos.