Aula 01 - INTRODUÇÃO E FORMULAÇÃO DO MODELO

Prévia do material em texto

PESQUISA OPERACIONAL I
CURSO DE ENGENHARIA DE PRODUÇÃO –
UNIVERSIDADE FEDERAL DO PIAUÍ – UFPIAULA 01
Prof. Airton CarneiroProf. Francisco Pinheiro
INTRODUÇÃO À PESQUISA OPERACIONAL
Pesquisa operacional é a aplicação de
métodos científicos a problemas complexos
para auxiliar no processo de tomada de
decisões, tais como projetar, planejar e
operar sistemas em situações que requerem
alocações eficientes de recursos escassos.
Prof. Airton CarneiroProf. Francisco Pinheiro
A PL é uma técnica de planejamento e otimização,
sendo esta um tópico da ciência Pesquisa Operacional,
a qual contém outros tópicos tais como teoria da
decisão, Teoria de Filas, Teoria probabilística de
estoques, e Simulação.
A PL é uma ferramenta utilizada para encontrar o lucro
máximo ou o custo mínimo em situações nas quais temos
diversas opções de escolha sujeitas a algum tipo de
restrição ou regulamentação.
Obs: O termo Programação em PO tem o sentido de
planejamento.
INTRODUÇÃO À PESQUISA OPERACIONAL
Programação Linear - PL
Prof. Airton CarneiroProf. Francisco Pinheiro
Sistema
Modelo = representação
INTRODUÇÃO À PESQUISA OPERACIONAL
Prof. Airton CarneiroProf. Francisco Pinheiro
Durante a segunda guerra mundial foi levantado um problema, nos EUA, que desafiou os estudiosos de ciências exatas. Este
problema ficou conhecido pelo nome de “Problema da Dieta” e se resumia em descobrir qual a alimentação mais econômica,
levando-se em conta que o organismo humano necessita de uma quantidade mínima diária de certos nutrientes (tais como
proteínas, vitaminas, etc), que devem ser obtidos de alimentos que possuem preços diferentes e composição de nutrientes
diferentes. O desafio foi publicado no conhecido jornal The New York Times e ganhou repercussão nacional. A melhor solução
ao problema foi apresentada por George Stigler, em 1945, na qual partindo de 77 alimentos e levando-se em consideração
a composição de 9 nutrientes em cada um, ele chegou à conclusão de que a dieta ideal implicaria um custo de US$ 59,88 e
seria composta de farinha de trigo, repolho e fígado de porco. A solução apresentada era inusitada, pois Stigler não levou
em consideração nenhum aspecto de diversidade, gosto, aspecto, etc: apenas considerou aspectos econômicos. O valor do
custo de sua composição ficava muito abaixo das outras propostas mas, certamente, ninguém iria manter aquela única
alimentação por qualquer período. Assim, o concurso foi alvo de muitas chacotas, mas em pouco tempo se constatou que
aquela técnica poderia ser utilizada sem rejeição em áreas semelhantes, tais como alimentação de animais ou carga de um
alto forno de uma siderurgia. Imediatamente se iniciaram tais estudos, mas a técnica utilizada por Stigler (tentativas) se
mostrou sujeita a erros, extremamente tediosa e cansativa, além de nem sempre encontrar a solução ótima.
Esta abordagem de planejamento somente se consolidou com George Dantzig, em 1947 que desenvolveu o Método Simplex,
capaz de resolver qualquer problema de PL. Dantzig desenvolveu esta técnica quando trabalhava na Rand Corporation no
projeto SCOOP (Scientific Computation of Optimum Programs) para a Força Aérea Americana, desenvolvendo técnicas de
otimização para problemas militares para a distribuição ótima de tropas. O algoritmo SIMPLEX implica em uma quantidade
grande cálculos e no início, ele se apoiou exclusivamente na resolução manual. Com o surgimento do computador em 1951, a
PL encontrou o seu aliado natural e foi se expandindo de uma maneira extraordinária, Na década de sessenta a PL tinha a
mesma divulgação e fascínio também obtido por outras técnicas, tal como a Gestão pela Qualidade Total obteve nas
décadas de oitenta e noventa. Do ponto de vista histórico, é importante saber que o assunto foi inicialmente analisado em
1936 por Wassily Leontieff, que criou um modelo constituído por um conjunto de equações lineares, considerado como o
primeiro passo para o estabelecimento das técnicas de Programação Linear. O matemático Russo L.V. Kantorovick, em 1939,
publicou um trabalho sobre planejamento da produção, o qual apresentava, dentre diversas abordagens, o uso de equações
lineares. Este trabalho somente veio a ser conhecido no Ocidente em 1960. É importante ainda citar que, em 1940, Frank L.
Hitchcock apresentou uma abordagem ao problema de transportes.
INTRODUÇÃO À PESQUISA OPERACIONAL
Aspectos Históricos
Prof. Airton CarneiroProf. Francisco Pinheiro
Durante a segunda guerra mundial foi levantado um problema, nos EUA,
que desafiou os estudiosos de ciências exatas. Este problema ficou
conhecido pelo nome de “Problema da Dieta” e se resumia em descobrir
qual a alimentação mais econômica, levando-se em conta que o
organismo humano necessita de uma quantidade mínima diária de certos
nutrientes (tais como proteínas, vitaminas, etc), que devem ser obtidos de
alimentos que possuem preços diferentes e composição de nutrientes
diferentes. O desafio foi publicado no conhecido jornal The New York
Times e ganhou repercussão nacional. A melhor solução ao problema foi
apresentada por George Stigler, em 1945, na qual partindo de 77
alimentos e levando-se em consideração a composição de 9 nutrientes em
cada um, ele chegou à conclusão de que a dieta ideal implicaria um custo
de US$ 59,88 e seria composta de farinha de trigo, repolho e fígado de
porco. A solução apresentada era inusitada, pois Stigler não levou
em consideração nenhum aspecto de diversidade, gosto, aspecto,
etc: apenas considerou aspectos econômicos.
INTRODUÇÃO À PESQUISA OPERACIONAL
Aspectos Históricos
Prof. Airton CarneiroProf. Francisco Pinheiro
O valor do custo de sua composição ficava muito abaixo das outras
propostas mas, certamente, ninguém iria manter aquela única alimentação
por qualquer período. Assim, o concurso foi alvo de muitas chacotas, mas
em pouco tempo se constatou que aquela técnica poderia ser utilizada sem
rejeição em áreas semelhantes, tais como alimentação de animais ou carga
de um alto forno de uma siderurgia. Imediatamente se iniciaram tais
estudos, mas a técnica utilizada por Stigler (tentativas) se mostrou sujeita a
erros, extremamente tediosa e cansativa, além de nem sempre encontrar a
solução ótima.
Esta abordagem de planejamento somente se consolidou com George
Dantzig, em 1947 que desenvolveu o Método Simplex, capaz de resolver
qualquer problema de PL. Dantzig desenvolveu esta técnica quando
trabalhava para a Força Aérea Americana, desenvolvendo técnicas de
otimização para problemas militares na distribuição ótima de tropas.
INTRODUÇÃO À PESQUISA OPERACIONAL
Aspectos Históricos
Prof. Airton CarneiroProf. Francisco Pinheiro
O algoritmo SIMPLEX implica em uma quantidade grande cálculos e no
início, ele se apoiou exclusivamente na resolução manual. Com o surgimento
do computador em 1951, a PL encontrou o seu aliado natural e foi se
expandindo de uma maneira extraordinária, Na década de sessenta a PL
tinha a mesma divulgação e fascínio também obtido por outras técnicas, tal
como a Gestão pela Qualidade Total obteve nas décadas de oitenta e
noventa. Do ponto de vista histórico, é importante saber que o assunto foi
inicialmente analisado em 1936 por Wassily Leontieff, que criou um modelo
constituído por um conjunto de equações lineares, considerado como o
primeiro passo para o estabelecimento das técnicas de Programação
Linear. O matemático Russo L.V. Kantorovick, em 1939, publicou um
trabalho sobre planejamento da produção, o qual apresentava, dentre
diversas abordagens, o uso de equações lineares. Este trabalho somente
veio a ser conhecido no Ocidente em 1960. É importante ainda citar que,
em 1940, Frank L. Hitchcock apresentou uma abordagem ao problema de
transportes.
INTRODUÇÃO À PESQUISA OPERACIONAL
Aspectos Históricos
Prof. Airton CarneiroProf. Francisco Pinheiro
Analisar um novo sistema antes de sua
implantação.
Melhorara operação de um sistema já existente.
Compreender melhor o funcionamento de um
sistema.
Por que Modelar e Simular?
INTRODUÇÃO À PESQUISA OPERACIONAL
Confrontar resultados.
Medir eficiências.
Prof. Airton CarneiroProf. Francisco Pinheiro
Pela sua posição média, o bêbado está vivo...
Mas, na média, o bêbado está morto...
INTRODUÇÃO À PESQUISA OPERACIONAL
O cuidado com as PALAVRAS: O bêbado está vivo ou morto?
Prof. Airton CarneiroProf. Francisco Pinheiro
 Rotas de Transporte: Qual deve ser o roteiro de
