pesquisa operacional

Prévia do material em texto

Andre´a Cardoso
Fundamentos da
PESQUISA OPERACIONAL
UNIFAL-MG
Fevereiro 2011
SUMA´RIO
1 Conhecendo a Pesquisa Operacional 4
1.1 Modelos Matema´ticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Primeiros Exemplos e Aplicac¸o˜es . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Lista de Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2 Programac¸a˜o Matema´tica 24
2.1 Modelos de Otimizac¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2 Problemas de Programac¸a˜o Matema´tica . . . . . . . . . . . . . . . . . . . 28
2.3 Lista de Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3 Programac¸a˜o Linear 44
3.1 Estruturac¸a˜o de Modelos Lineares . . . . . . . . . . . . . . . . . . . . . . . 45
3.2 Resoluc¸a˜o Gra´fica de um PPL . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2.1 Representac¸a˜o Gra´fica das Restric¸o˜es . . . . . . . . . . . . . . . . . 48
3.2.2 Representac¸a˜o Gra´fica da Func¸a˜o Objetivo . . . . . . . . . . . . . . 54
3.2.3 Soluc¸o˜es do Modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.3 Lista de Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4 Resoluc¸a˜o de PPL 64
4.1 Estruturac¸a˜o de Modelos Lineares . . . . . . . . . . . . . . . . . . . . . . . 64
4.2 Fundamentac¸a˜o Teo´rica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.3 Lista de Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
2
5 O Me´todo Simplex 79
5.1 Fluxograma para soluc¸o˜es finitas . . . . . . . . . . . . . . . . . . . . . . . 91
5.2 Ana´lise de Sensibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.3 Lista de Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.4 Lista de Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
CAP´ITULO 1
CONHECENDO A PESQUISA OPERACIONAL
O termo Pesquisa Operacional (PO) designa uma a´rea do conhecimento que consiste no
desenvolvimento de me´todos cient´ıficos de sistemas complexos, com a finalidade de prever
e comparar estrate´gias ou deciso˜es alternativas, cujo objetivo e´ dar suporte a` definic¸a˜o de
pol´ıticas e determinac¸a˜o de ac¸o˜es.
O trabalho do matema´tico russo Leonid Kantorovich de 1939 intitulado “Me´todos
matema´ticos na organizac¸a˜o e no planejamento de produc¸a˜o” e´ considerado um dos pre-
cursores da PO, pore´m manteve-se desconhecido da comunidade cient´ıfica ocidental ate´
1959. O pro´prio termo Pesquisa Operacional, do ingleˆs Operations Research, foi cunhado
pelo matema´tico russo na tentativa de englobar, sob uma u´nica denominac¸a˜o, todas as
te´cnicas existentes ou que viriam a ser desenvolvidas e que tinham o mesmo objetivo
citado. De fato, o termo PO designa um conjunto de disciplinas isoladas tais como Pro-
gramac¸a˜o Linear, Teoria das Filas, Simulac¸a˜o, Programac¸a˜o Dinaˆmica, Teoria dos Jogos,
dentre outras.
A Pesquisa Operacional tal qual como a conhecemos surgiu durante a Segunda Guerra
Mundial tendo como objetivo o desenvolvimento de metodologia para soluc¸a˜o de prob-
lemas relacionados com as operac¸o˜es militares quando os Aliados se viram confrontados
com problemas complexos de natureza log´ıstica, ta´tica e de estrate´gia militar. Para apoiar
os comandos operacionais na resoluc¸a˜o desses problemas foram criados grupos multidis-
ciplinares compostos por matema´ticos, f´ısicos, engenheiros e cientistas sociais. O que
esses cientistas fizeram foi aplicar o me´todo cient´ıfico, que ta˜o bem conheciam, aos pro-
blemas que lhes foram sendo colocados. Desenvolveram enta˜o a ide´ia de criar modelos
4
5
matema´ticos, apoiados em dados e fatos, que lhes permitissem perceber os problemas em
estudo, simular e avaliar o resultado hipote´tico de estrate´gias bem como propor deciso˜es
alternativas. Em 1941 a Inglaterra inaugura a Sec¸a˜o de Pesquisa Operacional do Co-
mando da Forc¸a Ae´rea de Combate para trabalhar com problemas de operac¸o˜es de guerra,
manutenc¸a˜o e inspec¸a˜o de avio˜es, melhoria da probabilidade de destruic¸a˜o de submarinos,
controle de artilharia antiae´rea, dimensionamento de comboios de frota, entre outros.
O sucesso e credibilidade ganhos durante a guerra foram ta˜o grandes que, terminado o
conflito, esses grupos de cientistas e a sua nova metodologia de abordagem dos problemas
se transferiram para as empresas que, com o vertiginoso crescimento econoˆmico que se
seguiu, se viram tambe´m confrontadas com problemas de decisa˜o de grande complexidade.
Em 1947 os Estados Unidos implantam o projeto SCOP (Scientific Computation of Op-
timal Programs) com o objetivo de apoiar deciso˜es de operac¸o˜es da forc¸a ae´rea americana,
coordenado por um economista e por um matema´tico George Dantzig que desenvolveu e
formalizou o Me´todo Simplex para resolver problemas de otimizac¸a˜o linear.
Face ao seu cara´ter multidisciplinar, atualmente as contribuic¸o˜es da PO estende-se
por praticamente todos os domı´nios da atividade humana, da Engenharia a` Medicina,
passando pela Economia e a` Gesta˜o Empresarial.
Os ramos mais importantes desenvolvidos em PO sa˜o:
Programac¸a˜o Matema´tica Outros Ramos
X Programac¸a˜o Linear X Ana´lise Estat´ıstica
X Programac¸a˜o Na˜o Linear X Teoria dos Jogos
X Programac¸a˜o Dinaˆmica X Teoria das Filas
X Programac¸a˜o Inteira X Simulac¸a˜o
X Otimizac¸a˜o Global X Gesta˜o de estoques
Resumidamente podemos dizer que o objetivo principal da PO e´ determinar a pro-
gramac¸a˜o otimizada de atividades ou recursos, fornecendo um conjunto de procedimentos
e me´todos quantitativos para tratar de forma sistematizada problemas que envolvam a
utilizac¸a˜o de recursos escassos. Para apoiar a tomada de decisa˜o, a PO busca a soluc¸a˜o
de problemas que podem ser representados por modelos matema´ticos.
De modo geral, para a resoluc¸a˜o de um problema, um estudo de PO e´ desenvolvido
em fases como indicado no esquema abaixo.
6 CAPI´TULO 1. CONHECENDO A PESQUISA OPERACIONAL
Figura 1.1: Passos para implementac¸a˜o de PO
Identificado o problema a ser estudado, a fase de formulac¸a˜o consiste na estruturac¸a˜o
dos dados e informac¸o˜es dispon´ıveis, a pro´xima fase de modelagem concentra-se na cons-
truc¸a˜o do modelo que e´ uma representac¸a˜o simplificada do sistema, em geral descrito
por um conjunto de equac¸o˜es e desigualdades matema´ticas. A soluc¸a˜o e´ obtida atrave´s
de um me´todo que pode ser um procedimento matema´tico ou algoritmo para alcanc¸ar o
resultado. A avaliac¸a˜o consiste na validac¸a˜o do modelo, nesta fase ajustes podem ser
feitos. A decisa˜o e´ a escolha e operacionalizac¸a˜o da soluc¸a˜o encontrada.
As fases de formulac¸a˜o e modelagem do problema devem ser executadas com muita
responsabilidade pois “E´ muito dif´ıcil encontrar uma soluc¸a˜o certa para um problema mal
formulado!”.
1.1 Modelos Matema´ticos
Observar, compreender, reproduzir e aprimorar fenoˆmenos, que podem ser naturais, soci-
ais ou econoˆmicos, tem sido desde sempre uma preocupac¸a˜o ba´sica da Cieˆncia. Eventual-
mente tais fenoˆmenos podem ser controla´veis e havera´ enta˜o condic¸o˜es de realizar previso˜es
com pequeno n´ıvel de incerteza, para tanto e´ necessa´ria a construc¸a˜o de modelos que sa˜o
representac¸o˜es idealizadas para tais fenoˆmenos, processos ou sistemas.
Um modelo descreve, representa e imita o procedimento que ocorre no mundo real, es-
tabelecendo o relacionamento das varia´veis com os objetivos, da melhor maneira poss´ıvel,
obedecendo a` limitac¸a˜o de tempo e de custo. Os modelos podem ser assim classificados:
1.1. MODELOS MATEMA´TICOS 7
verbais: quando sa˜o descritos e representados por palavras e sentenc¸as.
f´ısicos: quando representadospor algum tipo de material concreto, alterando-se suas
dimenso˜es, formato e custo. Por exemplo: maquetes e proto´tipos.
esquema´ticos: quando descritos por meio de gra´ficos, tabelas ou diagramas.
matema´ticos: quando representados por relac¸o˜es matema´ticas, como equac¸o˜es, inequa-
c¸o˜es, func¸o˜es ou lo´gica simbo´lica.
Um modelo matema´tico e´ uma representac¸a˜o simplificada de uma situac¸a˜o real e deve
refletir a esseˆncia do problema, representando as grandezas envolvidas por varia´veis e as
relac¸o˜es de interdependeˆncia existentes entre elas por expresso˜es matema´ticas. Esquemati-
camente, um modelo matema´tico pode ser visto como uma Caixa Preta, representando as
relac¸o˜es que descrevem a dependeˆncia das varia´veis, que recebe a entrada formada pelas
varia´veis do problema que se quer otimizar e processa essas informac¸o˜es para produzir a
sa´ıda que e´ a soluc¸a˜o do problema ou resultado da decisa˜o.
Entrada SaídaModelo
Matemático
O modelo mais adequado depende de va´rios fatores: a natureza das relac¸o˜es entre
as varia´veis, os objetivos almejados, a extensa˜o do controle sobre as varia´veis e o n´ıvel
de incerteza existente tanto nas relac¸o˜es entre as varia´veis como na pro´pria definic¸a˜o
das varia´veis. Para cada conjunto de situac¸o˜es espec´ıficas o modelo matema´tico, dora-
vante denominado somente modelo, devera´ ter uma forma padronizada e a soluc¸a˜o podera´
ser obtida por me´todos matema´ticos espec´ıficos para cada caso, que sera˜o estudados
posteriormente.
De maneira geral, um problema de tomada de decisa˜o requer soluc¸a˜o que responda a
treˆs perguntas:
1. Qual e´ a meta a ser atingida? (objetivo)
2. Quais sa˜o as alternativas para a decisa˜o? (varia´veis de decisa˜o)
3. Sob quais condic¸o˜es a decisa˜o deve ser tomada? (restric¸o˜es)
8 CAPI´TULO 1. CONHECENDO A PESQUISA OPERACIONAL
1.2 Primeiros Exemplos e Aplicac¸o˜es
Nesta sec¸a˜o sera˜o apresentadas os primeiras formulac¸o˜es de problemas de otimizac¸a˜o como
aux´ılio na tomada de decisa˜o, para serem analisados, modelados e, exceto o sexto exemplo,
resolvidos. Os treˆs primeiros exemplos sa˜o bem simples e podem ser resolvidos intuitiva-
mente ou por enumerac¸a˜o na˜o necessitando de modelos matema´ticos formais. O quarto
problema requer o uso de planilhas eletroˆnicas para realizar simulac¸o˜es de maneira mais
ra´pida e eficaz. O quinto problema necessita de conhecimentos pre´vios de Ca´lculo Diferen-
cial. O sexto exemplo, e´ um pouco mais complexos e necessita de modelos matema´ticos
estruturados de Programac¸a˜o Matema´tica assunto do cap´ıtulo seguinte cujas te´cnicas de
resoluc¸a˜o sera˜o estudadas no cap´ıtulo 3. Finalmente, o se´timo exemplo apresenta um
problema cla´ssico da Teoria dos Jogos e suas implicac¸o˜es.
. . . Exemplo 1.1. O problema da dona-de-casa 1
Considere a situac¸a˜o em que uma dona de casa precisa decidir entre comprar manteiga
ou margarina para o consumo da famı´lia. Ela vai seguir intuitivamente um racioc´ınio
lo´gico atrave´s do qual procurara´ alinhar as vantagens e desvantagens de cada alternativa,
segundo seus crite´rios de decisa˜o.
De in´ıcio, a dona de casa ira´ identificar as diferenc¸as entre os produtos segundo va´rios
fatores que poderiam ser tomados para comparac¸a˜o como: o custo, o sabor, a durabilidade,
a consisteˆncia quando gelado, os efeitos para sau´de, dentre outros. Para simplificar, ela se
limitara´ a avaliar apenas os itens que considera mais importantes: custo, sabor e efeitos
para a sau´de. Esses sera˜o os crite´rios para a tomada de decisa˜o da dona-de-casa.
As consequencias de cada alternativa sera˜o:
1. Comprando manteiga, a dona-de-casa
• gasta mais dinheiro;
• agrada a famı´lia;
• po˜e em risco a famı´lia devido ao teor mais alto de colesterol.
2. Comprando margarina, a dona-de-casa
• economiza dinheiro;
• desagrada a famı´lia;
• na˜o coloca em risco a sau´de da famı´lia.
1Extra´ıdo de Andrade, 2004
1.2. PRIMEIROS EXEMPLOS E APLICAC¸O˜ES 9
Dependendo do peso que atribuir a cada consequencia, a dona-de-casa podera´ chegar
a uma conclusa˜o. Se, por exemplo, a restric¸a˜o da famı´lia for dinheiro, a decisa˜o que lhe
parecera´ melhor sera´ comprar margarina.
. . . Exemplo 1.2. Problema da travessia do rio
Imagine que voceˆ esteja a margem leste de um rio juntamente com treˆs amigos Felipe,
Joa˜o e Kelly. Voceˆs querem atravessar para a margem oeste e dispo˜em de um u´nico meio
de locomoc¸a˜o, uma canoa que pode levar no ma´ximo duas pessoas por vez e na˜o pode
ir nem voltar vazia. Voceˆ tem constituic¸a˜o mais atle´tica e pode atravessar o rio a remo
em 1 minuto, enquanto Felipe, Joa˜o e Kelly levam 2, 5 e 10 minutos, respectivamente.
Se houver duas pessoas na canoa, o tempo da travessia sera´ a me´dia dos tempos que
seriam gastos individualmente. Apo´s duas travessias seguidas a pessoa fica cansada e leva
o dobro do tempo para atravessar o rio. Como e´ mais conveniente realizar a travessia de
modo que os quatro estejam do outro lado do rio no menor tempo poss´ıvel?
As seguintes alternativas podem ser consideradas:
1. Ir voceˆ e Felipe, voceˆ volta pega Joa˜o, voceˆ volta e pega Kelly.
2. Ir voceˆ e Felipe, Felipe volta pega Joa˜o, voceˆ volta e pega Kelly.
3. Ir voceˆ e Felipe, voceˆ volta vai Joa˜o e Kelly, Felipe volta e pega voceˆ.
Calculando os tempos gastos em cada uma das alternativas, temos:
T1 = 1, 5 + 1 + 3, 5 + 2 + 6 = 14 min
T2 = 1, 5 + 2 + 4, 5 + 1 + 5, 5 = 14, 5 min
T3 = 1, 5 + 1 + 7, 5 + 2 + 1, 5 = 13, 5 = 13, 5 min
Dentre as treˆs alternativas, a melhor e´ a alternativa 3, onde o tempo total para a
travessia sera´ de 13,5 minutos. Voceˆ pode identificar alternativas distintas cujo tempo
seja igual a 13,5 minutos? Existe outra alternativa melhor?
Varia´veis de decisa˜o: Alternativas 1, 2 e 3
10 CAPI´TULO 1. CONHECENDO A PESQUISA OPERACIONAL
Objetivo: Minimizar o tempo de travessia
Restric¸o˜es: Tempo individual para travessia,
Duas pessoas por vez na canoa,
A canoa na˜o atravessa o rio sozinha,
Penalidade para atravessar mais que duas vezes seguidas.
. . . Exemplo 1.3. Decisa˜o com risco ou incerteza 2
A tabela seguinte apresenta os retornos (ganhos ou perdas me´dias) para um valor fixo
de insvetimento associados a`s deciso˜es de investir em conta poupanc¸a, em do´lar ou fundos
de investimentos.
Decisa˜o A1 Decisa˜o A2 Decisa˜o A3
Estados poss´ıveis Probabilidades Investir em Investir em Investir em
da economia poupanc¸a do´lar fundos
S1 : Recessa˜o 0,40 $ 300 $ 400 - $ 100
S2 : Estabilidade 0,40 $ 300 $ 300 $ 200
S3 : Expansa˜o 0,20 $ 300 $ 200 $ 700
Qual e´ o melhor investimento?
Se a decisa˜o for baseada nos valores me´dios ou esperados dos ganhos, teremos:
GA1 = 0, 40× 300 + 0, 4× 300 + 0, 2× 300 = 300
GA2 = 0, 40× 400 + 0, 4× 300 + 0, 2× 200 = 320
GA3 = 0, 40× (−100) + 0, 4× 200 + 0, 2× 700 = 180
a melhor decisa˜o a ser tomada e´ a alternativa A2, investir em do´lar.
Varia´veis de decisa˜o: Investir em A1, A2 ou A3
Objetivo: Maximizar o retorno
Restric¸o˜es: Estados poss´ıveis da economia, probabilidades e retornos.
2Baseado em Shimizu, 2006
1.2. PRIMEIROS EXEMPLOS E APLICAC¸O˜ES 11
. . . Exemplo 1.4. O caso da Casa das Esfirras
A Casa das Esfirras produz e comercializa esfirras de carne a partir de dois ingredientes
ba´sicos: massa e recheio. A empresa necessita estabelecer um modelo para simulac¸a˜o de
lucros que lhe permita a formac¸a˜o do melhor prec¸o de venda a ser praticado. Considera-se
que o prec¸o unita´rio da esfirra e o prec¸o me´dio praticado pela concorreˆncia sa˜o os u´nicos
fatores relevantes na determinac¸a˜o da demanda. Atualmente a empresa pratica o mesmo
prec¸o me´dio do mercado local e comercializa 70.000 unidades de esfirras mensalmente.
Um estudo encomendadopela empresa constatou que, a cada 1% a menos cobrado pela
unidade de esfirra em relac¸a˜o ao prec¸o me´dio praticado pela concorreˆncia implica em um
aumento nas vendas de 5.000 unidades mensais.
Dados relevantes para o estudo sa˜o fornecidos na tabela seguinte:
em R$
Prec¸o me´dio praticado pela concorreˆncia (por unidade) 1,00
Custo unita´rio da massa 0,10
Custo unita´rio do recheio 0,30
Custo do processo de fabricac¸a˜o (por unidade) 0,40
Custo fixo 8.000,00
Varia´veis de decisa˜o: Prec¸o unita´rio da esfirra
Objetivo: Maximizar o lucro
Restric¸o˜es: Demanda de mercado
Para este problema, e´ preciso desenvolver um modelo que permita a simulac¸a˜o do lucro
operacional mensal a partir da demanda d e dos custos para estabelecer o prec¸o p a ser
praticado.
O lucro (L) e´ obtido pela diferenc¸a entre a receita (R) e o custo total (CT),
L = R− CT.
12 CAPI´TULO 1. CONHECENDO A PESQUISA OPERACIONAL
A receita pode ser calculada pelo produto entre o prec¸o praticado por unidade e a
quantidade vendida, neste caso a quantidade demandada, que por sua vez depende do
prec¸o praticado. Assim,
R(p) = p · d(p).
O custo total e´ a soma do custo fixo com o custo varia´vel, que depende da quantidade
a ser produzida, neste caso a demanda.
CT = C + C(d)
Para construir um modelo para formac¸a˜o de prec¸o, e´ primeiro necessa´rio calcular a
func¸a˜o demanda, isto e´, encontrar a lei que determina a quantidade de esfirras comercia-
lizadas mensalmente em func¸a˜o do prec¸o praticado.
De acordo com os dados, o prec¸o me´dio praticado e´ de R$ 1,00 e para este valor a
quantidade demandada e´ 70.000 unidades. Assim a func¸a˜o d(p) a ser determinada satisfaz:
d(1) = 70000.
Levando-se em conta que a cada desconto de 1% no prec¸o corresponde uma demanda
extra de 5.000 unidades, temos:
d(0, 99) = 75000.
Admitindo que a func¸a˜o demanda seja uma func¸a˜o afim do tipo:
d(p) = ap+ b
onde o coeficiente angular a pode ser determinado por:
a =
∆d
∆p
=
70000− 75000
1− 0, 99 = −500000
Para encontrar o coeficiente linear b e determinar d, basta substituir d(1) = 70000 na
1.2. PRIMEIROS EXEMPLOS E APLICAC¸O˜ES 13
expressa˜o d(p) = −500000p+ b, desta forma
70000 = d(1) = −500000(1) + b
Logo,
b = 570000.
Portanto, a func¸a˜o demanda nas condic¸o˜es do problema e´:
d(p) = −500000p+ 570000
Para este caso o modelo sera´ constru´ıdo em planilha eletroˆnica alcanc¸ando assim fa-
cilidade de interac¸a˜o com o usua´rio e possibilitando ra´pidas alterac¸o˜es. Admitindo que o
prec¸o praticado seja R$ 1,00 a unidade de esfirras, e´ poss´ıvel calcular a quantidade ven-
dida, a receita e os custos mensais e consequente prever o lucro operacional. O modelo em
planilha eletroˆnica e´ apresentado na tabela abaixo, onde as fo´rmulas para os respectivos
ca´lculos esta˜o explicitadas na coluna C.
Na tabela a seguir sa˜o apresentados os resultados do Lucro Operacional para diversos
valores simulados para o prec¸o a ser praticado, onde lucro negativo e´ representado por
valores entre pareˆnteses.
14 CAPI´TULO 1. CONHECENDO A PESQUISA OPERACIONAL
Uma ra´pida inspec¸a˜o garante que:
• Prec¸o acima de 1,00 retorna em lucro menor;
• Lucro crescente para valores entre 1,00 e 0,95;
• Lucro decrescente para valores entre 0,95 e 0,90.
Desta primeira ana´lise, conclui-se que o melhor prec¸o esta´ entre 1,00 e 0,95. Para
decidir qual prec¸o retorna o maior lucro, e´ preciso simular todos os valores neste intervalo.
Observando a segunda parte da tabela, conclu´ımos que o melhor prec¸o a ser praticado e´
R$ 0,97 resultando num lucro de R$ 6.450,00 que e´ 7,5% maior do que o lucro mensal
atual da empresa.
. . . Exemplo 1.5. Gesta˜o do estoque
Um posto de combust´ıveis tem uma demanda de gasolina e a´lcool ao longo dos u´ltimos
treˆs anos, conforme a tabela dada em milho˜es de litros:
1.2. PRIMEIROS EXEMPLOS E APLICAC¸O˜ES 15
Ano A´lcool Gasolina
2007 2,00 5,00
2008 2,05 5,80
2009 3,00 6,20
Seus custos estimados de colocac¸a˜o de um pedido sa˜o cerca de R$ 325,00 e os custos de
manutenc¸a˜o dos estoques sa˜o de 23% do custo de aquisic¸a˜o, por ano. A empresa adquire
os combust´ıveis a R$ 30,00 o gala˜o de 50 litros de a´lcool e R$ 78,00 o gala˜o de gasolina.
Atualmente o suprimento de combust´ıvel e´ feito em quantidades constantes a intervalos
regulares quinzenalmente, qual a quantidade ideal de cada combust´ıvel que o posto deve
pedir por vez?
O objetivo do problema e´ determinar o lote de compra que deve ser encomendado
por vez, de modo a minimizar o custo total de operac¸a˜o do estoque dos dois tipos de
combust´ıveis.
Varia´veis de decisa˜o: Quantidade de a´lcool a ser encomentada por vez
Quantidade de gasolina a ser encomendada por vez
Objetivo: Minimizar o custo de operac¸a˜o de estoque
Restric¸o˜es: Custo do pedido
Custo de Manutenc¸a˜o do estoque
O custo total e´ a soma dos custos de manutenc¸a˜o de estoques e de emissa˜o e colocac¸a˜o
de pedidos, considerando que a demanda e os custos sa˜o relativamente esta´veis durante o
ano.
minimizar Custo Total (CT) = custo de manutenc¸a˜o do a´lcool (CMA) +
+ custo de manutenc¸a˜o da gasolina (CMG) +
+ custo do pedido (CP)
O custo de manutenc¸a˜o e´ o produto do n´ıvel me´dio em estoque pelo custo unita´rio
de manutenc¸a˜o, onde o n´ıvel me´dio e´ a metade da quantidade encomendada (dados
16 CAPI´TULO 1. CONHECENDO A PESQUISA OPERACIONAL
emp´ıricos). O custo do pedido e´ o produto do nu´mero de pedidos anuais pelo custo
unita´rio de colocac¸a˜o do pedido.
Devemos identificar os elementos conhecidos e desconhecidos do problema que fornecera˜o
os dados e as varia´veis de decisa˜o.
n: total de pedidos anuais
qA: quantidade de a´lcool (em milho˜es de litros) encomendados por vez
qG: quantidade de gasolina (em milho˜es de litros) encomendados por vez
aA: quantidade de a´lcool (em milho˜es de litros) comercializada anualmente
aG: quantidade de gasolina (em milho˜es de litros) comercializada anualmente
A partir dos dados fornecidos, podemos calcular a me´dia de vendas da empresa dos
u´ltimos treˆs anos:
aA =
2 + 2, 05 + 3
3
= 2, 35
e
aG =
5 + 5, 8 + 6, 2
3
∼= 5, 67
E´ poss´ıvel obter qA e qG a partir do valor de n.
qA =
aA
n
e
qG =
aG
n
Portanto, podemos admitir que a u´nica varia´vel independente do problema e´ o nu´mero
de pedidos anuais n.
Sabe-se que o custo de manutenc¸a˜o dos estoques e´ de 23% do custo de aquisic¸a˜o de
cada combust´ıvel. A partir desta informac¸a˜o e´ poss´ıvel calcular CMA, considerando que
a unidade que estamos utilizando e´ um milha˜o de litros de combust´ıvel que equivale a
20.000 galo˜es de 50 litros, como cada gala˜o de a´lcool custa R$ 30,00, o custo da unidade
1.2. PRIMEIROS EXEMPLOS E APLICAC¸O˜ES 17
de a´lcool e´ R$ 600.000,00. Calculando a porcentagem para manutenc¸a˜o dos estoques,
temos que o custo unita´rio para manutenc¸a˜o do a´lcool e´ 138.000 e portanto,
CMA = 138.000
qA
2
= 69.000qA
De forma ana´loga calculamos que o custo da unidade de gasolina e´ R$ 1.560.000,00
e obtemos 358.800 como o custo unita´rio para manutenc¸a˜o do estoque de gasolina e
consequentemente:
CMG = 358.800
qG
2
= 179.400qG
Escrevendo o custo total em func¸a˜o das varia´veis e constantes assim definadas e cal-
culadas:
CT = 69.000qA + 179.400qG + 325n
= 69.000
2, 35
n
+ 179.400
5, 67
n
+ 325n
= 162.150
1
n
+ 1.017.198
1
n
+ 325n
Portanto,
CT (n) = 1.179.348
1
n
+ 325n
Como o objetivo e´ minimizar uma func¸a˜o em uma varia´vel real, devemos encontrar os
pontos cr´ıticos da func¸a˜o utilizando a primeira derivada.
d
dn
CT (n) = −1.179.348 1
n2
+ 325 = 0
A equac¸a˜o diferencial acima e´ satisfeita para n ∼= 60, 24ou n ∼= −60, 24. Entretanto
no contexto do problema proposto n deve ser um nu´mero inteiro positivo, sendo assim
tomamos, por arredondamento, n = 60. E o teste da segunda derivada nos garante que
este e´ um ponto de mı´nimo.
d2
dn2
CT (n) = 2.358.696
1
n3
> 0, ∀ n > 0
Assim, deve-se encomendar 39.166,67 litros de a´lcool e 94.500 litros de gasolina por
18 CAPI´TULO 1. CONHECENDO A PESQUISA OPERACIONAL
vez totalizando 60 pedidos anuais com custo total de R$ 39.155,80 contra os custos atuais
de R$ 53.809,54 referentes a 26 pedidos anuais, o que representa uma economia para a
empresa de aproximadamente 27,21%.
. . . Exemplo 1.6. Problema da dieta o´tima: 3
Em uma dieta, cada 100 g de alimento A e B fornecem os seguintes elementos nutritivos
(em unidades):
Elemento nutritivo A B
Carboidratos 1 3
Vitaminas 3 4
Prote´ınas 3 1
As quantidade mı´nimas necessa´rias de elementos nutritivos, por dia, sa˜o 8 unidades de
carboidratos, 19 unidades de vitaminas e 7 unidades de prote´ınas. Cada 100 g do alimento
A conte´m 300 kcal (kilocalorias) e custa $ 50 u.m. enquanto cada 100 g do alimento B tem
500 kcl e custa $ 25 u.m. Como e´ poss´ıvel minimizar o custo e a quantidade de calorias
da dieta formada pelos alimento A e B?
Varia´veis de decisa˜o: x1 : quantidade de A (em 100 g)
x2 : quantidade de B (em 100 g)
Objetivo: min z1 = 50x1 + 25x2 (minimizar o custo)
min z2 = 300x1 + 500x2 (minimizar quantidade de calorias)
Restric¸o˜es:

x1 + 3x2 ≥ 8 (quantidade de carboidratos)
3x1 + 4x2 ≥ 19 (quantidade de vitaminas)
3x1 + x2 ≥ 7 (quantidade de prote´ınas)
x1, x2 ≥ 0 (condic¸a˜o de na˜o-negatividade)
3Adaptado do exemplo inicialmente formulado por George Dantzig
1.2. PRIMEIROS EXEMPLOS E APLICAC¸O˜ES 19
Representando as inequac¸o˜es e func¸o˜es do problema no plano cartesiano obtemos o
seguinte gra´fico.
Por simples inspec¸a˜o visual e´ poss´ıvel identificar o ponto (1,4) do plano cartesiano
como sendo o ponto onde a func¸a˜o custo e´ minimizada, obtendo um custo mı´nimo de
$ 150 u.m. com consumo total de 2.300 kcal, enquanto o ponto (5,1) minimiza a quantidade
de calorias, 2.000 kcal, com custo de $ 275 u.m.
. . . Exemplo 1.7. O dilema do prisioneiro 4
Dois prisioneiros acusados de terem cometido um crime em conjunto esta˜o presos em
celas separadas e sa˜o interrogados separadamente por um delegado de pol´ıcia. Se os dois
prisioneiros confessarem o crime, ambos sera˜o condenados a` pena de 10 anos de prisa˜o.
Se nenhum dos dois prisioneiros confessar, o delegado, usando provas circunstanciais, so´
pode condena´-los a` pena de 2 anos. Se apenas um dos dois prisioneiros confessar, este
prisioneiro recebera´, como preˆmio, um pena leve de 1 ano de prisa˜o, e o outro, que na˜o
confessou, sera´ condenado a` pena maior, de 12 anos de prisa˜o. Qual decisa˜o deve ser
tomada?
4Proposto originalmente por M.Flood e M.Dresher em 1950, posteriormente adaptado por A.W.Tucker.
20 CAPI´TULO 1. CONHECENDO A PESQUISA OPERACIONAL
A tabela seguinte resume as penalidades atribuidas a cada prisioneiro
Prisioneiro B
C NC
C (10, 10) (1,12)
Prisioneiro A NC (12,1) (2,2)
onde a primeira entrada do par ordenado corresponde a` decisa˜o do prisioneiro A e a
segunda entrada a` decisa˜o do prisioneiro B.
Examinemos o problema do ponto de vista de um dos prisioneiros, objetivando deter-
minar a melhor estrate´gia assumindo que o cu´mplice tambe´m e´ racional.
Se seu companheiro confessar, o prisioneiro A, por exemplo, sera´ condenado a 10 anos
de prisa˜o se confessar e a 12 anos se permanecer calado. Neste caso a melhor decisa˜o e´
confessar. Agora, se B permanecer calado, A sera´ condenado a 1 ano se confessar e a 2
anos se na˜o confessar. O melhor estrate´gia nesta situac¸a˜o e´ confessar.
Aparentemente a melhor estrate´gia e´ portanto confessar! Entretanto se ambos seguirem
o mesmo racioc´ınio, os dois prisioneiros sera˜o condenados a 10 anos de prisa˜o. Se optarem
por cooperar e permanecerem calados, recebera˜o pena menor de 2 anos. E a´ı esta´ o dilema,
buscando individualmente a melhor estrate´gia para si acabam ambos por serem punidos
rigorosamente. O fato e´ que pode haver dois vencedores neste jogo, se o problema for
analisado em conjunto buscando a melhor soluc¸a˜o para o grupo e consequentemente a
cooperac¸a˜o resultara´ na melhor soluc¸a˜o para ambos.
“A teoria dos jogos sugere que,
embora a cooperac¸a˜o na˜o seja nada fa´cil de ser alcanc¸ada,
e´ poss´ıvel demonstrar que muitas vezes ela e´ prefer´ıvel ao conflito.”
David P. Barash
1.3. LISTA DE PROBLEMAS 21
1.3 Lista de Problemas
Resolva cada um dos seguintes problemas, identificando as varia´veis de decisa˜o, objetivo
e restric¸o˜es:
1. Durante a construc¸a˜o de uma casa, seis vigas de 8m cada devem ser recortadas
para atingir o comprimento correto de 7, 5m. As operac¸o˜es para cortar uma viga
obedecem a seguinte sequencia:
Operac¸a˜o Tempo [s]
1. Colocar vigas nos cavaletes 15
2. Marcar o comprimento 10
3. Cortar a viga 20
4. Armazenar a viga cortada 20
Ha´ treˆs pessoas envolvidas: dois carregadores devem trabalhar simultaneamente nas
operac¸o˜es 1,2 e 4, e um cortador se encarregara´ da operac¸a˜o 3. Ha´ dois pares de
cavaletes nos quais as vigas a recortar sa˜o colocadas na preparac¸a˜o para o corte, e
cada par pode suportar ate´ treˆs vigas lado a lado. Sugira um boa programac¸a˜o para
recortar as seis vigas.
2. Como deve ser montado um retaˆngulo a partir de uma corda de comprimento 10m
para que a a´rea seja ma´xima.
3. Em um jogo de beisebol, Jim e´ o lanc¸ador e Joe o rebatedor. Suponha que Jim
possa atirar uma bola com velocidade ou um bola curva de maneira aleato´ria. Se
Joe previr corretamente que sera´ uma bola curva, podera´ manter uma me´dia de
rebates de 0,5. Ao contra´rio, se Jim atirar uma bola curva e Joe se preparar para
uma bola com velocidade, sua me´dia de rebates ficara´ em 0,2. Por outro lado, se Joe
previr corretamente que sera´ uma bola com velocidade, conseguira´ uma me´dia de
rebates de 0,3; caso contra´rio, sua me´dia sera´ de apenas 0,1. Defina as alternativas
para essa situac¸a˜o.
22 CAPI´TULO 1. CONHECENDO A PESQUISA OPERACIONAL
4. A Paste´is e Pastelo˜es Ltda. fabrica paste´is de forno a partir de dois ingredientes
ba´sicos: massa semipronta e recheio congelado. A empresa pretende estabelecer um
modelo para previsa˜o de seu lucro operacional mensal que lhe permita estabelecer o
prec¸o dos paste´is que deve ser praticado pela empresa. Desconsiderando a hipo´tese
de alterac¸a˜o do tamanho e da qualidade dos paste´is, a diretoria considera que o prec¸o
unita´rio do pastel e o prec¸o me´dio praticado pela concorreˆncia sa˜o os u´nicos fatores
relevantes na determinac¸a˜o da demanda, a qual se comporta segundo a seguinte
equac¸a˜o:
Z = 15000− 5000x+ 5000y
onde x e´ o prec¸o do pastel da Paste´is e Pastelo˜es e y e´ o prec¸o me´dio dos paste´is
vendidos pelos concorrentes.
Dados adicionais sa˜o fornecidos pela tabela:
em R$
Prec¸o me´dio praticado pela concorreˆncia (por pastel) 7,00
Custo unita´rio da massa 1,30
Custo unita´rio do recheio 2,00
Custo do processo de fabricac¸a˜o (por pastel) 0,40
Custo fixo 6.000,00
5. Refac¸a o exemplo 1.5, considerando que o posto esta´ interessado em resolver o
problema do estoque separadamente para cada combust´ıvel, isto e´, determine o
nu´mero de pedidos anuais para o a´lcool que minimize o custo total e, apo´s calcule
o nu´mero de pedidos a ser realizados para a gasolina. Qual a relac¸a˜o entre estes
dois valores encontrados e o nu´mero o´timo de pedidos determinado para o problema
original?
6. Um atacadista de materiais de construc¸a˜o obte´m seu cimento de um fornecedor
u´nico. A demandade cimento e´ razoavelmente constante ao longo do ano. No
1.3. LISTA DE PROBLEMAS 23
u´ltimo ano, a empresa vendeu 2000 toneladas de cimento. Seus custos estimados de
colocac¸a˜o de um pedido sa˜o cerca de $25, e os custos de manutenc¸a˜o dos estoques
sa˜o de 20% do custo de aquisic¸a˜o, por ano. A empresa adquire cimento a $60 por
tonelada. Quanto cimento a empresa deveria pedir por vez?
7. Uma empresa comercializa queijos deseja estudar sua pol´ıtica de estocagem de modo
a otimizar sua operac¸a˜o, reduzindo os custos. Apo´s um cuidadoso levantamento, o
gerente estimou que o custo anual de manter um item em estoque e´ de $50,00. Tal
custo foi obtido considerando-se o custo do capital investido, o custo das instalac¸o˜es,
refrigerac¸a˜o, limpeza e seguros, durante um ano, e dividindo-se pelo nu´mero esti-
mado de itens que ira˜o compor o estoque no mesmo per´ıodo. Consideremos que este
nu´mero seja constante e igual a 1.000 por ano. O suprimento do produto e´ feito
em quantidades constantes e intervalos regulares, a colocac¸a˜o de cada encomenda
tem um custo fixo de $ 1.000,00, incluindo documentac¸a˜o, despesas de pedido e
transporte. Qual a quantidade de mercadoria que deve ser encomendada de cada
vez?
CAP´ITULO 2
PROGRAMAC¸A˜O MATEMA´TICA
Desde a antiguidade va´rios cientistas tais como Euclides, Newton, Lagrange, Leontief, Von
Neumann, dentre outros, tem dedicado seus estudos a` pesquisa do o´timo. A a´rea que es-
tuda Problemas de Otimizac¸a˜o e´ denominada Programac¸a˜o Matema´tica que engloba uma
ampla classe de problemas. O termo programac¸a˜o significa que existe um planejamento
das atividades.
A Programac¸a˜o Matema´tica vem se constituindo como uma das mais poderosas fer-
ramentas matema´ticas para diversos segmentos, propiciando melhorias mensura´veis nos
processos e automatizac¸a˜o dos mesmos, ana´lises operacionais, de projetos, reengenharia e
identificac¸a˜o de gargalos. Seus benef´ıcios sa˜o exatamente aqueles procurados por qualquer
empresa: diminuic¸a˜o dos custos e aumento dos lucros. Em algumas organizac¸o˜es ela esta´,
inclusive, embutida em suas rotinas informatizadas de planejamento dia´rio dos processos
de operac¸a˜o.
Segundo pesquisas efetuadas em empresas que tem utilizado esta ferramenta, a reduc¸a˜o
de custos se enquadra facilmente na faixa entre 1% e 5%, existindo casos que chegam
ate´ a 15%. A magnitude do benef´ıcio da Programac¸a˜o Matema´tica na performance das
empresas pode ser avaliada nos casos listados a seguir referentes a diferentes a´reas de
atividade econoˆmica:
24
25
1. A companhia de o´leos TEXACO utilizou a Programac¸a˜o Linear para obter condic¸o˜es
ideais de processamento do grude bruto para produzir quantidades proporcionais a`s
necessidades do mercado aos diversos derivados do grude: gasolina, o´leos com diver-
sas graduac¸o˜es ou asfalto. A aplicac¸a˜o da metodologia em sete das suas refinarias
permitiu obter uma melhoria de 30% nos lucros, atingindo 30 milho˜es de do´lares.
2. A rede de fast food McDonald’s nos Estados Unidos aplicou a Programac¸a˜o Ma-
tema´tica para otimizac¸a˜o dos hora´rios de trabalho em quatro de seus estabeleci-
mentos, pertencentes a Al Boxley. Este tipo de atividade recorre frequ¨entemente
a` ma˜o-de-obra em part-time, tendo como resultado uma grande aleatoriedade na
disponibilidade dos recursos humanos. A Programac¸a˜o Linear proporcionou um
melhor aproveitamento dos recursos dispon´ıveis, com a exigeˆncia de cobertura du-
rante todo per´ıodo de funcionamento das unidades, obtendo-se uma programac¸a˜o
de hora´rios mais conveniente de acordo com as prefereˆncias de hora´rio de cada fun-
ciona´rio.
3. O exe´rcito norte-americano desenvolveu um sistema designado de MLRPS
“Manpower Long-Range Planning System” que permite estimar as necessidades de
recursos humanos num horizonte que vai dos 7 aos 20 anos. O modelo de otimizac¸a˜o
analisa a forma com que as forc¸as armadas podem obter no futuro a estrutura
militar desejada. Para tal, aspectos como as admisso˜es, abandonos, promoc¸o˜es e
transfereˆncias sa˜o tidos em conta no modelo que determina o nu´mero de recursos
necessa´rio.
Uma das caracter´ısticas principais de Programac¸a˜o Matema´tica e´ sua extensibili-
dade, pode ser aplicada a diverso nu´mero de organizac¸o˜es e sistemas: indu´strias, gov-
ernos, ageˆncias, hospitais, economia, sociologia, biologia, dentre outros. Algumas de suas
aplicac¸o˜es se tornaram cla´ssicas:
 Problema de transporte;
 Administrac¸a˜o da produc¸a˜o;
26 CAPI´TULO 2. PROGRAMAC¸A˜O MATEMA´TICA
 Ana´lise de investimentos;
 Problemas de distribuic¸a˜o de recursos, pessoal e tarefas;
 Problemas de corte materiais, etc.
Em um Problema de Otimizac¸a˜o pretende-se maximizar ou minimizar uma quantidade
espec´ıfica, designada objetivo, que depende de um nu´mero finito de varia´veis indepen-
dentes ou interrelacionadas por limitac¸o˜es ou restric¸o˜es te´cnicas do sistema. Resolver o
problema significa aplicar uma sequencia de operac¸o˜es matema´ticas para distribuir recur-
sos limitados sobre operac¸o˜es que exigem a sua utilizac¸a˜o simultaˆnea, de forma o´tima para
o objetivo espec´ıfico. Um Problema de Programac¸a˜o Matema´tica (PPM) e´ um problema
de otimizac¸a˜o satisfazendo dois fatos principais:
• A existeˆncia de um objetivo que pode ser explicitado em termos das varia´veis de
decisa˜o do problema;
• A existeˆncia de restric¸o˜es a` aplicac¸a˜o dos recursos, tanto com relac¸a˜o a`s quantidades
dispon´ıveis quanto com relac¸a˜o a` forma de emprego.
2.1 Modelos de Otimizac¸a˜o
Especificamente, o objetivo primordial de um PPM e´ encontrar a melhor soluc¸a˜o para
problemas que podem ser representados por modelos matema´ticos onde o objetivo pode ser
expresso em func¸a˜o das varia´veis e as restric¸o˜es expressas como equac¸o˜es ou inequac¸o˜es.
Os modelos matema´ticos utilizados em PPM seguem, em geral, uma estrutura padra˜o
composta por uma func¸a˜o-objetivo, um crite´rio de otimizac¸a˜o e um conjunto de restric¸o˜es.
A forma geral de um modelo para um PPM com n varia´veis e m restric¸o˜es e´ apresentada
a seguir:
2.1. MODELOS DE OTIMIZAC¸A˜O 27
otimizar: z = f(x1, x2, . . . , xn)
sujeito a:

