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

23 Programação Dinâmica Estocástica – Modelos © 2020 Prof. Sérgio F. Mayerle 23 Programação Dinâmica Estocástica – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 2 of 20  Modelo 08: Operação do Sistema de Geração Elétrica  Modelo 09: Abatedouro de Frango 23 Programação Dinâmica Estocástica – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 3 of 20 Modelo 08: Operação do Sistema de Geração Elétrica A concessionária de energia elétrica dispõe de duas fontes geradoras, sendo uma hidráulica e outra térmica (carvão, óleo, nuclear,...), que abastecem o mercado local. O sistema de distribuição foi concebido de forma a permitir que a demanda seja atendida por qualquer uma das unidades. O custo de operação da unidade hidrelétrica pode ser considerado desprezível, se comparado com os custos operacionais da unidade térmica, que estão apresentados abaixo. Custo Operacional Mensal da Unidade Térmica Geração (UE/mês)* 0 1 2 3 4 5 Custo Mensal (R$/mês x 106) 1,00 2,00 4,00 7,00 11,00 16,00 * UE = unidades de energia equivalente Considere, ainda, a existência de um custo associado ao déficit de energia elétrica da ordem de 6 x 106 R$/UE, a ser pago pela concessionária no caso de não dispor de energia suficiente para abastecer o mercado (importação de energia de outras concessionárias interligadas ao sistema). A energia demandada pelo mercado deverá ser necessariamente atendida, a um preço de 5 x 106 R$/UE. O consumo do mercado, bem como a afluência ao reservatório da unidade hidráulica, são variáveis aleatórias, cujas distribuições de probabilidade estão apresentadas nos quadros abaixo. Distribuição de Probabilidade do Consumo Consumo Mensal (UE/mês) 9 10 11 12 13 14 Probabilidade 5% 10% 15% 25% 30% 15% 23 Programação Dinâmica Estocástica – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 4 of 20 Distribuição de Probabilidade de Afluência do Reservatório Afluência Mensal (UE/mês) 7 8 9 10 11 12 Probabilidade 10% 30% 30% 15% 10% 5% O reservatório pode armazenar até 5 UE equivalente, e a capacidade de geração mensal é de 10 UE. A afluência que exceder a capacidade do reservatório será vertida pela barragem, sem que haja aproveitamento energético. Para fins de planejamento da geração, poderá ser considerada, além da água armazenada no início do período, a afluência mínima prevista para o período. Pede-se: a) formular um modelo de programação dinâmica para determinar a política ótima de operação, considerando uma taxa de mínima atratividade efetiva de 1 % ao mês; b) determinar, com ajuda do modelo formulado, a política ótima de operação deste sistema de geração de energia; c) determinar o valor mínimo pelo qual este sistema hidro-térmico deveria ser vendido; d) determinar o máximo a ser gasto num projeto para aumentar a capacidade do reservatório em 1 UE; e) determinar o máximo que poderia ser gasto num projeto para aumentar a capacidade de geração da hidrelétrica em 1 UE; 23 Programação Dinâmica Estocástica – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 5 of 20 f) determinar o máximo que poderia ser gasto para implantação conjunta dos projetos descritos acima em (d) e (e); g) determinar o valor da água armazenada no reservatório, equivalente a 1 UE. k t c Figura 1 – Esquema de operação do sistema termo-elétrico 23 Programação Dinâmica Estocástica – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 6 of 20 Questão (a) Operação do Sistema de Geração Elétrica Sistema Reservatório da usina hidrelétrica Estado Volume de água disponível no reservatório da usina hidrelétrica:   0,1,..., RES i Cap  Estágio Número de meses que faltam para concluir o período de planejamento:  n 0,1,...,   . Ação Quantidade de energia entregue pela usina hidrelétrica:   0,1,..., GER k Cap  . Uma vez definido a quantidade de energia demandada pelo mercado   d e a produção da hidrelétrica   k , determina-se o quanto produzir na termoelétrica  t e o quanto importar   c , como segue:     max 0;min TERM ; t Cap d k     max 0; c d k t    Conjunto de Ações Viáveis As ações precisam respeitar a capacidade de geração da usina hidrelétrica e a disponibilidade mínima de água no período:     | 0 min 7, i GER K k Z k i Cap      Retorno É a renda mensal esperada produzida pelo sistema hidro-térmico, considerando a decisão k :     14 9 ( ) 5 6 cons d r k p d d CT t c          onde   CT t é o custo de operação mensal da usina térmica. Função de Probabilidade de Dado que 0 RES j i k a Cap      e 7 12  a  tem-se: a) se RES j  Cap , conclui-se que RES a Cap k i    ; 23 Programação Dinâmica Estocástica – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 7 of 20 Transição b) se RES j  Cap , conclui-se que a j k i              12 max 7; 0 , , , 7 12 0 se se e em caso contrário RES AF RES a Cap k i RES AF P a j Cap j Cap p n i j k P j k i j k i                         Valor do estado Valor presente da renda produzida pelo sistema hidro-térmico até o fim do período de planejamento, determinado pela seguinte função de recorrência:           0 1 , , , 1, 1 1% RES i Cap k K j f n i Max r k p i j k f n j                  onde     0, 0, 0,1,..., RES f i i Cap    j i a k 23 Programação Dinâmica Estocástica – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 8 of 20 Questão (b): Política ótima para Situação Atual DADOS ------------------------------------ Capacidade do Reservatório: 5 Capacidade de Hidrelétrica: 10 Iterações: 1324 MATRIZ DE PROBABILIDADE DE TRANSIÇÃO ------------------------------------ 0.1000 0.3000 0.3000 0.1500 0.1000 0.0500 0.1000 0.3000 0.3000 0.1500 0.1000 0.0500 0.1000 0.3000 0.3000 0.1500 0.1000 0.0500 0.0000 0.1000 0.3000 0.3000 0.1500 0.1500 0.0000 0.1000 0.3000 0.3000 0.1500 0.1500 0.0000 0.0000 0.1000 0.3000 0.3000 0.3000 PLANO ÓTIMO ---------------------------------------------------------- Nivel KÓtimo ProbEstac Retorno Valor Estado ---------------------------------------------------------- 0 7 0.05221239 43.15 5214.23 1 8 0.19292035 48.10 5219.18 2 9 0.27699115 52.20 5223.28 3 9 0.22168142 52.20 5226.76 4 10 0.14115044 55.30 5229.86 5 10 0.11504425 55.30 5232.63 ---------------------------------------------------------- Valor Presente Longo Prazo 5224.79 Questão (c) O valor esperado atual do sistema hidro-térmico de geração, independente do estado inicial, é R$ 5.224,79 milhões, valor que deveria ser fixado como preço de venda do sistema: ( ) 5.224,79 b VPLP  23 Programação Dinâmica Estocástica – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 9 of 20 Questão (d): Projeto de Ampliação da Capacidade do Reservatório em 1 UE DADOS ------------------------------------ Capacidade do Reservatório: 6 Capacidade de Hidrelétrica: 10 Iterações: 1324 MATRIZ DE PROBABILIDADE DE TRANSIÇÃO ------------------------------------ 0.1000 0.3000 0.3000 0.1500 0.1000 0.0500 0.0000 0.1000 0.3000 0.3000 0.1500 0.1000 0.0500 0.0000 0.1000 0.3000 0.3000 0.1500 0.1000 0.0500 0.0000 0.0000 0.1000 0.3000 0.3000 0.1500 0.1000 0.0500 0.0000 0.0000 0.1000 0.3000 0.3000 0.1500 0.1500 0.0000 0.0000 0.1000 0.3000 0.3000 0.1500 0.1500 0.0000 0.0000 0.0000 0.1000 0.3000 0.3000 0.3000 PLANO ÓTIMO ---------------------------------------------------------- Nivel KÓtimo ProbEstac Retorno Valor Estado ---------------------------------------------------------- 0 7 0.03982746 43.15 5224.39 1 8 0.14191229 48.10 5229.34 2 9 0.21653487 52.20 5233.44 3 9 0.22429907 52.20 5237.16 4 9 0.18670022 52.20 5240.34 5 10 0.11092739 55.30 5243.44 6 10 0.07979871 55.30 5246.06 ---------------------------------------------------------- Valor Presente Longo Prazo 5236.74 Portanto, o investimento máximo a ser realizado na ampliação da capacidade do reservatório em 1 UE será de R$ 11,95 milhões, calculado como segue: ( ) ( ) ( ) ( ) 5.236,74 5.224,79 11,95 d b LP LP d b LP LP VP VP VP VP      23 Programação Dinâmica Estocástica – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 10 of 20 Questão (e): Projeto de Ampliação da Capacidade de Geração em 1 UE DADOS ------------------------------------ Capacidade do Reservatório: 5 Capacidade de Hidrelétrica: 11 Iterações: 1324 MATRIZ DE PROBABILIDADE DE TRANSIÇÃO ------------------------------------ 0.1000 0.3000 0.3000 0.1500 0.1000 0.0500 0.1000 0.3000 0.3000 0.1500 0.1000 0.0500 0.1000 0.3000 0.3000 0.1500 0.1000 0.0500 0.0000 0.1000 0.3000 0.3000 0.1500 0.1500 0.0000 0.1000 0.3000 0.3000 0.1500 0.1500 0.0000 0.0000 0.1000 0.3000 0.3000 0.3000 PLANO ÓTIMO ---------------------------------------------------------- Nivel KÓtimo ProbEstac Retorno Valor Estado ---------------------------------------------------------- 0 7 0.05221239 43.15 5214.23 1 8 0.19292035 48.10 5219.18 2 9 0.27699115 52.20 5223.28 3 9 0.22168142 52.20 5226.76 4 10 0.14115044 55.30 5229.86 5 10 0.11504425 55.30 5232.63 ---------------------------------------------------------- Valor Presente Longo Prazo 5224.79 23 Programação Dinâmica Estocástica – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 11 of 20 Questão (f): Implantação conjunta dos projetos (d) + (e) DADOS ------------------------------------ Capacidade do Reservatório: 6 Capacidade de Hidrelétrica: 11 Iterações: 1324 MATRIZ DE PROBABILIDADE DE TRANSIÇÃO ------------------------------------ 0.1000 0.3000 0.3000 0.1500 0.1000 0.0500 0.0000 0.1000 0.3000 0.3000 0.1500 0.1000 0.0500 0.0000 0.1000 0.3000 0.3000 0.1500 0.1000 0.0500 0.0000 0.0000 0.1000 0.3000 0.3000 0.1500 0.1000 0.0500 0.0000 0.0000 0.1000 0.3000 0.3000 0.1500 0.1500 0.0000 0.0000 0.1000 0.3000 0.3000 0.1500 0.1500 0.0000 0.0000 0.0000 0.1000 0.3000 0.3000 0.3000 PLANO ÓTIMO ---------------------------------------------------------- Nivel KÓtimo ProbEstac Retorno Valor Estado ---------------------------------------------------------- 0 7 0.03982746 43.15 5224.39 1 8 0.14191229 48.10 5229.34 2 9 0.21653487 52.20 5233.44 3 9 0.22429907 52.20 5237.16 4 9 0.18670022 52.20 5240.34 5 10 0.11092739 55.30 5243.44 6 10 0.07979871 55.30 5246.06 ---------------------------------------------------------- Valor Presente Longo Prazo 5236.74 Portanto, como pode ser observado, apenas o investimento na ampliação da capacidade do reservatório melhora os resultados do sistema, e mesmo em conjunto, o resultado não é melhor do que o obtido somente com a ampliação do reservatório: ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 5.236,74 5.236,74 0 5.236,74 5.224,79 11,95 d e d LP LP d e d LP LP d e e LP LP d e e LP LP VP VP VP VP VP VP VP VP               23 Programação Dinâmica Estocástica – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 12 of 20 Questão (g) DADOS ------------------------------------ Capacidade do Reservatório: 5 Capacidade de Hidrelétrica: 10 Iterações: 1324 MATRIZ DE PROBABILIDADE DE TRANSIÇÃO ------------------------------------ 0.1000 0.3000 0.3000 0.1500 0.1000 0.0500 0.1000 0.3000 0.3000 0.1500 0.1000 0.0500 0.1000 0.3000 0.3000 0.1500 0.1000 0.0500 0.0000 0.1000 0.3000 0.3000 0.1500 0.1500 0.0000 0.1000 0.3000 0.3000 0.1500 0.1500 0.0000 0.0000 0.1000 0.3000 0.3000 0.3000 PLANO ÓTIMO ---------------------------------------------------------- Nivel KÓtimo ProbEstac Retorno Valor Estado ---------------------------------------------------------- 0 7 0.05221239 43.15 5214.23 1 8 0.19292035 48.10 5219.18 2 9 0.27699115 52.20 5223.28 3 9 0.22168142 52.20 5226.76 4 10 0.14115044 55.30 5229.86 5 10 0.11504425 55.30 5232.63 ---------------------------------------------------------- Valor Presente Longo Prazo 5224.79 O valor marginal da água pode ser determinado pelas diferenças entre valores dos estados, como segue: ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) (1) (0) 5.219,18 5.214,23 4,95 (2) (1) 5.223,28 5.219,18 4,10 (3) (2) 5.226,76 5.223,28 3,48 (4) (3) 5.229,86 5.226,76 3,10 (5) (4) 5.232,63 5.229,86 2,77 g g g g g g g g g g VP VP VP VP VP VP VP VP VP VP                     Como pode ser observado, o valor marginal da água é uma função decrescente em relação ao nível do reservatório. 23 Programação Dinâmica Estocástica – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 13 of 20 Valor Marginal x Nível Reservatório 4,95 4,10 3,48 3,10 2,77 0,00 1,00 2,00 3,00 4,00 5,00 6,00 1 2 3 4 5 UE R$ x 1.000.000 Valor Marginal x Nível Reservatório 4,95 4,10 3,48 3,10 2,77 0,00 1,00 2,00 3,00 4,00 5,00 6,00 1 2 3 4 5 UE R$ x 1.000.000 Esta conclusão corrobora, e é corroborada pela Lei da Utilidade Marginal Decrescente. Esta lei expressa que em uma relação econômica a utilidade marginal decresce à medida que se consome mais uma unidade. A utilidade total de um bem cresce quando se consome maiores quantidades dele, mas seu incremento da utilidade marginal é cada vez menor. A lei da utilidade marginal decrescente, demonstrada por Carl Menger (1840—1921), é axiomática por natureza. Trata- se de uma lei irrefutavelmente verdadeira, e ignorá-la leva a conclusões falaciosas e errôneas. Em última instância, leva à adoção de teorias econômicas sem fundamentos e políticas econômicas desastrosas. Para alguns economistas, entretanto, esta lei fundamental da Economia é tipicamente interpretada como se fosse uma lei psicológica, e que desta forma poderia ser alterada por um entendimento psicológico alternativo. Intencionalmente ou não, essa abordagem errônea e incompleta da ciência econômica, resulta em políticas equivocadas e destrutivas. 23 Programação Dinâmica Estocástica – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 14 of 20 Modelo 09: Abatedouro de Frango Um abatedouro de frango produz cortes em conformidade com os pedidos de diversos mercados. Excepcionalmente, quando um lote (30 toneladas) é abatido sem que exista um pedido correspondente em carteira, o abatedouro embala o lote para uma possível venda no mercado nacional ou para colocá-lo num frigorífico em área alfandegada, junto ao porto, à espera de um eventual comprador do mercado spot internacional. Os dados do problema são os seguintes:  o abate de frango, sem que exista um pedido correspondente em carteira, segue uma distribuição de Poisson com média de 1,5 lotes por semana;  o preço pago no mercado nacional depende da quantidade de lotes que se coloca à venda, como mostra a tabela abaixo; Num. de lotes Preço (R$/lote) 1 110.000,00 2 98.200,00 3 88.100,00 4 79.150,00 5 73.100,00 6 69.000,00 7 66.070,00 8 63.900,00  o preço pago pelo mercado internacional é de R$ 120.000,00 por lote; a demanda neste mercado segue uma distribuição de Poisson com média de 0,7 lotes por semana; 23 Programação Dinâmica Estocástica – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 15 of 20  a movimentação (entrada/saída) de um lote no armazém frigorífico custa R$ 15.000,00 (pagos na entrada), acrescido de um custo semanal de permanência de R$ 5.000,00 (pagos no início de cada semana);  todas as operações de venda são realizadas à vista, e a taxa de mínima atratividade semanal do abatedouro é de 1%. A venda no mercado nacional ocorre ao longo da mesma semana do abate. Entretanto, por razões de inspeção sanitária e alfandegária, a entrada no frigorífico ocorre somente 1 semana depois do abate. Formule o modelo de programação dinâmica e obtenha a estratégia ótima para operação deste sistema. Modelo Problema do Abatedouro Sistema Abatedouro + Frigorífico Estágio Número de semanas ( ) n que faltam para o fim do horizonte de planejamento: n{0,1,2,..., }  Estado Definido pela dupla ( , ) i a , onde ( )i é a quantidade de lotes em estoque no frigorífico e ( ) a é a quantidade de lotes disponíveis para abate: i {0,1,2,...,12} e a{0,1,2,...,12} Ação Quantidade ( ) k de lotes encaminhados para o estoque do frigorífico: k {0,1,2,...,12} Conjunto de Ações Viáveis Somente pode ser encaminhado para o frigorífico quantidades não superiores ao abatido. Portanto: { | 0 } Ka k k a      23 Programação Dinâmica Estocástica – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 16 of 20 Função de Retorno Esperado Resultado financeiro da semana, descontado para o início da semana, considerando as vendas no mercado nacional, as vendas no mercado spot internacional e os custos com armazenagem no frigorífico:       1 ( , , ) , , 1 2 nac spot frig r i a k R a k R i C a k          onde:  1% é a TMA semanal da empresa;       , Rnac a k a k P a k    é a receita no mercado nacional;   0 120 ( | ) i spot spot v R i v p v i      é a receita do mercado spot, descontado o custo de retirada do produto;   15 , 5 1 frig k C a k i     é o custo com o armazenamento; e         0.7 0.7 1 0.7 0 ! 0.7 ( | ) 1 ! 0 se se em caso contrário v d i spot d o e v i v e p v i v i d                    23 Programação Dinâmica Estocástica – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 17 of 20 Função de Recorrência Valor esperado do fluxo de caixa atualizado (rendas semanais) a partir do estágio   n e estado corrente   ,i a , considerando o uso da política ótima:         20 20 0 0 , , , , 1, , , , , , a k K j b f n i a Max r i a k f n j b p i a j b k               onde: 1 1     é o fator de desconto para o período semanal. Probabilidade de Transição  , , , ,  p i a j b k é a probabilidade de transição do estado   ,i a para o estado   ,j b , dado que foi tomada a decisão   k , calculada como:       , , , , | abate spot p i a j b k p b p i k j i    onde:       1.5 1.5 ! b abate e p b b   23 Programação Dinâmica Estocástica – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 18 of 20 Solução PLANO ÓTIMO Iterações = 1429 --------------------------------------------------------------- Estoque Abate Spot ProbEstac Retorno Valor Presente --------------------------------------------------------------- 0 0 0 0,0885 0,00 14.730,14 0 1 0 0,1327 109,45 14.839,59 0 2 1 0,0995 94,60 14.928,11 0 3 1 0,0498 180,57 15.014,08 0 4 2 0,0187 165,72 15.091,59 0 5 2 0,0056 233,28 15.159,15 0 6 3 0,0014 218,43 15.226,41 0 7 4 0,0003 203,58 15.285,06 --------------------------------------------------------------- 1 0 0 0,0846 55,11 14.836,58 1 1 0 0,1269 164,56 14.946,03 1 2 0 0,0952 250,53 15.032,00 1 3 1 0,0476 235,68 15.115,05 1 4 2 0,0178 220,83 15.187,47 1 5 2 0,0054 288,39 15.255,03 1 6 3 0,0013 273,54 15.318,02 1 7 4 0,0003 258,69 15.372,50 --------------------------------------------------------------- 2 0 0 0,0336 68,71 14.931,98 2 1 0 0,0504 178,17 15.041,43 2 2 0 0,0378 264,14 15.127,40 2 3 1 0,0189 249,28 15.201,54 2 4 1 0,0071 316,85 15.269,10 23 Programação Dinâmica Estocástica – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 19 of 20 2 5 2 0,0021 301,99 15.333,68 2 6 3 0,0005 287,14 15.389,51 2 7 3 0,0001 339,18 15.441,55 --------------------------------------------------------------- 3 0 0 0,0134 67,79 15.016,51 3 1 0 0,0201 177,24 15.125,96 3 2 0 0,0151 263,21 15.211,93 3 3 0 0,0075 330,77 15.279,50 3 4 1 0,0028 315,92 15.344,45 3 5 2 0,0008 301,07 15.400,63 3 6 2 0,0002 353,11 15.452,67 --------------------------------------------------------------- 4 0 0 0,0023 63,48 15.091,41 4 1 0 0,0034 172,93 15.200,86 4 2 0 0,0026 258,90 15.286,83 4 3 0 0,0013 326,46 15.354,40 4 4 1 0,0005 311,61 15.410,64 4 5 1 0,0001 363,65 15.462,68 --------------------------------------------------------------- 5 0 0 0,0006 58,57 15.157,52 5 1 0 0,0009 168,02 15.266,97 5 2 0 0,0007 253,99 15.352,94 5 3 0 0,0004 321,56 15.420,50 5 4 0 0,0001 373,60 15.472,54 --------------------------------------------------------------- Valor Presente Longo Prazo 14.955,39 23 Programação Dinâmica Estocástica – Modelos EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 20 of 20 F I M (© 2020 Prof. Sérgio Mayerle)