Aula 09 - Análise de Sensibilidade

Prévia do material em texto

Aula 9 – Análise de sensibilidade 
Objetivo: 
1. Mostrar qual o impacto na solução ótima das alterações no lado direito das restrições. 
 
1. Introdução 
Foi visto em aulas anteriores que o principal método de resolução de PPLs é o método Simplex. 
Uma pergunta natural que pode surgir após a aplicação deste método é: 
“Caso ocorram pequenas alterações no modelo, é necessário executar o método novamente para 
avaliar a alteração na solução ótima?” 
 A resposta para a pergunta prévia é não pois existem técnicas que permitem avaliar o 
comportamento da solução ótima caso pequenas alterações ocorram no modelo. Nesta aula, são 
vistas técnicas deste tipo para as seguintes alterações: 
• Alterações no lado direito das restrições. 
• Alterações nos custos das variáveis. 
• Adição de novas variáveis ao PPL. 
Todas as discussões nesta aula feitas partem do princípio que o modelo analisado esteja na forma 
canônica de maximização, ou seja, que o modelo esteja escrito como: 
 max max 𝑐𝑇𝑥 
s.a s.a. 𝐴𝑥 ≤ 𝑏 
𝑥 ≥ 0 
 
2. Alterações no lado direito das restrições 
Considere um PPL na forma canônica de maximização com 𝑛 variáveis e com 𝑚 restrições e com 
solução ótima 𝑥∗ = (𝑥1
∗, 𝑥2
∗, … , 𝑥𝑛
∗ ), que gera um valor da função objetivo com valor ótimo 𝑧∗. 
Queremos saber se o valor de 𝑧∗ muda e para quanto muda se forem adicionados 𝑡1, 𝑡2, … , 𝑡𝑚 ao 
lado direito de cada uma das restrições. O Teorema 9.1 responde tal pergunta. 
 
Teorema 9.1 Se um PPL na forma canônica de maximização com 𝑛 variáveis e 𝑚 restrições e 
possui solução ótima 𝑥∗ = (𝑥1
∗, 𝑥2
∗, … , 𝑥𝑛
∗ ) que gera um valor da função objetivo com valor ótimo 
𝑧∗ e com solução dual ótima 𝑦∗ = (𝑦1
∗, 𝑦2
∗, … , 𝑦𝑚
∗ ), então existe 𝜖 > 0 tal que para todo 𝑇 =
(𝑡1, 𝑡2, . . , 𝑡𝑚) com |𝑇| ≤ 𝜖 o valor ótimo da função objetivo muda para 𝑧∗ + ∑ 𝑦𝑖
∗𝑡𝑖
𝑚
𝑖=1 se 
𝑡1, 𝑡2, … , 𝑡𝑚 forem adicionados ao lado direito das restrições 1, 2,..., 𝑚 do modelo, 
respectivamente. 
 
O Teorema 9.1 diz então que quando o lado direito das restrições é pouco alterado, então a 
mudança no valor ótimo da função objetivo é proporcional aos valores das variáveis duais ótimas. 
Em outras palavras, os valores ótimos das variáveis duais funcionam como uma espécie de 
gradiente da função objetivo em relação ao lado direito das restrições. Por tal motivo, diversos 
autores se referem a cada valor ótimo das variáveis duais como preço-sombra. 
 
Muitos autores se referem a cada valor ótimo das variáveis duais como preço-sombra, por eles 
se comportarem como uma espécie de gradiente da função objetivo em relação ao lado direito 
das restrições. 
 
 
 
 
Para ilustrar o Teorema 12.1, considere os seguintes modelos primal e dual: 
 
Modelo Primal Modelo dual 
𝑀𝑎𝑥 𝑧 = 3𝑥1 + 𝑥2 𝑀𝑖𝑛 𝑤 = 3𝑦1 + 4𝑦2 + 14𝑦3 
s.a.: −2𝑥1 + 𝑥2 ≤ 3 s.a.: −2𝑦1 +
2
3
𝑦2 + 3y3 ≥ 3 
2
3
𝑥1 + 𝑥2 ≤ 4 
𝑦1 + 𝑦2 + 2y3 ≥ 1 
3𝑥1 + 2𝑥2 ≤ 14 y1, 𝑦2, 𝑦3 ≥ 0 
𝑥1 , 𝑥2 ≥ 0 
 
