PUC-Rio Pesquisa Operacional - Exercicios Lista 1 Resposta

Prévia do material em texto

1 
PUC/RJ – Pesquisa Operacional - Prof. Léa Benatti 
 
Exercícios Propostos (Respostas) - 1a LISTA DE EXERCÍCIO 
(P. O. – Medeiros da Silva - pág. 18). 
Construção de Modelos de Programação Linear 
 
Construir o modelo matemático de programação linear dos sistemas descritos a seguir: 
 
1 – Um sapateiro faz 6 (seis) sapatos por hora, se fizer somente sapatos, e 5 cintos por 
hora, se fizer somente cintos. Ele gasta 2 unidades de couro para fabricar 1 unidade de 
sapato e 1 unidade de couro para fabricar uma unidade de cinto. Sabendo-se que o total 
disponível de couro é de 6 unidades e que o lucro unitário por sapato é de 5 unidades 
monetárias e o do cinto é de 2 unidades monetárias, pede-se: o modelo do sistema de 
produção do sapateiro, se o objetivo é maximizar seu lucro por hora. 
 
Solução: 
 
Descrição do Modelo: 
Sapateiro: 6 sapatos/hora → só sapatos. ⇒ Restrições 
5 cintos/hora → só cintos. 
 
Para fabricar 1 (uma) unidade sapato → gasta 2 unidades de Couro. ⇒ Restrições 
Para fabricar 1 (uma) unidade cinto → gasta 1 unidade de Couro. 
 
Total disponível de couro: 6 unidades (restrição). 
 
Lucro unitário por sapato → 5 unidades monetárias (u.m.). 
Lucro unitário por cinto → 2 unidades monetárias (u.m.). 
 
Pede-se: O modelo do sistema de produção do sapateiro, se o objetivo é maximizar seu lucro por 
hora. 
 
Variáveis de Decisão: 
X1 → quantidade de sapatos fabricados por hora; 
X2 → quantidade de sapatos fabricados por hora. 
 
Deve-se decidir o sistema de produção, isto é, quais as quantidades por hora devem ser 
produzidos de sapatos e cintos para se obter o máximo de lucros. 
 
Função Objetivo: 
Maximizar L = 5X1 + 2X2 → lucro total/hora. 
Restrições: 
 2X1 + 1X2 ≤ 6 
10X1 + 12X2 ≤ 60 
 X1, X2 ≥ 0 (condição de não-negatividade) 
 
Obs.: Segunda restrição: 
utosmin10cadaasapato1faz
10
1
min60
sap6
sapatosó
hora
sap6 →=→→ 
 
 utosmin12cadaaointc1faz
12
1
min60
osintc5
ointcsó
hora
osintc5 →=→→ 
 
O sapateiro não pretende fabricar somente cintos ou somente sapatos, ele 
pretende fabricar cintos e sapatos. 
 
 2 
2 – Certa empresa fabrica dois produtos P1 e P2. O lucro por unidade de P1 é de 100 u.m. 
e o lucro unitário de P2 é de 150 u.m.. A empresa necessita de 2 horas para fabricar uma 
unidade de P1 e 3 horas para fabricar uma unidade de P2. O tempo mensal disponível 
para essas atividades é de 120 horas. As demandas esperadas para os 2 produtos 
levaram a empresa a decidir que os montantes produzidos de P1 e P2 não devem 
ultrapassar 40 unidades de P1 e 30 unidades de P2 por mês. Construa o modelo do 
sistema de produção mensal com o objetivo de maximizar o lucro da empresa. 
 
Solução: 
 
Descrição do Modelo: 
Empresa fabrica 2 produtos: P1 e P2. 
 
Lucro por unidade de P1 → 100 u.m. 
Lucro por unidade de P2 → 150 u.m. 
 
Necessita-se: Para fabricar uma unidade P1 → 2 horas. ⇒ Restrições 
 Para fabricar uma unidade P2 → 3 horas. 
 
Tempo mensal disponível para essas atividades: 120 horas. ⇒ Restrições 
 
Demandas esperadas para os 2 produtos levam a decidir que: 
Produção de P1 → não ultrapassa 40 unidades/mês. 
Produção de P2 → não ultrapassa 30 unidades/mês. 
 
