Teoria de Dualidad y Analisis de Sensibilidad
Escencia de la Dualidad
Desarrollo de la programación lineal
El concepto de dualidad en optimización apareció por primera vez en un trabajo publicado en 1963 por John von Neuman.
Descubrimiento del concepto de dualidad y sus importantes ramificaciones
Asociado a todo problema de programación lineal, existe otro problema lineal llamado dual.
Su importancia
Permite resolver problemas de programación lineal de forma más rápida y sencilla.
Es otra vía para resolver un problema de programación lineal.
Facilita profundizar en el contenido económico del problema original (primal).
Puede ser utilizada para resolver el caso en que se debe considerar la introducción de una nueva variable en el primal una vez que ha sido obtenida la solución óptima, sin tener que resolver completamente el problema.
Analisis de Sensibilidad
Revisión del modelo
se hacen los cambios deseados en el modelo que se va a investigar.
Revisión de la tabla símplex final
Se emplea la idea fundamental para determinar los cambios que resultan en la tabla símplex final.
Conversión a la forma apropiada de eliminación de Gauss
Se convierte esta tabla en la forma apropiada para identificar y evaluar la solución básica actual, para lo cual se aplica eliminación de Gauss.
Prueba de factibilidad
Se prueba la factibilidad de esta solución mediante la verificación de que todas las variables básicas de la columna del lado derecho aún tengan valores no negativos.
Prueba de optimalidad
Se verifica si esta solución es óptima, mediante la comprobación de que todos los coeficientes de las variables no básicas del renglón 0 continúen no negativos.
Reoptimización
Si esta solución no pasa una de las pruebas, se puede obtener la nueva solución óptima a partir de la tabla actual como tabla símplex inicial Por el método símplex o el símplex dual.
El metodo Primal y el Dual
Propiedades
Dualidad Debil
Si x es una solución factible para el problema primal y y es una solución factible para el problema dual, entonces
cx ≤ yb.
Dualidad Fuerte
Si x* es una solución óptima para el problema primal y y* es una solución óptima para el problema dual, entonces
cx* ≤ y*b.
Estas dos propiedades implican que cx < yb para soluciones factibles si una o ambas son no óptimas para sus problemas respectivos, mientras que la igualdad se cumple cuando ambas son óptimas.
En cuanto a soluciones
LSi un problema tiene soluciones factibles y una función objetivo acotada (y, por ende, una solución óptima), entonces ocurre lo mismo con el otro problema, de manera que se aplican tanto la propiedad de dualidad débil como la fuerte.
Si uno de los problemas tiene soluciones factibles y una función objetivo no acotada (es decir, no tiene solución óptima), entonces el otro problema no tiene soluciones factibles.
LSi un problema no tiene soluciones factibles, entonces el otro problema no tiene soluciones factibles o bien la función objetivo es no acotada.
En cuanto a variables
El dual tiene la matriz D transpuesta, es decir, si suponemos que D es de orden s x r, entonces Dt es de orden r x s. Además las variables del primal y el dual son diferentes, ya que X será un vector de r-componentes mientras que el vector Y tendrá s-componentes.
Las restricciones del dual cambian su sentido al igual que el criterio de optimización en términos de mínimo o máximo.
A cada restricción del problema primal le corresponde una variable dual y análogamente a cada restricción del dual le corresponde una variable del primal.
Si se halla el dual del problema dual, obtendremos el problema primal.
En cuanto a coeficientes
Los coeficientes de la función objetivo del problema primal son los lados derechos de las restricciones funcionales del problema dual.
Los lados derechos de las restricciones funcionales del problema primal son los coeficientes de la función objetivo del problema dual.
Los coeficientes de una variable de las restricciones funcionales del problema primal son los coeficientes de una restricción funcional del problema dual.
¿El problema Primal es de maximización?
Sí
El problema Dual entonces es de minimización
No
El problema Dual entonces es de maximización
Soluciones Complementarias
Propiedades
Soluciones Complementarias
En cada iteración, el método símplex 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.
Soluciones Complementarias Optimas
Al final de cada iteración, el método símplex identifica de manera simultánea una solución óptima x* para el problema primal y una solución óptima complementaria y* para el problema dual, donde
cx* = y*b.
Soluciones Basicas Complementarias
Propiedad de holgura complementaria: Enuncia que para cada par de variables asociadas, si una de ellas tiene holgura en su restricción de no negatividad, entonces la otra no debe tener holgura.
Metodo CER para Restricciones
Formule el problema primal de cualquier forma, maximización o minimización, y el problema dual automáticamente quedará en la forma contraria.
Determine si cada forma de las restricciones funcionales y de las restricciones sobre las variables es común, extraña o rara.
Por cada restricción sobre una variable individual en el problema dual, use la forma que tiene la misma condición que la restricción funcional en el problema primal que corresponde a esta variable dual
Por cada restricción funcional en el problema dual, use la forma que tiene la misma condición que la restricción sobre la variable individual correspondiente del problema primal.
Cada solución básica del problema primal tiene una solución básica complementaria para el problema dual, donde los valores respectivos de la función objetivo (Z y W ) son iguales.