As solução ótima do primal é 𝑥1
∗ =
14
3
 e 𝑥2
∗ = 0, que gera 𝑧∗ = 14 enquanto que a solução ótima 
do dual é 𝑦1
∗ = 0, 𝑦2
∗ = 0 e 𝑦3
∗ = 1, com 𝑤∗ = 14. 
 
Note que o valor ótimo da função objetivo é 𝑧∗ = 14 e os valores ótimos das variáveis duais 
(preços sombra) são 𝑦1
∗ = 0, 𝑦2
∗ = 0 e 𝑦3
∗ = 1. Com base no Teorema 9.1, pode-se concluir que: 
 
• Como 𝑦1
∗ = 0, 𝑦2
∗ = 0, se os lados direitos das restrições 1 e 2 forem alterados, o valor de 
𝑧∗ não mudará. 
• Como 𝑦3
∗ = 1, se o lado direito da terceira restrição for alterado de 14 para 14 + 𝑡3, então 
o valor ótimo da função objetivo mudará de 𝑧∗ = 14 para 𝑧∗ = 14 + 1 × 𝑡3 
 
Suponha que o modelo representa por exemplo a maximização do lucro de uma empresa em função 
da produção de dois tipos de produto (𝑥1 e 𝑥2) e a terceira restrição representa a disponibilidade 
de uma dada matéria prima, que atualmente está em 14 (lado direito). Suponha ainda que o 
fornecedor oferece a empresa a possibilidade de aumento da disponibilidade de 14 para 16 a um 
custo de R$ 0,50 por unidade de aumento. A empresa deve aceitar? A resposta para pergunta é sim 
pois o custo unitário oferecido (R$ 0,50) será menor do que o aumento proporcionado (R$ 1,00 
por unidade de aumento). 
 
A seguir, uma interpretação gráfica para o aumento de duas unidades no lado direito da terceira 
restrição. Primeiramente, observe a região de soluções viáveis sem o aumento, onde é destacada a 
solução ótima do modelo. 
 
 
 
Ao se adicionar duas unidades no lado direito da terceira restrição, ocorre um deslocamento para 
direita da reta verde, conforme ilustra a seguinte Figura. 
 
 
 
Note que o aumento mudará a solução ótima. Note ainda que dependendo do tamanho do aumento, 
existe a possibilidade da restrição se deslocar ao ponto de se tornar redundante. Neste caso, o 
Teorema 9.1 passaria a não valer mais. 
 
 
O Teorema 9.1 é válido inclusive se algum valor de 𝑡 for negativo mas deve-se sempre tomar 
cuidado ao pois as conclusões do Teorema só são em geral válidas para pequenas alterações. 
 
 
 
 
 
 
 
 
 
 
 
 
 
(𝑥1
∗ =
14
3
, 𝑥2
∗ = 0) 𝑧∗ = 14 
 
 
 
 
Vimos na aula anterior como encontrar o modelo dual de qualquer modelo PL. Vimos ainda 
também o teorema das folgas complementares que diz que se na solução ótima do modelo primal 
uma variável assume valor diferente de zero então a restrição associada no dual possuirá folga 
zero. De maneira similar, se uma variável dual ótima assume valor diferente de zero então a 
restrição associada no primal possuirá folga zero. Com base principalmente no teorema prévio, 
vimos: 
1. Como checar se uma solução viável é ótima ou não para um modelo PL. 
2. Como se obter a solução dual ótima com base na solução ótima de um modelo PL. 
 
Vamos relembrar alguns conceitos da aula anterior através de um exemplo: 
Exemplo 12.1 Considere o seguinte modelo: 
𝑀𝑎𝑥 𝑧 = 3𝑥1 + 𝑥2 
s.a. −2𝑥1 + 𝑥2 ≤ 3 
𝑥2 ≤ 10 
3𝑥1 + 2𝑥2 ≤ 14 
𝑥1 ≥ 0 
𝑥2 ≥ 0 
Com solução ótima 𝑥1
∗ =
14
3
 e 𝑥2