g1(x1, x2, . . . , xn)
g2(x1, x2, . . . , xn)
...
gm(x1, x2, . . . , xn)

≤
=
≥

b1
b2
...
bm
(2.1)
onde as varia´veis do problema esta˜o representadas por xj com j = 1, . . . , n e bi, para
i = 1, . . . ,m, representa a quantidade dispon´ıvel de determinado recurso. Utilizaremos a
notac¸a˜o vetorial para representar as varia´veis de decisa˜o, assim define-se:
x =
[
x1 x2 . . . xn
]
(2.2)
f(x) e´ denominada func¸a˜o-objetivo e gi(x) sa˜o as func¸o˜es restric¸o˜es do problema.
A soluc¸a˜o do modelo pode ser obtida por te´cnicas matema´ticas e algoritmos espec´ıficos,
e a construc¸a˜o do modelo deve levar em considerac¸a˜o a disponibilidade de uma te´cnica
para o ca´lculo da soluc¸a˜o. Para melhor estudar as te´cnicas dispon´ıveis para resoluc¸a˜o de
PPM, a a´rea pode ser subdividida em duas suba´reas determinadas pelas propriedades das
func¸o˜es envolvidas no problema:
Programac¸a˜o Linear: Todas as func¸o˜es do modelo sa˜o lineares em relac¸a˜o a`s varia´veis.
Programac¸a˜o Na˜o-Linear: Pelo menos uma das func¸o˜es envolvidas na˜o e´ linear.
A soluc¸a˜o de um PPM inicia-se pela modelagem, esta etapa e´ ta˜o importante tanto
quanto o desenvolvimento de me´todos de soluc¸a˜o, visto que a qualidade de todo o processo
e´ consequencia direta do grau de representatividade do modelo.
O exemplo 1.6 apresentado no cap´ıtulo anterior foi modelado seguindo certa sistema-
tizac¸a˜o e agora iremos nos concentrar na estruturac¸a˜ode modelos espec´ıficos para PPM.
A tarefa de construc¸a˜o do modelo a partir do enunciado do problema deve seguir uma
metodologia ba´sica, apresentada a seguir:
28 CAPI´TULO 2. PROGRAMAC¸A˜O MATEMA´TICA
Identificac¸a˜o das varia´veis de decisa˜o
Todas as grandezas envolvidas devem ser determinadas, explicitando as deciso˜es que
devem ser tomadas, nomeando-as xj, j = 1, . . . , n.
Definic¸a˜o do crite´rio de otimizac¸a˜o
Crite´rios de avaliac¸a˜o capazes de indicar que uma decisa˜o e´ prefer´ıvel a outras
devem ser definidos. Deve-se identificar as metas que se pretendem alcanc¸ar com
a resoluc¸a˜o do problema, expressando-as como func¸o˜es matema´ticas. Em geral, o
objetivo aparece na forma de maximizac¸a˜o ou minimizac¸a˜o de quantidades.
Formulac¸a˜o das restric¸o˜es
Todos os requisitos, condicionalismos e limitac¸o˜es do problema, tanto expl´ıcitas
como impl´ıcitas, devem ser identificados. Cada limitac¸a˜o imposta na descric¸a˜o do
problema deve ser expressa como uma equac¸a˜o ou inequac¸a˜o em func¸a˜o das varia´veis
de decisa˜o.
2.2 Problemas de Programac¸a˜o Matema´tica
Para melhor ilustrar os conceitos discutidos, sera˜o apresentadas algumas situac¸o˜es que po-
dem ser descritas com o aux´ılio de um modelo de Programac¸a˜o Matema´tica. A seguir sa˜o
propostos alguns PPM onde espera-se exemplificar e detalhar o processo de modelagem,
entretanto sera´ a experieˆncia individual responsa´vel pelo desenvolvimento de habilidades
para a criac¸a˜o de bons modelos matema´ticos, eficientes e realistas. Salientamos que, ainda
na˜o ha´ a preocupac¸a˜o com a soluc¸a˜o de problemas que podera´ ser obtida posteriormente.
. . . Exemplo 2.1. Produc¸a˜o de balas
Considere que uma doceira deseja abrir um pequeno nego´cio para produc¸a˜o de balas.
A princ´ıpio ela esta´ considerando produzir dois tipos de balas: caramelo e nozes. Na
produc¸a˜o sa˜o utilizados treˆs ingredientes: leite, ac¸u´car e nozes. A doceira tem em estoque
10kg de ac¸u´car, 1kg de nozes e 6l de leite. A composic¸a˜o da bala de caramelo e´: 40%
de leite e 60% de ac¸u´car, e para as balas de nozes os ingredientes devem ser misturados
2.2. PROBLEMAS DE PROGRAMAC¸A˜O MATEMA´TICA 29
na seguinte proporc¸a˜o: 40% de leite, 50% de ac¸u´car e 10% de nozes. Cada quilo de bala
de caramelo pode ser vendido a R$10,00 enquanto um quilo de bala de nozes pode ser
vendido por R$13,00. Qual deve ser a produc¸a˜o de cada tipo de bala para obter a maior
receita?
De acordo com a sistema´tica estabelecida anteriormente para a construc¸a˜o de modelos
de PPM, vamos elaborar o modelo para este problema em etapas.
Etapa 1: Identificac¸a˜o das varia´veis de decisa˜o
O objetivo do problema e´ determinar as quantidades de cada tipo de bala a ser
produzida de forma a resultar na ma´xima receita. Portanto, este problema tem
duas varia´veis de decisa˜o:
x1: a quantidade (em kg) a ser produzida de bala de caramenlo
x2: a quantidade (em kg) a ser produzida de bala de nozes
Etapa 2: Formulac¸a˜o da func¸a˜o objetivo
O crite´rio para a selec¸a˜o do melhor combinac¸a˜o poss´ıvel e´ a receita ma´xima. Cada
tipo de bala gera uma receita que e´ o produto do prec¸o de venda pela quantidade
vendida e a func¸a˜o receita e´ obtida pela soma das contribuic¸o˜es de cada tipo de bala
produzido. Matematicamente, temos:
max z = f(x1, x2) = 10x1 + 13x2
Etapa 3: Formulac¸a˜o das restric¸o˜es
O problema impo˜e restric¸o˜es na quantidade de mate´ria prima para fabricac¸a˜o dos
doces:
0, 6x1 + 0, 5x2 ≤ 10 (quantidade utilizada de ac¸u´car)
0, 4x1 + 0, 4x2 ≤ 6 (quantidade utilizada de leite)
0, 1x2 ≤ 1 (quantidade utilizada de nozes)
30 CAPI´TULO 2. PROGRAMAC¸A˜O MATEMA´TICA
Ainda ha´ uma condic¸a˜o impl´ıcita ao problema que devemos considerar, quais os val-
ores que as varia´veis de decisa˜o podem assumir? Nesta situac¸a˜o estamos
interessados em valores na˜o-negativos que satisfac¸am as limitac¸o˜es de mate´ria-prima.
Devemos tambe´m considerar o tipo de varia´vel, neste problema podemos admitir
que a varia´vel xj pode receber qualquer valor real. Assim temos definido o domı´nio
da func¸a˜o objetivo e o crite´rio de na˜o-negatividade: xj ≥ 0, xj ∈ R
O modelo completo para o problema da produc¸a˜o de balas representado no formato
(2.1) e´:
max z = 10x1 + 13x2
s.a. :

0, 6x1 + 0, 5x2 ≤ 10 (quantidade utilizada de ac¸u´car)
0, 4x1 + 0, 4x2 ≤ 6 (quantidade utilizada de leite)
0, 1x2 ≤ 1 (quantidade utilizada de nozes)
x1, x2 ≥ 0 (condic¸a˜o de na˜o-negatividade)
Observe que a condic¸a˜o xj ∈ R foi omitida do modelo final, isto deve-se ao fato que
em modelos de Programac¸a˜o Matema´tica, por convenc¸a˜o, esta condic¸a˜o e´ considerada
impl´ıcita ao modelo. A informac¸a˜o sobre o domı´nio da func¸a˜o constara´ no modelo caso o
domı´nio seja outro conjunto nume´rico.
. . . Exemplo 2.2. Localizac¸a˜o da antena de transmissa˜o
O Gerente de Projetos da LCL Telecom deve localizar uma antena de retransmissa˜o
para atender a treˆs localidades na Baixada Maranhense: Viana, Penalva e Cajari. Por
problemas te´cnicos a antena na˜o pode estar a mais de 10 km do centro de cada cidade.
Considerando as localizac¸o˜es relativas indicadas no mapa, determine o melhor posiciona-
mento para a torre.
Sejam (xi, yi) as coordenadas no plano cartesiano da localizac¸a˜o das cidades.
Etapa 1: Identificac¸a˜o das varia´veis de decisa˜o
2.2. PROBLEMAS DE PROGRAMAC¸A˜O MATEMA´TICA 31
O objetivo do problema e´ determinar a localizac¸a˜o (x, y) da antena que minimize a
soma das distaˆncias ate´ as treˆs localidades, as varia´veis de decisa˜o ja´ esta˜o definidas:
x: abscissa no plano cartesiano da localizac¸a˜o da torre de transmissa˜o
y: ordenada no plano cartesiano da localizac¸a˜o da torre de transmissa˜o
Etapa 2: Formulac¸a˜o da func¸a˜o objetivo
Admitamos que a localidade 1 seja Viana, a localidade 2 seja Cajari e a local-
idade 3 seja Penalva, as coordenadas cartesianas das localidades sera˜o (xi, yi),
com i = 1, 2, 3. Fixado uma localidade i, a distaˆncia entre esta e a antena de
transmissa˜o pode ser calculada por
√
(xi − x)2 + (yi − y)2.
A func¸a˜o distaˆncia e´ obtida pela soma treˆs distaˆncias entre a antena e as localidades.
min z =
3∑
i=1
√
(xi − x)2 + (yi − y)2
Etapa 3: Formulac¸a˜o das restric¸o˜es
As restric¸o˜es te´cnicas sa˜o as u´nicas limitac¸o˜es do problema:
√
(xi − x)2 + (yi − y)2 ≤ 10, ∀i ∈ {1, 2, 3}
As condic¸o˜es pra´ticas do problema na˜o requer restric¸o˜es de na˜o-negatividade e as
varia´veis de decisa˜o podem assumir valores reais.
32 CAPI´TULO 2. PROGRAMAC¸A˜O MATEMA´TICA
O modelo completo e´ apresentado a seguir:
min z =
3∑
i=1
√
(xi − x)2 + (yi − y)2
s.a. :

√
(x1 − x)2 + (y1 − y)2 ≤ 10 (distaˆncia a Viana)√
(x2 − x)2 + (y2 − y)2 ≤ 10 (distaˆncia a Cajari)√
(x3 − x)2 + (y3 − y)2 ≤ 10 (distaˆncia a Penalva)
. . . Exemplo 2.3. O problema da dieta
Um indiv´ıduo deve seguir uma dieta balanceada por recomendac¸a˜o me´dica baseada
no consumo de diversos tipos de alimentos de forma a suprir suas necessidades dia´rias de
energia, que pode variar de 3100 a 3300 kcal, e nutrientes essenciais para a boa sau´de. Uma
porc¸a˜o de cada alimento fornece uma porcentagem da Quantidade Dia´ria Recomentada
(QDR) de diferentes nutrientes de acordo com a tabela. Prec¸o e quantidade calo´rica de
cada porc¸a˜o tambe´m sa˜o informados na tabela. Deseja-se saber qual a combinac¸a˜o ideal
de alimentos com custo mı´nimo e que satisfac¸a a`s necessidades nutricionais.
Alimentos
1 2 3 4 5 6 7
unidade QDR carne arroz feija˜o pa˜o ovos laranja leite
Valor energe´tico kcal 225 170 76 300 146 45 160
Prote´ına g 37 35 3 4,8 8 13 0,6 8
Vitamina A mg 900 7 - 2 - 87 21 99
Vitamina C mg 300 - - 3 -12 59 2
Ferro mg 10 2,9 1,3 1,6 1 1,3 0,2 0,9
Ca´lcio mg 500 5 12 27 16 49 45 285
Custo (R$) 0,50 0,14 0,19 0,15 0,20 0,10 0,30
2.2. PROBLEMAS DE PROGRAMAC¸A˜O MATEMA´TICA 33
Etapa 1: Identificac¸a˜o das varia´veis de decisa˜o
O objetivo do problema e´ determinar uma composic¸a˜o ideal de alimentos com custo
mı´nimo, para calcular o custo de destas combinac¸o˜es e´ necessa´rio saber o nu´mero
de porc¸o˜es dia´rias de cada alimento, que e´ um elemento desconhecido do problema.
Portanto as quantidades de porc¸o˜es dia´rias de cada alimento definira˜o as varia´veis
de decisa˜o deste problema.
Sejam xj: nu´mero de porc¸o˜es consumidas do alimento j, j = 1, . . . , 7
Etapa 2: Formulac¸a˜o da func¸a˜o objetivo
O crite´rio para a selec¸a˜o do melhor combinac¸a˜o poss´ıvel e´ o custo mı´nimo. Cada
tipo de alimento gera um custo que e´ o produto do prec¸o da porc¸a˜o pelo nu´mero de
porc¸o˜es consumidas e a func¸a˜o custo e´ obtida pela soma das contribuic¸o˜es de cada
alimento consumido. Matematicamente, temos:
z = f(x1, . . . , x7) = 0, 5x1 + 0, 14x2 + 0, 19x3 + 0, 15x4 + 0, 2x5 + 0, 1x6 + 0, 3x7
Utilizando a notac¸a˜o vetorial para simplificar: z = f(x) =
7∑
j=1
cjxj
onde cj sa˜o os componentes do vetor
c =
[
0, 50 0, 14 0, 19 0, 15 0, 20 0, 10 0, 30
]
Etapa 3: Formulac¸a˜o das restric¸o˜es
O menor custo e´ obviamente zero, entretanto esta soluc¸a˜o na˜o atende a recomendac¸a˜o
me´dica. O problema impo˜e algumas condic¸o˜es explicitas que devem ser satisfeitas:
(a) A dieta deve suprir a necessidade dia´ria de energia
225x1 + 170x2 + 76x3 + 300x4 + 146x5 + 45x6 + 160x7 ≥ 3100 (mı´nimo kcal)
225x1 + 170x2 + 76x3 + 300x4 + 146x5 + 45x6 + 160x7 ≤ 3300 (ma´ximo kcal)
(b) A dieta deve fornecer as quantidades mı´nimas recomendadas de nutrientes
34 CAPI´TULO 2. PROGRAMAC¸A˜O MATEMA´TICA
35x1 + 3x2 + 4, 8x3 + 8x4 + 13x5 + 0, 6x6 + 8x7 ≥ 37 (Prote´ına)
7x1 + 2x3 + 87x5 + 21x6 + 99x7 ≥ 900 (Vitamina A)
3x3 + 12x5 + 59x6 + 2x7 ≥ 300 (Vitamina C)
2, 9x1 + 1, 3x2 + 1, 6x3 + x4 + 1, 3x5 + 0, 2x6 + 0, 9x7 ≥ 10 (Ferro)
5x1 + 12x2 + 27x3 + 16x4 + 49x5 + 45x6 + 285x7 ≥ 500 (Ca´lcio)
(c) Ainda ha´ uma condic¸a˜o impl´ıcita ao problema que devemos considerar, quais
os valores que as varia´veis de decisa˜o podem assumir? Nesta situac¸a˜o esta-
mos interessados em valores na˜o-negativos que satisfac¸am os n´ıveis mı´nimos
de nutrientes. Devemos tambe´m considerar o tipo de varia´vel, neste problema
podemos admitir que a varia´vel xj pode receber qualquer valor real. Assim
temos definido o domı´nio da func¸a˜o objetivo e o crite´rio de na˜o-negatividade:
xj ≥ 0, xj ∈ R.
O modelo completo para o problema da dieta representado no formato padra˜o conforme
(2.1) e´:
min z = 0, 5x1 + 0, 14x2 + 0, 19x3 + 0, 15x4 + 0, 2x5 + 0, 1x6 + 0, 3x7
s.a. :

