DUALIDAD Dualidad resulta de buscar relaciones que permitan obtener información adicional de un problema de optimización general. Esto en programación lineal nos conduce a relaciones primal-dual. Esta relación consiste en que todo problema de optimización primal tiene un problema asociado dual.
Teoría de la dualidad y análisis de la sensibilidad
RELACIÓN (PRIMAL –DUAL) La relación entre el problema Dual y su asociado, es decir el problema original llamado primal, presenta varias utilidades: o Aporta elementos que aumentan sustancialmente la comprensión de la PL. o El análisis de la dualidad es una herramienta útil en la solución de problemas de PL. o El problema Dual tiene interpretaciones e informaciones importantes.
Propiedad de simetría: 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
Propiedad de soluciones complementarias óptimas: Al fi nal 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 (que se encuentra en el renglón 0 como los coeficientes de las variables de holgura)
Subtema
Propiedad de 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 (que se encuentra en el renglón 0, como los coeficientes de las variables de holgura)
Propiedad de dualidad fuerte: Si x* es una solución óptima para el problema primal y
y* es una solución óptima para el problema dual.
Propiedad de dualidad débil: Si x es una solución factible para el problema primal y y es una solución factible para el problema dual.
Topic principal
ADAPTACIÓN A OTRAS FORMAS DEL PRIMAl
El método CER para determinar la forma de las restricciones en el dual
4. 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
3. 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
2. Determine si cada forma de las restricciones funcionales y de las restricciones sobre las variables es común, extraña o rara. La condición de las restricciones funcionales dependen de que el problema sea un problema de maximización (use la segunda columna) o un problema de minimización (use la tercera columna).
1. Formule el problema primal de cualquier forma, maximización o minimización, y el problema
dual automáticamente quedará en la forma contraria.
Soluciones básicas complementarias
Propiedad de holgura complementaria: Dada la asociación entre variables que se proporciona en las variables de la solución básica primal y de la solución básica dual complementaria satisfacen las relaciones de holgura complementaria
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.
ANÁLISIS DE SENSIBILIDAD
Consiste en determinar cual es el rango de variación de los parámetros del problema de modo que la base optima encontrada siga siendo optima. Buscar el intervalo en que estos parámetros son permisibles en su variación sin que se afecte la solución optima del problema.
PROCEDIMIENTO PARA EL ANÁLISIS DE SENSIBILIDAD
Reoptimización
Prueba de optimalidad
Prueba de factibilidad
Conversión a la forma apropiada
Revisión de la tabla simplex final
Revisión del modelo
(CAMBIOS) ANÁLISIS DE SENSIBILIDAD
Precio Sombra. Cambio en el valor de la función objetivo por aumento unitario en el valor del lado derecho de una restricción.
Intervalo de factibilidad. Es el intervalo de variabilidad de un lado derecho de una restricción.
Intervalo de optimalidad: es el intervalo de variabilidad de un coeficiente de la función objetivo.
Es importante porque nos permite investigar el efecto que tendría la solución optima proporcionada por el método simplex en el hecho de que los parámetros (datos de entrada) tomaran otros valores posibles
El objetivo fundamental del análisis de sensibilidad es identificar los parámetros sensibles. Por ejemplo los parámetros cuyos valores no pueden cambiar sin que cambie la solución optima.
PAPEL DE LA TEORÍA DE LA DUALIDAD EN EL ANÁLISIS DE SENSIBILIDAD
Como se describe en ésta y las dos secciones siguientes, el análisis de sensibilidad consiste, en esencia, en la investigación del efecto que tiene sobre la solución óptima el hecho de hacer cambios en los valores de los parámetros del modelo aij, bi y cj. Sin embargo, al cambiar los valores de los parámetros en el problema primal se cambian también los valores correspondientes en el
problema dual. Por tanto, se puede elegir qué problema se va a usar para investigar cada cambio.
Gracias a las relaciones primal-dual que hemos visto (en especial la propiedad de soluciones básicas complementarias), es fácil ir de un problema a otro según se desee. En algunos casos es más conveniente analizar el problema dual en forma directa con objeto de determinar el efecto complementario sobre el problema primal. Se comenzará por considerar
dos de estos casos.
Introducción de una nueva variable
Cambios en los coefi cientes de una variable no básica
Son aplicaciones que se la hacen al método simplex con el objetivo de garantizar la optimización de un problema y a su vez para un mejor manejo del mismo método
