1) El documento habla sobre el análisis de dualidad y sensibilidad en la optimización de procesos. 2) Explica cómo construir un problema dual a partir de uno primal y las relaciones entre las variables y restricciones de ambos problemas. 3) También describe técnicas como el método simplex dual y el análisis de sensibilidad para estudiar cómo cambia la solución óptima cuando varían los parámetros del modelo.
0 calificaciones0% encontró este documento útil (0 votos)
67 vistas8 páginas
1) El documento habla sobre el análisis de dualidad y sensibilidad en la optimización de procesos. 2) Explica cómo construir un problema dual a partir de uno primal y las relaciones entre las variables y restricciones de ambos problemas. 3) También describe técnicas como el método simplex dual y el análisis de sensibilidad para estudiar cómo cambia la solución óptima cuando varían los parámetros del modelo.
1) El documento habla sobre el análisis de dualidad y sensibilidad en la optimización de procesos. 2) Explica cómo construir un problema dual a partir de uno primal y las relaciones entre las variables y restricciones de ambos problemas. 3) También describe técnicas como el método simplex dual y el análisis de sensibilidad para estudiar cómo cambia la solución óptima cuando varían los parámetros del modelo.
1) El documento habla sobre el análisis de dualidad y sensibilidad en la optimización de procesos. 2) Explica cómo construir un problema dual a partir de uno primal y las relaciones entre las variables y restricciones de ambos problemas. 3) También describe técnicas como el método simplex dual y el análisis de sensibilidad para estudiar cómo cambia la solución óptima cuando varían los parámetros del modelo.
Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
Descargar como docx, pdf o txt
Está en la página 1/ 8
UNIVERSIDAD POLITÉCNICA DE TULANCINGO
Ingeniería Industrial
Materia:
U Optimización y Mejora de procesos
Alumnos:
Jessica Martinez Mendoza
Grupo:
82
P Profesora:
Mtra. Reyna Adriana Marroquín Gayoso
Fecha:
28 de Marzo de 2020
T DUALIDAD Y ANALISIS DE SENSIBILIDAD La solución óptima de una programación lineal se basa en una toma instantánea de las condiciones que prevalecen en el momento de formular y resolver el modelo. En el mundo real los ambientes de decisión rara la vez permanecen estáticos y es esencial determinar cómo cambia la solución óptima, cuando cambian los parámetros del modelo. Esto es lo que hace el análisis de sensibilidad. Proporciona técnicas de computo eficientes para estudiar el comportamiento dinámico de la solución óptima, que resulta al hacer cambios en los parámetros del modelo. Todo problema de optimización (primal), tiene un problema asociado (dual) con numerosas propiedades que los relacionan y nos permiten hacer un mejor análisis de los problemas. A continuación, se describen los resultados que se ocuparan en la resolución de los problemas.
Construcción de un problema dual
Bastante en general, para encontrar el dual de un problema lineal: 1. Si es problema de minimización el dual será de maximización y viceversa. 2. En el dual habrá tantas variables como restricciones 2 en el primal. 3. En el dual habrá tantas restricciones como variables en el primal. 4. Los coeficientes de la función objetivo del dual vendrán dados por los coeficientes del lado derecho de las restricciones del primal. 5. Los coeficientes del lado derecho del dual vendrán dados por los coeficientes de la función objetivo del primal. 6. Los coeficientes que acompañarán a las variables en una restricción del dual corresponderán a aquellos coeficientes que acompañan a la variable primal correspondiente a la restricción dual 3. 7. Para saber si las restricciones duales son de ≤, = o ≥, se recurre a la tabla de relaciones primal-dual. 8. Para saber si las variables duales son ≤ 0, = 0 o ≥ 0, se recurre a tabla de relaciones primal dual. Tabla Tucker Maximización Minimización ≤ ≥ Restricciones ≥ ≤ = >< ≥ ≥ Variables ≤ ≤ >< =
Relación entre primal y Dual
Estas relaciones nos permiten pasar de un problema de primal a su dual en forma bastante algorítmica, tanto para problemas de minimización como de maximización. Problema de minimización Problema de maximización Restricciones Variables ≥ ≥0 = Irrestricta ≤ ≤0 Variables Restricciones ≥0 ≤ Irrestricta = ≤0 ≥
Teoremas de dualidad Teorema de la coincidencia. El máximo (o mínimo) de la función objetivo del problema primal coincide con el mínimo (o máximo) de la función objetivo del problema dual. Teorema de la correspondencia. Los valores de las variables duales en el óptimo del problema dual coinciden con los rendimientos marginales de las variables de holgura en el óptimo del problema primal. A los valores de las variables del problema dual se les llama precio de referencia, precio teórico o precio sombra de los factores productivos. Consideremos el siguiente par primal-dual: (P) min z = c * x (D) max w=y* s.a A * x >= b s.a At * y <= c xi >= 0 yi <= 0 Teorema Débil de Dualidad Si ¯x e ¯y son factibles para (P) y (D) respectivamente, entonces z(¯x) ≥ w(¯y). Teorema Fundamental de Dualidad Dados un par de problemas primal-dual, si uno de ellos admite solución óptima, entonces el otro también la admite y los respectivos valores óptimos son iguales. Dados un par de problemas primal-dual, si uno de ellos admite solución óptima, entonces el otro también la admite y los respectivos valores óptimos son iguales. Teorema de existencia. La condición necesaria y suficiente para que un problema de programación lineal tenga solución es que, tanto el conjunto de oportunidades del primal (S) como en conjunto de oportunidades del dual (S’) no sean vacíos, es decir, que ambos problemas sean factibles. ∃ ( x* , λ* ) ←→ S ≠ ∅ ∧ S’ ≠ ∅ Teorema del Holgura complementaria. La condición necesaria y suficiente para que (x*, λ*) sean soluciones óptimas del programa primal y dual, es que satisfagan las condiciones de holgura complementaria: ( c - λ* A ) x* = 0 λ* ( b - A x* ) = 0
Condiciones de holgura complementaria
Nos permite encontrar la solución óptima del Problema Dual cuando conocemos la solución óptima del Problema Primal (y viceversa) a través de la resolución de un sistema de ecuaciones conformado por las variables de decisión (primales y duales) y las restricciones (del modelo primal y dual).
Interpretación económica de la dualidad
La solución óptima de un modelo determina la asignación óptima de recursos limitados. El valor óptimo de las variables duales indica si es o no conveniente cambiar el nivel de recursos en el modelo.
Precios sombra Los valores de las variables duales en el óptimo tienen una interpretación económica interesante en problemas de programación lineal: Corresponde a las tasas marginales de variación del valor de la función objetivo ante variaciones unitarias del lado derecho de una restricción. Por este motivo se le llama precio sombra al vector de variables duales en el óptimo.
Método simplex dual
Es una estrategia algorítmica eficiente cuando luego de llevar un modelo de programación lineal a su forma estándar, la aplicación del método simplex no es inmediata o más bien compleja. El algoritmo para resolver un modelo es: Paso 1: Hallar una solución básica inicial infactible e inmejorable Escribir el tablero inicial tomando a las variables de holgura y de exceso como variables básicas iniciales
Paso 2: Prueba de factibilidad
Si todas las variables básicas son no negativas, la actual solución es la óptima. Si hay al menos una variable básica negativa, seleccionar como variable de salida, (llamémosla (XB)s ), a aquella con el valor más negativo. Los empates se pueden romper arbitrariamente. Paso 3: Prueba de inmejorabilidad Sí en el renglón de la variable básica de salida (XB)s todos los coeficientes de reemplazo con las variables no básicas son no negativos, la solución del modelo es óptima ¡limitada. Se termina el proceso. Si en el renglón de la variable básica de salida (XB)s, hay al menos un coeficiente de intercambio negativo, se efectúan los cocientes entre el efecto neto de cada variable no básicas y su correspondiente coeficiente de intercambio negativo. Es decir, siendo (XB)s la variable de salida se calculan todos los cocientes.
Se toma como variable de entrada (Llamémosla Xe) a aquella que
corresponda al mínimo de los cocientes del anterior conjunto Si la variable de entrada es Xe el elemento pivote será el elemento (Se)s El empate se puede romper arbitrariamente. Aplicar la operación de pivoteo para generar la nueva tabla, en la cual aparezca Xe como variable básica en lugar de la variable de salida (XB)s Repetir el algoritmo a partir del paso 2.
Método de la restricción artificial
A cada problema de optimización lineal le corresponde otro que se denomina problema dual. En forma canónica. La correspondencia es biunívoca. El dual del dual es el primal
Efecto de la restricción artificial
Este completa el algoritmo simplex dual cuando es necesario, cuando la variable de holgura de la restricción artificial no está en la base optima puede ser por dos razones: M no es suficientemente grande o la solución es no acotada.
Análisis de sensibilidad En este ámbito, podemos distinguir 2 tipos de análisis: Análisis de sensibilidad: Consiste en determinar cuál es el rango de variación de los parámetros del problema de modo que la base ´optima encontrada siga siendo óptima. Análisis post optimal: Consiste en determinar cómo varía la base ´optima si cambia alguno de los parámetros del problema. En la presente sesión nos concentraremos en análisis de sensibilidad dejando el análisis post optimal para un poco más adelante. Consideremos la forma estándar siguiente: (P) min z = c*x s.a A*x = b x >= 0 Sea B la base óptima. Nos interesa estudiar el rango de variación de los parámetros c y b de modo que B siga siendo ´optima 5. Variación en el parámetro b. Buscamos el rango en el que puede tomar valores b de modo que la base B siga siendo ´optima. Para ello debemos verificar: 1. Factibilidad: xB = B−1b ≥ 0 2. Optimalidad: ¯ cR = cR −cBB−1R ≥ 0 Como en la ecuación 2. no hay dependencia explicita de b, no impone condiciones y por tanto solo debemos verificar 1.
Variaciones en el parámetro c. Buscamos el rango en el que puede tomar valores c de modo que la base B siga siendo ´optima. Para ello debemos verificar: 1. Factibilidad: xB = B−1b ≥ 0 2. Optimalidad: ¯ cR = cR −cBB−1R ≥ 0
Análisis de dualidad en la programación lineal
Problema primal Problema dual
Max (o min) Min(o max)
Coeficientes de la función objetivo Términos independientes de las
restricciones
Términos independientes de las Coeficientes de la función objetivo
restricciones
Matriz ( n * m) de los coeficientes de Matriz ( m * n) transpuesta de los
las restricciones coeficientes de las restricciones
Numero de variables Numero de restricciones
Numero de restricciones Numero de variables
Sentido de la inecuación Sentido de la inecuación
≤ (≥) ≥ (≤) y variables negativas Ecuaciones (=) Variables sin restricción de signos
Todo problema de programación lineal tiene, asociado a él, un problema de
programación lineal dual. Existen ciertas relaciones útiles entre el problema original (primal) y su problema dual que refuerzan la habilidad para analizar el problema primal. Por ejemplo, la interpretación económica del problema dual proporciona los precios sombra que miden el valor marginal de los recursos en el problema primal, al igual que permiten dar una interpretación del método símplex. Puesto que el método símplex se puede aplicar directamente a cualquiera de los dos problemas para obtener la solución de ambos al mismo tiempo, es posible ahorrar una gran cantidad de esfuerzo computacional si se maneja directamente el problema dual. La teoría de dualidad, que incluye el método símplex dual para trabajar con soluciones básicas superóptimas, juega un papel de gran importancia en el análisis de sensibilidad.
