Universidade Federal de Juiz de Fora Faculdade de Engenharia e Arquitetura Mestrado em Engenharia Elétrica Um Algoritmo Branch and Bound para o Problema da Alocação Ótima de Monitores de Qualidade de Energia Elétrica em Redes de Transmissão DÉBORA COSTA SOARES DOS REIS Juiz de Fora, MG - Brasil Agosto de 2007 ii REIS, DÉBORA COSTA SOARES DOS Um Algoritmo Branch and Bound para o Problema da Alocação Ótima de Monitores de Qualidade de Energia Elétrica em Redes de Transmissão [Juiz de Fora] 2007-08-13 IX, 110 p. 29,7cm (UFJF, M. Sc. Engenharia Elétrica, 2007) Dissertação – Universidade Federal de Juiz de Fora 1. Instrumentação e Controle 2. Otimização 3. Qualidade de Energia Elétrica I. UFJF II. Título (Série) iii Dedico este trabalho ao meu pai, José, de quem tenho muitas saudades e foi mestre um dia, à minha mãe, Rosângela, e aos meus avós, Nancy e Orlando, que são a minha fortaleza e inspiração. iv Agradecimentos Agradeço a Deus pela inteligência, disciplina, determinação e fé que me foram concedidas nesta caminhada. Ao professor Paulo Villela pela orientação desde que me formei até hoje, por ter sido uma pessoa presente e paciente, depositando sua credibilidade em mim, por não ter desistido nunca de me incentivar em momentos difíceis e por ter sido um grande mestre, que influenciará todo o meu futuro profissional e pessoal. Ao professor Carlos Duque pela paciência, apoio e dedicação fundamentais para o meu desempenho e crescimento. Ao corpo docente do Mestrado em Engenharia Elétrica e, em especial, ao professor Hélio Antônio que muito contribuiu na minha escolha pela vida acadêmica. Agradeço à minha mãe pelo carinho, compreensão, apoio e amor incondicionais; aos meus avós pelo exemplo de vida e zelo; às minhas irmãs Raquel e Carolina pela amizade e companheirismo; ao meu padrasto Francisco pelo suporte, ao meu namorado Thiago pela compreensão, amizade e incentivo e a toda minha família. A todos os amigos que estiveram direta ou indiretamente relacionados à conclusão deste trabalho; aos amigos do Softex, em especial à Fernanda Rabelo e ao Igor Knop, que tanto me ouviram e me apoiaram; ao amigo do Labspot, Marcelo Cantarino, que me ajudou bastante com o texto e simulações; aos amigos do Labsel que me receberam muito bem, em especial ao Thiago Castro, que foi parceiro desde o início do Mestrado e ao Rodrigo Teixeira, que trabalhou comigo. v Resumo da Dissertação de Mestrado apresentada ao Programa de Pós Graduação em Engenharia Elétrica da UFJF como parte dos requisitos necessários para a obtenção do grau de Mestre em Engenharia Elétrica. UM ALGORITMO BRANCH AND BOUND PARA O PROBLEMA DA ALOCAÇÃO ÓTIMA DE MONITORES DE QUALIDADE DE ENERGIA ELÉTRICA EM REDES DE TRANSMISSÃO. Débora Costa Soares dos Reis Agosto de 2007 Orientadores: Carlos Augusto Duque Paulo Roberto de Castro Villela Área de Concentração: Instrumentação e Controle Este trabalho desenvolve e avalia um algoritmo branch and bound para a solução do problema de alocação ótima de medidores de qualidade de energia elétrica numa rede de transmissão elétrica de potência. O problema de otimização é solucionado usando técnicas de programação inteira 0-1 e depende fortemente da topologia da rede. O algoritmo é implementado no software Matlab, minimiza o custo total do sistema de monitoramento e determina o número ótimo e a localização de monitores, sob dadas restrições de observabilidade da rede. São apresentados estudos de casos em redes de teste IEEE e numa rede de transmissão real da CEMIG - Companhia Energética de Minas Gerais. Os resultados alcançados são validados com a estimação das tensões e correntes na rede, a partir das grandezas monitoradas, o que reforça a flexibilidade e o bom desempenho computacional do algoritmo. vi Abstract of Thesis presented to the Master Program in Electrical Engineering of UFJF as a partial fulfillment of the requirements for the degree of Master of Science (M. Sc.) UM ALGORITMO BRANCH AND BOUND PARA O PROBLEMA DA ALOCAÇÃO ÓTIMA DE MONITORES DE QUALIDADE DE ENERGIA ELÉTRICA EM REDES DE TRANSMISSÃO. Débora Costa Soares dos Reis August, 2007 Supervisor: Carlos Augusto Duque Paulo Roberto de Castro Villela Program Area: Instrumentation and Control This work develops and tests a branch and bound algorithm for solving optimal allocation of power quality monitors in a transmission power system. The optimization problem is solved by using 0-1 integer programming techniques and depends highly on network topology. The algorithm, which is implemented in Matlab software, minimizes the total cost of monitoring system and found the optimal number and locations for monitors on the network studied, under a given network observability constraints. Case studies are presented for IEEE test networks and for CEMIG real transmission power system. Current and voltage values are estimated by using monitored variables to validate the obtained results. vii SSuummáárriioo CCaappííttuulloo 11 -- IInnttrroodduuççããoo.....................................................................................................1 1.1 – Considerações Iniciais....................................................................................1 1.2 – Objetivos..........................................................................................................2 1.3 – Metodologia.....................................................................................................3 1.4 – Revisão Bibliográfica......................................................................................5 1.5 – Divisão do Trabalho........................................................................................9 CCaappííttuulloo 22 -- MMooddeellaaggeemm ddoo PPrroobblleemmaa............................................................................11 2.1 – Introdução......................................................................................................11 2.2 – Exemplo Simples...........................................................................................12 2.3 – Formulação Matemática do Problema do Recobrimento...........................14 2.3.1 - Exemplo........................................................................................................17 2.4 – Formulação Matemática do Problema de Alocação de Monitores............19 2.4.1 – Vetor de Existência.......................................................................................21 2.4.2 – Vetor de Custo .............................................................................................22 2.4.3 – Função Objetivo...........................................................................................22 2.4.4 – Descrição das Restrições do Problema........................................................22 2.4.5 – Formulação do Problema de Otimização.....................................................29 2.5 – Exemplos de Redes de Energia Elétrica........................................................30 2.5.1 – Sistema de 3 barras.....................................................................................31 2.5.2 – Sistema de 6 barras.....................................................................................34 2.5.3 – Sistemas IEEE 14 e IEEE 30 .......................................................................38 2.5.4 – Sistema de Transmissão CEMIG.................................................................40 CCaappííttuulloo 33 -- SSoolluuççããoo ddoo pprroobblleemmaa..................................................................................43 3.1 – Introdução.........................................................................................................43 3.2 – Procedimentos básicos de um Branch and Bound aplicado ao Problema do Recobrimento............................................................................................................44 3.3 – Fluxograma Geral.............................................................................................49 3.4 – Um Exemplo Numérico....................................................................................51 3.4.1 – Conceitos Gerais..........................................................................................51 3.4.2 – Solução via árvore B&B................................................................................53 3.4.3 – Solução via fluxograma................................................................................64 CCaappííttuulloo 44 –– RReessuullttaaddooss.................................................................................................69 4.1 – Introdução.........................................................................................................69 4.2 – Cálculo do Fator de Redundância...................................................................69 4.3 – Soluções Ótimas de Alocação de Medidores................................................71 4.3.1 – Soluções para custos de instalação iguais...................................................71 4.3.2 – Soluções para custos de instalação diferentes............................................76 4.3.3 – Soluções com maior redundância................................................................81 4.3.4 – Soluções para monitores já instalados.........................................................84 CCaappííttuulloo 55 –– EEssttiimmaaççããoo ddaass tteennssõõeess ee ccoorrrreenntteess ddaa rreeddee aa ppaarrttiirr ddaass ggrraannddeezzaass mmoonniittoorraaddaass....................................................................................................................88 5.1 – Introdução.........................................................................................................88 5.2 – Estimação das Variáveis de Estado................................................................88 5.3 – Simulação de Redes Elétricas.........................................................................90 CCaappííttuulloo 66 –– CCoonncclluussõõeess ee TTrraabbaallhhooss FFuuttuurrooss...............................................................97 RReeffeerrêênncciiaass BBiibblliiooggrrááffiiccaass............................................................................................100 AAnneexxooss.........................................................................................................................104 A.1– Fluxograma para Montagem das Matrizes de Conectividade.....................104 A.2– Soluções para os problemas de alocação para o sistema IEEE 14 barras105 A.3– Implementação do Algoritmo em Matlab......................................................106 ix CCaappííttuulloo 11 -- IInnttrroodduuççããoo 1.1 – Considerações Iniciais Um dos grandes desafios para garantir a qualidade de energia em uma rede de transmissão é a identificação das diversas fontes “poluidoras” do sistema e a quantificação dos níveis de poluição de cada uma das fontes. Estas informações são fundamentais para as concessionárias de energia e agências reguladoras, uma vez que a partir delas será possível criar políticas corretivas e punitivas em relação aos agentes poluidores. A questão da localização das fontes de distúrbios tem motivado diversas pesquisas recentes entre elas podemos citar as referências (SZCZUPACK, 2004; TESOME, 2001; PARSONS ET AL., 1998; MA & GIRGIS, 1996; YU ET AL. 2005). Este problema, porém, é de difícil solução visto o alto nível de interconexão das redes elétricas e sua solução passa pelo monitoramento distribuído das redes, através dos monitores de qualidade de energia elétrica (QEE). O maior inconveniente enfrentado no monitoramento da rede elétrica está associado ao custo dos medidores e dos canais de comunicação, motivando assim o desenvolvimento de metodologias que procuram minimizar o custo total do sistema de monitoramento (ALMEIDA ET AL., 2005, 2007; OLGUIN ET AL., 2006; ELDERY ET AL., 2004, 2006; ABUR & MAGNANO, 1999, 2001; AMMER & RENNER, 2004; AKABANE ET AL., 2002; MADTHARAD ET AL., 2005; RAKPENTHAI ET AL., 2007). Uma das soluções de minimização do custo passa pela identificação do número mínimo de medidores a serem instalados na rede, bem como a sua localização, de modo que a observabilidade do sistema seja mantida, ou seja, que a partir das grandezas monitoradas pelos monitores de QEE, as grandezas elétricas (corrente e tensão) em qualquer outro ponto da rede possam ser estimadas. 1