Dualidad y Analisis de Sensibilidad

En el caso de cualquier problema primal y su problema dual, las relaciones entre ellos deben ser simétricas debido a que el dual de este problema dual es este problema primal.

Teoria de Dualidad y Analisis de Sensibilidad

Soluciones Complementarias

Soluciones Basicas Complementarias

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.

Metodo CER para Restricciones

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.

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

Determine si cada forma de las restricciones funcionales y de las restricciones sobre las variables es común, extraña o rara.

Formule el problema primal de cualquier forma, maximización o minimización, y el problema dual automáticamente quedará en la forma contraria.

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.

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.

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.

El metodo Primal y el Dual

¿El problema Primal es de maximización?

No

El problema Dual entonces es de maximización

Sí

El problema Dual entonces es de minimización

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.

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 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.

Propiedades

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.

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.

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.

Analisis de Sensibilidad

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.

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.

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.

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.

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.

Revisión del modelo

se hacen los cambios deseados en el modelo que se va a investigar.

Escencia de la Dualidad

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.