Aula 9 - Programação Dinâmica e Análise de Sistemas Ambientais

CENTRO FEDERAL DE EDUCAÇÃO TECNOLÓGICA DE MINAS GERAIS COORDENAÇÃO DO CURSO DE ENGENHARIA AMBIENTAL E SANITÁRIA DEPARTAMENTO DE CIÊNCIA E TECNOLOGIA AMBIENTAL Aula 9 Programação Dinâmica Prof Frederico Keizo Odan Análise de Sistemas Ambientais Análise de Sistemas Ambientais Motivação Problema determinar o caminho mais curto de 1 a 12 no grafo abaixo Procedimento Progressivo 0 1 9 7 3 2 4 2 7 11 11 8 6 5 3 5 6 4 2 5 2 1 15 9 16 11 7 3 3 4 2 5 9 2 11 4 7 9 6 10 8 14 10 16 12 Análise de Sistemas Ambientais Motivação Problema determinar o caminho mais curto de 1 a 12 no grafo abaixo Procedimento Regressivo 16 1 9 7 3 2 4 2 7 11 6 5 4 3 5 6 4 2 5 2 1 4 9 5 11 9 3 18 4 15 11 5 7 2 5 7 7 6 7 8 2 10 0 12 Análise de Sistemas Ambientais Motivação Problema determinar o caminho mais curto de 1 a 12 no grafo abaixo Combinação das trajetórias ótimas 5 4 8 11 9 0 1 9 7 3 2 4 2 7 11 6 3 5 6 4 2 5 2 1 2 07 3 27 6 5 4 7 95 10 142 12 Trajetória ótima através de cada nó Análise de Sistemas Ambientais Motivação Problema determinar o caminho mais curto de 1 a 12 no grafo abaixo Combinação das trajetórias ótimas Trajetória ótima com imposição de nó 8 5 4 3 7 6 11 10 9 1 9 7 3 2 4 2 7 11 11 8 6 5 4 3 5 6 4 2 5 2 1 2 28 8 107 12 Análise de Sistemas Ambientais Programação dinâmica Obtém solução ótima através da decomposição do problema em diferentes estágios Cada estágio é um subproblema com uma única variável Vantagem otimização de apenas uma variável por vez Estágios são interligado por meio da equação recursiva Cálculos são realizados recursivamente solução ótima de um subproblema é dado de entrada para o subproblema seguinte Análise de Sistemas Ambientais Resolução do problema do viajante Análise de Sistemas Ambientais Programação dinâmica Exemplo 1 Problema do caminho mais curto 1 2 3 5 6 7 7 8 5 12 8 9 7 13 4 9 6 Análise de Sistemas Ambientais Programação dinâmica Método exato para resolver problemas de programação inteira que envolvem apenas decisões sequenciais nos quais cada nova decisão depende apenas do estado atual do sistema e não das decisões anteriores isto é da forma como este estado foi atingido Principais conceitos envolvidos estágios etapas estados decisões função objetivo a ser otimizada restrições Análise de Sistemas Ambientais Programação dinâmica Definições estágio etapa parte do problema em que se toma uma determinada decisão que pode ou não alterar o estado do sistema representando uma transição entre o estado atual e o futuro estado condição do processo dentro de cada estágio Decisão alternativa disponível na conclusão de cada estágio Análise de Sistemas Ambientais Programação dinâmica Roteiro de aplicação 1 Dividir o problema em estágios 2 Determinar o ótimo em cada estágio 3 Relacionar o ótimo de um estágio a outro através de uma função recursiva 4 Percorrer todos os estágios para determinar o ótimo global Análise de Sistemas Ambientais Programação dinâmica Exemplo 1 Problema do caminho mais curto Divisão do problema em estágios 1 2 3 5 6 7 7 8 5 12 8 9 7 13 4 9 6 Estágio 3 Estágio 2 Estágio 1 Análise de Sistemas Ambientais Programação dinâmica Exemplo 1 Problema do caminho mais curto Qual a rota ótima em cada estágio 1 2 3 4 5 6 7 7 8 5 12 8 9 7 13 9 6 Estágio 1 Estágio 2 Estágio 3 2 3 4 5 6 f0 f1 f1 f2 f2 f3 Análise de Sistemas Ambientais Programação dinâmica Exemplo 1 Problema do caminho mais curto 1 2 3 4 7 7 8 5 9 7 1 9 6 Estágio 2 Estágio 3 2 3 4 0 f0 7 7 f3 f2 f2 12 12 12 8 5 5 17 17 6 3 6 8 5 8 5 21 Estágio 1 Função objetivo Variável de decisão Variável de estado si Função mudança de estado Análise de Sistemas Ambientais Programação dinâmica Exemplo 1 Problema do caminho mais curto 1 2 3 4 7 7 8 5 9 7 1 9 6 Estágio 2 Estágio 3 2 3 4 0 f0 7 7 f3 f2 f2 12 12 12 8 5 5 17 17 6 3 6 8 5 8 5 21 Função objetivo rota de distância mínima Min dxixi1 Variável de decisão rota escolhida no estágio i origem Variável de estado si qual cidade o viajante se dirige destino Função mudança de estado si xi si1 Estágio 1 Análise de Sistemas Ambientais Programação dinâmica Exemplo 1 Problema do caminho mais curto Roteiro ótimo 1 2 3 5 6 7 7 8 5 12 8 9 7 13 4 9 6 Estágio 3 Estágio 2 Estágio 1 Análise de Sistemas Ambientais Programação dinâmica Exemplo 1 Problema do caminho mais curto Mapeamento dos roteiros ótimos 1 2 3 4 5 6 7 Estágio 1 Estágio 2 Estágio 3 Solução ótima Análise de Sistemas Ambientais Programação dinâmica Aplicação a problemas de decisões sequenciais cada decisão aplicada a um estado em determinado estágio leva a um estado do estágio imediatamente seguinte Princípio da otimalidade uma sequencia ótima de decisões tem a propriedade de que quaisquer que sejam o estado e a decisão inicial as decisões remanescentes constituem uma sequencia ótima de decisões com relação ao estado decorrente da primeira decisão Alternativamente o toda subtrajetória da trajetória ótima é ótima com relação a suas extremidades inicial e final Análise de Sistemas Ambientais Problemas Típicos em RH Análise de Sistemas Ambientais Problemas típicos em recursos hídricos solucionados por PD Alocação de Água Operação de reservatórios Análise de Sistemas Ambientais Problemas típicos em recursos hídricos solucionados por PD Alocação de Água Alocação de água para irrigação em cinco pontos de captação A1 A2 A3 A4 A5 Q Q1 Q2 Q3 Q4 Q5 Qi vazão para irrigar Área Ai da cultura i Análise de Sistemas Ambientais Problemas típicos em recursos hídricos solucionados por PD Alocação de Água Função objetivo maximizar benefício Variável de decisão Nº de estágios Variável de estado Equação de mudança de estado Análise de Sistemas Ambientais Problemas típicos em recursos hídricos solucionados por PD Alocação de Água Retorno gerado pela alocação o 𝑅𝑛𝑄𝑛 O Rn retorno obtido ao se destinar vazão Qn ao usuário n Função objetivo o 𝑚𝑎𝑥 σ𝑖1 5 𝑅𝑖𝑄𝑖 Variável de decisão o 𝑄i vazão ótima alocada no ponto de captação i Nº de estágios 5 Variável de estado vazão disponível a montante do ponto de alocação Equação de mudança de estado o Eq Da continuidade 𝑆𝑛1 𝑆𝑛 𝑄𝑛 o Ex para 1º estágio S1 Q Análise de Sistemas Ambientais Problemas típicos em recursos hídricos solucionados por PD Alocação de Água Função recursiva regressiva Restrição Análise de Sistemas Ambientais Problemas típicos em recursos hídricos solucionados por PD Alocação de Água Função recursiva regressiva o 𝑓𝑛𝑆𝑛 𝑄𝑛 max 𝑅𝑛 𝑄𝑛 𝑓𝑛1 Sn1 o Para n5 𝑓5 𝑓5𝑆5 𝑄5 𝑅5𝑄5 máximo retorno para o ponto 5 o Para n4 𝑓4 𝑅4𝑄4 𝑓5𝑆5 o Retroativamente até o ponto 1 𝑓1 S1Q 𝑅1𝑄1 𝑓2𝑆2 σ𝑖1 5 𝑅𝑖𝑄𝑖 Restrição o σ𝑖1 5 𝑄𝑖 𝑄 Análise de Sistemas Ambientais Problemas típicos em recursos hídricos solucionados por PD Operação de reservatórios Objetivo maximizar benefício com operação do reservatório Variável de decisão Variável de estado Análise de Sistemas Ambientais Problemas típicos em recursos hídricos solucionados por PD Operação de reservatórios Objetivo maximizar benefício com operação do reservatório Variável de decisão vazão operada Variável de estado armazenamento do reservatório Análise de Sistemas Ambientais Problemas típicos em recursos hídricos solucionados por PD Operação de reservatórios estágio t Volume St Vazão Afluente qat Vazão Operada qot RSt St1 qot estágio t1 Volume St1 Vazão Afluente qat1 Vazão Operada qot1 RSt1 St1qat1qot1 qot1 Vol Reserv Vazão operada Obs R função de retorno Análise de Sistemas Ambientais Problemas típicos em recursos hídricos solucionados por PD Operação de reservatórios Função objetivo 𝑚𝑎𝑥 σ𝑖1 𝑇 𝑅𝑡𝑆𝑡 𝑆𝑡1 𝑞𝑜𝑡 Função o do volume em t St e t1 St1 o Vazão operada em t qot Equação de mudança de estado o St1 St qat Δt qotΔt Et Pt qmintΔt o Em que Et evapotranspiração Pt precipitação qmint vazão mínima descarregada Análise de Sistemas Ambientais Problemas típicos em recursos hídricos solucionados por PD Operação de reservatórios Função recursiva regressiva o 𝑓n𝑆n 𝑚𝑎𝑥 𝑅n𝑆𝑛 𝑆𝑛1 qonfn1Sn1 Restrições o Vazão positiva 𝑞𝑜𝑛 0 o Volume Mínimo 𝑞𝑜𝑛 𝑡 Sn qan 𝑡 o Volume Máximo 𝑞𝑜𝑛 𝑡 Sn qan 𝑡 𝑉𝑚𝑎𝑥 o Vazão operada máxima 𝑞𝑜𝑛 qomax Análise de Sistemas Ambientais Mal da dimensionalidade Seja a operação do Sistema Elétrico Brasileiro Composto por cerca de 60 reservatórios Considerandose 10 discretizações de volume de cada reservatório Resulta em 1060 estados a serem analisados em cada estágio Atualmente utilizase 4 reservatórios equivalentes com 10 discretizações de volume e 120 meses 10 anos resulta em 1200000 estados a serem analisados Análise de Sistemas Ambientais Exemplo de alocação de água Seja Q3 Determine alocação ótima de água entre os 3 usuários utilizandose a PD Regressiva A1 A2 A3 Q Q1 Q2 Q3 Vazão alocada Qi m³ Retorno Rj para usuário Aj 1000 R A1R1 A2R2 A3R3 1 2 1 4 2 5 4 5 3 6 7 6 Análise de Sistemas Ambientais Outras aplicações da PD Problema da MochilaCarga Problema de corte Problema da reposição de equipamento Problema do investimento