Exercicios sobre Programacao Matematica[1]

Prévia do material em texto

1 Programação Linear e Inteira – Prof. Edwin 
Lista 2 - Exercícios sobre Modelagem Matemática 
1) Um sapateiro faz 6 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,00 e o do cinto é de $2,00, pede-se: o 
modelo do sistema de produção do sapateiro, se o objetivo é maximizar seu lucro por hora. 
2) Certa empresa fabrica 2 produtos P1 e P2. O lucro por unidade de P1 é de $100, e o lucro por 
unidade de P2 é de $150. 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 estas atividades é de 
120 horas. As demandas esperadas para os 2 produtos levaram a empresa a decidir que os 
montantes produzidos não devem ultrapassar 40 unidades de P1 e 30 unidades de P2 por mês. 
Construa o modelo de produção mensal com o objetivo de maximizar o lucro da empresa. 
3) 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 a 
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. 
4) 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 empresa? Construa, o modelo do sistema descrito. 
5) Uma empresa, após um processo de racionalização de produção, ficou com disponibilidade de 
3 recursos produtivos, R1, R2, 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 2 3 5 
P2 4 2 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. 
 
 
2 Programação Linear e Inteira – Prof. Edwin 
6) 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 (100Kg/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 200Kg 
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 recursos 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. 
7) 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 possíveis atividades são: 
- 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. 
- Investir diretamente na divulgação de cada um 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. 
8) 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 Recuperado 1 - MR1 – Composição 
ferro - 60% 
carvão - 20% 
silício - 20% 
Custo por Kg: $0,20 
Material Recuperado 2 - MR2 - Composição 
ferro - 70% 
carvão - 20% 
 
3 Programação Linear e Inteira – Prof. Edwin 
silício - 5% 
níquel - 5% 
Custo por Kg: $0,25 
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 
O custo 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. 
9) 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), 100 m3 (loja 4) de areia grossa. Esta areia pode ser 
carrega de 3 portos P1, P2 e P3, cujas distâncias às lojas estão no quadro (em Km): 
 L1 L2 L3 L4 
P1 30 20 24 18 
P2 12 36 30 24 
P3 8 15 25 20 
O caminhão pode transportar 10 m3 por 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. Construa o modelo linear do problema. 
10) Um fabricante de gasolina para aviação vende dois tipos de combustível: A e B. O combustível 
A tem 25% de gasolina de grau 1, 25% de grau 2 e 50% de grau 3. O combustível B tem 50% de 
gasolina de grau 2 e 50% de grau 3. Existem 500 gal./hr de grau 1, 200 gal./hr de grau 2 e 200 
gal./hr de grau 3 disponíveis para produção. Os custos vão de 30 centavos ($0,30) por galão de 
grau 1, $0,60 por gal. de grau 2 e $0,50 de grau 3. O tipo A pode ser vendido a $0,75 por galão 
enquanto que o tipo B alcança $0,90/gal. Quais deverão ser as quantidades de produção de 
cada um dos combustíveis? 
11) Uma companhia de transporte tem 10 caminhões com capacidade de 40.000 libras e 5 
caminhões de 30.000 lbs. Os primeiros têm custos operacionais de $0,30/milha e os outros de 
$0,25/milha. Na próxima semana a companhia deverá transportar 400.000 lbs de cevada por 
um percurso de 800 milhas. A possibilidade de outros compromissos impõe que, a cada dois 
caminhões menores deve ficar ao menos um dos grandes de reserva. Pergunta-se: Qual é o 
número ótimo de caminhões de ambos os portes se deve movimentar para o transporte da 
cevada? 
 