transporte de veículos de carga de modo que entreguem
toda a carga no menor tempo e no menor custo total?
 Alimentação: Que alimentos as pessoas (ou animais)
devem utilizar de modo que o custo seja mínimo e que
possuam os nutrientes nas quantidades adequadas e que
também atendam a outros requisitos, tais como
variedade entre as refeições, aspecto, gosto, etc?
Aplicações da PL
INTRODUÇÃO À PESQUISA OPERACIONAL
Prof. Airton CarneiroProf. Francisco Pinheiro
 Siderurgia: Quais minérios devem ser carregados no
alto-forno de modo a se produzir, ao menor custo, um
determinado aço dentro de determinadas
especificações de elementos químicos?
 Manufatura: Qual deve ser a composição de
produtos a serem fabricados por uma empresa, de
modo que se atinja o lucro máximo, sendo respeitadas
as limitações ou exigências do mercado comprador e a
capacidade de produção da fábrica?
Aplicações da PL
INTRODUÇÃO À PESQUISA OPERACIONAL
Prof. Airton CarneiroProf. Francisco Pinheiro
 Agricultura: Que alimentos devem ser plantados de
modo que o lucro seja máximo e sejam respeitadas as
características do solo, do mercado comprador e dos
equipamentos disponíveis?
 Petróleo: Qual deve ser a mistura de petróleo a ser