225x1 + 170x2 + 76x3 + 300x4 + 146x5 + 45x6 + 160x7 ≥ 3100
225x1 + 170x2 + 76x3 + 300x4 + 146x5 + 45x6 + 160x7 ≤ 3300
35x1 + 3x2 + 4, 8x3 + 8x4 + 13x5 + 0, 6x6 + 8x7 ≥ 37
7x1 + 2x3 + 87x5 + 21x6 + 99x7 ≥ 900
3x3 + 12x5 + 59x6 + 2x7 ≥ 300
2, 9x1 + 1, 3x2 + 1, 6x3 + x4 + 1, 3x5 + 0, 2x6 + 0, 9x7 ≥ 10
5x1 + 12x2 + 27x3 + 16x4 + 49x5 + 45x6 + 285x7 ≥ 500
xj ≥ 0
2.2. PROBLEMAS DE PROGRAMAC¸A˜O MATEMA´TICA 35
. . . Exemplo 2.4. Distribuic¸a˜o da produc¸a˜o
Uma empresa montadora de eletroˆnicos produz ra´dio, toca-CD e aparelhos de DVD
em treˆs fa´bricas localizadas em Diadema, Ribeira˜o Preto e Campinas. As quantidades
despendidas na produc¸a˜o de cada produto, em pec¸as por hora, em cada uma das fa´bricas
sa˜o as seguintes:
Ra´dio Toca-CD DVD
Diadema 10 20 20
Ribeira˜o 20 10 20
Campinas 20 20 10
Os custos de operac¸a˜o por hora das fa´bricas sa˜o R$ 10.000,00, R$ 8.000,00 e
R$ 11.000,00 para Diadema, Ribeira˜o Preto e Campinas, respectivamente.
A empresa recebeu um pedido de 300 unidades de ra´dio, 500 unidades de toca-CD
e 600 unidades de aparelho de DVD, como deve distribuir a produc¸a˜o entre suas treˆs
fa´bricas para cumprir o pedido ao menor custo poss´ıvel?
Etapa 1: Identificac¸a˜o das varia´veis de decisa˜o
O objetivo e´ distribuir a produc¸a˜o ao menor custo poss´ıvel, sendo assim deve-se
decidir quanto produzir de cada produto em cada uma das fa´bricas, o que define as
varia´veis de decisa˜o do problema. Sejam:
x1d: nu´mero de ra´dios a produzir na fa´brica de Diadema
x2d: nu´mero de toca-CD a produzir na fa´brica de Diadema
x3d: nu´mero de DVD a produzir na fa´brica de Diadema
x1r: nu´mero de ra´dios a produzir na fa´brica de Ribeira˜o
x2r: nu´mero de toca-CD a produzir na fa´brica de Ribeira˜o
x3r: nu´mero de DVD a produzir na fa´brica de Ribeira˜o
x1c: nu´mero de ra´dios a produzir na fa´brica de Campinas
36 CAPI´TULO 2. PROGRAMAC¸A˜O MATEMA´TICA
x2c: nu´mero de toca-CD a produzir na fa´brica de Campinas
x3c: nu´mero de DVD a produzir na fa´brica de Campinas
Etapa 2: Formulac¸a˜o da func¸a˜o objetivo
O objetivo e´ primordial e´ determinar quantas horas cada uma das fa´bricas deve
dispor para o pedido com o menor custo poss´ıvel. O custo e´ dado por
z = f(x, y, z) = 10.000x+ 8.000y + 11000z
onde x e´ o nu´mero total de horas que fa´brica de Diadema funciona para atender o
pedido, y e´ o nu´mero total de horas da fa´brica de Ribeira˜o e z corresponde ao total
de horas da fa´brica de Campinas.
De acordo com a tabela fornecida podemos determinar x em func¸a˜o das varia´veis
de decisa˜o x1d, x2d e x3d, y em func¸a˜o de x1r, x2r e x3r e z em func¸a˜o de x1c, x2c e
x3c:
x =
x1d
10
+
x2d
20
+
x3d
20
= 0, 10x1d + 0, 05x2d + 0, 05x3d
y =
x1r
20
+
x2r
10
+
x3r
20
= 0, 05x1r + 0, 10x2r + 0, 05x3r
z =
x1c
20
+
x2c
20
+
x3c
10
= 0, 05x1c + 0, 05x2c + 0, 10x3c
Etapa 3: Formulac¸a˜o das restric¸o˜es
A limitac¸o˜es explic´ıtas do problema sa˜o o atendimento da quantidade demandada
no pedido, isto e´ a soma das produc¸o˜es das treˆs fa´bricas de um determinado produto
na˜o deve ser inferior a` quantidade encomendada:
x1d + x1r + x1c ≥ 300 (encomenda de ra´dios)
x2d + x2r + x2c ≥ 500 (encomenda de toca-CD)
x3d + x3r + x3c ≥ 600 (encomenda de DVD)
As condic¸o˜es implic´ıtas do problema sa˜o a na˜o-negatividade e o domı´nio da func¸a˜o
2.2. PROBLEMAS DE PROGRAMAC¸A˜O MATEMA´TICA 37
objetivo restrito ao conjunto dos nu´meros inteiros Z.
O modelo completo e´:
min z = 10.000(x1d + x2d + x3d) + 8.000(x1r + x2r + x3r) + 11.000(x1c + x2c + x3c)
s.a. :

x1d + x1r + x1c ≥ 300 (encomenda de ra´dios)
x2d + x2r + x2c ≥ 500 (encomenda de toca-CD)
x2d + x2r + x2c ≥ 600 (encomenda de DVD)
xia ≥ 0 para i = 1, 2, 3 e a = d, r, c
xia ∈ Z
. . . Exemplo 2.5. O caso da Loja dos queijos: 1
A Loja dos Queijos produz e comercializa dois tipos de queijos (Delux e Standard),
muito procurados na e´poca do Natal. Estes queijos sa˜o produzidos a partir de uma mistura
de frutas da e´poca e de um queijo especial muito caro. A Loja dos Queijos pode dispor
de 20 kg de mistura de frutas e 60 kg do queijo especial utilizado. Cada kg de Delux
consiste em 0,2 kg da mistura de frutas e 0,8 kg do queijo especial, enquanto que 1 kg de
Standard consiste em 0,2 kg da mistura de frutas, 0,3 kg do queijo especial e 0,5 kg de um
queijo comum, dispon´ıvel em grande quantidade. De acordo com a experieˆncia da Loja
dos Queijos, foi poss´ıvel descobrir que a procura de cada um dos dois queijos depende do
prec¸o adotado:
d1 = 190− 25p1
d2 = 250− 50p2
onde d representa a procura (em kg), p denota o prec¸o (em u.m./kg), e os ı´ndices 1 e 2
designam os tipos Delux e Standard, respectivamente.
Que quantidade de cada tipo de queijo devera´ a Loja dos Queijos preparar, e que
1Baseado em Bronson & Naadimuthu, 2001.38 CAPI´TULO 2. PROGRAMAC¸A˜O MATEMA´TICA
prec¸os devera˜o ser adotados para maximizar a receita e garantir que, apo´s a e´poca do
Natal, nada reste dos dois queijos em estoque?
Varia´veis de decisa˜o: x1 : quantidade (em kg) a produzir de queijo tipo Delux
x2 : quantidade (em kg) a produzir de queijo tipo Standard
Objetivo: max z = p1x1 + p2x2 (maximizar a receita)
Restric¸o˜es:

0, 2x1 + 0, 2x2 ≤ 20 (disponibilidade de frutas)
0, 8x1 + 0, 3x2 ≤ 60 (disponibilidade de queijo especial)
x1, x2 ≥ 0 (condic¸a˜o de na˜o-negatividade)
O modelo ainda na˜o esta´ completo pois e´ necessa´rio garantir que toda a produc¸a˜o seja
vendida, para tanto a produc¸a˜o xi na˜o deve ultrapassar a demanda di, isto e´,
xi ≤ di, i = 1, 2
Considerando as equac¸o˜es de demanda, temos:
x1 ≤ 190− 25p1 e x2 ≤ 250− 50p2
Reescrevendo as inequac¸o˜es, obtemos as seguintes restric¸o˜es de demanda:
x1 + 25p1 ≤ 190
x2 + 50p2 ≤ 250
Para simplificar o problema, o objetivo tambe´m deve ser reescrito somente em func¸a˜o
das varia´veis de decisa˜o. Observe que para quaisquer valores fixos de x1 e x2 a func¸a˜o
z = p1x1 + p2x2 aumenta conforme aumentarem os prec¸os p1 e p2, assim para maximizar
z, p1 e p2 devem assumir valores ma´ximos, isto e´ assumir valores tais que as inequac¸o˜es
2.2. PROBLEMAS DE PROGRAMAC¸A˜O MATEMA´TICA 39
referente a`s restric¸o˜es de demanda se tornem equac¸o˜es. Desta forma, os prec¸os podem ser
assumidos como:
p1 =
190− x1
25
= 7, 6− 0, 04x1
p2 =
250− x2
50
= 5 − 0, 02x2
Substituindo os valores dos prec¸os na func¸a˜o objetivo temos:
z = (7, 6− 0, 04x1)x1 + (5− 0, 02x2)x2
= 7, 6x1 + 5x2 − 0, 04x21 − 0, 02x22
O modelo completo e´ apresentado a seguir e deve-se notar que as restric¸o˜es de demanda
foram incorporadas na construc¸a˜o da func¸a˜o objetivo e na˜o sera˜o incorporadas a`s restric¸o˜es
do problema.
max z = 7, 6x1 + 5x2 − 0, 04x21 − 0, 02x22
s.a. :

0, 2x1 + 0, 2x2 ≤ 20 (disponibilidade de frutas)
0, 8x1 + 0, 3x2 ≤ 60 (disponibilidade de queijo especial)
x1, x2 ≥ 0 (condic¸a˜o de na˜o-negatividade)
. . . Exemplo 2.6. Um problema de transporte:
Uma companhia de panificac¸a˜o pode produzir pa˜o de forma em duas fa´bricas, de
acordo com a tabela:
Capacidade de produc¸a˜o Custo de Produc¸a˜o
Fa´brica (pa˜es de forma) (u.m./pa˜o de forma)
A 2500 2,3
B 2100 2,5
Quatro redes de restaurantes pretendem comprar pa˜es de forma, suas necessidades e
os prec¸os que esta˜o dispostos a pagar sa˜o os seguintes:
40 CAPI´TULO 2. PROGRAMAC¸A˜O MATEMA´TICA
Rede de Necessidade ma´xima Prec¸o ma´ximo
Restaurantes (pa˜es de forma) (u.m./pa˜o de forma)
1 1800 3,9
2 2300 3,7
3 550 4,0
4 1750 3,6
O custo (em u.m.) de transporte de uma unidade de pa˜o de forma de cada padaria
para cada rede de restaurantes e´ dado na tabela seguinte.
Restaurantes
Padaria 1 2 3 4
A 0,6 0,8 1,1 0,9
B 1,2 0,6 0,8 0,5
Determine o plano o´timo de fornecimento de pa˜es de forma a maximizar o lucro total
da empresa de panificac¸a˜o.
Varia´veis de decisa˜o: xij : quantidade a ser transportada (em unidades)
da origem i = A,B para o destino j = 1, 2, 3, 4
De acordo com tabela de prec¸os, a func¸a˜o receita sera´:
r = 3, 9xi1 + 3, 7xi2 + 4xi3 + 3, 6xi4 para i = A,B
A seguir e´ apresentado o modelo para maximizac¸a˜o da func¸a˜o lucro obtida subtraindo-
se dos prec¸os unita´rios os custos de produc¸a˜o e de transporte.
Objetivo: max z = xA1 + 0, 2xB1 + 0, 6xA2 + 0, 6xB2 + . . .
. . .+ 0, 6xA3 + 0, 7xB3 + 0, 4xA4 + 0, 6xB4
2.3. LISTA DE PROBLEMAS 41
Restric¸o˜es:

∑4
j=1 xAj ≤ 2500 (capacidade de produc¸a˜o da fa´brica A)∑4
j=1 xBj ≤ 2100 (capacidade de produc¸a˜o da fa´brica B)
xA1 + xB1 ≤ 1800 (necessidade do restaurante 1)
xA2 + xB2 ≤ 2300 (necessidade do restaurante 2)
xA3 + xB3 ≤ 550 (necessidade do restaurante 3)
xA4 + xB4 ≤ 1750 (necessidade do restaurante 4)
xij ≥ 0 (condic¸a˜o de na˜o-negatividade)
2.3 Lista de Problemas
Para cada PPM abaixo, elabore um modelo do sistema descrito de acordo com (2.1):
1. Sol Ltda. faz dois tipos de brinquedos de madeira: soldados e trens. Um soldado
e´ vendido por R$ 27,00 e usa R$ 10,00 de mate´ria prima. Cada soldado produzido
aumenta os custos de Sol Ltda. em R$ 14,00. Um trem e´ vendido por R$ 21,00 e
usa R$ 9,00 de mate´ria prima. O custo adicional para constru´ı-lo e´ de R$ 10,00.
Para construir os soldados e os trens de madeira e´ necessa´rio dois tipos de trabalho:
carpintaria e acabamento. Um soldado precisa de duas horas de acabamento e
um hora de carpintaria. Um trem necessita de uma hora de cada. Cada semana
Sol Ltda. pode obter toda mate´ria-prima necessa´ria, mas somente 100 horas de
acabamento e 80 horas na sec¸a˜o de carpintaria.
A demanda de trem e´ ilimitada mas somente 40 soldados sa˜o comprados por semana.
Sol Ltda. deseja maximizar o seu lucro.
2. Uma importante companhia petrol´ıfera pretende construir uma refinaria que sera´
abastecida por treˆs cidades portua´rias A,B e C. O porto A esta´ situado a 300 km a
leste e a 400 km a norte do porto B; o porto C esta´ situado a 100 km a sul do porto
B. Determine a localizac¸a˜o da refinaria que minimiza o comprimento total das vias
necessa´rias para interligar a refinaria aos treˆs portos.
42 CAPI´TULO 2. PROGRAMAC¸A˜O MATEMA´TICA
3. Uma empresa produz treˆs tipos de portas a partir de um determinado material.
Sabendo que diariamente a empresa dispo˜e de 500 kg de material e 600 horas de
trabalho, determinar um plano o´timo de produc¸a˜o que corresponda ao maior lucro.
A tabela seguinte indica a quantidade de material e horas de trabalho necessa´rias
para a produc¸a˜o de uma porta de cada tipo, assim como o lucro unita´rio de cada
uma delas:
Recursos Porta 1 Porta 2 Porta 3
Quantidade material 8 kg 4 kg 3 kg
Horas de trabalho 7 6 8
Lucro unita´rio R$ 50,00 R$ 40,00 R$ 55,00
4. A tabela de alimentac¸a˜o utilizada numa determinada loja de animais de estimac¸a˜o
especifica as seguintes necessidades mı´nimas para um hamster: 70 unidades de
prote´ına, 100 unidades de hidratos de carbono, 20 unidades de gordura. Ha´ seis tipos
de rac¸o˜es dispon´ıveis na loja cujas caracter´ısticas sa˜o dadas no quadro seguinte:
Prote´ınas H.Carbono Gordura Custo
Rac¸a˜o (unidades/kg) (unidades/kg) (unidades/kg) (u.m./kg)
A 20 50 4 2
B 30 30 9 3
C 40 20 11 5
D 40 25 10 6
E 45 50 9 8
F 30 20 10 8
Como deve ser feita uma mistura que satisfac¸a os requisitos da alimentac¸a˜o dia´ria
de um hamster a um custo mı´nimo?
2.3. LISTA DE PROBLEMAS 43
5. Uma rede de depo´sitos de material de construc¸a˜o tem 4 lojas que devem ser abaste-
cidas 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 distaˆncias a`s
lojas esta˜o no quadro (em km): O caminha˜o pode transportar 10 m3 por viagem.
L1 L2 L3 L4
P1 30 20 24 18
P2 12 36 30 24
P3 8 15 25 20
Os portos tem areia para suprir qualquer demanda. Estabelecer um plano de trans-
porte que minimize a distaˆncia total percorrida entre os portos e as lojas e que supra
as necessidades das lojas.
6. O departamento de marketing de uma empresa estuda a forma mais econoˆmica de
aumentar em 30% as vendas de seus dois produtos P1 e P2. As alternativas sa˜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 propor-
cionar um aumento de 3% nas vendas de cada produto, para cada $1.000,00
investidos.
b) Investir diretamente na divulgac¸a˜o dos produtos. Cada $1.000,00 investidos em
P1 retornam um aumento de 4% nas vendas, enquanto que para P2o retorno
e´ de 10%.
A empresa dispo˜e de $10.000,00 para esse empreendimento. Quanto devera´ destinar
a cada atividade?
CAP´ITULO 3
PROGRAMAC¸A˜O LINEAR
O objetivo da Programac¸a˜o Linear (PL) e´ encontrar a melhor soluc¸a˜o para problemas
que admitam modelos representados por func¸o˜es e inequac¸o˜es lineares, neste sentido o
termo programac¸a˜o significa que existe um planejamento das atividades e o termo linear
refere-se a` linearidade nas equac¸o˜es envolvidas na modelagem do problema. Conforme ja´
visto no cap´ıtulo anterior, um Problema de Programac¸a˜o Linear (PPL) e´ um Problema
de Programac¸a˜o Matema´tica cuja func¸a˜o objetivo e todas as restric¸o˜es sa˜o lineares rel-
ativamente a`s varia´veis de decisa˜o. Especificamente, as hipo´teses seguintes caracterizam
um PPL:
Certeza: Assume que o modelo seja determin´ıstico, isto e´, todos os paraˆmetros sa˜o
constantes conhecidas.
Proporcionalidade: Admite que a contribuic¸a˜o individual de cada varia´vel de decisa˜o,
tanto na func¸a˜o objetivo quanto nas restric¸o˜es, seja diretamente proporcional ao
valor da varia´vel.
Aditividade: Exige que a contribuic¸a˜o total na func¸a˜o objetivo e nas restric¸o˜es seja
soma direta da contribuic¸o˜es individuais de cada varia´vel de decisa˜o, na˜o podendo
haver interdependeˆncia entre as mesmas.
Divisibilidade: As varia´veis de decisa˜o podem assumir valores fraciona´rios.
44
3.1. ESTRUTURAC¸A˜O DE MODELOS LINEARES 45
3.1 Estruturac¸a˜o de Modelos Lineares
De acordo com as hipo´teses de proporcionalidade e aditividade, a func¸a˜o objetivo e as
restric¸o˜es de um PPL podem ser apresentadas da seguinte forma:
f(x1, x2, . . . , xn) = c1x1 + c2x2 + . . .+ cnxn
gi(x1, x2, . . . , xn) ∼ ai1x1 + ai2x2 + . . .+ ainxn
onde os coeficientes aij e cj sa˜o constantes para i = 1, . . . ,m e j = 1, . . . , n, e o sinal ∼
pode ser substituido pelos sinais de = ou ≤ ou ≥, indistintamente.
De acordo com o formato (2.1), um modelo de PPL apresenta a seguinte estrutura:
min ou max z = c1x1 + c2x2 + . . .+ cnxn
s.a. :