4 Programação Linear e Inteira – Prof. Edwin 
12) Uma refinaria pode comprar dois tipos de petróleo: o bruto leve e o bruto pesado. O custo por 
barril desses tipos são $11 e $9, respectivamente. De cada tipo de petróleo se produz, por barril, 
as seguintes quantidades de gasolina, kerosene e combustível para reatores: 
Petróleo Gasolina Kerosene Combustível 
Bruto leve 0,40 0,20 0,35 
Bruto pesado 0,320,40 0,20 
Observa-se que durante o processo de refinamento se perde 5% e 8% de bruto, 
respectivamente. A refinaria tem um contrato para entregar um milhão de barris de gasolina, 
400.000 de kerosene e 250.000 de combustível. Formule um PL para o problema de encontrar 
o número de barris de cada tipo de petróleo bruto que satisfaça a demanda e minimize o custo 
total. 
13) A Capitão Caverna S.A., localizada em Pedra Lascada, aluga 3 tipos de barcos para passeios 
marítimos: jangadas, supercanoas e arcas com cabine. A companhia fornece juntamente com o 
barco um capitão para navegá-lo e uma tripulação que varia de acordo com a embarcação: uma 
para jangadas, duas para supercanoas e três para arcas. A companhia tem 4 jangadas, 8 
supercanoas e 3 arcas e em seu corpo de funcionários: 10 capitães e 18 tripulantes. O aluguel 
é por diárias e a Capitão Caverna lucra $50 por jangada, $70 por supercanoa e $100 por arca. 
Faça um modelo de programação matemática que determine o esquema de aluguel que 
maximiza o lucro. 
14) Um excursionista planeja fazer uma viagem acampando. Há 5 itens que ele deseja levar consigo, 
mas estes, juntos, excedem o limite de 60 quilos que ele supõe ser capaz de carregar. Para 
ajudar a si próprio no processo de seleção, ele atribui valores, por ordem crescente de 
importância a cada um dos itens conforme a tabela a seguir: 
Item 1 2 3 4 5 
Peso(Kg) 52 23 35 15 7 
Valor 100 60 70 15 8 
Supondo a existência de uma unidade de cada item, faça um modelo de programação inteira 
que maximize o valor total sem exceder as restrições de peso. 
15) Um hospital trabalha com atendimento variável em demanda durante as 24 horas do dia. As 
necessidades distribuem-se segundo a tabela: 
Turno Horário Número requerido de enfermeiros 
1 08 às 12h 51 
2 12 às 16h 58 
3 16 às 20h 62 
4 20 às 24h 41 
5 24 às 04h 32 
6 04 às 08h 19 
 
 
5 Programação Linear e Inteira – Prof. Edwin 
O horário de trabalho de um enfermeiro é de 8 horas seguidas e só pode ser iniciado no começo 
de cada turno, isto é, às 8 ou 12 ou 16 ou 20 ou 24 ou 04 horas. Elabore um modelo de PLI que 
minimize o gasto com a mão-de-obra. Considere que cada enfermeiro recebe $100 por hora de 
trabalho no período diurno (08 às 20 h) e $125 no período noturno (20 às 08 h). 
16) Relativamente ao problema anterior, suponha que cada enfermeiro possa fazer hora-extra 
trabalhando mais 4 horas consecutivas além de sua jornada normal de trabalho, isto é, mais um 
turno de trabalho. Suponha que a hora-extra seja remunerada em 50% a mais que a hora 
normal. Considere, também, que em cada turno não mais de 20% dos enfermeiros possam estar 
fazendo hora-extra. Faça um modelo de programação linear inteira que minimize os gastos com 
a contratação de mão-de-obra. Antes de resolver o problema, pense na seguinte questão: A 
solução ótima dessa variante poderá ter custo menor que a da solução ótima sem a 
possibilidade de os enfermeiros fazerem hora-extra? Justifique. 
17) Uma fábrica manufatura 5 tipos de prateleiras (P1; P2; P3; P4; P5) utilizando dois processos de 
produção: processo normal (N) e processo acelerado (A). Cada produto requer um certo 
número de horas para ser trabalhado dentro de cada processo e alguns produtos só podem ser 
fabricados através de um dos tipos de processo. O quadro a seguir resume o consumo (em 
horas) dentro de cada esquema de fabricação e os lucros (em R$) obtidos após a dedução dos 
custos de produção. 
Prateleiras P1 P2 P3 P4 P5 
Lucro (R$/unidade) 570 575 555 550 560 
Processo Normal 12 16 - 19 9 
Processo Acelerado 10 16 5 - - 
A montagem final de cada prateleira requer 16 h de mão-de-obra por unidade. A fábrica possui 
3 máquinas para o processo normal e 2 para o processo acelerado. As máquinas trabalham em 
2 turnos de 8 horas por dia em um regime de 6 dias por semana. Uma equipe de 8 pessoas 
trabalha em turno único de 8 horas durante 6 dias na montagem das prateleiras. Determine o 
melhor esquema de produção. 
18) A figura a seguir representa uma rede de comunicação de dados entre computadores. Os 
números representam a capacidade máxima em MBytes por segundo que pode ser transmitido 
de um computador para outro. Admita que a transmissão só é possível no sentido especificado 
pela seta. Construa um modelo de programação linear inteira que determine o fluxo máximo 
que pode passar entre A e G através da rede? 
 
 
6 Programação Linear e Inteira – Prof. Edwin 
19) Uma fábrica de artigos de decoração, localizada em Lambari (MG), deve entregar uma grande 
quantidade de peças na cidade de Baependi (MG). A empresa quer saber qual o caminho que 
seu caminhão de entregas deve fazer para minimizar a distância total percorrida. A figura a 
seguir, representa, na forma de rede, as ligações entre as cidades da região. Construa um 
modelo de programação linear inteira que ajude a minimizar a distância percorrida. 
 
