dualidad

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 dualde 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, seconocen 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 programaprimario (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 dela 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 ≥ 0Ya que dado un programa en forma estándar su dual no se encuentra en la forma estándar, estos duales son asimétricos.






Unidad Tres: Dualidad y Análisis de Sensibilidad (Análisis de sensibilidad)










Análisis de Sensibilidad

El análisis de sensibilidad es un método para investigar el efecto que tiene los cambios en los diferentes parámetros sobre la soluciónóptima de un problema de programación lineal. Se pueden cambiar los coeficientes de la función objetivo, los valores del segundo término de las ecuaciones de restricción. Es frecuente que los coeficientes de la función objetivo o los valores del segundo término en las ecuaciones de restricción sean estimadas, y por ello, la sensibilidad de la solución ante cambios en estos parámetros es de especialvalor. El impacto que tienen los cambios en los coeficientes del cuerpo de las restricciones es de menor importancia porque se obtienen de la tecnología del problema, es más probable que estos coeficientes sean valores reales y no estimaciones, por estas razones, se consideran solo los cambios en los coeficientes de la función objetivo y en los valores del segundo término.

Ejemplo:

El gerentede Agroindustria S.A. necesita planear la combinación de fertilizantes para el siguiente mes. Los dos fertilizantes de la agro-fábrica son las mezclas denominadas: 5-5-10 y la 5-10-5.

El 5-5-10 está elaborado con 5% de nitrato, 5% de fosfato y 10% de potasio, el 80% restante es barro. El 5-10-5 está elaborado con 5% de nitrato, 10% de fosfato y 5% de potasio. Este mes la disponibilidad de...