asdasd

Pontificia Universidad Católica
Escuela de Ingeniería
Departamento de Ingeniería Industrial y de Sistemas

Clase 22 • An´lisis de Sensibilidad de los
a
Resultados
ICS 1102 • Optimizaci´n
o
Profesor : Claudio Seebach
20 de octubre de 2006

Apuntes de Clases • Optimizaci´n • Claudio Seebach
o

Programaci´n Lineal • 105
o

An´lisis de Sensibilidad de los Resultados
a
• Elsupuesto fundamental de los modelos de LP es que uno conoce en
forma exacta los distintos par´metros del problema
a
• En general, al modelar no se conocen los valores que pueden adoptar
los par´metros
a
• Muchas veces los parametros no son determin´
´
ısticos, sino que estoc´sticos
a
• Dado esto, es importante poder saber cuan robustas son nuestras soluciones frente a:
– Variaciones en loscostos ci
– Variaciones en los niveles de los recursos bj

Apuntes de Clases • Optimizaci´n • Claudio Seebach
o

Programaci´n Lineal • 106
o

Sensibilidad a variaciones en los costos
• ¿como var´ la soluci´n ´ptima de un problema de LP si var´ los
ıa
o o
ıan
costos de la funci´n objetivo ?
o
1. Modificar la funci´n objetivo no cambia el dominio del problema.
o
2. Una funci´nobjetivo diferente s´lo puede modificar el v´rtice ´ptimo.
o
o
e
o
• Identifiquemos el rango de las perturbaciones en uno de los coeficientes
de la funci´n objetivo de modo de no alterar la soluci´n ´ptima alcano
o o
zada:
• El vector de costos de la funci´n objetivo se puede dividir entre:
o
cB xB + cD xD
– cB : Costos asociados a las variables b´sicas
a
– cD : Costos asociados a lasvariables no b´sicas
a
• A medida que la base cambia en b´squeda de una base ´ptima, los
u
o
costos reducidos rD tambi´n cambian.
e

Apuntes de Clases • Optimizaci´n • Claudio Seebach
o

Programaci´n Lineal • 107
o

Variaciones de los costos de variables No B´sicas
a
• Para poder mantener la optimalidad de la soluci´n ´ptima, los costos
o o
reducidos deben permanecer positivos o nulos.• Es decir:
• Por lo tanto:

rD = cD − z ≥ 0 donde z = cB B−1D.
rk = ck − zk ≥ 0, ∀k no b´sico.
a

• Si el costo cj asociado a la variable no b´sica xj var´ en ∆cj para
a
ıa
que esta variable siga siendo no b´sica debe cumplirse que su respectivo
a
costo reducido siga siendo no negativo:
cj + ∆cj − zj ≥ 0 → rj + ∆cj ≥ 0
• Por lo tanto, el rango de esta variaci´n ∆cj es:
o
−rj ≤ ∆cj ≤∞

Apuntes de Clases • Optimizaci´n • Claudio Seebach
o

Programaci´n Lineal • 108
o

Variaciones de los costos de Variables B´sicas
a
• El an´lisis respecto a variaciones de los costos asociados a variables
a
b´sicas es m´s complejo que en las no b´sicas:
a
a
a
– Una perturbaci´n en alg´n elemento cj de cB , altera todos los como
u
ponentes del vector z = cB B−1D.
• Si anteesta perturbaci´n los costos reducidos no b´sicos siguen siendo
o
a
no negativos la base ´ptima permanece inalterada.
o
• Los costos reducidos b´sicos seguir´n siendo nulos por construcci´n !
a
a
o

• Basta que uno de los costos reducidos no b´sicos se torne negativo para
a
que la base (y por tanto la soluci´n) ´ptima cambie.
o o
• Si definimos:

ciαik

zk =
i∈B

donde αik es elproducto de la fila i de la matriz B−1, la inversa de la
base, con la columna k de la matriz D, es decir:
αik = B−1 iDcolumna k
fila
Apuntes de Clases • Optimizaci´n • Claudio Seebach
o

Programaci´n Lineal • 109
o

Variaciones de los costos de Variables B´sicas
a
ˆ
• Si modificamos el costo cj en ∆cj , los costos reducidos rk de todas la
variables no b´sicas ser´n:
a
a
ˆ
rk = ck −zk
= (ck −

i∈B

ciαik ) − ∆cj αjk

= rk − ∆cj αjk ≥ 0, ∀k ∈ D (i.e. no b´sico)
a
• En la medida que rk ≥ ∆cj αjk para todos los costos reducidos, la base
o
´ptima no cambia.
• Dado que los αjk pueden ser positivos, negativos o nulos, deber´ cumplirse
a
que:
rk
Si αjk > 0 ⇒ ∆cj ≤
αjk
rk
Si αjk < 0 ⇒ ∆cj ≥
αjk
Si αjk = 0 ⇒ ∆cj puede tomar cualquier valor
Apuntes de Clases...