20) A LCL Motores recebeu recentemente uma encomenda para produzir três tipos de motores. 
Cada tipo de motor necessita de um determinado número de horas de trabalho no setor de 
montagem e acabamento. A LCL pode terceirizar parte de sua produção. A tabela a seguir 
resume essas informações: 
 
Elabore o modelo de programação matemática que minimiza os custos de produção. 
21) Duas ligas metálicas, A e B são feitas de quatro metais distintos, I, II, III, IV, de acordo com as 
especificações apresentadas na seguinte tabela. 
LIGAS ESPECIFICAÇÃO 
A 
No máximo 80% de I 
No máximo 30% de II 
No mínimo 50% de IV 
B 
Entre 40% e 60% de II 
No mínimo 30% de III 
No mínimo 70% de IV 
Os quatro metais são extraídos de três minérios diferentes, cujas percentagens em peso destes 
metais, quantidades máximas dos minérios e custos por tonelada são mostrados a seguir. 
 
 
7 Programação Linear e Inteira – Prof. Edwin 
Minério 
Quantidade 
máxima 
(tonelada) 
Componentes (%) Preço por 
tonelada 
(R$) I II III IV Outros 
1 1000 20 10 30 30 10 30,00 
2 2000 10 20 30 30 10 40,00 
3 3000 5 5 70 20 0 50,00 
Considerando-se que os preços de venda das ligas A e B sejam R$ 200,00 e R$ 300,00 por 
tonelada, respectivamente, formular o problema como sendo um modelo de programação 
linear, escolhendo a função-objetivo apropriada que fará o melhor uso das informações dadas. 
22) Uma firma fabrica uma máquina constituída de três peças A e quatro peças B. As duas peças A 
e B são fabricadas a partir de três matérias-primas das quais 100, 200 e 300 unidades são 
disponibilizadas, respectivamente. A Tabela a seguir fornece os requisitos de matéria-prima e o 
número de peças fabricadas por turno de produção, em cada um dos três departamentos da 
firma. 
Departamentos 
Entradas (unidades) 
Matéria Prima 
Saída (unidades) 
Peças 
1 2 3 A B 
1 8 6 5 7 5 
2 5 9 10 6 9 
3 3 8 7 8 4 
Pede-se para determinar o número de turnos de produção para cada departamento que 
maximize o número de máquinas fabricadas. (Formule simplesmente o PPL). 
23) Uma companhia aérea possui três tipos de aviões e é obrigada a servir quatro rotas aéreas. A 
seguinte Tabela fornece a capacidade máxima (em número de passageiros) de cada tipo de 
aeronave, o número de aviões disponíveis de cada tipo, bem como o número de viagens na rota 
2 etc.). Na Tabela é dado também o número de passageiros que necessariamente terá que ser 
transportado em cada rota. 
 
O custo operacional por viagem para cada avião, nas diferentes rotas, é dado por 
 
 
8 Programação Linear e Inteira – Prof. Edwin 
Formule um modelo de programação linear que permita alocar os aviões às diversas rotas, 
visando a minimizar o custo operacional do sistema. Observação: Um avião não pode num 
mesmo dia servir a rotas distintas. 
24) Os esgotos de três cidades, A, B e C, depois de sofrerem um tratamento, são descarregados 
num rio. O esgoto de cada umadas três cidades produz uma quantidade diária de poluente 
expressa por PA, PB e PC toneladas. O tratamento do esgoto pode reduzir a quantidade de 
poluente até um máximo de 90%. Esta redução é denominada eficiência da estação de 
tratamento e o custo da estação i é diretamente proporcional à sua eficiência (ki * eficiência). 
 
Por outro lado, devido à ação bioquímica (aeração etc.), no final de cada trecho AB e BC do rio, 
a quantidade de poluentes é reduzida em 10% e 20%, respectivamente. 
Qual a eficiência que devem ter as estações de tratamento, de modo que, para qualquer ponto 
do rio, a quantidade de poluentes medida em um dia não ultrapasse P toneladas e de modo a 
minimizar o custo das estações de tratamento? Formular um PPL que permita resolver este 
problema.