Pede-se: O modelo do sistema de produção mensal com o objetivo de maximizar o lucro da 
empresa. 
 
Variáveis de Decisão: 
X1 → quantidade produto P1 fabricado por mês; 
X2 → quantidade produto P2 fabricado por mês. 
 
Função Objetivo: 
Maximizar L = 100X1 + 150X2 → lucro total da empresa. 
 
Restrições: 
 2X1 + 3X2 ≤ 120 → tempo mensal 
 X1 ≤ 40 
 X2 ≤ 30 
 X1, X2 ≥ 0 (condição de não-negatividade) 
 
3 – Um vendedor de frutas pode transportar 800 caixas de frutas para sua região de 
vendas. Ele necessita transportar 200 caixas de laranjas a 20 u.m. de lucro por caixa, pelo 
menos 100 caixas de pêssegos a 10 u.m. de lucro por caixa, e no máximo 200 caixas de 
tangerinas a 30 u.m. de lucro por caixa. De que forma deverá ele carregar o caminhão 
para obter o lucro máximo? Construa o modelo do problema. 
 
Solução: 
 
Descrição do Modelo: 
Vendedor transporta 800 caixas de frutas para região de vendas. 
 
Necessita transportar: 200 caixas laranjas → 20 u.m. lucro/caixa; 
 pelo menos 100 caixas pêssego → 10 u.m. lucro/caixa; 
 no máximo 200 caixas tangerinas → 30 u.m. lucro/caixa. 
 
De que forma deverá ele carregar o caminhão para obter o lucro máximo? 
 3 
Variáveis de Decisão: 
X1 → quantidade caixas pêssego; 
X2 → quantidade caixas tangerina. 
 
Quantidade de laranja → não é incógnita (200 caixas). 
 
Função Objetivo: 
Maximizar L = 10X1 + 30X2 + (20 x 200) 
Maximizar L = 10X1 + 30X2 + 4.000 
 
Restrições: 
 X1 + X2 ≤ 600 (800 totais cx – 200 cx laranjas) 
 X1 ≥ 100 
 X2 ≤ 200 
 X1, X2 ≥ 0 (condição de não-negatividade) 
 
4 – Uma rede de televisão local tem o seguinte problema: foi descoberto que o programa 
“A” com 20 minutos de música e 1 minuto de propaganda chama a atenção de 30.000 
telespectadores, enquanto o programa “B”, com 10 minutos de música e 1 minuto de 
propaganda chama atenção de 10.000 telespectadores. No decorrer de uma semana, o 
patrocinador insiste no uso de no mínimo, 5 minutos para sua propaganda e que não há 
verba para mais de 80 minutos de música. Quantas vezes por semana cada programa 
deve ser levado ao ar para obter o número máximo de telespectadores? Construa o 
modelo do sistema. 
 
Solução: 
 
Descrição do Modelo: 
Rede de Televisão Local. 
 
Programa A: 20 minutos música; ⇒ Chama a atenção de 30.000 telespectadores. 
 1 minuto propaganda. 
 
Programa B: 10 minutos música; ⇒ Chama a atenção de 10.000 telespectadores. 
 1 minuto propaganda. 
 
Decorrer de uma semana: 
No mínimo 5 minutos para propagandas do patrocinador; 
Não há verba para mais de 80 minutos de músicas 
 
Quantas vezes por semana cada programa deve ser levado ao ar para obter o número máximo de 
telespectadores? 
 
Variáveis de Decisão: 
X1 → freqüência semanal do programa A; 
X2 → freqüência semanal do programa B. 
 
Função Objetivo: 
Maximizar T = 30.000X1 + 10.000X2 
T: número de telespectadores. 
Restrições: 
 
 1X1 + 1X2 ≥ 5 (mínimo total propag./semana) 
 Min. propag. Min. propag. 
 programa A. programa B. 
 
 
 4 
20X1 + 10X2 ≤ 80 (máximo músicas./semana) 
 Música p/ Música p/ 
 programa A. programa B. 
 
 X1, X2 ≥ 0 (condição de não-negatividade) 
 
