Lista Dual Simplex e Análise de Sensibilidade

Prévia do material em texto

LISTA DE PROGRAMAÇÃO LINEAR – DUAL SIMPLEX E ANÁLISE DE SENSIBILIDADE 
 
Questão 1 – Escreva o dual dos problemas abaixo: 
 
Aplique o algoritmo simplex ao PL 
 min – x1 - 3 x2 
 s.a 2 x1 + x2 + x3 <= 8 
 4 x2 + 2 x3 <= 16 
 x3 <= 4 
 - x1 + x2 <= 3 
 - x1 + x3 <= 3 
 x1, x2, x3 >= 0 
determinando a solução ótima. Suponha alterado o termo independente b, de forma que para a 
mesma base B, os valores de x sejam x1 = 2, x2 = 4, x6 = 4, x7 = -1, x8 = -5, x3 = x4 = x5 = 0. 
Diga qual é o efeito que esse novo b acarreta na solução, e aplique o método dual simplex para 
alcançar a nova solução. 
 
 
Questão 2 – Considere o PL 
min x1 + 2 x2 + 5 x3 
 s.a x1 + x2 + x3 >= 5 
 2 x1 + 3 x2 + x3 >= 10 
 x1, x2, x3 >= 0 
(a) Resolva pelo dual simplex. Discuta que tipo de solução possui o problema. 
(b) Formule o dual do problema acima e encontre a solução ótima pelo quadro encontrado no 
item (a). 
(c) Resolva graficamente o dual e justifique o tipo de solução encontrada pelas equações KKT. 
(d) Proponha mudanças em: vetor c, vetor b, e na matriz A do problema. Em cada caso, 
verifique se há necessidade de encontrar novo ótimo, utilizando o algoritmo conveniente. 
 
Questão 3 – Considere o PL abaixo 
 
 min 10 x1 + 11 x2 
 s.a 10 x1 + 20 x2 >= 100 
 x1, x2 >= 0 
 
(a) Resolva pelo método da duas fases. 
(b) Escreva o dual do problema acima e retire, do quadro ótimo do simplex a solução ótima do 
dual. 
(c) Troque o vetor b para b = [51 101]T. Utilize o algoritmo dual simplex para encontrar a 
solução ótima do primal com o vetor b modificado. 
 
Questão 4 – Diga se Falso ou Verdadeiro. Justifique. 
 
(a) Considere x* = B-1 b a solução ótima de um PL. Fazendo uma alteração no vetor b para b’, 
podemos substituir no quadro ótimo do simplex o novo b (com as devidas atualizações no 
quadro). Em seguida, aplica-se o algoritmo simplex primal. 
(b) Considere x* = B-1 b a solução ótima de um PL. Introduzindo novas restrições, basta 
inserirmos tais restrições no quadro ótimo do simplex, sem qualquer preocupação de 
atualização. Em seguida, aplica-se o algoritmo dual-simplex. 
(c) B-1 b >= 0 é a condição de viabilidade do primal 
(d) cj – zj >= 0 é a condição de viabilidade do dual. 
(e) Restrições de igualdade no PL primal geram a respectiva variável dual irrestrita. 
(f) Considere um PL primal que tem solução ilimitada. Então, a função objetivo do dual 
também é ilimitada, dentro de sua região viável. 
(g) Se o conjunto de soluções viáveis de um dos problemas do par de problemas duais for 
vazio, então o conjunto de soluções viáveis do outro problema também o é. 
 
 
Questão 5 – Dado o modelo de Programação Linear 
 Maximizar 31 X4X2Z += 
sujeito a:







≥
≤+
≤
≤++
0X,X,X
620XX
6000X2
8000XX2X
321
32
1
321
 
 pede-se: 
