Slide Programação Dinâmica Estocástica -2020 1

22 Programação Dinâmica Estocástica © 2020 Prof. Sérgio F. Mayerle 22 Programação Dinâmica Estocástica EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 2 of 15  Caracterização e Terminologia  Modelo 07: Plano de Estoque da Concessionária 22 Programação Dinâmica Estocástica EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 3 of 15 Caracterização e Terminologia Na Programação Dinâmica Estocástica a transição entre estados não depende somente do processo de tomada de decisão. Após a escolha de uma ação, em um determinado estágio/estado, a “natureza” toma controle do processo definindo o estado para o qual o sistema evolui. Embora não se tenha controle desta trajetória, é conhecida a distribuição de probabilidade com que as transições ocorrem. Em outras palavras: seja a probabilidade  , , ,  p n i j k de ocorrer a transição do estado   ,n i para o estado  n 1,  j  , dado uma ação , n i k  K , e que associado a esta ação tem- se um retorno esperado  , ,  r n i k , como mostra o esquema a seguir: Assim, o valor esperado do estado   ,n i , denotado por  ,  f n i , é calculado para o caso de maximização da função de retornos, pela expressão:         , 1 ( , ) , , , , , 1, 1 n i N k K j f n i Max r n i k p n i j k f n j              , ,  r n i k  f n 1,  j  k  ,  f n i  , , ,  p n i j k 22 Programação Dinâmica Estocástica EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 4 of 15 Modelo 07: Plano de Estoque da Concessionária No início de cada semestre a concessionária da Lamborghini em São Paulo, que revende a Lamborghini Aventador (LP700-4), faz seu pedido à fábrica localizada na pacata Sant'Agata Bolognese (Italia). A fábrica garante a entrega de pedidos semestrais com até 3 unidades, num prazo de 180 dias, incluindo as operações alfandegárias. O preço por unidade pago à fábrica no ato do pedido é de R$ 1.650.000; na chegada do pedido, a concessionária paga ao despachante R$ 70.000 por custos alfandegários; e para manter o estoque sem riscos, a concessionária faz um seguro de R$ 40.000 por semestre/unidade. O preço final para o consumidor é de R$ 2.200.000. A taxa de mínima atratividade efetiva da concessionária é de 2% ao semestre. A demanda segue uma distribuição de Poisson com média  1,3 unidades por semestre, e quando não atendida no ato, é perdida para concessionárias de marcas rivais. Pede-se:  Formule o modelo de programação dinâmica para este problema;  Determine a estratégia ótima a ser adotada pela concessionária;  Por quanto você venderia a concessionária ?  Determine o lucro esperado por semestre na operação da concessionária com a venda deste modelo.  Sabendo que você tem 10 carros em estoque no início do semestre, neste momento você venderia um dos carros para um cliente que oferecesse pagar no máximo R$ 1.500.000 ?  E você aceitaria R$ 1.800.000 se tivesse apenas um veículo no estoque ? 22 Programação Dinâmica Estocástica EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 5 of 15 Observação  A distribuição de Poisson é caracterizada pela seguinte expressão: ( ) ! k e P N k k     onde N é a variável aleatória com distribuição de Poisson; k é o valor observado para a variável N ;  é o valor médio da variável aleatória N , e ( ) P N  k probabilidade de se observar o valor k para a variável aleatória N . Concessionária da Lamborghini LP 700-4 Sistema Estoque de automóveis da concessionária Estágio Número de anos que restam até o fim da vida útil da concessionária:  n 0,1,2,3,...,   Estado Número de automóveis em estoque no início do semestre:   0,1,..., i N  Ação Número de veículos pedidos à fábrica:  k  0,1,2,3 Retorno Ganho esperado no semestre: a) pagamento dos veículos pedidos; b) custo do seguro para os veículos em estoque no semestre; c) pagamento feito ao despachante na entrega do pedido; d) receita proveniente da venda dos automóveis. Calcula-se o retorno esperado como: 22 Programação Dinâmica Estocástica EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 6 of 15 1 ( ) 0 1 2 ( , ) 1 ( ) 0 1 1 2 se se seg desp compra seg RE i i C k r i k C RE i k P i C k                     onde ( ) RE i é a receita esperada do mês, calculada em função do número de veículos disponíveis em estoque no início do período. Calcula-se ( ) RE i como segue: 0 0 ( ) ( | ) ( | ) i venda venda v v RE i P v p v i P v p v i        onde ( | ) p v i é a probabilidade de vender v unidades dado que existe i unidades em estoque, calculado por: 1 0 0 ( | ) ! 1 ! se se se v d i d v i e p v i v i v e v i d                        Valor do Estado Valor da concessionária considerando o estoque existente. (0, ) 0 f i i   22 Programação Dinâmica Estocástica EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 7 of 15 Função de Recorrência Determina o valor do estado atual com base na função de retorno e nos valores dos estados do próximo estágio. É calculado como segue: 0 1 ( , ) max ( , ) ( , , ) ( 1, ) 1 i N k K j f n i r i k p i k j f n j               onde   (0, ) 0, 0,1,..., f i i N    Função Probabilidade de Transição 1 0 ( ) 1 ! ! ( , , ) ( )! 0 se se em caso contrário d d i d i d i k j e e j k d d e p i k j k j i k i k j                                    Conjunto de Ações Viáveis   | 0 min(3; ) Ki k Z k N i       22 Programação Dinâmica Estocástica EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 8 of 15 Resultado Iteração = 1 -------------------------------------------------------------------- i k f(n,i) f(n-1,i) Diferença ValorAuto -------------------------------------------------------------------- 0 0 0.00 0.00 0.00 1 0 1544584.21 0.00 1544584.21 1544584.21 2 0 2317444.74 0.00 2317444.74 772860.52 3 0 2588684.86 0.00 2588684.86 271240.12 4 0 2642556.14 0.00 2642556.14 53871.28 5 0 2625782.55 0.00 2625782.55 -16773.59 6 0 2590641.29 0.00 2590641.29 -35141.26 7 0 2551520.38 0.00 2551520.38 -39120.92 8 0 2511660.38 0.00 2511660.38 -39860.00 9 0 2471680.28 0.00 2471680.28 -39980.10 10 0 2431682.83 0.00 2431682.83 -39997.45 Iteração = 2 -------------------------------------------------------------------- i k f(n,i) f(n-1,i) Diferença ValorAuto -------------------------------------------------------------------- 0 0 0.00 0.00 0.00 1 0 1957278.63 1544584.21 412694.42 1957278.63 2 0 3473140.98 2317444.74 1155696.24 1515862.35 3 0 4434028.80 2588684.86 1845343.94 960887.83 4 0 4922114.26 2642556.14 2279558.12 488085.46 5 0 5105535.23 2625782.55 2479752.68 183420.97 6 0 5131221.50 2590641.29 2540580.21 25686.27 7 0 5088705.75 2551520.38 2537185.38 -42515.75 8 0 5020885.62 2511660.38 2509225.24 -67820.13 9 0 4944846.08 2471680.28 2473165.80 -76039.54 10 0 4866432.70 2431682.83 2434749.87 -78413.38 22 Programação Dinâmica Estocástica EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 9 of 15 Iteração = 3 -------------------------------------------------------------------- i k f(n,i) f(n-1,i) Diferença ValorAuto -------------------------------------------------------------------- 0 1 200273.17 0.00 200273.17 1 1 2149877.66 1957278.63 192599.03 1949604.49 2 0 3925276.29 3473140.98 452135.32 1775398.64 3 0 5421682.91 4434028.80 987654.11 1496406.62 4 0 6473457.01 4922114.26 1551342.75 1051774.10 5 0 7102707.97 5105535.23 1997172.74 629250.96 6 0 7406725.88 5131221.50 2275504.37 304017.91 7 0 7500921.43 5088705.75 2412215.67 94195.55 8 0 7478746.89 5020885.62 2457861.27 -22174.53 9 0 7400005.46 4944846.08 2455159.38 -78741.43 10 0 7296797.64 4866432.70 2430364.94 -103207.82 Iteração = 7 -------------------------------------------------------------------- i k f(n,i) f(n-1,i) Diferença ValorAuto -------------------------------------------------------------------- 0 3 1410436.80 1100308.11 310128.70 1 2 3404353.34 3079659.21 324694.13 1993916.54 2 2 5210435.29 4874161.62 336273.66 1806081.94 3 0 6883266.38 6557645.54 325620.85 1672831.10 4 0 8569161.38 8236136.29 333025.10 1685895.00 5 0 10167171.58 9782539.60 384631.98 1598010.20 6 0 11648001.75 11136458.24 511543.51 1480830.16 7 0 12958403.05 12236744.35 721658.70 1310401.30 8 0 14046418.50 13051018.96 995399.54 1088015.46 9 0 14879598.73 13585039.01 1294559.72 833180.23 10 0 15453820.82 13875952.90 1577867.91 574222.08 22 Programação Dinâmica Estocástica EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 10 of 15 Iteração = 30 -------------------------------------------------------------------- i k f(n,i) f(n-1,i) Diferença ValorAuto -------------------------------------------------------------------- 0 2 7456732.71 7247328.32 209404.40 1 2 9447591.03 9238186.64 209404.40 1990858.32 2 2 11251271.77 11041867.37 209404.40 1803680.73 3 0 12921534.10 12712129.70 209404.40 1670262.34 4 0 14608225.93 14398821.53 209404.40 1686691.83 5 0 16226590.74 16017186.34 209404.40 1618364.81 6 0 17789092.18 17579687.78 209404.40 1562501.44 7 0 19297792.39 19088387.99 209404.40 1508700.21 8 0 20753303.62 20543899.22 209404.40 1455511.23 9 0 22156362.54 21946958.14 209404.40 1403058.92 10 0 23507758.32 23298353.93 209404.40 1351395.79 Iteração = 1000 -------------------------------------------------------------------- i k f(n,i) f(n-1,i) Diferença ValorAuto -------------------------------------------------------------------- 0 2 17926952.50 17926952.50 0.00 1 2 19917810.82 19917810.82 0.00 1990858.32 2 2 21721491.55 21721491.55 0.00 1803680.73 3 0 23391753.89 23391753.89 0.00 1670262.34 4 0 25078445.71 25078445.71 0.00 1686691.83 5 0 26696810.53 26696810.53 0.00 1618364.81 6 0 28259311.97 28259311.96 0.00 1562501.44 7 0 29768012.17 29768012.17 0.00 1508700.21 8 0 31223523.41 31223523.41 0.00 1455511.23 9 0 32626582.33 32626582.33 0.00 1403058.92 10 0 33977978.11 33977978.11 0.00 1351395.79 22 Programação Dinâmica Estocástica EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 11 of 15 Iteração = 2000 -------------------------------------------------------------------- i k f(n,i) f(n-1,i) Diferença ValorAuto -------------------------------------------------------------------- 0 2 17926952.55 17926952.55 0.00 1 2 19917810.87 19917810.87 0.00 1990858.32 2 2 21721491.60 21721491.60 0.00 1803680.73 3 0 23391753.94 23391753.94 0.00 1670262.34 4 0 25078445.76 25078445.76 0.00 1686691.83 5 0 26696810.58 26696810.58 0.00 1618364.81 6 0 28259312.01 28259312.01 0.00 1562501.44 7 0 29768012.22 29768012.22 0.00 1508700.21 8 0 31223523.46 31223523.46 0.00 1455511.23 9 0 32626582.37 32626582.37 0.00 1403058.92 10 0 33977978.16 33977978.16 0.00 1351395.79 Observações  Nas primeiras iterações (1, 2, 3 e 7), os valores de  ,  f n i e  f n 1,  i  se modificam a cada iteração, e por conta disto, também a Diferença     , 1, f n i f n i   e o ValorAuto do i-ésimo automóvel, calculado por     , , 1 f n i  f n i  . Nesta situação, nenhuma informação é útil para tomada de decisão.  Quando a iteração 30 é alcançada, observa-se que os valores da Diferença são os mesmos entre todos os estados. Isto caracteriza uma situação a partir da qual a estratégia ótima e o ValorAuto não mais se alteram, por maior que seja o número de iterações. 22 Programação Dinâmica Estocástica EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 12 of 15  A partir da milésima iteração, a Diferença se anula e todos os valores apresentados se estabilizam. Esta situação indica que, ao aumentar o número de períodos analizados, os retornos acrescidos ao final do horizonte de planejamento são irrelevantes e seus valores presentes tendem para zero.  Pode-se utilizar os resultados da iteração 30, na qual já se observa a igualdade nas Diferença’s dos estados, para tomar decisão e obter as informações pertinentes:               30 30 209.404,40 0 [0] 7.456.732,71 17.926.952,71 0,02 0 0 0,02 17.926.952,71 358.539,05 1 1 0,02 19.917.810,87 398.356,22 10 10 0,02 33.977.978,16 679.559,56 Dif f f R f R f R f                              Calculando a matriz de transição de estados, considerando as decisões ótimas, tem-se ij P     , onde ( , , * ) ij   p i j ki . 22 Programação Dinâmica Estocástica EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 13 of 15 0,0000 0,0000 1,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,7275 0,2725 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 P  0,0000 0,3732 0,3543 0,2725 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,1429 0,2303 0,3543 0,2725 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0431 0,0998 0,2303 0,3543 0,2725 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 0,0107 0,0324 0,0998 0,2303 0,3543 0,2725 0,0000 0,0000 0,0000 0,0000 0,0000 0,0022 0,0084 0,0324 0,0998 0,2303 0,3543 0,2725 0,0000 0,0000 0,0000 0,0000 0,0004 0,0018 0,0084 0,0324 0,0998 0,2303 0,3543 0,2725 0,0000 0,0000 0,0000 0,0001 0,0003 0,0018 0,0084 0,0324 0,0998 0,2303 0,3543 0,2725 0,0000 0,0000 0,0000 0,0001 0,0003 0,0018 0,0084 0,0324 0,0998 0,2303 0,3543 0,2725 0,0000 0,0000 0,0000 0,0001 0,0003 0,0018 0,0084 0,0324 0,0998 0,2303 0,3543 0,2725                                   Determinando as probabilidades do sistema se encontrar nos diversos estados, tem-se:    0,0501 0,0854 0,4073 0,3047 0,1526 0,0000 0,0000 0,0000 0,0000 0,0000 0,0000 Calculando o valor presente esperado da concessionária,independente do estoque disponível, bem como a rendimento esperado por período, tem-se:   22.398.404,99 0,02 22.398.404,99 447.968,10 i i VP f i R VP           22 Programação Dinâmica Estocástica EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 14 of 15 O valor de R precisa ser suficiente para pagar os custos fixos semestrais, incluido aluguéis da loja, custo de pessoal, despesas com energia, entre outros. O que sobra é o lucro semestral do investidor. 22 Programação Dinâmica Estocástica EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 15 of 15 F I M (© 2020 Prof. Sérgio Mayerle)