enviada para uma torre de craqueamento para
produzir seus derivados (gasolina, diesel, querosene
etc) a um custo mínimo? Os petróleos são de diversas
procedências e possuem composição diferentes.
Aplicações da PL
INTRODUÇÃO À PESQUISA OPERACIONAL
Prof. Airton CarneiroProf. Francisco Pinheiro
 Mineração: Em que sequência deve-se lavrar
blocos de minério abaixo do solo dados sua
composição, posicionamento e custos de extração?
 Carteira de Investimentos: Quais ações devem
compor uma carteira de investimentos de modo que o
lucro seja máximo e sejam respeitadas as previsões de
lucratividade e as restrições governamentais?
Aplicações da PL
INTRODUÇÃO À PESQUISA OPERACIONAL
Prof. Airton CarneiroProf. Francisco Pinheiro
 Localização Industrial: Onde devem ser localizadas
as fábricas e os depósitos de um novo empreendimento
industrial de modo que os custos de entrega do produto
aos varejistas sejam minimizados.
Aplicações da PL
INTRODUÇÃO À PESQUISA OPERACIONAL
Prof. Airton CarneiroProf. Francisco Pinheiro
 Redes Logísticas 
 Manufatura
 Terminais: portos, aeroportos, estações rodoviárias e 
ferroviárias
 Hospitais
 Militar
 Redes de Computadores 
 Reengenharia de Processos
 Supermercados, Redes de “Fast Food” e franquias.
 Parques de Diversões.
 Tráfego…
Áreas de aplicação
INTRODUÇÃO À PESQUISA OPERACIONAL
Prof. Airton CarneiroProf. Francisco Pinheiro
EXEMPLO: Considere que você é uma marceneiro e
produz mesas e cadeiras.
PLANEJAMENTO DE PRODUÇÃO
Prof. Airton CarneiroProf. Francisco Pinheiro
 Se você pudesse, planejaria produzir os dois
produtos ao mesmo tempo, e a todo tempo.
 Mas, isto não é possível pois você é o único
marceneiro da fábrica.
Qual é a decisão?
PLANEJAMENTO DE PRODUÇÃO
Prof. Airton CarneiroProf. Francisco Pinheiro
 Para garantir o melhor lucro, você precisa
decidir quanto de cada produto produzir na
semana.
Qual é a decisão?
PLANEJAMENTO DE PRODUÇÃO
Prof. Airton CarneiroProf. Francisco Pinheiro
 Chamemos assim:
 x1 a quantidade de mesas que você produz
por semana;
 x2 a quantidade de cadeiras que você
produz por semana;
PLANEJAMENTO DE PRODUÇÃO
Prof. Airton CarneiroProf. Francisco Pinheiro
O que nós criamos, x1 e x2, são as chamadas
Variáveis de Decisão;
As variáveis de decisão são aqueles valores que
representam o cerne do problema, e que podemos
escolher (decidir) livremente;
Variáveis de Decisão
PLANEJAMENTO DE PRODUÇÃO
Prof. Airton CarneiroProf. Francisco Pinheiro
Entretanto, existe um pequeno problema:
 A mesa tem tampo de vidro, logo o custo de
produção é mais caro e cada uma custa R$180,00;
 A cadeira é mais simples, com isto o custo de
produção é somente R$100,00;
Entretanto o marceneiro possui apenas R$ 800,00!
Como fazer para garantir que você não vai se
endividar?
Problemas Financeiros
PLANEJAMENTO DE PRODUÇÃO
Prof. Airton CarneiroProf. Francisco Pinheiro
Se você produzir mesas x1 vezes na semana, e
cada vez gasta R$180,00, então você gasta R$
180x1 por semana!
Fazendo o mesmo raciocínio para a cadeira,
você gasta R$ 100x2 por semana. No geral
temos o seguinte:
21 100180 xx 
800
gasto total da semana total disponível por semana
garantia
PLANEJAMENTO DE PRODUÇÃO
Prof. Airton CarneiroProf. Francisco Pinheiro
As diferenças entre os produtos não são apenas
no volume de gastos:
 A cadeira possui mais peças. Cada vez que você
produz uma cadeira, gasta em média 4 horas
do seu tempo produzindo-a.
 Já o tempo de produção de uma mesa é menor,
gastando apenas 2 horas.
Problemas com o relógio
PLANEJAMENTO DE PRODUÇÃO
Prof. Airton CarneiroProf. Francisco Pinheiro
Considere que o marceneiro só trabalhe um turno
por dia, ou seja 20 horas por semana.
Usando a notação anterior, como fazer para
garantir que não vai extrapolar este tempo?
2021 42 xx 
total de horas
garantia
tempo livre
PLANEJAMENTO DE PRODUÇÃO
Prof. Airton CarneiroProf. Francisco Pinheiro
Você já pode se planejar! Decida quantas mesas
(x1) e cadeiras (x2) poderão ser produzidas por
semana!
Vamos ver quantas horas e quanto de dinheiro
nós consumimos, e depois quanto sobra!
800100180
2042
21
21


