Aula 09

Prévia do material em texto

1
Análise de sensibilidade
Prof.: Eduardo Uchoa
http://www.logis.uff.br/~uchoa/POI
2
Análise de Sensibilidade
Uma vez que já se tenha resolvido um PL, 
existem técnicas para avaliar como 
“pequenas alterações” nesse PL podem 
alterar a solução ótima, sem precisar resolver 
o novo PL do zero. Por exemplo:
� Alterações no lado direito das restrições
� Alterações nos custos das variáveis
� Adição de novas variáveis ao PL
3
Análise de Sensibilidade
Quando se resolve um PL, além da solução primal ótima 
x*, também se obtém a solução do dual ótima y*.
Essas duas soluções geram outros dados que podem 
ser úteis:
� A folga da restrição i:
� O custo reduzido da variável j:
O custo reduzido é a folga do dual.
* *
1
i j
n
i ij
j
s b a x
=
= −∑
*
*
1
i
m
j j ij
i
c c a y
=
= −∑
4
Análise de sensibilidade
Tela de um resolvedor
5
Análise de sensibilidade
Tela de um resolvedor
Uma restrição de igualdade
sempre tem folga =0. Sua
variável dual não tem limitação
de sinal.
6
Análise de sensibilidade
Tela de um resolvedor
Uma restrição de ≤ sempre
tem folga ≥ 0. 
Uma restrição de ≥ sempre 
tem folga ≤ 0 (folga negativa
↔ excesso positivo).
7
Análise de sensibilidade
Tela de um resolvedor
Uma desigualdade no formato
canônico tem variável dual ≥ 0.
Uma desigualdade contrária ao
formato canônico tem variável
dual ≤ 0.
8
Análise de sensibilidade
Tela de um resolvedor
O teorema das folgas
complementares é sempre
respeitado.
9
Alterando o lado direito das 
restrições
10
Propriedades das variáveis duais
� Teorema – Se um PL possui solução ótima 
não-degenerada x* com valor z* e solução 
ótima dual y*, então existe um ε>0 tal que 
para todo vetor T=(t1,t2,...,tm), com |ti|≤ε, a 
solução ótima do novo PL em que T é
somado ao vetor de lados direitos b tem 
valor:
* *
1
m
i i
i
z y t
=
+∑
11
Interpretação do teorema
As variáveis duais indicam o que acontece com 
a função objetivo quando se altera “pouco” o 
lado direito de uma ou mais restrições. 
As variáveis duais são o “gradiente” da função 
objetivo em relação ao lado direito das 
restrições.
12
Interpretação do teorema
A partir de certo ponto, o aumento/diminuição 
do lado direito de uma restrição deixa de 
influenciar o valor da solução ótima.
13
xmad
xal
a
6 12
6
12
4
42 108 1614
2
10
8
14 Max z = 4,0 xmad + 6,0 xal
S. a
1,5 xmad + 4,0 xal ≤ 24 (ycorte)
3,0 xmad + 1,5 xal ≤ 21 (ymontagem)
1,0 xmad + 1,0 xal ≤ 8 (yacabamento)
14
xmad
xal
a
6 12
6
12
4
42 108 1614
2
10
8
14 Max z = 4,0 xmad + 6,0 xal
S. a
1,5 xmad + 4,0 xal ≤ 24 (ycorte)
3,0 xmad + 1,5 xal ≤ 21 (ymontagem)
1,0 xmad + 1,0 xal ≤ 8 (yacabamento)
Solução Primal Ótima:
xmad = 3,2; xal = 4,8
z = 41,6
15
xmad
xal
a
6 12
6
12
4
42 108 1614
2
10
8
14 Max z = 4,0 xmad + 6,0 xal
S. a
1,5 xmad + 4,0 xal ≤ 24 (ycorte)
3,0 xmad + 1,5 xal ≤ 21 (ymontagem)
1,0 xmad + 1,0 xal ≤ 8 (yacabamento)
Solução Dual Ótima:
ycorte = 0,8; ymontagem = 0; 
yacabamento = 2,8
w = 41,6
16
Interpretação da solução dual
� A solução dual nos diz que:
� Se aumentarmos a disponibilidade do setor de 
corte de 24h para 25h, teremos uma acréscimo 
de até 0,8 no lucro da empresa.
� Não haverá aumento no lucro da empresa se 
aumentarmos o número de horas disponíveis no 
setor de montagem
� Teremos um aumento no lucro de no máximo 2,8 
se a disponibilidade do setor de acabamento tiver 
1h a mais
17
xmad
xal
a
6 12
6
12
4
42 108 1614
2
10
8
14 Max z = 4,0 xmad + 6,0 xal
S. a
1,5 xmad + 4,0 xal ≤ 24 (ycorte)
3,0 xmad + 1,5 xal ≤ 21 (ymontagem)
1,0 xmad + 1,0 xal ≤ 8 (yacabamento)
Aumentando a disponibilidade de 8h 
para 9h no setor de acabamento
18
xmad
xal
a
6 12
6
12
4
42 108 1614
2
10
8
14 Max z = 4,0 xmad + 6,0 xal
S. a
1,5 xmad + 4,0 xal ≤ 24 (ycorte)
3,0 xmad + 1,5 xal ≤ 21 (ymontagem)
1,0 xmad + 1,0 xal ≤ 8 (yacabamento)
Aumentando a disponibilidade de 8h 
para 9h no setor de acabamento
19
xmad
xal
a
6 12
6
12
4
42 108 1614
2
10
8
14 Max z = 4,0 xmad + 6,0 xal
S. a
1,5 xmad + 4,0 xal ≤ 24 (ycorte)
3,0 xmad + 1,5 xal ≤ 21 (ymontagem)
1,0 xmad + 1,0 xal ≤ 9 (yacabamento)
Nova Solução Primal Ótima:
xmad = 4,8; xal = 4,2
z = 44,4 = 41,6 + 2,8
20
xmad
xal
a
6 12
6
12
4
42 108 1614
2
10
8
14 Max z = 4,0 xmad + 6,0 xal
S. a
1,5 xmad + 4,0 xal ≤ 24 (ycorte)
3,0 xmad + 1,5 xal ≤ 21 (ymontagem)
1,0 xmad + 1,0 xal ≤ 9 (yacabamento)
Nova Solução Dual Ótima:
ycorte = 0,8; ymontagem = 0; yacabamento = 2,8
w = 44,4
21
xmad
xal
a
6 12
6
12
4
42 108 1614
2
10
8
14 Max z = 4,0 xmad + 6,0 xal
S. a
1,5 xmad + 4,0 xal ≤ 24 (ycorte)
3,0 xmad + 1,5 xal ≤ 21 (ymontagem)
1,0 xmad + 1,0 xal ≤ 9 (yacabamento)
Aumentando a disponibilidade de 9h 
para 10h no setor de acabamento
22
xmad
xal
a
6 12
6
12
4
42 108 1614
2
10
8
14 Max z = 4,0 xmad + 6,0 xal
S. a
1,5 xmad + 4,0 xal ≤ 24 (ycorte)
3,0 xmad + 1,5 xal ≤ 21 (ymontagem)
1,0 xmad + 1,0 xal ≤ 9 (yacabamento)
Aumentando a disponibilidade de 9h 
para 10h no setor de acabamento
23
xmad
xal
a
6 12
6
12
4
42 108 1614
2
10
8
14 Max z = 4,0 xmad + 6,0 xal
S. a
1,5 xmad + 4,0 xal ≤ 24 (ycorte)
3,0 xmad + 1,5 xal ≤ 21 (ymontagem)
1,0 xmad + 1,0 xal ≤ 10 (yacabamento)
Nova Solução Primal Ótima:
xmad = 4,92; xal = 4,15
z = 44,61 = 44,4 + 0,21 < 44,4+2,8
24
xmad
xal
a
6 12
6
12
4
42 108 1614
2
10
8
14 Max z = 4,0 xmad + 6,0 xal
S. a
1,5 xmad + 4,0 xal ≤ 24 (ycorte)
3,0 xmad + 1,5 xal ≤ 21 (ymontagem)
1,0 xmad + 1,0 xal ≤ 10 (yacabamento)
Nova Solução Primal Ótima:
xmad = 4,92; xal = 4,15
z = 44,61 = 44,4 + 0,21 < 44,4+2,8
A partir de um certo ponto o aumento
de horas de acabamento deixa de fazer
efeito porque a solução ótima passa a ser
bloqueada pelas horas de montagem.
25
xmad
xal
a
6 12
6
12
4
42 108 1614
2
10
8
14 Max z = 4,0 xmad + 6,0 xal
S. a
1,5 xmad + 4,0 xal ≤ 24 (ycorte)
3,0 xmad + 1,5 xal ≤ 21 (ymontagem)
1,0 xmad + 1,0 xal ≤ 10 (yacabamento)
Nova Solução Dual Ótima:
ycorte = 1,23; ymontagem = 0,718; yacabamento = 0
w = 44,61
26
xmad
xal
a
6 12
6
12
4
42 108 1614
2
10
8
14 Max z = 4,0 xmad + 6,0 xal
S. a
1,5 xmad + 4,0 xal ≤ 24 (ycorte)
3,0 xmad + 1,5 xal ≤ 21 (ymontagem)
1,0 xmad + 1,0 xal ≤ 8 (yacabamento)
Voltando ao problema original, agora 
vamos diminuir a disponibilidade do 
setor de corte em 0,5h e aumentar a do 
acabamento em 0,5h, simultaneamente
27
xmad
xal
a
6 12
6
12
4
42 108 1614
2
10
8
14 Max z = 4,0 xmad + 6,0 xal
S. a
1,5 xmad + 4,0 xal ≤ 24 (ycorte)
3,0 xmad + 1,5 xal ≤ 21 (ymontagem)
1,0 xmad + 1,0 xal ≤ 8 (yacabamento)
Voltando ao problema original, agora 
vamos diminuir a disponibilidade do 
setor de corte em 0,5h e aumentar a do 
acabamento em 0,5h, simultaneamente
28
xmad
xal
a
6 12
6
12
4
42 108 1614
2
10
8
14 Max z = 4,0 xmad + 6,0 xal
S. a
1,5 xmad + 4,0 xal ≤ 23,5 (ycorte)
3,0 xmad + 1,5 xal ≤ 21 (ymontagem)
1,0 xmad + 1,0 xal ≤ 8,5 (yacabamento)
Voltando ao problema original, agora 
vamos diminuir a disponibilidade do 
setor de corte em 0,5h e aumentar a do 
acabamento em 0,5h, simultaneamente
29
xmad
xal
a
6 12
6
12
4
42 108 1614
2
10
8
14 Maxz = 4,0 xmad + 6,0 xal
S. a
1,5 xmad + 4,0 xal ≤ 23,5 (ycorte)
3,0 xmad + 1,5 xal ≤ 21 (ymontagem)
1,0 xmad + 1,0 xal ≤ 8,5 (yacabamento)
Nova Solução Primal Ótima:
xmad = 4,2; xal = 4,3
z = 42,6 = 41,6 – 0,5*0,8 + 0,5*2,8
30
xmad
xal
a
6 12
6
12
4
42 108 1614
2
10
8
14 Max z = 4,0 xmad + 6,0 xal
S. a
1,5 xmad + 4,0 xal ≤ 23,5 (ycorte)
3,0 xmad + 1,5 xal ≤ 21 (ymontagem)
1,0 xmad + 1,0 xal ≤ 8,5 (yacabamento)
Nova Solução Dual Ótima:
ycorte = 0,8; ymontagem = 0; yacabamento = 2,8
w = 42,6
31
Alterando o custo das 
variáveis
32
Em princípio podemos aplicar os 
resultados já conhecidos ao problema dual
� Teorema – Se um PL possui solução dual 
ótima não-degenerada y* com valor z* e 
solução ótima primal x*, então existe um ε>0 
tal que para todo vetor T=(t1,t2,...,tn), com |tj|≤ε, a solução ótima do novo PL em que T é
somado ao vetor de custos c tem valor:
* *
1
n
j j
j
z x t
=
+∑
33
Interpretação do teorema
Esse teorema indica que uma pequena 
alteração no custo de uma variável tem efeito 
proporcional ao valor dessa variável na 
solução ótima atual (algo quase óbvio). 
Para avaliar melhor o que acontece ao se 
mudar o custo das variáveis não-básicas 
(que costumam ser a maioria) usamos os 
custos reduzidos.
34
Usando os custos reduzidos
� Imagine que resolvemos o seguinte PL pelo 
Simplex
maximizar z = 4,0 x1 + 6,0 x2
Sujeito a
1,5 x1 + 4,0 x2 ≤ 24
3,0 x1 + 1,5 x2 ≤ 21
1,0 x1 + 1,0 x2 ≤ 8
x1 , x2 ≥ 0
35
Os valores na linha z do dicionário final 
fornecem os custos reduzidos das variáveis 
não-básicas (as básicas tem custo red. zero)
2 3 5
4 3 5
1 3 5
3 5
24 2 3
5 5 5
21 3 39
5 5 10
16 2 8
5 5 5
208
5
4 14
5 5
x x x
x x x
x x x
z x x
= − +
= − +
=
− −
+ −
=
36
Os custos reduzidos das variáveis de 
folga/excesso nos fornecem as variáveis 
duais das restrições correspondentes
maximizar z = 4,0 x1 + 6,0 x2
Sujeito a
1,5 x1 + 4,0 x2 + x3 = 24
3,0 x1 + 1,5 x2 + x4 = 21
1,0 x1 + 1,0 x2 + x5 = 8
x1 , x2 ≥ 0
[ ]3 1 2 3 1
1
4 / 5 0 0 4 / 5
0
c y y y y
 
 
= − = − → = 
  