a11x1 + a12x2 + . . .+ a1nxn ∼ b1
a21x1 + a22x2 + . . .+ a2nxn ∼ b2
...
am1x1 + am2x2 + . . .+ amnxn ∼ bm
x1, x2, . . . , xn ≥ 0
(3.1)
Apesar da aparente limitac¸a˜o do modelo, existem aplicac¸o˜es de PL nas mais diversas
a´reas. De fato, e´ uma das te´cnicas mais utilizadas em PO justamente pela simplicidade
do modelo envolvido e facilidade para resoluc¸a˜o de problemas utilizando te´cnicas gra´ficas,
alge´bricas ou algoritmı´cas.
Como exemplos de PPL citamos os exemplos 1.6, 2.1, 2.3, 2.4 e 2.6 apresentados nos
cap´ıtulos anteriores, utilizaremos o problema da produc¸a˜o de balas exposto no exemplo
2.1 para ilustrar as hipo´teses de linearidade.
. . . Exemplo 3.1.
Considere que doceira deseja abrir um pequeno nego´cio para produc¸a˜o de balas. A
46 CAPI´TULO 3. PROGRAMAC¸A˜O LINEAR
princ´ıpio ela esta´ considerando produzir dois tipos de balas: caramelo e nozes. Na
produc¸a˜o sa˜o utilizados treˆs ingredientes: leite, ac¸u´car e nozes. A doceira tem em es-
toque 10kg de ac¸u´car, 1kg de nozes e 6l de leite. A composic¸a˜o da bala de caramelo e´:
40% de leite e 60% de ac¸u´car, e para as balas de nozes os ingredientes devem ser mistu-
rados na seguinte proporc¸a˜o: 40% de leite, 50% de ac¸u´car e 10% de nozes. Cada quilo de
bala de caramelo pode ser vendido a R$10,00 enquanto um quilo de bala de nozes pode
ser vendido por R$13,00. Qual deve ser a produc¸a˜o de cada tipo de bala para obter a
maior receita?
O modelo completo e´: max z = 10x1 + 13x2
s.a. :