xx
xx
(horas por semana)
(R$ p/ semana)
Pensando em tudo junto - Restrições
PLANEJAMENTO DE PRODUÇÃO
Prof. Airton CarneiroProf. Francisco Pinheiro
Por exemplo:
– produzir 3 mesas e 2 cadeiras:
x1 = 3
x2 = 2 74021003180
142432


horas
Reais
Consumo
800100180
2042
21
21


xx
xx
(horas por semana)
(R$ p/ semana)
PLANEJAMENTO DE PRODUÇÃO
Prof. Airton CarneiroProf. Francisco Pinheiro
Quanto sobra?
Consumo:
14 horas e
R$740,00 60740800
61420


horas
reais
Sobra
PLANEJAMENTO DE PRODUÇÃO
Prof. Airton CarneiroProf. Francisco Pinheiro
– Produzir 3 mesas e 4 cadeiras:
x1 = 3
x2 = 4
(horas por semana)
(R$ p/ semana)
94041003180
224432


horas
reais
Consumo
800100180
2042
21
21


xx
xx
Outra situação
PLANEJAMENTO DE PRODUÇÃO
Prof. Airton CarneiroProf. Francisco Pinheiro
Consumo:
22 horas e 
R$940,00
(horas por semana)
(R$ p/ semana)
140940800
22220


horas
reais
Sobra
800100180
2042
21
21


xx
xx
Quanto sobra?
PLANEJAMENTO DE PRODUÇÃO
Prof. Airton CarneiroProf. Francisco Pinheiro
Neste exemplo gastaria-se 22 horas, e só há
disponível 20h! Gastaria R$940,00 e só há
disponível R$800,00!
 Esta é uma situação impossível, dentro das
condições que foram propostas.
Isso não pode!
PLANEJAMENTO DE PRODUÇÃO
Prof. Airton CarneiroProf. Francisco Pinheiro
É preciso pensar no objetivo final. O que eu
quero, para obter o melhor?
 Algumas Opções:
produzir a maior quantidade possívelde vezes 
por semana;
21max xx 
Ou Seja:
Falta um objetivo
PLANEJAMENTO DE PRODUÇÃO
Prof. Airton CarneiroProf. Francisco Pinheiro
Suponha que você lucre duas vezes mais com
cadeiras do que com mesas.
Assim, você pode criar um índice que representa a
sua preferência:
21 2max xx 
Outro objetivo possível
PLANEJAMENTO DE PRODUÇÃO
Prof. Airton CarneiroProf. Francisco Pinheiro
0,
800100180
2042
s.r.
max
21
21
21
21




xx
xx
xx
xx
Modelo com o primeiro
objetivo
0,
800100180
2042
s.r.
2max
21
21
21
21




xx
xx
xx
xx
modelo com o segundo
objetivo
Criamos dois modelos diferentes!
PLANEJAMENTO DE PRODUÇÃO
Prof. Airton CarneiroProf. Francisco Pinheiro
EXEMPLO
INTRODUÇÃO À PESQUISA OPERACIONAL
GERENTE GERAL
GERENTE DE ALMOFARIFADO 
GERENTE DE RH
GERENTE DE INSUMOS
GERENTE DA LINHA DE 
PRODUÇÃO - BOLA
GERENTE DA LINHA DE 
PRODUÇÃO - TRIANGULO
GERENTE DA LINHA DE 
PRODUÇÃO - QUADRADO
GERENTE DA LINHA DE 
PRODUÇÃO - RETANGULO
ANALISTA DE MERCADO
Prof. Airton CarneiroProf. Francisco Pinheiro
EXEMPLO
INTRODUÇÃO À PESQUISA OPERACIONAL
GERENTE DE 
ALMOFARIFADO 
GERENTE DE RH
GERENTE DE INSUMOS
ANALISTA DE MERCADO
Prego
Madeira
Quantidade de 
funcionários
Água
Energia
Lucro Bola
Lucro Quadrado
Lucro Triangulo
Lucro Retângulo
Obs: O analista de mercado observou ao longo dos anos que a quantidade de bola é
superior a de retângulo e inferior a soma de triangulo e quadrado.
Prof. Airton CarneiroProf. Francisco Pinheiro
EXEMPLO
INTRODUÇÃO À PESQUISA OPERACIONAL
GERENTE DA LINHA DE 
PRODUÇÃO - BOLA
GERENTE DA LINHA DE 
PRODUÇÃO - TRIANGULO
GERENTE DA LINHA DE 
PRODUÇÃO - QUADRADO
GERENTE DA LINHA DE 
PRODUÇÃO - RETANGULO
Quanto de prego, madeira, pessoas, água e energia é 
necessário da produção do produto BOLA
Quanto de prego, madeira, pessoas, água e energia é 
necessário da produção do produto TRIANGULO
Quanto de prego, madeira, pessoas, água e energia é 
necessário da produção do produto QUADRADO
Quanto de prego, madeira, pessoas, água e energia é 
necessário da produção do produto RETANGULO
Prof. Airton CarneiroProf. Francisco Pinheiro
 Em problemas reais de otimização busca-se
maximizar ou minimizar uma quantidade
específica, chamada objetivo, que depende de
um número finito de variáveis de entrada.
 As variáveis de entrada podem ser
