FUCHIGAMI 2018 PO1 notas de aula (aplicações) (2)

Prévia do material em texto

Pesquisa Operacional 1 – Notas de aula – Prof. Hélio Fuchigami ⬧ 1 
 
APLICAÇÕES DE PROGRAMAÇÃO LINEAR 
 
1. Problema da mistura 
 
Exemplo: A firma ZYB Tintas Ltda. produz dois tipos de tintas: seca rápido (SR) e 
superseca (SS). Ambas são produzidas a partir de uma base de silicato e de óleo de 
linhaça, que são adquiridos pela ZYB de vários fornecedores. Atualmente, apenas duas 
soluções preliminares estão disponíveis no mercado, além dos produtos isolados. A 
solução do tipo A contém 60% de silicato e 40% de óleo de linhaça, e a do tipo B contém 
30% de silicato e 70% de óleo de linhaça. O preço da solução A é de R$ 0,50 o litro e o 
do tipo B é de R$ 0,75 o litro, enquanto o silicato e o óleo de linhaça isoladamente custam 
R$ 1,00 e R$ 1,50 o litro, respectivamente. Cada litro de SR requer, no mínimo, 25% de 
silicato e 50% de óleo de linhaça e cada litro de SS requer, no mínimo, 20% de silicato e, 
no máximo, 50% de óleo de linhaça. Formule o problema de programação linear para 
determinar quantos litros de cada solução e de cada produto puro devem ser comprados 
para a produzir exatamente 100 litros de SR e 250 litros de SS. [13] 
 
 
2. Problema da dieta 
 
Exercício: Uma refeição padrão é constituída de cinco alimentos diferentes: carne 
(alcatra magra), arroz, feijão, ovo cozido e batata. A tabela a seguir fornece os valores 
nutricionais desses alimentos, para cada 100 g, os preços de cada porção e as 
quantidades mínimas nutricionais de cada nutriente. Deseja-se saber o consumo diário 
de cada alimento de tal maneira que a refeição satisfaça as quantidades mínimas 
com o menor custo possível. [17] 
 
Alimento 
Energi
a (kcal) 
Proteína 
(g) 
Gordura 
(g) 
Carboi-
drato (g) 
Fibra 
(g) 
Cálcio 
(mg) 
Ferro 
(mg) 
Preço 
Carne magra 156 29,2 4,4 0 0 6 2,8 1,00 
Arroz 123 2,2 0,3 29,6 0,8 1 0,2 0,20 
Feijão 103 8,4 0,5 17,4 9,0 37 2,5 0,26 
Ovo cozido 147 12,5 10,8 0 0 57 1,9 0,12 
Batata 72 1,5 0,3 17,8 1,2 5 0,3 0,23 
Quantidades 
mínimas 
1.000 30 4 20 6 30 2 
 
 
 
 
 
v2018 
2 ⬧ Pesquisa Operacional 1 – Notas de aula – Prof. Hélio Fuchigami 
 
3. Problema da carteira de investimentos 
 
Exemplo: A ZYB Investimentos S.A. gerencia recursos de terceiros por meio da escolha 
de carteiras de investimento para diversos clientes, com base em bonds de diversas 
empresas. Um de seus clientes exige que: 
▪ Não mais de 25% do total aplicado deve ser aplicado em um único investimento; 
▪ Um valor superior a 50% do total aplicado deve ser investido em títulos de 
maturidade maiores que dez anos; 
▪ O total aplicado em títulos de alto risco deve ser, no máximo, de 50% do total 
investido. 
A tabela a seguir mostra os dados dos títulos selecionados. Determine qual porcentagem 
do total deve ser aplicado em cada tipo de título. [13] 
 
Aplicação Retorno anual 
Anos para 
vencimento 
Risco 
Título 1 8,7% 15 1 – Muito baixo 
Título 2 9,5% 12 3 – Regular 
Título 3 12,0% 8 4 – Alto 
Título 4 9,0% 7 2 – Baixo 
Título 5 13,0% 11 4 – Alto 
Título 6 20,0% 5 5 – Muito alto 
 
 
4. Problema da refinaria 
 
Exemplo 1: Em uma determinada refinaria, o petróleo bruto sofre os seguintes processa-
mentos antes de ser transformado em gás/óleo ou gasolina bruta: 
 
 
 
A tabela a seguir apresenta a capacidade máxima de processamento de cada unidade de 
operação. Formule o problema de modo a maximizar os lucros totais. [8, 11] 
 
Operação 
Produto (ton/ano) 
Gasolina bruta Gás/Óleo 
Destilação 500.000 600.000 
Dessulfuração 700.000 500.000 
Reforming 400.000 – 
Cracking – 450.000 
Lucros 
unitários ($/ton) 
10,00 7,00 
 Pesquisa Operacional 1 – Notas de aula – Prof. Hélio Fuchigami ⬧ 3 
 
