Aula 1

Transcrição

Aula 1

Introdução
O problema do fazendeiro
O problema do jornaleiro
Uma Introdução à Otimização sob Incerteza
Bernardo Kulnig Pagnoncelli1 e Humberto José Bortolossi2
1
Departamento de Matemática
Pontifı́cia Universidade Católica do Rio de Janeiro
2
Departamento de Matemática Aplicada
Universidade Federal Fluminense
III Bienal da SBM
Universidade Federal de Goiânia
6 a 11 de novembro de 2006
Referências
Introdução
1a aula
Referências
Introdução
Sumário
1
Introdução
2
Introduzindo cenários
EVPI e VSS
3
Enunciado e formulação
Solução
Exemplo
Outras interpretações para o problema
4
Referências
Referências
Introdução
Sumário
1
Introdução
2
EVPI e VSS
3
Solução
Exemplo
4
Referências
Referências
Introdução
Referências
O que é otimização?
Segundo J.L. Nazareth, “Optimization is the art, science, and
mathematics of finding the “best” member of a finite or
infinite set of possible choices, based on some objective
measure of the merit of each choice in the set”.
A área de otimização tem uma longa história de sucesso,
tanto no plano teórico quanto nas aplicações.
Introdução
Referências
Introdução
Referências
Introdução
Referências
Seleção de portfólio
O modelo de Markowitz (1952):
minimizar σp2 =
sujeito a
xT Vx
= Rp ,
T
x 1 = 1.
xt µ
As incertezas µ e V são definidas à priori, usando por exemplo
séries históricas dos ativos. É possı́vel incorporá-las ao modelo
de alguma forma?
Introdução
Referências
minimizar σp2 =
sujeito a
xT Vx
= Rp ,
T
x 1 = 1.
xt µ
de alguma forma?
Introdução
Referências
minimizar σp2 =
sujeito a
xT Vx
= Rp ,
T
x 1 = 1.
xt µ
de alguma forma?
Introdução
A resposta é dada por otimização estocástica. É uma área
voltada para a modelagem e resolução de problemas que
envolvem incertezas.
Diferentemente de otimização determinı́stica, as incertezas
estão explicitamente descritas nos modelos através de
variáveis aleatórias.
Ao invés de definições formais, vamos começar com uma
aplicação de otimização estocástica.
Referências
Introdução
Referências
Introdução
Referências
Introdução
Sumário
1
Introdução
2
EVPI e VSS
3
Solução
Exemplo
4
Referências
Referências
Introdução
Referências
João é um fazendeiro especializado em três culturas: trigo,
milho e cana-de-açúcar.
Ele precisa decidir durante o inverno o que plantar em seus
500 ha de terras.
Cada um dos cultivos possui um custo associado, em R$/ha.
Introdução
Referências
500 ha de terras.
Introdução
Referências
500 ha de terras.
Introdução
Referências
Duas divisões possı́veis de terra
milho
trigo
cana-de-açúcar
cana-de-açúcar
trigo
milho
Introdução
Referências
Restrições
O gado precisa de pelo menos 240 T de trigo e 200 T de
milho.
João pode comprar milho e trigo no mercado local, a preços
elevados. Seu excedente também pode vendido para
atacadistas.
A cana-de-açúcar pode ser vendida por 36 reais por tonelada
(R$/T). O governo impõe uma cota em 6000 T. A partir
desse valor a cana-de-açúcar é vendida por 10 R$/T.
Baseado em experiência pessoal, João sabe que os
rendimentos médios de trigo, milho e cana-de-açúcar são 2.5,
3.0 e 20 T/ha respectivamente.
Introdução
Referências
Restrições
milho.
atacadistas.
Introdução
Referências
Restrições
milho.
atacadistas.
Introdução
Referências
Restrições
milho.
atacadistas.
Introdução
Dados para o problema do fazendeiro
Rendimento (T/ha)
Custo de produção (R$/ha)
Preço de venda (R$/T)
Trigo
2.5
150
170
Preço de compra (R$/T)
238
Mı́nimo para o gado (T)
200
Total de terra disponı́vel: 500 ha
Milho
3.0
230
150
210
240
Cana-de-açúcar
20
260
36(≤ 6000 T)
10(> 6000 T)
–
–
Referências
Introdução
Enunciado
O Problema do fazendeiro
Encontrar uma divisão de terras que maximize o lucro do
fazendeiro sujeito às restrições relativas ao gado, à cota
governamental e à dimensão da propriedade.
Referências
Introdução
Referências
Formulação determinı́stica
minimizar
sujeito a
150 x1 + 230 x2 + 260 x3 +
238 y1 − 170 w1 + 210 y2 − 150 w2 − 36 w3 − 10 w4
x1 + x2 + x3 ≤ 500,
2.5 x1 + y1 − w1 ≥ 200,
3 x2 + y2 − w2 ≥ 240,
w3 + w4 ≤ 20 x3 ,
w3 ≤ 6000,
x1 , x2 , x3 , y1 , y2 , w1 , w2 , w3 , w4 ≥ 0.
Introdução
Referências
Esse é um problema de otimização linear! Podemos escrevê-lo
em AMPL, uma linguagem apropriada para otimização e fácil
de aprender (http://www.ampl.com/).
Existem resolvedores eficientes disponı́veis gratuitamente
(http://www.ampl.com/DOWNLOADS/cplex80.html).
A solução completa do problema foi obtida através do
resolvedor CPLEX.
Introdução
Referências
resolvedor CPLEX.
Introdução
Referências
resolvedor CPLEX.
Introdução
Solução do problema
Trigo
Área (ha)
120
Total produzido 300
Total vendido
100
Total comprado
–
Lucro total: R$118 600
Milho
80
240
–
–
Cana-de-açúcar
300
6000
6000
–
Referências
Introdução
Referências
Pronto, o problema está resolvido!
Mas...
João não tem tanta certeza sobre os valores dos rendimentos
médios, afinal mudanças climáticas podem alterar bastante
suas estimativas e, conseqüentemente, seus lucros.
Introdução
Referências
Mas...
Introdução
Referências
Mas...
Introdução
Referências
Solução ótima com rendimentos 20% acima da média.
Suponha que num ano particularmente favorável, os
rendimentos das culturas foram 20% acima da média. Qual é
a solução do problema neste caso?
Trigo
183.33
Área (ha)
Total produzido
550
Total vendido
350
Total comprado
Milho
66.67
240
-
Cana-de-açúcar
250
6000
6000
-
Introdução
Referências
Suponha que num ano particularmente favorável, os
rendimentos das culturas foram 20% acima da média. Qual é
a solução do problema neste caso?
Trigo
183.33
Área (ha)
Total produzido
550
Total vendido
350
Total comprado
Milho
66.67
240
-
Cana-de-açúcar
250
6000
6000
-
Introdução
Referências
Em um ano particularmente desfavorável, os rendimentos das
culturas foram 20% abaixo da média. Qual é a a solução do
problema neste caso?
Trigo
100
Área (ha)
Total produzido 200
Total vendido
Total comprado
Milho
25
60
180
Cana-de-açúcar
375
6000
6000
-
Introdução
Referências
Em um ano particularmente desfavorável, os rendimentos das
culturas foram 20% abaixo da média. Qual é a a solução do
problema neste caso?
Trigo
100
Área (ha)
Total produzido 200
Total vendido
Total comprado
Milho
25
60
180
Cana-de-açúcar
375
6000
6000
-
Introdução
Referências
Sensibilidade da solução
Mudanças de 20% nos rendimentos das culturas em relação
ao rendimento médio fazem o seu lucro variar de R$59 950 a
R$167 667!
Pensando na cana-de-açúcar, João tem o seguinte dilema: se
a área reservada para a cana-de-açúcar for muito grande e os
rendimentos forem acima da média, então ele terá que vender
parte da produção a um preço desfavorável.
Por outro lado, se ele reservar uma área muito pequena e os
rendimentos foram abaixo da média, então ele terá perdido a
oportunidade de vender cana-de-açúcar a um preço favorável.
Como encontrar uma solução que seja satisfatória para todos
os cenários?
Introdução
Referências
R$167 667!
os cenários?
Introdução
Referências
R$167 667!
os cenários?
Introdução
Referências
R$167 667!
os cenários?
Introdução
Forma extensa de um problema estocástico
minimizar
150 x1 + 230 x2 + 260 x3
1
− (170 w11 − 238 y11 + 150 w21 − 210 y21 + 36 w31 + 10 w41 )
3
1
− (170 w12 − 238 y12 + 150 w22 − 210 y22 + 36 w32 + 10 w42 )
3
1
− (170 w13 − 238 y13 + 150 w23 − 210 y23 + 36 w33 + 10 w43 )
3
Referências
Introdução
Restrições
sujeito a
x1 + x2 + x3 ≤ 500
3 x1 + y11 − w11 ≥ 200, 3.6 x2 + y21 − w21 ≥ 240,
w31 + w41 ≤ 24 x3 , w31 ≤ 6000,
2.5 x1 + y12 − w12 ≥ 200, 3 x2 + y22 − w22 ≥ 240,
w32 + w42 ≤ 20 x3 , w32 ≤ 6000,
2 x1 + y13 − w13 ≥ 200, 2.4 x2 + y23 − w23 ≥ 240,
w33 + w43 ≤ 16 x3 , w33 ≤ 6000
x1 , x2 , x3 ≥ 0,
y11 , y21 , y12 , y22 , y13 , y23 ≥ 0,
w11 , w21 , w31 , w41 , w12 , w22 , w32 , w42 , w13 , w23 , w33 , w43 ≥ 0
Referências
Introdução
Referências
As variáveis xi são ditas de primeiro estágio: seu valor deve
ser determinado antes que se conheça a condição climática.
As variáveis yis e wis são de segundo estágio: elas são
escolhidas após a definição dos valores de xi e do
conhecimento do clima. Elas corrigem possı́veis déficits na
alimentação do gado gerados pelas escolhas xi de primeiro
estágio.
O problema estocástico na forma extensa é linear e pode ser
resolvido da mesma forma que fizemos para a formulação
inicial.
Introdução
Referências
estágio.
inicial.
Introdução
Referências
estágio.
inicial.
Introdução
Referências
Solução estocástica
estágio
s=1
(Acima)
Área (ha)
Rendimento (T)
Venda (T)
Trigo
170
510
310
s=2
(Média)
Compra(T)
Rendimento (T)
Venda (T)
–
425
225
–
240
–
s=3
(Abaixo)
Compra(T)
Rendimento (T)
Venda (T)
–
340
140
–
192
–
–
48
1o
Compra(T)
Milho
80
288
48
Cana-de-açúcar
250
6000
6000
(preço favorável)
–
5000
5000
–
4000
4000
–
Introdução
Referências
Análise da solução
A solução ótima do problema estocástico não é igual a
nenhuma das soluções encontradas anteriormente:
(x1 , x2 , x3 ) = (170, 80, 250).
No caso em que os rendimentos são 20% abaixo da média,
temos a necessidade de se comprar milho no mercado devido a
baixa produtividade.
Queremos agora estudar a qualidade da solução estocástica,
isto é, queremos mensurar o ganho em se considerar as
variações climáticas bem como o quanto se deixa de ganhar
por não se conhecer com exatidão o futuro.
Introdução
Referências
(x1 , x2 , x3 ) = (170, 80, 250).
Introdução
Referências
(x1 , x2 , x3 ) = (170, 80, 250).
Introdução
Referências
EVPI e VSS
Valor esperado de informação perfeita (EVPI)
O EVPI mede o quanto perdemos por não saber com exatidão
o futuro.
Para calculá-lo temos que fazer a média entre os rendimentos
obtidos conhecendo-se cada um dos cenários climáticos e
subtrair esse valor do ganho com a solução estocástica.
Temos
EVPI = RP − WS =
R$ 59 950 + R$ 167 667 + R$ 118 600
= R$ 7 016.
− 108 390 +
3
Introdução
Referências
EVPI e VSS
o futuro.
Temos
EVPI = RP − WS =
R$ 59 950 + R$ 167 667 + R$ 118 600
= R$ 7 016.
− 108 390 +
3
Introdução
Referências
EVPI e VSS
o futuro.
Temos
EVPI = RP − WS =
R$ 59 950 + R$ 167 667 + R$ 118 600
= R$ 7 016.
− 108 390 +
3
Introdução
Referências
Valor da solução estocástica (VSS)
O VSS mede o ganho em se considerar o modelo estocástico
ao invés de assumir rendimentos médios.
Para calculá-lo, pense que João é um fazendeiro teimoso: ele
divide suas terras supondo que os rendimentos são os médios.
Resolve-se o problema inicial para cada cenário, fixando
(x1 , x2 , x3 ) = (120, 80, 300).
Dessa forma o VSS é dado por
VSS = EEV − RP
R$ 55 120 + R$ 118 600 + R$ 148 000
−
+ R$108 390 = R$ 1 150.
3
Introdução
Referências
(x1 , x2 , x3 ) = (120, 80, 300).
VSS = EEV − RP
R$ 55 120 + R$ 118 600 + R$ 148 000
−
+ R$108 390 = R$ 1 150.
3
Introdução
Referências
(x1 , x2 , x3 ) = (120, 80, 300).
VSS = EEV − RP
R$ 55 120 + R$ 118 600 + R$ 148 000
−
+ R$108 390 = R$ 1 150.
3
Introdução
Sumário
1
Introdução
2
EVPI e VSS
3
Solução
Exemplo
4
Referências
Referências
Introdução
Referências
João tem um irmão na cidade chamado José, que é jornaleiro.
Toda manhã ele vai ao editor do jornal e tem que decidir
quantos jornais comprar sem saber a demanda daquele dia.
Seu poder de compra é limitado, ou seja, ele pode comprar
até uma quantidade fixa u. Além disso, os jornais não
vendidos podem ser devolvidos ao editor, a um preço menor
do que o valor pago no inı́cio do dia.
Introdução
Referências
Introdução
Referências
Introdução
Formulação
min {cx + Q(x)}
0≤x≤u
onde
Q(x) = Eξ [Q(x, ξ)]
e
Q(x, ξ)
=
min
sujeito a
−qy (ξ) − rw (ξ)
y (ξ) ≤ ξ,
y (ξ) + w (ξ) ≤ x,
y (ξ), w (ξ) ≥ 0.
Referências
Introdução
Referências
Assim como no problema do fazendeiro, o problema do
jornaleiro é estruturado em dois estágios: no primeiro estágio
José decide quantos jornais vai comprar através da variável x.
As variáveis de segundo estágio representam quanto ele
conseguiu vender (y (ξ)) e quanto ele devolveu ao editor
(w (ξ)).
José procura a quantidade ótima de jornais a comprar de
forma a maximizar seu lucro esperado sob incerteza de
demanda.
Introdução
Referências
(w (ξ)).
demanda.
Introdução
Referências
(w (ξ)).
demanda.
Introdução
Referências
Solução
O primeiro passo para encontrar uma solução explı́cita do
problema do jornaleiro é resolver o problema de segundo
estágio.
A solução é imediata: y ∗ (ξ) = min{ξ, x} e
w ∗ (ξ) = max{x − ξ, 0}.
Com isso temos Q(x) = Eξ [−q min{ξ, x} − r max{x − ξ, 0}].
Introdução
Referências
Solução
estágio.
w ∗ (ξ) = max{x − ξ, 0}.
Introdução
Referências
Solução
estágio.
w ∗ (ξ) = max{x − ξ, 0}.
Introdução
Referências
Vamos aprender mais à frente que a função Q é convexa,
contı́nua e, se ξ é v.a. contı́nua, derivável.
Como estamos no intervalo [0, u], se cx + Q′ (0) > 0, então a
derivada não troca de sinal no intervalo e solução ótima é
x ∗ = 0.
Se cx + Q′ (u) < 0, então a solução ótima é x ∗ = u.
Vamos procurar por soluções de cx + Q′ (x) = 0.
Introdução
Referências
x ∗ = 0.
Introdução
Referências
x ∗ = 0.
Introdução
Referências
x ∗ = 0.
Introdução
A expressão para Q é
Z x
Z
Q(x) =
(−qt − r (x − t))f (t) dt +
−qx f (t) dt.
x
−∞
Rearrumando, temos
Z
Q(x) = −(q − r )
∞
x
t f (t)dt − rxF (x) − qx(1 − F (x)).
−∞
Usando integração por partes obtém-se
Z x
Q(x) = −qx + (q − r )
F (t)dt.
−∞
Referências
Introdução
Z x
Z
Q(x) =
(−qt − r (x − t))f (t) dt +
−qx f (t) dt.
x
−∞
Rearrumando, temos
Z
Q(x) = −(q − r )
∞
x
t f (t)dt − rxF (x) − qx(1 − F (x)).
−∞
Z x
Q(x) = −qx + (q − r )
F (t)dt.
−∞
Referências
Introdução
Z x
Z
Q(x) =
(−qt − r (x − t))f (t) dt +
−qx f (t) dt.
x
−∞
Rearrumando, temos
Z
Q(x) = −(q − r )
∞
x
t f (t)dt − rxF (x) − qx(1 − F (x)).
−∞
Z x
Q(x) = −qx + (q − r )
F (t)dt.
−∞
Referências
Introdução
Referências
Derivando, chegamos a Q′ (x) = −q + (q − r )F (x).
Finalmente, a solução do problema é

∗

se q−c

q−r < F (0),
x = 0,
q−c
∗
x = u,
se q−r > F (u),


x ∗ = F −1 q−c , caso contrário.
q−r
Qualquer modelagem razoável da demanda ξ admite que ela
só assume valores positivos, e portanto não temos x ∗ = 0.
Introdução
Referências

∗

se q−c

q−r < F (0),
x = 0,
q−c
∗
x = u,
se q−r > F (u),


q−r
Introdução
Referências

∗

se q−c

q−r < F (0),
x = 0,
q−c
∗
x = u,
se q−r > F (u),


q−r
Introdução
Referências
Exemplo
Um exemplo numérico
Suponha que o custo do jornal para o jornaleiro seja c = 10,
que o preço de venda seja q = 25, que o preço de devolução
seja r = 5 e que o poder de compra é u = 150.
A demanda ξ é uma variável aleatória uniforme no intervalo
[50, 150].
A solução é x ∗ = F −1 (3/4) = 125.
Introdução
Referências
Exemplo
[50, 150].
A solução é x ∗ = F −1 (3/4) = 125.
Introdução
Referências
Exemplo
[50, 150].
A solução é x ∗ = F −1 (3/4) = 125.
Introdução
Referências
VSS
Inicialmente precisamos calcular a solução ótima para
ξ = 100. A solução é trivial: se a demanda é 100, então
compre x ∗ = 100 jornais!
Precisamos calcular o EEV, que é igual a
Eξ [10 · 100 + Q(100, ξ)] = 1000 − 25 · 100 + 20
75
= 1000 − 2500 + 20
− 25 = −1250,
2
Conclui-se que VSS = 1312.5 − 1250 = 62.5.
Z
100
50
ξ − 50
dξ
100
Introdução
Referências
VSS
Eξ [10 · 100 + Q(100, ξ)] = 1000 − 25 · 100 + 20
75
= 1000 − 2500 + 20
− 25 = −1250,
2
Z
100
50
ξ − 50
dξ
100
Introdução
Referências
VSS
Eξ [10 · 100 + Q(100, ξ)] = 1000 − 25 · 100 + 20
75
= 1000 − 2500 + 20
− 25 = −1250,
2
Z
100
50
ξ − 50
dξ
100
Introdução
EVPI
Se conhecemos o valor da demanda ξ, então a solução é
x ∗ = ξ.
Assim, temos que
WS = Eξ [cξ + −qξ] = −15Eξ (ξ) = −1500.
Logo, EVPI = 1500 − 1312.5 = 187.5.
Referências
Introdução
EVPI
x ∗ = ξ.
Assim, temos que
WS = Eξ [cξ + −qξ] = −15Eξ (ξ) = −1500.
Logo, EVPI = 1500 − 1312.5 = 187.5.
Referências
Introdução
EVPI
x ∗ = ξ.
Assim, temos que
WS = Eξ [cξ + −qξ] = −15Eξ (ξ) = −1500.
Logo, EVPI = 1500 − 1312.5 = 187.5.
Referências
Introdução
Custo marginal
Vamos usar o conceito de ganho marginal para derivar a
solução do problema por uma outra trilha.
A expressão ganho marginal em economia se refere ao
crescimento no lucro obtido quando se aumenta em uma
unidade a quantidade vendida ou adquirida de um
determinado bem.
Suponha que jornaleiro comprou k jornais. Qual é o lucro
esperado na venda do k-ésimo jornal?
A resposta é
lucro esperado = P(ξ < k)(r − c) + P(ξ ≥ k)(q − c).
Referências
Introdução
Custo marginal
determinado bem.
A resposta é
Referências
Introdução
Custo marginal
determinado bem.
A resposta é
Referências
Introdução
Custo marginal
determinado bem.
A resposta é
Referências
Introdução
Referências
Se o lucro esperado for negativo temos jornais encalhados e se
o lucro for positivo temos excesso de demanda. A situação
ideal ocorre quando esse lucro é zero.
Nesse caso temos
lucro esperado = 0
= P(ξ < k)(r − c) + P(ξ ≥ k)(q − c)
= F (k)(r − c) + (1 − F (k))(q − c).
Devemos então comprar
k = F −1
q−c
q−r
jornais.
Introdução
Referências
Nesse caso temos
lucro esperado = 0
= P(ξ < k)(r − c) + P(ξ ≥ k)(q − c)
= F (k)(r − c) + (1 − F (k))(q − c).
k = F −1
q−c
q−r
jornais.
Introdução
Referências
Nesse caso temos
lucro esperado = 0
= P(ξ < k)(r − c) + P(ξ ≥ k)(q − c)
= F (k)(r − c) + (1 − F (k))(q − c).
k = F −1
q−c
q−r
jornais.
Introdução
Referências
Estoque zerado
A probabilidade de se vender todos os jornais é
P({vender tudo}) = P(ξ ≥ x) = 1 − F (x).
Para a escolha x ∗ temos
P({vender tudo}) = 1 − F (x ∗ ) = 1 −
q−c
c −r
=
.
q−r
q−r
Conclui-se que se r = 0 então a quantidade de jornal a ser
comprada deve ser escolhida de maneira que a probabilidade
de se vender todos os jornais seja igual a razão custo/preço
unitário.
Introdução
Referências
Estoque zerado
P({vender tudo}) = 1 − F (x ∗ ) = 1 −
q−c
c −r
=
.
q−r
q−r
unitário.
Introdução
Referências
Estoque zerado
P({vender tudo}) = 1 − F (x ∗ ) = 1 −
q−c
c −r
=
.
q−r
q−r
unitário.
Introdução
Sumário
1
Introdução
2
EVPI e VSS
3
Solução
Exemplo
4
Referências
Referências
Introdução
Internet
Página do curso de otimização estocástica lecionado na
PUC-Rio em 2006.1:
http://www.mat.pucrio.br/∼hjbortol/disciplinas/2006.1/soe/
Página da comunidade de otimização estocástica:
http://www.stoprog.org
Banco de artigos de otimização estocástica:
http://edoc.hu-berlin.de/browsing/speps/
Referências
Introdução
Internet
PUC-Rio em 2006.1:
Referências
Introdução
Internet
PUC-Rio em 2006.1:
Referências

Aula 1

Transcrição

Documentos relacionados

A PLANICOM divulga o calendário promocional de cada mês. Então

Água é essencial É um bem natural Ela é bem legal Ajuda no

Estudo para celulas (19-05-13) - Igreja "O Brasil para Cristo

Untitled

Desafiados a renunciar por amor a Jesus

A MARCA DA FERRADURA AUTORES : TONICO E TINOCO VOU

Matriz adjunta, regra de Cramer

1 Segunda Prova: EDO - Mecânica /Integral em 20/10/2015 C. A.

Bases e soluç˜oes de equaç˜oes diferenciai

Matemática Discreta 2011.1