Terceira Lista Método das Duas Fases e Dualidade

Prévia do material em texto

1) Resolva pelo método das duas fases os seguintes problemas: 
 
a) Maximizar Q(x) = 2x1 + 3x2 
 s.a. 
 x1 + x2 ≥ 10 
 2x1 + x2 ≤ 16 
x1, x2 ≥ 0 
 
b) Maximizar Q(x) = 4x1 + 3x2 
 s.a. 
 x1 + 2x2 = 10 
 6x1 + 6x2 ≤ 40 
x1, x2 ≥ 0 
 
c) Minimizar Q (x) = x1 + x2 + x3 
s.a 
-x1 + x2 >= 1 
2x1 - 2x2 - x3 = 2 
x1 ,x2, x3 >= 0 
 
 
 
 
 
 
 
 
d) Maximizar Q(x) = 5x1 + 3x2 + 2x3 + 4x4 
 s.a. 
 5x1 + 1x2 + 1x3 + 8x4 = 10 
2x1 + 4x2 + 3x3 + 2x4 = 10 
x1, x2, x3, x4 ≥ 0 
 
e) Minimizar Q(x) = x1 + 3x2 
 s.a. 
 -x1 - x2 ≥ 1 
 x1, x2 ≥ 0 
 
f) Maximizar Q (x) = x1 + 2x2 + 3x3 
s.a 
x1 - x2 >= 0 
 x2 + x3 <= 2 
-x1 + x3 = 0 
x1 ,x2, x3 >= 0 
 
 
2) Encontrar o dual dos problemas anteriores e dos seguintes: 
 
a) Minimizar Q(x) = 2x1 + 3x2 – x3 + x4 
 s.a. 
 2x1 - 3x2 + x3 - x4 ≤ 5 
x1 + 3x3 + x4 ≥ 6 
3x1 - x2 + x3 ≤ 7 
 x1, x2, x3 ≥ 0 e x4 qualquer 
 
 
 
 
 
b) Maximizar Q(x) = -2x1 + x2 – 3x3 
 s.a. 
 2x1 - 3x2 + x3 ≤ 5 
-2x1+ x2 - x3 ≥ -7 
3x1 - 2x2 - x3 ≥ 8 
 x1 - 2x2 - x3 = -7 
 x1, x2 ≥ 0 e x3 qualquer 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
UNIVERSIDADE FEDERAL DE OURO PRETO 
DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO 
 
Programação Linear 
 
Terceira Lista de Exercícios – Duas Fases, Dualidade e Análise de Sensibilidade 
Professor: Alexandre Martins 
 
3) Análise de Sensibilidade 
 
3.1) Uma determinada empresa está interessada em maximizar o lucro mensal proveniente de quatro de 
seus produtos, designados por I, II, III e IV. Para fabricar esses produtos, ela utiliza dois tipos de 
máquinas (M1 e M2) e dois tipos de mão-de-obra (MO1 e MO2), que têm as seguintes disponibilidades: 
Máquinas Disponibilidades 
(máquina-hora/mês) 
 Mão-de-obra Disponibilidade 
(homem-hora/mês) 
M1 70 MO1 120 
M2 20 MO2 160 
 
 
 
 
 
O setor técnico da empresa fornece os seguintes coeficientes, que especificam o total de horas de 
máquina e horas de mão-de-obra necessárias para a produção de uma unidade de cada produto: 
 Produtos Produtos 
Máquinas I II III IV Mão-de-obra I II III IV 
M1 5 4 8 9 MO1 2 4 2 8 
M2 2 6 0 8 MO2 7 3 0 7 
 
O setor comercial fornece as seguintes informações: 
Produtos Potencial de venda 
(unidades/mês) 
Lucro unitário 
(R$/mês) 
I 70 10 
II 60 8 
III 40 9 
IV 20 7 
 
Deseja-se planejar a produção mensal da empresa que maximize o lucro. 
 O modelo de programação matemática relativo a esse problema é: 
∑
∈Produtos
max
j
jj xL 
∑
∈
∈∀≤
Produtos
MaquinasDispMaqtmaq
j
ijij ix 
∑
∈
∈∀≤
Produtosj
MaoDeObraDispObratobra kx kjkj 
ProdutosDemanda ∈∀≤ jx jj 
Produtos∈∀Ζ∈ + jx j 
onde: 
(i) jL é o lucro unitário relativo à venda do produto j; 
(ii) jx representa a quantidade de produtos do tipo j = I, II, III, IV a ser produzida mensalmente; 
(iii) Demandaj representa a demanda mensal do produto j; 
(iv) DispMaqi representa a disponibilidade mensal de cada máquina i; 
(v) tmaqij representa o tempo gasto para produzir uma unidade do produto j na máquina i; 
(vi) DispObrak indica a disponibilidade da k-ésima mão-de-obra; 
(vii) tobrakj representa o tempo gasto para produzir uma unidade do produto j com a mão-de-obra k; 
 
 
 
 
 
 
 
 
 
 O modelo expandido aplicado aos dados do problema considerado é: 
 4321 79810max xxxx +++ 