Exemplo 2: A Shale Oil, localizada na Ilha de Aruba, tem uma capacidade de 1.500.000 
barris de óleo cru por dia. Entre os produtos finais de refinaria estão três tipos de gasolina 
sem chumbo, com diferentes octanagens (ON): normal com ON = 87, premium com ON = 
89 e super com ON = 92. O processo de refinação abrange três estágios: 1) uma torre de 
destilação que produz uma fração (ON = 82) à razão de 0,2 barris por barris de óleo cru; 
2) uma unidade de craqueamento que produz frações de gasolina (ON = 98) usando uma 
porção da fração produzida na torre de destilação à taxa de 0,5 barris por barris de fração; 
e 3) uma unidade misturadora que mistura a fração de gasolina da unidade de 
craqueamento com a fração da torre de destilação. A empresa estima o lucro líquido por 
barril dos três tipos de gasolina em $ 6,70, $ 7,20 e $ 8,10, respectivamente. A 
capacidade de entrada da unidade de craqueamento é 200.000 barris de fração por dia. 
Os limites da demanda para gasolina comum, premium e super são 50.000, 30.000 e 
40.000 barris por dia. Desenvolva um modelo para determinar a programação ótima de 
produção para a refinaria. [21] 
 
 
Dica: a octanagem de uma gasolina é a média ponderada das octanagens das correntes de 
entrada usadas no processo de mistura e pode ser calculada, por exemplo, como: 
ONgas. comum = (82 x barris/dia de fração + 98 x barris/dia de craqueamento)/total barris/dia de gasolina comum 
 
 
Exercício: A OilCo está construindo uma refinaria para fabricar quatro produtos: óleo 
diesel, gasolina, lubrificantes e combustível para jatos. A demanda mínima (em barris/dia) 
para cada um desses produtos é 14.000, 30.000, 10.000 e 8.000, respectivamente. A 
OilCo tem contratos de fornecimento de óleo cru para o Irã e Dubai. Por causa das cotas 
de produção especificadas pela Organização dos Países Exportadores de Petróleo 
(OPEP), a nova refinaria pode receber no mínimo 40% de seu óleo cru do Irã e a 
quantidade restante de Dubai. A OilCo prevê que a demanda e as cotas de óleo cru 
permanecerão estáveis nos próximos dez anos. 
As especificações dos dois óleos crus resultam em duas misturas de produtos diferentes: 
um barril de óleo cru do Irã rende 0,2 barril de diesel, 0,25 barril de gasolina, 0,1 barril de 
lubrificante e 0,15 barril de combustível para jatos. Os rendimentos correspondentes do 
óleo cru de Dubai são 0,1; 0,6; 0,15 e 0,1, respectivamente. A OilCo precisa determinar a 
capacidade mínima da refinaria em (barris/dia). [21] 
 
Resposta do livro: 55.000 barris/dia do Irã, 30.000 barris/dia de Dubai, Z = 85. 
(Fração) 
(Destilação) (Unidade 
de craque-
amento) 
(Unidade 
de mistura) 
(Cru) 
4 ⬧ Pesquisa Operacional 1 – Notas de aula – Prof. Hélio Fuchigami 
 
APLICAÇÕES DE PROGRAMAÇÃO INTEIRA 
 
✓ Otimização Discreta 
✓ Otimização Combinatória 
✓ Programação Binária e Inteira 
 
▪ Programação (Linear) Inteira: todas as variáveis são inteiras 
▪ Programação Binária: todas as variáveis assumem valores 0 ou 1 
▪ Programação Linear Inteira Mista (PLIM): há variáveis inteiras e contínuas 
 
▪ Técnicas de solução: algoritmos Branch-and-bound e Planos de Corte 
 
 
1. Problema da planejamento da produção (ou mix de produção) 
 
Exemplo: Uma empresa está interessada em maximizar o lucro mensal proveniente de 
quatro de seus produtos, designados por I, II, III e IV. Para fabricar esses produtos, ela 
utiliza dois tipos de máquinas (M1 e M2) e dois tipos de mão de obra (MO1 e MO2), que 
têm as seguintes disponibilidades 
 
Máquina 
Disponibilidade 
(máquina-hora/mês) 
 Mão de obra 
Disponibilidade 
(homem-hora/mês) 
M1 70 MO1 120 
M2 20 MO2 160 
 
O setor técnico da empresa fornece os seguintes coeficientes, que especificam o total de 
horas de máquina e horas de mão de obra necessárias para a produção de uma unidade 
de cada produto: 
 
Máquina 
Produtos 
Mão de obra 
Produtos 
I II III IV I II III IV 
M1 5 4 8 9 MO1 2 4 2 8 
M2 2 6 0 8 MO2 7 3 0 7 
 
O setor comercial fornece as seguintes informações: 
 
Produtos 
Potencial de venda 
(unidades/mês) 
Lucro unitário 
(R$/mês) 
I 70 10 
II 60 8 
III 40 9 
IV 20 7 
 
