Aula – Análise Pós-Otimalidade

Prévia do material em texto

Pesquisa 
Operacional 
Gisele Tessari Santos, D.Sc. 
gisele.santos@prof.una.br 
Aula – Análise Pós-Otimalidade – 
Análise de Sensibilidade 
!"#$%&'()'(*'"&%+%$%),)'(
•  Uma das hipóteses dos problemas de programação linear 
é a consideração de certeza nos coeficientes e 
constantes (parâmetros) do modelo. 
•  A solução ótima é dependente dos coeficientes da função 
objetivo (geralmente lucro, receita ou custo) e dos 
coeficientes e constantes das restrições (geralmente 
necessidades por produto e disponibilidade de um 
recurso). 
•  No mundo real, quase nunca temos certeza destes 
valores, geralmente são apenas estimativas. 
•  Portanto, devemos saber o quanto a solução ótima é 
dependente de um determinado parâmetro. E para isso 
devemos verificar quais são as possíveis variações nos 
valores desses parâmetros que não alteram a solução 
ótima. 
 
!"#$%&'()'(*'"&%+%$%),)'(
•  Devemos, então, fazer uma análise de pós-otimalidade conhecida 
com Análise de Sensibilidade. 
•  Um dos principais objetivos da análise de sensibilidade é 
identificar os parâmetros sensíveis, isto é, aqueles que não 
podem ser modificados sem alterar a solução ótima. 
•  Os parâmetros sensíveis são aqueles que precisam ser estimados 
com especial cuidado para minimizar o risco de se obter uma 
solução ótima errônea e devem ser monitorados de perto à 
medida que o estudo é implementado. 
•  Em uma Análise de Sensibilidade deveremos responder 
basicamente a três perguntas: 
1.  Qual o efeito de uma mudança num coeficiente de uma restrição 
(aij)? 
2.  Qual o efeito de uma mudança numa constante de uma restrição 
(bi)? 
3.  Qual o efeito de uma mudança num coeficiente da função objetivo 
(cj)? 
Sensibilidade dos parâmetros aij(
•  Normalmente é dada mais atenção na realização da 
análise de sensibilidade dos parâmetros bi e cj que nos 
parâmetros aij. 
•  Em problemas reais com centenas ou milhares de 
restrições e variáveis, o efeito de alterar o valor aij 
normalmente é desprezível. 
•  Além disso, em muitos casos, os valores aij são 
determinados pela tecnologia que está sendo empregada. 
Assim, pode haver pouca (ou nenhuma) incerteza em 
relação aos seus valores finais. 
Sensibilidade dos parâmetros bi(
•  No caso dos parâmetros bi, os parâmetros sensíveis são 
identificados a partir dos preços-sombra fornecidos pela 
tabela simplex ou pelo relatório de sensibilidade do Solver 
(excel). 
•  yi* > 0 ! solução ótima muda caso bi seja modificado; 
portanto, bi é um parâmetro sensível e deve ser 
monitorado de perto caso seja uma estimativa do recurso 
disponível. 
•  yi* = 0 ! solução ótima não é sensível a pequenas 
alteração de bi. 
Sensibilidade dos parâmetros bi(
Intervalo possível de bi 
•  Para qualquer bi, seu intervalo possível é o intervalo de 
valores para o lado direito em relação ao qual a solução 
BV ótima atual permanece viável, supondo-se que não 
ocorra nenhuma alteração nos demais lados direitos. 
" O valor de Z e das variáveis de decisão (solução ótima) são 
alterados, mas a solução ótima permanece viável, ou seja, 
respeitando todas as restrições do modelo. 
•  Quando se altera bi dentro desse intervalo possível, o 
preço-sombra atual para bi permanece válido para avaliar 
o efeito sobre Z. 
 
 
 
Como calcular o intervalo possível de bi? 
 
Vamos recordar o nosso problema protótipo. 
Não negatividade !!! 
x
1
≤ 4
2x
2
≤12
3x
1
+ 2x
2
≤18
e
x
1
≥ 0
x
2
≥ 0
Restrições 
Quantidade de recurso bi 
disponibilizados para as 
atividades consideradas. 
•  y1*= 0 – preço sombra para o recurso 1. 
•  y2*= 3/2 – preço sombra para o recurso 2. 
•  y3*= 1 – preço sombra para o recurso 3. 
 
Vamos recordar o nosso problema protótipo. 
 
Veja abaixo a tabela final do Simplex: 
Vamos verificar no gráfico o intervalo possível para o recurso 2: 
*-$./0-(12#3%4,(
2x
2
=18 Z = 3(0)+5(9) = 45
2x
2
= 6 Z = 3(4)+5(3) = 27
Intervalo possível de b2: 
6 ≤ b2 ≤ 18 
Vamos verificar no gráfico o intervalo possível para o recurso 3: 
*-$./0-(12#3%4,(
∆Z= y3* = 1 
Z = 3(4)+5(6) = 42
3x
1
+ 2x
2
=12
Z = 3(0)+5(6) = 30
Intervalo possível de b3: 
12 ≤ b3 ≤ 24 
(2,6) 
3x
1
+ 2x
2
= 24
Vamos verificar no gráfico o intervalo possível para o recurso 1: 
*-$./0-(12#3%4,(
∆Z= y1* = 0 
Z = 3(2)+5(6) = 36
Intervalo possível de b1: 
2 ≤ b1 ≤∞ ou 2 ≤ b1 
(2,6) 
x
1
= 2
Sensibilidade dos parâmetros cj(
•  A alteração em um dos coeficientes cj provoca uma 
alteração no coeficiente angular (inclinação) da reta que 
define a função objetivo. 
•  Visualmente pode-se notar que se a variação na 
inclinação for pequena a solução ótima (valor das 
variáveis de decisão que produzem o maior valor da 
função objetivo) não sofrerá alteração. 
•  Devemos deixar claro que o valor máximo (Z) a ser 
produzido pela solução ótima será diferente, 
independentemente da manutenção da solução ótima. 
Sensibilidade dos parâmetros cj(
Intervalo possível de cj 
•  Para qualquer cj, seu intervalo possível é o intervalo de 
valores para esse coeficiente sobre o qual a solução ótima 
atual permanece ótima, pressupondo-se que não haja 
nenhuma alteração nos demais coeficientes. 
" Os valores das variáveis de decisão (solução ótima) permanecem 
os mesmos, entretanto o resultado para a função objetivo Z se 
altera. 
•  Como cj pode ser modificado dentro do intervalo possível 
sem alterar a solução ótima, cj não é um parâmetro 
sensível. 
 
 
 
Como calcular o intervalo possível de cj? 
 
Vamos verificar no gráfico o intervalo possível para c1 e c2: 
*-$./0-(12#3%4,(
A 
B 
Sensibilidade dos parâmetros cj(
Intervalo possível de cj 
•  Portanto, enquanto a inclinação da função objetivo estiver entre 
as inclinações das retas (2x2 = 12 e 3x1 + 2x2 = 18) que 
determinam a solução ótima esta não se alterará. 
•  Matematicamente, isto pode ser representado por: 
 
Declividade ≤ Declividade ≤ Declividade 
 da Linha A da FO da Linha B 
 
 
 
 
 -3/2 ≤ Declividade ≤ 0 
 da FO 
 
2x
2
=12
0x
1
+ 2x
2
=12
x
2
= −0x
1
+6
3x
1
+ 2x
2
=18
x
2
= −
3
2
x
1
+9
Sensibilidade dos parâmetros cj(
Intervalo possível de cj 
•  De uma forma geral, podemos obter o valor da inclinação 
de uma função objetivo (Z = c1x1 + c2x2) por: 
 
 
 
 
•  Isto é, a inclinação é dada por – c1/c2. Logo, no caso, 
queremos: 
 
 
 
x
2
= −
c
1
c
2
x
1
+
Z
c
2
−3
2
≤ −
c
1
c
2
≤ 0
Sensibilidade dos parâmetros cj(
Intervalo possível de cj 
•  Assim, tem-se: 
 
 
 
 
 
 
 
−3
2
≤ −
c
1
5
≤ 0
−
c
1
5
≥
−3
2
→
c
1
5
≤
3
2
→ c
1
≤ 7,5
E
−
c
1
5
≤ 0→
c
1
5
≥ 0→ c
1
≥ 0








0 ≤ c
1
≤ 7,5
−3
2
≤ −
3
c
2
≤ 0
−
3
c
2
≥
−3
2
→
3
c
2
≤
3
2
→ 6 ≤ 3c
2
→ c
2
≥ 2
E
−
3
c
2
≤ 0→
3
c
2
≥ 0→ 3≥ 0c
2
→ c
2
≤∞









2 ≤ c
2
≤∞
5'$,672%-()'(*'"&%+%$%),)'()-(*-$8'2(
9%+$%-:2,3%,(
Introdução à Pesquisa Operacional; 9ª Edição 
Autor: Frederick S. Hillier; Gerald J. Lieberman 
Editora: McGraw-Hill!