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

21 Programação Dinâmica Determinística – Modelos © 2020 Prof. Sérgio F. Mayerle 21 Programação Dinâmica Determinística – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 2 of 12  Modelo 04: Planejamento da produção  Modelo 05: Carregamento do veículo  Modelo 06: Planejamento da manutenção 21 Programação Dinâmica Determinística – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 3 of 12 Modelo 04: Planejamento da Produção Um construtor de barcos tem, em carteira, os pedidos apresentados na tabela abaixo para serem atendidos no fim dos próximos meses. Pedidos em Carteira Mês Fev Mar Abr Mai Jun Jul Barcos 1 2 5 3 2 1 Este construtor pode fabricar até quatro barcos por mês, e pode manter em estoque até três barcos. Se houver fabricação de barcos em um determinado mês, um custo de US$ 400.000,00 é 1realizado, independente da quantidade produzida, além do custo de fabricação que é de US$ 1.000.000,00 por barco produzido. O custo de manutenção de um barco em estoque por um mês completo é de US$ 100.000,00. Determine o plano ótimo de produção, assumindo que o estoque inicial no início de Fevereiro é zero, e que o estoque no final de Julho deve ser zero. 0 i 3 0 j 3  , ,  r n i k  f n 1,  j  n-1 n k  ,  f n i 21 Programação Dinâmica Determinística – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 4 of 12 Solução Planejamento da Produção e Estoque de Barcos Sistema Estoque de barcos Estágio Número de períodos que faltam para o fim do horizonte de planejamento:  n 0,1,...,6 Estado Número de barcos em estoque:  i 0,...,3 Ação Número de barcos que devem ser produzidos no período:  k  0,1,...,4 Retorno Custo do período, incluindo custos fixos, de estoque e de produção: 100 0 ( , , ) 400 100 1000 1 se se i k r n i k i k k         Valor do Estado Custo total de operação da fábrica, até o fim do horizonte de planejamento: (0, ) 0 f i i   Função de Recorrência   , ( , ) ( , , ) ( 1, ) k Kn i f n i Min r n i k f n j     Função de Transição   ( , , ) j t n i k i k D n     onde   D n são as encomendas a serem entregues no final do estágio n Conjunto de Ações Viáveis 0 3  k  0 ( ) 3 ( ) 3 ( ) j i k D n D n i k D n i                  , | max 0; ( ) min 3;3 ( ) Kn i k D n i k D n i       21 Programação Dinâmica Determinística – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 5 of 12 ---------------------------------------------------------------------- Data i k Demanda Fixo Produção Estoque Resultado ---------------------------------------------------------------------- 1 0 2 1 400.00 2000.00 0.00 2400.00 2 1 3 2 400.00 3000.00 100.00 3500.00 3 2 3 5 400.00 3000.00 200.00 3600.00 4 0 3 3 400.00 3000.00 0.00 3400.00 5 0 3 2 400.00 3000.00 0.00 3400.00 6 1 0 1 0.00 0.00 100.00 100.00 ---------------------------------------------------------------------- Valor Total 16400.00 ---------------------------------------------------------------------- 21 Programação Dinâmica Determinística – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 6 of 12 Modelo 05: Carregamento do veículo Um mercador itinerante pode transportar no máximo 14 ton de mercadorias em seu caminhão. Ele vende quatro diferentes mercadorias, denominadas por A, B, C e D, cujos volumes unitários são 1 ton, 3 ton, 4 ton e 6 ton, respectivamente. O lucro esperado associado às diversas quantidades de carga, por tipo de produto, é apresentado abaixo. Lucro Esperado por Tipo de Produto (R$) Nivel de Carga (unid) A B C D 1 5.000 18.000 14.000 22.000 2 9.000 32.000 28.000 40.000 3 12.000 42.000 38.000 50.000 4 14.000 50.000 44.000 *** 5 15.000 56.000 *** *** Quantos itens de cada mercadoria deverão ser transportados, para que o retorno esperado seja maximizado? 0 i 14 0 j 14  , ,  r n i k  f n 1,  j  n-1 n k  ,  f n i 21 Programação Dinâmica Determinística – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 7 of 12 Solução Carregamento do Veículo Sistema Espaço existente na carroceria do veículo Estágio Número de produtos que faltam ser carregados, considerando a sequência (A,B,C,D):  n 0,1,...,4 Estado Capacidade disponível na carroceria:  i 0,1,...,14 Ação Quantidade do produto n carregada no veículo:  k  0,1,...,5 Retorno Lucro obtido com a venda de k unidades do produto n:     , , , r n i k  Lucro k n Valor do Estado Lucro total com o carregamento a ser alocado no espaço disponível na carroceria do veículo: (0, ) 0 f i i   Função de Recorrência   , ( , ) ( , , ) ( 1, ) k Kn i f n i Max r n i k f n j     Função de Transição ( , , ) ( ) j t n i k i k P n    onde   P n é o peso de uma unidade do produto n Conjunto de Ações Viáveis 0 5  k  0 ( ) 14 ( ) i j i k P n k P n       , | 0 min 5; ( ) n i i K k k P n                21 Programação Dinâmica Determinística – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 8 of 12 ---------------------------------- Prod i k PesoUnit Resultado ---------------------------------- 1 14 1 6 22000.00 2 8 0 4 0.00 3 8 2 3 32000.00 4 2 2 1 9000.00 ---------------------------------- Lucro Total 63000.00 ---------------------------------- 21 Programação Dinâmica Determinística – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 9 of 12 Modelo 06: Planejamento da Manutenção A manutenção de uma instalação deve ser completada em 10 dias. A manutenção tem três estágios: terraplanagem, reparos e reconstrução, que deverão ser realizados seqüencialmente. O tempo necessário para a realização de cada uma destas etapas, e o custo das mesmas, dependem dos recursos empregados para a sua realização, conforme mostra a tabela abaixo. Custo (em US$ x 1.000.000) Tempo de Execução (em dias) Etapa 1 2 3 4 5 6 7 Terraplenagem 18.0 17.0 15.0 12.0 8.0 7.0 6.0 Reparos 11.0 10.0 9.0 8.0 7.0 6.0 5.0 Reconstrução 20.0 18.0 15.0 12.0 9.0 8.0 7.0 Desenvolva um modelo de alocação do tempo disponível entre as etapas desta manutenção.  , ,  r n i k  f n 1,  j  k  ,  f n i 21 Programação Dinâmica Determinística – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 10 of 12 Solução Planejamento da Reconstrução Sistema Horizonte de planejamento Estágio Número de etapas que faltam ser realizadas (Terraplenajem, Reparos,Reconstrução):  n 0,1,...,3 Estado Tempo disponível para completar a manutenção:  i 0,1,...,10 Ação Tempo alocado para a realização da etapa n:  k  0,1,...,5 Retorno Custo de realização da etapa n em k dias:     , , , r n i k  Custo n k Valor do Estado Custo total para realização das etapas remanescentes considerando o tempo disponível: (0, ) 0 f i i   Função de Recorrência   , ( , ) ( , , ) ( 1, ) k Kn i f n i Min r n i k f n j     Função de Transição ( , , ) j t n i k i k    Conjunto de Ações Viáveis 1 7  k  0 10 10 j i k i k i             , |1 min 7; Kn i k k i    21 Programação Dinâmica Determinística – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 11 of 12 ------------------------ n i k Resultado ------------------------ 3 10 4 12000.00 2 6 1 11000.00 1 5 5 8000.00 ------------------------ Custo Total 31000.00 ------------------------ 21 Programação Dinâmica Determinística – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 12 of 12 F I M (© 2020 Prof. Sérgio Mayerle)