Análise de Sensibilidade

Prévia do material em texto

Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Análise de Sensibilidade
André Gustavo dos Santos
Departamento de Informática
Universidade Federal de Viçosa
INF 280 - 2013/1
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Análise de sensibilidade
Resolvido um modelo, analisar o impacto que pequenas
alterações nos dados causam na soluçao ótima
Exemplos: o que acontece com a solução ótima se:
houver mais uma unidade de certa matéria-prima?
houver mais duas, mais 10 unidades?
houver menos unidades?
aumentar/diminuir a receita de certo produto?
mudar o consumo de matéria-prima para fabricar certo
produto?
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Problema da fábrica de tintas - Solução gráfica
Modelo de PL
max z = 5xe + 4xi
s.a.
6xe + 4xi ≤ 24
xe + 2xi ≤ 6
xi − xe ≤ 1
xi ≤ 2
xe, xi ≥ 0
Solução ótima:
xe = 3
xi = 1.5
z = 21
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Exemplo de modelo de PL
Dois produtos: x1 e x2
Duas restrições de matéria-prima: M1 e M2
Modelo
max 20x1 + 24x2
s.a.
2x1 + 3x2 ≤ 12 (M1)
2x1 + x2 ≤ 8 (M2)
x1, x2 ≥ 0
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Solução simplex
Quadro inicial e final
x1 x2 f1 f2 b
−z 20 24 0 0 0
f1 2 3 1 0 12
f2 2 1 0 1 8
...
x1 x2 f1 f2 b
−z 0 0 -7 -3 -108
x2 0 1 1/2 -1/2 2
x1 1 0 -1/4 3/4 3
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Solução simplex
E se houvesse 9 de M2?
x1 x2 f1 f2 b
−z 20 24 0 0 0
f1 2 3 1 0 12
f2 2 1 0 1 9
...
x1 x2 f1 f2 b
−z 0 0 -7 -3 -111
x2 0 1 1/2 -1/2 1.5
x1 1 0 -1/4 3/4 3.75
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Solução simplex
E se houvesse 10 de M2?
x1 x2 f1 f2 b
−z 20 24 0 0 0
f1 2 3 1 0 12
f2 2 1 0 1 10
...
x1 x2 f1 f2 b
−z 0 0 -7 -3 -114
x2 0 1 1/2 -1/2 1
x1 1 0 -1/4 3/4 4.5
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Solução simplex
Note que cada unidade a mais de M2 aumenta 3 na FO!
x1 x2 f1 f2 b
−z 20 24 0 0 0
f1 2 3 1 0 12
f2 2 1 0 1 8 9 10
...
x1 x2 f1 f2 b
−z 0 0 -7 -3 -108 -111 -114
x2 0 1 1/2 -1/2 2 1.5 1
x1 1 0 -1/4 3/4 3 3.75 4.5
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Solução simplex
Na verdade isso pode ser previsto na linha z...
x1 x2 f1 f2 b
−z 20 24 0 0 0
f1 2 3 1 0 12
f2 2 1 0 1 8 9 10
...
x1 x2 f1 f2 b
−z 0 0 -7 -3 -108 -111 -114
x2 0 1 1/2 -1/2 2 1.5 1
x1 1 0 -1/4 3/4 3 3.75 4.5
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Solução simplex
Os coeficientes das folgas na linha z indicam a taxa de variação na
FO resultante da alteração na disponibilidade do recurso
correspondente
x1 x2 f1 f2 b
−z 0 0 -7 -3 -108
x2 0 1 1/2 -1/2 2
x1 1 0 -1/4 3/4 3
Os valores marcados permitem prever que:
Cada unidade a mais de M1 aumenta 7 na FO
Cada unidade a mais de M2 aumenta 3 na FO
Cada unidade a menos de M1 diminui 7 na FO
Cada unidade a menos de M2 diminui 3 na FO
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Solução simplex
O quadro final indica não apenas a solução ótima:
Produzir 2 de x2 e 3 de x1, valor ótimo 108.
x1 x2 f1 f2 b
−z 0 0 -7 -3 -108
x2 0 1 1/2 -1/2 2
x1 1 0 -1/4 3/4 3
Também permite prever soluções em outros cenários, por exemplo:
Se puder escolher entre uma unidade adicional de M1 ou M2, a
custo zero, qual é melhor? M1, pois ganha mais por unidade
Se o fornecedor de M1 cobrar 5 por unidades adicionais,
compensa adquirir? Sim, pois ganharia 7 por unidade
Se o fornecedor de M2 cobrar 5 por unidades adicionais,
compensa adquirir? Não, pois ganharia apenas 3 por unidade
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Solução simplex
Os coeficientes das folgas na linha z indicam a taxa de variação, e
são chamados de preços duais (ou preço sombra).
x1 x2 f1 f2 b
−z 0 0 -7 -3 -108
x2 0 1 1/2 -1/2 2
x1 1 0 -1/4 3/4 3
Eles podem ser vistos como o valor unitário equivalente do recurso:
Uma unidade de M1 vale 7
Uma unidade de M2 vale 3
Note que eram disponíveis 12 e 8 respectivamente de M1 e M1.
O valor total é 12× 7 + 8× 3 = 108, exatamente o valor da FO
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
ATENÇÃO!!
Isso vale dentro de uma faixa de viabilidade!
Vale desde que a base permaneça viável!
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Mudança no termo independente
Modelo PL na forma padrão,
em notação matricial
max z = cx
Ax = b
x ≥ 0
Modelo PL com divisão em
variáveis básicas e não-básicas
max z = cBxB + cNxN
BxB + NxN = b
xB,xN ≥ 0
Na solução simplex, x é particionado em xB e xN ,
respectivamente variáveis básicas e não-básicas
Pode-se então particionar o vetor c e a matriz A de
coeficientes, de acordo com a partição de x
Sejam cB e cN os coeficientes na função objetivo das
variáveis básicas e não-básicas respectivamente
Sejam B e N as matrizes de coeficientes nas restrições
das variáveis básicas e não-básicas respectivamente
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Mudança no termo independente
Para uma dada base xB viável temos:
BxB + NxN = b
Como xN são não-básicas, xN = 0
BxB = b
Multiplicando a equação pela matriz inversa1 de B
B−1BxB = B−1b
IxB = B−1b
xB = B−1b
Então, dado um vetor xB de variáveis básicas, e sendo B a
matriz de coeficientes dessas variáveis nas restrições, a
solução pode ser calculada por
xB = B−1b
1se o sistema for compatível, B possui inversa
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Exemplo de modelo de PL
Três tipos de cultura: xA, xB e xC
Restrições de hectares, água e fertilizante
Modelo
max 30xA + 20xB + 50xC
s.a.
xA + xB + xC ≤ 18 (hectares)
2xA + xB + 2xC ≤ 30 (água)
xA + xB + 2xC ≤ 24 (fertilizante)
xA, xB, xC ≥ 0
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Solução simplex
Inicial:
xA xB xC f1 f2 f3 b
−z 30 20 50 0 0 0 0
f1 1 1 1 1 0 0 18 (hectares)
f2 2 1 2 0 1 0 30 (água)
f3 1 1 2 0 0 1 24 (fertilizante)
Final:
xA xB xC f1 f2 f3 b
−z 0 -5 0 0 -5 -20 -630
f1 0 1/2 0 1 -1/2 0 3
xA 1 0 0 0 1 -1 6
xC 0 1/2 1 0 -1/2 1 9
B =

