Lista 6

Prévia do material em texto

TEP117 – PESQUISA OPERACIONAL I Prof. Eduardo Uchoa 
LISTA DE EXERCÍCIOS 6 
 
As letras A e B em negrito são o penúltimo e o último dígito da sua matrícula, 
respectivamente. Por exemplo, se sua matrícula for 21042139, A representa o número 3, 
Bx1 representa 9x1, etc. 
 
1. [2.5] Uma construtora precisa produzir 80 toneladas de concreto em um certo dia. 
Para isso ela precisa alugar máquinas. Existem 6 máquinas disponíveis para aluguel. A 
tabela abaixo mostra o valor diário do aluguel, a capacidade da máquina e custo por 
tonelada produzida para cada máquina. Note que não é necessário usar toda a 
capacidade de uma máquina. Formule o problema de determinar quais máquinas devem 
ser alugadas para minimizar o custo total. Ache a solução ótima usando um pacote 
computacional (como o UFFLP). 
 
Máquina Aluguel ($) Custo ($/ton) Capacidade (ton) 
1 20000 1200 20+A 
2 18000 1400 22+B 
3 17000 1500 30-B 
4 16000 1600 33 
5 15700 1400 21 
6 15500 1600 23 
 
 
2. [5.0] Resolva os PIs pelo método branch-and-bound, mostrando a árvore de 
enumeração em detalhes. Cada PL pode ser resolvido por um pacote computacional. 
 
a) 
1 2 3 4
1 2 3 4
1 2 3 4
1 3 4
Min z 10 (10 ) (40 ) 14
S. a
5 10 15 9 16
3 8 12 4 17
2 3 3
0
 inteiro
x x x x
x x x x
x x x x
x x x
x
x
= + + + − +
+ + + ≥
+ + + ≥
+ + ≥
≥
B A
 
 
b) 
1 2 3
1 2 3
1 2
Max z 2 5
S. a
2 3 10
2 3 7
0
 inteiro
x x x
x x x
x x
x
x
= + −
+ + = +
+ ≤
≥
A
B
 
 
 
3. [2.5] Resolva graficamente e também pelo branch-and-bound: 
 
1 2
1 2
1 2
1 2
1 2
1 2
Max z 2
S. a
10 6 30
5 3 20
4 2 25
, 0
, inteiros
x x
x x
x x
x x
x x
x x
= +
+ ≤ −
+ ≤ −
+ ≤ − −
≥
B
A
A B