Teoria de la dualidad y analisis de la sensibilidad

更多类似内容

Gráficos de Control - Paola Santamaría

由Paola Andrea Santamaria Vallejo

Para qué el arte musical en la infancia.

由Luisa Torres

Mapa mental sobre Analisis de sensibilidad y Dualidad

由Carlos Perez

CARTILLA N°30. Ser competente en tecnología: ¡Una necesidad para el desarrollo!

由daniela paola moyano albarracin

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