P1 - OC - 2014-2

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 1) 
 
Nome: 
 
Data: 
1) (1 ponto) Encontre a forma canônica do PPL abaixo: 
 
 
 
 
 
 
 
2) (4,5 pontos) A Brinquedos S.A. fabrica dois tipos de brinquedos de madeira: soldados e trens. O 
lucro da venda de um soldado é R$ 3 enquanto o lucro da venda de um trem é R$2. A fabricação 
requer dois tipos de mão de obra: carpinteiro e pintor. A fabricação de um soldado requer duas 
horas de pintura e 1 hora de carpinteiro. Um trem demanda 1 hora de pintura e 1 hora de 
carpintaria. Para cada semana, a empresa consegue fazer 100 horas de pintura e 80 horas de 
carpintaria. A demanda para os trens é ilimitada mas a de soldados é no máximo 40 por semana. 
 
(a) (1 ponto) Faça um modelo de programação linear que decida quantos trens e soldados devem 
ser fabricados em uma semana que maximize o lucro da empresa. 
(b) (0,5 ponto) Desenhe um gráfico ilustrando o conjunto de soluções viáveis do problema anterior. 
(c) (0,5 ponto) De acordo com o método gráfico, qual é a solução ótima do problema? 
(d) (1 ponto) Resolva o modelo do item (a) utilizando o método simplex. 
(e) (0,5 ponto) Foi oferecido a empresa um aumento nas horas máximas semanais de pintura a um 
custo de R$ 0,50 por hora. A empresa deve aceitar? Justifique. 
(f) (0,5 ponto) Caso a demanda máxima de soldados aumente para 42, a solução ótima mudará? 
Justifique 
(g) (0,5 ponto) Caso a empresa conseguisse aumentar a disponibilidade de pintura de 100 para 101 
horas e a disponibilidade de carpintaria de 80 para 81 horas, quantos soldados e quantos trens 
seriam fabricados na solução ótima? 
 
3) (3, 5 pontos) Resolva o PPL abaixo através do método das duas fases: 
 
 
 
 
 
4) (1,5 pontos) Considere a seguinte iteração do método simplex para um problema de programação 
linear de maximização: 
Base z x1 x2 s1 s2 sol. 
z 1 0 0 2 0 32 
x1 0 1 1/2 1/4 0 4 
S2 0 0 1/2 - 1/4 1 2 
a) (0,5 ponto) Categorize as variáveis como básicas ou não básicas e dê os valores atuais de todas as 
variáveis. 
b) (0,5 ponto) Esta solução é ótima? Justifique. 
c) (0,5 ponto) Podemos afirmar que este problema tem mais de uma solução ótima? Justifique.