Matheus Pereira Vieira Modelo de Leilão de Energia e Reserva de Geração para Sistemas Termo-Eólicos Baseado em Otimização Robusta Bauru 2022 Matheus Pereira Vieira Modelo de Leilão de Energia e Reserva de Geração para Sistemas Termo-Eólicos Baseado em Otimização Robusta Dissertação de Mestrado apresentada ao Programa de Pós-Graduação em Engenharia Elétrica da Faculdade de Engenharia de Bauru como um dos requisitos para a obtenção do título de mestre em Engenharia Elétrica. Orientador: Prof. Dr. Leonardo Nepo- muceno Área de Concentração: Automação Linha de Pesquisa: Sistemas de Energia Universidade Estadual Paulista “Júlio de Mesquita Filho” Faculdade de Engenharia de Bauru Departamento de Engenharia Elétrica Bauru 2022 UNIVERSIDADE ESTADUAL PAULISTA Câmpus de Bauru ATA DA DEFESA PÚBLICA DA DISSERTAÇÃO DE MESTRADO DE MATHEUS PEREIRA VIEIRA, DISCENTE DO PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA, DA FACULDADE DE ENGENHARIA - CÂMPUS DE BAURU. Aos 04 dias do mês de maio do ano de 2022, às 14:00 horas, por meio de Videoconferência, realizou- se a defesa de DISSERTAÇÃO DE MESTRADO de MATHEUS PEREIRA VIEIRA, intitulada MODELO DE LEILÃO TERMO-EÓLICO BASEADO EM OTIMIZAÇÃO ROBUSTA. A Comissão Examinadora foi constituida pelos seguintes membros: Prof. Dr. LEONARDO NEPOMUCENO (Orientador(a) - Participação Virtual) do(a) Departamento de Engenharia Eletrica / Faculdade de Engenharia de Bauru - UNESP, Prof. Dr. ANDRE CHRISTOVAO PIO MARTINS (Participação Virtual) do(a) Departamento de Engenharia Elétrica / Faculdade de Engenharia de Bauru - UNESP, Profª. Drª. CLAUDIA ALEJANDRA SAGASTIZABAL (Participação Virtual) do(a) Instituto de Matemática, Estatística e Computação Científica - IMECC / Universidade Estadual de Campinas - UNICAMP. Após a exposição pelo mestrando e arguição pelos membros da Comissão Examinadora que participaram do ato, de forma presencial e/ou virtual, o discente recebeu o conceito final:_ _ _ _ _ _ _ _ _ _ _ _ _ . Nada mais havendo, foi lavrada a presente ata, que após lida e aprovada, foi assinada pelo(a) Presidente(a) da Comissão Examinadora. Prof. Dr. LEONARDO NEPOMUCENO Faculdade de Engenharia - Câmpus de Bauru - Av. Engenheiro Luiz Edmundo Carrijo Coube, , 14-01, 17033360, Bauru - São Paulo http://www.feb.unesp.br/posgrad_elet/index.phpCNPJ: 48.031.918/0030-69. Aprovado Faculdade de Engenharia de Bauru – Pós-graduação Av. Eng. Luiz Edmundo Carrijo Coube, 14-01 17033-360 Bauru - SP tel. (14) 3103-6108 spg.feb@unesp.br www.feb.unesp.br PROPOSTA DE ALTERAÇÃO DO TÍTULO A COMISSÃO EXAMINADORA PROPÕE A ALTERAÇÃO DO TÍTULO DO TRABALHO DO ALUNO: MATHEUS PEREIRA VIEIRA DE: “MODELO DE LEILÃO TERMO-EÓLICO BASEADO EM OTIMIZAÇÃO ROBUSTA” PARA: “MODELO DE LEILÃO DE ENERGIA E RESERVA DE GERAÇÃO PARA SISTEMAS TERMO- EÓLICOS BASEADO EM OTIMIZAÇÃO ROBUSTA” Bauru, 04 de maio de 2022. Prof. Dr. Leonardo Nepomuceno Orientador Resumo Este trabalho propõe um modelo de leilão para sistemas termo-eólicos baseado em oti- mização robusta para ser utilizado como despacho de energia e reserva do dia seguinte por operadores do sistema. O modelo tem como objetivo minimizar os custos de operação, maximizando a função de bem comum associada aos leilões de energia e reserva, levando em conta possíveis aleatoriedades na geração de potência eólica existentes dentro de um conjunto de incertezas robusto estabelecido. O modelo robusto toma uma decisão conservadora em relação ao leilão do dia seguinte, garantindo o atendimento da potência consumida alocada mesmo quando da ocorrência de flutuações na geração de potência eólica prevista. O grau de conservadorismo do modelo, entretanto, pode ser ajustado a partir do parâmetro de meta de incerteza. Foram comparadas as abordagens robusta e de ajuste de reserva por meio de simulações realizadas no sistema IEEE de 24 barras, evidenciando a relação de compromisso entre os aspectos econômicos e de segurança do sistema. Uma avaliação estatística da robustez das abordagens foi realizada, simulando-se uma grande quantidade de situações aleatórias para a geração eólica, evidenciando a confiabilidade e robustez do modelo proposto no que diz respeito ao atendimento das restrições de demanda e de reserva do sistema. Palavras-chave: Sistemas termo-eólicos, Otimização robusta, Geração eólica, Leilão multiperíodo, Procedimento de equilíbrio de mercado. Abstract This work proposes an auction model for thermal-wind power systems which is based on a robust optimization approach and used as a day-ahead power and reserve calculation procedure by a system operator. The model aims to minimize operating costs, maximizing the social welfare function associated with energy and reserve auctions, taking into account possible randomness in wind power generation existing within a robust set of uncertainties established. The robust model takes conservative decisions in relation to the day ahead auction, ensuring that the allocated power consumption is met even when there are fluctuations in the predicted wind power generation. The degree of conservativeness of the model can be adjusted by the uncertainty target adopted. The robust and reserve adjustment approaches are compared through simulations carried out in the IEEE 24-bus system, evidencing the compromise relationship between the economic and security aspects of the system. A statistical evaluation of the robustness of the approaches was carried out, simulating a large number of random situations for wind power generation, evidencing the reliability and robustness of the proposed model with regard to meeting the system’s demand and reserve constraints. Keywords: Thermo-wind power systems, Robust Optimization, Wind power generation, Multiperiod auction, Market clearing procedure. Sumário 1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Mercados de Eletricidade . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1 Organização Geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.1 Agentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.2 Mercados de Curto Prazo . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.3 Mercados de Reserva . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Impacto das Energias Renováveis . . . . . . . . . . . . . . . . . . . . . . . 12 3 Modelo de Leilão Termo-Eólico para Tratamento de Incertezas . . . . 14 3.1 Nomenclatura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.1.1 Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.1.2 Parâmetros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.1.3 Variáveis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2 Modelo Determinístico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.3 Abordagem Tradicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.4 Modelo Robusto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.4.1 Definindo um Conjunto de Incertezas para a Potência Eólica . . . . 23 3.4.2 Problema Robusto . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4 Métodos de Solução Utilizados . . . . . . . . . . . . . . . . . . . . . . . 27 4.1 Dualidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2 Método de Outer Approximation . . . . . . . . . . . . . . . . . . . . . . . 29 4.3 Método de Decomposição de Benders . . . . . . . . . . . . . . . . . . . . . 34 5 Metodologia de Solução Proposta para o Problema Robusto . . . . . 40 5.1 Modelo de Despacho Econômico: Problema Dual . . . . . . . . . . . . . . . 41 5.2 Método de Outer Approximation para o Tratamento do Termo Bilinear . . 47 5.2.1 Fluxograma do Método de Outer Approximation . . . . . . . . . . . 48 5.3 Método de Decomposição de Benders para a Obtenção das Decisões de Liga/Desliga . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.3.1 Fluxograma do Método de Decomposição de Benders . . . . . . . . 51 5.4 Estrutura Geral do Método Proposto . . . . . . . . . . . . . . . . . . . . . 51 5.5 Modelo de simulação de cenários aleatórios . . . . . . . . . . . . . . . . . . 52 6 Resultados Numéricos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 6.1 Dados do Sistema Teste . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 6.2 Comparação entre os Problemas Determinísticos Primal e Dual . . . . . . . 57 6.3 Comparação entre as Abordagens Robusta e de Ajuste de Reservas . . . . 60 6.4 Avaliação de cenários aleatórios . . . . . . . . . . . . . . . . . . . . . . . . 68 7 Conclusões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 Apêndices 77 APÊNDICE A Dados computacionais do Sistema de 24 Barras . . . . . 78 1 1 Introdução Muitos problemas existentes nas áreas de engenharia estão sujeitos à influência de incertezas causadas por fenômenos naturais ou desconhecidos, que dificultam a aplicação de modelos matemáticos determinísticos para a representação de processos ou sistemas. Isso ocorre também nos mercados de energia, principalmente quando há a inserção de energias de fontes renováveis provenientes da natureza. A questão das mudanças climáticas estudada por vários pesquisadores impulsionou a discussão sobre a necessidade da diminuição da emissão de gases do efeito estufa, além de dados indicarem o esgotamento dos combustíveis fósseis, o que causaria uma crise energética devido à forte influência das usinas termelétricas que utilizam esse tipo de combustível em todo o mundo. Assim, as energias renováveis passaram a obter destaque nas pesquisas e incentivos dados pelos governos, causando o aumento da parcela desse tipo de energia dentro das matrizes energéticas. Uma das energias renováveis que está ganhando força com o passar do tempo é a eólica, que utiliza a ação dos ventos para transformar energia cinética em energia elétrica. Apesar da utilização da energia eólica ter um impacto positivo na descarbonização do setor elétrico, esta fonte de energia introduz altos níveis de incerteza associados à velocidade dos ventos necessários à geração de energia. Estas incertezas trazem dificuldades adicionais para o despacho de geração do sistema elétrico, no que diz respeito a sua segurança e confiabilidade operativa. Os mercados de eletricidade, que possuem seus próprios procedimentos de despacho, também necessitam se adaptar à presença destas fontes de geração. Em mercados de eletricidade, o operador, juntamente com a câmara de comerciali- zação de energia elétrica, deve determinar, por meio de procedimentos de equilíbrio de mercado (MOTTO et al., 2002; BREGADIOLI et al., 2016; PEREIRA et al., 2017), o montante de energia e reserva que será alocado para o dia seguinte juntamente com o preço de equilíbrio, sendo que essa decisão pode estar sujeita a incertezas caso existam fontes alternativas de energia vinculadas ao sistema, como é o caso da eólica, onde a velocidade do vento pode variar de forma aleatória. Assim, um dos problemas enfrentados pelo operador do sistema de potência consiste na determinação, para cada período, do preço de compensação de mercado, da produção de energia, do nível de consumo e quais unidades estarão ligadas/desligadas, levando em conta as incertezas na potência gerada por parte das usinas eólicas. Na literatura, existem formas diferentes de tratar as incertezas nos leilões de energia que possuem geração eólicas em seu sistema. Em Anstine et al. (1963), Billinton e Karki (1999), Gooi et al. (1999) são utilizados valores determinísticos para as potências do sistema, sendo que incertezas existentes são ajustadas apenas através da alocação de potências de reserva. Esta abordagem é simples de ser implementada, porém pode comprometer a otimalidade do despacho de geração térmica caso seja designada uma reserva muito Capítulo 1. Introdução 2 grande para proteger o sistema de aleatoriedades. Por outro lado, caso seja designada uma reserva insuficiente, um desvio significativo de potência eólica pode deixar a segurança e a confiabilidade do sistema comprometidas. Já em Morales et al. (2014) uma das formas para o tratamento das incertezas na geração eólica em leilões, de modo a definir o despacho de potência do dia seguinte, consiste em adotar o valor esperado para potência eólica. Nesta abordagem, caso haja variações significativas nessa geração média esperada, é necessário executar um despacho de ajuste intra-diário que permite realocar a geração poucas horas antes da entrega de energia. Esse modelo, que trata a potência eólica como um valor determinístico, tem o inconveniente de deixar o sistema subdimensionado ou superdimensionado com relação a utilização de geradores térmicos, existindo a necessidade de outro algoritmo para ajustar o despacho do sistema, visto que a geração eólica é incerta. A forma de tratar incertezas provenientes da geração eólica mais difundida na literatura consiste em trabalhar com modelos de leilão estocásticos/probabilísticos, que resolvem o problema considerando um conjunto pré estabelecido de cenários possíveis para a velocidade de vento nas usinas eólicas (YIN et al., 2019; WANG et al., 2016; ZIA; NASIR; BHATTI, 2013). O inconveniente existente na abordagem estocástica/probabilística é que, caso ocorra na operação prática algum cenário muito diferente daqueles previamente mapeados, a geração termelétrica poderá estar subdimensionada ou superdimensionada, resultando no não atendimento da demanda total (em caso de subdimensionamento), ou em altos de custo de reserva (em caso de superdimensionamento). Caso sejam adotados muitos cenários para tentar diminuir as possibilidades de subdimensionamento/superdi- mensionamento, o algoritmo que aloca a geração poderá ficar inviável de ser executado computacionalmente em tempo real, devido à quantidade de combinações exponenciais de cenários que podem ocorrer. Conforme descrito em (CONEJO; CARRIóN; MORALES, 2010), existe a neces- sidade de um modelo de leilão para sistemas termo-eólicos que leve em consideração a aleatoriedade existente na geração eólica e estime de maneira eficaz e viável o despacho do sistema para o dia seguinte. Nesse sentido, este trabalho tem como objetivo propor um mo- delo de leilão termo-eólico baseado em otimização robusta que leva em conta as incertezas existentes na geração de potência por parte das unidades eólicas. A otimização robusta tem sido uma alternativa importante para o tratamento de incertezas em problemas de tomada de decisão. Diferentemente da otimização estocástica, que se baseia em um conjunto de cenários para a tomada de decisão, o tratamento de incertezas utilizado na otimização robusta busca estabelecer uma faixa no entorno da geração esperada, denominada de conjunto de incerteza, e calcular as decisões que deixam o sistema imune aos piores casos que possam ocorrer nesta faixa. Dessa forma, as decisões obtidas por meio da otimização robusta têm um alto grau de segurança na região de incerteza, o que é uma característica fundamental para a segurança e confiabilidade do despacho de geração calculado pelo Capítulo 1. Introdução 3 leilão. Por outro lado, há um custo associado à essa segurança, o qual vai se refletir nos preços de equilíbrio calculados pelo leilão. O problema de leilão para sistemas termo-eólicos proposto neste trabalho é formu- lado como um modelo de otimização robusto, em que a região de incerteza é caraterizada utilizando-se um conjunto de incertezas determinístico. O modelo proposto co-otimiza os sub-mercados de energia e reserva, de modo a representar explicitamente as inter-relações entre esses dois sub-mercados de energia. O modelo incorpora todas as restrições relevantes associadas à geração termelétrica, tais como rampas de partida, parada, subida e descida, restrições de mínimo tempo de operação e de desligamento, além dos custos de partida e desligamento das unidades termelétricas. Os consumidores são representados por meio de demanda elástica, e podem fornecer lances tanto no mercado de energia quanto no de reserva, i.e. considera-se que os consumidores podem vender energia no mercado de reserva, por meio de redução ou aumento em sua demanda, quando solicitado pelo operador do sistema. O modelo proposto é descrito por meio de um problema de otimização não linear inteiro-misto. Para a solução deste modelo, é proposta neste trabalho uma metodologia específica cujo objetivo é explorar algumas características do problema, e resolver algumas questões computacionais relacionadas à metodologia robusta, as quais são discutidas a seguir. Assim, a partir da metodologia proposta, obtém-se um modelo final que corresponde a um problema de programa linear inteiro-misto. A formulação robusta impõe algumas dificuldades computacionais para a resolução do problema robusto resultante, dentre as quais se destaca a estrutura Max-Min que resulta da abordagem. No caso do modelo de leilão proposto, deseja-se minimizar, utilizando-se as variáveis de decisão (basicamente dadas pelos despachos de geração e consumo e pela alocação de reservas), os custos das ofertas/lances fornecidos aos mercados de energia e reserva, ao mesmo tempo em que se busca maximizar, utilizando-se as variáveis aleatórias (i.e. despacho de geração das unidades eólicas), esses mesmos custos. Esta maximização é necessária à abordagem robusta pois tem como objetivo tomar a pior situação (pior caso), de modo a buscar imunizar o sistema contra tal situação. Assim, a estrutura do tipo Max-Min aparece também naturalmente na formulação de leilão proposta neste trabalho, e sua solução envolve uma metodologia específica, descrita a seguir. A técnica de solução aqui utilizada é baseada na metodologia descrita em (BERT- SIMAS et al., 2013), em que os autores resolvem um problema de unit commitment com incertezas na demanda dos consumidores. Nesta metodologia de solução, aplica-se, inicial- mente, o método de decomposição de Benders, de modo a decompor as decisões associadas às variáveis inteiras (liga/desliga das unidades) das variáveis contínuas do modelo. A partir desta decomposição, o problema de nível inferior corresponde a um despacho econômico com restrições de rede de transmissão em que a decisão de liga/desliga dos geradores é iterativamente fixada com os valores calculados pelo problema mestre (nível superior). O problema mestre, por sua vez, calcula os valores de liga/desliga levando em conta cortes Capítulo 1. Introdução 4 associados aos problemas iterativos de nível inferior. O problema de minimização de nível inferior apresenta ainda uma dificuldade adicional, relacionada à metodologia robusta, pois possui uma estrutura do tipo Max-Min, conforme comentado acima. Assim, uma segunda etapa da metodologia consiste em reformular este problema de minimização de nível inferior por meio do seu problema de otimização dual associado. Com esta reformulação, passa-se a ter uma estrutura do tipo Max-Max, que pode ser resolvida de forma direta, mas que possui ainda um termo bilinear na função objetivo. A linearização do termo bilinear também é feita com base em (BERTSIMAS et al., 2013), utilizando-se o método de outer approximation. Neste método, que corresponde a uma segunda decomposição do problema, o termo bilinear é iterativamente linearizado, sendo estabelecidos limites inferiores e superiores de forma iterativa para seus valores, até a convergência. O modelo de otimização que resulta da metodologia proposta é finalmente testado em um sistema elétrico de 24 barras utilizando a plataforma IBM ILOG CPLEX Optimization Studio, versão 12.6.0.0 (IBM, 2022). As principais contribuições deste trabalho envolvem: i) A proposição de um modelo de leilão termo-eólico multi-período em que energia e reserva são co-otimizadas, com base na otimização robusta, e em que o sistema de geração termelétrica é descrito em detalhe. Ainda que abordagens robustas tenham sido utilizadas para a solução de problemas de unit commitment, ainda não foram avaliados métodos de otimização robusta para a solução de problemas de leilão termo-eólico; ii) A adaptação da metodologia de solução descrita em (BERTSIMAS et al., 2013) para a solução do modelo de leilão proposto; iii) A comparação do modelo proposto com os chamados modelos de ajuste de reserva, em que os níveis determinísticos de reserva são fixados posteriormente ao despacho de geração, utilizado-se regras do tipo ad-hoc e iv) A proposição de um modelo de simulação das decisões calculadas tanto pelo modelo proposto quanto pelo modelo de ajuste de reservas. Este modelo tem como objetivo simular situações reais, em que níveis aleatórios são estabelecidos para a geração eólica. Para avaliação dos resultados, são simuladas 1000 situações reais aleatórias para ambos os modelos, permitindo uma avaliação estatística dos níveis de otimalidade e de segurança estabelecidos para cada um dos modelos. Os resultados obtidos com o modelo proposto e com o modelo de ajuste de reserva mostram que as decisões calculadas pelo modelo proposto elevam a robustez das decisões calculadas (i.e. a garantia de factibilidade do modelo) em situações reais de incertezas para 99,74%. Ou seja, em 99,74% das situações as decisões implementadas pelo modelo proposto foram capazes de manter a factibilidade de todas as restrições, mesmo quando se considera a possibilidade prática de que ocorram situações operativas fora da faixa de incerteza prevista no modelo robusto para a geração eólica. Os resultados mostram ainda que para alcançar esta robustez, a função de bem comum foi reduzida em apenas 0,85%, o que atesta um ótimo compromisso entre otimalidade e segurança para o modelo proposto. Já para o modelo de ajuste de reservas, a robustez atingiu um valor de apenas 73,05%, Capítulo 1. Introdução 5 comprovando que os modelos robustos trazem efetivamente uma maior segurança para o sistema em situações reais de aleatoriedade na geração eólica. O restante do trabalho está dividido da seguinte forma. No Capítulo 2 definem-se os principais conceitos de mercados de eletricidade. No Capítulo 3 é descrito o modelo de leilão termo-eólico proposto, em suas abordagens determinística e robusta. O Capítulo 4 apresenta alguns conceitos básicos acerca dos métodos de solução utilizados para resolução do problema. O Capítulo 5 descreve a metodologia de solução do modelo robusto proposto. Os resultados numéricos referentes as análises feitas são fornecidos no Capítulo 6 e as conclusões obtidas são apresentadas no Capítulo 7. O Apêndice A apresenta a íntegra dos dados computacionais do sistema de 24 barras utilizados para realizar os ensaios. 6 2 Mercados de Eletricidade Na sociedade moderna, o recurso utilizado para movimentar as atividades domés- ticas, industriais e serviços é a energia elétrica. Desde o início da utilização de sistemas de transmissão interconectados até as duas últimas décadas do século XX, os sistemas de energia eram operados de maneira centralizada, deixando a cargo dos operadores do sistema todas as atividades relacionadas à geração, transmissão e distribuição de energia. As primeiras ações para a criação dos mercados de eletricidade modernos foram estabelecidas com a separação das atividades de geração, transmissão e distribuição, em um estrutura de mercado que permitisse a competição entre os produtores e consumidores de energia. Nessa nova estrutura de mercado, a comercialização de eletricidade é realizada por meio de ofertas de geração e lances de consumo nos chamados leilões de eletricidade. As ofertas e lances, envolvendo blocos de quantidades e preços ofertados por cada agente, os quais são submetidos ao operador do sistema. As ofertas e lances são geralmente calculadas utilizando-se modelos de cálculo de ofertas estratégicas (CRUZ et al., 2016), (AFSHAR; GHIASVAND; BIGDELI, 2018), com base na estimação dos custos de produção, nas ações dos demais agentes no mercado, etc. Em cada continente ou área que possui um mercado de eletricidade vigente são adotadas estruturas diversas para o comércio de energia. Em geral, a maioria destas estruturas possuem características em comum. O principal ponto em comum entre todas as estruturas de mercados consiste na separação entre a comercialização da geração, transmissão, distribuição e varejo. A maior competição acontece geralmente na geração e no varejo, onde os preços de venda e compra oscilam para que haja uma combinação e, por fim, a concretização da transação. A transmissão e distribuição normalmente atuam como meio, ou seja, atuam para que a eletricidade saia de sua origem e chegue ao seu destino, possuindo custos e taxas. Mercados de eletricidade específicos são estabelecidos para a transmissão e distribuição, os quais não são foco desta dissertação de mestrado. 2.1 Organização Geral O mercado de eletricidade tem seus componentes e modos de operação bem definidos e são organizados de maneira a facilitar o comércio de energia entre empresas geradoras e consumidores. A área de estudo deste trabalho envolve o mercado de curto prazo que será descrito nas Seções 2.1.2 e 2.1.3, correspondendo à alocação de potência para o dia seguinte passando pelos mercados de equilíbrio e de reserva. Para realização do mercado de eletricidade existem agentes interessados nas partes de comercialização, operação e regulamentação conforme descrito na seção 2.1.1. Como se trata da alocação de potência de todas as unidades existentes no sistema para o dia Capítulo 2. Mercados de Eletricidade 7 seguinte, o tempo de discretização que deve ser utilizado é de 24 horas. 2.1.1 Agentes Nos mercados de energia existem agentes que participam dos processos, cada um exercendo sua função e tendo papeis importantes para obter o equilíbrio de mercado. Conforme descrito em (CONEJO; CARRIóN; MORALES, 2010), existem agentes que atuam diretamente no mercado de energia e agentes institucionais que regulam e operam o mercado. As companhias geradoras são as detentoras das unidades de produção e têm o objetivo de gerar energia para vendê-la. Essa venda pode ser feitas por meio de mercados organizados de eletricidade (coordenado pelo operador de mercado) ou diretamente, para consumidores, através de contratos bilaterais. O objetivo das companhias geradoras consiste em obter o maior lucro possível com a venda de eletricidade e de reserva nos vários mercados disponíveis. As companhias geradoras também podem comercializar sua energia nos mercado de reserva. Existem também os geradores não despacháveis, tais como fontes eólicas ou solares, os quais possuem esse nome devido à intermitência da natureza da sua fonte de energia, o que dificulta a sua programação de despacho. Os geradores não despacháveis participam do mercado de energia porém não fornecem ofertas nos leilões de energia do dia seguinte. Estes geradores atuam diretamente no equilíbrio de geração-demanda do sistema. Sempre que tais unidades são conectadas à rede, é necessário estabelecer reservas adicionais de energia, de modo que as aleatoriedades na sua geração possam ser compensadas por outras unidades, quando necessário. Assim, custos adicionais de reserva estão sempre associados a estas unidades. Os consumidores são os usuários finais da eletricidade e buscam comprar a energia nos mercados organizados ou por meio do estabelecimento de contratos bilaterais. Os consumidores geralmente têm como objetivo minimizar os custos de aquisição de seus ativos no mercado de energia (NOJAVAN et al., 2015; CAO et al., 2020). Os consumidores também podem participar do mercado de reserva, principalmente quando existem geradores não despacháveis atuando no equilíbrio de mercado. Quando os consumidores não atuam diretamente no mercado de eletricidade eles adquirem energia por meio de empresas varejistas. Os varejistas normalmente não possuem unidades de produção e devem comprar eletricidade por meio de contratos bilaterais ou no mercado. Como agentes institucionais existem o operador de mercado, operador independente do sistema e o regulador de mercado, cada um com suas atribuições. O Operador de Mercado (OM) é uma entidade, que pode ou não ter fins lucrativos, que tem a função de gerir economicamente todos os mercados de eletricidade, estabelecendo as regras e determinando os preços e quantidades de energia a serem comercializados. No Brasil, este papel é desempenhado pela Câmara de Comercialização de Energia (CCEE). Capítulo 2. Mercados de Eletricidade 8 O Operador Independente do Sistema (OIS) é uma entidade sem fins lucrativos que tem a responsabilidade de gerir tecnicamente o sistema de potência associado ao mercado, fornecendo acesso igualitário à rede a todos os consumidores, varejistas e geradores. O OIS gerencia as reservas, regulamenta os mercados e auxilia o operador de mercado a encontrar o equilíbrio associado a todas as ofertas/lances de compra e venda, feitos pelos participantes dos mercados nos leilões de energia. No Brasil, este papel é desempenhado pelo Operador Nacional do Sistema (ONS). O regulador de mercado é uma entidade que tem por objetivo zelar pelo mercado e garantir seu funcionamento competitivo, promovendo e fazendo cumprir regulamentos pré estabelecidos. No Brasil, este papel é desempenhado pela Agência Nacional de Energia Elétrica (ANEEL). 2.1.2 Mercados de Curto Prazo O pool é o ambiente de mercados onde a energia é negociada no curto prazo. O pool compreende basicamente três estruturas de mercados: o mercado do dia seguinte, vários mercados de ajuste ou intra-diários e o mercado de equilíbrio, também denominado de mercado em tempo real. Em todas as estruturas de mercado do pool, geradores, varejistas e grandes consumidores oferecem lances/ofertas para compra/venda de energia em diferentes períodos do dia de operação. Após o fechamento destes mercados, os agentes fazem a retirada ou entrega de eletricidade da rede, de acordo com os valores calculados pelos algoritmos de leilão de cada mercado. Os algoritmos de leilão calculam as quantidades que cada gerador/consumidor devem ser despachados no leilão bem como os preços de equilíbrio em cada período. Os leilões são estruturados de modo a privilegiar os geradores que estão dispostos a vender sua energia a preços mais baixos e os consumidores que estão dispostos a comprar a energia a preços mais altos. Esses algoritmos devem ainda levar em conta as restrições operativas e de segurança do sistema. Algoritmos específicos são utilizados em cada estrutura de sub-mercado do pool. A Figura 2.1 exemplifica como são dispostas as transações no mercado pool, mos- trando seus agentes atuantes e a resultante de todo o processo, ou seja, a quantidade de energia despachada e o preço de energia do sistema, além dos despachos de cada unidade geradora e cada consumidor, calculados pelos algoritmos de leilão em cada sub-mercado do pool. Capítulo 2. Mercados de Eletricidade 9 Figura 2.1 – Mercado de curto prazo. Geradores Consumidores Quantidade e preço de energia Mercado de curto prazo Operador de mercado Geradores não- despacháveis Varejistas Fonte: autoria própria. Os interessados nas negociações de energia no pool devem enviar seus lances/ofertas de compra/venda de acordo com o seu desejo, sendo que cada um desses lances/ofertas são formatados como um conjunto de blocos de preço e quantidade, fazendo com que seja de conhecimento de todos os envolvidos a quantidade de energia e o preço que o participante está disposto a negociar a energia. A partir das ofertas de venda de energia em cada período, é possível para o operador do sistema construir a curva de geração agregada para cada período. Por outro lado, a partir dos lances de compra em cada período, o operador pode construir a curva de demanda agregada para cada período. O ponto de intersecção das curvas de geração e demanda agregadas em cada período, em que ocorre o equilíbrio de geração-demanda, está associado ao preço de energia neste período (λ∗), e à potência total efetivamente despachada no período (P ∗), tanto para a geração quanto para a carga, conforme mostrado na Figura 2.2. Na operação prática do mercado, não há necessidade de levantar as curvas de geração e demanda agregadas, uma vez que a interseção entre estas curvas pode ser diretamente obtida por meio de um modelo de leilão, no qual se adota a função objetivo de bem comum (do inglês, social welfare), a qual será descrita em detalhes na formulação do modelo de leilão proposto neste trabalho. Capítulo 2. Mercados de Eletricidade 10 Figura 2.2 – Equilíbrio de mercado.  $ / MW  P MW Geração agregada Demanda agregada *P Equilíbrio * Fonte: autoria própria. Além da preocupação de balanço de potência entre geração e demanda, os modelos de leilão devem levar em conta também uma série de restrições relacionadas à operação dos sistemas de geração e transmissão, sem as quais, os despachos e preços calculados podem se tornar infactíveis na operação prática. Quando a rede de transmissão e as demais restrições operativas são desconsideradas no processo de compensação de mercado realizado pelo modelo de leilão, a interseção entre a curva de geração e demanda agregada define um preço da energia único para o sistema, o qual se aplica a todos os participantes do mercado. Nesse caso, são aceitas as ofertas de venda que não sejam superiores a este valor e os lances de compra que não sejam inferiores a ele, determinando o cronograma para o dia seguinte. Quando a rede de transmissão e as demais restrições operativas são efetivamente consideradas no procedimento de compensação de mercado, os preços da energia ficam associados a cada barra do sistema. Os preços de equilíbrio são efetivamente calculados como a variável dual associada às restrições de atendimento de demanda em cada barra. Assim, nestes caso, temos não um único preço para a energia em cada período, mas preços nodais em cada período. Esses valores de preços de equilíbrio podem se diferenciar consideravelmente se houver congestionamentos na rede e em função das perdas nas linhas de transmissão. 2.1.3 Mercados de Reserva Nos mercados de eletricidade a principal commodity comercializada é a energia, porém quando se trata de um mercado com energias renováveis e com aleatoriedades, é necessária a existência de um mercado de reserva que tem como objetivo alocar uma energia de backup no caso de alguma intermitência ou mudança repentina de geração ou demanda. O mercado de reserva pode ser fechado em conjunto com o mercado de curto Capítulo 2. Mercados de Eletricidade 11 prazo, sendo que geradores e consumidores podem fornecer estas reservas. Para os geradores existem três tipos de reserva, a reserva up, a down e a non- spinning. A reserva up tem como objetivo suprir uma geração superior àquela já negociada no mercado de energia. Assim, para os geradores que estão conectados à rede, a reserva corresponde à quantidade que sobra da subtração entre a capacidade do gerador e a potência que já foi efetivamente negociada no mercado de energia de curto prazo. A reserva down dos geradores tem como objetivo a diminuição da geração (em função de uma redução de carga, por exemplo), podendo ir até o desligamento da máquina. Já a reserva non-spinning corresponde a uma reserva de energia comercializada pelos geradores que se encontram desligados. Nesse caso, quando necessário, é possível ligar um novo gerador de modo a suprir algum aumento imprevisto de carga. Todas as reservas dos geradores possuem preços e quantidades de venda ofertados pelos geradores, sendo que estes agentes recebem o pagamento pelas reservas efetivamente comercializadas, mesmo que não seja necessário utilizá-la na operação em tempo real. Para os consumidores existem dois tipos básicos de reserva, a reserva up e a down. A reserva up corresponde a um decréscimo no consumo de energia, de modo que a geração do sistema precise ser aumentada, enquanto que a down corresponde a um aumento no consumo de energia, de modo que a geração do sistema precise ser reduzida. Esses valores de acréscimo e decréscimo são estabelecidos excluindo-se os valores de consumo já acordados no mercado de energia de curto prazo. Normalmente, as reservas de consumidor podem não ser necessárias na prática, mas existem em caso de alguma eventualidade. Figura 2.3 – Mercados de reserva. Geradores Consumidores Tipo e quantidade de reserva para geradores e consumidores Mercado de reserva Operador independente do sistema Fonte: autoria própria. A Figura 2.3 descreve um diagrama esquemático do funcionamento do mercado de reserva, em que os geradores e consumidores fornecem as ofertas e lances para as reservas e o operador independente do sistema atua no mercado de reserva de modo a ajustar o tipo e quantidade de reserva para cada um dos participantes, com base nestas ofertas e lances fornecidos. Capítulo 2. Mercados de Eletricidade 12 2.2 Impacto das Energias Renováveis Para as fontes de energia renováveis, o custo marginal de operação é geralmente muito baixo, fazendo com que esse tipo de geração seja programada antes dos produtores de energia convencionais, influenciando diretamente o preço de mercado (MORALES et al., 2014). Como a energia renovável pode variar no decorrer do tempo, a curva de oferta agregada do sistema (sale, no gráfico) é deslocada para esquerda quando existe baixa produção das renováveis, aumentando o preço de equilíbrio do sistema; ou para direita, no caso de uma alta produção de renováveis, reduzindo o preço de equilíbrio do sistema, conforme mostrado na Figura 2.4. Nota-se ainda que para situações de alta produção de renováveis, a geração programada aumenta juntamente com o consumo enquanto que o preço de mercado reduz, uma vez que a curva de consumo (purchase, no gráfico) permanece a mesma. Figura 2.4 – Equilíbrio de mercado com energias renováveis. 1.2 Electricity Markets 5 Fig. 1.1 The merit-order effect and the impact of renewables on the clearing price in an electricity exchange 100 200 300 400 500 10 20 30 40 50 60 70 80 Energy (MWh) P ric e (€ /M W h) sale renewable power purchase Fig. 1.2 Day-ahead electricity prices registered in the Spanish area of the Iberian Electricity Market on March 12, 2013 0 5 10 15 20 25 0 20 40 60 80 100 Hour eu ro /M W h gate closure approaches real-time, as well as for an efficient use of the resources participating in these markets. In particular, the balancing market is of special importance to renewable power producers, as it allows them to adjust their contracts so that they match their actual output. Consequently, as the penetration of stochastic production in the electricity market grows, the share of balancing costs in the total system operation costs increases. This increase may become critical if the balancing market is not provided with enough flexible and competitive generation capacity able to cope with uncertainties during the real-time operation of the power system in an economical manner. To clarify this effect, consider the series of illustrations in Fig. 1.3, starting from the top-left drawing and finishing with the bottom-left one. In this series, the black plot represents the aggregated power supply curve of the system. This curve is built by collecting, one day in advance of the physical energy delivery, selling offers from producers, and sorting them out based on a merit-order criterion. Similarly, the grey plot is the aggregated demand curve, which is here represented by a vertical line on the assumption that such a demand is inelastic. Following a traditional market approach, the intercept between the aggregated power supply and demand curves leads to the day-ahead market price �D (Illustration 1). In principle, if all the market participants were completely flexible, these two curves Fonte: (MORALES et al., 2014). Dado que a natureza das energias renováveis é incerta, como no caso das eólicas, em que as velocidades dos ventos podem variar de forma aleatória, é necessário alocar uma quantidade de potência de reserva advinda das unidades termelétricas ou de outra fonte de geração não intermitente. Essa energia de reserva alocada é utilizada de forma preventiva, para situações em que aconteça uma queda de geração de origem renovável, de modo que a reserva possa suprir essa falta de potência. Quanto maior o montante associado ao despacho de energia renovável, maior o montante de potência de reserva associada que deve ser contratada, o que implica em custos adicionais para o sistema, os quais devem ser pagos por todos os agentes envolvidos. Assim sendo, a energia de reserva possui também seus custos associados, os quais também impactam no processo de tomada de decisão de programação da geração do sistema. Desse modo, além de estabelecer o equilíbrio de mercado entre geração e consumo em cada período, é importante que os modelos de leilão levem em consideração também os custos associados à alocação dos montantes de energia de reserva em cada período, os Capítulo 2. Mercados de Eletricidade 13 quais estão diretamente relacionados com a quantidade de energias renováveis contratadas no sistema. 14 3 Modelo de Leilão Termo-Eólico para Tratamento de Incertezas Neste capítulo, o modelo de leilão termo-eólico proposto é descrito em detalhes. Antes, porém, descreve-se um modelo de leilão determinístico, o qual tem sido comumente utilizado na literatura para o tratamento das incertezas associadas à energia eólica, que despreza as incertezas neste tipo de geração. No modelo determinístico, assume-se que a geração eólica esperada (determinística) é despachada, e as gerações das demais fontes são calculadas de forma a suprir a demanda restante. Para a descrição detalhada dos modelos, na Seção 3.1, descreve-se a nomenclatura utilizada. Na Seção 3.2, descreve-se o modelo de leilão determinístico, em que as incertezas associadas à geração eólica são desprezadas, e adota-se um valor esperado fixo para essa geração. Na Seção 3.3, descreve-se uma abordagem de ajustes de reservas, a qual tem sido tradicionalmente adotada no setor elétrico de vários países para o estabelecimento de reservas de geração. Na abordagem de ajuste de reservas, utiliza-se a abordagem determinística para o despacho de geração do sistema, considerando-se a geração eólica esperada (fixa), e estabelece-se alguma regra do tipo ad-hoc para estipular um valor de reserva que se considera adequado para suprir as variações do despacho de geração, causadas pelas intermitências na geração eólica. Na Seção 3.4, o modelo robusto proposto para o tratamento das incertezas associadas à geração eólica é descrito. Neste modelo, busca-se calcular um despacho de geração que esteja imunizado contra qualquer situação operativa adversa que ocorra dentro de uma região denominada de conjunto de incerteza. Os modelos de leilão descritos neste capítulo representam de forma detalhada as restrições associadas à geração termelétrica (i.e. restrições de rampa de partida, parada, subida e descida e mínimo tempo de operação e desligamento), reservas associadas à geração e à carga, e restrições da rede de transmissão por meio de equações de fluxo de potência linearizadas, com perdas desprezíveis. 3.1 Nomenclatura 3.1.1 Conjuntos BT Blocos de oferta de energia submetidos pelas unidades termelétricas; BC Blocos de oferta de energia submetidos pelos consumidores; C Consumidores; CC n Consumidores conectados à barra n; Capítulo 3. Modelo de Leilão Termo-Eólico para Tratamento de Incertezas 15 E Unidades geradoras eólicas; GE n Unidades geradoras eólicas conectadas à barra n; GT n Unidades geradoras termelétricas conectadas à barra n; I Unidades geradoras termelétricas; N Barras do sistema de transmissão; NN n Barras do sistema de transmissão vizinhas à barra n; T Períodos do leilão. 3.1.2 Parâmetros λR U it Oferta de preço de reserva up submetido pela unidade termelétrica i no período t[$/MW ]; λR D it Oferta de preço de reserva down submetido pela unidade termelétrica i no período t [$/MW ]; λR NS it Oferta de preço de reserva não girante (do inglês, non-spinning) submetido pela unidade termelétrica i no período t [$/MW ]; λTitb Oferta de preço de energia submetido pela unidade termelétrica i no período t, bloco b [$/MW ]; γCctb Oferta de preço de energia submetido pelo consumidor c no período t, bloco b [$/MW ]; γR U ct Oferta de preço de reserva up do consumidor c no período t; γR D ct Oferta de preço de reserva down do consumidor c no período t; ∆t Meta de incerteza do problema no período t; Bnm Susceptância série da linha n−m; CFIX i Custo fixo da unidade termelétrica i; CSU i Custo de partida da unidade termelétrica i; CSD i Custo de parada da unidade termelétrica i; Fmax nm Limite de fluxo de potência na linha n−m; E C ctb Oferta de quantidade de energia submetido pelo consumidor c no período t, bloco b [MW ]; Capítulo 3. Modelo de Leilão Termo-Eólico para Tratamento de Incertezas 16 E T itb Oferta de quantidade de energia submetido pela unidade termelétrica i no período t, bloco b [MW ]; NE Número de unidades geradoras eólicas; PCSmax ct Potência máxima cortada para o consumidor c no período t; P E et Potência de saída média da unidade eólica e no período t; Rsys t Valor da reserva do sistema para o período t; R0 t Valor base de reserva do sistema para o período t; V LOL ct Valor da penalidade do corte de carga do sistema para a carga c no período t; V LOR t Valor da penalidade associada com a folga do balanço de reservas no período t; V GER t Valor da penalidade associada com a folga do balanço de potência no período t; UTi Número de períodos que o gerador i deve permanecer ligado após dar partida; DTi Número de períodos que o gerador i deve permanecer desligado após realizar uma parada; Gi Número de períodos que o gerador i deve ficar ligado no início do horizonte de análise; Fi Número de períodos que o gerador i deve ficar desligado no início do horizonte de análise. 3.1.3 Variáveis θnt Ângulo da tensão na barra n no período t; pEet Potência de saída da unidade eólica e no período t; p̂Eet Desvio da geração de potência eólica nominal da unidade eólica e no período t; pTit Potência de saída da unidade termelétrica i no período t; pCct Potência de saída do consumidor c no período t; pCSct Corte de potência do consumidor c no período t; eTitb Potência de saída da unidade termelétrica i no período t, bloco b; eCctb Potência consumida pelo consumidor c no período t, bloco b; rUit Reserva de potência up da unidade termelétrica i no período t; Capítulo 3. Modelo de Leilão Termo-Eólico para Tratamento de Incertezas 17 rDit Reserva de potência down da unidade termelétrica i no período t; rNSit Reserva de potência não girante da unidade termelétrica i no período t; sUct Reserva de potência up do consumidor c no período t; sDct Reserva de potência down do consumidor c no período t; εsyst Variável de folga associada com o balanço de reservas do sistema no período t; εgernt Variável de folga associada com o balanço de potência na barra n no período t; uit Estado (liga/desliga) da unidade termelétrica i no período t; zit Estado que representa se a unidade termelétrica i ligou no início do período t; wit Estado que representa se a unidade termelétrica i desligou no início do período t. x Vetor associado às variáveis binárias (unit commitment). y Vetor associado às variáveis reais do problema original (despacho e reservas). 3.2 Modelo Determinístico O modelo determinístico para o problema de leilão busca a minimização dos custos de partida, parada e custos fixos de operação, além da maximização da função do bem comum, minimização de todos os tipos de reserva de geração, demanda e minimização dos cortes de carga. São também inseridos na função objetivo dois termos de penalização, um associado à factibilidade das reservas totais do sistema e outro associado à factibilidade do atendimento de demanda nas barras do sistema. A otimização destes critérios está sujeita às restrições econômicas, limites na geração, consumo e no corte de carga, limites impostos pelas restrições de reserva para os geradores e consumidores, definição dos custos de partida e parada e limites na transmissão. Neste modelo, as incertezas associadas à geração eólica são desprezadas, adotando-se para esta geração o valor esperado fixo associado ao conjunto de dados de geração eólica. Assim, o despacho neste modelo envolve somente a geração termelétrica. O modelo proposto é descrito de (3.1) a (3.26), a seguir: Min ∑ i∈I ∑ t∈T zitC SU i + ∑ i∈I ∑ t∈T witC SD i + ∑ i∈I ∑ t∈T uitC FIX i + ∑ i∈I ∑ t∈T ∑ b∈BT λTitbe T itb − ∑ c∈C ∑ t∈T ∑ b∈BC γCctbe C ctb + (∑ i∈I ∑ t∈T λR U it r U it + ∑ i∈I ∑ t∈T λR D it r D it + ∑ i∈I ∑ t∈T λR NS it rNSit ) + (∑ c∈C ∑ t∈T γR U ct s U ct + ∑ c∈C ∑ t∈T γR D ct s D ct ) + ∑ c∈C ∑ t∈T V LOL ct pCSct + ∑ t∈T V LOR t εsyst + ∑ n∈N ∑ t∈T V GER t εgernt (3.1) Capítulo 3. Modelo de Leilão Termo-Eólico para Tratamento de Incertezas 18 sujeito a: 0 6 eTitb 6 uitE T itb, ∀i ∈ I, ∀t ∈ T, ∀b ∈ BT (3.2) eTitb = uitE T itb; b = 1, ∀i ∈ I, ∀t ∈ T (3.3) 0 6 eCctb 6 E C ctb, ∀c ∈ C, ∀t ∈ T, ∀b ∈ BC (3.4) pTit = ∑ b∈BT eTitb, ∀i ∈ I, ∀t ∈ T (3.5) pCct = ∑ b∈BC eCctb, ∀c ∈ C, ∀t ∈ T (3.6) 0 6 pCSct 6 PCSmax ct , ∀c ∈ C, ∀t ∈ T (3.7) 0 6 rUit 6 ∑ b∈BT ( uitE T itb − eTitb ) , ∀i ∈ I, ∀t ∈ T (3.8) 0 6 rNSit 6 (1− uit) ∑ b∈BT E T itb, ∀i ∈ I, ∀t ∈ T (3.9) 0 6 rDit 6 ∑ b∈BT eTitb, ∀i ∈ I, ∀t ∈ T (3.10) 0 6 sUct 6 ∑ b∈BC eCctb, ∀c ∈ C, ∀t ∈ T (3.11) 0 6 sDct 6 ∑ b∈BC ( E C ctb − eCctb ) , ∀c ∈ C, ∀t ∈ T (3.12) ∑ i∈I ( rUit + rNSit − rDit ) + ∑ c∈C ( sUic − sDic ) + εsyst > Rsys t , ∀t ∈ T (3.13) εsyst > 0, ∀t ∈ T (3.14) ∑ i∈GT n pTit + ∑ e∈GE n P E et − ∑ c∈CC n ( pCct − pCSct ) − ∑ m∈NN n Bnm (θnt − θmt) + εgernt = 0, ∀n ∈ N, ∀t ∈ T (3.15) εgernt ≥ 0, ∀n ∈ N, ∀t ∈ T (3.16) −Fmax nm 6 Bnm (θnt − θmt) 6 Fmax nm , ∀n ∈ N, ∀m ∈ NN n , ∀t ∈ T (3.17) Capítulo 3. Modelo de Leilão Termo-Eólico para Tratamento de Incertezas 19 wit − zit = uit − ui(t−1), ∀i ∈ I, ∀t ∈ T : t 6= 1 (3.18) wit + zit 6 1, ∀i ∈ I, ∀t ∈ T (3.19) Gi∑ t=1 (1− uit) = 0, ∀i ∈ I (3.20) t+UTi−1∑ l=t uil > UTizit, ∀i ∈ I, ∀t = Gi + 1...NT − UTi + 1 (3.21) NT∑ l=t (uil − zit) > 0, ∀i ∈ I, ∀t = NT − UTi + 2..NT (3.22) Fi∑ t=1 uit = 0, ∀i ∈ I (3.23) t+DTi−1∑ l=t (1− uil) > DTiwit, ∀i ∈ I, ∀t = Fi + 1...NT −DTi + 1 (3.24) NT∑ l=t (1− uit − wit) > 0, ∀i ∈ I, ∀t = NT −DTi + 2..NT (3.25) uit,zit,wit binárias (3.26) em que: Rsys t = R0 t + ∑ e∈E p̂Eet ( 1− ∆t NE ) . É importante destacar que para uma situação mais geral, em que a potência eólica é tratada como uma variável sujeita a incerteza por meio da otimização robusta, é necessário adotar um valor variável, diferente do valor médio pEet adotado no problema de otimização (3.1)–(3.26). Na função objetivo, cada termo está relacionado a objetivos específicos do modelo de leilão. Os três primeiros termos da função objetivo referem-se aos custos de partida, parada e custos fixos de operação das unidades termelétricas. Todos estes custos estão associados aos estados ligado/desligado das unidades de geração modelados por meio das variáveis binárias u (estado ligado/desligado), z (partida) e w (parada). O quarto e quinto termos da função objetivo representam a função de bem comum com sinal inverso (de modo a buscar a maximização desta função). Esta função é fundamental para o leilão, pois garante que as melhores ofertas/lances de geração/consumo de energia sejam selecionadas no leilão. A qualidade das ofertas/lances depende dos preços ofertados pelos geradores (λTitb) e consumidores (γCctb), o que deve definir as quantidades que serão efetivamente Capítulo 3. Modelo de Leilão Termo-Eólico para Tratamento de Incertezas 20 despachadas para os geradores (eTitb) e consumidores (eCctb). Os três termos seguintes na função objetivo dizem respeito à minimização das reservas up, down e non-spinning do gerador e up, down do consumidor. Neste caso, os valores de preços ofertados para cada uma dessas reservas (i.e. λRU it , λ RD it , λ RNS it para as reservas up, down e non-spinning dos geradores e γRU it e γRD it para as reservas up e down dos consumidores) influi nos valores de reserva efetivamente despachados (i.e. rUit , rDit e rNSit para os geradores e sUit e sDit para os consumidores). O termo seguinte da função objetivo refere-se a penalização para o corte de carga pCS do sistema. Para que os cortes de carga sejam minimizados são atribuídos valores altos para a constante V LOL ct (geralmente valores acima de 1000 são adotados). Finalmente, os dois últimos termos na função objetivo são utilizados para analisar a factibilidade das restrições (3.13), (3.14), (3.15) e (3.16). Para que essas restrições sejam atendidas quando possível, são atribuídos valores de penalidades elevados para V LOR t e V GER t , para que os valores de folga de reserva e de atendimento de demanda, dados por (εsys) e (εger), respectivamente, sejam nulos na solução ótima. Cada restrição do modelo apresentado possui uma finalidade e representa matema- ticamente uma condição existente no modelo real de leilão de eletricidade. O conjunto de restrições (3.2) - (3.4) representa os limites associados aos tamanhos dos blocos alocados para os geradores e consumidores. As restrições (3.2) definem a faixa de alocação de cada bloco, para cada unidade e período, que vai de zero até o tamanho do bloco ofertado. O valor de geração mínimo atribuída para cada gerador, caso ele esteja ligado, corresponde ao tamanho do primeiro bloco ofertado conforme representado nas restrições (3.3). Já (3.4) define a faixa de alocação de cada bloco, para cada consumidor e período, podendo variar de zero ao tamanho de cada bloco ofertado pelos consumidores. As restrições (3.5) e (3.6) definem que as potências geradas e consumidas, respectivamente, são dadas pela soma dos blocos que foram efetivamente alocados. Em (3.7) são definidos os limites mínimos e máximos para o corte de carga, os quais devem estar na faixa de zero ao valor máximo de corte de carga pré estabelecido para cada consumidor em cada período. As restrições associadas às reservas do sistema são definidas em (3.8) - (3.13). Para os geradores, a restrição (3.8) define a faixa de reserva up, que vai de zero à capacidade máxima de geração ofertada, descontada a potência que já foi efetivamente alocada para cada unidade em cada período. A restrição (3.9) define a faixa para a reserva non-spinning que vai de zero até capacidade máxima de geração ofertada por cada gerador, desde que este esteja desligado (somente geradores desligados podem oferecer reserva do tipo non-spinning). A restrição (3.10), define a faixa para a reserva down, que vai de zero até o valor efetivamente alocado no despacho, visto que esta é uma reserva que busca a redução do uso de energia. Para as reservas associadas aos consumidores, a restrição (3.11) define a faixa de reserva up que vai de zero até o valor de potência alocada para o consumidor. Em (3.12) são definidos os limites de reserva down para o consumidor, na faixa que vai Capítulo 3. Modelo de Leilão Termo-Eólico para Tratamento de Incertezas 21 de zero até o valor que ainda não foi alocado no despacho regular, ou seja, a capacidade máxima de consumo ofertada descontada a potência já alocada ao consumidor. A restrição (3.13) estabelece um limite mínimo para a reserva total do sistema, de modo que a soma de todos os tipos de reserva associadas aos geradores e consumidores, juntamente com a variável de folga εsys acrescentada para garantir a factibilidade desta restrição, deve ser maior que a reserva do sistema Rsys t . Deseja-se que os valores da variável εsys sejam nulos na solução ótima, o que garante que a restrição (3.13) seja factível sem a necessidade de folgas. A restrição (3.15) define o balanço de potência ativa em cada barra do sistema de transmissão. Nesta restrição, garante-se que o somatório de todos os tipos de geração em cada barra menos a potência demandada em cada barra deve igualar os fluxos de potências que saem de cada barra. Adota-se também nesta restrição a variável de folga εger cujo objetivo é garantir a factibilidade da restrição. Também neste caso, deseja-se que os valores de εger sejam nulos na solução ótima. Na restrição (3.17) são definidos os limites de fluxo de potência nas linhas da rede de transmissão. As restrições (3.18), (3.19) e (3.26) garantem uma operação lógica para as situações de liga/desliga das unidades, ou seja, garantem que não haja conflito lógico nos estados de liga e desliga das máquinas. As restrições (3.20) – (3.22) definem o mínimo tempo em que as máquinas deverão permanecer ligadas após uma partida, dado um tempo UT pré definido. Analogamente, para o mínimo tempo desligado são definidas as restrições (3.23) – (3.25). Neste caso, o mínimo tempo desligado é dado pelo parâmetro DT , pré definido para cada máquina. As restrições de mínimo tempo ligado e desligado são baseadas na formulação, descrita em (ARROYO; CONEJO, 2002). Para a definição de Rsys t são utilizados valores relacionados com um valor mínimo base para a reserva R0 t , o desvio da geração de potência eólica nominal p̂Eet, a meta de incerteza ∆t do problema e o número de unidades eólicas NE. O comportamento da reserva é de uma reta descendente, sendo que quanto maior o ∆t do problema, menor o valor mínimo necessário de alocação de potência, limitado ao valor do número de unidades eólicas existentes, conforme Figura 3.1. Capítulo 3. Modelo de Leilão Termo-Eólico para Tratamento de Incertezas 22 Figura 3.1 – Reserva do sistema. Fonte: autoria própria. A seguir, descreve-se a abordagem tradicional comumente utilizada no setor elétrico de alguns países para o estabelecimento de reservas de geração que utiliza a formulação determinística descrita nesta seção. 3.3 Abordagem Tradicional A abordagem tradicionalmente usada para alocação de reservas do sistema, despreza o caráter de incerteza da geração eólica, estabelecendo um valor esperado fixo para esta geração. Assim, esta abordagem utiliza o modelo de leilão determinístico descrito na Seção 3.2 para alocação das reservas, e estabelece uma reserva total para o sistema, dada por Rsys, que deve ser respeitada. Como a potência eólica é fixada em seu valor esperado (médio), este tipo de abordagem não retrata de maneira condizente as situações aleatórias que podem ocorrer no leilão de curto prazo, desprezando as aleatoriedades presentes nos fluxos dos ventos que impactam diretamente a geração. Outra deficiência desta abordagem consiste no uso de uma reserva previamente fixada, que por ser constante, não tem seu valor alterado caso seja alterado o valor da potência eólica. Em situações práticas, espera-se que o valor da reserva do sistema aumente conforme ocorra o aumento da inserção de potência eólica no sistema, visto que podem haver intermitências não planejadas e maiores quantidades de reserva podem ser requisitadas. Assim, a abordagem tradicional tem uma formulação mais simplista para o problema, não havendo a necessidade de aplicação de métodos matemáticos elaborados para a resolução e correção de não linearidades que possam surgir, visto que o parâmetro da potência eólica é tratado como uma constante. Para que o modelo tenha uma maior representatividade e seja imune a aleatoriedades na potência eólica que possam existir, é necessário tratar a potência eólica como uma variável e aplicar técnicas que tornem o modelo imunizado contra estas aleatoriedades. Uma alternativa que tem sido investigada Capítulo 3. Modelo de Leilão Termo-Eólico para Tratamento de Incertezas 23 para o tratamento de problema de otimização com incertezas são os modelos de otimização robustos, os quais serão discutidos nas seções seguintes. Antes porém, para possibilitar comparações justas entre a abordagem tradicional e a abordagem robusta, é importante ajustar a modelagem da reserva do sistema de modo que ela acompanhe o valor da meta de incerteza ∆t, a qual será detalhada na seção seguinte, conforme mostrado em (3.27): Rsys t = R0 t + ∑ e∈E p̂Eet ( 1− ∆aux t NE ) , (3.27) em que: ∆aux t = ∆t, se houver variação de ∆t. Em (3.27) a reserva é fixada a partir de um valor inicial R0 t somado a um termo que depende da meta de incerteza ∆aux t . Este ajuste na meta de reserva do sistema, dado como uma função da meta de incerteza, possibilita que a meta estabelecida pela abordagem tradicional acompanhe a meta variável utilizada na abordagem robusta, que será descrita na seção a seguir. A criação da variável auxiliar ∆aux t se dá pela necessidade de acompanhamento da variação da reserva de acordo com o modelo robusto, porém como se trata de um modelo determinístico, este não possui a meta de incerteza em sua formulação. Assim, a definição dada em (3.27) permite comparar duas abordagem distintas, porém com as mesmas reservas para o sistema. 3.4 Modelo Robusto A otimização robusta tem sido uma técnica utilizada para o tratamento das incertezas em problemas de otimização. Com relação à otimização estocástica, a otimização robusta possui algumas vantagens (BERTSIMAS et al., 2013): i) ela requer apenas informações moderadas sobre o conjunto de dados, tais como a média e a faixa dos dados incertos a serem tratados; ii) a técnica é suficientemente flexível para que se possa inserir informações adicionais sobre os dados, tais como correlações com o modelo de incerteza quando estas informações estão disponíveis; iii) o modelo de otimização robusta constrói uma solução ótima que imuniza contra todas as realizações dos dados incertos dentro de um conjunto de incertezas. 3.4.1 Definindo um Conjunto de Incertezas para a Potência Eólica O conjunto de incertezas é um conceito fundamental para a otimização robusta. Diferentemente da otimização estocástica, o modelo de incerteza em um problema de otimização robusta não é uma distribuição de probabilidades, mas um conjunto com uma faixa pré estabelecida. Neste trabalho, o parâmetro de incerteza é a potência gerada pEet Capítulo 3. Modelo de Leilão Termo-Eólico para Tratamento de Incertezas 24 pela unidade eólica e, em cada período t. O conjunto de incerteza PEt está descrito em (3.28), conforme proposto por Bertsimas et al. (2013): PEt ( p̂E t ,pE t ,∆t ) := pE t ∈ RNE : ∑ e∈E ∣∣∣pEet − pEet∣∣∣ p̂Eet 6 ∆t, p E et ∈ [ pEet − p̂Eet, pEet + p̂Eet ] , ∀e ∈ E  , (3.28) em que E é o conjunto de geradores eólicos, NE é a quantidade desses geradores, pE t é o vetor de geração de potência eólica no período t, pEet é o valor médio da geração de potência da unidade eólica e no período t, p̂Eet é o desvio da geração de potência eólica nominal da unidade eólica e no período t, o intervalo [pEet − p̂Eet, pEet + p̂Eet] é a faixa da incerteza de pEet. A desigualdade em (3.28) controla o desvio total com relação aos seus valores nominais de todas as gerações no período t. O parâmetro ∆t é denominado de “meta de incerteza” e pode assumir valores de 0 até NE. Quando ∆t = 0 o conjunto de incertezas PEt = pE t é um singleton, correspondendo a um caso determinístico. Conforme ∆t aumenta, o tamanho do conjunto de incertezas PEt se expande. Isso significa que quanto maior o desvio total da injeção de potência líquida esperada, isso resulta em um unit commitment robusto com soluções mais conservadoras fazendo com que o sistema esteja protegido contra um alto grau de incerteza. Quando ∆t = NE, PEt é igual a um hipercubo definido pelos intervalos de pEet para cada unidade geradora e ∈ E, resultando em decisões mais seguras. 3.4.2 Problema Robusto A reformulação do modelo (3.1)–(3.26) como um problema robusto envolve a representação nas incertezas sobre a geração eólica pEet ao invés do seu tratamento como um valor médio constante pEet. Para isso, adota-se uma faixa de valores possíveis para esta variável dada pelo conjunto de incertezas PEt , descrito em (3.28), conforme (3.29): pEet ∈ PEt ,∀e ∈ E,∀t ∈ T. (3.29) Como a restrição (3.29) não pode ser diretamente inserida no problema de otimi- zação (3.1)–(3.26), e a otimização robusta visa que a solução esteja imunizada contra o pior caso, a teoria de otimização robusta define algumas reformulações do problema, de modo que esta restrição seja representada. Para isso, é mais simples descrever o modelo em termos dos vetores x, associado às variáveis binárias (unit commitment) e y, associado às variáveis reais do problema original (despacho), conforme (3.30) e (3.31), respectivamente: x = (uit,wit,zit, ∀i ∈ I, ∀t ∈ T ) . (3.30) Capítulo 3. Modelo de Leilão Termo-Eólico para Tratamento de Incertezas 25 y =  eTitb, ∀i ∈ I, ∀t ∈ T, ∀b ∈ BT eCctb, ∀c ∈ C, ∀t ∈ T, ∀b ∈ BC pTit, ∀i ∈ I, ∀t ∈ T pCct, p CS ct , ∀c ∈ C, ∀t ∈ T rUit , r D it , r NS it , ∀i ∈ I, ∀t ∈ T sUct, s D ct, ∀c ∈ C, ∀t ∈ T θnt, ε ger nt , ∀n ∈ N, ∀t ∈ T εsyst , ∀t ∈ T  . (3.31) Para que o modelo (3.1)–(3.26) possa ser rescrito em termos de x e y, definem-se as funções e o conjunto dados em (3.32)–(3.35), em que se destaca a dependência implícita dos valores de y em relação ao vetor de gerações eólicas pE = ( pEet, e ∈ E, t ∈ T ) : F (y) := ∑ i∈I ∑ t∈T ∑ b∈BT λTitbe T itb − ∑ c∈C ∑ t∈T ∑ b∈BC γCctbe C ctb + (∑ i∈I ∑ t∈T λR U it r U it + ∑ i∈I ∑ t∈T λR D it r D it + ∑ i∈I ∑ t∈T λR NS it rNSit ) + (∑ c∈C ∑ t∈C γR U ct s U ct + ∑ c∈C ∑ t∈T γR D ct s D ct ) + ∑ c∈C ∑ t∈T V LOL ct pCSct + ∑ t∈T V LOR t εsyst + ∑ n∈N ∑ t∈T V GER t εgernt . (3.32) Ωy := {y : as restrições (3.4)–(3.7), (3.10)–(3.17) são satisfeitas} . (3.33) Ωx := {x : as restrições (3.18) –(3.26) são satisfeitas} . (3.34) Ωx,y := {(x,y) : as restrições (3.2), (3.3), (3.8), (3.9) são satisfeitas} . (3.35) em que o conjunto Ωy engloba as restrições dependentes exclusivamente de y, ΩX as restrições exclusivamente dependentes de x e Ωx,y engloba as restrições dependentes de x e y. Por simplicidade, a relação de dependência das variáveis à direita da expressão (3.32) com relação ao vetor pE não estão explicitadas. A partir destas definições, o modelo (3.1)–(3.26), pode ser rescrito conforme (3.36), em que se destaca a restrição de balanço de potência (3.36)(d), na qual aparece a variável Capítulo 3. Modelo de Leilão Termo-Eólico para Tratamento de Incertezas 26 pEet, cuja incerteza se pretende tratar: Min x,y ∑ i∈I ∑ t∈T zitC SU i + ∑ i∈I ∑ t∈T witC SD i + ∑ i∈I ∑ t∈T uitC FIX + F (y) s.a: y ∈ Ωy (a) x ∈ Ωx (b) (x,y) ∈ Ωx,y (c)∑ i∈GT n pTit + ∑ e∈GE n pEet − ∑ c∈CC n ( pCct − pCSct ) + − ∑ m∈NN n Bnm (θnt − θmt) + εgernt = 0, ∀n ∈ N, ∀t ∈ T (d) x binárias. (e) (3.36) A otimização robusta busca uma solução que fique imune à pior solução possível dentro do conjunto de incertezas. Isto é feito utilizando-se uma estrutura Max-Min, conforme mostrado em (3.37): Min x ∑ i∈I ∑ t∈T zitC SU i + ∑ i∈I ∑ t∈T witC SD i + ∑ i∈I ∑ t∈T uitC FIX +Max pE { Min y F (y) } s.a: y ∈ Ωy (a) x ∈ Ωx (b) (x,y) ∈ Ωx,y (c)∑ i∈GT n pTit + ∑ e∈GE n pEet − ∑ c∈CC n ( pCct − pCSct ) + − ∑ m∈NN n Bnm (θnt − θmt) + εgernt = 0, ∀n ∈ N, ∀t ∈ T (d) x binárias. (e) (3.37) Neste trabalho, utiliza-se a metodologia para a solução do problema robusto descrito em (3.37) a qual é discutida no Capítulo 5. Para resolver as variáveis binárias é utilizada a decomposição de Benders, descrita na Seção 4.3 e com relação às não linearidades da função objetivo é utilizado o método de outer approximation, descrito na Seção 4.2. 27 4 Métodos de Solução Utilizados Para que o modelo de leilão termo-eólico seja resolvido é necessário adotar técnicas matemáticas e computacionais que permitam resolver adversidades existentes em decor- rência da complexidade do modelo proposto. Para a solução do modelo robusto proposto neste trabalho, foram utilizadas três técnicas de solução, que são descritas nas seções a seguir neste capítulo. A técnica de dualização, dada pela teoria da dualidade, é descrita na Seção 4.1, sendo peça importante para reformulação da estrutura Max-Min do problema robusto, de modo que esta estrutura possa ser reformulada como um problema de maximização, somente. O problema de maximização resultante é então decomposto, pelo método de decomposição de Benders, nos problemas de nível superior e inferior, sendo que o problema de nível superior é formulado como um problema de unit commitment, que determina as variáveis binárias associadas com o liga/desliga das unidades, e o problema de nível inferior corresponde a um despacho de geração. O problema de nível inferior possui em sua função objetivo uma função bilinear. Para a solução deste problema, adota-se o método de outer approximation. Os métodos citados acima, quais sejam, os métodos de reformulação dual, descrito na Seção 4.1, decomposição de Benders, descrito na Seção 4.3 e outer approximation, descrito na Seção 4.2, são detalhados neste capítulo para a solução de problemas de otimização genéricos. A aplicação destes métodos especificamente para a solução do problema de leilão robusto proposto neste trabalho é descrita no Capítulo 5. 4.1 Dualidade Dado um problema de otimização, é possível definir outro problema de otimização associado, sendo que o primeiro é denominado problema primal enquanto o segundo é denominado de problema dual. Segundo Arenales et al. (2007), observar o problema dual corresponde a analisar o problema matemático primal sob outro ponto de vista. Além da definição do problema dual fornecer subsídios para resolver questões matemáticas complexas, esta abordagem também pode ser utilizada como alternativa para resolver o problema de otimização primal original. Quando certas condições de convexidade e qualificação das restrições são satisfeitas, os problemas primal e dual possuem equivalência no que diz respeito ao valor da função objetivo no ótimo. Para situações em que tais condições não ocorrem, entretanto, pode ocorrer o chamado gap dualidade, de modo que, nestes caso, os valores ótimos das funções objetivo primal e dual podem não coincidir. Matematicamente, um problema primal genérico composto por variáveis x é definido como em (4.1), em que se destacam, entre parênteses, os multiplicadores de Lagrange (ui) Capítulo 4. Métodos de Solução Utilizados 28 e (vi) associados às restrições de igualdade e desigualdade (BAZARAA, 2013): Min x f (x) s.a : gi (x) 6 0 : (ui) para i = 1, · · · , m (a) hi (x) = 0 : (vi) para i = 1, · · · , l (b) x ∈ X. (c) (4.1) Dado o problema primal (4.1), o dual problema Lagrangiano associado é definido conforme (4.2): Max u,v θ (u,v) s.a : u > 0, (4.2) em que: θ (u,v) = inf { f (x) + m∑ i=1 uigi (x) + l∑ i=1 vihi (x) : x ∈ X } , (4.3) sendo u e v correspondentes a vetores das variáveis duais u e v. No problema (4.2) as restrições (4.1)(a) e (4.1)(b) foram incorporadas na função objetivo (4.3) utilizando os multiplicadores de Lagrange ou também chamadas variáveis duais ui e vi. Mesmo existindo várias definições acerca de problemas duais a formulação mais utilizada é a formulação dual Lagrangiana, que consiste em maximizar o maior limite inferior da função, também denominado problema dual Max-Inf. Existem alguns teoremas que regem as relações envolvendo os problemas dual e primal, todos eles descritos em (BAZARAA, 2013). De forma prática e para problemas de otimização linear, a construção de um problema dual a partir de um problema de otimização primal, pode ser mais facilmente realizada por meio de regras de construção, conforme descrito em Arenales et al. (2007) e reproduzido na Tabela 4.1. Capítulo 4. Métodos de Solução Utilizados 29 Tabela 4.1 – Regras para construção de um problema dual a partir de um problema primal (e vice-versa) para problemas de otimização lineares. Primal (dual) Dual (primal) Minimização Maximização Vetor de recursos Gradiente do objetivo Gradiente do objetivo Vetor de recursos Restrição = ≤ ≥ Variável Livre ≤ ≥ Variável ≥ ≤ Livre Restrição ≤ ≥ = Seguindo as regras da Tabela 4.1 é possível descrever qualquer problema de oti- mização linear em sua forma dual, ou ainda fazer o contrário, escrever um problema dual em sua forma primal. Se um dos problemas (primal ou dual ) corresponde a uma minimização, o outro problema (dual ou primal) deve ser escrito como um problema de maximização e vice-versa. Em um dos problemas (primal ou dual) o vetor de recursos corresponde ao gradiente do objetivo do outro problema (dual ou primal), e o gradiente do objetivo de um dos problemas (primal ou dual) corresponde ao vetor de recursos do outro problema (dual ou primal). Há também uma relação entre as variáveis no problema primal e as restrições no problema dual, e vice-versa. Assim, o tipo de cada restrição em um problema (primal ou dual) vai ditar se a respectiva variável será positiva, negativa ou livre no outro problema (dual ou primal) e vice-versa. A Tabela 4.1 sintetiza todas essas regras construtivas sendo utilizada para o desenvolvimento dos problemas duais utilizados nesta dissertação, conforme detalhado no Capítulo 5. 4.2 Método de Outer Approximation O método de outer approximation é uma abordagem utilizada para resolver pro- blemas de programação não linear inteira-mista utilizando princípios de decomposição, aproximação externa e relaxação. Conceitualmente, algoritmos baseados em aproximação externa descrevem a região de solução de um problema como a interseção de uma coleção infinita de conjuntos, possibilitando substituir um programa não linear por um de pro- gramação linear inteira-mista (DURAN; GROSSMANN, 1986; FLETCHER; LEYFFER, 1994; VARVAREZOS; GROSSMANN; BIEGLER, 1992). Para a descrição do método, seja um problema de programação não linear inteira- mista conforme descrito em (4.4), em que as funções f(y) e g(y) são não lineares, porém Capítulo 4. Métodos de Solução Utilizados 30 convexas e diferenciáveis: Min x,y z = cTx+ f(y) s.a. g(y) +Bx ≤ 0 Ax ≤ a y ∈ Y, x ∈ {0,1}nx (4.4) em que y ∈ Rny são as variáveis contínuas, Y ⊂ Rny, x ∈ {0,1}nx, são as variáveis inteiras, f : Rny → R, g : Rny → Rm. Os parâmetros A, B e a, c são respectivamente matrizes e vetores constantes de dimensões conformáveis com as variáveis do problema. O primeiro conjunto de restrições do problema envolve variáveis contínuas e binárias, enquanto o segundo conjunto de restrições envolve somente as variáveis binárias, sendo linear em x. O método de outer approximation, proposto por Duran e Grossmann (1986), se inicia com a definição do problema (4.5), obtido ao fixar as variáveis binárias de (4.4) em xk. O problema (4.5) corresponde a uma projeção do problema original em y. Problema U  Min y z(xk) = cTxk + f(y) s.a. g(y) +Bxk 6 0 y ∈ Y. (4.5) É possível usar o problema (4.6) para verificar se o problema U dado em (4.5) é infactível. Se u ≤ 0 na solução do problema (4.6), o modelo (4.5) é factível, por outro lado, se u > 0 na solução de (4.6), o modelo (4.5) é infactível: Min y,u u s.a. g(y) +Bxk ≤ u y ∈ Y,u ∈ R. (4.6) O fato de xk estar fixo no problema (4.5) reduz o espaço de otimização deste problema, em relação ao problema (4.4) original. Como todas as demais restrições são idênticas em ambos os problemas de otimização, a solução ótima obtida pelo problema (4.5) corresponde a um caso particular do problema original (4.4). Assim, o valor ótimo da função objetivo no problema (4.5) não pode ser menor do que o valor ótimo da função objetivo do problema (4.4), de modo que pode-se utilizar a solução ótima de (4.5) como um limite superior para o problema (4.4). A ideia principal do método de outer approximation consiste em desenvolver uma representação linear equivalente para o problema de programação não linear inteira-mista Capítulo 4. Métodos de Solução Utilizados 31 (4.4) e aplicar a relaxação. Inicialmente, para a descrição do problema mestre, é necessário reformular o problema (4.4) por meio do problema equivalente (4.7): Min x,y,α α s.a. α ≥ cTx+ f(y) g(y) +Bx ≤ 0 Ax ≤ a y ∈ Y, x ∈ {0,1}nx α ∈ R. (4.7) Com base na solução do problema U que define o limite superior, dado em (4.5), é possível obter, por relaxação, o problema mestre, que consiste em um problema de programação linear inteira-mista, conforme (4.8), em que as funções não lineares f(y) e g(y) são aproximadas por suas respectivas séries de Taylor de primeira ordem no entorno do ponto fixo yk: Mestre  Min x,y,α α s.a. α > cTx+ f(yk) +∇f(yk)T (y − yk) g(yk) +∇g(yk)T (y − yk) +Bx 6 0 Ax 6 a y ∈ Y, x ∈ {0,1}nx α ∈ R, (4.8) em que ∇f(yk)T e ∇g(yk)T são os vetores gradientes associadas às funções f(y) e g(y), respectivamente. O problema mestre (4.8) é um problema de programação linear inteira-mista, e corresponde à relaxação do problema original (4.4), de modo que o valor ótimo da sua função objetivo, pode então ser utilizada como limite inferior do método. Comparando o limite superior obtido a partir de (4.5) e o limite inferior (4.8), dois casos podem ocorrer: i) Caso estes valores sejam iguais, a solução final foi encontrada; ii) Caso estes valores forem diferentes, atualiza-se xk como o novo valor fixo de x obtido em (4.8), então retorna-se ao subproblema de limite superior para encontrar novos limites. Este procedimento é executado iterativamente até que os limites superior e inferior sejam iguais. O algoritmo geral do método outer approximation é mostrado na Figura 4.1. A seguir, para uma melhor compreensão dos passos do algoritmo, o método de outer approximation é aplicado em um problema de otimização para um exemplo simples, Capítulo 4. Métodos de Solução Utilizados 32 Figura 4.1 – Algoritmo para o método de outer approximation. Fonte: autoria própria. descrito em (4.9): Min z = x1 + x2 + y2 1 + y2 2 s.a. (y1 − 2)2 − y2 6 0 y1 − 2x1 > 0 y1 − y2 − 3(1− x1) 6 0 y1 − (1− x1) > 0 y2 − x2 > 0 y1 + y2 > 3x1 x1 + x2 > 1 0 6 y1 6 4, 0 6 y2 6 4 x1, x2 ∈ {0,1} . (4.9) Adotando-se como ponto de partida os valores de x1 = x2 = 1 e substituindo-se em (4.9), obtém-se o problema (4.10): Min z = 2 + y2 1 + y2 2 s.a. (y1 − 2)2 − y2 6 0 y1 − 2 > 0 y1 − y2 6 0 y2 − 1 > 0 y1 + y2 > 3 0 6 y1 6 4, 0 6 y2 6 4 (4.10) A solução do problema (4.10) é dada por y1 = (2,2) sendo o valor ótimo para o limite superior é dado por zU = 10. Capítulo 4. Métodos de Solução Utilizados 33 Escrevendo o problema original de maneira relaxada, obtém-se o problema mestre dado em (4.11): Min α s.a. α > x1 + x2 + 8 + 4(y1 − 2) + 4(y2 − 2) −y2 6 0 y1 − 2x1 > 0 y1 − y2 − 3(1− x1) 6 0 y1 − (1− x1) > 0 y2 − x2 > 0 y1 + y2 > 3x1 x1 + x2 > 1 0 6 y1 6 4, 0 6 y2 6 4 x1, x2 ∈ {0,1} . (4.11) A solução do problema (4.11) é dada por y2 = (1,1) e x1 = (0,1) e o valor ótimo é zL = 1. Como zU e zL não são iguais, resolve-se novamente o problema original (4.9), com x2 = (0,1): Min z = 1 + y2 1 + y2 2 s.a. (y1 − 2)2 − y2 6 0 y1 > 0 y1 − y2 − 3 6 0 y1 − 1 > 0 y2 − 1 > 0 y1 + y2 > 0 0 6 y1 6 4, 0 6 y2 6 4. (4.12) A solução de (4.12) é dada por y3 = (1,1), com solução ótima de zU = 3. Reescrevendo-se o problema original relaxado conforme descrito em (4.11), obtém-se Capítulo 4. Métodos de Solução Utilizados 34 (4.13): Min α s.a. α > x1 + x2 + 2 + 2(y1 − 1) + 2(y2 − 1) −2y1 − y2 + 3 6 0 y1 − 2x1 > 0 y1 − y2 − 3(1− x1) 6 0 y1 − (1− x1) > 0 y2 − x2 > 0 y1 + y2 > 3x1 x1 + x2 > 1 0 6 y1 6 4, 0 6 y2 6 4 x1, x2 ∈ {0,1} . (4.13) A solução de (4.13) é dada por y3 = (1,1) e x2 = (0,1) e o valor ótimo corresponde ao limite inferior dado por zL = 3. Como os limites superior zU e inferior zL são iguais, a solução ótima do problema foi encontrada. 4.3 Método de Decomposição de Benders O algoritmo de decomposição de Benders permite que problemas de otimização que apresentem variáveis complicadoras sejam resolvidos de maneira decomposta por meio de um processo iterativo (CONEJO et al., 2006). As variáveis complicadoras são aquelas que, se forem fixadas, tornam a solução numérica do problema de otimização mais simples, i.e. consideravelmente mais tratável. A ideia de decomposição proposta por Benders (1962) para problemas de otimização linear inteira-mista e generalizada por Geoffrion (1972) para problemas de otimização não linear inteira-mista consiste em fazer com que as variáveis complicadoras sejam fixadas temporariamente, tornando-o um problema de otimização linear/não linear de simples solução, porém parametrizado nessas variáveis complicadoras. O algoritmo, então, encontra o valor ótimo do vetor de variáveis restantes não fixas do problema e emprega uma abordagem de planos de corte, de modo a construir representações do valor extremo do problema linear/não linear mais simples, como uma função do vetor de parametrização e o conjunto de valores do vetor de parametrização. O método de decomposição de Benders generalizado, descrito em Geoffrion (1972), é detalhado a seguir. Seja o problema de otimização P (x,y) dado em (4.14): Min x,y f (x,y) s.a : g (x,y) ≥ 0 x ∈ X, y ∈ Y, (4.14) Capítulo 4. Métodos de Solução Utilizados 35 em que: x ∈ Rnx; y ∈ Rny, f (x,y) : Rnx+ny → R, g (x,y) : Rnx+ny → Rng. Supondo que y seja a variável complicadora, tem-se Y como o conjunto de variáveis complicadoras. Assim, para um valor fixo de y, o problema P (x,y) dado em (4.14) se apresenta como um problema mais simples de se resolver. O problema P (x,y) dado em (4.14) pode ser reescrito por meio do problema Q (x,y) equivalente, conforme descrito em (4.15): Min y Min x f (x,y) s.a : g (x,y) ≥ 0 x ∈ X, y ∈ Y. (4.15) O problema Q (x,y) também pode ser reescrito por meio de uma projeção do problema P (x,y) em y, denominada R (y), dada em (4.16): Min y v (y) s.a : y ∈ Y ∩ V (a) v (y) = inf x∈X {f (x,y) : g (x,y) ≥ 0} (b) V = {y : ∃ x ∈ X : g (x,y) ≥ 0.} (c) (4.16) Por meio da restrição 4.16(a) é descrita a projeção da região factível de P (x,y) em y. Em 4.16(b) é estalecida a condição que garantirá a otimalidade do problema enquanto que em 4.16(c) é garantida a factibilidade, ou seja, os valores de y para os quais o problema Q (x,y) é factível. Relações de equivalência entre P (x,y) e R (y) são demonstradas por Geoffrion (1972). Uma das relações demonstradas entre os problemas P (x,y) e R (y) é que o problema P (x,y) é infactível ou possui valor ótimo ilimitado, se, e somente se, o mesmo ocorre para R (y). Além disso, demonstra-se que se (x∗,y∗) é ótimo em P (x,y), então y∗ é ótimo de R (y). Finalmente, demonstra-se a seguinte relação entre os problemas (4.14), (4.15) e (4.16): se y∗ é ótimo de R (y), x∗ atinge seu supremo em Q (x,y∗), então (x∗,y∗) é o ótimo de P (x,y). A projeção de P (x,y) em y pode ser representada graficamente conforme a Figura 4.2, sendo que, o gráfico à esquerda representa a factibilidade dada pelo conjunto Y ∩ V e o gráfico à direta representa a otimalidade dada pela função v (y). Capítulo 4. Métodos de Solução Utilizados 36 Figura 4.2 – Representação gráfica da projeção de P (x,y) em y. 2y 1y ( )v y y (1) 2y ( )1 y ( )( )1*,f x y (1) 1y ( ) ( )1 (1) (1) 1 2,y y y= Y V Fonte: autoria própria. Para a construção da função v (y), para cada ponto y(1) = ( y (1) 1 ,y (1) 2 ) ∈ Y ∩ V resolve-se o problema Q ( x,y(1) ) , obtém-se o valor de f ( x∗,y(1) ) , conforme mostrado na Figura 4.2, e dado em (4.17): v ( y(1) ) = f ( x∗,y(1) ) = inf x∈X { f ( x,y(1) ) : g ( x,y(1) ) ≥ 0 } . (4.17) Para o tratamento do conjunto de factibilidade V , é necessário assumir as seguintes premissas: i) X é não vazio e convexo; ii) g (x,y) é côncava em x para cada y ∈ Y fixo e iii) o conjunto Zy = {z ∈ Rm : g (x,y) ≥ z} para algum x ∈ X é fechado para cada y ∈ Y fixo a todas as variáveis complicadoras que satisfazem V . A partir dessas premissas, mostra-se em (GEOFFRION, 1972) que um ponto y ∈ Y pertence ao conjunto V , se e somente se satisfaz o sistema infinito S (x,y) dado pelo problema (4.18): sup x∈X λTg (x,y) ≥ 0, ∀λ ∈ Λ Λ = { λ ∈ Rm : λ ≥ 0 e m∑ i=1 λi = 1 } . (4.18) Como forma de provar as relações entre o conjunto V e o sistema infinito S (x,y), é conveniente adotar um ponto arbitrário y em Y . É trivial mostrar que se y está em V , então o sistema (4.18) é satisfeito. O inverso pode ser demonstrado com a utilização da teoria da dualidade. Supondo que y satisfaz (4.18) é possível descrever que: inf λ∈Λ [ sup x∈X λTg (x,y) ] ≥ 0. (4.19) Segue-se ainda que: inf λ≥0 [ sup x∈X λTg (x,y) ] = 0. (4.20) O problema (4.20) pode ser interpretado como o dual do seguinte problema de otimização: Max x∈X 0Tx s.a : g (x,y) ≥ 0. (4.21) Capítulo 4. Métodos de Solução Utilizados 37 Então, conforme descrito em (GEOFFRION, 1972), se Zy é fechado, o problema (4.21) deve ser factível e portanto y ∈ V . Para o tratamento da função v (y) parte-se da sua definição, conforme (4.22): v (y) = inf x∈X {f (x,y) : g (x,y) ≥ 0} . (4.22) Da teoria de dualidade, e sob condições de qualificação de restrições de Slater, sabe-se que: v (y) = sup u≥0 [ inf x∈X { f (x,y) + uTg (x,y) }] , ∀y ∈ Y ∩ V. (4.23) Assim, com as condições dadas em (4.22) e (4.23) o problema R (y) fica da forma: Min y∈Y [ sup u≥0 [ inf x∈X { f (x,y) + uTg (x,y) }]] s.a. : sup x∈X λTg (x,y) ≥ 0, ∀λ ∈ { λ ∈ Rm : λ ≥ 0 e m∑ i=1 λi = 1 } . (4.24) Da teoria de otimização sabe-se que o supremo de uma função corresponde ao seu menor limite superior, ou seja:  sup z h (z) z ∈ Z =  inf θ θ s.a : θ ≥ h (z) , ∀z ∈ Z. (4.25) Geometricamente, a interpretação de (4.25) é dada pela Figura 4.3, onde o supremo de h (z) é dado pelo inf θ sujeito a θ ≥ h (z) , ∀z ∈ Z. Figura 4.3 – Interpretação geométrica do supremo de h (z).  h z z  Fonte: autoria própria. Assim, o problema R (y) dado em (4.24) resulta na forma (4.26): Min y∈Y,θ θ s.a : θ > inf x∈X { f (x,y) + uTg (x,y) } , ∀u > 0 sup x { λTg (x,y) } > 0, ∀λ ∈ { λ ∈ Rm : λ > 0e m∑ i=1 λi = 1 } . (4.26) Capítulo 4. Métodos de Solução Utilizados 38 Teoricamente, o problema (4.26) deveria ser resolvido para infinitos valores de u e λ, i.e. ∀u > 0 e ∀λ ∈ { λ ∈ Rm : λ > 0 e m∑ i=1 λi = 1 } . Entretanto, pode-se estabelecer um conjunto finito para estes valores por meio de relaxação. Para isso, são inseridos sucessivos cortes relacionados à otimalidade (i.e. associados com o primeiro conjunto de restrições em (4.26)) e cortes relacionados à factibilidade (i.e. associados com o segundo conjunto de restrições em (4.26)), em um processo iterativo (com variável contadora k), utilizando-se valores de u(j) e λ(i), pertencentes aos conjuntos Ok, e Fk, respectivamente. Estes conjuntos são estabelecidos em cada iteração k, conforme haja a necessidade de inserir cortes de otimalidade ou de factibilidade, respectivamente. O problema descrito em (4.27) é denominado de mestre, o qual representa o problema relaxado: M(u, λ)  Min y∈Y,θ θ s.a : θ > inf x∈X { f (x,y) + u(j)Tg (x,y) } , ∀u(j) ∈ Ok sup x { λ(i)Tg (x,y) } > 0, ∀λ(i) ∈ Fk. (4.27) Para a descrição do algoritmo, são definidos dois problemas de otimização a seguir. O problema primal Pk dado em (4.28), consiste no problema original em que a variável complicadora é fixada no valor y(k), associado à iteração k do método de decomposição de Benders. Problema Pk ( y(k) )  Min x f ( x,y(k) ) s.a : g ( x,y(k) ) > 0 x ∈ X. (4.28) O problema de Fk dado em (4.29) busca verificar se o problema Pk dado em (4.28) é factível ou não. Se o valor ótimo obtido para z no problema Fk for nulo, o problema Pk é factível, caso contrário, o problema é infactível. Problema Fk ( y(k) )  Max x,z z s.a : g ( x,y(k) ) > z x ∈ X,z > 0. (4.29) O algoritmo do método de decomposição de Benders generalizado é sintetizado na Figura 4.4. Capítulo 4. Métodos de Solução Utilizados 39 Figura 4.4 – Fluxograma do método de Decomposição de Benders. Fonte: autoria própria. No algoritmo, são estabelecidos inicialmente valores para as variáveis complicadoras y(k), para os limites inferior (LBD) e superior (UBD), para a precisão ε do método, e para os conjuntos Ok e Fk, associados com os cortes de otimalidade e factibilidade, respectivamente. Com o valor de y(k) fixo, o algoritmo checa a factibilidade associada a cada problema primal Pk ( y(k) ) . Se o problema for factível, atualiza-se o valor de UBD, e inserem-se cortes de otimalidade, atualizando-se o conjunto de otimalidade Ok. Caso contrário, resolve o problema de factibilidade Fk ( y(k) ) , inserindo-se cortes de factibilidade por meio da atualização do conjunto de factibilidade Fk. Em ambos os casos, resolve-se o problema mestreM ( u(i),λ(i),∀u(i) ∈ Ok,∀λ(i) ∈ Fk ) no qual os cortes de otimalidade e factibilidade são efetivamente inseridos. Atualizam-se os valores de k, y(k) e do limite inferior LBD, voltando-se à fase de verificação do erro do método, e assim, sucessivamente. Assim, com o método de decomposição de Benders, o problema se torna mais tratável, através da fixação de variáveis complicadoras e resolução de uma abordagem de planos de cortes, por um procedimento iterativo. A aplicação do método de decomposição de Benders na resolução do problema proposto neste trabalho será detalhada no Capítulo 5. 40 5 Metodologia de Solução Proposta para o Problema Robusto O problema de otimização robusto (3.37) proposto no Capítulo 3 para a representa- ção de um leilão termo-eólico com incertezas possui uma estrutura Max-Min que dificulta sua solução. Outra dificuldade envolve as variáveis binárias do problema, que tornam a sua solução mais difícil. Assim, se tratarmos as variáveis binárias como complicadoras, pode-se utilizar o método de decomposição de Benders de forma a solucionar uma série de problemas de otimização linear mais simples. Neste capítulo, propõe-se uma metodologia de solução que, inicialmente, envolve a aplicação da decomposição de Benders ao problema, a qual é descrita a seguir. O tratamento da estrutura Max-Min resultante é discutido posteriormente. O problema (3.37) pode ser reescrito em termos das variáveis x (complicadoras) e y, conforme mostrado em (5.1), de modo a aplicar a técnica de decomposição de Benders, conforme será discutido à frente: Min x ∑ i∈I ∑ t∈T zitC SU i + ∑ i∈I ∑ t∈T witC SD i + ∑ i∈I ∑ t∈T uitC FIX +Max pE∈PE Min y∈Ω(x,y,pE) F (y) s.a : x ∈ Ωx x ∈ {0,1} (5.1) em que o conjunto Ω ( x,y,pE ) é dado por: Ω ( x,y,pE ) = {y : y ∈ Ωy, (x,y) ∈ Ωx,y,∑ i∈GT n pTit + ∑ e∈GE n pEet − ∑ c∈CC n ( pCct − pCSct ) + − ∑ m∈NN n Bnm (θnt − θmt) + εgernt = 0, ∀t ∈ T, ∀n ∈ N } . (5.2) O conjunto Ω ( x,y,pE ) pode ser entendido como o conjunto factível de soluções de despacho dada uma programação liga/desliga em x fixa e um vetor pE que é composto das potências eólicas. Já o problema interno, dado por Min y∈Ω(x,y,pE) F (y), é um despacho econômico, para uma dada configuração liga/desliga x e o vetor de potências eólica pE. É conveniente, para a técnica de solução que será descrita na seção seguinte, escrever o problema dual associado ao despacho econômico. Isto porque o problema dual associado a Min y∈Ω(x,y,pE) F (y) é um problema de maximização, que torna a estrutura interna Max-Min em um único problema de maximização. Capítulo 5. Metodologia de Solução Proposta para o Problema Robusto 41 5.1 Modelo de Despacho Econômico: Problema Dual Conforme discutido na seção anterior, o modelo de nível inferior de (5.1), dado por Min y∈Ω(x,pE) F (y) é idêntico ao problema original (3.1)–(3.26), caso sejam fixados os valores de x, sendo x o vetor associado às variáveis binárias de unit commitment que impacta diretamente nos valores de liga e desliga dos geradores térmicos. É adotado um despacho de potência eólica fixo dado pelo vetor PE (diferente dos valores médios da potência eólica PE dado no problema original). Esse problema, que é determinístico, é reescrito em (5.3)–(5.19), definindo-se entre parêntesis as variáveis duais associadas a cada restrição: Min ∑ i∈I ∑ t∈T ∑ b∈BT λTitbe T itb − ∑ c∈C ∑ t∈T ∑ b∈BC γCctbe C ctb + (∑ i∈I ∑ t∈T λR U it r U it + ∑ i∈I ∑ t∈T λR D it r D it + ∑ i∈I ∑ t∈T λR NS it rNSit ) + (∑ c∈C ∑ t∈T γR U ct s U ct + ∑ c∈C ∑ t∈T γR D ct s D ct ) + ∑ c∈C ∑ t∈T V LOL ct pCSct + ∑ t∈T V LOR t εsyst + ∑ t∈T ∑ n∈N V GER t εgernt sujeito a : (5.3) 0 ≤ eTitb ≤ UitE T itb, ( δTminitb , δTmaxitb ) , ∀i ∈ I, ∀t ∈ T, ∀b ∈ BT (5.4) eTitb = UitE T itb, ( δTmin1 itb ) , ∀i ∈ I, ∀t ∈ T, b = 1 (5.5) 0 ≤ eCctb ≤ E C ctb, ( δCminctb , δCmaxctb ) , ∀c ∈ C, ∀t ∈ T, ∀b ∈ BC (5.6) pTit − ∑ b∈BT eTitb = 0, ( πTit ) , ∀i ∈ I, ∀t ∈ T (5.7) pCct − ∑ b∈BC eCctb = 0, ( πCct ) , ∀c ∈ C, ∀t ∈ T (5.8) 0 6 pCSct 6 PCSmax ct , ( πCSminct , πCSmaxct ) , ∀c ∈ C, ∀t ∈ T (5.9) 0 6 rUit 6 ∑ b∈BT ( UitE T itb − eTitb ) , ( ρUminit ,ρUmaxit ) , ∀i ∈ I, ∀t ∈ T (5.10) 0 6 rNSit 6 (1− Uit) ∑ b∈BT E T itb, ( ρNSminit , ρNSmaxit ) , ∀i ∈ I, ∀t ∈ T (5.11) 0 6 rDit 6 Uit ∑ b∈BT eTitb, ( ρDminit , ρDmaxit ) , ∀i ∈ I, ∀t ∈ T (5.12) 0 6 sUct 6 ∑ b∈BC eCctb, ( σUminct , σUmaxct ) , ∀c ∈ C, ∀t ∈ T (5.13) Capítulo 5. Metodologia de Solução Proposta para o Problema Robusto 42 0 6 sDct 6 ∑ b∈BC ( E C ctb − eCctb ) , ( σDminct , σDmaxct ) , ∀c ∈ C, ∀t ∈ T (5.14) ∑ i∈I ( rUit + rNSit − rDit ) + ∑ c∈C ( sUct − sDct ) + εsyst ≥ Rsys t , (ρsyst ) , ∀t ∈ T (5.15) εsyst ≥ 0, (ρεsyst ) , ∀t ∈ T (5.16) ∑ i∈GT n pTit − ∑ c∈CC n ( pCct − pCSct ) − ∑ m∈NN n Bnm (θnt − θmt) + εgernt = − ∑ e∈GE n PE et , (µnt) , ∀n ∈ N, ∀t ∈ T (5.17) εgernt ≥ 0, (ρgernt ) , ∀n ∈ N, ∀t ∈ T (5.18) −Fmax nm 6 Bnm (θnt − θmt) 6 Fmax nm , ( ϕminnmt, ϕ max nmt ) , ∀n ∈ N, ∀m ∈ NN n , ∀t ∈ T. (5.19) A regra de construção do problema dual associado ao problema primal (5.3)–(5.19) é dada em Arenales et al. (2007), tendo sido sintetizada na Tabela 4.1. O primeiro passo consiste em deixar do lado esquerdo da restrição todas as parcelas associadas às variáveis do problema, deixando do lado direito os recursos (constantes) do problema primal conforme (5.20)–(5.44). Além disso, todas as restrições foram reescritas como do tipo > 0, de modo que todas as variáveis duais sejam também não negativas: eTitb > 0, ( δTminitb ) , ∀i ∈ I, ∀t ∈ T, ∀b ∈ BT . (5.20) −eTitb > −UitE T itb, ( δTmaxitb ) , ∀i ∈ I, ∀t ∈ T, ∀b ∈ BT . (5.21) eTitb = UitE T itb, ( δTmin1 itb ) , ∀i ∈ I, ∀t ∈ T, b = 1. (5.22) eCctb > 0, ( δCminctb ) , ∀c ∈ C, ∀t ∈ T, ∀b ∈ BC . (5.23) −eCctb > −E C ctb, ( δCmaxctb ) , ∀c ∈ C, ∀t ∈ T, ∀b ∈ BC . (5.24) pTit − ∑ b∈BT eTitb = 0, ( πTit ) ∀i ∈ I, ∀t ∈ T. (5.25) pCct − ∑ b∈BC eCctb = 0, ( πCct ) , ∀c ∈ C, ∀t ∈ T. (5.26) Capítulo 5. Metodologia de Solução Proposta para o Problema Robusto 43 pCSct > 0, ( πCSminct ) , ∀c ∈ C, ∀t ∈ T. (5.27) −pCSct > −PCSmax ct , ( πCSmaxct ) , ∀c ∈ C, ∀t ∈ T. (5.28) rUit > 0, ( ρUminit ) , ∀i ∈ I, ∀t ∈ T. (5.29) −rUit − ∑ b∈BT eTitb > − ∑ b∈BT UitE T itb, ( ρUmaxit ) , ∀i ∈ I, ∀t ∈ T. (5.30) rNSit > 0, ( ρNSminit ) , ∀i ∈ I, ∀t ∈ T. (5.31) −rNSit > (Uit − 1) ∑ b∈BT E T itb, ( ρNSmaxit ) , ∀i ∈ I, ∀t ∈ T. (5.32) rDit > 0, ( ρDminit ) , ∀i ∈ I, ∀t ∈ T. (5.33) −rDit + ∑ b∈BT eTitb > 0, ( ρDmaxit ) , ∀i ∈ I, ∀t ∈ T. (5.34) sUct > 0, ( σUminct ) , ∀c ∈ C, ∀t ∈ T. (5.35) −sUct + ∑ b∈BC eCctb > 0, ( σUmaxct ) , ∀c ∈ C, ∀t ∈ T. (5.36) sDct > 0, ( σDminct ) , ∀c ∈ C, ∀t ∈ T. (5.37) −sDct − ∑ b∈BC eCctb > − ∑ b∈BC E C ctb, ( σDmaxct ) , ∀c ∈ C, ∀t ∈ T. (5.38) ∑ i∈I ( rUit + rNSit − rDit ) + ∑ c∈C ( sUct − sDct ) + εsyst ≥ Rsys t , (ρsyst ) , ∀t ∈ T. (5.39) εsyst ≥ 0 (ρεsyst ) , ∀t ∈ T. (5.40) ∑ i∈GT n pTit − ∑ c∈CC n ( pCct − pCSct ) − ∑ m∈NN n Bnm (θnt − θmt) + εgernt = − ∑ e∈GE n PE et , (µnt) , ∀n ∈ N, ∀t ∈ T. (5.41) εgernt ≥ 0, (ρgernt ) , ∀n ∈ N, ∀t ∈ T. (5.42) Capítulo 5. Metodologia de Solução Proposta para o Problema Robusto 44 Bnm (θnt − θmt) > −Fmax nm , ( ϕminnmt ) , ∀n ∈ N, ∀m ∈ NN n , ∀t ∈ T. (5.43) Bnm (θmt − θnt) > −Fmax nm , (ϕmaxnmt ) , ∀n ∈ N, ∀m ∈ NN n , ∀t ∈ T. (5.44) A construção da função objetivo dual é dada pela multiplicação dos recursos do problema primal pelas variáveis duais associadas. Assim, a função objetivo dual é dada conforme (5.45): D(X,PE) = + ∑ i∈I ∑ t∈T δTmin1 it1 UitE T it1 − ∑ i∈I ∑ t∈T ∑ b∈BT δTmaxitb UitE T itb − ∑ c∈C ∑ t∈T ∑ b∈BC δCmaxctb E C ctb − ∑ c∈C ∑ t∈T πCSmaxct PCSmax ct −∑ i∈I ∑ t∈T ( ρUmaxit Uit ∑ b∈BT E T itb ) − ∑ i∈I ∑ t∈T ( ρNSmaxit (1− Uit) ∑ b∈BT E T itb ) + ∑ t∈T Rsys t ρsyst − ∑ c∈C ∑ t∈T ( σDmaxct ∑ b∈BC E C ctb ) − ∑ n∈N ∑ t∈T µnt ∑ e∈GE n PE et − ∑ n∈N ∑ m∈NN n ∑ t∈T (ϕminnmt + ϕmaxnmt )Fmax nm . (5.45) Nota-se que os termos com recursos nulos não aparecem na função primal. O vetor de variáveis duais do problema é dado por (5.46). α =  δTminitb , δTmaxitb , δTmin1 itb , ∀i ∈ I, ∀t ∈ T, ∀b ∈ BT δCminctb , δCmaxctb , ∀c ∈ C, ∀t ∈ T, ∀b ∈ BC πTit , ρ Umin it ,ρUmaxit ,ρNSminit , ρNSmaxit , ρDminit , ρDmaxit ,∀i ∈ I, ∀t ∈ T πCct, π CSmin ct , πCSmaxct , σUminct , σUmaxct , σDminct , σDmaxct , ∀c ∈ C, ∀t ∈ T ρsyst , ρεsyst , ∀t ∈ T µnt, ρ ger nt , ∀n ∈ N, ∀t ∈ T ϕminnmt, ϕ max nmt , ∀n ∈ N, ∀m ∈ NN n , ∀t ∈ T  . (5.46) Segundo regra de construção, as restrições de igualdade e desigualdade associadas ao problema dual estão relacionadas a cada variável de otimização do problema dual. Assim, por exemplo, associadas às variáveis primais eTitb devem aparecer, no problema dual, restrições para cada t ∈ T, i ∈ I e b ∈ BT , conforme restrição mostrada em (5.47): δTminitb − δTmaxitb − πTit − ρUmaxit + ρDmaxit = λTitb, ∀i ∈ I, ∀t ∈ T, ∀b ∈ BT : b 6= 1. (5.47) Do lado esquerdo da restrição de igualdade (5.47), aparecem os fatores que multi- plicam as variáveis eTitb em cada restrição onde esta variável aparece no problema primal, multiplicados pelas variáveis duais associadas a cada restrição. Do lado direito da igualdade aparecem os fatores relacionados ao gradiente da função objetivo do problema primal, os quais, segundo a regra de construção, se tornam os respectivos recursos no problema dual. Como as variáveis primais estão livres no problema primal (i.e. existem restrições Capítulo 5. Metodologia de Solução Proposta para o Problema Robusto 45 explícitas para representar a não negatividade destas variáveis), todas as restrições do problema dual são dadas na forma de restrições de igualdade, como em (5.47). Para a situação em que b = 1 a restrição de eTitb é dada por (5.48): δTmin1 itb + δTminitb − δTmaxitb − πTit − ρUmaxit + ρDmaxit = λTitb, ∀i ∈ I, ∀t ∈ T : b = 1. (5.48) De forma análoga, pode-se escrever as restrições do problema dual em relação a cada variável primal do problema. Para a variável eCctb, tem-se a restrição dual dada em (5.49): δCminctb − δCmaxctb − πCct + σUmaxct − σDmaxct = −γCctb, ∀c ∈ C, ∀t ∈ T, ∀b ∈ BC . (5.49) Para a variável primal rUit , tem-se a restrição (5.50): ρUminit − ρUmaxit + ρsyst = λR U it , ∀i ∈ I, ∀t ∈ T. (5.50) Para a variável primal rDit , tem-se a restrição (5.51): ρDminit − ρDmaxit − ρsyst = λR D it , ∀i ∈ I, ∀t ∈ T. (5.51) Para a variável primal rNSit , tem-se a restrição (5.52): ρNSminit − ρNSmaxit + ρsyst = λR NS it , ∀i ∈ I, ∀t ∈ T. (5.52) Para a variável primal sUct, tem-se a restrição (5.53): σUminct − σUmaxct + ρsyst = γR U ct , ∀c ∈ C, ∀t ∈ T. (5.53) Para a variável primal sDct, tem-se a restrição (5.54): σDminct − σDmaxct − ρsyst = γR D ct , ∀c ∈ C, ∀t ∈ T. (5.54) Para a variável primal pCSct , tem-se a restrição (5.55): πCSminct − π