Exercícios de Programação Linear com Método Simplex

Prévia do material em texto

MB-244 - PRINCÍPIOS DA PESQUISA OPERACIONAL 
LISTA DE EXERCÍCIOS 3 – MÉTODO SIMPLEX 
 
1. Considere o seguinte problema de programação linear: 
 
Maximizar x1 + 3x2 
 
S.A. x1 - 3x2  3 
 -2x1 + x2  2 
 -3x1 + 4x2  12 
 3x1 + x2  9 
 x1, x2  0 
 
a. Desenhe a região viável no espaço (x1,x2) e ache a solução ótima. 
b. Resolva o problema pelo método simplex. 
c. Suponha que a quarta restrição seja removida. Resolva o problema pelo método simplex 
e interprete a solução. 
 
2. Considere o seguinte problema de programação linear: 
 
Maximizar 5x1 + 4x2 
 
S.A. x1 + 2x2  6 
 -2x1 + x2  4 
 5x1 + 3x2  15 
 x1, x2  0 
 
a. Resolva o problema graficamente. 
b. Resolva o problema pelo método simplex. 
 
3. Considere o problema de programação linear: 
 
Maximizar 2x1 + x2 + 5x3 - 3x4 
 
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 viável com as variáveis x1, x2 e x4. Essa solução é ótima? Se não 
for, então inicie a resolução do método simplex por essa solução e encontre a solução 
ótima. 
 
4. Os tableaux inicial e corrente são mostrados abaixo. Encontre os valores das 
incógnitas a a l. 
 
Tableaux inicial 
 x1 x2 x3 x4 x5 RHS 
Z a 1 -3 0 0 0 
x4 b c d 1 0 6 
x5 -1 2 e 0 1 1 
 
 
Tableaux corrente 
 x1 x2 x3 x4 x5 RHS 
Z 0 -1/3 j k l -4 
 g 2/3 2/3 1/3 0 f 
 h i -1/3 1/3 1 3 
 
 
5. Resolva o seguinte problema de programação linear pelo método simplex e a cada 
iteração identifique B, B
-1
 e w: 
 
Maximizar 3x1 + 2x2 + x3 
 
S.A. 2x1 - 3x2 + 2x3  3 
 -x1 + x2 + x3  5 
 x1, x2, x3  0 
 
6. Considere o seguinte problema de programação linear: 
 
Maximizar x1 + 3x2 
 
S.A. x1 - 3x2  3 
 -2x1 + x2  2 
 -3x1 + 4x2  12 
 3x1 + x2  9 
 x1, x2  0 
 
Resolva o problema pelo método simplex identificando a cada iteração B, B
-1
 e w. 
 
7. A PC-Express é uma loja de computadores que vende dois tipos de microcomputadores: 
desktops e laptops. A empresa ganha R$600,00 por cada desktop vendido e R$900,00 por cada 
laptop vendido. Os computadores que a PC-Express vende são montados por outra empresa. 
Esta outra empresa tem outro pedido para atender, de forma que não poderá montar mais do que 
80 desktops e 75 laptops no próximo mês. Os funcionários da PC-Express gastam 2 horas 
instalando softwares e testando os desktops. No caso dos laptops eles gastam 3 horas. No 
próximo mês os empregados da PC-Express trabalharão 300 horas nessas atividades. A PC-
Express quer saber quantos desktops e laptops serão solicitados à empresa que faz a montagem, 
de forma a maximizar seu lucro. 
a. Formule e resolva o problema de programação linear utilizando o método simplex. 
b. Há múltiplas soluções ótimas? Se há, como é possível verificar isso no tableau?