Faculdade de Engenharia “Eng. Celso Daniel”
Engenharia de Produção
Pesquisa Operacional II
Profa. Dra. Lílian Kátia de Oliveira
2a. lista de exercícios
1. Resolva pelo método simplex. Escreva o valor de todas as variáveis, indicando quais são básicas e quais são
não-básicas, no quadro final e o valor de z.
a.
Minimizar z = 3x1 + 2 x2
Minimizar z = 2 x1 + 4 x2 + 5 x3
⎧ 2x1 + x2 ≥ 10
⎪
sujeito a ⎨ x1 + 5 x2 ≥ 15
⎪x , x ≥ 0
⎩ 1 2
⎧ x1 + 2 x2 + 10 x3 ≤ 600
⎪ x − x + x ≥ 50
d.
⎪ 1 2 3
sujeito a ⎨
⎪2 x1 − x3 ≤ 100
⎪⎩ x1 , x2 , x3 ≥ 0
Maximizar z = x1 + x2 + 2 x3
b.
Minimizar z = 3 x1 + 2 x2 + x3
⎧ x1 + 2 x2 ≤ 10
⎪
sujeito a ⎨3 x1 + 4 x2 + x3 ≤ 20
⎪ x ≥ 0 , x livre, x ≥ 0
2
3
⎩ 1
⎧3 x1 + x2 + 3 x3 ≥ 6
⎪3 x + 2 x = 6
e.
⎪ 1
2
sujeito a ⎨
⎪ x1 − x2 ≤ 1
⎪⎩ x1 , x2 , x3 ≥ 0
Minimizar z = 2 x1 + 4 x2 + 10 x3
c.
⎧ x1 + x2 + x3 ≤ 120
⎪
sujeito a ⎨ x1 + 2 x2 + 5 x3 ≥ 30
⎪x , x , x ≥ 0
⎩ 1 2 3
2. Verifique se a solução do modelo abaixo é ilimitada. Qual a melhor solução básica antes que a solução fique
ilimitada?
Maximizar z = x1 + 2 x2 + x3
⎧2 x1 + 3 x2 + x3 ≥ 10
⎪
sujeito a ⎨4 x1 + x2 + 2 x3 ≥ 20
⎪x , x , x ≥ 0
⎩ 1 2 3
3. Uma empresa que faz três produtos e tem três máquinas disponíveis como recursos, constrói o seguinte
problema de programação linear:
Maximizar lucro = 4 x1 + 4 x2 + 7 x3
(horas na máquina 1)
⎧ x1 + 7 x2 + 4 x3 ≤ 100
⎪2 x + x + 7 x ≤ 100
(horas na máquina 2)
⎪ 1 2
3
sujeito a ⎨
(horas na máquina 3)
⎪8 x1 + 4 x2 + x3 ≤ 100
⎪⎩ x1 , x2 , x3 ≥ 0
Resolva o modelo pelo método simplex e responda às questões:
a. antes da terceira iteração do método simplex, quais máquinas permanecem com tempo disponível?
1
b. quando a solução final é encontrada, existe algum tempo disponível em qualquer uma das três
máquinas?
4. Considere o seguinte quadro:
x1
x4
x7
z
a.
b.
c.
d.
0
1
0
0
x1
-7
-2
7
0
x2
-3
2
3
1
x3
0
0
1
0
x4
0
-1
4
3
x5
3
2
0
-3
x6
0
0
0
1
x7
50
10
7
3
b
Qual a variável candidata a entrar na base? Por quê?
Alguma outra variável poderá entrar na base? Qual ou quais e por quê?
Existe alguma variável (escreva qual, se existir) que ao entrar na base não altera o valor de z? Por quê?
Se a variável x2 entrar na base qual o valor máximo que a mesma poderá assumir e por quê?
5. Um distribuidor de produtos para festas infantis compra dos produtores chapéus de papel, línguas-de-sogra e
bexigas, e prepara caixas com esses três produtos na forma de kits para festas. Observações anteriores
mostram:
a. a quantidade de chapéus e línguas-de-sogra deve ser pelo menos 50% do total;
b. o pacote deve ter pelo menos 20 bexigas
c. cada item deve concorrer com pelo menos 25% do total da caixa.
O custo dos componentes (em milhares de unidades) é:
- chapéu de papel: 50.000
- língua-de-sogra: 20.000
- bexigas: 5.000
Qual a composição da caixa que tem o menor custo?
6. Reduza os seguintes problemas de programação lineares à forma padrão:
a.
Max z = 6 x1 − 2 x2
Max z = 5 x1 + 2 x2
⎧ x1 − x2 ≤ 1
⎪
sujeito a ⎨3x1 − x 2 ≤ 6
⎪ x ≥ 0, x livre
2
⎩ 1
⎧6 x1 + 5 x2 ≥ 6
⎪4x + 3x ≥ 12
⎪
2
sujeito a ⎨ 1
⎪ x1 + 2 x2 ≥ −4
⎪⎩ x1 livre, x2 ≥ 0
c.
Min z = x1 − 2 x2 + 4 x3 − 5 x4
b.
Min z = x1 + 2 x2 + 3 x3
⎧ x1 + 2 x2 − x3 ≥ 10
⎪2
⎪ x1 − x2 + 4 x3 − x4 ≤ -5
sujeito a ⎨
⎪ x1 + 5 x2 − 3 x4 = 7
⎪⎩ x1 ≥ 0, x2 ≥ 0, x4 ≥ 0, x3 livre
d.
2
⎧3 x1 + 4 x3 ≤ 5
⎪5 x + x + 6 x = 7
⎪ 1 2
3
sujeito a ⎨
⎪8 x1 + 9 x3 ≥ −5
⎪⎩ x1 ≥ 0, x2 ≥ 0, x3 ≥ 0