lista4-simplex

Prévia do material em texto

Lista de Exercícios - Otimização Linear 
Profa. Maria do Socorro – DMAp/IBILCE/UNESP 
 
Método Simplex 
 
Ref.: Bazaara, M. e J.J. Javis - ‘Linear Programming and Network Flows’ - John Wiley, 1977. 
 
1) Resolva o problema abaixo pelo método simplex começando com a solução básica factível 
(x1,x2) = (4,0). 
 max -x1 + 2x2 
 s.a 3x1 + 4x2 = 12 
 2x1 - x2  12 
 x1, x2  0 
 
2) Considere o problema 
 
 max 2x1 + x2 – 3x3 + 5x4 
 s.a x1 + 2x2 + 4x3 - x4  6 
 2x1 + 3x2 - x3 + x4  12 
 x1 + x3 + x4  4 
 x1, x2, x3, x4  0 
 
Encontre a solução básica factível onde as variáveis x1, x2 e x4 são básicas. Esta solução é ótima? 
Senão encontre a solução ótima partindo desta solução. 
 
 
3) Resolva os problemas abaixo pelo método simplex. 
 
a) 
Min zxx  212 
s.a. 93 21  xx 
 322 21  xx 
and 80,10 21  xx 
 
b) 
Min zxxxxx  54321 322 
s.a 022 54321  xxxxx 
 
5,...,1,0
0
022
54321
54321



jx
xxxxx
xxxxx
j
 
 
c) 
Max z 1x 
s.a 
2043 4321  xxxx 
4,...1,0
037
52
421
31



jx
xxx
xx
j
 
 
d) 
02,1
121
62312
.
3min 21




xx
xx
xx
as
xxz
 
 
e) 
02,1
121
4221
.
2412max




xx
xx
xx
as
xxz
 
f) 
02,1
321
4221
.
231max




xx
xx
xx
as
xxz
 
4) Verifique usando o método simplex que o problema abaixo é ilimitado. Escreva a classe de 
soluções viáveis que fazem com que: 
as
xxxx
.
321 = zMin 4321  
102 4321  xxxx 
4,...,1,0
302443
20225
4321
4321



jx
xxxx
xxxx
j
 
5) - Considere o seguinte problema: 
 Min zxxxx  4321 52 
 s.a. 44321  xxxx 
 
4,...,1,0
252
52432
4321
4321



jx
xxxx
xxxx
j
. 
Mostre, usando o método simplex que o problema é infactível. 
 
4- Use o método simplex para verificar se o sistema de inequações abaixo é compatível. 
 
4,...,1,0
9235
45444
44
4321
4321
431




jx
xxxx
xxxx
xxx
j
 
 
6) Considere o problema: 
Min zxxxx  4321 1232 
s.a 
0992 4321  xxxx 
0,0,0,0
02
4321
433
1
213
1


xxxx
xxxx
 
acrescente as variáveis de folga 5x 6x , e as use como solução básica inicial. 
a) Resolva o problema pelo método simplex considerando que: 
i - a variável candidata a entrar na base é a variável não básica como menor custo relativo 
ii - a variável que sai da base é a variável básica com menor índice 𝑙 = 𝑖 satisfazendo 






 miy
y
x
l i
i
B
i
,..1,0,
ˆ
min 
 o que acontece? 
b) Resolva o problema usando a regra de Bland para mostrar que o algoritmo converge. 
c) Resolva o problema usando um dado para tomar as suas decisões em caso de empate e mostre 
que o algoritmo converge. 
 
 
 
7) Considere o problema: 
 Max 21 xxz  
 s.a 121  xx 
 
0,0
32
3
21
21
21



xx
xx
xx
 
a) Desenhe a região factível 
b) Resolva o problema graficamente 
c) Mostre graficamente que a solução ótima é degenerada 
d) mostre na figura que restrição pode ser retirada do problema para obter uma solução ótima nào 
degenerada. 
 
8) Considere o seguinte problema de programação linear: 
 𝑚𝑎𝑥 321 32 xxxz  
 s.a 
62 321  xxx 
3,...,1,0
42 31


jx
xx
j
 
 
a)Resolva pelo método simplex. 
b) Multiplique a segunda equação por 2 e resolva o problema novamente. Qual é o efeito desta 
multiplicação nos valores da variáveis duais? Qual é o efeito no valor ótimo da função objetivo? 
 
9) Considere o seguinte problema de programação linear: 
 Min 321 3 xxxz  
 s.a 
 
3,...,1,0
2
62
321
321



jx
xxx
xxx
j
 
a)Resolva pelo método simplex. 
b)Troque o sinal da primeira restrição para ' <=' e resolva o problema novamente. 
 
10) Resolva o problema pelo método simplex revisado: 
 min 4321 8429 xxxxz  
 s.a 
 
4,...,1,0
103
2032
4321
4321



jx
xxxx
xxxx
j
 
a) mostre que o problema possui infinitas soluções 
b) encontre todas as soluções básicas viáveis ótimas 
 
 
11) Resolve o problema abaixo pelo método simplex. Desenhe a região factível e mostre no gráfico 
a solução visitada a cada iteração. 
 
.0,0
523
42
.
min
21
21
21
21




xx
xx
xx
as
xxz
 
12) Mostre que o seguinte problema é infactível. 
 
0,0,0
1
6
54
.
332min
321
1
321
321
321





xxx
x
xxx
xxx
as
xxxz
 
 
13) Vimos que a maior parte do esforço computacional do método simplex é dedicado ao cálculo 
dos custos relativos, j
t
jj Acc ˆ , das variáveis não básicas. Suponha que ao invés de usar a regra: 
}ˆ{minˆ j
j
k cc  para escolher a variável não básica candidata a entrar na base, simplesmente 
escolhemos a primeira variável que tiver 0ˆ  j
t
jj Acc  . Isto poderia eliminar o cálculo de um 
grande número de custos relativos. Discute as vantagens e desvantagens desta regra. 
 
14) O objetivo deste exercício é examinar o que acontece com a solução ótima do problema 
quando pequenas modificações no mesmo ocorrem. Considere o problema: 
 
Min zxxxx  4321 1234 
s.a 
10232 4321  xxxx 
4,...1,0
163241 4321


jx
xxxx
j
 
a) Resolva o problema usando um software. Anote a solução obtida 
b) mude o custo de 𝑥4 para 4 e reotimize o problema. Mude para 8 e reotimize. Como a soluçào 
ótima do problema variou em cada caso? 
c) mude o coeficiente de 𝑥2 na segunda equação para 𝑎22 = 5 e reotimize. O que muda na soluçào 
do problema? 
d) Faça as seguintes modificações no valor do lado direito da primeira restrição: 
 mude de b1 = 10 para b1 = 8 e reotimize. 
 mude de b1 = 10 para b1 = 12 e reotimize 
 mude de b1 = 10 para b1 = 20 e reotimize 
examine a nova solução em cada caso. 
e) Acrescente uma nova atividade (𝑥5) ao problema com os seguintes dados: 
c5 = -1 
a15 = 2, a25 = -3. 
Reotimize o problema. Como voce poderia ter previsto esta nova solução analisando a solução do 
problema original? 
f) Acrescente individualmente cada uma das restrições abaixo e analise as mudanças na solução 
ótima. 
6
8422
4
4321
4321
4321



xxxx
xxxx
xxxx