Faça o planejamento da produção mensal da empresa objetivando maximizar o lucro. [20]Pesquisa Operacional 1 – Notas de aula – Prof. Hélio Fuchigami ⬧ 5 
 
Exercício 1: A ZYB Motores Ltda. 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 ZYB pode terceirizar parte de sua 
produção. A tabela a seguir resume essas informações: 
 
Tipo de Motor 1 2 3 
Tempo 
disponível (h) 
Montagem (h/unidade) 1,1 1,9 0,7 6.000 
Acabamento (h/unidade) 2,5 0,8 4,0 10.000 
Demanda (unidades) 3.000 2.500 500 
Custo de produção (R$) 50 90 120 
Terceirizado (R$) 65 92 140 
 
Elabore o modelo de programação matemática que minimiza os custos de produção. [13] 
 
Exercício 2: Como precaução para o inverno, uma empresa de confecção está 
fabricando parcas e casacos com enchimento de penas de ganso, calças com isolamento 
térmico e luvas. Todos os produtos são fabricados em quatro departamentos diferentes: 
corte, isolamento térmico, costura e embalagem. A empresa recebeu pedidos fechados 
para seus produtos. O contrato estipula uma multa para itens não entregues. A tabela a 
seguir mostra os dados pertinentes à situação. 
 
Departamento 
Tempo por unidade (horas) Capacidade 
(horas) Parca Casacos Calças Luvas 
Corte 0,30 0,30 0,25 0,15 1.000 
Isolamento 0,25 0,35 0,30 0,10 1.000 
Costura 0,45 0,50 0,40 0,22 1.000 
Embalagem 0,15 0,15 0,10 0,05 1.000 
Demanda 800 750 600 500 
Lucro por unidade ($) 30 40 20 10 
Multa por unidade ($) 15 20 10 8 
 
Elabore um plano ótimo de produção para a empresa. [21] 
 
 
2. Problema de produção e estoque multiperíodo 
 
Exemplo: Uma empresa foi contratada para produzir dois produtos, A e B, nos meses de 
junho, julho e agosto. A capacidade total de produção (expressa em horas) varia 
mensalmente. A tabela a seguir apresenta os dados básicos da situação. 
 
 Junho Julho Agosto 
Demanda para A (unidades) 500 5.000 750 
Demanda para B (unidades) 1.000 1.200 1.200 
Capacidade (horas) 3.000 3.500 3.000 
6 ⬧ Pesquisa Operacional 1 – Notas de aula – Prof. Hélio Fuchigami 
 
As taxas de produção em unidades por hora são 1,25 e 1 para os produtos A e B, 
respectivamente. Toda a demanda deve ser atendida. Contudo, a demanda para um mês 
posterior pode ser completada com a produção de um anterior. Para qualquer 
carregamento de um mês para o seguinte são cobrados custos de permanência no 
estoque de $ 0,90 e $ 0,75 por unidade por mês para os produtos A e B, respectivamente. 
Os custos unitários de produção para os dois produtos são $ 30 e $ 28, para A e B, 
respectivamente. Determine a programação ótima de produção para os dois produtos. [21] 
 
 
Exercício 1: A ZYB Armazéns e Comércio Ltda. possui um armazém com capacidade de 
200.000 toneladas de grãos. No início do mês de janeiro, a ZYB tinha 8.000 toneladas de 
grãos de trigo em seu armazém. Considerando que em cada mês ela pode comprar ou 
vender trigo a preços prefixados pelo governo (conforme a tabela a seguir), em qualquer 
quantidade desejada, desde que sujeitas às restrições de armazenagem e do estoque 
inicial do mês (vendas máximas no mês i = saldo do mês i–1), resolva o problema de 
maneira a maximizar o lucro da operação nos próximos doze meses. [13] 
 
Mês Preço de venda (R$/t) 
Preço de 
compra (R$/t) 
Janeiro 3 8 
Fevereiro 6 8 
Março 8 2 
Abril 2 3 
Maio 4 4 
Junho 5 3 
Julho 6 3 
Agosto 1 2 
Setembro 3 5 
Outubro 2 5 
Novembro 3 3 
Dezembro 3 3 
 
 
Exercício 2: A Acme Manufacturing Company firmou um contrato para entrega de janelas 
de casa para os próximos seis meses. As demandas para cada mês são de 100, 250, 
190, 140, 220 e 110, respectivamente. O custo de produção por janela varia de mês para 
mês, dependendo do custo de mão de obra, do material e de utilidades. A Acme estima 
que o custo de produção por janela nos próximos seis meses seja $ 50, $ 45, $ 55, $ 48, $ 
52 e $ 50, respectivamente. Para aproveitar a vantagem das variações no custo de 
fabricação, a Acme pode optar por produzir mais do que o necessário em determinado 
mês e reter as unidades excedentes para entregar em meses posteriores. Entretanto, isso 
incorrerá em custos de armazenagem de $ 8 por janela, por mês, considerando o estoque 
no final do mês. Desenvolva um modelo de programação linear para determinar a 
programação ótima de produção. [21] 
 
 Pesquisa Operacional 1 – Notas de aula – Prof. Hélio Fuchigami ⬧ 7 
 