709845 4321 ≤+++ xxxx (Restrição de tempo na máquina 1) 
208062 4321 ≤+++ xxxx (Restrição de tempo na máquina 2) 
1208242 4321 ≤+++ xxxx (Restrição de tempo com a mão-de-obra 1) 
1607037 4321 ≤+++ xxxx (Restrição de tempo com a mão-de-obra 2) 
701 ≤x (Demanda máxima para o produto I) 
602 ≤x (Demanda máxima para o produto II) 
403 ≤x (Demanda máxima para o produto III) 
204 ≤x (Demanda máxima para o produto IV) 
4,3,2,1=∀Ζ∈ + jx j 
 Considerando a relaxação linear desse problema, isto é, eliminando a integralidade da solução, 
resolva esse modelo por qualquer aplicativo de otimização e responda às seguintes questões: 
 
Modelo no LINGO: 
[qx] max = 10*x1 + 8*x2 + 9*x3 + 7*x4; 
 
[r1] 5*x1 + 4*x2 + 8*x3 + 9*x4 <= 70; 
[r2] 2*x1 + 6*x2 + 8*x4 <= 20; 
[r3] 2*x1 + 4*x2 + 2*x3 + 8*x4 <= 120; 
[r4] 7*x1 + 3*x2 + 0*x3 + 7*x4 <= 160; 
x1 <= 70; 
x2 <= 60; 
x3 <= 40; 
x4 <= 20; 
 
(a) Qual o planejamento ótimo da produção? 
(b) Qual o gargalo do sistema produtivo? Justifique. 
(c) Para qual faixa de lucro trazida pela venda do produto III as quantidades ótimas permanecem as 
mesmas? Justifique. 
(d) Qual deve ser o lucro mínimo que torna a venda do produto IV economicamente atrativa? 
Justifique. 
(e) Qual o lucro trazido por uma hora a mais de disponibilidade da máquina 1? Justifique. 
(f) A informação anterior vale para até quantas horas a mais de disponibilidade da máquina 1? 
Justifique. 
(g) Quanto vale uma hora a mais de disponibilidade da mão-de-obra 1? Justifique. 
(h) No planejamento ótimo, existe ociosidade da mão-de-obra 2? Justifique. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
3.2) Uma pequena siderúrgica recebe encomenda de um lote de lingotes de ferro que deverá totalizar 240 
toneladas de conteúdo do elemento ferro (Fe). O cliente admitirá que o lote tenha quantidades adicionais 
do elemento silício (Si), mas para cada tonelada de Si deverá haver na liga pelo menos 15 toneladas de 
Fe. A firma tem em estoque quantidade mais que suficiente: 
• Minério do tipo A, que custa R$6.000,00 cada centena de toneladas e que tem 2% de Si e 60% 
de Fe. 
• Minério do tipo B, que custa R$3.000,00 cada centena de toneladas e que tem 4% de Si e 40% 
de Fe. 
A firma tem ainda a oportunidade de usar como matéria-prima uma sucata de boa qualidade, que 
custa R$250,00 a tonelada, e que possui praticamente 100% de Fe. Pede-se: 
(a) Formule o problema de programação linear que calcula a mistura de mínimo custo para a 
produção dos lingotes encomendados; 
(b) Resolva o problema utilizando o LINGO. 
(c) De quanto varia o custo da solução para cada tonelada de ferro acrescida ao lote encomendado? 
(d) Qual o preço máximo que a sucata pode ter a fim de que seja economicamente vantajosa para a 
produção da liga? 
(e) Até quanto o custo do minério A será atrativo para permanecer na solução ótima? 
 
Modelo no LINGO: 
[Qx] min = 60*x1 + 30*x2 + 2500*x3; 
 
0.6*x1 + 0.4*x2 + x3 >= 240; 
0.3*x1 - 0.2*x2 + x3 >= 0; 
 
4) Seja o PPL: 
 
a) Minimizar Q(x) = 10x1 + 4x2 + 5x3 
 s.a. 
 5x1 - 7x2 + 3x3 ≥ 50 
 x1, x2, x3 ≥ 0 
Defina o dual. Encontre a solução ótima do dual por inspeção. Encontre a solução ótima do primal usando 
o teorema das folgas complementares. 
 
b) Minimizar Q(x) = x1+ x2 + x3 
 s.a. 
 4/5x1+ 2/5x2 + 3x3 = 108 
 3/5x2 + 9/10x3 = 120 
 x1, x2, x3 ≥0 
Seja a solução viável primal x1= 35, x2= 200 e x3= 0. Encontre a solução dual. Verifique se ela é ótima