Slide Programação Dinâmica Determinística Modelos-2020 1

20 Programação Dinâmica Determinística – Modelos © 2020 Prof. Sérgio F. Mayerle 20 Programação Dinâmica Determinística – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 2 of 14  Modelo 01: Compra e venda de estoque com retorno  Modelo 02: Ampliação de capacidade da fábrica  Modelo 03: Manutenção e substituição de equipamentos 20 Programação Dinâmica Determinística – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 3 of 14 Modelo 01: Compra e venda de estoque com retorno Uma companhia possui um armazém no qual pode ser guardado determinado tipo de mercadoria. No início de cada ano o armazém pode estar cheio ou vazio. Se o armazém estiver cheio, a companhia pode tomar as seguintes decisões:  Não comprar e não vender, deixando o armazém cheio para o início do próximo ano;  Vender toda a mercadoria e adquirir estoque novo, deixando o armazém cheio no início do ano seguinte;  Vender toda a mercadoria e não comprar nada. Se o armazém estiver vazio, a companhia poderá:  Não comprar;  Comprar o suficiente para encher o armazém. Uma estimativa dos preços de compra e venda da mercadoria foi preparada e é apresentada abaixo: Valores (em milhões de US$) Ano 1 2 3 4 5 Preço de venda 10 13 18 14 11 Preço de compra 11 13 15 15 11 Se o armazém estiver cheio durante um ano, sem movimento de estoque, a companhia tem um custo de US$ 1.000.000,00. Determine o plano ótimo de compra e venda de mercadoria para um período de planejamento de 5 anos, supondo que o armazém atualmente está cheio, e que deverá estar cheio no final deste período. Considere que os valores futuros são descontados com uma taxa de 25% ao ano. 20 Programação Dinâmica Determinística – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 4 of 14 Modelo  , ,  r n i k 2 k   f n 1,  j   ,  f n i 1 k  4 k  3 k  4 k        , 1, , , , 1,25 n i k K f n j f n i Max r n i k           Compra e venda de estoque com retorno Sistema Armazém Estágio Número de períodos para o fim do horizonte de planejamento:  n 0,1,...,5 Estado Situação do armazém:  i 1 estoque cheio;  i  0 estoque vazio:  i 0,1 Ação Comprar e vender ( k 1) ; comprar ( k  2) ; vender ( k  3) ; não comprar e não vender ( k  4) :  k  1,2,3,4 20 Programação Dinâmica Determinística – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 5 of 14 Retorno Receita líquida anual de operação do armazém, onde ( ) PV n é o preço de venda no estágio n, e ( ) PC n é o preço de compra no estágio n: ( ) ( ) 1 ( ) 2 ( , , ) ( ) 3 4 se se se se PV n PC n k PC n k r n i k PV n k i k              Valor do Estado Receita líquida total obtida com a operação ótima do armazém, até o fim do horizonte de planejamento: 0 1 (0, ) 0 se se i f i i       Função de Recorrência   , ( 1, ) ( , ) ( , , ) 1 25% n i k K f n j f n i Max r n i k            Função de Transição 1 {1,2} ( , , ) 4 0 3 se se se k j t n i k i k k           20 Programação Dinâmica Determinística – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 6 of 14 Conjunto de Ações Viáveis , {1,3,4} 1 {2,4} 0 se se n i i K i       A solução de um problema de programação dinâmica se dá mediante a implementação do modelo via programação computacional. Solução -------------------------------------------------------------------- n i k j r(n,i,k) f(n-1,j) f(n,i|k) f(n,i) -------------------------------------------------------------------- 0 0 *** *** *** *** *** -100000.00 0 1 *** *** *** *** *** 0.00 -------------------------------------------------------------------- 1 0 2 1 -11.00 0.00 -11.00 -11.00 1 0 4 0 0.00 -100000.00 -80000.00 -11.00 -------------------------------------------------------------------- 1 1 1 1 0.00 0.00 0.00 0.00 1 1 3 0 11.00 -100000.00 -79989.00 0.00 1 1 4 1 -1.00 0.00 -1.00 0.00 -------------------------------------------------------------------- 2 0 2 1 -15.00 0.00 -15.00 -15.00 2 0 4 0 0.00 -11.00 -8.80 -8.80 -------------------------------------------------------------------- 2 1 1 1 -1.00 0.00 -1.00 -1.00 2 1 3 0 14.00 -11.00 5.20 5.20 2 1 4 1 -1.00 0.00 -1.00 5.20 -------------------------------------------------------------------- 20 Programação Dinâmica Determinística – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 7 of 14 3 0 2 1 -15.00 5.20 -10.84 -10.84 3 0 4 0 0.00 -8.80 -7.04 -7.04 -------------------------------------------------------------------- 3 1 1 1 3.00 5.20 7.16 7.16 3 1 3 0 18.00 -8.80 10.96 10.96 3 1 4 1 -1.00 5.20 3.16 10.96 -------------------------------------------------------------------- 4 0 2 1 -13.00 10.96 -4.23 -4.23 4 0 4 0 0.00 -7.04 -5.63 -4.23 -------------------------------------------------------------------- 4 1 1 1 0.00 10.96 8.77 8.77 4 1 3 0 13.00 -7.04 7.37 8.77 4 1 4 1 -1.00 10.96 7.77 8.77 -------------------------------------------------------------------- 5 0 2 1 -11.00 8.77 -3.99 -3.99 5 0 4 0 0.00 -4.23 -3.39 -3.39 -------------------------------------------------------------------- 5 1 1 1 -1.00 8.77 6.01 6.01 5 1 3 0 10.00 -4.23 6.61 6.61 5 1 4 1 -1.00 8.77 6.01 6.61 -------------------------------------------------------------------- 20 Programação Dinâmica Determinística – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 8 of 14 Modelo 02: Ampliação de capacidade da fábrica Uma empresa fabricante de refrigeradores está estudando a possibilidade de ampliar as suas instalações industriais, que está estruturada em linhas de produção. Atualmente, o seu sistema produtivo conta com 10 linhas de produção em operação, sendo que cada uma delas pode produzir mensalmente 2.000 refrigeradores. No último ano, foram vendidos 235.000 refrigeradores, existindo uma tendência deste número aumentar a uma taxa de 3,0% ao ano. O lucro líquido que a empresa ganha com cada refrigerador vendido é de US$ 10,25. Para que uma nova linha de produção seja implantada, há necessidade de se investir US$ 105.000,00. Estes valores vêm se mantendo constantes nos últimos 15 anos, e não se acredita que possam vir a mudar nos próximos anos. O tempo necessário para a implantação de uma destas linhas é de um ano, isto é, tomando a decisão de implantar uma ou mais linhas em um ano qualquer, as mesmas entrarão em produção no ano seguinte. Formule um modelo de Programação Dinâmica que maximize o lucro da empresa nos próximos 10 anos, sabendo que Taxa de Mínima Atratividade (TMA) da empresa é de 13% ao ano.  , ,  r n i k  f n 1,  j  k  ,  f n i 20 Programação Dinâmica Determinística – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 9 of 14 Modelo Ampliação de uma fábrica de refrigeradores Sistema Fábrica Estágio Número de períodos que faltam para o fim do horizonte de planejamento:  n 0,1,2,...,10 Estado Número de linhas de produção instaladas:  i 10,11,..,14 Ação Instalar ( k 1) ou não instalar ( k  0) uma linha de produção no período:  k  0,1 Retorno Receita líquida anual obtida com as vendas ( Vn ) e investimentos da fábrica: ( , , ) 10,25 105000 n r n i k V k    , onde: 11 {24000 ; 235000 (1 3%) } n Vn Min i      Valor do Estado Valor presente dos lucros obtidos com vendas e investimentos realizados: ( , ) 0 f n i i   Função de Recorrência     , ( , , ) ( 1, ) ( , ) 1 6,5% 1 13% n i k K r n i k f n j f n i Max             20 Programação Dinâmica Determinística – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 10 of 14 Função de Transição ( , , ) j t n i k i k    Conjunto de Ações viáveis , {0,1} 14 {0} 14 se se n i i K i       Solução -------------------------------------------------------------------- Ano i k Capac Demanda Vendas Receita Invest VPLiquido -------------------------------------------------------------------- 1 10 1 240000 242050 240000 2460,00 105,00 2204,86 2 11 0 264000 249312 249312 2555,44 0,00 2399,48 3 11 0 264000 256791 256791 2632,11 0,00 2471,46 4 11 1 264000 264495 264000 2706,00 105,00 2435,85 5 12 0 288000 272429 272429 2792,40 0,00 2621,97 6 12 0 288000 280602 280602 2876,17 0,00 2700,63 7 12 1 288000 289020 288000 2952,00 105,00 2666,83 8 13 0 312000 297691 297691 3051,33 0,00 2865,10 9 13 0 312000 306622 306622 3142,87 0,00 2951,05 10 13 0 312000 315820 312000 3198,00 0,00 3002,82 -------------------------------------------------------------------- Valor Presente Líquido Total 15634,30 -------------------------------------------------------------------- 20 Programação Dinâmica Determinística – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 11 of 14 Modelo 03 – Manutenção e Subst. de Equipamentos Um equipamento de um processo de produção é inspecionado anualmente, podendo ser substituído ou reparado para mais um ano de operação. O custo de manutenção e o valor de mercado do equipamento são apresentados abaixo, em função da idade no momento da inspeção: Idade (anos) 0 1 2 3 4 5 Manutenção (US$x1.000) 1.250 1.850 2.820 4.150 Valor Mercado (US$x1.000) 20.000 14.000 9.800 6.800 4.800 3.200 O custo de um equipamento novo é US$ 20.000.000,00. A linha de produção deve operar por mais 10 anos, e no fim deste período todos os equipamentos da linha serão sucateados. O equipamento atualmente instalado terá três anos de idade na próxima revisão. Determine o plano ótimo de substituição deste equipamento, considerando a TMA efetiva de 10% a.a. 1 i 5 1 j 5  , ,  r n i k  f n 1,  j  n-1 n 0 k   ,  f n i k 1 20 Programação Dinâmica Determinística – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 12 of 14 Modelo Manutenção e substituição de equipamentos Sistema Máquina Estágio Número de períodos que faltam para o fim do horizonte de planejamento:  n 0,1,2,...,10 Estado Número de linhas de produção instaladas:  i 1,2,..,5 Ação Manter ( k  0) ou substituir ( k 1) :  k  0,1 Retorno Custos de manutenção e substituição do equipamento no período:         0 , , 0 1 se se CM i k r n i k VM i VM k        Valor do Estado Valor presente dos custos de manutenção e substituição de equipamento:   ( , ) f n i VM i i   Função de Recorrência   ( 1, ) ( , ) ( , , ) 1 10% i k K f n j f n i Max r n i k            20 Programação Dinâmica Determinística – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 13 of 14 Função de Transição 1 0 ( , , ) 1 0 se se i k j t n i k k         Conjunto de Ações viáveis {0,1} 5 {1} 5 se se i i K i       Solução ------------------------------------------------------------ Data i k Manutenção Compra Venda Resultado ------------------------------------------------------------ 0 3 0 -2820.00 0.00 0.00 -2820.00 1 4 0 -4150.00 0.00 0.00 -4150.00 2 5 1 0.00 -20000.00 3200.00 -16800.00 3 1 0 -1250.00 0.00 0.00 -1250.00 4 2 0 -1850.00 0.00 0.00 -1850.00 5 3 0 -2820.00 0.00 0.00 -2820.00 6 4 1 0.00 -20000.00 4800.00 -15200.00 7 1 0 -1250.00 0.00 0.00 -1250.00 8 2 0 -1850.00 0.00 0.00 -1850.00 9 3 0 -2820.00 0.00 0.00 -2820.00 10 4 *** *** *** 4800.00 4800.00 ------------------------------------------------------------ Valor Presente Líquido Total -33860.58 ------------------------------------------------------------ 20 Programação Dinâmica Determinística – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 14 of 14 F I M (© 2020 Prof. Sérgio Mayerle)