0, 6x1 + 0, 5x2 ≤ 10 (qtde.utilizada de ac¸u´car)
0, 4x1 + 0, 4x2 ≤ 6 (qtde. utilizada de leite)
0, 1x2 ≤ 1 (qtde. utilizada de nozes)
x1, x2 ≥ 0 (na˜o-negatividade)
1. Certeza: No contexto do Exemplo 2.1, tanto prec¸os de venda dos produtos, como
a quantidade a ser utilizada de cada ingrediente para fabricac¸a˜o dos doces sa˜o
constantes conhecidas. Entretanto este e´ um fato rara na maioria das aplicac¸o˜es
pra´ticas, em geral utiliza-se como coeficientes para o modelo de textitPPL aprox-
imac¸o˜es do valor me´dio das distribuic¸o˜es de probabilidade quando os respectivos
desvios-padro˜es forem suficientemente pequenos, caso contra´rio, o problema na˜o
podera´ ser modelado como PPL.
2. Proporcionalidade: Se a doceira vender 1kg de bala de caramelado ela recebera´
R$10, 00, se vender 2kg obtera´ R$20, 00, se vender x1kg obtera´ 10x1. O valor obtido
na venda de balas de caramelo e´ proporcional a` quantidade vendida e prec¸o de venda
do produto e´ a constante de proporcionalidade. A receita referente a` produc¸a˜o
de bala de nozes e´ 13x2, sendo o produto da constante de proporcionalidade 13
pela quantidade vendida. Portanto, a receita referente a` determinado produto e´
proporcional a quantidade vendida, se a doceira conceder algum tipo de desconto
3.1. ESTRUTURAC¸A˜O DE MODELOS LINEARES 47
quando a quantidade adquirida ultrapassar certo patamar, a receita na˜o sera´ mais
proporcional a`s quantidades vendidas e a func¸a˜o receita se tornara´ na˜o-linear. De
maneira ana´loga, para produzir 1kg de bala de caramelo utiliza-se 0, 6kg de ac¸u´car,
para produzir o dobro necessita-se do dobro de ac¸u´car, sendo assim a quantidade
utilizada do ingrediente e´ proporcional a quantidade produzida. Similarmente para
os outros ingredientes, constatamos a proporcionalidade em todas as restric¸o˜es do
problema.
3. Aditividade: Para a func¸a˜o objetivo, a receita total e´ a soma das receitas referentes
a cada um dos produtos. Tambe´m para as restric¸o˜es o todo e´ igual a soma das
partes, o total consumido de ac¸u´car e´ a soma do ac¸u´car utilizado para produc¸a˜o
da bala de caramelo e do ac¸u´car gasto na produc¸a˜o da bala de nozes. Analoga-
mente para os demais ingredientes. O comportamento aditivo e´ bastante comum,
entretanto ha´ situac¸o˜es onde na˜o e´ poss´ıvel assumir o princ´ıpio da aditividade, por
exemplo, se os produtos competirem entre si de forma que o aumento nas vendas
de um provoque diminuic¸a˜o na procura do outro, a hipo´tese de aditividade na˜o sera´
satisfeita. Outro exemplo ocorre com reac¸o˜es qu´ımicas, se adicionarmos a um litro
de a´gua o equivalente a 0,1 litro de ac¸u´car o volume resultante na˜o sera´ 1,1 litro de
a´gua doce.
4. Divisibilidade: Neste problema e´ poss´ıvel vender 1kg de bala como 0, 5kg. Depen-
dendo do problema, as varia´veis de decisa˜o devera˜o assumir valores inteiros, neste
caso e´ ainda poss´ıvel modelar o problema como linear utilizando arredondamento,
entretanto este procedimento pode resultar em valores distorcidos, requerendo a
utilizac¸a˜o de algoritmos espec´ıficos de programac¸a˜o inteira.
A`s etapas estabelecidas anteriormente para modelar um PPM, e´ necessa´rio acrescentar
a verificac¸a˜o das hipo´teses de linearidade. Portanto, para proceder a ana´lise do problema
e formular um modelo de PPL o analista seguir as seguintes fases:
X Identificac¸a˜o das varia´veis de decisa˜o
X Identificac¸a˜o da func¸a˜o objetivo
48 CAPI´TULO 3. PROGRAMAC¸A˜O LINEAR
X Identificac¸a˜o das restric¸o˜es
X Verificac¸a˜o dos axiomas de linearidade
X Formulac¸a˜o matema´tica no formato padronizado de acordo com (4.1)
3.2 Resoluc¸a˜o Gra´fica de um PPL
Apo´s a obtenc¸a˜o da formulac¸a˜o matema´tica e´ preciso se preocupar com a resoluc¸a˜o do
problema de otimizac¸a˜o. Em particular, PPL´s com duas varia´veis permitem visualizac¸a˜o
geome´trica, sendo assim, a princ´ıpio recorreremos ao me´todo gra´fico para resolver proble-
mas mais simples. O me´todo gra´fico consiste em, primeiramente determinar o conjunto
de todas as poss´ıveis soluc¸o˜es para o problema, determinado pelo sistema de restric¸o˜es, e
dentreestas identificar aquela onde ocorre o valor o´timo, avaliado pela func¸a˜o objetivo.
3.2.1 Representac¸a˜o Gra´fica das Restric¸o˜es
O espac¸o das soluc¸o˜es de problemas com duas varia´veis e´ o plano R2. Dois pontos distintos
A = (xa, ya) e B = (xb, yb) do plano determinam um reta, e pelas condic¸o˜es de alinha-
mento, um ponto qualquer P = (x, y) ∈ R2 pertence a` reta AB que passa por A e B, se
e somente se, a inclinac¸a˜o da reta AB for a mesma inclinac¸a˜o da reta AP . Assim, temos:
yb − ya
xb − xa =
y − ya
x− xa ⇐⇒
(yb − ya)(x− xa) = (y − ya)(xb − xa) ⇐⇒
(yb − ya)x− (yb − ya)xa = (xb − xa)y − (xb − xa)ya ⇐⇒
(yb − ya)x− (xb − xa)y = xayb − xaya − xbya + xaya ⇐⇒
(yb − ya)︸ ︷︷ ︸
a
x+ (xa − xb)︸ ︷︷ ︸
b
y = xayb − xbya︸ ︷︷ ︸
c
3.2. RESOLUC¸A˜O GRA´FICA DE UM PPL 49
Sendo assim, toda reta no plano tem equac¸a˜o geral da forma:
ax+ by = c (3.2)
onde a,b e c sa˜o constantes que podem assumir qualquer valor real. E, reciprocamente,
toda equac¸a˜o deste tipo representa uma reta no plano R2.
Uma reta divide o plano em duas regio˜es denominadas semiplanos, e as inequac¸o˜es
ax+ by > c e ax+ by < c
representam semiplanos abertos distintos, enquanto as inequac¸o˜es
ax+ by ≥ c e ax+ by ≤ c
determinam semiplanos fechados cuja intersec¸a˜o e´ a reta ax+ by = c.
. . . Exemplo 3.2.
Considere a equac¸a˜o da reta r : −2x + y = 1, representada graficamente abaixo em
linhas pontilhadas. A regia˜o hachurada e´ a representac¸a˜o gra´fica do semiplano aberto
−2x+ y < 1
Se um semiplano e´ a representac¸a˜o gra´fica de uma inequac¸a˜o em duas varia´veis, enta˜o
a representac¸a˜o gra´fica de um sistema de inequac¸o˜es lineares em duas varia´veis sera´ a
intersecc¸a˜o dos semiplanos correspondentes a cada inequac¸a˜o. As restric¸o˜es de um PPL
50 CAPI´TULO 3. PROGRAMAC¸A˜O LINEAR
juntamente com as condic¸o˜es de na˜o-negatividade e´ um conjunto de semiplanos cuja
intersecc¸a˜o determina um conjunto de pontos do R2 denominado Regia˜o das Soluc¸o˜es
Via´veis ou simplesmente Regia˜o Via´vel (RV).
. . . Exemplo 3.3.
A empresa Te´cniBOLA S.A. tem como u´nica atividade a fabricac¸a˜o de bolas, sendo
todas elas em couro e fabricadas segundo os processos primordiais. Atualmente fabrica
dois produtos, a bola de futebol Catechumbo e a bola de vo´lei Voleitok. Ambos os produtos
sa˜o feitos do mesmo material, variando apenas na dimensa˜o, tipo de costuras e rotulagem.
Os recursos que definem a fabricac¸a˜o das bolas sa˜o: o corte do couro, o trabalho de
costura, a pintura de inscric¸o˜es na bola e preparac¸a˜o final. Esta u´ltima e´ composta pelas
atividades de enchimento, controle de qualidade (inspec¸a˜o visual, calibrac¸a˜o e pesagem)
e embalagem.
Os dados fornecidos pela empresa referentes a` quantidade de recursos necessa´rios para
a produc¸a˜o de cada tipo de bola e as quantidades dispon´ıveis para o dia de amanha˜ sa˜o
os indicados na tabela:
Recursos unid. Voleitok Catechumbo Disponibilidade
Couro m2 0,25 0,3 ilimitada
Linha m 2,5 4 ilimitada
Caˆmera de Ar un 1 1 25
Embalagens un 1 1 ilimitada
Operac¸a˜o de Corte min 2 8 ilimitada
Operac¸a˜o de Costura min 9 25 480
Operac¸a˜o de Logotipagem min 1,5 1 ilimitada
Operac¸o˜es de Finalizac¸a˜o min 11 6 240
Para a tomada de decisa˜o, a empresa disponibilizou informac¸o˜es a respeito dos valores
moneta´rios envolvidos (em u.m.) nos seus produtos, apresentados a seguir:
3.2. RESOLUC¸A˜O GRA´FICA DE UM PPL 51
Bola Custo de Produc¸a˜o Prec¸o de Venda
Catechumbo 26,00 32,50
Voleitok 15,00 25,00
Como deve ser distribu´ıda a produc¸a˜o amanha˜ de forma a maximizar o lucro, tendo
em conta os recursos existentes?
De acordo com o objetivo do problema, as varia´veis de decisa˜o podem ser assim
definidas:
x1 : nu´mero de bolas Catechumbo a ser produzido amanha˜.
x2 : nu´mero de bolas Voleitok a ser produzido amanha˜.
Utilizando as hipo´teses de linearidade, obtemos o seguinte modelo:
max z = 6, 5x1 + 10x2 (Lucro Total)
s.a. :

x1 + x2 ≤ 25 (restric¸a˜o de caˆmera de ar)
25x1 + 9x2 ≤ 480 (restric¸a˜o de operac¸a˜o de costura)
6x1 + 11x2 ≤ 240 (restric¸a˜o de operac¸o˜es de finalizac¸a˜o)
x1, x2 ≥ 0 (restric¸a˜o de na˜o-negatividade)
Neste caso, estamos admitindo a hipo´tese de divisibilidade, entretando o problema re-
quer varia´veis inteiras, na pro´xima sec¸a˜o este PPL sera´ resolvido com as te´cnicas usuais,
mas a resposta final devera´ respeitar a imposic¸a˜o pra´tica de quantidades inteiras, uti-
lizando arredondamento, se necessa´rio.
. . . Exemplo 3.4. Construir a regia˜o via´vel do problema da Te´cniBOLA S.A., apre-
sentado no exemplo 3.3, cujo modelo e´:
52 CAPI´TULO 3. PROGRAMAC¸A˜O LINEAR
max z = 6, 5x1 + 10x2 (Lucro Total)
s.a. :

x1 + x2 ≤ 25 (restric¸a˜o de caˆmera de ar) (1)
25x1 + 9x2 ≤ 480 (restric¸a˜o de operac¸a˜o de costura) (2)
6x1 + 11x2 ≤ 240 (restric¸a˜o de operac¸o˜es de finalizac¸a˜o) (3)
x1, x2 ≥ 0 (restric¸a˜o de na˜o-negatividade) (4) e (5)
Somente as restric¸o˜es do problema sa˜o consideradas para determinar a regia˜o via´vel,
sendo assim as restric¸o˜es foram identificadas e numeradas. A seguir e´ apresentada a
representac¸a˜o gra´fica de cada semiplano fechado correspondente a`s restric¸o˜es do problema.
(1) x1 + x2 ≤ 25
A reta r1: x1 + x2 = 25 determina o semi-
plano correspondente a` primeira restric¸a˜o, e
pode ser determinada por dois de seus pontos,
da seguinte maneira:
se x1 = 0 enta˜o x2 = 25 ∴ (0; 25) ∈ r1
se x2 = 0 enta˜o x1 = 25 ∴ (25; 0) ∈ r1
(2) 25x1 + 9x2 ≤ 480
(3) 6x1 + 11x2 ≤ 240
(4) x1 ≥ 0
(5) x2 ≥ 0
A intersecc¸a˜o dos cinco semiplanos definidos pelas restric¸o˜es (1), (2), (3), (4) e (5),
determina a regia˜o das poss´ıveis soluc¸o˜es do problema e esta´ representada pela regia˜o
hachurada abaixo:
3.2. RESOLUC¸A˜O GRA´FICA DE UM PPL 53
O pol´ıgono ABCDE e´ o conjunto de todos os pontos X = (x1, x2) que satisfazem
todas as restric¸o˜es simultaneamente. Sendo assim, toda combinac¸a˜o poss´ıvel da produc¸a˜o
de x1 unidades de bolas Catechumbo e de x2 unidades de bolas Voleitok sera´ um ponto
54 CAPI´TULO 3. PROGRAMAC¸A˜O LINEAR
do pol´ıgono ABCDE, do seu interior ou ponto de fronteira.
3.2.2 Representac¸a˜o Gra´fica da Func¸a˜o Objetivo
Func¸o˜es lineares com duas varia´veis do tipo z = f(x1, x2) = c1x1 + c2x2 sa˜o geometrica-
mente planos em R3, e somente admitem ma´ximo e/ou mı´nimo se estiverem sujeitas a
restric¸o˜es, como no caso de um PPL. As curvas de n´ıvel desse tipo de func¸a˜o sa˜o retas
paralelas que crescem monotonamente na direc¸a˜o do gradiente
∇f(x1, x2) =
(
∂f
∂x1
,
∂f
∂x2
)
A cada ponto do conjunto de soluc¸o˜es via´veis esta´ associada uma, e somente uma, reta
da famı´lia de retas paralelas correspondente a` func¸a˜o objetivo. E solucionar graficamente
um PPL e´ determinar quais pontos da RV retornam o melhor valor para a func¸a˜o objetivo.
A origem do sistema de coordenadas e´ o u´nico ponto cr´ıtico de func¸o˜es lineares, para
o caso espec´ıfico de PPL com duas varia´veis o ponto cr´ıtico e´ (0, 0), que e´ um dos ve´rtices
da RV e qualquer outro ponto extremo da func¸a˜o objetivo deve necessariamente estar
na fronteira da regia˜o delimitada pelas restric¸o˜es. Para encontrar tais pontos deve-se
percorrer a famı´lia de retas paralelas no sentido do gradiente.
Considere um ponto arbitra´rio P ∈ RV e a reta z = c passando por P . Se P for
um ponto interior do pol´ıgono, sera´ poss´ıvel melhorar o valor da func¸a˜o objetivo porque
existem pontos de RV no semiplano determinado por z = c e pelo gradiente. Para
3.2. RESOLUC¸A˜O GRA´FICA DE UM PPL 55
melhorar este valor basta tomar outro ponto de RV localizado a` direita de P e trac¸ar o
representante da famı´lia