Teoría de la dualidad

Plus de détails

GESTION DE INVENTARIOS

par Diana Angel

HETEROSISTEMA

par Miguel Angel Beltran Orozco

Bronislaw Malinowsky

par Yolima ramirez

programacion lineal

par adriana urbano

Teoría de la dualidad

Aplicación del análisis de sensibilidad

Introducción una nueva restricción

Luego de obtener una solución, introducir una nueva restricción. esto puede ocurrir si se pasó de alto la restricción en un principio o porque hayan surgido nuevas consideraciones después de formular el modelo.

Suponiendo que una variable xj (con j fija) que está en estudio es una variable básica de la solución optima dentro de la tabla simplex final. los únicos cambios se realizan los coeficientes de esta variable. aquí la tabla simplex debe estar en la forma apropiada de eliminación de gauss.

Introducción de una nueva variable

Para considerar una nueva actividad que la formulación de programación lineal no haya tomado en cuenta, se introduce un nueva variable con los coeficientes apropiados en la función objetivo y en las restricciones del modelo actual.

Cambios en los coeficientes de una variable básica

Análisis de cambios simultáneos en los coeficientes de la función objetivo

Intervalo permitido para un coeficiente de la función objetivo de una variable no básica

Cambios en las bi

Análisis de cambios simultáneos en los lados derechos

Intervalo permisible para un lado derecho

Adaptación a otras formas del primal

Método CER (Común-Extraño-Raro)

Para cada restricción funcional en el problema dual, utilizar la misma condición que la restricción sobre la variable individual correspondiente del problema primal.

Para cada restricción sobre una variable individual en el problema dual, usar la forma que tiene la misma condición que la restricción funcional en el problema primal correspondiente a la variable dual.

Determinar si cada forma de las restricciones funcionales y de las restricciones es c, e o r.

Formular problema primar de cualquier forma, maximización o minimización. el dual quedara automáticamente en forma contraria.

Papel de la teoría de la dualidad en el análisis de sensibilidad

Aplicaciones de la teoría de la dualidad al análisis de sensibilidad

Método simplex dual: se utiliza cuando se desea reoptimizar para identificar la nueva solución optima.

Precios sombra: la solución optima dual proporciona los precios sombra de los recursos respectivos que indican cuanto puede cambiar z si se hace cambios en las cantidades de recurso.

Introducción de una nueva variable: la inclusión de otra variable equivale a introducir una nueva variable al modelo. El único cambio que resulta en el problema cual es la introducción de una nueva restricción.

Cambios en los coeficientes de una variable no básica: el cambio en sus coeficientes no puede afectar la factibilidad de la solución.

Esencia del análisis de sensibilidad

Procedimiento para análisis de sensibilidad

Reoptimización

Probar optimalidad: verificar si la solución es óptima (factible)

Probar factibilidad: se verifican todas las variables básicas de la columna del lado derecho

Conversión a la forma apropiada de eliminación de gauss

Revisión de la tabla simplex final

Revisión del modelo: hacer cambio deseados

Análisis de sensibilidad

Utilizado para problemas grandes, en vez de realizar el simplex nuevamente

Objetivo fundamental: identificar los parámetros sensibles

Parámetros no clasificados como sensibles: determinar el intervalo de valores del parámetro para el que la solución óptima no cambia.

Parámetros sensibles (no pueden cambiar sin que cambie la solución óptima)

Relaciones Primal -Dual

Propiedad de las soluciones básicas óptimas complementarias

Soluciones se clasifican según cumplan con que todas las variables de la solución aumentada son no negativas (condición de factibilidad) o cuando todos los coeficientes del renglón 0 son no negativos (condición de optimalidad).

Para que se de esta propiedad, la solución dual debe ser factible para el problema dual, ya que la condición de optimalidad para el problema primal requiere que todas las variables duales sean no negativas.

Dado el renglón 0 de la tabla simplex de la solución primal óptima, se puede encontrar la solución dual óptima complementaria.

Propiedad de holgura complementaria

La relación entre las variables de la solución básica primal y dual complementaria: es simétrica, es decir, las dos soluciones básicas son complementarias entre sí.

Propiedad de las soluciones básicas 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.

Soluciones básicas complementarias

Cada variable del problema primal tiene una variable asociada en el dual.

La clave de correspondencia directa entre las soluciones básicas es el renglón de la tabla simplex de la solución básica primal.

Interpretación económica de la dualidad

Interpretación de problemas duales proporcionan una interpretación económica de lo que el método simplex hace en el problema dual.

Llegar a solución BF que satisfaga los requisitos sobre el uso provechoso de los recursos (estos comprenden la condición de optimalidad del algoritmo)

Directamente basada en la interpretación más común del problema primal

Esencia de la teoría de la dualidad

Solución óptima problema primal = solución factible nuevo problema

Se requiere que el valor mínimo factible de W en el nuevo problema sea minimizado

Correspondencia directa elementos problemas duales y primales

Función objetivo de un problema = lados derechos del otro problema

Restricción I de un problema = variable I del otro problema

Iguales parámetros problema dual y primal

Coeficientes de una variable de las restricciones funcionales del problema primal = coeficientes de una restricción funcional del problema dual.

Lados derechos de las restricciones funcionales del problema dual primal = coeficientes de la función objetivo del problema dual.

Coeficientes de función objetivo del problema primal = lados derechos de las restricciones funcionales del problema dual

Problema dual = solución problema primal (satisfacer prueba de optimalidad)