Exercícios de Pesquisa Operacional

Prévia do material em texto

MB-244 - PRINCÍPIOS DA PESQUISA OPERACIONAL 
LISTA DE EXERCÍCIOS 6 – O PROBLEMA DUAL, ALGORITMOS SIMPLEX 
ADICIONAIS E ANÁLISE PÓS-OTIMIZAÇÃO 
 
1. Uma empresa de manufatura produz dois tipos de cadeira reclinável. Há duas etapas 
no processo de fabricação das cadeiras – montagem e acabamento. Uma unidade da 
cadeira “top” de linha requer 3/2 horas na montagem, 1 hora no acabamento e é vendida 
gerando lucro de R$ 20,00. Uma unidade da cadeira mais simples requer ½ hora na 
montagem e ½ hora no acabamento e é vendida gerando lucro de R$ 12,00. A 
disponibilidade atual é de 100 horas para montagem e 80 horas para acabamento. A 
empresa está envolvida em negociações com o sindicato em relação a modificações 
salariais para o próximo ano e pediram que você determinasse (quantificasse) o valor da 
hora de montagem e de acabamento. 
 
2. Giapetto Woodcarving, Inc fabrica dois tipos de brinquedos de madeira: soldados e 
trens. Um soldado é vendido por $27 e usa $10 de matéria-prima. Cada soldado 
fabricado incrementa os custos variáveis de trabalho e "overhead" por $14. Um trem é 
vendido por $21 e usa $9 de matéria-prima. Cada trem produzido incrementa os custos 
variáveis de trabalho e "overhead" por $10. 
 A fabricação de soldados de madeira e de trens requer dois tipos de trabalho 
qualificado: carpintaria e acabamento. Um soldado requer 02 horas de trabalho de 
acabamento e 01 hora de trabalho de carpintaria. Um trem requer 01 hora de trabalho de 
acabamento e 01 hora de trabalho de carpintaria. A cada semana, Giapetto pode obter 
toda a matéria prima necessária, mas dispõe de somente 100 horas de trabalho de 
acabamento e 80 horas de trabalho de carpintaria. A demanda para os trens é ilimitada, 
mas no máximo 40 soldados são vendidos a cada semana. Giapetto deseja maximizar 
seu lucro semanal (faturamento menos custos). 
 
Temos a seguinte formulação: 
 
2,10
40
80
1002
..
23
1
21
21
21





ix
x
xx
xx
as
xxZMax
i
 
 
a) Encontre o Dual do problema do Giapetto 
b) Encontre a solução dos problemas Primal e Dual e compare os resultados. 
c) Encontre a relação das soluções primal e dual. 
 
3. Solucione o problema de programação linear que se segue com auxílio das relações 
expressas pela dualidade (dica: quando o problema tem apenas 2 variáveis de decisão é 
possível resolvê-lo pelo método gráfico). 
 
3,2,1,0
12
12
..
42
321
321
321




ix
xxx
xxx
as
xxxZMin
i
 
 
4. Solucione o problema de programação linear que se segue com auxílio das relações 
expressas pela dualidade (dica: quando o problema tem apenas 2 variáveis de decisão é 
possível resolvê-lo pelo método gráfico). 
 
Maximizar Z = 2x1 + 3x2 + 6x3 + 8x4 
 
S.A. x1 + 2x2 + 3x3 + x4  3 
 -2x1 + x2 - x3 + 3x4  -4 
 x1, x2, x3, x4  0 
 
5. Demonstre o teorema fraco da dualidade. 
 
6. Demonstre o teorema das folgas complementares. 
 
7. Considere a região de soluções da Figura abaixo, na qual desejamos encontrar o 
ponto extremo ótimo que o método dual simplex usa para Minimizar Z = 2x1 + x2. A 
solução ótima ocorre no ponto F = (0,5; 1,5) no gráfico. 
 
(a) O dual simplex pode iniciar no ponto A? 
(b) Se a solução básica inicial (inviável, porém melhor do que a ótima) é dada 
pelo ponto G, seria possível que as iterações do método dual simplex 
percorressem o caminho G → E → F? Explique. 
(c) Se a solução básica inicial (inviável) começar no ponto L, indique um 
possível caminho do método dual simplex que leva ao ponto ótimo viável no 
ponto F. 
 
8. Gere as iterações do dual simplex ou do simplex (determine qual método utilizar) 
para os seguintes problemas e trace o caminho do algoritmo no gráfico da região de 
soluções. 
 
(a) Minimizar Z = 2x1 + 3x2 
 S.A. 2x1 + 2x2 ≤ 30 
 x1 + 2x2 ≥ 10 
 x1, x2 ≥ 0 
 
(b) Minimizar Z = 5x1 + 6x2 
 S.A. x1 + x2 ≥ 2 
 4x1 + x2 ≥ 4 
 x1, x2 ≥ 0 
 
9. A Ozark Farm tem 20.000 frangos que são alimentados durante oito semanas e só 
depois são comercializados. A ração semanal por frango varia de acordo com o esquema 
da Tabela abaixo. 
 
Para o frango conseguir o ganho de peso desejado em oito semanas, as rações devem 
satisfazer necessidades nutricionais específicas. Embora uma lista típica de itens para 
compor as rações seja grande, para simplificar limitaremos o problema a três itens 
apenas: calcário, milho e preparado de soja. As necessidades nutricionais também serão 
limitadas a três tipos: cálcio, proteína e fibra. A Tabela abaixo resume o teor nutritivo 
dos ingredientes selecionados, junto com os dados de custo. 
 
O mix da ração deve conter: 
(a) No mínimo 0,8% de cálcio, porém não mais do que 1,2%. 
(b) No mínimo 22% de proteína. 
(c) No máximo 5% de fibra em estado natural. 
Resolva o problema de PL para a semana 1 e depois use a análise pós-otimização para 
desenvolver uma esquema ótimo para as sete semanas restantes. 
 
10. Mostre que o método dual simplex é precisamente o método simplex (primal) 
aplicado ao problema dual. 
 
11. Considere o problema Maximizar c´x, S.A. Ax = b, x ≥ 0. Indique se as seguintes 
afirmações são verdadeiras ou falsas e discuta. 
a. Viabilidade do problema dual é o mesmo que otimalidade do problema primal. 
b. Adicionar variáveis artificiais ao problema primal serve para restringir variáveis 
que são realmente irrestritas no problema dual. 
c. Converter um problema de maximização em um problema de minimização muda 
o sinal das variáveis do problema dual. 
d. Se o problema primal tem solução finita o seu dual não é ilimitado. 
e. Se o problema primal tem múltiplas soluções ótimas então o seu dual é 
degenerado.