5 – Uma empresa fabrica 2 modelos de cintos de couro. O modelo M1, de melhor 
qualidade, requer o dobro do tempo de fabricação em relação ao modelo M2. Se todos os 
cintos fossem do modelo M2, a empresa poderia produzir 1.000 unidades por dia. A 
disponibilidade de couro permite fabricar 800 cintos de ambos os modelos por dia. Os 
cintos empregam fivelas diferentes, cuja disponibilidade diária é de 400 para M1 e 700 
para M2. Os lucros unitários são de $4,00 para M1 e $3,00 para M2. Qual o programa 
ótimo de produção que maximiza o lucro total diário da emprese? Construa o modelo do 
sistema descrito. 
 
Solução: 
 
Descrição do Modelo: 
Dois modelos de cinto de couro. 
 
Modelo M1 (melhor qualidade) → dobro de tempo de fabricação em relação ao modelo M2. 
 
Todos os cintos M2 → produz-se 1.000 unidades/dia. 
(Quantidade produzida atrelada (Se todos os cintos usassem 1 (um) tempo para fabricação, 
ao tempo de fabricação) seriam produzidos até 1.000 unidades/dia) 
 
Disponibilidadede couro permite fabricar 800 cintos de ambos os modelos por dia. 
 
 Disponibilidade diária: 
 
Fivelas diferentes: 400 unidades para M1; 
700 unidades para M2. 
 
Lucro unitário: $4,00 para M1; 
$3,00 para M2. 
 
Qual o programa ótimo de produção que maximiza o lucro total diário da empresa? 
 
Variáveis de Decisão: 
X1 → quantidade produzida de M1; 
X2 → quantidade produzida de M2. 
 
Função Objetivo: 
Maximizar L = 4X1 + 3X2 
 
Restrições: 
 2X1 + 1X2 ≤ 1.000 → relação em função ao tempo de fabricação. 
(Tempo p/ (Tempo p/ (Quantidade de tempos se só 
 1 M1) 1M2) cintos M2 forem produzidos) 
 
 X1 + X2 ≤ 800 → relação em função da disponibilidade de couro. 
 X1 ≤ 400 
 X2 ≤ 700 
 X1, X2 ≥ 0 (condição de não-negatividade) 
 
 
 
 5 
6 – Uma empresa, após um processo de racionalização de produção, ficou com 
disponibilidade de 3 recursos produtivos, R1, R2 e R3. Um estudo sobre o uso desses 
recursos indicou a possibilidade de se fabricar 2 produtos P1 e P2. Levantando os custos e 
consultando o departamento de vendas sobre o preço de colocação no mercado, 
verificou-se que P1 daria um lucro de $120,00 por unidade e P2, $150,00 por unidade. O 
departamento de produção forneceu a seguinte tabela de uso de recursos. 
 
Produto Recursos R1 por 
unidade 
Recursos R2 por 
unidade 
Recursos R3 por 
unidade 
P1 
P2 
2 
4 
3 
2 
5 
3 
Disponibilidade de 
recursos por mês 100 90 120 
 
Que produção mensal de P1 e P2 traz o maior lucro para a empresa? Construa o modelo 
do sistema. 
 
Solução: 
 
Descrição do Modelo: 
Disponibilidade de recursos produtivos R1, R2 e R3. 
 
Uso desses recursos possibilita fabricar 2 produtos → P1 e P2. 
 
Todos os cintos M2 → produz-se 1.000 unidades/dia. 
(Quantidade produzida atrelada (Se todos os cintos usassem 1 (um) tempo para fabricação, 
ao tempo de fabricação) seriam produzidos até 1.000 unidades/dia) 
 
P1 → daria lucro de $120,00 por unidade. 
P2 → daria lucro de $150,00 por unidade. 
 
Tabela de recursos: 
Produto Recursos R1 por unidade 
Recursos R2 
por unidade 
Recursos R3 
por unidade 
P1 
P2 
2 
4 
3 
2 
5 
3 
Disponibilidades 
de recursos/mês 100 90 120 
 
Qual produção mensal de P1 e P2 traz o maior lucro para a empresa? 
 
Variáveis de Decisão: 
X1 → produção mensal de P1; 
X2 → produção mensal de P2. 
 
Função Objetivo: 
Maximizar L = 120X1 + 150X2 
 
Restrições: 
 2X1 + 4X2 ≤ 100 
 3X1 + 2X2 ≤ 90 
 5X1 + 3X2 ≤ 120 
 X1, X2 ≥ 0 (condição de não-negatividade) 
 
 
 6 