3. Problema de nivelamento da produção 
 
Exemplo: Uma empresa fabricará um produto para os próximos quatro meses: março, 
abril, maio e junho. A demanda de cada mês é de 520, 720, 520 e 620 unidades, 
respectivamente. A empresa dispõe de mão de obra constante de dez empregados, mas 
pode atender a necessidades variáveis de produção contrantando e demitindo 
empregados temporários, se necessário. Os custos adicionais de contratação e demissão 
em qualquer mês são de $ 200 e $ 400 por empregado, respectivamente. Um operário 
permanente pode produzir 12 unidades por mês, e um temporário, por não ter experiência 
comparável, produz apenas 10 unidades por mês. A empresa pode produzir mais do que 
o necessário em qualquer mês e transferir o excedente de produção para um mês 
posterior a um custo de carregamento de $ 50 por unidade por mês. Desenvolva uma 
política ótima de contratação/demissão para a empresa na projeção de um planejamento 
de quatro meses. [21] 
 
Dica: neste modelo existem variáveis irrestritas de sinal. 
 
 
4. Problema de planejamento agregado 
 
▪ Planejamento agregado estuda o balanceamento entre produção e demanda 
▪ Horizonte de tempo de médio prazo 
▪ Para atender a uma demanda flutuante a um custo mínimo, pode-se atuar sobre os 
recursos da empresa (mão de obra, nível de produção e estoque), pode-se 
influenciar a demanda ou buscar uma combinação entre as duas estratégias 
▪ Estratégias para influenciar a demanda: propagandas, promoções, 
desenvolvimento de produtos alternativos etc. 
▪ Estratégias para influenciar a produção: controle do nível de estoques, contratação 
e demissão de mão de obra, horas extras ou redução da jornada de trabalho, 
subcontratação de mão de obra terceirizada 
▪ A maioria dos modelos considera a demanda como um fator determinístico 
 
 
Exemplo: A empresa Lifestyle, fabricante de sucos naturais, estava estudando diversos 
planos alternativos de planejamento agregado que poderiam ser adotados para a 
produção do suco de jabuticaba no segundo semestre do próximo ano. Porém, verificou-
se que a solução ótima do problema poderia ser obtida a partir de um modelo de 
programação linear. A demanda prevista para o período analisado, de acordo com o setor 
de vendas, está listada na tabela a seguir. 
 
 
 
8 ⬧ Pesquisa Operacional 1 – Notas de aula – Prof. Hélio Fuchigami 
 
Mês Demanda (litros) 
Julho 4.500 
Agosto 5.200 
Setembro 4.780 
Outubro 5.700 
Novembro 5.820 
Dezembro 4.480 
 
O setor de produção forneceu os seguintes dados: 
 
Custo de produção regular (horas normais) R$ 1,50/litro 
Custo de produção em horas extras R$ 2,00/litro 
Custo de subcontratação de terceiros R$ 2,70/litro 
Custo de aumentar a produção com a admissão de funcionários R$ 3,00/litro 
Custo de diminuir a produção com a demissão de funcionários R$ 1,20/litro 
Custo de manutenção de estoques R$ 0,40/litro-mês 
Estoque inicial 1.000 litros 
Produção regular no mês anterior 4.000 litros 
Capacidade máxima de armazenagem 1.500 litros/mês 
Capacidade máxima de produção regular 5.000 litros/mês 
Capacidade máxima de produção em horas extras 50 litros/mês 
Capacidade máxima de produção subcontratada 500 litros/mês 
 
Determine a formulação matemática do problema de planejamento agregado, de forma a 
minimizar os custos totais de produção, respeitando as restrições de capacidade do 
problema. [5] 
 
 
Trabalho (em dupla): A empresa Farmacom, do setorde cosméticos e produtos de 
limpeza, deseja definir o planejamento agregado de produção de sabonetes do tipo 
Leveza para o primeiro semestre do próximo ano. Para isso, o setor de vendas forneceu a 
demanda prevista para o período em estudo, conforme mostra a tabela a seguir. 
 
Mês Demanda (kg) 
Janeiro 9.600 
Fevereiro 10.600 
Março 12.800 
Abril 10.650 
Maio 11.640 
Junho 10.430 
 
Os dados de produção estão detalhados a seguir: 
 
Custo de produção regular R$ 1,50/kg 
Custo de subcontratação de terceiros R$ 2,00/kg 
 Pesquisa Operacional 1 – Notas de aula – Prof. Hélio Fuchigami ⬧ 9 
 
