AULA 2 - Solução de Problemas Usando Modelos
Matemáticos
•
•
•
•
O Enfoque da Pesquisa Operacional
Exemplo de motivação - Modelo EOQ
Construindo Modelos Matemáticos
Resolvendo Modelos Matemáticos
– Solução factível e solução ótima
– Solução analítica ou fechada
• Analisando os Resultados
– Validação do Modelo
• Ainda sobre Métodos de Resolução - Busca Heurística
2-1
O Enfoque da Pesquisa Operacional
2-2
Exemplo de Motivação - Modelo EOQ
A empresa H. Intern comercializa diamantes. Ela viaja regularmente
para Antuérpia (Bélgica) para se reabastecer e não pode comprar
menos que 100 quilates/viagem a um custo de $700/quilate. O lucro no
Brasil é de $200/quilate. Cada viagem demora 1 semana e custa
$2000. Manter estoques no Brasil lhe custa $3,50/quilate.semana
(capital empatado e seguros). Se falta produto para vender, ela perde
o lucro esperado. Os custos do ano passado foram:
custos de viagens
manter estoques
lucros não-realizados
Total de custos
=$24.000
=$38.409
=$31.600
=$94.009.
Este custo pode ser diminuído?
2-3
H. Intern - Decisões do ano passado
2-4
Construindo um modelo matemático
• Identificar quais decisões efetivamente resolvem o problema
• Identificar quais as restrições que limitam as decisões a tomar
• Definir objetivos capazes de indicar que uma decisão é preferível a
outras
DECISÕES
– Quando reabastecer o estoque (quando viajar)
– Quanto comprar em cada viagem
RESTRIÇÕES
– Comprar lotes não menores que 100 quilates
OBJETIVOS
– Minimizar os custos de viagens + manter estoque + lucros não-realizados
2-5
Construindo um modelo matemático
DECISÕES:
q := quantidade a ser adquirida em cada reabastecimento
(tamanho do lote)
r := ponto de reabastecimento
(nível de estoque que determina o reabastecimento)
RESTRIÇÕES: (até o momento)
q >= 100
r >= 0
OBJETIVOS: (apenas um, minimizar o custo total anual)
c(q,r) := custo total em função de q e r
2-6
Construindo um modelo matemático
Construindo modelos, sempre aparece a questão de compromisso entre:
A: Construir um modelo complexo (próximo do problema real), mas de
difícil resolução
ou
B: Construir um modelo simples (perda de realismo), mas fácil de
resolver
Em geral, recorre-se a hipóteses simplificadoras:
No problema da H. Intern, a demanda será considerada constante
d := demanda semanal média = 55 quilates/semana
2-7
Construindo um modelo matemático
ciclo = q/55 semanas
hipótese 1:
–com estoque de segurança
–déficit não permitido
hipótese 2:
–sem estoque de segurança
–déficit não permitido
2-8
Construindo um modelo matemático
hipótese 3:
- déficit permitido
2-9
Construindo um modelo matemático
Ainda tentando simplificar o modelo:
Será que podemos descartar o custo de lucro não-realizado (hipótese 3)?
Perceba que descartar este custo equivale a atribuir uma alta penalidade à
falta de produto.
Ou seja, estaremos compensando a falta de produto por um aumento nos
estoques. Será que esta simplificação é razoável?
Será que o custo de estoque já é bastante alto comparado ao de perdas?
Custo de perda = $200/quilate
Custo estoque = $3,5/quilate.semana  200/3,5 = 57,1 semanas
Ou seja: adquirindo um quilate a mais, os 200$ economizados dá para
estocar 1 quilate por 57,1 semanas!
Como em média um lote fica 4 ou 5 semanas em estoque (pg. 2-4), não
parece necessário considerar o custo de perda explicitamente no
modelo.
2-10
Construindo um modelo matemático
O nosso modelo segue então a figura b, já que o estoque de segurança fica
desnecessário devido às hipóteses de demanda constante e perda nula.
RESTRIÇÕES:
Como cada viagem demora 1 semana, a demanda é de 55/semana e não se
admite falta do produto,
r >= 55
q >= 100
(restrição que impede que falte produto;
r >=0 torna-se redundante e é eliminada)
(compra mínima em Antuérpia)
2-11
Construindo um modelo matemático
OBJETIVO: minimizar o custo médio/semana = custo de manter estoque
/semana + custo de reabastecimento/semana
Custo de manter estoque por semana:
Im = estoque médio do ciclo = área do triângulo  ciclo
Custo de manter estoque/ciclo = h . Im . T
pois: h ($/unid.semana) . Im (unid./ciclo) . T (semanas) = h.Im.T ($/ciclo)
Custo de manter estoque/semana = Custo de manter estoque/ciclo  T
= h . Im = 3,5 . q /2
Custo de reabastecimento por semana:
2000  q/55 = 2000 . 55/q
2-11’
Construindo um modelo matemático
O modelo matemático (chamado de EOQ - Economic Order Quantity)
fica:
minimizar c(q,r) = 3,5 q/2 + 2000 . 55/q
sujeito a
q >= 100, r >= 55
Vamos agora resolver o modelo
2-12
Resolvendo modelos matemáticos - solução factível e solução ótima
Resolver um modelo é achar uma solução (valores para as variáveis de
decisão) que não viole as restrições e que otimize (max ou mim) a
função objetivo.
Esta solução é chamada de solução ótima do modelo.
Uma solução que apenas não viola as restrições é dita solução factível.
Modelos são resolvidos através de:
Métodos (algoritmos) Matemáticos  Programação Matemática
ou
Fórmulas fechadas (solução analítica), quando possível
2-13
Resolvendo modelos matemáticos
O modelo EOQ tem uma solução analítica:
Reescrevendo o modelo em função dos parâmetros
q := tamanho do lote
d := demanda semanal (55)
f := custo fixo de reabastecimento (2000)
h := custo unitário semanal para manter estoque (3,5)
l := tempo decorrido entre o ponto de reabastecimento e o recebimento
do novo lote (1 semana) - lead time
m := lote mínimo (100)
OBJETIVO: MIN c(q,r) = h . q/2 + f . (d/q), que tem solução analítica
2 fd
 250,7
