Lista Dual Simplex e Análise de Sensibilidade 2

Prévia do material em texto

Lista de Exercícios – Programação Linear 
Análise de Sensibilidade e Dualidade Simplex 
 
 
1. Dado o problema 
Min -3x1 - 5x2 
s.a 2x1 + 4x2 <= 10 
 5x1 + 2x2 <= 12 
 x1, x2 >= 0 
Sabe-se que a solução ótima z* = -107 / 8, x1* = 7 / 4, x2* = 13/ 8 é dada no quadro 
abaixo onde x3* = x4* = 0 são as variáveis de folga associadas às restrições (1) e (2) 
respectivamente. 
 
 Z x1 x2 x3 x4 RHS 
z 1 0 0 -19/16 -1/8 -107/8 
x1 0 1 0 -1/8 ¼ 7/4 
x2 0 0 1 5/16 -1/8 13/8 
 
Pede-se: 
a) Se a função objetivo passar a Z = -3x1 - 2x2 , a solução continua ótima? 
b) Se a função objetivo passar a Z = -3x1 - x2 , a solução continua ótima? No caso de 
resposta negativa determine a nova solução ótima 
c) Formular o dual e obter a solução dual ótima 
d) Qual a solução dual ótima no caso em que a função objetivo primal for Z = -3x1 - x2 ? 
e) Supor que o vetor b seja alterado para [14 5]T. Como ficaria a solução ótima? 
f) Supor que o vetor b seja alterado para [4 5]T. Como ficaria a solução ótima? 
g) Supor que a restrição x1 ≤ 1 seja incorporada ao problema. Qual a solução ótima 
resultante? 
 
2. Seja o problema 
Min z = -7x1 - 9x2 
s.a - x1 + x2 + x3 = 2 
 3 x1 + 5 x2 + x4 = 15 
 5 x1 + 4 x2 + x5 = 20 
 xj > = 0 (j=1, ..., 5) 
Sabe-se que a solução ótima é 
z* = -415 /13, x1* = 40 /13, x2* = 15 /13. x3* = 51/13 e x4* = x5* = 0 
com a tabela dada por 
 Z x1 x2 x3 x4 x5 RHS 
z 1 0 0 0 -17/13 -8/13 -415/13 
x2 0 0 1 0 5/13 -3/13 15/13 
x1 0 1 0 0 -4/13 5/13 40/13 
x3 0 0 0 1 -9/13 8/13 51/13 
 
Pede-se: 
a) Qual conjunto de vetores que forma a base qual a sua inversa? 
b) Formular o dual e obter a solução dual ótima. 
c) Supor que o vetor b seja alterado para [2 13 13]T como ficaria a solução ótima? 
d) Suponha que uma nova atividade x6 seja considerada, com valor na função objetiva c6 
= -1 e componentes a6 = ( -2, 2,1) nas três restrições. Verificar o efeito dessa nova 
atividade na solução. 
 
 
3. Considere o seguinte problema de programação linear: 
min z = x1 - 3 x2 + 2 x3 
s.a 3 x1 – x2 + 2 x3 <= 7 (recurso A) 
 - 2 x1 + 4 x2 <= 12 (recurso B) 
 4 x1 + 3 x2 + 8 x3 <= 10 (recurso C) 
 x1, x2, x3 >= 0 
cujo quadro ótimo é dado por 
 Z x1 x2 x3 x4 x5 x6 RHS 
z 1 0 0 -12/5 -1/5 -4/5 0 -11 
x1 0 1 0 4/5 2/5 1/10 0 4 
x2 0 0 1 2/5 1/5 3/10 0 5 
x6 0 0 0 10 1 -1/2 1 11 
 
Pede-se: 
a) Formular o dual e obter a sua solução ótima com essas informações. 
b) Sendo Z um lucro expresso em $, qual seria a contribuição para esse lucro, se mais 
uma unidade do recurso A estivesse disponível? Responder a mesma pergunta para os 
recursos B e C. 
c) Verificar se a solução atual continuaria ótima para função objetivo Z = x1 - 3x2 + x3 . 
d) Verificar se a solução atual continuaria ótima para função objetivo Z = x1 - 2x2 + 2x3 
e) Que vetores formam a base e qual a sua inversa? 
f) Se os recursos disponíveis A, B e C passarem a 5, 15 e 10 respectivamente, como fica 
a solução ótima? 
 
4. Considere o seguinte problema de programação linear 
min z = -3x1 - 2x2 - 5x3 
s.a 2x1 + 2x2 + 4x3 < = 10 
 5 x1 + 6x2 + 2x3 <= 12 
 x1, x2, x3 >= 0 
 
Colocando as variáveis de folga x4 e x5 obtém-se a seguinte solução ótima: 
 Z x1 x2 x3 x4 x5 RHS 
z 1 0 -37/16 0 -19/16 -1/8 107/8 
x3 0 0 3/16 1 5/16 -1/8 13/8 
x1 0 1 9/8 0 -1/8 1/4 7/4 
 
Deseja-se saber para que intervalos de c1, c2 e c3 (coeficientes de x1, x2 e x3, 
respectivamente) a solução acima continuará ótima? Fazer a análise de cada coeficiente 
separadamente.