Ensayo 1
Ensayo 1
Ensayo 1
Ingeniería Industrial
Materia:
Alumnos:
Grupo:
82
P Profesora:
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.
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
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.
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