f1 xA xC
1 1 1
0 2 2
0 1 2

B−1 =
1 − 1/2 00 1 − 1
0 − 1/2 1

Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Solução simplex
Inicial:
xA xB xC f1 f2 f3 b
−z 30 20 50 0 0 0 0
f1 1 1 1 1 0 0 18 (hectares)
f2 2 1 2 0 1 0 30 (água)
f3 1 1 2 0 0 1 24 (fertilizante)
Final:
xA xB xC f1 f2 f3 b
−z 0 -5 0 0 -5 -20 -630
f1 0 1/2 0 1 -1/2 0 3
xA 1 0 0 0 1 -1 6
xC 0 1/2 1 0 -1/2 1 9
B =

f1 xA xC
1 1 1
0 2 2
0 1 2

B−1 =
1 − 1/2 00 1 − 1
0 − 1/2 1

Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Solução simplex
Inicial:
xA xB xC f1 f2 f3 b
−z 30 20 50 0 0 0 0
f1 1 1 1 1 0 0 18 (hectares)
f2 2 1 2 0 1 0 30 (água)
f3 1 1 2 0 0 1 24 (fertilizante)
Final:
xA xB xC f1 f2 f3 b
−z 0 -5 0 0 -5 -20 -630
f1 0 1/2 0 1 -1/2 0 3
xA 1 0 0 0 1 -1 6
xC 0 1/2 1 0 -1/2 1 9
B =