7 – Um fazendeiro está estudando a divisão de sua propriedade nas seguintes atividades 
produtivas: 
A (Arrendamento) – Destinar certa quantidade de alqueires para a plantação de cana-de-
açúcar, a uma usina local, que se encarrega da atividade e paga pelo aluguel da terra 
$300,00 por alqueire por ano. 
P (Pecuária) – Usar outra parte para a criação de gado de corte. A recuperação das 
pastagens requer adubação (100 kg/Alq) e irrigação (100.000 litros de água/Alq) por ano. 
O lucro estimado nessa atividade é de $400,00 por alqueire por ano. 
S (Plantio de soja) – Usar uma terceira parte para o plantio de soja. Essa cultura requer 
200 kg por alqueire de adubos e 200.000 litros de água/Alq para irrigação por ano. O lucro 
estimado nessa atividade é de $500,00/alqueire no ano. 
Disponibilidade de recurso por ano: 12.750.000 litros de água 
14.000 kg de adubo 
100 alqueires de terra 
Quantos alqueires deverá destinar a cada atividade para proporcionar o melhor retorno? 
Construa o modelo de decisão. 
 
Solução: 
 
Descrição do Modelo: 
Divisão de Propriedade: 
A (Arrendamento) → Plantação açúcar, a uma Usina local; 
Aluguel (recebido com o arrendamento) → $300,00 por alqueire por ano. 
 
B (Pecuária) → criação de gado de corte. 
Recuperação pastagem: adubação → 100 Kg/alq. por ano; 
irrigação → 100.000 l água/alq. por ano. 
 
Lucro estimado nesta atividade: $400,00 por alqueire no ano. 
 
S (Plantio Soja) → plantio de soja. 
Requer: adubos → 200 Kg/alq. por ano; 
irrigação → 200.000 l água/alq. por ano. 
 
Lucro estimado nesta atividade: $500,00 por alqueire no ano. 
 
Disponibilidade de recursos por ano: 12.750.000 l. de água; 
14.000 Kg de adubo; 
100 alqueires de terra. 
 
Quantos alqueires deverá destinar a cada atividade para proporcionar o melhor retorno? 
 
Variáveis de Decisão: 
X1 → alqueires para arrendamento; 
X2 → alqueires para pecuária; ⇒ presentes na pergunta do modelo. 
X3 → alqueires para soja. 
 
Função Objetivo: (Maximizar lucro L) 
Maximizar L = 300X1 + 400X2 + 500X3 → melhor retorno 
 
Restrições: 
 X1 + X2 + X3 ≤ 100 → número alqueires terra. 
 100X2 + 200 X3 ≤ 14.000 → adubo. 
 100.000X2 + 200.000X3 ≤ 12.750.000 
 X1, X2, X3 ≥ 0 (condição de não-negatividade) 
 
 7 
8 – O departamento de marketing de uma empresa estuda a forma mais econômica de 
aumentar em 30% as vendas de seus dois produtos P1 e P2. 
As alternativas são: 
a) Investir em um programa institucional com outras empresas do mesmo ramo. 
Esse programa requer um investimento mínimo de $3.000,00 e deve proporcionar um 
aumento de 3% nas vendas de cada produto, para cada $1.000,00 investidos. 
b) Investir diretamente na divulgação dos produtos. Cada $1.000,00 investidos em P1 
retornam um aumento de 4% nas vendas, enquanto que para P2 o retorno é de 10%. 
A empresa dispõe de $10.000,00 para esse empreendimento. Quanto deverá destinar a 
cada atividade? Construa o modelo do sistema descrito. 
 
Solução: 
 
Descrição do Modelo: 
Departamento de Marketing de uma empresa deseja aumentar em 30% as vendas dos produtos P1 
e P2. (Aumento de no mínimo 30%). 
 
Alternativas: 
a) Investir programa institucional com empresas de mesmo ramo. 
 
Investimento mínimo: $3.000,00 → proporciona 3% aumento nas vendas de cada produto, 
para cada $1.000,00 investidos. 
 
e (as alternativas a e b devem ser usadas simultaneamente) 
 
b) Investir diretamente na divulgação dos produtos. 
 
