Buscar

P2 - OC - 2014-2 - Gabarito

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

UERJ – Universidade do Estado do Rio de Janeiro 
Instituto de Matemática e Estatística. Departamento de Matemática Aplicada 
Disciplina: Otimização Combinatória. Professor: Marcos Roboredo 
2014 – 2 (Prova 2 - Gabarito) 
 
1) (1,5 pontos) Resolva o PLI abaixo através do método branch-and-bound: 
 
 
 
 
 
 
Solução: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
𝑧 9 
PL 1 
𝑥 
 
 
, 
𝑥 0 
𝑧 
 5
 
 
PL 2 
𝑥 , 𝑥 
 
 
 
PL 3 
Inviável 
𝑥 𝑥 ≥ 
𝑧 
PL 4 
𝑥 , 𝑥 1 
𝑧 
PL 5 
𝑥 
5
 
, 𝑥 
𝑥 𝑥 ≥ 
𝑧 
 
 
 
PL 6 
𝑥 0, 
𝑥 
 
 
 
PL 7 
Inviável 
𝑥 0 𝑥 ≥ 
𝑧 
PL 8 
𝑥 0, 
𝑥 
PL 9 
Inviável 
𝑥 𝑥 ≥ 
2) (1 ponto ) Uma confeitaria pode produzir dois tipos de sorvete em lata: chocolate e creme. Cada 
lata do sorvete de chocolate é vendido com um lucro de $3 e as latas de creme com um lucro de $1. 
Contratos com várias lojas impõem que sejam produzidas no mínimo 10 latas de sorvete de 
chocolate por dia e que o total de latas fabricadas por dia nunca seja menor que 20. O mercado só 
é capaz de consumir até 40 latas de sorvete de creme e 60 de chocolate. As máquinas de 
preparação do sorvete disponibilizam 180 horas de operação por dia, sendo que cada lata de 
sorvete de chocolate consome 2 horas de trabalho e cada lata de creme, 3 horas. Faça um modelo 
PLI que determina o esquema de produção, maximizando os lucros com a venda de latas de 
sorvete. 
 
Solução: 
 
 nº de latas de sorvete de chocolate produzidas. 
 nº de latas de sorvete de creme produzidas. 
 
 
s.a. 
 0 
 0 
 ≥ 0 
 ≥ 0 
 0 
 
 
 
 
3) (1,5 pontos) Considere mochilas, todas com uma mesma capacidade . Considere também 
 itens que deverão ser colocados em alguma das mochilas. Cada item possui um peso que será 
denotado por . Deseja-se saber qual o número mínimo de mochilas, de modo que todos os itens 
sejam colocados em alguma das mochilas. Faça um modelo PLI para o problema. 
 
Solução: 
 
 {
 
0 
 
 
 {
 
0 
 
 
 
 ∑ 
 
 
 
s.a. 
 ∑ 
 
 
 { } 
 ∑ 
 
 
 { } 
 {0 } { } 
 {0 } { }

Outros materiais