Custo de mão de obra regular R$ 600,00/homens-mês 
Custo de admissão de um operário R$ 1.000,00/operário 
Custo de demissão de um operário R$ 900,00/operário 
Custo por hora extra R$ 7,00/hora extra 
Custo de manutenção de estoques R$ 1,00/kg-mês 
Mão de obra regular no mês anterior 10 operários 
Estoque inicial 600 kg 
Produtividade média por funcionário 16 kg/homem-hora 
Produtividade média por hora extra 14 kg/homem-hora 
Capacidade máxima de produção subcontratada 1.000 kg/mês 
Capacidade máxima de mão de obra regular 20 operários 
Capacidade máxima de armazenagem 2.500 kg/mês 
 
Cada funcionário trabalha, regularmente, 6 horas úteis por dia, durante 20 dias úteis no 
mês, podendo fazer, no máximo, 20 horas extras por mês. Formule o modelo de 
planejamento agregado (programação inteira mista) que minimiza os custos totais de 
produção, mão de obra e estoques para o horizonte de tempo analisado, respeitando as 
restrições de capacidade do sistema. Implemente computacionalmente o modelo. [5] 
 
 
5. Problema de corte 
 
▪ Variantes do problema: corte unidimensional e bidimensional 
 
Exemplo: A Pacific Paper Company produz rolos de papel com uma largura de 20 pés 
cada. Pedidos específicos com larguras diferentes são produzidos pelo corte padronizado 
de rolos. Os pedidos típicos estão resumidos na tabela a seguir: 
 
Pedido 
Largura 
desejada (pés) 
Número de 
rolos desejado 
1 5 150 
2 7 200 
3 9 300 
 
Formule o modelo de programação linear para fazer as entregas destes pedidos de forma 
a minimizar a perda devida ao corte de rolos. [21] 
 
Dica: determine primeiro os padrões de corte possíveis. 
 
 
Exercício: Uma empresa produz barras de ferro padronizadas de 8 metros de 
comprimento. Um cliente necessita de barras de 2, 3 e 5 metros, nas quantidades 15, 10 
e 18, respectivamente. Elabore o modelo de programação linear para determinar como as 
barras de 8 metros serão cortadas de modo a minimizar a perda de material. [10] 
 
10 ⬧ Pesquisa Operacional 1 – Notas de aula – Prof. Hélio Fuchigami 
 
6. Problema da escala de funcionários 
 
Exemplo: A ZYB Correios e Malotes, uma franquia da ECT (Empresa de Correios e 
Telégrafos), deseja determinar o número de funcionários de horário integral que deve 
contratar para iniciar suas atividades. Para fazê-lo, recebeu uma tabela da ECT com o 
número mínimo de funcionários por dia da semana, que se encontra a seguir. 
 
Dia da semana Dom Seg Ter Qua Qui Sex Sáb 
Nº de funcionários 11 18 12 15 19 14 16 
 
O sindicato dos empregados de franqueadores dos correios mantém um acordo sindical 
que determina que cada empregado deve trabalhar cinco dias consecutivos e folgar em 
seguida dois dias (por exemplo, um funcionário que trabalha de segunda a sexta-feira, 
deve folgar no sábado e no domingo) e que as franquias devem ter apenas empregados 
com horário integral (não há subdivisão de turnos). Formule o problema de maneira a 
determinar o número total de empregados que a franquia deve contratar e o número de 
empregados por dia. [13] 
 
 
Exercício: Uma empresa de segurança tem vários contratos com casas de espetáculos e 
necessita de efetivos diferentes, por dias da semana, para o cumprimento desses 
contratos. Segundo levantamento da empresa, o número mínimo de empregados 
necessários diariamente é: 
 
Dia da semana Dom Seg Ter Qua Qui Sex Sáb 
Necessidade 
de pessoal 
780 386 450 680 790 980 1.100 
 
Considerando que o funcionário trabalhará cinco dias da semana e folgará os outros dois, 
a empresa necessita saber qual o número mínimo de empregados que deverá ser 
contratado para que possa atender aos seus contratos. Formule o modelo de 
programação linear. [17] 
 
 
7. Problema da mochila 
 
▪ Dentre n objetos possíveis, com respectivos pesos e utilidades, determinar quais 
devem ser carregados na mochila, respeitando-se sua capacidade máxima 
▪ O objetivo é maximizar a utilidade total, sujeita ao peso máximo permitido 
▪ Programação binária 
 
▪ Variantes do problema (knapsack problem): mochila 0-1, mochila inteira, 
múltiplas mochilas e empacotamento em mochilas (bin packing) [4] 
 
 Pesquisa Operacional 1 – Notas de aula – Prof. Hélio Fuchigami ⬧ 11 
 
Parâmetros do modelo: 
 cj = utilidade do objeto j 
 pj = peso do objeto j 
 C = capacidade (peso) da mochila 
 
Variáveis de decisão: 
 1, se o objeto j é carregado na mochila 
 0, caso contrário 
 
Formulação matemática: 

=
=
n
j
jj xcZ
1
max 
sujeito a 
 