• Independentes uma das outras
• Relacionadas umas com as outras por meio
de uma ou mais restrições
O Objeto que trabalharemos: Problemas de Otimização
INTRODUÇÃO À PESQUISA OPERACIONAL
Prof. Airton CarneiroProf. Francisco Pinheiro
Um problema de programação matemática é linear
se a função objetivo e cada uma das restrições
forem lineares das respectivas variáveis de entrada
INTRODUÇÃO À PESQUISA OPERACIONAL
Programação Linear
Otimizar: 
Sujeito a: 
z f x x x
g x x x
g x x x
g x x x
b
b
b
n
n
n
n n n


















( , ,..., )
( , ,..., )
( , ,..., )
:
( , ,..., )
:
1 2
1 1 2
2 1 2
1 2
1
2
Prof. Airton CarneiroProf. Francisco Pinheiro
 A presença de qualquer das expressões abaixo
tornam o problema não linear
 
1
1
1
;1;
x
nx
n

  basequalquer com ;log 1x
aa
x
 dealor qualquer v para ;1
etc. );cos();(sen 11 xx
INTRODUÇÃO À PESQUISA OPERACIONAL
Quebrando a linearidade
Prof. Airton CarneiroProf. Francisco Pinheiro
 Os exemplos criados anteriormente eram
Problemas de Programação Linear:
0,
800100180
2042
s.r.
max
21
21
21
21




xx
xx
xx
xx
0,
800100180
2042
s.r.
2max
21
21
21
21




xx
xx
xx
xx
INTRODUÇÃO À PESQUISA OPERACIONAL
Exemplos
Prof. Airton CarneiroProf. Francisco Pinheiro
 Existem 4 características para um problema na
forma padrão:
A função objetivo é de Maximizar;
As restrições são todas com sinal de menor ou
igual;
As constantes de todas as restrições são não
negativas;
As variáveis são todas não negativas.
INTRODUÇÃO À PESQUISA OPERACIONAL
Forma Padrão
Prof. Airton CarneiroProf. Francisco Pinheiro
0,...,,
...
:
...
...
 :a Sujeito
... Maximizar 
321
2211
22222121
11212111
2211





n
mnmnmm
nn
nn
nn
xxxx
bxaxaxa
bxaxaxa
bxaxaxa
xcxcxcZ
não 
negativos
INTRODUÇÃO À PESQUISA OPERACIONAL
Forma Padrão
Prof. Airton CarneiroProf. Francisco Pinheiro
 Solução Viável é uma solução em que todas as
restrições são satisfeitas;
 Solução Inviável é uma solução em que alguma das
restrições ou as condições de não-negatividade
não são atendidas;
INTRODUÇÃO À PESQUISA OPERACIONAL
Classificação das Soluções
Prof. Airton CarneiroProf. Francisco Pinheiro
0,
800100180
2042
s.r.
max
21
21
21
21




xx
xx
xx
xx
x1 = 3
x2 = 2
S = (3,2)
Solução viável:
todas as restrições
são atendidas
x1 = 3
x2 = 4
S=(3,4)
Solução inviável:
as restrições não
são respeitadas
INTRODUÇÃO À PESQUISA OPERACIONAL
Exemplos de Solução Viável e Inviável
Prof. Airton CarneiroProf. Francisco Pinheiro
 É especialmente importante verificar como fica o
valor de Z nas soluções viáveis que podemos
determinar: )1,1(S 2Z
0,
800100180
2042
s.r.
max
21
21
21
21




xx
xx
xx
xx
)1,2(S 3Z )2,3(S 5Z
INTRODUÇÃO À PESQUISA OPERACIONAL
A Solução
Prof. Airton CarneiroProf. Francisco Pinheiro
 A Solução Ótima é uma solução viável especial. De
todas as soluções viáveis, aquela que obtiver o
valor da função objetivo mais adequado é
chamada de ótima;
 A grande questão é como determinar a solução
ótima!
 Isto veremos a partir das aulas seguintes.
INTRODUÇÃO À PESQUISA OPERACIONAL
A Solução Ótima
Prof. Airton CarneiroProf. Francisco Pinheiro
Faça as seguintes modelagens:
Exercício 1: Um produtor de frutas pode
transportar até 800 caixas de frutas para sua
região de vendas. Ele necessita transportar
exatamente 200 caixas de laranja a R$ 20,00 de
lucro por caixa, pelo menos 100 caixas de
pêssegos a R$ 10,00 de lucro por caixa, e no
máximo 200 caixas de tangerinas a R$ 30,00 de
lucro por caixa. De que forma ele deverá carregar
o caminhão para obter o lucro máximo?
INTRODUÇÃO À PESQUISA OPERACIONAL
EXERCÍCIOS
Prof. Airton CarneiroProf. Francisco Pinheiro
Exercício 2: Um confeiteiro fabrica dois tipos de bolo:
chocolate e baunilha. Cada bolo de chocolate é vendido a
R$12,00 e cada um de baunilha a R$ 9,00. Cada bolo de
chocolate requer 45 minutos para bater, 20 minutos para
assar e gasta 4 ovos. Cada bolo de baunilha leva 15
minutos para bater, 40 minutos para assar e gasta 1 ovo. O
confeiteiro dispõe de 8 horas para bater, 8 horas de forno
e de 30 ovos. Ele deseja saber quantos bolos de cada tipo
deve produzir para aumentar sua receita.
INTRODUÇÃO À PESQUISA OPERACIONAL
Prof. Airton CarneiroProf. Francisco Pinheiro
Exercício 3: Uma grande fábrica de móveis dispõe em estoque
de 300m de tábuas, 600m de pranchas e 500m de painéis de
aglomerado. Oferece normalmente 4 modelos de móveis:
Escrivaninha, Mesa, Armário e Prateleira. Os modelos são
vendidos respectivamente por R$100,00; R$80,00; R$120,00;
R$30,00 e consomem:
 Escrivaninha: 1m tábua, 3m de painéis.
 Mesa: 1m tábua, 1m prancha, 2m painéis. Armário: 1m tábua, 1m prancha, 4 painéis.
 Prateleira: 4m tábua, 2 de prancha.
Quanto a empresa deve fabricar de cada produto para ter a
maior receita?
INTRODUÇÃO À PESQUISA OPERACIONAL
Prof. Airton CarneiroProf. Francisco Pinheiro
Exercício 4: A empresa ITAJUBÁ LTDA fabrica e comercializa dois tipos de
cadeiras: a cadeira Jenny, menor, de espaldar mais baixo, e a cadeira Tom,
imponente, de luxo, espaldar alto. O dono da ITAJUBÁ LTDA tem que decidir
qual a quantidade de cada uma das cadeiras tem que produzir para a
próxima feira de móveis. Ambas as cadeiras usam a mesma armação, e o
fabricante tem disponível apenas 200 armações. A diferença básica entre as
cadeiras é a quantidade de couro que cada uma delas gasta e o número de
horas necessárias para se fazer cada tipo de cadeira. A cadeira Jenny,
menor, é mais trabalhosa, e gasta 5 horas de trabalho, enquanto a cadeira
Tom gasta apenas 2. Porém, cada cadeira Jenny gasta apenas 3 metros de
couro, ao passo que cada cadeira Tom gasta 4 metros de couro. ITAJUBÁ
LTDA tem disponíveis 950 homem/horas para o trabalho, e 720 metros de
couro. Cada cadeira Jenny é vendida com um lucro de R$350,00 e a cadeira
Tom é vendida com um lucro de R$300,00. A demanda na feira é grande, de
maneira que toda e qualquer quantidade produzida será vendida. Quantas
cadeiras Tom e quantas cadeiras Jenny a cia ITAJUBÁ LTDA deverá produzir
para maximizar o lucro na feira?
INTRODUÇÃO À PESQUISA OPERACIONAL
Prof. Airton CarneiroProf. Francisco Pinheiro
Exercício 5: Uma refinaria produz três tipos de gasolina: verde, azul e comum. Cada
tipo requer gasolina pura, octana e aditivo que são disponíveis nas quantidades de
9.600.000, 4.800.000, 2.200.000 litros por semana, respectivamente. As
especificações de cada tipo são:
 um litro de gasolina verde requer 0,22 litro de gasolina pura; 0,50 litro de octana e
0,28 litro de aditivo;
 um litro de gasolina azul requer 0,52 litro de gasolina pura, 0,34 de octana e 0,14
litro de aditivo.
 um litro de gasolina comum requer 0,74 litro de gasolina pura, 0,20 litro de octana
e 0,06 litro de aditivo.
Como regra de produção, com base na demanda de mercado, o planejamento da
refinaria estipulou que a quantidade de gasolina comum deve ser no mínimo igual a 16
vezes a quantidade de gasolina verde, e que a quantidade de gasolina azul seja no
máximo igual a 600.000 litros por semana. A empresa sabe que a cada litro de
gasolina verde, azul e comum dá uma margem de contribuição para o lucro de $0,30,
$0,25, e $0,20, respectivamente, e seu objetivo é determinar o programa de produção
que maximiza a margem total de contribuição para o lucro.
INTRODUÇÃO À PESQUISA OPERACIONAL
Prof. Airton CarneiroProf. Francisco Pinheiro
Exercício 6: Uma propriedade apresenta dois talhões florestais aptos
para corte: talhão1 com 40 ha e 84 m³/ha de madeira disponíveis; e
talhao2 com 18 ha e uma produtividade de 112 m³/ha. O custo por
hectare para a administração da venda de madeira é de R$ 300, e a
disponibilidade de capital é de R$15.000,0. Ambos os talhões
permitem o desenvolvimento de atividades recreativas. Anualmente, o
talhão1 é capaz de sustentar a 480 visitantes por hectare e o talhão2
apresenta capacidade para 1920 visitantes por hectare. A
propriedade deve ser capaz de receber no mínimo 10.000
visitantes/ano. Naturalmente, cada hectare cortado fica inutilizado
para atividades de recreação. O problema é determinar quantos
hectares explorar em cada talhão de forma a maximizar o volume de
madeira cortado.
INTRODUÇÃO À PESQUISA OPERACIONAL
Prof. Airton CarneiroProf. Francisco Pinheiro
Exercício 7: Uma metalúrgica deseja maximizar sua
Receita Bruta. A Tabela ilustra a proporção de cada
material na mistura para a obtenção da ligas passíveis de
fabricação. O preço está cotado em Reais por Tonelada
da liga fabricada. Também em toneladas estão expressas
a restrições de disponibilidade de matéria-prima.
RESTRIÇÕES / CUSTOS
INTRODUÇÃO À PESQUISA OPERACIONAL
Prof. Airton CarneiroProf. Francisco Pinheiro
Exercício 1: Um produtor de frutas pode transportar até 800 caixas de
frutas para sua região de vendas. Ele necessita transportar
(EXATAMENTE) 200 caixas de laranja a R$ 20,00 de lucro por caixa,
pelo menos 100 caixas de pêssegos a R$ 10,00 de lucro por caixa, e no
máximo 200 caixas de tangerinas a R$ 30,00 de lucro por caixa. De que
forma ele deverá carregar o caminhão para obter o lucro máximo?
INTRODUÇÃO À PESQUISA OPERACIONAL
EXERCÍCIOS
x1 = nº de caixas de laranjas
x2 = nº de caixas de pêssegos
x3 = nº de caixas de tangerinas
Função Objetivo:
Max Z = 20x1 + 10x2 + 30x3
Restrições:
Caixas de laranja: x1 = 200
Caixas de pêssegos: x2 ≥ 100
Caixas de tangerina: x3 ≤ 200
Lotação do caminhão: x1 + x2 + x3 ≤
800
Não negatividade: x1 ≥0; x2 ≥0; x3 ≥0
Prof. Airton CarneiroProf. Francisco Pinheiro
Exercício 2: Um confeiteiro fabrica dois tipos de bolo: chocolate e baunilha.
Cada bolo de chocolate é vendido a R$12,00 e cada um de baunilha a R$
9,00. Cada bolo de chocolate requer 45 minutos para bater, 20 minutos
para assar e gasta 4 ovos. Cada bolo de baunilha leva 15 minutos para
bater, 40 minutos para assar e gasta 1 ovo. O confeiteiro dispõe de 8 horas
para bater, 8 horas de forno e de 30 ovos. Ele deseja saber quantos bolos
de cada tipo deve produzir para aumentar sua receita.
INTRODUÇÃO À PESQUISA OPERACIONAL
x1 = nº de bolos de chocolate
x2 = nº de bolos de baunilha
Função Objetivo:
Max Z = 12x1 + 9x2
Restrições:
Tempo para bater: 45x1 + 15x2 ≤ 480 min
Tempo para assar: 20x1 + 40x2 ≤ 480 min
Número de ovos: 4x1 + x2 ≤ 30
Não negatividade: x1 ≥0; x2 ≥0
Prof. Airton CarneiroProf. Francisco Pinheiro
Exercício 3: Uma grande fábrica de móveis dispõe em estoque de 300m de
tábuas, 600m de pranchas e 500m de painéis de aglomerado. Oferece
normalmente 4 modelos de móveis: Escrivaninha, Mesa, Armário e Prateleira. Os
modelos são vendidos respectivamente por R$100,00; R$80,00; R$120,00;
R$30,00 e consomem:
 Escrivaninha: 1m tábua, 3m de painéis.
 Mesa: 1m tábua, 1m prancha, 2m painéis.
 Armário: 1m tábua, 1m prancha, 4 painéis.
 Prateleira: 4m tábua, 2 de prancha.
Quanto a empresa deve fabricar de cada produto para ter a maior receita?
INTRODUÇÃO À PESQUISA OPERACIONAL
x1 = quantidade de escrivaninha
x2 = quantidade de mesas
x3 = quantidade de armários
X4 = quantidade de prateleiras
Função Objetivo:
Max Z = 100x1 + 80x2 + 120x3 + 30x4
Restrições:
Tábuas: x1 + x2 + x3 + 4x4 ≤ 300
Pranchas: 0x1 + x2 + x3 + 2x4 ≤ 600
Painéis: 3x1 + 2x2 + 4x3 + 0x4 ≤ 500
Não negatividade: x1≥0; x2≥0; x3≥0; x4 ≥0
Prof. Airton CarneiroProf. Francisco Pinheiro
Exercício 4: A empresa ITAJUBÁ LTDA fabrica e comercializa dois tipos de cadeiras: a cadeira
Jenny, menor, de espaldar mais baixo, e a cadeira Tom, imponente, de luxo, espaldar alto. O
dono da ITAJUBÁ LTDA tem que decidir qual a quantidade de cada uma das cadeiras tem que
produzir para a próxima feira de móveis. Ambas as cadeiras usam a mesma armação, e o
fabricante tem disponível apenas 200 armações. A diferença básica entre as cadeiras é a
quantidade de couro que cada uma delas gasta e o número de horas necessárias para se fazer
cada tipo de cadeira. A cadeira Jenny, menor, é mais trabalhosa, e gasta 5 horas de trabalho,
enquanto a cadeira Tom gasta apenas 2. Porém, cada cadeira Jenny gasta apenas 3 metros de
couro, ao passo que cada cadeira Tom gasta 4 metros de couro. ITAJUBÁ LTDA tem disponíveis
950 homem/horas para o trabalho, e 720 metros de couro. Cada cadeira Jenny é vendida com
um lucro de R$350,00 e a cadeira Tom é vendida com um lucro de R$300,00. A demanda na
feira é grande, de maneira que todae qualquer quantidade produzida será vendida. Quantas
cadeiras Tom e quantas cadeiras Jenny a cia ITAJUBÁ LTDA deverá produzir para maximizar o
lucro na feira?
INTRODUÇÃO À PESQUISA OPERACIONAL
x1 = Nº de cadeiras do tipo Jenny
x2 = Nº de cadeiras do tipo Tom
Função Objetivo:
Max Z = 350x1 + 300x2
Restrições:
Armações: x1 + x2 ≤ 200
Homem/hora: 5x1 + 2x2 ≤ 950
Couro: 3x1 + 4x2 ≤ 720
Não negatividade: x1 ≥0; x2 ≥0
Prof. Airton CarneiroProf. Francisco Pinheiro
Exercício 5: Uma refinaria produz três tipos de gasolina: verde, azul e comum. Cada
tipo requer gasolina pura, octana e aditivo que são disponíveis nas quantidades de
9.600.000, 4.800.000, 2.200.000 litros por semana, respectivamente. As
especificações de cada tipo são:
 um litro de gasolina verde requer 0,22 litro de gasolina pura; 0,50 litro de octana e
0,28 litro de aditivo;
 um litro de gasolina azul requer 0,52 litro de gasolina pura, 0,34 de octana e 0,14
litro de aditivo.
 um litro de gasolina comum requer 0,74 litro de gasolina pura, 0,20 litro de octana
e 0,06 litro de aditivo.
Como regra de produção, com base na demanda de mercado, o planejamento da
refinaria estipulou que a quantidade de gasolina comum deve ser no mínimo igual a 16
vezes a quantidade de gasolina verde, e que a quantidade de gasolina azul seja no
máximo igual a 600.000 litros por semana. A empresa sabe que a cada litro de
gasolina verde, azul e comum dá uma margem de contribuição para o lucro de $0,30,
$0,25, e $0,20, respectivamente, e seu objetivo é determinar o programa de produção
que maximiza a margem total de contribuição para o lucro.
INTRODUÇÃO À PESQUISA OPERACIONAL
Prof. Airton CarneiroProf. Francisco Pinheiro
Exercício 5: Uma refinaria.....RESPOSTA
INTRODUÇÃO À PESQUISA OPERACIONAL
x1 = quantidade de gasolina verde
x2 = quantidade de gasolina azul
x3 = quantidade de gasolina comum
Função Objetivo:
Max Z = 0,3x1 + 0,25x2 + 0,2x3
Restrições:
Gasolina pura: 0,22x1 + 0,52x2 + 0,74x3 ≤ 9.600.000,00
Octana: 0,5x1 + 0,34x2 + 0,20x3 ≤ 4.800.000,00
Aditivo: 3x1 + 2x2 + 4x3 + ≤ 2.200.000,00
Relação Gasol comum e verde: x3 ≥ 16x1 16x1- x3 ≤0
Lim. Gasolina Azul: x2 ≤ 600.000
Não negatividade: x1 ≥0; x2 ≥0; x3 ≥0
Prof. Airton CarneiroProf. Francisco Pinheiro
Exercício 6: Uma propriedade apresenta dois talhões florestais aptos para corte: talhão1
com 40 ha e 84 m³/ha de madeira disponíveis; e talhao2 com 18 ha e uma produtividade de
112 m³/ha. O custo por hectare para a administração da venda de madeira é de R$ 300, e
a disponibilidade de capital é de R$15.000,0. Ambos os talhões permitem o desenvolvimento
de atividades recreativas. Anualmente, o talhão1 é capaz de sustentar a 480 visitantes por
hectare e o talhão2 apresenta capacidade para 1920 visitantes por hectare. A propriedade
deve ser capaz de receber no mínimo 10.000 visitantes/ano. Naturalmente, cada hectare
cortado fica inutilizado para atividades de recreação. O problema é determinar quantos
hectares explorar em cada talhão de forma a maximizar o volume de madeira cortado.
INTRODUÇÃO À PESQUISA OPERACIONAL
x1 = quantidade de Hectares no talhão 1
x2 = quantidade de Hectares no talhão 2
Função Objetivo:
Max Z = 84x1 + 112x2
Restrições:
Área do talhão 1: x1 ≤ 40
Área do talhão 2: x2 ≤ 18
Capital: 300x1 + 300x2 ≤ 15000
Recreaçaõ: 480(40-x1) + 1920(18-x2) ≥ 10.000
Não negatividade: x1 ≥0; x2 ≥0
Prof. Airton CarneiroProf. Francisco Pinheiro
Exercício 7: Uma metalúrgica deseja maximizar sua Receita Bruta. A Tabela ilustra a proporção
de cada material na mistura para a obtenção da ligas passíveis de fabricação. O preço está
cotado em Reais por Tonelada da liga fabricada. Também em toneladas estão expressas a
restrições de disponibilidade de matéria-prima. RESTRIÇÕES / CUSTOS
INTRODUÇÃO À PESQUISA OPERACIONAL
x1 = nº de toneladas de liga de baixa resistência
x2 = nº de toneladas de liga de alta resistência
Função Objetivo:
Max Z = 3000x1 + 5000x2
Restrições:
Disponibilidade de cobre: 0,5x1 + 0,2x2 ≤ 16
Disponibilidade de zinco: 0,25x1 + 0,3x2 ≤ 11
Disponibilidade de chumbo: 0,25x1 + 0,5x2 ≤ 15
Não negatividade: x1 ≥0; x2 ≥0