f1xA xC
1 1 1
0 2 2
0 1 2

B−1 =
1 − 1/2 00 1 − 1
0 − 1/2 1

Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Solução simplex
Inicial:
xA xB xC f1 f2 f3 b
−z 30 20 50 0 0 0 0
f1 1 1 1 1 0 0 18 (hectares)
f2 2 1 2 0 1 0 30 (água)
f3 1 1 2 0 0 1 24 (fertilizante)
Final:
xA xB xC f1 f2 f3 b
−z 0 -5 0 0 -5 -20 -630
f1 0 1/2 0 1 -1/2 0 3
xA 1 0 0 0 1 -1 6
xC 0 1/2 1 0 -1/2 1 9
B =

f1 xA xC
1 1 1
0 2 2
0 1 2

B−1 =
1 − 1/2 00 1 − 1
0 − 1/2 1

Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Solução simplex
Inicial:
xA xB xC f1 f2 f3 b
−z 30 20 50 0 0 0 0
f1 1 1 1 1 0 0 18 (hectares)
f2 2 1 2 0 1 0 30 (água)
f3 1 1 2 0 0 1 24 (fertilizante)
Final:
xA xB xC f1 f2 f3 b
−z 0 -5 0 0 -5 -20 -630
f1 0 1/2 0 1 -1/2 0 3
xA 1 0 0 0 1 -1 6
xC 0 1/2 1 0 -1/2 1 9
B =

f1 xA xC
1 1 1
0 2 2
0 1 2

B−1 =
1 − 1/2 00 1 − 1
0 − 1/2 1

Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Solução simplex
Inicial:
xA xB xC f1 f2 f3 b
−z 30 20 50 0 0 0 0
f1 1 1 1 1 0 0 18 (hectares)
f2 2 1 2 0 1 0 30 (água)
f3 1 1 2 0 0 1 24 (fertilizante)
Final:
xA xB xC f1 f2 f3 b
−z 0 -5 0 0 -5 -20 -630
f1 0 1/2 0 1 -1/2 0 3
xA 1 0 0 0 1 -1 6
xC 0 1/2 1 0 -1/2 1 9
B =

f1 xA xC
1 1 1
0 2 2
0 1 2
 B−1 =
1 − 1/2 00 1 − 1
0 − 1/2 1

Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Solução simplex
Inicial:
xA xB xC f1 f2 f3 b
−z 30 20 50 0 0 0 0
f1 1 1 1 1 0 0 18 (hectares)
f2 2 1 2 0 1 0 30 (água)
f3 1 1 2 0 0 1 24 (fertilizante)
Final:
xA xB xC f1 f2 f3 b
−z 0 -5 0 0 -5 -20 -630
f1 0 1/2 0 1 -1/2 0 3
xA 1 0 0 0 1 -1 6
xC 0 1/2 1 0 -1/2 1 9
B =