cada $1.000,00 investidos em P1 → retornam aumento 4% nas vendas; 
cada $1.000,00 investidos em P2 → retornam aumento 10% nas vendas. 
 
Disponibilidade da empresa para esse empreendimento: $10.000,00. 
 
Quanto deverá destinar a cada atividade? 
 
Variáveis de Decisão: 
X1 → quantidade em $1.000 para programa institucional; 
X2 → quantidade em $1.000 diretamente em P1; 
X3 → quantidade em $1.000 diretamente em P2. 
 
Função Objetivo: (Minimizar o custo C) 
Minimizar C = 1.000X1 + 1.000X2 + 1.000X3 → quantas quantidades de $1.000 são 
necessárias para obter a forma mais 
econômica de aumentar as vendas. 
 
Restrições: 
 X1 ≥ 3 → para cada $1.000 ⇒ $3.000 (investimento mínimo). 
3X1 + 4X2 ≥ 30 → 30% aumento vendas → p/ 30% aumento em P1 usando a e b. 
(% p/ cada (% p/ P1) 
 produto) 
 
3X1 + 10X2 ≥ 30 → 30% aumento vendas → p/ 30% aumento em P2 usando a e b. 
(% p/ cada (% p/ P2) 
 produto) 
 
 X1 + X2 + X3 ≤ 10 → para cada $1.000 ⇒ $10.000 
 X1, X2, X3 ≥ 0 (condição de não-negatividade) 
 
 8 
9 – Uma liga especial constituída de ferro, carvão, silício e níquel pode ser obtida usando 
a mistura desses minerais puros além de 2 tipos de materiais recuperados: 
Material recuperado1 – MR1 – Composição: 
 Ferro – 60% Custo por kg: $0,20 
 Carvão – 20% 
 Silício – 20% 
Material Recuperado 2 – MR2 – Composição: 
 Ferro – 70% Custo por kg: $0,25 
 Carvão – 20% 
 Silício – 5% 
 Níquel – 5% 
A liga deve ter a seguinte composição final: 
Matéria-prima: % mínima: % máxima: 
 Ferro 60 65 
 Carvão 15 20 
 Silício 15 20 
 Níquel 5 8 
Os custos dos materiais puros são (por kg): ferro: $0,30; carvão: $0,20; silício: $0,28; 
níquel: $0,50. Qual deverá ser a composição da mistura em termos dos materiais 
disponíveis, com menor custo por kg? Construa o modelo de decisão. 
 
Solução: 
 
Descrição do Modelo: 
Liga: Ferro, carvão, silício e níquel (minerais puros) 
e 
Tipos de materiais recuperados (MR) 
 
MR1 – composição: 
 Ferro: 60% ; Custo por Kg: $0,20. 
 Carvão: 20% 
 Silício: 20% 
 
MR2 – composição: 
 Ferro: 70% ; Custo por Kg: $0,25. 
 Carvão: 20% 
 Silício: 5% 
 Níquel: 5% 
 
Composição final da liga: 
Matéria-prima % mínima % máxima 
 Ferro 60 65 
 Carvão 15 20 
 Silício 15 20 
 Níquel 5 8 
 
Custos dos materiais puros (por kg): 
Ferro: $0,30; Carvão: $0,20; Silício: $0,28; Níquel: $0,50. 
 
Qual deverá ser a composição da mistura em termos dos materiais disponíveis, com menor custo 
por Kg? 
 
Variáveis de Decisão: 
X1 → quantidade de MR1 na mistura; 
X2 → quantidade de MR2 na mistura; 
X3 → quantidade de ferro puro na mistura; 
 9 
X4 → quantidade de carvão puro na mistura; 
X5 → quantidade de silício puro na mistura;; 
X6 → quantidade de níquel puro na mistura. 
 
Função Objetivo: (Minimizar custo C). 
Minimizar C = 0,20X1 + 0,25X2 + 0,30X3 + 0,20X4 + 0,28X5 + 0,50X6 
 
Restrições: 
0,6X1 + 0,7X2 + X3 ≥ 0,60 → ferro mínimo 
(% ferro (% ferro (ferro 
em MR1) em MR2) puro) 
 
0,6X1 + 0,7X2 + X3 ≤ 0,65 → ferro máximo 
 
0,20X1 + 0,20X2 + X4 ≥ 0,15 → carvão mínimo 
(% carvão (% carvão (carvão 
em MR1) em MR2) puro) 
 