1) os intervalos ótimos para os coeficientes de lucro da função-objetivo c1, c2, c3. Determine 
também o intervalo para o lucro (valor de Z) de acordo com o intervalo ótimo dos coeficientes 
de lucro. 
2) os intervalos ótimos para os termos independentes (valores dos recursos) b1, b2, b3. 
Determine também o intervalo para o lucro (valor de Z) de acordo com o intervalo ótimo dos 
termos independentes. 
3) o intervalo ótimo para o coeficiente tecnológico a21. Determine também o intervalo para o 
lucro (valor de Z) de acordo com o intervalo ótimo do coeficiente tecnológico. 
 
Questão 6 – Suponha que um problema de produção tenha como modelo: 
Max 321 X3X3.0XZ ++= 
sujeito a:






≥
≤−+
≤++
≤++
0X,X,X
9XX3X
12X4XX2
10XXX
321
321
321
321
 
e que o quadro final de solução pelo Simplex seja (minimização) 
 Z X1 X2 X3 u1 u2 u3 b 
z 1 -0.5 -0.45 0 0 -0.75 0 -9 
RHS 
X3 0 0.5 0.25 1 0 0.25 0 3 
u3 0 1.5 3.25 0 0 0.25 1 12 
u1 0 0.5 0.75 0 1 -0.25 0 7 
 
onde xi são as decisões de fabricação dos produtos Pi e ui as sobras dos recursos Ri no programa 
(ou seja, são as variáveis de folga, ou quanto vai sobrar de cada material Ri). O objetivo é 
maximizar o lucro devido a produção e comercialização dos produtos. 
PS: No caso de alunos que estejam familiarizados com minimização, basta adotar a função 
objetivo como: Min –x1 –0.3 x2 – 3 x3, e conseqüentemente a linha z do quadro ótimo (cj-zj) 
acima teria seus valores com sinais trocados, ou seja, 0.5, 045, 0, 0, 0.75, e 0. 
 
Pergunta-se: 
1) Qual a solução mostrada no quadro ? 
2) Quais os recursos escassos ? 
3) O que ocorreria com o objetivo se por um motivo de força maior tivéssemos que fabricar 
uma unidade de P1 ? 
4) Se alguém quisesse adquirir uma unidade do recurso R1, você estaria disposto a vender ? 
Qual o preço que compensa a venda ? 
5) Se alguém insistir em comprar uma unidade do recurso R2, que preço de venda 
compensaria o fato de ele ser escasso ? 
6) Construa o modelo dual do problema. 
7) Qual a solução dual ? 
8) O que significa a variável dual w1 ? 
9) O que mede a função objetivo dual ? 
10) Quanto você pagaria por uma unidade adicional do recurso R2 ? Por quê ? 
 
Questão 7 – Considere o seguinte problema de programação linear 
Max –x1 + 2 x2 
sujeito a: 3x1 + 4x2 ≤ 12 
 2x1-x2 ≥ 2 
 x1, x2 ≥ 0 
1) Resolva o problema gradicamente. Resposta: x* = (20/11; 18/11) e z* = 16/11 
2) Formule o problema dual e resolva-o graficamente. Resposta: (3/11; -10/11) e 
z*=16/11. 
3) Utilize as propriedades da dualidade para obter os valores das variáveis primais a partir 
da solução ótima do problema dual. 
 
Questão 8 – Considere o PPL 
Min 20x1 + 5 x2 
sujeito a: x1 + 2x2 ≥ 40 
 3x1+2x2 ≥ 60 
 x1, x2 ≥ 0 
1) Resolva-0 utilizando o algoritmo dual simplex. Resposta: x* = (0; 30; 20; 0) e z* = 150. 
2) Verifique o teorema dos desvios complementares. 
3) Indique, justificando, que outro algoritmo poderia utilizar na sua resolução. 
 
Questão 9 – Resolva o seguinte PPL utilizando o dual simplex aplicado ao problema dual de 
Max 3x1 + x2 + 4x3 
sujeito a: 6x1 + 3x2 + 5 x3 ≤ 25 
 3x1+ 4x2 + 5x3 ≤ 20 
 x1, x2 , x3≥ 0 
Resposta: Sol. Primal = (5/3; 0; 3; 0; 0)T; Sol. Dual = (1/5; 3/5; 0; 2; 0)T; Imagem = 17.