f1 xA xC
1 1 1
0 2 2
0 1 2
 B−1 =
1 − 1/2 00 1 − 1
0 − 1/2 1

Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Solução simplex
Inicial:
xA xB xC f1 f2 f3 b
−z 30 20 50 0 0 0 0
f1 1 1 1 1 0 0 18 (hectares)
f2 2 1 2 0 1 0 30 (água)
f3 1 1 2 0 0 1 24 (fertilizante)
Final:
xA xB xC f1 f2 f3 b
−z 0 -5 0 0 -5 -20 -630
f1 0 1/2 0 1 -1/2 0 3
xA 1 0 0 0 1 -1 6
xC 0 1/2 1 0 -1/2 1 9
A matriz inversa da base pode ser obtida diretamente dos valores
nas colunas das variáveis de folga no quadro simplex final
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Mudança no termo independente
Inicial:
xA xB xC f1 f2 f3 b
−z 30 20 50 0 0 0 0
f1 1 1 1 1 0 0 18 (hectares)
f2 2 1 2 0 1 0 30 (água)
f3 1 1 2 0 0 1 24 (fertilizante)
Final:
xA xB xC f1 f2 f3 b
−z 0 -5 0 0 -5 -20 -630
f1 0 1/2 0 1 -1/2 0 3
xA 1 0 0 0 1 -1 6
xC 0 1/2 1 0 -1/2 1 9
Cálculo da solução ótima:
xB = B−1b ∴
 f1xA
xC
 =
1 −1/2 00 1 −1
0 −1/2 1
×
1830
24
 ∴
 f1xA
xC
 =
36
9

z = 30xA + 20xB + 50xC = 30× 6 + 50× 9 = 630
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Mudança no termo independente
Inicial:
xA xB xC f1 f2 f3 b
−z 30 20 50 0 0 0 0
f1 1 1 1 1 0 0 18 (hectares)
f2 2 1 2 0 1 0 30 (água)
f3 1 1 2 0 0 1 24 (fertilizante)
Final:
xA xB xC f1 f2 f3 b
−z 0 -5 0 0 -5 -20 -630
f1 0 1/2 0 1 -1/2 0 3
xA 1 0 0 0 1 -1 6
xC 0 1/2 1 0 -1/2 1 9
Se houvesse 25 un. fertilizante:
xB = B−1b ∴
 f1xA
xC
 =
1 −1/2 00 1 −1
0 −1/2 1
×
1830
25
 ∴
 f1xA
xC
 =
 35
10

z = 30xA + 20xB + 50xC = 30× 5 + 50× 10 = 650
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Mudança no termo independente
Inicial:
xA xB xC f1 f2 f3 b
−z 30 20 50 0 0 0 0
f1 1 1 1 1 0 0 18 (hectares)
f2 2 1 2 0 1 0 30 (água)
f3 1 1 2 0 0 1 24 (fertilizante)
Final:
xA xB xC f1 f2 f3 b
−z 0 -5 0 0 -5 -20 -630
f1 0 1/2 0 1 -1/2 0 3
xA 1 0 0 0 1 -1 6
xC 0 1/2 1 0 -1/2 1 9
Se houvesse 17 hectares:
xB = B−1b ∴
 f1xA
xC
 =
1 −1/2 00 1 −1
0 −1/2 1
×
1730
24
 ∴
 f1xA
xC
 =
26
9