q* =
h
r* = l . d = 55
, desde que q* >= m
2-14
Resolvendo modelos matemáticos
O modelo EOQ também admite solução gráfica:
2-15
Resolvendo modelos matemáticos
O custo da solução fica:
c(q*,r*) = $ 877,5 por semana ou
$ 45.630,00 por ano
contra os
$ 94.009,00 do ano passado!
2-16
Analisando os resultados - Validação do modelo
Modelos e suas soluções precisam ser validados, ou seja
• As soluções obtidas aderem à realidade?
• Tais soluções são confiáveis para que decisões baseadas nelas sejam
tomadas?
• Como a solução ótima reage à análise de sensibilidade sobre os
parâmetros?
De particular importância é a análise de sensibilidade :
2-17
Analisando os resultados - Validação do modelo
Suponha que o custo de viagem varie de $1000 a $3000/viagem
Como varia a solução ótima no modelo EOQ?
2-18
Analisando os resultados - Validação do modelo
Os resultados ótimos do modelo podem também ser analisados através
da sua comparação com uma SIMULAÇÃO do que ocorreu no ano
passado.
Vamos construir um programa de computador (simulador) que a cada
semana determine a ação a tomar e calcule o custo real incorrido,
considerando os dados de demanda do ano passado e os resultados
ótimos q* e r* obtidos pelo modelo matemático.
No início de cada semana:
•
•
•
Cheque se o estoque chegou ao nível de reabastecimento r*;
se sim, mande alguém para Antuérpia.
Cheque se alguém chegou de viagem com um novo lote q*;
se sim, atualize o nível de estoque.
No início de cada semana atualize o estoque, subtraindo a demanda ocorrida
na semana.
Calcule o custo total real anual = estoque + viagens + perda de lucro
2-19
Analisando os resultados - Validação do modelo
2-20
Analisando os resultados - Validação do modelo
Os resultados da simulação depois de 52 semanas deu que a solução
ótima do modelo EOQ (q* = 251; r* = 55) tem um custo total real de
$ 108.621 (sendo $ 67.000 o custo de perda)
contra
$ 94.009 do ano passado
Ou seja, se no ano passado H. Intern tivesse adotado a solução ótima
EOQ teria tido um custo adicional de 108.621 - 94.009 = $14.621!
Conclusão: o modelo EOQ está muito simples e precisa ser refeito.
Note que o custo de perda foi o vilão da estória, indicando que a hipótese
de estoque de segurança nulo e/ou perda nula são inadequadas na
prática e que um modelo melhor (mais aderente) deve ser construído.
2-21
Ainda sobre métodos de solução - Busca Heurística
Para solucionar um problema de otimização nem sempre precisamos
construir um modelo matemático.
Certos métodos de solução prescindem de modelos matemáticos.
É o caso dos métodos de busca heurística.
Ache uma solução factível inicial;
Repita k vezes:
Perturbe esta solução, obtendo outra factível e calcule o seu custo;
Se melhorou, guarde essa solução e volte ao passo anterior.
2-22
Ainda sobre métodos de solução - Busca Heurística
Vamos perturbar a solução “ótima” q = 251 r = 55 somando ou
subtraindo 10 unidades em cada iteração.
Calcular o custo real das soluções usando o programa de simulação já
descrito.
2-23
Ainda sobre métodos de solução - Busca Heurística
Vamos reiniciar de uma outra solução:
Custo simulado da melhor solução da busca: $ 54.193 !
(ano passado $ 94.009)
2-24