∗ = 0, que gera 𝑧∗ = 14 (verifique com exercício). O dual do 
modelo prévio é: 
𝑀𝑖𝑛 𝑤 = 3𝑦1 + 10𝑦2 + 14𝑦3 
s.a. −2𝑦1 + 0𝑦2 + 3y3 ≥ 3 
 𝑦1 + 𝑦2 + 2y3 ≥ 1 
 y1, 𝑦2, 𝑦3 ≥ 0 
Com base no Teorema das folgas complementares, vamos encontrar a solução dual ótima sem 
precisarmos aplicar o Simplex no modelo dual. Para isso, calculamos as folgas de cada restrição 
do modelo primal com base na solução ótima 𝑥1
∗ =
14
3
 e 𝑥2
∗ = 0: 
Restrição 
primal 
Inequação Folga 
1 −2𝑥1 + 𝑥2 ≤ 3 37
3
 
2 𝑥2 ≤ 10 10 
3 3𝑥1 + 2𝑥2 ≤ 14 0 
 
Com base no teorema das folgas complementares, tiramos algumas conclusões: 
• Como as folgas das restrições 1 e 2, foram diferentes de zeros, na solução dual ótima 
teremos 𝑦1
∗ = 0 e 𝑦2
∗ = 0. 
• Como 𝑥1
∗ =
14
3
 é diferente de zero, temos que a restrição 1 do dual (−2𝑦1 + 0𝑦2 + 3y3 ≥
 3) não possuirá folga, ou seja, −2𝑦1
∗ + 0𝑦2
∗ + 3y3
∗ = 3 
Com base nas conclusões prévias temos que 𝑦1
∗ = 0, 𝑦2
∗ = 0 e 𝑦3
∗ = 1. Note quando substituímos 
os valores prévios na função objetivo do dual, encontramos 𝑤∗ = 3(0) + 10(0) + 14(1) = 14. 
Tal valor já era esperado pois o teorema da dualidade forte garante que os valores ótimos das 
funções objetivo do dual e do primal são iguais. 
Nesta aula, veremos que uma vez que já tenhamos resolvido um modelo PL, existem técnicas que 
permitem avaliar como pequenas alterações no modelo podem alterar a solução ótima, sem 
precisar resolver o modelo PL do início novamente. As possíveis alterações que veremos são: 
• Alterações no lado direito das restrições. 
• Alterações nos custos das variáveis. 
• Adição de novas variáveis. 
 
Antes de detalharmos cada uma destas alterações, vamos definir o conceito de custo reduzido de 
uma variável, que nada mais é do que a folga da restrição associadano modelo dual. Voltemos 
ao Exemplo 12.1. Com base na solução ótima dual 𝑦1
∗ = 0, 𝑦2
∗ = 0 e 𝑦3
∗ = 1, vamos calcular as 
folgas no modelo dual: 
 
Restrição 
dual 
Inequação Folga 
1 −2𝑦1 + 0𝑦2 + 3y3 ≥ 3 0 
2 𝑦1 + 𝑦2 + 2y3 ≥ 1 -1 
 
Com base na definição de custo reduzido, temos custo reduzido de 𝑥1 é igual a zero e custo 
reduzido de 𝑥2 é igual a -1. 
De agora em diante, vamos usar 𝑐̅ para denotar custo reduzido. Assim, no Exemplo 12.1 temos 
𝑐1̅ = 0 e 𝑐2̅ = −1 
 
Alterando o lado direito das restrições 
 
Seja um modelo PL com 𝑛 variáveis e com 𝑚 restrições e com solução ótima 𝑥∗ =
(𝑥1
∗, 𝑥2
∗, … , 𝑥𝑛
∗ ), que gera um valor da função objetivo ótimo 𝑧∗. Queremos saber se o valor de 𝑧∗ 
muda e para quanto muda se adicionarmos 𝑡1, 𝑡2, … , 𝑡𝑚 ao lado direito de cada uma das restrições. 
O Teorema 12.1 responde tal pergunta. 
 