z = 30xA + 20xB + 50xC = 30× 6 + 50× 9 = 630
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Mudança no termo independente
Note que o aumento de 1 un. de fertilizante aumentou a
receita de 630 para 650, um aumento de 20 (exatamente o
preço dual do fertilizante)
Isso foi obtido mudando-se a quantidade cultivada de cada
cultura, porém a base permaneceu a mesma: f1, xA, xC
A diminuição de 1 hectare não alterou a receita (em
conformidade com o preço dual do hectare, 0)
A solução permanece, a única diferença é sobrar 1
hectare a menos (f1 = 2 em vez de 3)
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Mudança no termo independente
Inicial:
xA xB xC f1 f2 f3 b
−z 30 20 50 0 0 0 0
f1 1 1 1 1 0 0 18 (hectares)
f2 2 1 2 0 1 0 30 (água)
f3 1 1 2 0 0 1 24 (fertilizante)
Final:
xA xB xC f1 f2 f3 b
−z 0 -5 0 0 -5 -20 -630
f1 0 1/2 0 1 -1/2 0 3
xA 1 0 0 0 1 -1 6
xC 0 1/2 1 0 -1/2 1 9
Se houvesse 14 hectares:
xB = B−1b ∴
 f1xA
xC
 =
1 −1/2 00 1 −1
0 −1/2 1
×
1430
24
 ∴
 f1xA
xC
 =
−16
9

Inviável!
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Mudança no termo independente
Isso não quer dizer que não existe solução viável para 14
hectares!
Quer dizer que, para 14 hectares, a base xB = (f1, xA, xC)
não é viável
E a análise de sensibilidade (e preços duais) não valem
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Mudança no termo independente
Para que quantidade de hectares a base continua viável?
xB = B−1b f1xA
xC
 =
1 −1/2 00 1 −1
0 −1/2 1
×
 λ30
24

 f1xA
xC
 =
λ− 156
9

xB ≥ 0 ∴
λ− 156
9
 ≥ 0 ∴ λ ≥ 15
Para 15 hectares ou mais.
O que faz sentido, já que para 18 sobravam 3.
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Mudança no termo independente
Para que quantidade de água a base continua viável?
xB = B−1b f1xA
xC
 =
1 −1/2 00 1 −1
0 −1/2 1
×
18λ
24

 f1xA
xC
 =
 18− λ/2λ− 24
−λ/2 + 24

xB ≥ 0 ∴
 18− λ/2λ− 24
−λ/2 + 24
 ≥ 0 ∴
 λ ≤ 36λ ≥ 24
λ ≤ 48
∴ 24 ≤ λ ≤ 36
De 24 a 36 un. de água. Dentro dessa faixa vale a análise e vale o
preço dual. Fora dessa faixa de viabilidade, a base atual não é viável.
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Mudança no termo independente
Para que quantidade de fertilizante a base continua viável?
xB = B−1b f1xA
xC
 =
1 −1/2 00 1 −1
0 −1/2 1
×
1830
λ

 f1xA
xC
 =
 330− λ
−15 + λ

xB ≥ 0 ∴
 330− λ