0,20X1 + 0,20X2 + X4 ≤ 0,20 → carvão máximo 
 
0,2X1 + 0,05X2 + X5 ≥ 0,15 → silício mínimo 
(% silício (% silicio (silício 
em MR1) em MR2) puro) 
 
0,2X1 + 0,05X2 + X5 ≤ 0,20 → silício máximo 
 
0,05X2 + X6 ≥ 0,05 → níquel mínimo 
(% níquel (níquel 
em MR2) puro) 
 
0,05X2 + X6 ≤ 0,08 → níquel máximo 
 
X1 + X2 + X3 + X4 + X5 + X6 = 1 → porcentagem máxima. 
(Soma de todos os componentes deve 
ser igual a 100%). 
 
 X1, X2, X3, X4, X5, X6 ≥ 0 (condição de não-negatividade) 
 
10 – Uma rede de depósitos de material de construção tem 4 lojas que devem ser 
abastecidas com 50 m3 (loja 1), 80 m3 (loja 2), 40 m3 (loja 3) e 100 m3 (loja 4) de areia 
grossa. Essa areia pode ser carregada em 3 portos P1, P2 e P3, cujas distâncias às lojas 
estão no quadro (em km): 
 
 
L1 L2 L3 L4 
P1 
P2 
P3 
30 
12 
8 
20 
36 
15 
24 
30 
25 
18 
24 
20 
 
O caminhão pode transportar 10m3 por viagem. Os portos têm areia para suprir qualquer 
demanda. Estabelecer um plano de transporte que minimize a distância total percorrida 
entre os portos e as lojas e supra as necessidades das lojas. Construa o modelo linear do 
problema. 
 
Solução: 
 
Descrição do Modelo: 
Rede material de construção: 4 lojas. 
 10 
Abastecimento das lojas: 50 m3 (loja 1); 80 m3 (loja 2); 40 m3 (loja 3) e 100 m3 (loja 4). 
(areia grossa) 
 
Areia é carregada em 3 portos P1, P2 e P3 cujas distâncias das lojas são: (em Km) 
 
 
L1 L2 L3 L4 
P1 
P2 
P3 
30 
12 
8 
20 
36 
15 
24 
30 
25 
18 
24 
20 
 
Caminhão transporta 10 m3/viagem. 
Os portos tem areia para suprir qualquer demanda. 
 
Estabelecer um plano de transporte que minimize a distância total percorrida entre os portos e as 
lojas e supra as necessidades das lojas. 
 
Fç. Objetivo: minimizar distância. 
Plano de transporte: número de viagens dos portos às lojas. 
 
Variáveis de Decisão: 
X11 → no viagens do P1 a L1; 
X12 → no viagens do P1 a L2; 
X13 → no viagens do P1 a L3; 
X14 → no viagens do P1 a L4. 
X21 → no viagens do P2 a L1; 
X22 → no viagens do P2 a L2; 
X23 → no viagens do P2 a L3; 
X24 → no viagens do P2 a L4. 
X31 → no viagens do P3 a L1; 
X32 → no viagens do P3 a L2; 
X33 → no viagens do P3 a L3; 
X34 → no viagens do P3 a L4. 
 
Função Objetivo: (Minimizar distância total percorrida D). 
Minimizar D = 30X11 + 20X12 + 24X13 + 18X14 + 
 12X21 + 36X22 + 30X23 + 24X24 + 
 8X31 + 15X32 + 25X33 + 20X34 
 
Restrições: 
X11 + X21 + X31 = 5 → 50m3 / (10m3/viagenm) = 5 viagens por caminhão; 
X12 + X22 + X32 = 8 → 80m3 / (10m3/viagenm) = 8 viagens por caminhão; 
X13 + X23 + X33 = 4 → 40m3 / (10m3/viagenm) = 4 viagens por caminhão; 
X14 + X24 + X34 = 10 → 100m3 / (10m3/viagenm) = 10 viagens por caminhão. 
 
 Xij ≥ 0 , i = 1, 2, 3 → condições não-negativas. 
 J = 1, 2, 3, 4 
 
-- # # -- 
Lojas a serem 
abastecidas. 
 
Distâncias dos 
portos às lojas. 
Portos