Aula 1
Transcrição
Aula 1
Introdução O problema do fazendeiro O problema do jornaleiro Uma Introdução à Otimização sob Incerteza Bernardo Kulnig Pagnoncelli1 e Humberto José Bortolossi2 1 Departamento de Matemática Pontifı́cia Universidade Católica do Rio de Janeiro 2 Departamento de Matemática Aplicada Universidade Federal Fluminense III Bienal da SBM Universidade Federal de Goiânia 6 a 11 de novembro de 2006 Referências Introdução O problema do fazendeiro O problema do jornaleiro 1a aula Referências Introdução O problema do fazendeiro O problema do jornaleiro Sumário 1 Introdução 2 O problema do fazendeiro Introduzindo cenários EVPI e VSS 3 O problema do jornaleiro Enunciado e formulação Solução Exemplo Outras interpretações para o problema 4 Referências Referências Introdução O problema do fazendeiro O problema do jornaleiro Sumário 1 Introdução 2 O problema do fazendeiro Introduzindo cenários EVPI e VSS 3 O problema do jornaleiro Enunciado e formulação Solução Exemplo Outras interpretações para o problema 4 Referências Referências Introdução O problema do fazendeiro O problema do jornaleiro Referências O que é otimizaçã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 área de otimização tem uma longa história de sucesso, tanto no plano teórico quanto nas aplicações. Introdução O problema do fazendeiro O problema do jornaleiro Referências O que é otimizaçã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 área de otimização tem uma longa história de sucesso, tanto no plano teórico quanto nas aplicações. Introdução O problema do fazendeiro O problema do jornaleiro Referências O que é otimizaçã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 área de otimização tem uma longa história de sucesso, tanto no plano teórico quanto nas aplicações. Introdução O problema do fazendeiro O problema do jornaleiro Referências Seleção de portfólio O modelo de Markowitz (1952): minimizar σp2 = sujeito a xT Vx = Rp , T x 1 = 1. xt µ As incertezas µ e V são definidas à priori, usando por exemplo séries históricas dos ativos. É possı́vel incorporá-las ao modelo de alguma forma? Introdução O problema do fazendeiro O problema do jornaleiro Referências Seleção de portfólio O modelo de Markowitz (1952): minimizar σp2 = sujeito a xT Vx = Rp , T x 1 = 1. xt µ As incertezas µ e V são definidas à priori, usando por exemplo séries históricas dos ativos. É possı́vel incorporá-las ao modelo de alguma forma? Introdução O problema do fazendeiro O problema do jornaleiro Referências Seleção de portfólio O modelo de Markowitz (1952): minimizar σp2 = sujeito a xT Vx = Rp , T x 1 = 1. xt µ As incertezas µ e V são definidas à priori, usando por exemplo séries históricas dos ativos. É possı́vel incorporá-las ao modelo de alguma forma? Introdução O problema do fazendeiro O problema do jornaleiro A resposta é dada por otimização estocástica. É uma área voltada para a modelagem e resolução de problemas que envolvem incertezas. Diferentemente de otimização determinı́stica, as incertezas estão explicitamente descritas nos modelos através de variáveis aleatórias. Ao invés de definições formais, vamos começar com uma aplicação de otimização estocástica. Referências Introdução O problema do fazendeiro O problema do jornaleiro A resposta é dada por otimização estocástica. É uma área voltada para a modelagem e resolução de problemas que envolvem incertezas. Diferentemente de otimização determinı́stica, as incertezas estão explicitamente descritas nos modelos através de variáveis aleatórias. Ao invés de definições formais, vamos começar com uma aplicação de otimização estocástica. Referências Introdução O problema do fazendeiro O problema do jornaleiro A resposta é dada por otimização estocástica. É uma área voltada para a modelagem e resolução de problemas que envolvem incertezas. Diferentemente de otimização determinı́stica, as incertezas estão explicitamente descritas nos modelos através de variáveis aleatórias. Ao invés de definições formais, vamos começar com uma aplicação de otimização estocástica. Referências Introdução O problema do fazendeiro O problema do jornaleiro Sumário 1 Introdução 2 O problema do fazendeiro Introduzindo cenários EVPI e VSS 3 O problema do jornaleiro Enunciado e formulação Solução Exemplo Outras interpretações para o problema 4 Referências Referências Introdução O problema do fazendeiro O problema do jornaleiro Referências O problema do fazendeiro João é um fazendeiro especializado em três culturas: trigo, milho e cana-de-açú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. Introdução O problema do fazendeiro O problema do jornaleiro Referências O problema do fazendeiro João é um fazendeiro especializado em três culturas: trigo, milho e cana-de-açú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. Introdução O problema do fazendeiro O problema do jornaleiro Referências O problema do fazendeiro João é um fazendeiro especializado em três culturas: trigo, milho e cana-de-açú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. Introdução O problema do fazendeiro O problema do jornaleiro Referências Duas divisões possı́veis de terra milho trigo cana-de-açúcar cana-de-açúcar trigo milho Introdução O problema do fazendeiro O problema do jornaleiro Referências Restrições O gado precisa de pelo menos 240 T de trigo e 200 T de milho. João pode comprar milho e trigo no mercado local, a preços elevados. Seu excedente também pode vendido para atacadistas. A cana-de-açúcar pode ser vendida por 36 reais por tonelada (R$/T). O governo impõe uma cota em 6000 T. A partir desse valor a cana-de-açúcar é vendida por 10 R$/T. Baseado em experiência pessoal, João sabe que os rendimentos médios de trigo, milho e cana-de-açúcar são 2.5, 3.0 e 20 T/ha respectivamente. Introdução O problema do fazendeiro O problema do jornaleiro Referências Restrições O gado precisa de pelo menos 240 T de trigo e 200 T de milho. João pode comprar milho e trigo no mercado local, a preços elevados. Seu excedente também pode vendido para atacadistas. A cana-de-açúcar pode ser vendida por 36 reais por tonelada (R$/T). O governo impõe uma cota em 6000 T. A partir desse valor a cana-de-açúcar é vendida por 10 R$/T. Baseado em experiência pessoal, João sabe que os rendimentos médios de trigo, milho e cana-de-açúcar são 2.5, 3.0 e 20 T/ha respectivamente. Introdução O problema do fazendeiro O problema do jornaleiro Referências Restrições O gado precisa de pelo menos 240 T de trigo e 200 T de milho. João pode comprar milho e trigo no mercado local, a preços elevados. Seu excedente também pode vendido para atacadistas. A cana-de-açúcar pode ser vendida por 36 reais por tonelada (R$/T). O governo impõe uma cota em 6000 T. A partir desse valor a cana-de-açúcar é vendida por 10 R$/T. Baseado em experiência pessoal, João sabe que os rendimentos médios de trigo, milho e cana-de-açúcar são 2.5, 3.0 e 20 T/ha respectivamente. Introdução O problema do fazendeiro O problema do jornaleiro Referências Restrições O gado precisa de pelo menos 240 T de trigo e 200 T de milho. João pode comprar milho e trigo no mercado local, a preços elevados. Seu excedente também pode vendido para atacadistas. A cana-de-açúcar pode ser vendida por 36 reais por tonelada (R$/T). O governo impõe uma cota em 6000 T. A partir desse valor a cana-de-açúcar é vendida por 10 R$/T. Baseado em experiência pessoal, João sabe que os rendimentos médios de trigo, milho e cana-de-açúcar são 2.5, 3.0 e 20 T/ha respectivamente. Introdução O problema do fazendeiro O problema do jornaleiro Dados para o problema do fazendeiro Rendimento (T/ha) Custo de produção (R$/ha) Preço de venda (R$/T) Trigo 2.5 150 170 Preç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-açúcar 20 260 36(≤ 6000 T) 10(> 6000 T) – – Referências Introdução O problema do fazendeiro O problema do jornaleiro Enunciado O Problema do fazendeiro Encontrar uma divisão de terras que maximize o lucro do fazendeiro sujeito às restrições relativas ao gado, à cota governamental e à dimensão da propriedade. Referências Introdução O problema do fazendeiro O problema do jornaleiro Referências Formulaçã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. Introdução O problema do fazendeiro O problema do jornaleiro Referências Esse é um problema de otimização linear! Podemos escrevê-lo em AMPL, uma linguagem apropriada para otimização e fácil de aprender (http://www.ampl.com/). Existem resolvedores eficientes disponı́veis gratuitamente (http://www.ampl.com/DOWNLOADS/cplex80.html). A solução completa do problema foi obtida através do resolvedor CPLEX. Introdução O problema do fazendeiro O problema do jornaleiro Referências Esse é um problema de otimização linear! Podemos escrevê-lo em AMPL, uma linguagem apropriada para otimização e fácil de aprender (http://www.ampl.com/). Existem resolvedores eficientes disponı́veis gratuitamente (http://www.ampl.com/DOWNLOADS/cplex80.html). A solução completa do problema foi obtida através do resolvedor CPLEX. Introdução O problema do fazendeiro O problema do jornaleiro Referências Esse é um problema de otimização linear! Podemos escrevê-lo em AMPL, uma linguagem apropriada para otimização e fácil de aprender (http://www.ampl.com/). Existem resolvedores eficientes disponı́veis gratuitamente (http://www.ampl.com/DOWNLOADS/cplex80.html). A solução completa do problema foi obtida através do resolvedor CPLEX. Introdução O problema do fazendeiro O problema do jornaleiro Solução do problema Trigo Área (ha) 120 Total produzido 300 Total vendido 100 Total comprado – Lucro total: R$118 600 Milho 80 240 – – Cana-de-açúcar 300 6000 6000 – Referências Introdução O problema do fazendeiro O problema do jornaleiro Referências Introduzindo cenários Pronto, o problema está resolvido! Mas... João não tem tanta certeza sobre os valores dos rendimentos médios, afinal mudanças climáticas podem alterar bastante suas estimativas e, conseqüentemente, seus lucros. Introdução O problema do fazendeiro O problema do jornaleiro Referências Introduzindo cenários Pronto, o problema está resolvido! Mas... João não tem tanta certeza sobre os valores dos rendimentos médios, afinal mudanças climáticas podem alterar bastante suas estimativas e, conseqüentemente, seus lucros. Introdução O problema do fazendeiro O problema do jornaleiro Referências Introduzindo cenários Pronto, o problema está resolvido! Mas... João não tem tanta certeza sobre os valores dos rendimentos médios, afinal mudanças climáticas podem alterar bastante suas estimativas e, conseqüentemente, seus lucros. Introdução O problema do fazendeiro O problema do jornaleiro Referências Solução ótima com rendimentos 20% acima da média. Suponha que num ano particularmente favorável, os rendimentos das culturas foram 20% acima da média. Qual é a solução do problema neste caso? Trigo 183.33 Área (ha) Total produzido 550 Total vendido 350 Total comprado Lucro total: R$167 600 Milho 66.67 240 - Cana-de-açúcar 250 6000 6000 - Introdução O problema do fazendeiro O problema do jornaleiro Referências Solução ótima com rendimentos 20% acima da média. Suponha que num ano particularmente favorável, os rendimentos das culturas foram 20% acima da média. Qual é a solução do problema neste caso? Trigo 183.33 Área (ha) Total produzido 550 Total vendido 350 Total comprado Lucro total: R$167 600 Milho 66.67 240 - Cana-de-açúcar 250 6000 6000 - Introdução O problema do fazendeiro O problema do jornaleiro Referências Solução ótima com rendimentos 20% acima da média. Em um ano particularmente desfavorável, os rendimentos das culturas foram 20% abaixo da média. Qual é a a solução do problema neste caso? Trigo 100 Área (ha) Total produzido 200 Total vendido Total comprado Lucro total: R$59 950 Milho 25 60 180 Cana-de-açúcar 375 6000 6000 - Introdução O problema do fazendeiro O problema do jornaleiro Referências Solução ótima com rendimentos 20% acima da média. Em um ano particularmente desfavorável, os rendimentos das culturas foram 20% abaixo da média. Qual é a a solução do problema neste caso? Trigo 100 Área (ha) Total produzido 200 Total vendido Total comprado Lucro total: R$59 950 Milho 25 60 180 Cana-de-açúcar 375 6000 6000 - Introdução O problema do fazendeiro O problema do jornaleiro Referências Sensibilidade da solução Mudanças de 20% nos rendimentos das culturas em relação ao rendimento médio fazem o seu lucro variar de R$59 950 a R$167 667! Pensando na cana-de-açúcar, João tem o seguinte dilema: se a área reservada para a cana-de-açúcar for muito grande e os rendimentos forem acima da média, então ele terá que vender parte da produção a um preço desfavorável. Por outro lado, se ele reservar uma área muito pequena e os rendimentos foram abaixo da média, então ele terá perdido a oportunidade de vender cana-de-açúcar a um preço favorável. Como encontrar uma solução que seja satisfatória para todos os cenários? Introdução O problema do fazendeiro O problema do jornaleiro Referências Sensibilidade da solução Mudanças de 20% nos rendimentos das culturas em relação ao rendimento médio fazem o seu lucro variar de R$59 950 a R$167 667! Pensando na cana-de-açúcar, João tem o seguinte dilema: se a área reservada para a cana-de-açúcar for muito grande e os rendimentos forem acima da média, então ele terá que vender parte da produção a um preço desfavorável. Por outro lado, se ele reservar uma área muito pequena e os rendimentos foram abaixo da média, então ele terá perdido a oportunidade de vender cana-de-açúcar a um preço favorável. Como encontrar uma solução que seja satisfatória para todos os cenários? Introdução O problema do fazendeiro O problema do jornaleiro Referências Sensibilidade da solução Mudanças de 20% nos rendimentos das culturas em relação ao rendimento médio fazem o seu lucro variar de R$59 950 a R$167 667! Pensando na cana-de-açúcar, João tem o seguinte dilema: se a área reservada para a cana-de-açúcar for muito grande e os rendimentos forem acima da média, então ele terá que vender parte da produção a um preço desfavorável. Por outro lado, se ele reservar uma área muito pequena e os rendimentos foram abaixo da média, então ele terá perdido a oportunidade de vender cana-de-açúcar a um preço favorável. Como encontrar uma solução que seja satisfatória para todos os cenários? Introdução O problema do fazendeiro O problema do jornaleiro Referências Sensibilidade da solução Mudanças de 20% nos rendimentos das culturas em relação ao rendimento médio fazem o seu lucro variar de R$59 950 a R$167 667! Pensando na cana-de-açúcar, João tem o seguinte dilema: se a área reservada para a cana-de-açúcar for muito grande e os rendimentos forem acima da média, então ele terá que vender parte da produção a um preço desfavorável. Por outro lado, se ele reservar uma área muito pequena e os rendimentos foram abaixo da média, então ele terá perdido a oportunidade de vender cana-de-açúcar a um preço favorável. Como encontrar uma solução que seja satisfatória para todos os cenários? Introdução O problema do fazendeiro O problema do jornaleiro Forma extensa de um problema estocá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 Referências Introdução O problema do fazendeiro O problema do jornaleiro Restriçõ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 Referências Introdução O problema do fazendeiro O problema do jornaleiro Referências As variáveis xi são ditas de primeiro estágio: seu valor deve ser determinado antes que se conheça a condição climática. As variáveis yis e wis são de segundo estágio: elas são escolhidas após a definição dos valores de xi e do conhecimento do clima. Elas corrigem possı́veis déficits na alimentação do gado gerados pelas escolhas xi de primeiro estágio. O problema estocástico na forma extensa é linear e pode ser resolvido da mesma forma que fizemos para a formulação inicial. Introdução O problema do fazendeiro O problema do jornaleiro Referências As variáveis xi são ditas de primeiro estágio: seu valor deve ser determinado antes que se conheça a condição climática. As variáveis yis e wis são de segundo estágio: elas são escolhidas após a definição dos valores de xi e do conhecimento do clima. Elas corrigem possı́veis déficits na alimentação do gado gerados pelas escolhas xi de primeiro estágio. O problema estocástico na forma extensa é linear e pode ser resolvido da mesma forma que fizemos para a formulação inicial. Introdução O problema do fazendeiro O problema do jornaleiro Referências As variáveis xi são ditas de primeiro estágio: seu valor deve ser determinado antes que se conheça a condição climática. As variáveis yis e wis são de segundo estágio: elas são escolhidas após a definição dos valores de xi e do conhecimento do clima. Elas corrigem possı́veis déficits na alimentação do gado gerados pelas escolhas xi de primeiro estágio. O problema estocástico na forma extensa é linear e pode ser resolvido da mesma forma que fizemos para a formulação inicial. Introdução O problema do fazendeiro O problema do jornaleiro Referências Solução estocástica estágio s=1 (Acima) Área (ha) Rendimento (T) Venda (T) Trigo 170 510 310 s=2 (Mé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) Lucro total: R$108 390 Milho 80 288 48 Cana-de-açúcar 250 6000 6000 (preço favorável) – 5000 5000 (preço favorável) – 4000 4000 (preço favorável) – Introdução O problema do fazendeiro O problema do jornaleiro Referências Análise da solução A solução ótima do problema estocástico não é igual a nenhuma das soluções encontradas anteriormente: (x1 , x2 , x3 ) = (170, 80, 250). No caso em que os rendimentos são 20% abaixo da média, temos a necessidade de se comprar milho no mercado devido a baixa produtividade. Queremos agora estudar a qualidade da solução estocástica, isto é, queremos mensurar o ganho em se considerar as variações climáticas bem como o quanto se deixa de ganhar por não se conhecer com exatidão o futuro. Introdução O problema do fazendeiro O problema do jornaleiro Referências Análise da solução A solução ótima do problema estocástico não é igual a nenhuma das soluções encontradas anteriormente: (x1 , x2 , x3 ) = (170, 80, 250). No caso em que os rendimentos são 20% abaixo da média, temos a necessidade de se comprar milho no mercado devido a baixa produtividade. Queremos agora estudar a qualidade da solução estocástica, isto é, queremos mensurar o ganho em se considerar as variações climáticas bem como o quanto se deixa de ganhar por não se conhecer com exatidão o futuro. Introdução O problema do fazendeiro O problema do jornaleiro Referências Análise da solução A solução ótima do problema estocástico não é igual a nenhuma das soluções encontradas anteriormente: (x1 , x2 , x3 ) = (170, 80, 250). No caso em que os rendimentos são 20% abaixo da média, temos a necessidade de se comprar milho no mercado devido a baixa produtividade. Queremos agora estudar a qualidade da solução estocástica, isto é, queremos mensurar o ganho em se considerar as variações climáticas bem como o quanto se deixa de ganhar por não se conhecer com exatidão o futuro. Introdução O problema do fazendeiro O problema do jornaleiro Referências EVPI e VSS Valor esperado de informação perfeita (EVPI) O EVPI mede o quanto perdemos por não saber com exatidão o futuro. Para calculá-lo temos que fazer a média entre os rendimentos obtidos conhecendo-se cada um dos cenários climáticos e subtrair esse valor do ganho com a solução estocástica. Temos EVPI = RP − WS = R$ 59 950 + R$ 167 667 + R$ 118 600 = R$ 7 016. − 108 390 + 3 Introdução O problema do fazendeiro O problema do jornaleiro Referências EVPI e VSS Valor esperado de informação perfeita (EVPI) O EVPI mede o quanto perdemos por não saber com exatidão o futuro. Para calculá-lo temos que fazer a média entre os rendimentos obtidos conhecendo-se cada um dos cenários climáticos e subtrair esse valor do ganho com a solução estocástica. Temos EVPI = RP − WS = R$ 59 950 + R$ 167 667 + R$ 118 600 = R$ 7 016. − 108 390 + 3 Introdução O problema do fazendeiro O problema do jornaleiro Referências EVPI e VSS Valor esperado de informação perfeita (EVPI) O EVPI mede o quanto perdemos por não saber com exatidão o futuro. Para calculá-lo temos que fazer a média entre os rendimentos obtidos conhecendo-se cada um dos cenários climáticos e subtrair esse valor do ganho com a solução estocástica. Temos EVPI = RP − WS = R$ 59 950 + R$ 167 667 + R$ 118 600 = R$ 7 016. − 108 390 + 3 Introdução O problema do fazendeiro O problema do jornaleiro Referências Valor da solução estocástica (VSS) O VSS mede o ganho em se considerar o modelo estocástico ao invés de assumir rendimentos médios. Para calculá-lo, pense que João é um fazendeiro teimoso: ele divide suas terras supondo que os rendimentos são os médios. Resolve-se o problema inicial para cada cenário, fixando (x1 , x2 , x3 ) = (120, 80, 300). Dessa forma o VSS é dado por VSS = EEV − RP R$ 55 120 + R$ 118 600 + R$ 148 000 − + R$108 390 = R$ 1 150. 3 Introdução O problema do fazendeiro O problema do jornaleiro Referências Valor da solução estocástica (VSS) O VSS mede o ganho em se considerar o modelo estocástico ao invés de assumir rendimentos médios. Para calculá-lo, pense que João é um fazendeiro teimoso: ele divide suas terras supondo que os rendimentos são os médios. Resolve-se o problema inicial para cada cenário, fixando (x1 , x2 , x3 ) = (120, 80, 300). Dessa forma o VSS é dado por VSS = EEV − RP R$ 55 120 + R$ 118 600 + R$ 148 000 − + R$108 390 = R$ 1 150. 3 Introdução O problema do fazendeiro O problema do jornaleiro Referências Valor da solução estocástica (VSS) O VSS mede o ganho em se considerar o modelo estocástico ao invés de assumir rendimentos médios. Para calculá-lo, pense que João é um fazendeiro teimoso: ele divide suas terras supondo que os rendimentos são os médios. Resolve-se o problema inicial para cada cenário, fixando (x1 , x2 , x3 ) = (120, 80, 300). Dessa forma o VSS é dado por VSS = EEV − RP R$ 55 120 + R$ 118 600 + R$ 148 000 − + R$108 390 = R$ 1 150. 3 Introdução O problema do fazendeiro O problema do jornaleiro Sumário 1 Introdução 2 O problema do fazendeiro Introduzindo cenários EVPI e VSS 3 O problema do jornaleiro Enunciado e formulação Solução Exemplo Outras interpretações para o problema 4 Referências Referências Introdução O problema do fazendeiro O problema do jornaleiro Referências Enunciado e formulação O problema do jornaleiro João tem um irmão na cidade chamado José, que é jornaleiro. Toda manhã ele vai ao editor do jornal e tem que decidir quantos jornais comprar sem saber a demanda daquele dia. Seu poder de compra é limitado, ou seja, ele pode comprar até uma quantidade fixa u. Além disso, os jornais não vendidos podem ser devolvidos ao editor, a um preço menor do que o valor pago no inı́cio do dia. Introdução O problema do fazendeiro O problema do jornaleiro Referências Enunciado e formulação O problema do jornaleiro João tem um irmão na cidade chamado José, que é jornaleiro. Toda manhã ele vai ao editor do jornal e tem que decidir quantos jornais comprar sem saber a demanda daquele dia. Seu poder de compra é limitado, ou seja, ele pode comprar até uma quantidade fixa u. Além disso, os jornais não vendidos podem ser devolvidos ao editor, a um preço menor do que o valor pago no inı́cio do dia. Introdução O problema do fazendeiro O problema do jornaleiro Referências Enunciado e formulação O problema do jornaleiro João tem um irmão na cidade chamado José, que é jornaleiro. Toda manhã ele vai ao editor do jornal e tem que decidir quantos jornais comprar sem saber a demanda daquele dia. Seu poder de compra é limitado, ou seja, ele pode comprar até uma quantidade fixa u. Além disso, os jornais não vendidos podem ser devolvidos ao editor, a um preço menor do que o valor pago no inı́cio do dia. Introdução O problema do fazendeiro O problema do jornaleiro Formulaçã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. Referências Introdução O problema do fazendeiro O problema do jornaleiro Referências Assim como no problema do fazendeiro, o problema do jornaleiro é estruturado em dois estágios: no primeiro estágio José decide quantos jornais vai comprar através da variável x. As variáveis de segundo estágio representam quanto ele conseguiu vender (y (ξ)) e quanto ele devolveu ao editor (w (ξ)). José procura a quantidade ótima de jornais a comprar de forma a maximizar seu lucro esperado sob incerteza de demanda. Introdução O problema do fazendeiro O problema do jornaleiro Referências Assim como no problema do fazendeiro, o problema do jornaleiro é estruturado em dois estágios: no primeiro estágio José decide quantos jornais vai comprar através da variável x. As variáveis de segundo estágio representam quanto ele conseguiu vender (y (ξ)) e quanto ele devolveu ao editor (w (ξ)). José procura a quantidade ótima de jornais a comprar de forma a maximizar seu lucro esperado sob incerteza de demanda. Introdução O problema do fazendeiro O problema do jornaleiro Referências Assim como no problema do fazendeiro, o problema do jornaleiro é estruturado em dois estágios: no primeiro estágio José decide quantos jornais vai comprar através da variável x. As variáveis de segundo estágio representam quanto ele conseguiu vender (y (ξ)) e quanto ele devolveu ao editor (w (ξ)). José procura a quantidade ótima de jornais a comprar de forma a maximizar seu lucro esperado sob incerteza de demanda. Introdução O problema do fazendeiro O problema do jornaleiro Referências Solução O primeiro passo para encontrar uma solução explı́cita do problema do jornaleiro é resolver o problema de segundo estágio. A solução é imediata: y ∗ (ξ) = min{ξ, x} e w ∗ (ξ) = max{x − ξ, 0}. Com isso temos Q(x) = Eξ [−q min{ξ, x} − r max{x − ξ, 0}]. Introdução O problema do fazendeiro O problema do jornaleiro Referências Solução O primeiro passo para encontrar uma solução explı́cita do problema do jornaleiro é resolver o problema de segundo estágio. A solução é imediata: y ∗ (ξ) = min{ξ, x} e w ∗ (ξ) = max{x − ξ, 0}. Com isso temos Q(x) = Eξ [−q min{ξ, x} − r max{x − ξ, 0}]. Introdução O problema do fazendeiro O problema do jornaleiro Referências Solução O primeiro passo para encontrar uma solução explı́cita do problema do jornaleiro é resolver o problema de segundo estágio. A solução é imediata: y ∗ (ξ) = min{ξ, x} e w ∗ (ξ) = max{x − ξ, 0}. Com isso temos Q(x) = Eξ [−q min{ξ, x} − r max{x − ξ, 0}]. Introdução O problema do fazendeiro O problema do jornaleiro Referências Vamos aprender mais à frente que a função Q é convexa, contı́nua e, se ξ é v.a. contı́nua, derivável. Como estamos no intervalo [0, u], se cx + Q′ (0) > 0, então a derivada não troca de sinal no intervalo e solução ótima é x ∗ = 0. Se cx + Q′ (u) < 0, então a solução ótima é x ∗ = u. Vamos procurar por soluções de cx + Q′ (x) = 0. Introdução O problema do fazendeiro O problema do jornaleiro Referências Vamos aprender mais à frente que a função Q é convexa, contı́nua e, se ξ é v.a. contı́nua, derivável. Como estamos no intervalo [0, u], se cx + Q′ (0) > 0, então a derivada não troca de sinal no intervalo e solução ótima é x ∗ = 0. Se cx + Q′ (u) < 0, então a solução ótima é x ∗ = u. Vamos procurar por soluções de cx + Q′ (x) = 0. Introdução O problema do fazendeiro O problema do jornaleiro Referências Vamos aprender mais à frente que a função Q é convexa, contı́nua e, se ξ é v.a. contı́nua, derivável. Como estamos no intervalo [0, u], se cx + Q′ (0) > 0, então a derivada não troca de sinal no intervalo e solução ótima é x ∗ = 0. Se cx + Q′ (u) < 0, então a solução ótima é x ∗ = u. Vamos procurar por soluções de cx + Q′ (x) = 0. Introdução O problema do fazendeiro O problema do jornaleiro Referências Vamos aprender mais à frente que a função Q é convexa, contı́nua e, se ξ é v.a. contı́nua, derivável. Como estamos no intervalo [0, u], se cx + Q′ (0) > 0, então a derivada não troca de sinal no intervalo e solução ótima é x ∗ = 0. Se cx + Q′ (u) < 0, então a solução ótima é x ∗ = u. Vamos procurar por soluções de cx + Q′ (x) = 0. Introdução O problema do fazendeiro O problema do jornaleiro A expressão para Q é 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 integração por partes obtém-se Z x Q(x) = −qx + (q − r ) F (t)dt. −∞ Referências Introdução O problema do fazendeiro O problema do jornaleiro A expressão para Q é 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 integração por partes obtém-se Z x Q(x) = −qx + (q − r ) F (t)dt. −∞ Referências Introdução O problema do fazendeiro O problema do jornaleiro A expressão para Q é 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 integração por partes obtém-se Z x Q(x) = −qx + (q − r ) F (t)dt. −∞ Referências Introdução O problema do fazendeiro O problema do jornaleiro Referências Derivando, chegamos a Q′ (x) = −q + (q − r )F (x). Finalmente, a solução do problema é ∗ se q−c q−r < F (0), x = 0, q−c ∗ x = u, se q−r > F (u), x ∗ = F −1 q−c , caso contrário. q−r Qualquer modelagem razoável da demanda ξ admite que ela só assume valores positivos, e portanto não temos x ∗ = 0. Introdução O problema do fazendeiro O problema do jornaleiro Referências Derivando, chegamos a Q′ (x) = −q + (q − r )F (x). Finalmente, a solução do problema é ∗ se q−c q−r < F (0), x = 0, q−c ∗ x = u, se q−r > F (u), x ∗ = F −1 q−c , caso contrário. q−r Qualquer modelagem razoável da demanda ξ admite que ela só assume valores positivos, e portanto não temos x ∗ = 0. Introdução O problema do fazendeiro O problema do jornaleiro Referências Derivando, chegamos a Q′ (x) = −q + (q − r )F (x). Finalmente, a solução do problema é ∗ se q−c q−r < F (0), x = 0, q−c ∗ x = u, se q−r > F (u), x ∗ = F −1 q−c , caso contrário. q−r Qualquer modelagem razoável da demanda ξ admite que ela só assume valores positivos, e portanto não temos x ∗ = 0. Introdução O problema do fazendeiro O problema do jornaleiro Referências Exemplo Um exemplo numérico Suponha que o custo do jornal para o jornaleiro seja c = 10, que o preço de venda seja q = 25, que o preço de devolução seja r = 5 e que o poder de compra é u = 150. A demanda ξ é uma variável aleatória uniforme no intervalo [50, 150]. A solução é x ∗ = F −1 (3/4) = 125. Introdução O problema do fazendeiro O problema do jornaleiro Referências Exemplo Um exemplo numérico Suponha que o custo do jornal para o jornaleiro seja c = 10, que o preço de venda seja q = 25, que o preço de devolução seja r = 5 e que o poder de compra é u = 150. A demanda ξ é uma variável aleatória uniforme no intervalo [50, 150]. A solução é x ∗ = F −1 (3/4) = 125. Introdução O problema do fazendeiro O problema do jornaleiro Referências Exemplo Um exemplo numérico Suponha que o custo do jornal para o jornaleiro seja c = 10, que o preço de venda seja q = 25, que o preço de devolução seja r = 5 e que o poder de compra é u = 150. A demanda ξ é uma variável aleatória uniforme no intervalo [50, 150]. A solução é x ∗ = F −1 (3/4) = 125. Introdução O problema do fazendeiro O problema do jornaleiro Referências VSS Inicialmente precisamos calcular a solução ótima para ξ = 100. A solução é trivial: se a demanda é 100, então compre x ∗ = 100 jornais! Precisamos calcular o EEV, que é 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 Introdução O problema do fazendeiro O problema do jornaleiro Referências VSS Inicialmente precisamos calcular a solução ótima para ξ = 100. A solução é trivial: se a demanda é 100, então compre x ∗ = 100 jornais! Precisamos calcular o EEV, que é 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 Introdução O problema do fazendeiro O problema do jornaleiro Referências VSS Inicialmente precisamos calcular a solução ótima para ξ = 100. A solução é trivial: se a demanda é 100, então compre x ∗ = 100 jornais! Precisamos calcular o EEV, que é 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 Introdução O problema do fazendeiro O problema do jornaleiro EVPI Se conhecemos o valor da demanda ξ, então a solução é x ∗ = ξ. Assim, temos que WS = Eξ [cξ + −qξ] = −15Eξ (ξ) = −1500. Logo, EVPI = 1500 − 1312.5 = 187.5. Referências Introdução O problema do fazendeiro O problema do jornaleiro EVPI Se conhecemos o valor da demanda ξ, então a solução é x ∗ = ξ. Assim, temos que WS = Eξ [cξ + −qξ] = −15Eξ (ξ) = −1500. Logo, EVPI = 1500 − 1312.5 = 187.5. Referências Introdução O problema do fazendeiro O problema do jornaleiro EVPI Se conhecemos o valor da demanda ξ, então a solução é x ∗ = ξ. Assim, temos que WS = Eξ [cξ + −qξ] = −15Eξ (ξ) = −1500. Logo, EVPI = 1500 − 1312.5 = 187.5. Referências Introdução O problema do fazendeiro O problema do jornaleiro Outras interpretações para o problema Custo marginal Vamos usar o conceito de ganho marginal para derivar a solução do problema por uma outra trilha. A expressã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 é o lucro esperado na venda do k-ésimo jornal? A resposta é lucro esperado = P(ξ < k)(r − c) + P(ξ ≥ k)(q − c). Referências Introdução O problema do fazendeiro O problema do jornaleiro Outras interpretações para o problema Custo marginal Vamos usar o conceito de ganho marginal para derivar a solução do problema por uma outra trilha. A expressã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 é o lucro esperado na venda do k-ésimo jornal? A resposta é lucro esperado = P(ξ < k)(r − c) + P(ξ ≥ k)(q − c). Referências Introdução O problema do fazendeiro O problema do jornaleiro Outras interpretações para o problema Custo marginal Vamos usar o conceito de ganho marginal para derivar a solução do problema por uma outra trilha. A expressã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 é o lucro esperado na venda do k-ésimo jornal? A resposta é lucro esperado = P(ξ < k)(r − c) + P(ξ ≥ k)(q − c). Referências Introdução O problema do fazendeiro O problema do jornaleiro Outras interpretações para o problema Custo marginal Vamos usar o conceito de ganho marginal para derivar a solução do problema por uma outra trilha. A expressã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 é o lucro esperado na venda do k-ésimo jornal? A resposta é lucro esperado = P(ξ < k)(r − c) + P(ξ ≥ k)(q − c). Referências Introdução O problema do fazendeiro O problema do jornaleiro Referências Se o lucro esperado for negativo temos jornais encalhados e se o lucro for positivo temos excesso de demanda. A situação ideal ocorre quando esse lucro é 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 então comprar k = F −1 q−c q−r jornais. Introdução O problema do fazendeiro O problema do jornaleiro Referências Se o lucro esperado for negativo temos jornais encalhados e se o lucro for positivo temos excesso de demanda. A situação ideal ocorre quando esse lucro é 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 então comprar k = F −1 q−c q−r jornais. Introdução O problema do fazendeiro O problema do jornaleiro Referências Se o lucro esperado for negativo temos jornais encalhados e se o lucro for positivo temos excesso de demanda. A situação ideal ocorre quando esse lucro é 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 então comprar k = F −1 q−c q−r jornais. Introdução O problema do fazendeiro O problema do jornaleiro Referências Estoque zerado A probabilidade de se vender todos os jornais é 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 entã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 razão custo/preço unitário. Introdução O problema do fazendeiro O problema do jornaleiro Referências Estoque zerado A probabilidade de se vender todos os jornais é 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 entã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 razão custo/preço unitário. Introdução O problema do fazendeiro O problema do jornaleiro Referências Estoque zerado A probabilidade de se vender todos os jornais é 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 entã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 razão custo/preço unitário. Introdução O problema do fazendeiro O problema do jornaleiro Sumário 1 Introdução 2 O problema do fazendeiro Introduzindo cenários EVPI e VSS 3 O problema do jornaleiro Enunciado e formulação Solução Exemplo Outras interpretações para o problema 4 Referências Referências Introdução O problema do fazendeiro O problema do jornaleiro Internet Página do curso de otimização estocástica lecionado na PUC-Rio em 2006.1: http://www.mat.pucrio.br/∼hjbortol/disciplinas/2006.1/soe/ Página da comunidade de otimização estocástica: http://www.stoprog.org Banco de artigos de otimização estocástica: http://edoc.hu-berlin.de/browsing/speps/ Referências Introdução O problema do fazendeiro O problema do jornaleiro Internet Página do curso de otimização estocástica lecionado na PUC-Rio em 2006.1: http://www.mat.pucrio.br/∼hjbortol/disciplinas/2006.1/soe/ Página da comunidade de otimização estocástica: http://www.stoprog.org Banco de artigos de otimização estocástica: http://edoc.hu-berlin.de/browsing/speps/ Referências Introdução O problema do fazendeiro O problema do jornaleiro Internet Página do curso de otimização estocástica lecionado na PUC-Rio em 2006.1: http://www.mat.pucrio.br/∼hjbortol/disciplinas/2006.1/soe/ Página da comunidade de otimização estocástica: http://www.stoprog.org Banco de artigos de otimização estocástica: http://edoc.hu-berlin.de/browsing/speps/ Referências