Teorema 12.1 Se um modelo PL com 𝑛 variáveis e 𝑚 restrições e possui solução ótima 𝑥∗ =
(𝑥1
∗, 𝑥2
∗, … , 𝑥𝑛
∗ ) que gera um valor da função objetivo ótimo 𝑧∗ e uma solução dual ótima 𝑦∗ =
(𝑦1
∗, 𝑦2
∗, … , 𝑦𝑚
∗ ), então existe 𝜖 > 0 tal que para todo 𝑇 = (𝑡1, 𝑡2, . . , 𝑡𝑚) com |𝑇| ≤ 𝜖 o valor ótimo 
da função objetivo muda para 𝑧∗ + ∑ 𝑦𝑖
∗𝑡𝑖
𝑚
𝑖=1 se somarmos o vetor 𝑇 ao lado direito das restrições 
do modelo. 
 
O Teorema 12.1 diz então que quando alteramos pouco o lado direito das restrições a mudança no 
valor ótimo da função objetivo será proporcional ao valore das variáveis duais. Em outras palavras, 
as variáveis duais funcionam como uma espécie de gradiente da função objetivo em relação ao 
lado direito das restrições. 
 
Quando o assunto é análise de sensibilidade, os valores das variáveis duais recebem o nome 
especial de preço-sombra. 
 
Vamos voltar ao Exemplo 12.1. Neste exemplo, o valor ótimo da função objetivo é 𝑧∗ = 14 e 
solução ótima é dual ótima (preços sombra) é 𝑦1
∗ = 0, 𝑦2
∗ = 0 e 𝑦3
∗ = 1. Com base no Teorema 
12.1 podemos concluir que: 
 
• Como 𝑦1
∗ = 0, 𝑦2
∗ = 0, se alterarmos os lados direitos das restrições 1 e 2, o valor de 𝑧∗ não 
mudará. 
• Como 𝑦3
∗ = 1, se alteramos o lado direito da no lado direito da terceira restrição de 14 
para 14 + 𝑡3 e , então o valor ótimo da função objetivo mudará de 𝑧∗ = 14 para 𝑧∗ = 14 +
1𝑡3 
 
Suponha que o modelo representa por exemplo a maximização lucro em R$ de uma empresa em 
função da produção de dois tipos de produto (𝑥1 e 𝑥2) e a terceira restrição representa a 
disponibilidade de uma matéria prima, que atualmente está em 14 (lado direito). Suponha ainda 
que o fornecedor oferece a empresa a possibilidade de aumento da disponibilidade de 14 para 15 
a um custo de R$ 1,50. A empresa deve aceitar? A resposta para pergunta é não pois o custo 
oferecido (R$ 1,50) será maior do que o aumento proporcionado (R$ 1,00). 
 
O Teorema 12.1 é válido inclusive se algum valor de 𝑡 for negativo mas devemos sempre tomar 
cuidado ao usarmos este pois as suas conclusões só são em geral válidas para pequenas alterações. 
Para exemplificar, considere o Exemplo 12.2 
 
Exemplo 12.2 
 
𝑀𝑎𝑥 𝑧 = 20𝑥1 + 10𝑥2 
s.a. 3𝑥1 + 2𝑥2 ≤ 90 
𝑥1 ≤ 25 
𝑥2 ≤ 15 
 
𝑥1 , 𝑥2 ≥ 0 
A região de soluções deste problema é: 
 
A solução ótima deste problema é 𝑥1
∗ = 25 e 𝑥2
∗ = 7,5 e gera 𝑧∗ = 575. A solução dual ótima 
(preços sombra) é 𝑦1
∗ = 5, 𝑦2
∗ = 5 e 𝑦3
∗ = 0 (verifique). Assim, de acordo com Teorema 12.1, se 
por exemplo aumentarmos o lado direito da restrição 1 em 1 unidade (90 para 91), teremos um 
aumento de 5 unidades em 𝑧∗ (575 para 580) e isto realmente acontece. A pergunta que fica é: se 
este aumento no lado direito for muito grande, esta conclusão ainda é válida? A resposta é não 
pois quando aumentamos o lado direito da restrição 3𝑥1 + 2𝑥2 ≤ 90 obtemos uma restrição 
paralela um pouco mais acima da restrição original. Veja graficamente o que acontece quando 
aumentamos por exemplo o lado direito de 90 para 150 (60 unidades de aumento). 
 