−15 + λ
 ≥ 0 ∴ { λ ≤ 30
λ ≥ 15 ∴ 15 ≤ λ ≤ 30
De 15 a 30 un. Dentro dessa faixa vale a análise e vale o preço dual.
Fora dessa faixa de viabilidade, a base atual não é viável.
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Mudança no termo independente
Qual o impacto de cada 1 un. a mais de fertilizante?
xB = B−1b f1xA
xC
 =
1 −1/2 00 1 −1
0 −1/2 1
×
 1830
24 + λ

 f1xA
xC
 =
 36− λ
9 + λ

z = cBxB = 30(6− λ) + 50(9 + λ) = 630 + 20λ
Para cada un. adicional de fertilizante
há um aumento de 20 un. na receita (já previsto pelo preço dual)
para isso, cultivar 1 hectare a menos de A e 1 a mais de C
issovale até 6 a mais ou 9 a menos (já previsto no slide anterior)
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Mudança na função objetivo
Inicial:
xA xB xC f1 f2 f3 b
−z 30 20 50 0 0 0 0
f1 1 1 1 1 0 0 18 (hectares)
f2 2 1 2 0 1 0 30 (água)
f3 1 1 2 0 0 1 24 (fertilizante)
Final:
xA xB xC f1 f2 f3 b
−z 0 -5 0 0 -5 -20 -630
f1 0 1/2 0 1 -1/2 0 3
xA 1 0 0 0 1 -1 6
xC 0 1/2 1 0 -1/2 1 9
Por que não cultivar B? Quanto “custa” sua produção?
Note que 1 un. de B gasta 1 ha, 1 un. água, 1 un. fertilizante
Valor total dos recursos: 1× 0 + 1× 5 + 1× 20 = 25
Custo reduzido = 20 (receita) - 25 (recursos) = -5
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Mudança na função objetivo
Inicial:
xA xB xC f1 f2 f3 b
−z 30 20 50 0 0 0 0
f1 1 1 1 1 0 0 18 (hectares)
f2 2 1 2 0 1 0 30 (água)
f3 1 1 2 0 0 1 24 (fertilizante)
Final:
xA xB xC f1 f2 f3 b
−z 0 -5 0 0 -5 -20 -630
f1 0 1/2 0 1 -1/2 0 3
xA 1 0 0 0 1 -1 6
xC 0 1/2 1 0 -1/2 1 9
Por que não cultivar B? Quanto “custa” sua produção?
Note que 1 un. de B gasta 1 ha, 1 un. água, 1 un. fertilizante
Valor total dos recursos: 1× 0 + 1× 5 + 1× 20 = 25
Custo reduzido = 20 (receita) - 25 (recursos) = -5
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Mudança na função objetivo
Inicial:
xA xB xC f1 f2 f3 b
−z 30 20 50 0 0 0 0
f1 1 1 1 1 0 0 18 (hectares)
f2 2 1 2 0 1 0 30 (água)
f3 1 1 2 0 0 1 24 (fertilizante)
Final:
xA xB xC f1 f2 f3 b
−z 0 -5 0 0 -5 -20 -630
f1 0 1/2 0 1 -1/2 0 3
xA 1 0 0 0 1 -1 6
xC 0 1/2 1 0 -1/2 1 9
Por que não cultivar B? Quanto “custa” sua produção?
Note que 1 un. de B gasta 1 ha, 1 un. água, 1 un. fertilizante
Valor total dos recursos: 1× 0 + 1× 5 + 1× 20 = 25
Custo reduzido = 20 (receita) - 25 (recursos) = -5
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Mudança na função objetivo
Custo reduzido
indica a variação na função objetivo por unidade, se a
variável deixar de ser zero (entrar na base)
indica quanto seu coeficiente na função objetivo deveria
melhorar para que ela deixasse de ser zero na solução
ótima (para que compensasse na base)
atenção: só se aplica a variáveis que estão fora da base
Cálculo do custo reduzido
estão na linha z do quadro final do simplex
podem ser calculados por:
receita (coef. na FO) - recursos (consumo x preço dual)
que é dado também pela fórmula: cj = cj − cBB−1aj
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Mudança na função objetivo
Inicial:
xA xB xC f1 f2 f3 b
−z 30 20 50 0 0 0 0
f1 1 1 1 1 0 0 18 (hectares)
f2 2 1 2 0 1 0 30 (água)
f3 1 1 2 0 0 1 24 (fertilizante)
Final:
xA xB xC f1 f2 f3 b
−z 0 -5 0 0 -5 -20 -630
f1 0 1/2 0 1 -1/2 0 3
xA 1 0 0 0 1 -1 6
xC 0 1/2 1 0 -1/2 1 9
Exemplo: custo reduzido de xB:
cxB = cxB − cBB−1axB = cxB −
[
cf1 cxA cxC
]
B−1axB
= 20− [0 30 50]
1 −1/2 00 1 −1
0 −1/2 1
11
1
 = 20− [0 5 20]
11
1
 = −5
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Mudança na função objetivo
Inicial:
xA xB xC f1 f2 f3 b
−z 30 20 50 0 0 0 0
f1 1 1 1 1 0 0 18 (hectares)
f2 2 1 2 0 1 0 30 (água)
f3 1 1 2 0 0 1 24 (fertilizante)
Final:
xA xB xC f1 f2 f3 b
−z 0 -5 0 0 -5 -20 -630
f1 0 1/2 0 1 -1/2 0 3
xA 1 0 0 0 1 -1 6
xC 0 1/2 1 0 -1/2 1 9
E se a receita de B fosse 21, qual seria seu custo reduzido?
cxB = cxB − cBB−1axB = cxB −
[
cf1 cxA cxC
]
B−1axB
= 21− [0 30 50]
1 −1/2 00 1 −1
0 −1/2 1
11
1
 = 21− [0 5 20]
11
1
 = −4
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Mudança na função objetivo
Inicial:
xA xB xC f1 f2 f3 b
−z 30 20 50 0 0 0 0
f1 1 1 1 1 0 0 18 (hectares)
f2 2 1 2 0 1 0 30 (água)
f3 1 1 2 0 0 1 24 (fertilizante)
Final:
xA xB xC f1 f2 f3 b
−z 0 -5 0 0 -5 -20 -630
f1 0 1/2 0 1 -1/2 0 3
xA 1 0 0 0 1 -1 6
xC 0 1/2 1 0 -1/2 1 9
Para que receita de B seria interessante cultivá-lo ?
cxB = λ−
[
0 30 50
] 1 −1/2 00 1 −1
0 −1/2 1
11
1
 = λ− 25
Se cxB > 0, xB entra na base, logo, para λ− 25 > 0 ∴ a partir de 25
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Mudança na função objetivo
Inicial:
xA xB xC f1 f2 f3 b
−z 30 20 50 0 0 0 0
f1 1 1 1 1 0 0 18 (hectares)
f2 2 1 2 0 1 0 30 (água)
f3 1 1 2 0 0 1 24 (fertilizante)
Final:
xA xB xC f1 f2 f3 b
−z 0 -5 0 0 -5 -20 -630
f1 0 1/2 0 1 -1/2 0 3
xA 1 0 0 0 1 -1 6
xC 0 1/2 1 0 -1/2 1 9
Para que receita de A não seria interessante cultivá-lo ?
Esse cálculo é mais complicado que o anterior. Como xA está na
base, não basta calcular seu custo reduzido, pois será zero.
Deve-se calcular os custos reduzidos das variáveis que estão fora da
base, para ver quando alguma deve entrar.
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Mudança na função objetivo
Para que receita de A a base continua ótima ?
cxB = 20−
[
0 λ 50
] 1 −1/2 00 1 −1
0 −1/2 1
11
1
 = −5
cf2 = 0−
[
0 λ 50
] 1 −1/2 00 1 −1
0 −1/2 1
01
0
 = 25− λ
cf3 = 0−
[
0 λ 50
] 1 −1/2 00 1 −1
0 −1/2 1
00
1
 = λ− 50
Para 25 ≤ λ ≤ 50 todos os custos reduzidos e preços duais2
permanecem ≤ 0. Fora dessa faixa a base não é mais ótima.
2o “custo reduzido” das folgas é normalmente chamado de preço dual
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Mudança na função objetivo
Inicial:
xA xB xC f1 f2 f3 b
−z λ 20 50 0 0 0 0
f1 1 1 1 1 0 0 18 (hectares)
f2 2 1 2 0 1 0 30 (água)
f3 1 1 2 0 0 1 24 (fertilizante)
Final:
xA xB xC f1 f2 f3 b
−z 0 -5 0 0 25-λ λ - 50 -630
f1 0 1/2 0 1 -1/2 0 3
xA 1 0 0 0 1 -1 6
xC 0 1/2 1 0 -1/2 1 9
Por exemplo:
se a receita de A é < 25, cf2 > 0, e f2 entra na base
3
se a receita de A é > 50, cf3 > 0, e f3 entra na base
4
3justamente no lugar de A, pois não é mais interessante cultivá-lo
4no lugar de C, já não é mais interessante cultivá-lo
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Mudança na função objetivo
Para que receita de C a base continua ótima ?
cxB = 20−
[
0 30 λ
] 1 −1/2 00 1 −1
0 −1/2 1
11
1
 = 20− λ/2
cf2 = 0−
[
0 30 λ
] 1 −1/2 00 1 −1
0 −1/2 1
01
0
 = λ/2− 30
cf3 = 0−
[
0 30 λ
] 1 −1/2 00 1 −1
0 −1/2 1
00
1
 = 30− λ
Para 40 ≤ λ ≤ 60 todos os custos reduzidos e preços duais
permanecem ≤ 0. Fora dessa faixa a base não é mais ótima.
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Mudança na função objetivo
Inicial:
xA xB xC f1 f2 f3 b
−z 30 20 λ 0 0 0 0
f1 1 1 1 1 0 0 18 (hectares)
f2 2 1 2 0 1 0 30 (água)
f3 1 1 2 0 0 1 24 (fertilizante)
Final:
xA xB xC f1 f2 f3 b
−z 0 20− λ/2 0 0 λ/2− 30 30− λ -630
f1 0 1/2 0 1 -1/2 0 3
xA 1 0 0 0 1 -1 6
xC 0 1/2 1 0 -1/2 1 9
Por exemplo:
se a receita de C é < 40, cxB > 0, e xB entra na base
se a receita de C é > 60, cf2 > 0, e f2 entra na base
5
5no lugar de A, já não é mais interessante cultivá-lo
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Nova variável
Inicial:
xA xB xC xD f1 f2 f3 b
−z 30 20 50 65 0 0 0 0
f1 1 1 1 1 1 0 0 18 (hectares)
f2 2 1 2 2 0 1 0 30 (água)
f3 1 1 2 3 0 0 1 24 (fertilizante)
Final:
xA xB xC xD f1 f2 f3 b
−z 0 -5 0 ? 0 -5 -20 -630
f1 0 1/2 0 ? 1 -1/2 0 3
xA 1 0 0 ? 0 1 -1 6
xC 0 1/2 1 ? 0 -1/21 9
Considere a opção da cultura D
Seu preço de mercado é 65
Cada hectare gasta 2 un. de água e 3 un. de fertilizante
Cultivar ou não?
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Nova variável
Isso depende se seu custo reduzido. Se for > 0 compensa
cultivá-lo (entra na base)
cxD = 65−
[
0 30 50
] 1 −1/2 00 1 −1
0 −1/2 1
12
3
 = −5
Logo, não compensa cultivá-lo
Alternativamente:
cxD = receita - consumo de recurso ∴
cxD = 65− (1× 0 + 2× 5 + 3× 20) = −5
Note que só compensaria cultivá-lo se seu valor de mercado
fosse > 70
Análise de sensibilidade Gráfico Simplex Mudança no termo independente Mudança na função objetivo
Resumo
Mudanças no termo independente
Causam mudança nos valores das variáveis básicas
(última coluna do quadro)
O impacto pode ser avaliado pelos preços duais
A base atual pode não ser viável
A análise vale dentro de uma faixa de viabilidade
Se a base não for viável, pode-se usar o dual simplex (visto a seguir)
Mudanças nos coeficientes da FO
Causam mudança nos custos reduzidos e preços duais
(linha z do quadro)
O impacto pode ser avaliado pelos custos reduzidos
A base atual continua viável, mas pode não ser ótima
A análise vale dentro de uma faixa de otimalidade
Se a base não for ótima, pode-se continuar o simplex
	Análise de sensibilidade
	Gráfico
	Simplex
	Mudança no termo independente
	Mudança na função objetivo