.,...,1},1,0{
1
njx
Cxp
j
n
j
jj
=

= 
 
Exemplo: Um alpinista deseja escolher quais objetos carregar na mochila a fim de 
maximizar a sua utilidade. Para cada possível objeto, o alpinista atribui uma nota em 
função de sua utilidade, conforme mostra a tabela a seguir. O peso de cada objeto 
também está ilustrado na mesma tabela. O peso máximo que o alpinista pode carregar é 
de 5 kg. Modele o problema da mochila. [5] 
 
Objeto Utilidade Peso (g) 
Barra de cereal 6 200 
Casaco 7 400 
Tênis 3 400 
Celular 2 100 
Água 9 1.000 
Protetor solar 5 200 
Protetor labial 2 30 
Cilindro de oxigênio 10 3.000 
Máquina fotográfica 6 500 
 
Exercício: A empresa transportadora Translibert opera no trecho São Paulo – Ubatuba e 
está analisando pegar mais alguns passageiros durante o percurso, considerando o último 
ônibus que saiu do terminal. Há um total de oito passageiros aguardando, sendo que cada 
um deles percorrerá um trecho diferente, pagando por diferentes tarifas, conforme mostra 
a tabela a seguir. O peso dos passaeiros também deve ser considerado, já que um peso 
máximo de 280 kg pode ser adicionado, a fim de não ultrapassar a capacidade do ônibus 
em circulação. Formule o modelo para determinar quais passageiros devem ser 
selecionados, a fim de maximizar o lucro da empresa respeitando as restrições de 
capacidade. [5] 
 
xj = 
12 ⬧ Pesquisa Operacional 1 – Notas de aula – Prof. Hélio Fuchigami 
 
Passageiro 
Preço da 
passagem (R$) 
Peso (kg) 
1 48,00 80 
2 40,00 70 
3 52,00 84 
4 45,00 72 
5 55,00 90 
6 40,00 65 
7 30,00 50 
8 35,00 55 
 
 
8. Problema de seleção de projetos 
 
Exemplo: A ZYB Tecnologia tem de planejar seus gastos em Pesquisa e 
Desenvolvimento para os próximos cinco anos. A empresa pré-selecionou quatro projetos 
e deve escolher quais priorizar. Os dados relevantes ao problema encontram-se na tabela 
a seguir. Nela também temos a disponibilidade de capital a ser alocado em cada um dos 
anos, bem como o valor presente líquido de cada projeto. Como todos os projetos 
apresentam valor presente líquido (VPL) positivo, todos seriam candidatos. Vale notar que 
existe uma limitação no valor a ser investido anualmente. Formule o modelo matemático 
para determinar quais projetos devem ser selecionados para maximizar o VPL total. [13] 
 
Projeto 
VPL (8%) 
(mil R$) 
Capital requerido (mil R$) 
Ano 1 Ano 2 Ano 3 Ano 4 Ano 5 
1 105,99 70 15 0 20 20 
2 128,90 80 20 25 15 10 
3 136,14 90 20 0 30 20 
4 117,38 50 30 40 0 20 
Capital disponível (mil R$) 200 70 70 70 70 
 
 
9. Problema de cobertura 
 
▪ Cobertura de conjuntos (set covering problem): garantir a satisfação de um 
conjunto de restrições expressas como elementos de um conjunto 
 
Exemplo: A SouthWestern Airwaysprecisa alocar suas tripulações para cobrir todos os 
seus próximos voos. Iremos nos concentrar no problema de alocar três tripulações com 
base em São Francisco aos voos listados na primeira coluna da tabela a seguir. As outras 
12 colunas mostram as 12 sequências de voos possíveis para uma tripulação. Os 
números em cada coluna indicam a ordem dos voos. Exatamente três dessas sequências 
precisam ser escolhidas (uma por tripulação) de maneira que todos os voos sejam 
 Pesquisa Operacional 1 – Notas de aula – Prof. Hélio Fuchigami ⬧ 13 
 
cobertos. É permitido ter mais de uma tripulação em um voo, no qual as tripulações extras 
voariam como passageiros, porém acordos sindicais exigem que as tripulações extras 
precisem de qualquer maneira serem pagas pelo tempo que estiverem nesses voos como 
se estivessem trabalhando. O custo de designar uma tripulação a determinada sequência 
de voos é dado (em termos de milhares de dólares) na última linha da tabela. O objetivo é 
minimizar o custo total das alocações das três tripulações que cobrem todos os voos. 
Formule o modelo de programação inteira. [12] 
 
Voos 
Sequência de voos possíveis 
1 2 3 4 5 6 7 8 9 10 11 12 
1. São Francisco a Los Angeles 1 1 1 1 
2. São Francisco a Denver 1 1 1 1 
3. São Francisco a Seatle 1 1 1 1 
4. Los Angeles a Chicago 2 2 3 2 3 
5. Los Angeles a São Francisco 2 3 5 5 
6. Chicago a Denver 3 3 4 
7. Chicago a Seatle 3 3 3 3 4 
8. Denver a São Francisco 2 4 4 5 
9. Denver a Chicago 2 2 2 
10. Seatle a São Francisco 2 4 4 5 
11. Seatle a Los Angeles 2 2 4 4 2 
Custo em US$ 1.000 2 3 4 6 7 5 7 8 9 9 8 9 
 
 
Exercício: Para promover a segurança no campus, o Departamento de Segurança de 
uma universidade iniciou um processo de instalação de telefones de emergência em 
locais selecionados. O departamento quer instalar o número mínimo de telefones, 
contanto que cada uma das ruas principais do campus seja atendida por no mínimo um 
telefone. A figura a seguir mapeia as ruas principais (A a K) do campus. É lógico colocar 
os telefones em cruzamentos de ruas, de modo que cada telefone atenda no mínimo duas 
ruas. A mesma figura mostra que o layout das ruas requer um máximo de oito 
localizações de telefones. Formule o modelo para determinar qual o menor número e em 
quais locais devem ser instalados os telefones. [21] 
 
 
14 ⬧ Pesquisa Operacional 1 – Notas de aula – Prof. Hélio Fuchigami 
 
10. Problema de localização de facilidades 
 
▪ “Facilidade” (facilities): fábricas, centros de distribuição, portos, aeroportos, 
terminais 
▪ Determinar os locais ótimos dentre um conjunto de candidatos para a melhor 
distribuição dos produtos das facilidades para os clientes finais, de modo que as 
suas demandas sejam satisfeitas com o menor custo possível 
▪ Problema de fluxos em redes 
▪ Programação binária mista 
 
▪ Variantes do problema (com p facilidades): p-medianas (minimiza soma das 
distâncias), p-centros (minimiza distância máxima) e p-medianas capacitado 
(associa-se uma capacidade à cada facilidade instalada) 
 
Índices: 
 i = 1, ..., m: facilidades 
 j = 1, ..., n: consumidores 
 
Parâmetros do modelo: 
 cij = custo de transporte da localidade i para o consumidor j 
 fi = custo de manter a localidade i aberta 
 Ci = capacidade da localidade i 
 Dj = demanda do consumidor j 
 
Variáveis de decisão: 
 xij = quantidade transportada da localidade i para o consumidor j 
 1, se a localidade i for aberta 
 0, caso contrário 
 
Formulação matemática: 

== =
+=
m
i
ii
m
i
n
j
ijij yfxcZ
11 1
min 
sujeito a 
 
)4(.,...,1},1,0{
)3(,...,1,,...,1,0
)2(,...,1,
)1(,...,1,
1
1
miy
njmix
njDx
miyCx
i
ij
m
i
jij
ii
n
j
ij
=
==
==
=


=
=
 
 
 
yi = 
 Pesquisa Operacional 1 – Notas de aula – Prof. Hélio Fuchigami ⬧ 15 
 
A função objetivo minimiza a soma dos custos fixos de manutenção das localidades 
e dos custos de transporte. A restrição (1) garante que a capacidade máxima de cada 
localidade não seja excedida, obviamente, apenas se a localidade for aberta. A restrição 
(2) assegura que a demanda de cada consumidor seja atendida. E as expressões (3) e (4) 
expressam o domínio das variáveis de decisão. 
 
 
Exemplo: Uma empresa do setor alimentício está planejando abrir novas fábricas 
considerando cinco possibilidades: Manaus, Fortaleza, Vitória, Barueri e Curitiba. A partir 
das novas localidades, os produtos serão entregues para cinco consumidores finais: São 
Luís, Brasília, Belo Horizonte, Rio de Janeiro e São Paulo. Cada fábrica possui um custo 
fixo de manutenção e uma capacidade máxima, conforme mostra a tabela a seguir. Os 
custos de transporte por unidade transportada de cada fábrica para cada consumidor 
final, além da demanda dos consumidores, também estão detalhados na mesma tabela. A 
empresa quer determinar qual(is) fábrica(s) abrir, de modo a minimizar a soma dos custos 
fixos e de instalação e dos custos de transporte, garantindo que a demanda dos 
consumidores finais seja atendida. Modele o problema de localização de facilidades. [5] 
 
Custos de 
transporte 
Consumidores 
Custos 
fixos 
Capaci-
dade 
Localidades São Luís Brasília 
Belo 
Horizonte 
Rio de 
Janeiro 
São 
Paulo 
Manaus 0,82 0,95 1,10 1,33 1,22 111.000 35.000 
Fortaleza 0,74 1,12 1,06 1,13 1,24 124.000 30.000 
Vitória 1,34 1,24 0,72 0,72 0,88 120.00 25.000 
Barueri 1,48 1,26 0,95 0,95 0,70 135.000 30.000 
Curitiba 1,52 1,45 1,33 1,22 1,15 140.000 20.000 
Demanda 16.000 18.000 12.000 17.000 20.000 
 
 
Exercício: A Empresa Distribuidora Domus tem cinco entregas a fazer hoje. Ela deve 
fazer uma entrega de 1.000 kg ao cliente A, 2.000 kg ao cliente B, 3.000 ao cliente C, 
5.000 kg ao cliente D e 8.000 kg ao cliente E. Trata-se de cargas unitárias que devem ser 
transportadas numa única viagem. A empresa tem oferta de fretar quatro furgões: o 
furgão 1 tem capacidade de 2.000 kg, o furgão 2, de 6.000 kg, o furgão 3, de 8.000 kg, e o 
furgão 4, de 11.000 kg. O custo fixo de fretar cada furgão é $ 800, $ 1.100, $ 1.500 e $ 
1.800, respectivamente. Formule o modelo de programação inteira para determinar quais 
furgões fretar a custo mínimo, atendendo aos clientes e supondo que cada furgão só 
possa fazer uma única viagem, embora atendendo a mais de um cliente. [10] 
 
 
 
 
 
 
16 ⬧ Pesquisa Operacional 1 – Notas de aula – Prof. Hélio Fuchigami 
 
REFERÊNCIAS 
 
[1] ALVES, A.C.B.; MENEZES, M.A.F. Introdução à Pesquisa Operacional. Goiânia: PUC Goiás, 
2010. 
[2] ANDRADE, E.L. Introdução à Pesquisa Operacional: métodos e modelos para análise de 
decisões. Rio de Janeiro: LTC, 2015. 5ª ed. 
[3] ARAÚJO, S.A.; RANGEL, S. Matemática aplicada ao planejamento da produção e 
logística. Notas em Matemática Aplicada. SBMAC – Sociedade Brasileira de Matemática Aplicada 
e Computacional, 2014. 
[4] ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H. Pesquisa Operacional 
para cursos de Engenharia. Rio de Janeiro: Elsevier, 2015. 2ª ed. 
[5] BELFIORE, P.; FÁVERO, L.P. Pesquisa Operacional para cursos de Engenharia. Rio de 
Janeiro: Elsevier, 2013. 
[6] BELFIORE, P.; FÁVERO, L.P. Pesquisa Operacional para cursos de Administração, 
Contabilidade e Economia. Rio de Janeiro: Elsevier, 2012. 
[7] CAIXETA-FILHO, J.V. Pesquisa Operacional: técnicas de otimização aplicadas a sistemas 
agroindustriais. São Paulo: Atlas, 2004. 2ª ed. 
[8] COLIN, E.C. Pesquisa Operacional: 170 aplicações em Estratégia, Finanças, Logística, 
Produção, Marketing e Vendas. Rio de Janeiro: LTC, 2007. 
[9] CORRAR, L.J.; THEÓPHILO, C.R. (Coord.) Pesquisa Operacional para decisão em 
Contabilidade e Administração: Contabilometria. São Paulo: Atlas, 2004. 
[10] PIZZOLATO, N.D.; GANDOLPHO, A.A. Técnicas de Otimização. Rio de Janeiro: LTC, 2009. 
[11] GOLDBARG, M.C.; LUNA, H.P.L. Otimização Combinatória eProgramação Linear: 
modelos e algoritmos. Rio de Janeiro: Elsevier, 2005. 
[12] HILLIER, F.S.; LIEBERMAN, G.J. Introdução à Pesquisa Operacional. Porto Alegre: 
McGraw Hill, 2010. 8ª ed. 
[13] LACHTERMACHER, G. Pesquisa Operacional na tomada de decisões. São Paulo: 
Pearson Prentice Hall, 2009. 
[14] LOESCH, C.; HEIN, N. Pesquisa Operacional: fundamentos e modelos. São Paulo: Saraiva, 
2009. 
[15] MOREIRA, D.A. Pesquisa Operacional: curso introdutório. São Paulo: Cengage Learning, 
2010. 2ª ed. 
[16] MURTY, K.G. Linear programming. New York: John Wiley & Sons, 1983. 
[17] PASSOS, E.J.P.F. Programação Linear como instrumento da Pesquisa Operacional. São 
Paulo: Atlas, 2008. 
[18] RAGSDALE, C.T. Modelagem e Análise de Decisão. São Paulo: Cengage Learning, 2009. 
[19] SILVA, E.M.; SILVA, E.M.; GONÇALVES, V.; MUROLO, A.C. Pesquisa Operacional para os 
cursos de Administração e Engenharia. São Paulo: Atlas, 2010. 4ª ed. 
 Pesquisa Operacional 1 – Notas de aula – Prof. Hélio Fuchigami ⬧ 17 
 
[20] SOUZA, M.J.F. Otimização Combinatória. Notas de aula – Departamento de Computação, 
Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto, 2009. 
[21] TAHA, H.A. Pesquisa Operacional: uma visão geral. São Paulo: Pearson Prentice Hall, 
2008. 8ª ed. 
[22] VANDERBEI, R.J. Linear programming: foundations and extensions. New York: Springer, 
2001. 2nd ed. 
[23] YOSHIDA, L.K. Métodos quantitativos: programação linear. São Paulo: Atual, 1987.