A solução ótima agora 𝑥1
∗ = 25 e 𝑥2
∗ = 15 e gera 𝑧∗ = 650. Note que o aumento não foi de 
60 × 5 = 300 unidades. 
 
Como então saber o quanto podemos aumentar ou diminuir o lado direito das restrições de modo 
que a conclusão do Teorema 12.1 continue válida? Este processo é conhecido como determinação 
das faixas de viabilidade de cada recurso e é o que aprenderemos agora. 
 
Determinando as faixas de viabilidade 
 
Suponha que você resolveu o modelo do Exemplo 12.2 via Simplex. Para isso, você colocou o 
modelo na forma padrão: 
𝑀𝑎𝑥 𝑧 = 20𝑥1 + 10𝑥2 
s.a. 3𝑥1 + 2𝑥2 + 𝑥3 = 90 
𝑥1 + 𝑥4 = 25 
𝑥2 + 𝑥5 = 15 
 
𝑥1 , 𝑥2 ≥ 0 
e obteve o dicionário (quadro) ótimo: 
 
Note que os coeficientes de 𝒙𝟑, 𝒙𝟒 e 𝒙𝟓 na linha 𝒛 são justamente os preços sombra das 
restrições 1, 2 e 3 com o sinal trocado e isto não é uma coincidência. Tal fato sempre acontece. 
Assim, os preços sombra das restrições 1,2 e 3 são respectivamente 5, 5 e 0. 
 
Caso tivéssemos adicionado 𝑡1, 𝑡2 e 𝑡3 ao lado direito das restrições 1, 2 e 3 respectivamente, 
teríamos: 
 
𝑀𝑎𝑥 𝑧 = 20𝑥1 + 10𝑥2 
s.a. 3𝑥1 + 2𝑥2 + 𝑥3 = 90 +
𝑡1 
𝑥1 + 𝑥4 = 25 + 𝑡2 
𝑥2 + 𝑥5 = 15 + 𝑡3 
𝑥1 , 𝑥2 ≥ 0 
 
 
 
Note que 𝑡1, 𝑡2 e 𝑡3 tem sinais opostos aos das variáveis de folga 𝑥3, 𝑥4, 𝑥5 respectivamente. Assim, 
no quadro ótimo 𝑡1, 𝑡2 e 𝑡3 apareceriam com os mesmos coeficientes destas variáveis mas com 
sinal trocado: 
 
Como as variáveis são todas não negativas, então a faixa de viabilidade são todos os valores de 𝑡1, 
𝑡2 e 𝑡3 tais que: 
 
Assim, por exemplo, quando aumentamos o lado direito da primeira restrição de 90 para 91, 
tomamos 𝑡1 = 1, 𝑡2 = 0 e 𝑡3 = 0. Note que as inequações prévias continuam satisfeitas. Logo, 
esta alteração é válida e conseguimos calcular o novo valor da função objetivo com base nos preços 
sombra. Já quando aumentamos de 90 para 150, tomamos 𝑡1 = 60, 𝑡2 = 0 e 𝑡3 = 0. Note que 
neste caso a primeira inequação não é satisfeita, e portanto, não podemos calcular a alteração no 
valor ótimo da função objetivo com base nos preços sombra. 
 
Mantendo 𝑡2 = 0 e 𝑡3 = 0, qual o maior aumento que podemos fazer na primeira restrição? 
Queremos neste caso, o maior valor de 𝑡1 que satisfazem as inequações. Note que este valor é 15. 
 
Na próxima aula, veremos os demais tipos de alterações. 
Exercícios 
Exercício 12.1 Considere o modelo: 
𝑚𝑎𝑥 𝑧 = 2𝑥1 + 3𝑥2 
s.a. 𝑥1 + 2𝑥2 ≤ 8 
−2𝑥1 + 3𝑥2 ≤ 5 
𝑥1 + 𝑥2 ≤ 6 
𝑥1, 𝑥2 ≥ 0 
 
Com quadro ótimo: 
 
 
 
a) Quais os preços sombra de cada restrição? 
b) Quais as faixas de viabilidade? 
c) Se você fosse investir no aumento do lado direito de uma das restrições, em qual você 
investiria? Justifique.