Proama Dual Primal

TEORIA DE DUALIDAD Y ANALISIS DE SENSIBILIDAD
Uno de los descubrimientos más importantes durante el desarrollo inicial de la programación lineal fue el concepto de dualidad y sus muchas e importantes ramificaciones. Este descubrimiento revelo que, asociado a todo problema de programación lineal, existe otro problema lineal llamado dual.
Uno de los aspectos más importantes de la teoría de ladualidad es la interpretación y realización del análisis de sensibilidad; el análisis de sensibilidad constituye una parte esencial en casi todos los estudios de programación lineal. Dado que algunos o todos los valores de los parámetros que se emplean en el modelo original son solo estimaciones de las condiciones futuras, es necesario investigar el efecto que se tendría sobre la solución óptima encaso de que prevalecieran otras condiciones.
ESENCIA DE LA TEORÍA DE DUALIAD

El problema dual usa exactamente los mismos parámetros que el problema primal, pero en diferentes lugares.
Problemas primal y dual para el ejemplo de la Wyndor Glass Co.








Enconsecuencia:
1) Los parámetros para una restricción en cualquier problema son los coeficientes de una variable en el otro.
2) Los coeficientes de la función objetivo en un problema son los valores del lado derecho en el otro.
ORIGEN DEL PROBLEMA DUAL
Para ilustrar estas relaciones con el ejemplo de la Wyndor, la ecuación da , que es justo la función objetivo del problema dual mostradoanteriormente. El segundo conjunto de ecuaciones da , y , que son los lados izquierdos de las restricciones funcionales para este problema dual. Así, se restan los lados derechos de estas restricciones tipo , entonces (z₁ - c₁) y (z₂ - c₂) se pueden interpretar como las variables de superávit para estas restricciones funcionales.
Condición de optimalidad:


Después de sustituir la expresiónanterior para , la condición de optimalidad dice que el método simplex se puede interpretar como la búsqueda de los valores de .
Como W es sencillamente el valor de Z, y como el objetivo del problema primal es maximizar Z, una relación neutral seria que W se maximizara también. Sin embargo, esto no es correcto debido a una razón bastante factibles para este nuevo problema son aquellas quesatisfacen la condición de optimalidad para el problema primal. Por o tanto, solo la solución optima para el problema primal corresponde a la solución factible para este nuevo problema. En consecuencia, el valor óptimo de Z en el problema primal es el valor mínimo factible de W en el nuevo problema, de manera que W debe minimizarse.
W óptima no es otra cosa que el valor optimo de Z de manera que losvalores de la función objetivo son iguales para los dos problemas.
Resumen de las relaciones primal – dual
 Propiedad de dualidad débil:
Si x es una solución factible para el problema primal y es una solución factible para el problema dual, entonces
c x ≤ y b.
 Propiedad de dualidad fuerte:
Si x˟ es una solución optima para el problema primal y y˟ es una solución óptima para el problemadual, entonces:
cx˟= y˟b
 Propiedad de soluciones complementarias:
En cada iteración, el método simplex identifica de manera simultánea una solución FEV, x, para el problema primal y una solución complementaria, y, para el problema dual donde
cx =yb
Si x no es optima para el problema primal, entonces y no es para el problema dual.
 Propiedad de soluciones complementarias optimas
Al finalde cada iteración, el método simplex identifica de manera simultanea una solución optima x˟ para el problema primal y una solución optima complementaria y˟ para el problema dual, donde
cx˟=y˟b
Los valores de son los precios sombra para el problema primal.
 Propiedad de simetría:
Para cualquier problema primal y su problema dual, las relaciones entre ellos deben ser simétricas debido a...