[ ]5 1 2 3 3
0
14 / 5 0 0 14 / 5
1
c y y y y
 
 
= − = − → = 
  
[ ]4 1 2 3 2
0
0 0 1 0
0
c y y y y
 
 
= = − → = 
  
37
Um dicionário é ótimo se o custo reduzido 
de todas as variáveis é desfavorável (≤ 0 
para maximização, ≥ 0 para minimização) 
2 3 5
4 3 5
1 3 5
3 5
24 2 3
5 5 5
21 3 39
5 5 10
16 2 8
5 5 5
208
5
4 14
5 5
x x x
x x x
x x x
z x x
= − +
= − +
= + −
= − −
38
Alterações no custo de uma variável não-
básica mudam diretamente o seu custo 
reduzido.
2 3 5
4 3 5
1 3 5
3 5
24 2 3
5 5 5
21 3 39
5 5 10
16 2 8
5 5 5
208 4 14
5 5 5
x x x
x x x
x x x
z x x
= − +
= − +
= + −
= − −
39
Suponha que o custo de x5 aumenta de 0 
para 2 (digamos que a hora sobrando possa 
ser vendida)
2 3 5
4 3 5
1 3 5
3 5
24 2 3
5 5 5
21 3 39
5 5 10
16 2 8
5 5 5
208 4
5
4
5 5
x x x
x x x
x x x
z x x
= − +
= − +
= + −
= − −
A solução atual
continua sendo
ótima
40
Suponha que o custo de x5 aumenta de 0 
para 4
2 3 5
4 3 5
1 3 5
3 5
24 2 3
5 5 5
21 3 39
5 5 10
16 2 8
5 5 5
208 4
5
6
5 5
x x x
x x x
x x x
z x x
= − +
= − +
=
+
+ −
= −
A solução atual
não é mais ótima!
ótima.
Fazer iterações do
simplex a partir
desse ponto para
achar o novo ótimo.
41
Avaliando o efeito de novas 
variáveis pelo custo reduzido
42
Exemplo
� Uma fábrica produz 50 cadeiras de um único 
tipo por semana.
� A produção não pode ser aumentada porque o 
suprimento de matéria-prima (madeira e 
tecido) são limitados.
� 50 lâminas/semana 75 metros/semana
43
Exemplo
� Para aumentar o lucro, a fábrica considera 
diversificar seu mix de produção. Quais outros 
modelos valem a pena serem produzidos?
44
Dados
150 500 200
1 4 1
1 1 2
400
3
1
45
Programa Linear Completo
x1 x2 x4150 + 500 + 200
x1 x2 x41 + 4 + 1
x1 x2 x41 + 1 + 2
max x3+ 400
x3+ 3
x3+ 1
= 50
= 75
+ x5
+ x6
46
O mix atual representa a solução 
ótima do problema sem as variáveis 
x2, x3 e x4
x1 x2 x4150 + 500 + 200
x1 x2 x41 + 4 + 1
x1 x2 x41 + 1 + 2
max x3+ 400
x3+ 3
x3+ 1
= 50
= 75
+ x5
+ x6
Solução atual = ( 50, 0, 0, 0, 0, 25 )
Lucro atual = R$ 7500,00
pi1= 150
pi2= 0
47
Interpretação das variáveis duais
x1 x2 x4150 + 500 + 200
x1 x2 x41 + 4 + 1
x1 x2 x41 + 1 + 2
max x3+ 400
x3+ 3
x3+ 1
= 50
= 75
+ x5
+ x6
pi1= 150
pi2= 0
Com o mix atual, um aumento ou redução no 
suprimento de madeira afeta o lucro em R$ 
150,00 por unidade.
48
Interpretação das variáveis duais
x1 x2 x4150 + 500 + 200
x1 x2 x41 + 4 + 1
x1 x2 x41 + 1 + 2
max x3+ 400
x3+ 3
x3+ 1
+ x5
+ x6
pi1= 150
pi2= 0
No mix atual existe uma sobra de tecido.
Uma redução nesse suprimento (até um certo ponto ) 
não altera o lucro. 
= 50
= 75
49
Cálculo do custo reduzido das variáveis 
que estão fora do mix atual
x1 x2 x4150 + 500 + 200
x1 x2 x41 + 4 + 1
x1 x2 x41 + 1 + 2
max x3+ 400
x3+ 3
x3+ 1
+ x5
+ x6
pi1= 150
pi2= 0
c2 = ?
c3 = ?
c4 = ?
= 50
= 75
50
Cálculo do custo reduzido das 
variáveis que estão fora do mix atual
x1 x2 x4150 + 500 + 200
x1 x2
x41 + 4 + 1
x1 x2 x41 + 1 + 2
max x3+ 400
x3+ 3
x3+ 1
+ x5
+ x6
pi1= 150
pi2= 0
c3 = ?
c4 = ?
c2 = 500 – [ 150 0 ]
4
1
c2 = -100
= 50
= 75
51
Cálculo do custo reduzido das 
variáveis que estão fora do mix atual
x1 x2 x4150 + 500 + 200
x1 x2 x41 + 4 + 1
x1 x2 x41 + 1 + 2
max x3+ 400
x3+ 3
x3+ 1
+ x5
+ x6
pi1= 150
pi2= 0
c3 = -50
c4 = ?
c3 = 400 – [ 150 0 ]
3
1
c2 = -100
= 50
= 75
52
Cálculo do custo reduzido das 
variáveis que estão fora do mix atual
x1 x2 x4150 + 500 + 200
x1 x2 x41 + 4 + 1
x1 x2 x41 + 1 + 2
max x3+ 400
x3+ 3
x3+ 1
+ x5
+ x6
pi1= 150
pi2= 0
c3 = -50
c4 = 50
c4 = 200 – [ 150 0 ]
1
2
c2 = -100
= 50
= 75
53
Cálculo do custo reduzido das 
variáveis que estão fora do mix atual
x1 x2 x4150 + 500 + 200
x1 x2 x41 + 4 + 1
x1 x2 x41 + 1 + 2
max x3+ 400
x3+ 3
x3+ 1
+ x5
+ x6
pi1= 150
pi2= 0
c3 = -50
c2 = -100
c4 = 50
Só o modelo 4 aumentaria o 
lucro
= 50
= 75
54
Incluindo essa variável no modelo, temos 
uma nova solução
x1 x2 x4150 + 500 + 200
x1 x2 x41 + 4 + 1
x1 x2 x41 + 1 + 2
max x3+ 400
x3+ 3
x3+ 1
= 50
= 75
+ x5
+ x6
Nova solução = ( 25, 0, 0, 25, 0, 0 )
Novo lucro = R$ 8750,00
pi1= 100
pi2= 50
55
Interpretação física da 
dualidade (curiosidade)
56
Interpretação física da dualidade
� Imagine uma “caixa” no espaço cujas 
paredes internas são definidas por 
desigualdades lineares
� Uma pequena bola solta em qualquer ponto 
dessa caixa vai descer até o canto mais 
baixo da caixa.
� O cálculo desse ponto pode ser feito 
resolvendo-se um PL
57
Exemplo
x1
x2
a
b
cd
3 6
3
6
2
2
58
Programa Linear
2
1 2
1 2
1 2
1 2
1 2
min
s. a 2 7
3 0
3 2 0
2 14
, 0
z x
x x
x x
x x
x x
x x
=
+ ≥
− + ≥
− ≥
− − ≥ −
≥
59
Resolvendo Graficamente
x1
x2
a
b
cd
3 6
3
6
2
260
Resolvendo Graficamente
x1
x2
a
b
cd
3 6
3
6
2
2
FO
61
Resolvendo Graficamente
x1
x2
a
b
cd
3 6
3
6
2
2
FO
62
Resolvendo Graficamente
x1
x2
a
b
cd
3 6
3
6
2
2
FO
63
Resolvendo Graficamente
x1
x2
a
b
cd
3 6
3
6
2
2
FO
Sol. Ótima
x1 = 3, x2 = 1
z = 1
64
Dual
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
max 7 0 0 14
s. a 2 3 2 0
3 2 1
, , , 0
w y y y y
y y y y
y y y y
y y y y
= + + −
− + − ≤
+ − − ≤
≥
65
Dual
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
max 7 0 0 14
s. a 2 3 2 0
3 2 1
, , , 0
w y y y y
y y y y
y y y y
y y y y
= + + −
− + − ≤
+ − − ≤
≥
Solução dual ótima:
y1 = 1/7, y2 = 2/7, y3 = 0, y4 = 0
w = 1
66
Interpretação física pelo dual
x1
x2
a
b
cd
3 6
3
6
2
2
Nesse ponto a
única força
sobre a bola
é a gravidade.
Isso corresponde a
uma solução dual
de zero
O ponto não é
estável, a solução
dual não é
ótima
67
Interpretação física pelo dual
x1
x2
a
b
cd
3 6
3
6
2
2
68
Interpretação física pelo dual
x1
x2
a
b
cd
3 6
3
6
2
2
Nesse ponto a
parede b também
exerce uma força
sobre a bola.
Isso corresponde a
uma solução em
que a variável dual
da parede b é > zero
O ponto não é
estável, a solução
dual não é
ótima
69
Interpretação física pelo dual
x1
x2
a
b
cd
3 6
3
6
2
2
70
Interpretação física pelo dual
x1
x2
a
b
cd
3 6
3
6
2
2
71
Interpretação física pelo dual
x1
x2
a
b
cd
3 6
3
6
2
2
Esse ponto é estável,
a bola para.
Isso corresponde a
uma solução dual
em que a forças
exercidas pelas
paredes anula
a gravidade.
72
Interpretação física pelo dual
x1
x2
a
b
cd
3 6
3
6
2
2
c
y1 a1
y2 a2
73
OBSERVAÇÃO
Este material refere-se às notas de aula do curso 
TEP117 (Pesquisa Operacional I) da Universidade 
Federal Fluminense (UFF) e não pode ser 
reproduzido sem autorização prévia do autor. 
Quando autorizado, seu uso é exclusivo para 
atividades de ensino e pesquisa em instituições 
sem fins lucrativos.