Programa dual

Programa dual

Aunque el programa primario ofrece una solución por el método de símplex, solo se nos garantiza que no podremos mejorar la solución. Para probar que es una solución óptima, también debemos resolver su programa dual. Este programa dual, además de garantizar la optimización o no, también permitirá analizar la sensibilidad de las variables al cambio.

Cuando el programa primario tiene más variables que restricciones, entonces no hay solución garantizada (como para un sistema de ecuaciones). En este caso, es preferible pasar por el dual para encontrar una solución.

Construcción del programa dual

El programa dual es una simetría del programa primario: hay una restricción para cada variable del programa primario; y una variable dual para cada restricción del programa principal; los coeficientes de la función objetivo principal son elementos B del dual y viceversa. Cabe señalar que el dual del dual es el primario.

Para las siguientes reglas de transformación particulares, se considera que el primario está bajo el forma canónica :

• Si la variable i del primario es positiva o cero, entonces la restricción i del dual está en su forma canónica
• Si la variable i del primal es un número real, entonces la restricción i del dual es una igualdad (lógica si consideramos la igualdad como una combinación de "menor o igual" y "mayor o igual")
• Si la restricción j del primario está en forma canónica, entonces la variable j del dual es positiva o cero.
• Si la restricción j del primario es una igualdad, entonces la variable j del dual es un número real (lógico si consideramos la igualdad como una combinación de "menor o igual" y "mayor o igual")

Teniendo en cuenta la transformación de un programa lineal en forma canónica, el segundo punto y el cuarto punto normalmente no se aplican durante la transformación en dual para el cálculo del Simplex!

Aquí hay un resumen de la transformación en Dual por la forma canónica.

Dualidad débil y dualidad fuerte

Baja dualidad : para cualquier solución del dual y para cualquier solución del primario, el valor objetivo del dual z = cx * es mayor o igual que el del primario w = por *.

Fuerte dualidad : si el primario tiene una solución óptima x * entonces el dual tiene una solución óptima y * y el valor objetivo del primario es igual al del dual.

Dado que el dual del dual es el primario, el primario tiene una solución óptima si y solo si el dual tiene una solución óptima.

Existe una relación en las soluciones de lo primario y lo dual:

• si un problema tiene soluciones factibles y un dominio acotado para la función objetivo, entonces también lo tiene su dual.
• si un problema tiene soluciones factibles y un dominio ilimitado para la función objetivo, entonces su dual no tiene solución factible.
• si un problema no tiene soluciones factibles, el dual tiene un dominio ilimitado para la función objetivo o no tiene soluciones factibles.

Interpretación del programa dual