Ilha Solteira UNIVERSIDADE ESTADUAL PAULISTA “JÚLIO DE MESQUITA FILHO” FACULDADE DE ENGENHARIA Câmpus de Ilha Solteira Jeferson Back Vanderlinde PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO USANDO TÉCNICAS ESPECIALIZADAS DE PROGRAMAÇÃO INTEIRA MISTA Ilha Solteira 2017 Jeferson Back Vanderlinde PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO USANDO TÉCNICAS ESPECIALIZADAS DE PROGRAMAÇÃO INTEIRA MISTA Trabalho apresentado como requisito para a ob- tenção do título de doutor no Departamento de Engenharia Elétrica da Universidade Estadual Paulista “Júlio de Mesquita Filho”, Campus de Ilha Solteira. Especialidade: Automação. Rubén Augusto Romero Lázaro Orientador Yong Fu Coorientador Ilha Solteira 2017 VanderlindePlanejamento da expansão de sistemas de transmissão usando técnicas especializadas de programação inteira mistaIlha Solteira2017 155 Sim Tese (doutorado)Engenharia Elétrica30404029 Não . . . FICHA CATALOGRÁFICA Desenvolvido pelo Serviço Técnico de Biblioteca e Documentação Vanderlinde, Jeferson Back. Planejamento da expansão de sistemas de transmissão usando técnicas especializadas de programação inteira mista / Jeferson Back Vanderlinde. -- Ilha Solteira: [s.n.], 2017 153 f. : il. Tese (doutorado) - Universidade Estadual Paulista. Faculdade de Engenharia de Ilha Solteira. Área de conhecimento: Automação, 2017 Orientador: Rubén Augusto Romero Lázaro Co-orientador: Yong Fu Inclui bibliografia 1. Dual simplex canalizado. 2. Branch and bound. 3. Primal simplex canalizado. 4. Programação linear inteira mista. 5. Planejamento da expansão de sistemas de transmissão. 6. Modelos de transporte e linear disjuntivo. V235p DEDICO Este trabalho ao meu pai, Maurício Vanderlinde, e à minha mãe, Jacinta Juliana Back Vanderlinde, que me educaram e lutaram muito para que alcançasse mais essa conquista, exemplos de vida fundamentais para mim, e à minha querida esposa, Debora Aparecida Barbosa Vanderlinde que me apoiou e lutou comigo nessa etapa da minha vida. AGRADECIMENTOS Agradeço primeiramente a Deus, por todas as bênçãos recebidas em minha vida e por me prover força, conhecimento e inteligência para que eu alcançasse mais esta vitória. Aos meus pais, Maurício Vanderlinde e Jacinta Juliana Back Vanderlinde, pela boa educação e suporte que me deram, por terem lutado muito para que eu tivesse sucesso e pelo incentivo que me deram para que eu continuasse estudando e nunca desistisse diante dos obstáculos. Aos meus irmãos, Keila Cristina Back Vanderlinde e Douglas Vanderlinde, pelo apoio concedido nos momentos difíceis. Eu também gostaria de expressar meus sinceros agradecimentos ao Prof. Dr. Rubén Augusto Romero Lázaro pela ajuda concedida no mestrado e doutorado, pelo apoio e dedicação em todo o período de orientação deste trabalho. Meus agradecimentos aos membros da banca examinadora, Prof. Dr. José Roberto Sanches Mantovani, Prof. Dr. Antonio Padilha Feltrin, Profa. Dra. Lina Paola Garces Negrete, Prof. Dr. Luis Gustavo Wesz da Silva pelas sugestões e críticas construtivas. Aos professores da UNEMAT - Campus Universitário de Sinop, principalmente Dr. Rogério dos Reis Gonçalves, Dr. Milton Luiz Neri Pereira, Dr. Silvio Cesar Garcia Granja e Dra. Vera Lúcia Vieira de Camargo, pelo incentivo, ajuda e amizade. Aos meus caríssimos amigos, Dr. João Toledo da Silva, Sueli Terezinha Ribeiro Soares Toledo da Silva e Lucas Toledo da Silva por serem quase uma família para mim, sempre me apoiando, ajudando e me ensinando coisas novas durante todo o doutorado. Aos amigos do LAPSEE, principalmente, Diogo Rupolo, Renzo Amilcar Vargas Peralta e Leonardo Henrique Faria Macedo Possagnolo. Aos demais amigos de outros laboratórios. Agradeço também à UNESP, ao departamento de Engenharia Elétrica da FEIS, pela es- trutura oferecida para o desenvolvimento do trabalho. À CAPES pelo apoio financeiro concedido durante o doutorado e doutorado-sanduíche. Finalmente, à minha esposa, Debora Aparecida Barbosa Vanderlinde, declaro minha completa e mais sincera admiração e agradecimento pelo amor, dedicação, companheirismo, paciência e compreensão nesta fase de minha educação e por compartilharmos nossas alegrias. Sinceramente, Jeferson Back Vanderlinde, 07 de setembro de 2017 “Deixem que o futuro diga a verdade e avalie cada um de acordo com o seu trabalho e realizações. O presente pertence a eles, mas o futuro pelo qual eu sempre trabalhei pertence a mim.” Nikola Tesla RESUMO Neste trabalho, consideram-se a análise teórica e a implementação computacional dos algoritmos Primal Simplex Canalizado (PSC) e Dual Simplex Canalizado (DSC) especializados. Esses algoritmos foram incorporados em um algoritmo Branch and Bound (B&B) de modo a resolver o problema de Planejamento da Expansão de Sistemas de Transmissão (PEST). Neste caso, o problema PEST foi modelado usando os chamados modelo de Transportes e modelo Linear Disjuntivo (LD), o que produz um problema de Programação Linear Inteiro Misto (PLIM). O algoritmo PSC é utilizado na resolução do problema de Programação Linear (PL) inicial após desconsiderar a restrição de integralidade do problema PLIM original. Juntamente com o algoritmo PSC, foi implementada uma estratégia para reduzir o número de variáveis artificiais adicionadas ao PL, consequentemente reduzindo o número de iterações do algoritmo PSC. O algoritmo DSC é utilizado na reotimização eficiente dos subproblemas gerados pelo algoritmo B&B, através do quadro ótimo do PL inicial, excluindo, assim, a necessidade da resolução completa de cada subproblema e, consequentemente, reduzindo o consumo de processamento e memória. Nesta pesquisa, é apresentada uma nova proposta de otimização, e, consequentemente, a implementação computacional usando a linguagem de programação FORTRAN que opera independentemente de qualquer solver. Palavras-chave: Dual simplex canalizado. Branch and bound. Primal simplex canalizado. Pro- gramação linear inteira mista. Planejamento da expansão de sistemas de transmissão. Modelo de transportes. Modelo linear disjuntivo. ABSTRACT In this research, the theoretical analysis and computational implementation of the specialized dual simplex algorithm (DSA) and primal simplex algorithm (PSA) for bounded variables is considered. These algorithms have been incorporated in a Branch and Bound (B&B) algorithm to solve the Transmission Network Expansion Planning (TNEP) problem. In this case, the TNEP problem is modeled using transportation model and linear disjunctive model (DM), which produces a mixed-integer linear programming (MILP) problem. After relaxing the integrality of investment variables of the original MILP problem, the PSA is used to solve the initial linear programming (LP) problem. Also, it has been implemented a strategy in PSA to reduce the number of artificial variables which are added into the LP problem, and consequently reduces the number of iterations of PSA. Through optimal solution of the initial LP, the DSA is used in efficient reoptimization of subproblems, resulting from the B&B algorithm, thus excludes the need for complete resolution of each subproblems, which results reducing the CPU time and memory consumption. This research presents the implementation of the proposed approach using the FORTRAN programming language which operates independently and does not use any commercial solver. Keywords: Dual simplex for bounded variables. Branch and bound. Primal simplex for bounded variables. Mixed-integer linear programming. Transmission network expansion planning. Transportation model. Linear disjunctive model. LISTA DE FIGURAS Figura 1 – Sistema didático de 3 barras . . . . . . . . . . . . . . . . . . . . . . . . . . 33 Figura 2 – Uma das árvores Branch and Bound de solução do sistema de 3 barras com uma linha na topologia base mostrado na Figura 1. . . . . . . . . . . . . . . 56 Figura 3 – Determinação simplificada de estimativas através de pseudocustos para se- leção do subproblema candidato a ser resolvido pelo algoritmo B&B . . . . 62 Figura 4 – Fluxograma do Algoritmo Branch and Bound . . . . . . . . . . . . . . . . 67 Figura 5 – Fluxograma do Algoritmo Primal Simplex Canalizado . . . . . . . . . . . . 78 Figura 6 – Fluxograma do Algoritmo Dual Simplex Canalizado . . . . . . . . . . . . . 90 Figura 7 – Estrutura inicial do modelo de transporte para a construção do PL . . . . . . 92 Figura 8 – Matriz de incidência nó-ramo para o modelo de transporte . . . . . . . . . . 93 Figura 9 – Matriz dos coeficientes das barras geradoras . . . . . . . . . . . . . . . . . 94 Figura 10 – Estrutura completa do modelo de transporte para a construção do PL . . . . 95 Figura 11 – Matrizes de coeficientes das variáveis básicas B e não básicas N1 e N2 . . . 96 Figura 12 – Matriz de coeficientes das variáveis de ângulo para o modelo linear disjuntivo 99 Figura 13 – Estrutura inicial do modelo linear disjuntivo para a construção do PL . . . . 100 Figura 14 – Matriz dos coeficientes das variáveis de investimento referente à restrição do número máximo de linhas que podem ser construídas em cada caminho do sistema no modelo linear disjuntivo. . . . . . . . . . . . . . . . . . . . . . 101 Figura 15 – Matriz dos coeficientes das variáveis de investimento referente à restrição que garante a construção sequencial de cada linha candidata no modelo linear disjuntivo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 Figura 16 – Matriz de coeficientes das variáveis de folga e artificiais, limites e vetores de custos do modelo linear disjuntivo . . . . . . . . . . . . . . . . . . . . . . 104 Figura 17 – Estrutura completa do modelo linear disjuntivo para a construção do PL . . 105 Figura 18 – Solução ótima do modelo de transporte para o sistema de 3 barras com uma linha na topologia base encontrada em P2 . . . . . . . . . . . . . . . . . . . 110 Figura 19 – Solução ótima do modelo de transporte para o sistema de 3 barras com uma linha na topologia base encontrada em P6 . . . . . . . . . . . . . . . . . . . 111 Figura 20 – Árvore Branch and Bound do modelo de transporte para o sistema de 3 barras com uma linha na topologia base . . . . . . . . . . . . . . . . . . . . . . . 111 Figura 21 – Sistema de Garver com 6 barras e 15 caminhos . . . . . . . . . . . . . . . . 115 Figura 22 – Sistema IEEE(a) com 24 barras e 41 caminhos . . . . . . . . . . . . . . . . 116 Figura 23 – Sistema Sul-Brasileiro com 46 barras e 79 caminhos . . . . . . . . . . . . . 117 LISTA DE TABELAS Tabela 1 – Quadro Simplex Canalizado Alternativo . . . . . . . . . . . . . . . . . . . 68 Tabela 2 – Notação a ser utilizada . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 Tabela 3 – Quadro Simplex Canalizado Alternativo de Duas Fases . . . . . . . . . . . 80 Tabela 4 – Estrutura inicial do sistema de três barras no modelo de transporte para a construção do PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 Tabela 5 – Estrutura inicial do sistema de três barras no modelo de transporte para a construção do PL resolvido passo a passo . . . . . . . . . . . . . . . . . . . 109 Tabela 6 – Estrutura completa do sistema de três barras no modelo de transporte para a construção do PL resolvido passo a passo . . . . . . . . . . . . . . . . . . . 110 Tabela 7 – Estrutura inicial do sistema de três barras no modelo linear disjuntivo para a construção do PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 Tabela 8 – Matriz de coeficientes das variáveis de folga e artificiais, limites e vetores de custos do modelo linear disjuntivo para o sistema de três barras . . . . . . . 113 Tabela 9 – Desempenho dos algoritmos no planejamento do sistema de Garver . . . . . 118 Tabela 10 – Desempenho dos algoritmos no planejamento do sistema IEEE(a) . . . . . . 119 Tabela 11 – Desempenho dos algoritmos no planejamento do sistema Sul-Brasileiro . . 119 Tabela 12 – Soluções ótimas do sistema de Garver . . . . . . . . . . . . . . . . . . . . 121 Tabela 13 – Soluções ótimas do sistema IEEE(a) . . . . . . . . . . . . . . . . . . . . . 121 Tabela 14 – Soluções ótimas do sistema Sul-Brasileiro . . . . . . . . . . . . . . . . . . 121 Tabela 15 – Quadro Primal Simples Canalizado Inicial de P0 . . . . . . . . . . . . . . . 134 Tabela 16 – Quadro ótimo de P0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 Tabela 17 – Quadro ótimo de P2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 Tabela 18 – Quadro ótimo de P1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 Tabela 19 – Quadro ótimo de P4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 Tabela 20 – Quadro ótimo de P6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 Tabela 21 – Quadro ótimo de P5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 Tabela 22 – Quadro ótimo de P8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 Tabela 23 – Dados das barras do sistema de Garver . . . . . . . . . . . . . . . . . . . . 149 Tabela 24 – Dados dos caminhos do sistema de Garver . . . . . . . . . . . . . . . . . . 149 Tabela 25 – Dados das barras do sistema IEEE(a) . . . . . . . . . . . . . . . . . . . . . 149 Tabela 26 – Dados dos caminhos do sistema IEEE(a) . . . . . . . . . . . . . . . . . . . 150 Tabela 27 – Dados das barras do sistema Sul-Brasileiro . . . . . . . . . . . . . . . . . . 151 Tabela 28 – Dados dos caminhos do sistema Sul-Brasileiro . . . . . . . . . . . . . . . . 152 LISTA DE ALGORITMOS 1 Algoritmo de Garver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2 Algoritmo Branch and Bound Básico . . . . . . . . . . . . . . . . . . . . . . . 55 3 Algoritmo Primal Simplex Canalizado . . . . . . . . . . . . . . . . . . . . . . 75 4 Algoritmo Dual Simplex Canalizado . . . . . . . . . . . . . . . . . . . . . . . 88 LISTA DE ABREVIATURAS E SIGLAS AC Meta-heurística ant colony AG Algoritmo de Garver B&B Branch and Bound CC Modelo de Corrente Contínua CA Modelo de Corrente Alternada DSC Dual Simplex Canalizado EA Algoritmos Evolutivos - Evolutionary algorithms GRASP Meta-heurística GRASP - Greedy Randomized Adaptive Search Procedure GA Algoritmos genéticos - Genetic algorithm KKT Condições de Karush-Kuhn-Tucker LCK Lei das Correntes de Kirchhoff LIFO Last In First Out LTK Lei das Tensões de Kirchhoff LD Modelo Linear Disjuntivo LI Limite Inferior LS Limite Superior PEST Planejamento da Expansão de Sistemas de Transmissão PL Programação Linear PLBM Programação Linear Binário Misto PLI Programação linear inteiro PLIM Programação Linear Inteiro Misto PNLIM Programação Não Linear Inteiro Misto PSO Meta-heurística particle swarm optimization PSC Primal Simplex Canalizado PR Path Relinking SA Meta-heurística simulated annealing SBF Solução Básica Factível TS Meta-heurística tabu search LISTA DE SÍMBOLOS Operadores D(x) Operador que cria uma matriz quadrada com os elementos de um vetor qualquer x na diagonal principal e os demais elementos da matriz iguais a zero. Conjuntos Z conjunto dos números inteiros. Ωb conjunto das barras do sistema de transmissão. Ωl conjunto dos caminhos do sistema de transmissão. Ω0 l , Ω1 l conjunto dos caminhos nos quais já existem linhas na configuração base. Ω2 l conjunto dos caminhos novos. I conjunto das variáveis inteiras. R1 conjunto de índices das variáveis não básicas que estão fixadas nos seus limites inferiores. R2 conjunto de índices das variáveis não básicas que estão fixadas nos seus limites superiores. Y conjunto das linhas que podem ou não ser adicionadas no caminho i j. Constantes 0m,n matriz de m linhas e n colunas com todos os elementos iguais a zero. 1m,n matriz de m linhas e n colunas com todos os elementos iguais a um. F̄ vetor que define os limites do fluxo total de potência ativa em cada caminho ij no modelo de transporte. F̄ 0 vetor que define os limites do fluxo total de potência ativa nas linhas existentes em cada caminho i j no modelo linear disjuntivo. ḡg vetor com os valores de ḡi somente das barras que possuem geração. ∞m,n matriz de m linhas e n colunas com todos os elementos iguais a infinito (∞). f i j máximo fluxo de potência ativa permitido para uma linha no caminho i j. f 0 i j, f 1 i j máximo fluxo de potência ativa permitido para uma linha no conjunto de linhas exis- tentes no caminho i j. f 2 i j máximo fluxo de potência ativa permitido para uma linha no conjunto de linhas novas no caminho i j. gi máxima capacidade de geração na barra i. ni j número máximo de linhas permitidas no caminho i j. n1 i j número máximo de linhas que pode ser adicionado em paralelo a linhas já existentes no caminho i j. n2 i j número máximo de linhas permitido em novos caminhos i j. θk ângulo de fase da barra de referência k. A matriz dos coeficientes das variáveis do problema de programação linear inteiro misto na forma padrão. A∗ parte inicial da matriz de coeficientes A, cujas colunas correspondem às variáveis origi- nais do problema. A f a matriz dos coeficientes das variáveis de folga e artificiais. A0 matriz dos coeficientes das variáveis artificiais adicionadas nas restrições de igualdade; essa matriz tem a forma de uma matriz identidade, mas o sinal de alguns elementos da diagonal principal podem ser negativos. A1 matriz dos coeficientes das variáveis artificiais extras que são adicionadas nas restrições de desigualdade quando necessário; cada coluna dessa matriz tem somente um elemento diferente de zero, sendo −1 na linha referente à restrição onde foi adicionada a variável artificial. ai j um elemento da matriz de coeficientes A. ai linha i da matriz de coeficientes A. B solução básica factível para o PL. b vetor de termos constantes do problema de programação linear inteiro misto na forma padrão. b f n0 vetor com os valores da multiplicação do fluxo máximo de potência e o número de linhas existentes em cada caminho i j no modelo de transporte. bi um elemento do vetor de termos constantes b. c vetor com valores de ci j. c vetor de custos do problema de programação linear inteiro misto na forma padrão. c′ vetor de custos da função objetivo de Fase I. c′ f a vetor de custos da função objetivo de Fase I das variáveis de folga e artificiais. c∗ vetor linha inicial de custos do PL. c f a vetor de custo das variáveis de folga e artificiais. cB custos referentes às variáveis básicas. ci j custo de construção de uma linha no caminho i j. cN1 custos referentes às variáveis não básicas fixadas em seus limites inferiores. cN2 custos referentes às variáveis não básicas fixadas em seus limites superiores. d vetor com os valores de di. di demanda de potência ativa na barra i. G matriz dos coeficientes das barras geradoras gi. Im matriz identidade com m linhas e colunas. l vetor com os limites inferiores das variáveis do problema de programação linear inteiro misto na forma padrão. l∗ vetor coluna inicial com os limites inferiores das variáveis originais do problema. l f a vetor com os limites inferiores das variáveis de folga e artificiais. M um número suficientemente grande. m número de restrições do problema. n número de variáveis do problema. N1 matriz de coeficientes das variáveis não básicas fixadas nos seus limites inferiores. N2 matriz de coeficientes das variáveis não básicas fixadas nos seus limites superiores. n0 i j número de linhas existentes na configuração base no caminho i j. na número de varáveis artificiais. nae número de variáveis artificiais extras que são adicionadas ao PL quando uma variável de folga não pode fazer parte da SBF inicial. nb número de barras existentes no sistema. n f número de variáveis de folga. ng número de barras que possuem geração. nl número de linhas do sistema. no número de caminhos com linhas existentes na configuração base do sistema. ns número de restrições que garantem a alocação sequencial das linhas em cada caminho i j. nt número de variáveis de ângulo do modelo linear disjuntivo. nw número máximo de linhas que podem ser adicionadas ao sistema. P0 problema de programação linear inicial com integralidade relaxada no algoritmo Branch and Bound. Pk problema de programação linear descendente do problema inicial com integralidade relaxada no algoritmo Branch and Bound. S matriz de incidência nó-ramo. S0 matriz de incidência nó-ramo que corresponde à matriz dos coeficientes das variáveis de fluxo de potência ativa nas linhas existentes. T matriz dos coeficientes das variáveis de ângulo referente às restrições da lei de tensões de Kirchhof nas linhas novas no modelo linear disjuntivo. T ′ matriz dos coeficientes das variáveis de ângulo referente à restrição da lei de tensões de Kirchhof nas linhas existentes no modelo linear disjuntivo. u vetor com os limites superiores das variáveis do problema de programação linear inteiro misto na forma padrão. u∗ vetor coluna inicial com os limites superiores das variáveis originais do problema. u f a vetor com os limites superiores das variáveis de folga e artificiais. WS matriz dos coeficientes das variáveis de investimento wi j,y na restrição que garante a alocação sequencial das novas linhas em cada caminho i j do sistema elétrico no modelo linear disjuntivo. WT matriz dos coeficientes das variáveis de investimento wi j,y na restrição de limite do número máximo de novas linhas que podem ser construídas em cada caminho i j do sistema elétrico no modelo linear disjuntivo. xi j reatância no caminho i j. Variáveis contínuas b vetor do quadro simplex com os valores correntes das variáveis básicas. x0, y00 valor corrente da função objetivo no quadro simplex. θi ângulo de fase na barra i. z̃00 novo valor da função objetivo, após a mudança de base, no algoritmo Dual Simplex Canalizado. fi j,y fluxo de potência ativa na linha y no caminho i j. fi j fluxo de potência ativa total no caminho i j. f 0 i j, f 1 i j fluxo de potência ativa para o conjunto de linhas existentes no caminho i j. f 2 i j fluxo de potência ativa para o conjunto de linhas novas no caminho i j. f v i j fluxo de potência ativa total da topologia corrente para cada caminho i j. f k i parte fracionária de nk i . f k j parte fracionária de nk j. gi geração de potência ativa da barra i. n∗i , x∗j valor corrente não inteiro da variável inteira escolhida para separar o PL do problema de programação linear inteiro misto no algoritmo Branch and Bound. P+ i pseudocusto de aumento da variável inteira do problema original. P−i pseudocusto de redução da variável inteira do problema original. P+ j pseudocusto de aumento da variável inteira usada na separação de um subproblema gerado pelo algoritmo Branch and Bound. P−j pseudocusto de redução da variável inteira usada na separação de um subproblema gerado pelo algoritmo Branch and Bound. vk+1 est valor estimado da função objetivo do subproblema descendente em que a variável inteira com valor corrente não inteiro assume um valor inteiro menor que o valor corrente da variável. vk+2 est valor estimado da função objetivo do subproblema descendente em que a variável inteira com valor corrente não inteiro assume um valor inteiro maior que o valor corrente da variável. vk est valor estimado da função objetivo da melhor solução inteira de um subproblema candidato k do algoritmo Branch and Bound. Vinc, v∗ solução incumbente do algoritmo Branch and Bound. vin f limitante inferior dos subproblemas de PL descendentes no algoritmo Branch and Bound. vk in f limitante inferior do subproblema de PL candidato PCk do algoritmo Branch and Bound. vPL valor ótimo da função objetivo para o problema de PL corrente no algoritmo Branch and Bound. vk+ PL valor ótimo do subproblema de PL descendente de k obtido com o aumento da variável n j. vk− PL valor ótimo do subproblema de PL descendente de k obtido com a redução da variável n j. vk PL valor ótimo do subproblema de PL relaxado k. x vetor das variáveis do problema de programação linear inteiro misto na forma padrão. xa(e) variáveis artificiais extras adicionadas nas restrições de desigualdade quando algumas variáveis de folga não podem fazer parte da SBF inicial. x0 valor da função objetivo do problema de programação linear inteiro misto na forma padrão. xa vetor de variáveis artificiais. xBi variável básica i do quadro simplex. xBm última variável básica do quadro simplex. xBr variável básica do quadro simplex escolhida para sair da base. xB variáveis básicas. xi um elemento do vetor de variáveis x. xa i uma variável artificial do vetor de variáveis artificiais xa. x f i uma variável de folga. x j variável não básica j do quadro simplex. xk variável não básica do quadro simplex escolhida para entrar na base. xN1 variáveis não básicas fixadas nos seus limites inferiores. xN2 variáveis não básicas fixadas nos seus limites superiores. y′0 j coeficientes de custo relativo da variável não básica j no quadro simplex após o processo de pivotagem. y0 j coeficiente de custo relativo da variável não básica j no quadro simplex. y0k coeficiente de custo relativo da variável não básica no quadro simplex escolhida para entrar na base. yi0 valor corrente da variável básica i no quadro simplex. yi j valor corrente do elemento do quadro simplex correspondente à linha da variável básica i e à coluna da variável não básica j. yik valor corrente do elemento do quadro simplex correspondente à linha da variável básica i e à coluna da variável não básica escolhida para entrar na base. ym0 valor corrente da última variável básica no quadro simplex. ym j valor corrente do elemento do quadro simplex correspondente à linha da última variável básica e à coluna da variável não básica j. ymk valor corrente do elemento do quadro simplex correspondente à linha da última variável básica e à coluna da variável não básica escolhida para entrar na base. yr0 valor corrente da variável básica no quadro simplex escolhida para sair da base. yr j valor corrente do elemento do quadro simplex correspondente à linha da variável básica escolhida para sair da base e à coluna da variável não básica j. yrk valor corrente do elemento pivô do quadro simplex que corresponde à linha da variável básica escolhida para sair da base e à coluna da variável não básica escolhida para entrar na base. z00 valor da função objetivo, antes da mudança de base, no algoritmo Dual Simplex Canali- zado. Variáveis inteiras ⌊n∗i ⌋ , ⌊ nk j ⌋ , ⌊ x∗j ⌋ maior inteiro em que a variável inteira com valor corrente não inteiro esco- lhida para separar o PL correspondente do problema de programação linear inteiro misto no algoritmo Branch and Bound está contida. ⌊ nk i ⌋ maior inteiro em que a variável inteira i com valor corrente não inteiro está contida, em um nó k da árvore Branch and Bound. ni j número de linhas que podem ser adicionados no caminho i j. n1 i j número de linhas adicionadas em paralelo às linhas existentes no caminho i j. n2 i j número de linhas adicionadas em caminhos novos i j. ni, nk j, x j variável inteira com valor corrente não inteiro escolhida para separar o PL corres- pondente do problema de programação linear inteiro misto no algoritmo Branch and Bound. nk i variável inteira i com valor corrente não inteiro em um nó k da árvore Branch and Bound. wi j,y variável binária correspondente à linha y candidata a ser adicionada ou não no caminho i j. SUMÁRIO 1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.1 O PROBLEMA DE PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.2 MODELAGEM MATEMÁTICA DO PROBLEMA DE PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO . . . . . . . . . . . 36 1.2.1 Modelo de Transportes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 1.2.2 Modelo CC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 1.2.3 Modelos Híbridos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 1.2.3.1 Modelo Híbrido Linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 1.2.3.2 Modelo Híbrido Não Linear . . . . . . . . . . . . . . . . . . . . . . . . . 40 1.2.4 Modelo Linear Disjuntivo . . . . . . . . . . . . . . . . . . . . . . . . . . 42 1.3 TÉCNICAS DE OTIMIZAÇÃO USADAS NO PROBLEMA DE PLANE- JAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO . . . . . 44 1.3.1 Métodos Clássicos de Otimização . . . . . . . . . . . . . . . . . . . . . . 44 1.3.2 Métodos Heurísticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 1.3.3 Meta-heurísticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 1.4 OBJETIVOS E JUSTIFICATIVA . . . . . . . . . . . . . . . . . . . . . . . 49 2 OS MODELOS DE TRANSPORTE E LINEAR DISJUNTIVO E A TÉCNICA BRANCH AND BOUND . . . . . . . . . . . . . . . . . . . . 51 2.1 O ALGORITMO DE GARVER . . . . . . . . . . . . . . . . . . . . . . . . 51 2.2 ALGORITMO BRANCH AND BOUND . . . . . . . . . . . . . . . . . . . 53 2.3 POSSÍVEIS MELHORIAS QUE PODEM SER INCLUÍDAS NO ALGO- RITMO BRANCH AND BOUND . . . . . . . . . . . . . . . . . . . . . . 57 2.3.1 O Conceito de Pseudocusto . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.3.2 Seleção do Subproblema Candidato . . . . . . . . . . . . . . . . . . . . . 60 2.3.3 Seleção da Variável de Separação . . . . . . . . . . . . . . . . . . . . . . 62 3 ALGORITMOS ESPECIALIZADOS NA ESTRUTURA BRANCH AND BOUND . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.1 PROBLEMAS DE PROGRAMAÇÃO LINEAR INTEIRA MISTA NA ES- TRUTURA BRANCH AND BOUND . . . . . . . . . . . . . . . . . . . . 65 3.2 QUADRO SIMPLEX ALTERNATIVO PARA VARIÁVEIS CANALIZADAS 67 3.2.1 Pivotagem do Quadro Simplex . . . . . . . . . . . . . . . . . . . . . . . . 69 3.3 ALGORITMO PRIMAL SIMPLEX CANALIZADO . . . . . . . . . . . . 70 3.3.1 Escolha da variável não básica que deve entrar na base . . . . . . . . . . 70 3.3.2 Se houver troca de base, escolher a variável básica que deve sair da base 71 3.3.2.1 Uma variável não básica em seu limite inferior é candidata a entrar na base71 32 SUMÁRIO 3.3.2.2 Uma variável não básica em seu limite superior é candidata a entrar na base73 3.3.3 Algoritmo Primal Simplex Canalizado . . . . . . . . . . . . . . . . . . . 75 3.3.4 Algoritmo Primal Simplex Canalizado de Duas Fases . . . . . . . . . . . 77 3.4 ALGORITMO DUAL SIMPLEX CANALIZADO . . . . . . . . . . . . . . 81 3.4.1 Variações dos valores da função objetivo e das variáveis básicas após a mudança de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.4.2 Escolha da variável básica que deve sair da base . . . . . . . . . . . . . . 84 3.4.3 Escolha da variável não básica que deve entrar na base . . . . . . . . . . 84 3.4.4 Algoritmo Dual Simplex Canalizado . . . . . . . . . . . . . . . . . . . . 88 3.5 IMPLEMENTAÇÃO COMPUTACIONAL DO ALGORITMO PRIMAL SIM- PLEX CANALIZADO NA ESTRUTURA BRANCH AND BOUND . . . . 90 3.5.1 Montagem do PL padrão para o modelo de transporte . . . . . . . . . . 91 3.5.2 Montagem do PL padrão para o modelo linear disjuntivo . . . . . . . . 97 3.6 IMPLEMENTAÇÃO COMPUTACIONAL DO ALGORITMO DUAL SIM- PLEX CANALIZADO NA ESTRUTURA BRANCH AND BOUND . . . . 106 3.7 EXEMPLOS ILUSTRATIVOS . . . . . . . . . . . . . . . . . . . . . . . . 107 3.7.1 Modelo de Transporte . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 3.7.2 Modelo Linear Disjuntivo . . . . . . . . . . . . . . . . . . . . . . . . . . 112 4 TESTES COM O ALGORITMO BRANCH AND BOUND ESPECIA- LIZADO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 4.1 SISTEMA DE GARVER DE 6 BARRAS E 15 CAMINHOS . . . . . . . . 115 4.2 SISTEMA IEEE(a) DE 24 BARRAS E 41 CAMINHOS . . . . . . . . . . . 116 4.3 SISTEMA SUL-BRASILEIRO DE 46 BARRAS E 79 CAMINHOS . . . . 117 4.4 RESULTADOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 5 CONCLUSÕES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 5.1 SUGESTÕES DE TRABALHOS FUTUROS . . . . . . . . . . . . . . . . . 125 REFERÊNCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 APÊNDICE A – SOLUÇÃO DO EXEMPLO ILUSTRATIVO . . . . . 133 ANEXO A – DADOS DOS SISTEMAS DE TRANSMISSÃO . . . . . . . 149 33 1 INTRODUÇÃO 1.1 O PROBLEMA DE PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO O problema de Planejamento da Expansão de Sistemas de Transmissão (PEST), em longo prazo, é um problema clássico de sistemas de energia elétrica, onde há diversas pesquisas sobre o tema. O planejamento adequado da expansão dos sistemas de transmissão possui grande importância no mercado de energia atual, pois esses sistemas são responsáveis por transportar a energia produzida pelas usinas até as subestações das concessionárias de distribuição de energia. Neste problema, dada uma configuração inicial para o sistema de transmissão (linhas candidatas, dados de geração e demanda, limites de operação, custos e restrições de investimento em um horizonte de planejamento), como pode ser visualizado na Figura 1, o objetivo é encontrar o plano ótimo da expansão do sistema, a um custo mínimo, definindo onde, quando e quais tipos de equipamentos e/ou recursos devem ser utilizados ao longo do horizonte de planejamento para que se satisfaça a demanda de energia exigida pelo mercado energético, seguindo especificações de qualidade e segurança do serviço impostas pelas agências reguladoras de cada país. Figura 1 – Sistema didático de 3 barras 1 2 3 ḡ1 = 80 MW 60 MW 20 MW f12f13 f23 f̄12 = 35 MW f̄13 = 40 MW f̄23 = 40 MW c12 = 3 c13 = 2 c23 = 2 γ12 = 1 3 γ13 = 1 2 γ23 = 1 2 Fonte – Escobar, Romero e Gallego (2010) Como a grande maioria dos problemas reais, o problema PEST, frequentemente é mode- lado como um problema de Programação Não Linear Inteiro Misto (PNLIM). O maior problema, ao se resolver um problema PEST modelado como um problema PNLIM, é que, geralmente, o problema não é convexo e não se pode garantir que ele satisfaça as condições de Karush-Kuhn- Tucker (KKT). Isso significa que não se pode garantir que uma determinada solução encontrada seja a solução ótima global do problema. Outro fator importante que dificulta muito a sua reso- lução é a sua natureza combinatória que proporciona o fenômeno da explosão combinatória em sistemas de grande porte, isto é, proporciona um número elevado de alternativas de investimento. Como todo problema de otimização matemática, o problema PEST é dividido em duas partes distintas: a modelagem matemática e as técnicas de otimização utilizadas na sua resolução. 34 Capítulo 1 INTRODUÇÃO A modelagem matemática tem como objetivo representar adequadamente problemas da vida real, através de modelos matemáticos, que, por sua vez, relacionam variáveis de decisão com relações matemáticas dos mais variados tipos e formas. Quando um problema real é modelado, o mesmo pode ser simulado e/ou solucionado, podendo, assim, obter previsões de seu comportamento sobre determinadas condições. A modelagem matemática pode representar um problema real de maneira mais exata ou mais simplificada, ficando evidente, que, quanto maior a precisão de sua representação, maior fica a complexidade de resolução do modelo matemático do problema real. Nesse contexto, é visto que deve haver um comprometimento do modelo matemático escolhido para representar o problema real com a técnica de otimização escolhida para resolvê-lo. A modelagem matemática deve representá-lo adequadamente e ainda permitir sua resolução através das técnicas de otimização com recursos computacionais atualmente existentes (ROMERO, 1999). O conceito de modelagem matemática adequada muda com o tempo, pois, com a continuidade das pesquisas na área de otimização desenvolvendo novas técnicas e com a rápida evolução dos computadores, modelos que antes eram considerados de grande complexidade podem tornar-se adequados em outro contexto. Na literatura especializada, são apresentados vários modelos de rede elétrica como o modelo de transportes, modelo de corrente contínua (CC), modelos híbridos, modelo linear disjuntivo (LD), modelo de corrente alternada (CA), etc. A Seção 1.2, apresenta de forma mais detalhada, os modelos CC, transportes, híbridos e LD. Para cada tipo de modelo existe uma técnica de otimização mais adequada. A Seção 1.3 faz uma breve descrição de algumas técnicas de solução empregadas na resolução do problema PEST, dentre elas encontram-se os algoritmos de Decomposição de Benders, algoritmos da família Branch and Bound (B&B), algoritmos heurísticos construtivos, algoritmos simulated annealing (SA), algoritmos genéticos (GA) e evolutivos (EA), tabu search (TS), GRASP, particle swarm optimization (PSO), ant colony (AC), etc. (LATORRE et al., 2003). No Capítulo 2, é apresentado o algoritmo B&B de forma mais detalhada, pois este é o algoritmo escolhido como técnica de resolução do problema PEST modelado através do modelo de transportes e LD. Em relação ao horizonte de planejamento, o problema PEST pode ser tratado de duas formas: planejamento estático e planejamento multiestágio ou dinâmico. Naquele, considera-se somente um único período no horizonte de planejamento. Neste, o horizonte de planejamento é dividido em dois ou mais períodos ou estágios, procedimento que facilita a tomada de decisão em etapas e possibilita ao final de cada estágio a revisão do planejamento para estágios posteri- ores. No planejamento dinâmico da expansão de sistemas de transmissão, para cada estágio é necessário conhecer a geração e a demanda em cada barra do sistema. Nos modelos utilizados para representar o problema PEST, podem ser adicionadas as exigências de operação segura, as quais produzem um modelo matemático que considera contingências. Em Silva et al. (2005), é apresentado o modelo CC que considera contingências do tipo (N−1), isto é, o sistema deve ser expandido de forma que opere adequadamente se 1.1 O PROBLEMA DE PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO 35 for retirada uma linha de transmissão do sistema elétrico devido às contingências. Outra forma alternativa de considerar a expansão segura consiste em abandonar a estratégia (N−1) e usar a técnica proposta no trabalho de Choi et al. (2005) para modelar o processo de expansão. Os modelos também podem ser generalizados para considerar incertezas na demanda futura. Essa demanda, no planejamento tradicional, em cada barra é determinística, isto é, assume um valor determinado através de técnicas de previsão de demanda e, para o problema de planejamento, representa um dado de entrada. Entretanto, pode-se considerá-la como uma variável em torno de um valor de referência (SILVA et al., 2006). Assim, deve-se expandir o sistema de forma que se levem em conta as incertezas na demanda futura. Existem ainda outras exigências que podem ser incorporadas no modelo matemático, tais como as exigências de operação em mercado competitivo do sistema expandido. Isso implica que o sistema deve ser expandido de forma que opere adequadamente no horizonte de planejamento atendendo às exigências de operação em mercado competitivo. Em outras palavras, esse sistema não deve apresentar congestão quando opera com as exigências de operação do mercado elétrico (FANG; HILL, 2003). Nesta pesquisa, é apresentada uma nova proposta de melhoria do algoritmo B&B em- pregado na resolução do problema PEST, quando, este é modelado como um problema de programação linear inteiro misto (PLIM). São considerados somente os modelos de transpor- tes e LD básicos, mas a metodologia é desenvolvida de forma que, no futuro, seja estendida para o planejamento multiestágio e que também se considerem exigências de operação segura, incertezas na demanda futura, exigências de operação em mercado competitivo, etc. A pro- posta apresentada nesse trabalho usa o algoritmo dual simplex canalizado (DSC) para fazer a reotimização dos subproblemas gerados pelo algoritmo B&B, durante o processo de resolução, através do quadro simplex ótimo do problema original com a restrição de integralidade relaxada. Dessa forma, consegue-se uma economia de recursos computacionais e tempo de processamento durante a resolução do problema. Para a resolução do problema original com a restrição de integralidade relaxada foi escolhido o algoritmo primal simplex canalizado (PSC) juntamente com uma estratégia para diminuir o número de variáveis artificiais canalizadas que devem ser inseridas no problema inicial. Nas seguintes seções deste capítulo, é feita uma revisão dos principais modelos e técnicas de resolução empregados no problema PEST. Na última seção deste mesmo capítulo, são apresentados os objetivos e justificativas dessa pesquisa. O Capítulo 2 apresenta de forma mais detalhada o algoritmo B&B e também o motivo para a escolha dos algoritmos PSC e DSC para atuarem em conjunto com ele. O Capítulo 3, primeiramente, apresenta o funcionamento dos algoritmos PSC e DSC em suas formas padrão; posteriormente, são apresentadas características e peculiaridades da implementação computacional dos algoritmos na resolução do problema PEST. No Capítulo 4, são apresentados os testes realizados com o algoritmo B&B especializado juntamente com os resultados obtidos na resolução dos sistemas de transmissão de Garver com 36 Capítulo 1 INTRODUÇÃO 6 barras e 15 caminhos, IEEE(a) com 24 barras e 41 caminhos, e, o Sul-Brasileiro de 46 barras e 79 caminhos. Finalmente, o Capítulo 5 apresenta as conclusões obtidas nessa pesquisa. O Apêndice A apresenta o passo a passo da resolução de um sistema didático de 3 barras e caminhos utilizando a proposta apresentada nessa pesquisa. O Anexo A apresenta os dados de entrada dos sistemas de transmissão resolvidos nessa pesquisa. 1.2 MODELAGEM MATEMÁTICA DO PROBLEMA DE PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO A modelagem matemática pode considerar vários aspectos do problema PEST, dentre eles, modelagem da rede elétrica, forma de planejamento, exigências de segurança, riscos, incertezas na demanda futura, formas de operação devido às regras do mercado de energia elétrica, etc. A modelagem matemática ideal para o problema PEST deveria representar o problema através de relações matemáticas de fluxo de carga CA, as quais levam em consideração a geração de cargas ativa e reativa. Esse tipo de modelagem tem sido pouco explorado tanto que o modelo CA foi uma das últimas modelagens do problema PEST a ser desenvolvido devido a sua alta complexidade e a suas dificuldades de solução. A primeira publicação relevante com o modelo CA foi apresentada por Rider, Garcia e Romero (2007), onde os autores utilizaram um algoritmo heurístico construtivo (AHC) para resolver o problema PEST, juntamente com o método de pontos interiores (MPI) para resolver os problemas de programação não linear (PNL) gerados no processo iterativo do AHC. 1.2.1 Modelo de Transportes O modelo de transportes foi a primeira proposta sistemática de modelagem do PEST proposto por Garver (1970) em cujo trabalho sugeriu-se a utilização de modelos diferentes para problemas de operação e de planejamento. Sua proposta tornou-se fundamental em pesquisas do problema PEST, pois era a única forma de otimizar o problema com as técnicas disponíveis na época. Devido às dificuldades da utilização do fluxo de carga CA, Garver sugeriu a utilização de modelos matemáticos mais relaxados, também chamados modelos de síntese de rede, que permitem encontrar topologias atrativas para o crescimento do sistema elétrico, mesmo que sejam aproximadas. O modelo de transportes não utiliza a Lei das Tensões de Kirchhoff (LTK) e, portanto, é um problema de programação linear (PL). Outro fato importante é a utilização de variáveis inteiras na sua modelagem, o que acarreta uma maior complexidade de solução. Assim, diante dessas observações, a modelagem matemática do problema PEST com o modelo de transportes é um problema PLIM e, mesmo com a característica de ser o modelo de rede mais elementar, em sistemas de grande porte, pode apresentar dificuldades na sua resolução. 1.2 MODELAGEM MATEMÁTICA DO PROBLEMA DE PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO 37 O problema PEST, usando o modelo de transportes, pode ser modelado como um pro- blema de PLIM (LATORRE et al., 2003; SILVA, 2013; GALLEGO; MONTICELLI; ROMERO, 1998b; SILVA; GIL; AREIZA, 2000; ESCOBAR, 2008), como mostrado em (1): min v = ∑ i j∈Ωl ci jni j (1a) s.a. ∑ ji∈Ωl f ji− ∑ i j∈Ωl fi j +gi = di ∀ i ∈Ωb (1b) | fi j| ≤ (ni j +n0 i j) f i j ∀ i j ∈Ωl (1c) 0≤ gi ≤ gi ∀ i ∈Ωb (1d) 0≤ ni j ≤ ni j ∀ i j ∈Ωl (1e) ni j ∈ Z ∀ i j ∈Ωl. (1f) A função objetivo (1a) representa o custo do investimento na rede de transmissão devido à adição de novas linhas. A restrição (1b) representa o conjunto de equações de balanço de potência ativa, correspondente à Lei das Correntes de Kirchhoff (LCK). A restrição (1c) representa as restrições de capacidade de transmissão dos caminhos (linhas e/ou transformadores). Na restrição (1c), o valor absoluto é necessário, pois o fluxo de potência ativa é bidirecional. A restrição (1d) define os limites de geração em cada barra. A restrição (1e) representa os limites do número de linhas que podem ser instalados em cada caminho i j. A restrição (1f) representa o número inteiro de linhas que deve ser adicionado em cada caminho i j, constituindo a maior fonte de complexidade do problema. As grandes vantagens trazidas pelo modelo de transportes são que, sendo um PLIM, existem várias técnicas que resolvem esse tipo de problema (algumas garantem até a otimalidade da solução) e, praticamente, não existe diferença em modelar problemas conexos ou altamente ilhados, já que a técnica de otimização resolve esse tipo de problema da mesma forma que em sistemas conexos. A principal desvantagem de usar o modelo de transportes é que, no contexto atual, com o avanço no campo computacional, por se tratar do modelo de rede mais elementar e não considerar todas as características físicas do problema, geralmente a solução ótima encontrada pode assumir valores distantes da realidade e dos valores encontrados por outros modelos mais sofisticados. 1.2.2 Modelo CC Posteriormente ao modelo de transporte, foi desenvolvido o modelo CC que é um problema PNLIM. Atualmente, o modelo CC é considerado a modelagem matemática ideal para o PEST por vários motivos. Entre os principais motivos, citam-se: (i) as dificuldades de utilizar o modelo CA; (ii) a existência de várias técnicas de otimização que resolvem o problema PEST utilizando o modelo CC (ROMERO, 1999; LATORRE et al., 2003; LEE et al., 2006) (iii) a 38 Capítulo 1 INTRODUÇÃO existência de sistemas em que não se conhece a solução ótima mesmo sendo considerado como modelo ideal e possuindo várias pesquisas em que se aplicam diversas técnicas de otimização para sua resolução. Esse modelo foi e continua sendo amplamente pesquisado pela comunidade científica. Sendo uma generalização do fluxo de carga CC, o sistema elétrico deve operar obede- cendo às duas leis de Kirchhoff. Esse modelo, o qual considera apenas a potência ativa no sistema elétrico, também é uma aproximação, com precisão aceitável, do modelo CA, sendo, portanto, um modelo simplificado da rede de transmissão. Mesmo sendo um modelo aproxi- mado, o modelo matemático é um problema de PNLIM de alta complexidade. A não linearidade do modelo CC eleva consideravelmente o esforço computacional no processo de solução, e tam- bém, neste caso é muito difícil garantir que o problema seja convexo, e sem essa garantia não é possível afirmar que a solução encontrada é a solução ótima global do problema. Outro fator que aumenta a complexidade do processo de solução do modelo CC é a utilização de variáveis inteiras na sua modelagem. Para sistemas de grande porte não se conhecem soluções ótimas, mas sim soluções aproximadas de boa qualidade. O problema PEST, utilizando o modelo CC, pode ser modelado como um problema de PNLIM, como mostrado em (2): min v = ∑ i j∈Ωl ci jni j (2a) s.a. ∑ ji∈Ωl f ji− ∑ i j∈Ωl fi j +gi = di ∀ i ∈Ωb (2b) fi j = (ni j +n0 i j) ( θi−θ j ) xi j ∀ i ∈Ωb (2c) | fi j| ≤ (ni j +n0 i j) f i j ∀ i j ∈Ωl (2d) 0≤ gi ≤ gi ∀ i ∈Ωb (2e) 0≤ ni j ≤ ni j ∀ i j ∈Ωl (2f) ni j ∈ Z ∀ i j ∈Ωl (2g) θk = 0 k ∈ barra de referência. (2h) A função objetivo (2a) representa o custo do investimento na rede de transmissão devido à adição de novas linhas. A restrição (2b) representa o conjunto de equações de balanço de potência ativa para cada barra do sistema elétrico (corresponde à LCK). A restrição (2c) representa o conjunto de equações relacionadas com a aplicação da LTK, uma relação para cada laço fundamental (laço formado por uma linha de transmissão conectada entre duas barras e as conexões dessas barras com a terra através das cargas (demanda)). Esse tipo de restrição introduz a não linearidade no modelo matemático, introduzindo nele uma fonte de complexidade. A restrição (2d) representa as restrições de capacidade de transmissão dos caminhos (linhas e/ou transformadores). Na restrição (2d), o valor absoluto é necessário, pois o fluxo de potência ativa 1.2 MODELAGEM MATEMÁTICA DO PROBLEMA DE PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO 39 é bidirecional. A restrição (2e) define os limites de geração em cada barra (se gi = 0, então a barra i é consumidora, caso contrário, a barra i pode ser geradora). A restrição (2f) representa os limites do número de linhas que podem ser instalados em cada caminho i j. A restrição (2g) representa o número inteiro de linhas que deve ser adicionado, constituindo outra fonte de complexidade do problema. A restrição (2h) implica que, em uma determinada barra de referência k, o ângulo θk = 0. 1.2.3 Modelos Híbridos Pelas dificuldades de resolução apresentadas pelo modelo CC, na época foram criados novos modelos mais simplificados desse tipo de modelo e mais sofisticados que o modelo de transportes. Neste grupo de modelos, encontram-se os modelos híbridos linear e não linear que foram utilizados por vários autores para realizar o planejamento; dentre eles, destaca-se o trabalho apresentado por Villasana, Garver e Salon (1985). Os modelos híbridos são versões relaxadas do modelo CC que tentam contornar as dificuldades por este apresentadas. Nos modelos híbridos, somente uma parcela do sistema elétrico deve satisfazer as duas leis de Kirchhoff. A utilização desse tipo de modelo tem como objetivo encontrar soluções mais próximas do modelo CC, sem aumentar a complexidade do problema. 1.2.3.1 Modelo Híbrido Linear O modelo híbrido linear (MHL), apresentado por Villasana, Garver e Salon (1985), como o próprio nome diz, é uma modelagem linear do problema PEST. O problema resultante, ao utilizar a modelagem híbrida linear, é um problema PLIM. Essa modelagem é uma versão relaxada do modelo CC e mais sofisticada que o modelo de transportes. A formulação híbrida linear exige que todas as linhas (existentes e adicionadas) devem satisfazer a LCK e somente os laços existentes devem respeitar a LTK. Neste contexto, equivale considerar dois sistemas superpostos, a configuração base, que deve satisfazer as duas leis de Kirchhoff, e o sistema formado pelas linhas candidatas à adição, que devem satisfazer somente a LCK. Na época em que foi publicado o trabalho de Villasana, Garver e Salon (1985), os recursos computacionais existentes eram limitados, e também, não havia começado a aplicação dos métodos exatos de resolução de problemas com variáveis inteiras. Diante dessas condições, a ideia foi usar um AHC para resolver o problema PEST, em que, a cada iteração, era resolvido um PL e, através de um índice de sensibilidade, escolhia-se a linha candidata mais atrativa para compor a topologia base do sistema. Desse modo, ao final de cada iteração do AHC, a topologia base do sistema de transmissão era acrescida em uma linha, e, na próxima iteração, a última linha adicionada também passava a respeitar a LTK. Ao término do processo iterativo do AHC, era obtida uma boa solução para o modelo híbrido linear, e, consequentemente, também uma 40 Capítulo 1 INTRODUÇÃO boa solução para o modelo CC, onde as linhas existentes e construídas respeitavam as duas leis de Kirchhoff. O problema PEST, utilizando o modelo híbrido linear, pode ser modelado como um problema de PLIM, como mostrado em (3): min v = ∑ i j∈Ωl ci jni j (3a) s.a. ∑ ji∈Ωl f ji− ∑ i j∈Ωl fi j + ∑ ji∈Ω0 l f 0 ji− ∑ i j∈Ω0 l f 0 i j +gi = di ∀ i ∈Ωb (3b) f 0 i j = n0 i j ( θi−θ j ) xi j ∀ i j ∈Ω0 l (3c) ∣ ∣ f 0 i j ∣ ∣≤ n0 i j f 0 i j ∀ i j ∈Ω0 l (3d) ∣ ∣ fi j ∣ ∣≤ ni j f i j ∀ i j ∈Ωl (3e) 0≤ gi ≤ gi ∀ i ∈Ωb (3f) 0≤ ni j ≤ ni j ∀ i j ∈Ωl (3g) ni j ∈ Z ∀ i j ∈Ωl. (3h) A função objetivo (3a) representa o custo do investimento na rede de transmissão devido à adição de novas linhas. A equação (3b) representa as equações de balanço de potência ativa (corresponde à LCK). A equação (3c) corresponde à LTK, válida para este modelo apenas nas linhas existentes. As equações (3d) e (3e) representam, respectivamente, as equações de capacidade de transmissão das linhas existentes e a capacidade de transmissão das linhas que devem ser adicionadas. Nas equações (3d) e (3e), o valor absoluto é necessário, pois o fluxo de potência ativa é bidirecional. A equação (3f) define os limites de geração em cada barra (se gi = 0, então a barra i é consumidora, caso contrário, a barra i pode ser geradora). A equação (3g) representa os limites do número de linhas que podem ser instaladas em cada caminho i j. A equação (3h) representa o número inteiro de linhas que deve ser adicionado. A equação (3h) representa a maior fonte de complexidade do problema. O modelo híbrido linear é um problema de PLIM com complexidade próxima do modelo de transportes. Sendo assim, podem-se utilizar as mesmas técnicas de otimização usadas para resolver o modelo de transportes. Além disso, o modelo híbrido linear é uma versão relaxada do modelo CC, logo é evidente que o problema resultante é uma representação menos adequada do problema real e, portanto, a solução pode estar distante da solução encontrada utilizando o modelo CC. 1.2.3.2 Modelo Híbrido Não Linear O modelo híbrido não linear (MHNL) é uma proposta a qual utiliza características do modelo CC e do modelo de transportes, com o objetivo de contornar alguns problemas 1.2 MODELAGEM MATEMÁTICA DO PROBLEMA DE PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO 41 apresentados por esses modelos. A modelagem do problema PEST, através do modelo híbrido não linear, na sua formula- ção mais pura, especifica que uma parcela do sistema elétrico correspondente aos caminhos que já possuem linhas na configuração base e também as linhas que são adicionadas em paralelo a essas linhas devem satisfazer as duas leis de Kirchhoff. Outra parcela a qual corresponde aos novos caminhos devem satisfazer somente a LCK. O problema PEST, utilizando o modelo híbrido não linear, pode ser modelado como um problema de PNLIM, como mostrado em (4): min v = ∑ i j∈Ω1 l ci jn 1 i j + ∑ i j∈Ω2 l ci jn 2 i j (4a) s.a. ∑ ji∈Ω2 l f 2 ji− ∑ i j∈Ω2 l f 2 i j + ∑ ji∈Ω1 l f 1 ji− ∑ i j∈Ω1 l f 1 i j +gi = di ∀ i ∈Ωb (4b) f 1 i j = (n1 i j +n0 i j) ( θi−θ j ) xi j ∀ i j ∈Ω1 l (4c) | f 1 i j| ≤ (n1 i j +n0 i j) f 1 i j ∀ i j ∈Ω1 l (4d) | f 2 i j| ≤ n2 i j f 2 i j ∀ i j ∈Ω2 l (4e) 0≤ gi ≤ gi ∀ i ∈Ωb (4f) 0≤ n1 i j ≤ n1 i j ∀ i j ∈Ω1 l (4g) 0≤ n2 i j ≤ n2 i j ∀ i j ∈Ω2 l (4h) n1 i j ∈ Z ∀ i j ∈Ω1 l (4i) n2 i j ∈ Z ∀ i j ∈Ω2 l . (4j) A função objetivo (4a) representa o custo do investimento na rede de transmissão devido à adição de novas linhas. A equação (4b) representa as equações de balanço de potência ativa (corresponde à LCK). A equação (4c) define a não linearidade do modelo híbrido não linear (corresponde à LTK). As equações (4d) e (4e) representam, respectivamente, as equações de capacidade de transmissão das linhas adicionadas em paralelo às já existentes e nas linhas adicionadas em novos caminhos. Nas equações (4d) e (4e), o valor absoluto é necessário, pois o fluxo de potência ativa é bidirecional. A equação (4f) define os limites de geração em cada barra (se gi = 0, então a barra i é consumidora, caso contrário, a barra i pode ser geradora). As equações (4g) e (4h) representam os limites do número de linhas que podem ser instalados em cada caminho i j. As equações (4i) e (4j) representam, respectivamente, o número inteiro de linhas que deve ser adicionado em paralelo às já existentes e o número inteiro de linhas que deve ser adicionado nos novos caminhos. As equações (4i) e (4j) representam outra fonte de complexidade do problema. O problema PEST definido em (4) representa um problema de PNLIM, visto que as restrições referentes à LTK são não lineares, e as variáveis n1 i j e n2 i j são inteiras. Em particular, 42 Capítulo 1 INTRODUÇÃO apresenta complexidade parecida ao do modelo CC. Nesse contexto, para encontrar a solução do problema através do modelo híbrido não linear, é necessário utilizar as mesmas técnicas de otimização empregadas no modelo CC e, portanto, pode ser mais conveniente trabalhar diretamente com o modelo CC, considerado ideal. 1.2.4 Modelo Linear Disjuntivo Uma alternativa recente de modelagem do problema PEST foi apresentada por Bahiense et al. (2001), o modelo LD, que é um problema PLIM, ou, mais especificamente, um problema de Programação Linear Binário Misto (PLBM) cuja solução ótima é a mesma do modelo CC, pois o tipo de linearização utilizada no modelo LD não altera a solução ótima do problema. A utilização do modelo LD garante a convergência para a solução ótima através de técnicas de resolução atuais. Em geral, sempre é possível transformar um problema não linear quadrático com variá- veis inteiras e reais num problema linear com variáveis binárias e reais usando uma transformação que permite “separar” os termos quadráticos em relações lineares (SILVA, 2013). A formulação do modelo LD parte da formulação do modelo CC, em que se separam os fluxos de potência ativa das linhas existentes na configuração base e das linhas candidatas. Esse procedimento implica na modificação da restrição (2b) e na divisão das restrições (2c) e (2d) em duas novas restrições cada. Salienta-se que a forma de calcular o fluxo de potência ativa nas linhas existentes na configuração base permanece a mesma. A variável inteira ni j é transformada em um conjunto Y de variáveis binárias wi j,y; assim, a variável inteira ni j passa a ser representada por ∑y∈Y wi j,y. Para melhorar o desempenho do algoritmo B&B na resolução do problema, é necessário adicionar a restrição (5) garantindo a alocação sequencial das linhas y. wi j,y ≤ wi j,y−1 ∀ i j ∈Ωl, ∀y ∈ Y |y > 1 (5) Para transformar a restrição não linear (2c) em restrições lineares, é necessário substituí- la pelas restrições (6) e (7): ∣ ∣xi j fi j,y− ( θi−θ j ) ∣ ∣≤M ( 1−wi j,y ) ∀ i j ∈Ωl, ∀y ∈ Y (6) | fi j,y| ≤ wi j,y f i j ∀ i j ∈Ωl, ∀y ∈ Y (7) onde M é um número suficientemente grande. Vale notar que, se wi j,y = 1 (a linha y é instalada no caminho i j), então fi j,y = (θi−θ j) xi j e − f̄i j ≤ fi j,y ≤ f̄i j; caso contrário, fi j,y = 0, e a diferença angular é −M ≤ θi−θ j ≤M. Portanto, o modelo LD pode ser modelado como um problema PLBM, como apresentado em (8): 1.2 MODELAGEM MATEMÁTICA DO PROBLEMA DE PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO 43 min v = ∑ i j∈Ωl ci j ∑ y∈Y wi j,y (8a) s.a. ∑ ji∈Ωl ( ∑ y∈Y f ji,y+ f 0 ji ) − ∑ i j∈Ωl ( ∑ y∈Y fi j,y+ f 0 i j ) +gi = di ∀ i ∈Ωb (8b) f 0 i j = n0 i j ( θi−θ j ) xi j ∀ i j ∈Ω0 (8c) | f 0 i j| ≤ n0 i j f 0 i j ∀ i j ∈Ω0 (8d) ∣ ∣xi j fi j,y− ( θi−θ j ) ∣ ∣≤M ( 1−wi j,y ) ∀ i j ∈Ωl, ∀y ∈ Y (8e) | fi j,y| ≤ wi j,y f i j ∀ i j ∈Ωl, ∀y ∈ Y (8f) 0≤ gi ≤ gi ∀ i ∈Ωb (8g) ∑ y∈Y wi j,y ≤ ni j ∀ i j ∈Ωl (8h) wi j,y ≤ wi j,y−1 ∀ i j ∈Ωl, ∀y ∈ Y |y > 1 (8i) wi j,y ∈ {0, 1} ∀ i j ∈Ωl, ∀y ∈ Y (8j) θk = 0 k ∈ barra de referência. (8k) A função objetivo (8a) representa o custo do investimento na rede de transmissão devido à adição de novas linhas. A restrição (8b) representa o conjunto de equações que correspondem à LCK, uma equação para o balanço de potência ativa em cada barra i. As restrições (8c) e (8d) correspondem, respectivamente, à LTK e ao limite de fluxo nas linhas existentes. As restrições (8e) e (8f) representam, respectivamente, à LTK e o limite de fluxo em linhas novas. Em (8d) e (8f), o valor absoluto é necessário, pois o fluxo de potência ativa é bidirecional. A restrição (8g) define os limites de geração em cada barra i. A restrição (8h) representa o limite do número de linhas que podem ser instaladas em cada caminho i j. A restrição (8i) é necessária para garantir a alocação sequencial das linhas y. Na equação (8j), a variável wi j,y deve ser binária e representa a instalação ou não de uma linha em cada caminho i j. Essa restrição representa a maior fonte de complexidade do modelo LD. A restrição (8k) implica que, em uma determinada barra de referência k, o ângulo θk = 0. A utilização desse modelo apresenta vantagens e desvantagens na resolução do problema PEST em relação ao modelo CC. Sua vantagem é a sua linearidade permitindo a utilização de algoritmos de resolução eficientes existentes na atualidade. Já a sua principal desvantagem é o acréscimo de muitas variáveis binárias no problema o que diminui a eficiência em sistemas de grande porte. Outra desvantagem é como encontrar o parâmetro M ideal para cada ramo do sistema, de modo a garantir o grau de liberdade da diferença angular. Uma análise detalhada da utilização do modelo LD é apresentada em Binato (2000). Em Binato, Oliveira e Araujo (2001), para calcular o valor mínimo do parâmetro M, é apresentada uma metodologia baseada na teoria de grafos, a qual resolve problemas de caminho mínimo e máximo. 44 Capítulo 1 INTRODUÇÃO 1.3 TÉCNICAS DE OTIMIZAÇÃO USADAS NO PROBLEMA DE PLA- NEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO Como mencionado anteriormente, deve haver um comprometimento entre o modelo matemático e a técnica de otimização; sendo assim, em um determinado contexto e época, para cada modelo existe uma técnica de otimização mais adequada. Latorre et al. (2003) faz um levantamento bibliográfico das principais técnicas de otimização utilizadas na resolução do problema PEST. As técnicas de otimização são divididas em dois grupos: (a) métodos exatos, também chamados de métodos clássicos de otimização, e (b) métodos aproximados. Os métodos aproximados, por sua vez, podem ser divididos em dois subgrupos: (i) as heurísticas e as (ii) meta-heurísticas. 1.3.1 Métodos Clássicos de Otimização Entre os métodos clássicos de otimização mais conhecidos, dedicados à programação inteira, estão o método de decomposição de Benders e os métodos da família B&B. Esses tipos de algoritmos garantem a otimalidade da solução para problemas lineares e também para problemas não lineares, desde que sejam convexos. Esses algoritmos apresentam grande eficiência em problemas pequenos e de baixa complexidade. Entretanto, em sistemas de grande porte, apresentam dificuldades de convergência e elevado esforço computacional. Para problemas não lineares, há um decréscimo acentuado da eficiência desses algorit- mos, pois é necessário resolver internamente problemas de PNL, cujos métodos empregados na resolução demandam um esforço computacional mais elevado. Outro fator complicante em problemas não lineares é garantir a sua convexidade; sem essa garantia, não é possível afirmar que a solução encontrada no final do processo iterativo é ótima global do problema. Muitas pesquisas utilizaram o algoritmo de decomposição de Benders; na resolução do problema PEST, entre as principais, estão Granville e Pereira (1985), Pereira et al. (1985), Pereira (1987), Romero e Monticelli (1994a), Romero e Monticelli (1994b), Binato (2000) e Haffner et al. (2000). Basicamente, a ideia do algoritmo de decomposição de Benders para resolver um PLIM ou PNLIM é resolver, em cada iteração, primeiramente um PL ou PNL, chamado no algoritmo de problema escravo, e, posteriormente, resolver o problema mestre que é um problema de programação inteira (PI). Através da teoria de dualidade em programação linear, é possível demonstrar que qualquer PLIM pode ser escrito como um problema de programação linear inteiro (PLI), cujas restrições dependem do valor numérico de um ponto ou raio extremo do poliedro convexo. Isso implica que o número de restrições é tão grande quanto o número de pontos e raios extremos existentes no poliedro convexo. O algoritmo de decomposição de Benders consegue evitar esse último inconveniente gerando somente um conjunto reduzido de 1.3 TÉCNICAS DE OTIMIZAÇÃO USADAS NO PROBLEMA DE PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO 45 restrições essenciais do PI, de tal modo que a solução do problema resultante é equivalente à solução do problema original (GALLEGO; ESCOBAR; ROMERO, 2007). O algoritmo de decomposição de Benders aplicado na resolução do PEST decompõe o problema original em dois subproblemas: (i) subproblema de investimento, correspondente ao problema mestre do algoritmo e (ii) subproblema de operação, correspondente ao problema escravo. Durante o processo de resolução, o problema mestre informa ao escravo sobre as decisões de investimento (adição de linhas), e o escravo informa ao mestre as necessidades do sistema de transmissão (cortes). O artigo apresentado por Romero e Monticelli (1994a) utilizou o algoritmo de decom- posição de Benders na resolução do problema PEST e foi o primeiro a apresentar as soluções ótimas globais do modelo CC para os sistemas de Garver e Sul-Brasileiro, ambos com valores de geração estática e variável. Esse fato gerou grandes expectativas sobre a aplicação do algoritmo de decomposição de Benders na resolução do problema PEST, mas mostrou-se ineficiente na resolução de problemas de grande porte (BINATO, 2000; HAFFNER et al., 2000; ROMERO; MONTICELLI, 1994a). Várias pesquisas utilizaram os algoritmos da família B&B para resolver o problema PEST, dentre elas, Shin e Park (1993), Levi (1995), Haffner et al. (2000), Haffner et al. (2001), Asada et al. (2005), Choi et al. (2005) e Rider, Garcia e Romero (2008). A Seção 2.2 faz uma apresentação mais detalhada do algoritmo B&B. A ideia geral para resolver um PLIM ou PNLIM, através do algoritmo B&B, é dividir o problema original, com a restrição de integralidade relaxada, em vários subproblemas des- cendentes mais restritos, cuja única diferença do problema original são os limites das variáveis inteiras que separaram os subproblemas antecessores. Geralmente o algoritmo B&B é ilustrado por uma árvore, onde os nós representam os subproblemas descendentes, e o ramos são as mudanças de limites das variáveis inteiras. Devido ao fator combinatorial dos problemas, para alcançar a solução do mesmo, de- veriam ser resolvidas todas as combinações possíveis de subproblemas. O algoritmo B&B consegue contornar esse problema, através das propriedades de sondagem, que identificam quando não é mais necessário dividir determinados subproblemas. O processo iterativo do algo- ritmo B&B termina quando não existem mais subproblemas para serem resolvidos, e a solução do problema original é a melhor solução encontrada no processo iterativo. Os trabalhos de Haffner et al. (2000) e Haffner et al. (2001) apresentam um algoritmo B&B, para resolver o problema PEST, modelado a partir do modelo de transportes. Esses trabalhos mostraram que o algoritmo B&B possui maior eficiência comparado ao algoritmo de decomposição de Benders. 46 Capítulo 1 INTRODUÇÃO 1.3.2 Métodos Heurísticos Existem vários trabalhos na literatura que utilizam algoritmos heurísticos para resolver o problema PEST, como Garver (1970), Pereira e Pinto (1985) e Villasana, Garver e Salon (1985). Basicamente, um algoritmo heurístico é um conjunto de procedimentos simples, muitas vezes baseados no senso comum, que encontram soluções de boa qualidade (não necessariamente a ótima) de forma rápida e simples. De maneira geral, a utilização de algoritmos heurísticos torna-se interessante nos seguintes casos: (i) quando não existem métodos exatos para resolver determinado problema; (ii) quando não é necessário encontrar a solução ótima, e uma solução de boa qualidade já é suficiente; (iii) quando o tempo é um fator essencial, como, por exemplo, nos problemas que exigem solução em tempo real; e (iv) quando são utilizados para encontrar soluções que servem de ponto de partida para outros métodos. O primeiro algoritmo de importância para o PEST foi o Algoritmo de Garver (AG) para o modelo de transportes apresentado por Garver (1970). Garver (1970) sugere resolver o modelo de transportes com integralidade relaxada, isto é, resolver o PL resultante da modelagem, para que se possa identificar qual linha é mais atrativa para ser adicionada ao sistema elétrico. A ideia de Garver pode ser estendida para os outros modelos e também generalizada para o planejamento dinâmico da expansão de sistemas de transmissão como apresentados por Romero et al. (2003), Rider, Garcia e Romero (2004) e Rider, Garcia e Romero (2007). Os algoritmos heurísticos apresentam a vantagem de serem rápidos e robustos. No entanto, esses algoritmos só apresentam soluções de boa qualidade e, raramente, encontram a solução ótima em sistemas de grande porte. Além disso, não fornecem informações sobre a qualidade da solução obtida. Atualmente, os algoritmos heurísticos ainda representam um interessante tema de pes- quisa, e as soluções encontradas por eles podem ser usadas como base para algoritmos que demandam maior esforço computacional, como as meta-heurísticas. 1.3.3 Meta-heurísticas No final da década de 80, iniciou-se a utilização de uma nova classe de algoritmos heurísticos chamados de meta-heurísticas para a resolução de problemas complexos de sistemas de energia elétrica. A utilização foi intensificada a partir da década de 90 e, atualmente, ainda está fortemente presente nas pesquisas, muitas vezes, sendo a única forma viável de resolver determinados tipos de problemas. As meta-heurísticas são diferentes dos algoritmos heurísticos tradicionais, geralmente mais eficientes e com esforço computacional variável. A definição apresentada no livro de Glover e Kochenberger (2003) diz que as meta-heurísticas são métodos de resolução que conduzem uma interação entre procedimentos de melhora local e estratégias de alto nível para criar um processo 1.3 TÉCNICAS DE OTIMIZAÇÃO USADAS NO PROBLEMA DE PLANEJAMENTO DA EXPANSÃO DE SISTEMAS DE TRANSMISSÃO 47 capaz de escapar de ótimos locais e exercer uma busca robusta em um espaço de soluções. A estratégia básica das meta-heurísticas é realizar procedimentos específicos de cada tipo de algoritmo os quais desempenham um número determinado de transições dentro do espaço de soluções factíveis (para algumas meta-heurísticas também soluções infactíveis), con- vencionalmente chamado de espaço de busca. Portanto, a ideia é fazer uma varredura dentro do espaço de busca de problemas com elevado número de soluções possíveis, percorrendo, preferencialmente, um número reduzido de soluções para encontrar soluções da boa qualidade dentre todas as possíveis. Cada tipo de meta-heurística possui a sua própria estratégia que guia o processo de varredura; se a estratégia nesse processo é eficiente, certamente soluções de boa ou excelente qualidade, e também, possivelmente a solução ótima poderão ser visitadas. A principal diferença entre as meta-heurísticas está na estratégia escolhida para realizar a transição. Para as meta-heurísticas, as exigências especiais de convexidade e diferenciabilidade presentes nos métodos exatos praticamente desaparecem. Dessa forma, a crucialidade para as meta-heurísticas consiste em: (i) encontrar melhores formas de identificar, representar ou codificar uma solução candidata; (ii) encontrar a forma mais adequada de quantificar a função objetivo ou a qualidade de uma solução; e (iii) encontrar a melhor estratégia de transição para cada tipo de problema. Entre as principais vantagens e diferenças que as meta-heurísticas apresentam em com- paração com os algoritmos heurísticos estão: (i) a codificação pode ser mais eficiente e mais genérica levando em conta soluções infactíveis; (ii) o indicador de desempenho é muito mais complexo e pode ser adaptativo; (iii) a estrutura de vizinhança pode variar em forma e tama- nho; (iv) geralmente se trabalha com um conjunto de soluções; etc. Pertencem à classe das meta-heurísticas os algoritmos SA, GA, EA, TS, GRASP, PSO, AC, etc. (GLOVER; KOCHEN- BERGER, 2003). Especificamente para o problema PEST, as meta-heurísticas estão sendo amplamente utilizadas nos últimos anos para a resolução desse tipo de problema. Romero, Gallego e Monticelli (1996) apresentaram um algoritmo SA para resolver o modelo CC. O SA é uma meta-heurística baseada no processo físico de construção de cristais perfeitos, onde o material é aquecido até uma temperatura crítica e depois esfriado lentamente até alcançar o quase equilíbrio termodinâmico, tornando-se, ao final, um cristal perfeito. O artigo de Gallego et al. (1997) apresentou um SA paralelo para resolver o modelo CC com o objetivo de diminuir o tempo computacional. Gallego, Monticelli e Romero (1998a) utilizaram um algoritmo híbrido do SA, GA e TS para resolver o modelo CC. O GA é um algoritmo baseado no processo de seleção natural, onde o indivíduo geneticamente melhor capacitado tem maiores chances de sobrevivência. O algoritmo GA vale-se da ideia de divisão e duplicação de células reprodutivas, do fenômeno da recombinação genética, da reprodução sexuada e da mutação genética. O algoritmo TS foi desenvolvido a partir de conceitos usados na inteligência artificial, conceitos de memória de 48 Capítulo 1 INTRODUÇÃO longo e curto prazo e, basicamente, consiste em um procedimento meta-heurístico que gerencia um algoritmo heurístico de busca local; neste caso, são utilizadas estratégias para contornar ou sair de soluções ótimas locais. O trabalho de Gallego, Monticelli e Romero (1998b) apresentou um GA modificado para resolver o modelo CC; as modificações foram realizadas na etapa de escolha dos indivíduos iniciais e na etapa de mutação. Na etapa de seleção dos indivíduos iniciais, foram utilizados métodos exatos na escolha. Por outro lado, na etapa de mutação, foram utilizados conceitos do algoritmo SA. Silva, Gil e Areiza (2000) também apresentaram um GA com outros tipos de modificações com o intuito de melhorar o desempenho do processo de resolução do modelo CC. O artigo de Silva et al. (2005) usou o GA, só que, nesse caso, para resolver o modelo CC que considera restrições de segurança do tipo (N−1). Gallego, Monticelli e Romero (2000) apresentaram um algoritmo TS paralelo de modo a acelerar o processo de resolução do modelo CC. Em sequência, o artigo apresentado por Silva et al. (2001) usou o algoritmo TS com algumas modificações para resolver também o modelo CC. O trabalho apresentado por Binato, Oliveira e Araujo (2001) usou a meta-heurística GRASP para resolver o modelo CC. A meta-heurística GRASP é uma evolução direta dos algoritmos heurísticos construtivos do tipo guloso. O algoritmo heurístico do tipo guloso adiciona, em cada iteração, o elemento mais atrativo na configuração corrente até não ser necessário adicionar novos elementos. Por outro lado, o GRASP seleciona aleatoriamente um elemento dentre os mais atrativos para adicionar em cada iteração. O conceito adaptativo do GRASP ocorre quando é usada uma lista de tamanho variável e que depende da evolução do processo. Em cada iteração do GRASP, depois da escolha do elemento a ser adicionado na topologia corrente, é possível fazer uma busca local tentando encontrar um ótimo local. O artigo de Faria et al. (2005) apresentou um novo algoritmo GRASP para resolver o modelo MHNL; nesse novo algoritmo, foi utilizada a ideia de Path Relinking (PR) na etapa de busca local. O PR permite gerar uma nova configuração usando como base duas ou três configurações de qualidade chamadas de configurações de elite. As grandes vantagens apresentadas pelas meta-heurísticas é que são relativamente sim- ples de implementar, são robustas e encontram soluções ótimas, ou quase ótimas, mesmo em sistemas grandes e complexos, com um esforço de processamento elevado, mas não proibitivo. Adicionalmente, quando se aumenta a complexidade do modelo matemático a aplicabilidade das meta-heurísticas sofre pouca ou quase nenhuma alteração. Por outro lado, uma das desvantagens que elas apresentam deve-se ao elevado tempo de processamento para encontrar uma solução de qualidade além de não garantir sua otimalidade. 1.4 OBJETIVOS E JUSTIFICATIVA 49 1.4 OBJETIVOS E JUSTIFICATIVA Neste trabalho, é abordado um tema específico relacionado com a técnica de otimização do problema PEST. A maioria das técnicas de otimização resolve subproblemas especializados de PL dentro da estrutura de otimização (heurísticas, meta-heurísticas e técnicas de otimiza- ção clássica). Observa-se que, em grande parte das publicações apresentadas na literatura especializada, esses subproblemas de PL são resolvidos usando solvers de PL como MINOS e CPLEX. Também se deve observar que, nos casos em que o sistema elétrico a ser otimizado é de complexidade média, pode ser necessário resolver milhares de problemas de PL até atingir a convergência. Adicionalmente, para sistemas elétricos de grande complexidade, como o sistema norte-nordeste brasileiro, pode ser necessário resolver dezenas ou centenas de milhares de problemas de PL até atingir a convergência. Nesta pesquisa, resolve-se, de forma eficiente, os subproblemas de PL, quando é utilizado o algoritmo B&B para resolver o modelo de transportes e o modelo LD do problema PEST. Sendo assim, foram desenvolvidas técnicas eficientes de programação linear dos tipos PSC e DSC para resolver de forma mais eficiente os problemas de PL que são gerados pelo algoritmo B&B durante a resolução do problema PEST. O modelo de transportes e o modelo LD (cuja solução ótima é a mesma do modelo CC, que é considerado como modelo ideal para o problema PEST) resultam em problemas PLIM. Portanto, as técnicas de otimização clássicas, como o algoritmo B&B, conseguem encontrar a solução ótima global do problema, exceto em problemas muito grandes em que o algoritmo não converge para solução devido aos limites computacionais disponíveis. Outro aspecto que deve ser mencionado é que mais de 90% do tempo de processamento usado pelo algoritmo B&B, para resolver o problema PEST, é usado para resolver e armazenar os problemas de PL que aparecem durante o processo de otimização (HASHIMOTO; ROMERO; MANTOVANI, 2003). Portanto, se for desenvolvido um algoritmo de PL altamente eficiente, o tempo total de processamento do algoritmo B&B pode diminuir de forma significativa. O desafio é tornar o algoritmo B&B suficientemente rápido e com capacidade de resolver problemas altamente complexos. Adicionalmente, no futuro, podem ser implementadas técnicas eficientes de otimização da família B&B como, por exemplo, algoritmos tipo Branch and Cut, onde os módulos de PL desenvolvidos nesta pesquisa, podem ser usados de forma mais eficiente. E também possibilitando no futuro, após adaptações, utilizar os módulos de PL desenvolvidos em conjunto com outras técnicas de otimização como as heurísticas e as meta-heurísticas. Todo o pacote de otimização foi implementado em linguagem de programação FOR- TRAN e opera de forma autônoma, isto é, sem o auxílio de solvers comerciais de PL, produzindo assim, programas de otimização independentes. 51 2 OS MODELOS DE TRANSPORTE E LINEAR DISJUNTIVO E A TÉCNICA BRANCH AND BOUND No Capítulo 1, foram apresentados os diversos modelos utilizados na modelagem ma- temática do problema de Planejamento da Expansão de Sistemas de Transmissão (PEST) e também os principais métodos utilizados na sua resolução. A proposta desta pesquisa é apre- sentar uma melhoria de um dos métodos utilizados na resolução do problema PEST, o algoritmo Branch and Bound (B&B) para problemas de Programação Linear Inteira Mista (PLIM), como os problemas resultantes dos modelos de transporte e linear disjuntivo (LD). Este capítulo tem como objetivo fazer uma introdução e apresentar os fundamentos teóricos, de forma simples e didática, da técnica de otimização B&B escolhida como técnica de resolução do problema PEST, modelado a partir dos modelos de transporte e LD. Nesse capítulo, também será discutido o Algoritmo de Garver (AG) devido a sua importância na área de PEST, sendo o primeiro algoritmo utilizado na resolução do problema, e, ainda por sua versatilidade, já que o mesmo pode ser adaptado para resolver outros modelos e pode fazer parte de outras técnicas de otimização mais elaboradas como o algoritmo B&B. 2.1 O ALGORITMO DE GARVER Garver (1970) apresentou o primeiro algoritmo de grande difusão inaugurando a fase dos algoritmos heurísticos usados para resolver o PEST. Basicamente, esses algoritmos consistem em um procedimento passo a passo, em que são adicionados em cada passo uma ou várias linhas no caminho mais atrativo para expansão do sistema elétrico, até que sejam satisfeitas todas as condições de operação. Esse caminho mais atrativo é escolhido através de um indicador de sensibilidade local que, de alguma forma, indica a variação da função objetivo devido a alguma mudança dos parâmetros do sistema elétrico corrente. O algoritmo desenvolvido por Garver (1970) foi uma estratégia para encontrar uma solução de boa qualidade, não necessariamente a solução ótima, em sistemas grandes e com- plexos. A proposta de Garver foi um grande avanço na pesquisa do problema PEST, pois era a única maneira que existia naquela época para resolver problemas de PEST de grande porte. O algoritmo heurístico construtivo de Garver ou simplesmente AG é robusto e apresenta esforço computacional muito pequeno. Adicionalmente, muitas características e propriedades desse algoritmo podem ser incorporadas em algoritmos mais complexos, como, por exemplo, no al- goritmo B&B, em que pode ser usado o AG para encontrar uma solução incumbente inicial de boa qualidade. O modelo de transportes representado pelo conjunto de equações (1) e o modelo LD representado pelo conjunto de equações (8) são problemas de PLIM em que as variáveis ni j devem ser inteiras, e as variáveis wi j,y devem ser binárias. Ao relaxar a integralidade das 52 Capítulo 2 OS MODELOS DE TRANSPORTE E LD E A TÉCNICA B&B variáveis ni j e wi j,y dos problemas (1) e (8), são obtidos problemas de Programação Linear (PL), sendo que o primeiro é chamado de PL correspondente ou também de P0, e os demais são chamados de problemas sucessores. Dessa forma, a ideia de Garver consiste em usar a solução do PL como uma estratégia para encontrar uma boa solução do problema original. O AG consiste em resolver o PL correspondente e encontrar a solução ótima não inteira para a configuração corrente n0 i j. Conhecidas as incógnitas ni j ou wi j,y (encontradas através de um algoritmo para resolver o PL correspondente), podem-se encontrar os fluxos de potência em todas as linhas antigas (n0 i j) e novas (ni j) ou (wi j,y). Aquele caminho i j, que apresentar o maior fluxo de potência ativa, representa o caminho mais atrativo para adição de linhas. Portanto, adiciona-se uma linha no caminho identificado como mais atrativo e atualiza-se a configuração corrente de acordo com a adição escolhida. Repete-se essa estratégia adicionando em cada passo uma linha no caminho mais atrativo. O processo termina quando a solução do PL que corresponde à topologia corrente apresenta solução com todos os ni j = 0 ou wi j,y = 0 (significa que não é mais necessário realizar adição ao conjunto de adições realizadas), e a configuração corrente é uma configuração factível e eventualmente ótima para o sistema elétrico. O AG pode ser resumido nos seguintes passos: Algoritmo 1 Algoritmo de Garver 1. Assumir a configuração base n0 i j como configuração corrente; 2. Resolver o PL da configuração corrente. Se todos os ni j = 0, então pare, pois foi encontrada uma boa configuração factível. Caso contrário, ir ao passo 3; 3. Calcular os fluxos em todas as novas linhas adicionadas pelo PL, (ni j 6= 0), usando a relação f v i j = ni j f i j. Identificar o caminho novo i j com o maior valor de fluxo f v i j e atualizar a configuração corrente adicionando uma linha naquele caminho i j. Voltar ao passo 2. Fonte Escobar, Romero e Gallego (2010) O maior esforço computacional do AG está no passo 2 em que é necessário utilizar outro algoritmo para resolver o PL da topologia corrente. Existem algumas modificações que podem tornar o AG mais rápido, isto é, o algoritmo de resolução de PL será chamado menos vezes. Essas modificações podem acelerar o AG, mas nem sempre, as soluções obtidas serão de melhor qualidade. Assim, as modificações que podem ser realizadas são as seguintes: 1. Após a resolução do primeiro PL, pode-se incorporar na configuração base, simultanea- mente, a parte inteira de todos os caminhos que apresentam valores de ni j ≥ 1. 2. Em cada passo, pode-se escolher para adição de uma linha, aquele caminho com maior valor de ni j em lugar de escolher o caminho com maior valor de f v i j. 2.2 ALGORITMO BRANCH AND BOUND 53 3. Em cada passo, pode-se manter o critério de adição daquele caminho com maior valor de f v i j, mas em lugar de adicionar uma linha simples naquele caminho, pode-se adicionar um número de linhas igual à parte inteira de ni j. 4. Incorporar um processo de Fase II para retirar linhas irrelevantes adicionadas na fase inicial. 2.2 ALGORITMO BRANCH AND BOUND O algoritmo B&B, primeiramente, foi proposto por Land e Doig (1960) para resolver problemas de programação inteira e depois tornou-se uma ferramenta muito utilizada na otimi- zação combinatória para resolver problemas do tipo NP-completo. Esse algoritmo é geralmente utilizado para encontrar a solução ótima de vários problemas de otimização. O algoritmo B&B é conceitualmente simples e bastante eficiente para problemas lineares com variáveis inteiras, pois consegue identificar um grande número de subproblemas candidatos que terão soluções de baixa qualidade e poderão ser descartados, muitas vezes, antes mesmo de serem resolvidos. O mesmo método também pode ser estendido para resolver problemas não lineares com variáveis inteiras; neste último caso, só é possível garantir que a solução é ótima global do problema se ele for convexo. A ideia básica para resolver um problema linear com variáveis inteiras, é resolver um conjunto de problemas de PL que são versões relaxadas do problema original, isto é, dividir a região factível do problema original em sub-regiões menores. Assim, através de um algoritmo de PL, inicialmente deve ser resolvido o problema original relaxando a integralidade das variáveis de investimento; esse problema inicial relaxado será chamado P0. Caso P0 apresente solução inteira, em que todas as variáveis inteiras tenham valores inteiros, o algoritmo B&B deve parar, pois foi encontrada a solução ótima global do problema original. Caso contrário, isto é, se a solução de P0 apresente valores não inteiros para alguma ou algumas variáveis inteiras, P0 deve ser separado em dois subproblemas, P1 e P2, em que é escolhida uma variável inteira com valor corrente não inteiro de P0 para fazer a separação. Assim, se uma variável inteira ni possui valor corrente não inteiro n∗i , então os subproblemas sucessores, P1 e P2, são obtidos da seguinte forma: • Subproblema P1: É o problema P0 acrescido da restrição ni ≤ ⌊n ∗ i ⌋ (9) em que ⌊n∗i ⌋ é o maior inteiro contido em n∗i ; • Subproblema P2: 54 Capítulo 2 OS MODELOS DE TRANSPORTE E LD E A TÉCNICA B&B É o problema P0 acrescido da restrição ni ≥ ⌊n ∗ i ⌋+1. (10) Nos casos em que as variáveis inteiras ni são binárias, os subproblemas sucessores, P1 e P2, são obtidos da forma a seguir: • Subproblema P1: É o problema P0 acrescido da restrição ni = 0; (11) • Subproblema P2: É o problema P0 acrescido da restrição ni = 1. (12) O problema P0 é separado em dois subproblemas menores, P1 e P2, isto é, são problemas mais restritos por causa da adição das novas restrições. Assim, esses subproblemas devem ser adicionados em uma lista de problemas a serem resolvidos. Depois de resolvidos, eles podem ainda apresentar valores não inteiros para variáveis inteiras e serem separados novamente em novos subproblemas mais restritos; como o problema é de minimização, implica que os novos subproblemas terão funções objetivos com valores maiores ou iguais ao da função objetivo do seu subproblema gerador. Entretanto, às vezes, a solução de um subproblema permite descobrir se ainda é necessário fazer a sua separação em novos subproblemas, ou se ele pode ser eliminado do processo de busca. Para ocorrer a eliminação do subproblema, é necessário que sua solução apresente as seguintes características: 1. A solução não é inteira, mas é de pior qualidade que a incumbente. Neste caso, o subproblema corrente pode conter soluções inteiras dentro da sua região factível, mas serão de pior qualidade que a solução incumbente. 2. A solução é infactível. Nesse caso, os subproblemas sucessores continuarão sendo infac- tíveis. 3. A solução é inteira, isto é, todos os valores das variáveis inteiras são inteiros. Nesse caso, se a solução do subproblema é inteira, significa que ainda podem existir outras soluções inteiras dentro de sua região factível, mas certamente todas serão de pior quali- dade. Se a solução encontrada é de melhor qualidade que todas as soluções encontradas anteriormente, ela é armazenada como incumbente. Portanto, não há a necessidade de continuar buscando soluções inteiras dentro de sua região factível, e o subproblema deve ser eliminado de análises futuras. 2.2 ALGORITMO BRANCH AND BOUND 55 As características apresentadas anteriormente são conhecidas como testes de sondagem. O algoritmo B&B consiste fundamentalmente de uma estratégia de separação do problema em subproblemas menores até que todos eles sejam sondados. Na verdade, no algoritmo B&B, é implementada uma estratégia de enumeração implícita e/ou explícita de todas as soluções inteiras da região factível do problema original; isso garante que a melhor solução encontrada seja ótima global do problema. Esse algoritmo termina quando todos os subproblemas gerados forem sondados. A solução ótima global é a melhor solução inteira encontrada, chamada também de solução incumbente. Um algoritmo B&B básico assume a seguinte forma: Algoritmo 2 Algoritmo Branch and Bound Básico 1. Inicialização: Escolher uma incumbente inicial Vinc = v∗ = ∞. Resolver o problema original com a integralidade das variáveis inteiras relaxada que se designa como P0. Se a solução de P0 for inteira, PARE, pois foi encontrada a solução ótima global do problema original. Caso contrário, adicionar o valor da função objetivo como limitante inferior vin f dos subproblemas sucessores. 2. Escolha da variável para separar o subproblema: Escolher a primeira variável inteira ni com valor corrente não inteiro n∗i para fazer a separação do problema. Gerar dois novos subproblemas a partir do problema corrente adicionando a restrição (13), no primeiro subproblema, e a restrição (14), no segundo subproblema: ni ≤ ⌊n ∗ i ⌋ (13) ni ≥ ⌊n ∗ i ⌋+1 (14) em que ⌊n∗i ⌋ é o maior inteiro contido em n∗i ; 3. Resolução do subproblema selecionado: Pela regra LIFO (Last In First Out), resolver primeiro o último subproblema gerado usando o algoritmo de PL e armazenar a solução ótima vPL = vin f como limitante inferior para prováveis subproblemas sucessores. 4. Testes de sondagem: Verificar os testes de sondagem no subproblema resolvido. O subproblema é eliminado de análises futuras se satisfaz um dos seguintes testes de sondagem: Teste 1 Se vin f ≥ v∗, em que v∗ é o valor da incumbente; Teste 2 Se o subproblema for infactível; Teste 3 Se a solução do subproblema for inteira, isto é, todas as variáveis inteiras pos- suem valor corrente inteiro. Nesse caso, se a solução ótima do subproblema for de melhor qualidade que a incumbente, armazenar a solução como a nova incumbente e aplicar o Teste 1 para todos os subproblemas ainda não analisados. 56 Capítulo 2 OS MODELOS DE TRANSPORTE E LD E A TÉCNICA B&B Algoritmo 2 Algoritmo Branch and Bound Básico (Continuação) 5. Se o problema não foi sondado, ir ao passo 2 para realizar a separação do subproblema corrente em dois subproblemas sucessores. Caso contrário, verificar se existem ainda subproblemas que não foram sondados. Se todos os problemas foram sondados, PARE, o processo termina, e a solução incumbente é a solução ótima do problema; caso contrário, voltar ao passo 3 para resolver o último problema gerado. Fonte Gallego, Escobar e Romero (2007) Os subproblemas gerados pelo algoritmo B&B podem ser representados em um gráfico em formato de árvore, como pode ser visto na Figura 2; esse gráfico é conhecido pelo nome Árvore Branch and Bound. O primeiro nó da árvore representa o problema original com a restrição de integralidade relaxada P0; seus demais nós representam os subproblemas gerados pela divisão de P0 e seus descendentes, e os ramos (arestas) da árvore representam as variáveis inteiras com valores não inteiros escolhidas para separar P0 e seus sucessores. Figura 2 – Uma das árvores Branch and Bound de solução do sistema de 3 barras com uma linha na topologia base mostrado na Figura 1. v 31/7= n12 = 8/7 =1n 3 0 1/2n23 = v 5= n12 = 0 =1n 3 1 3/2n23 = v 40/7= n12 = 4/7 =1n 3 1 1n23 = v 9/2= n12 = 1 =1n 3 1/8 5/8n23 = n12 £ 1 Infactível Infactível v 6= n12 = 2 =1n 3 0 0n23 = v 6= n12 = 0 =1n 3 1 2n23 = v 25/4= n12 = 1 =1n 3 1 13/8n23 = Po P4 P5 P1 P3 P7 P6 P8 P2 n12 ³ 2 n13 £ 0 n13 ³ 1 n23 £ 1 n23 ³ 2 n12 £ 0 n12 ³ 1 S S S S S Fonte – Dados da pesquisa do autor. 2.3 POSSÍVEIS MELHORIAS QUE PODEM SER INCLUÍDAS NO ALGORITMO B&B 57 Mesmo o algoritmo B&B sendo conceitualmente simples, sua implementação compu- tacional possui maior complexidade, podendo haver problemas que envolvam esforço computa- cional e de memória durante a execução do algoritmo em sistemas de grande porte. Portanto, pelos motivos apresentados na Seção 1.4, foram escolhidos o modelo de transporte representado pelo conjunto de equações (1) e o modelo LD representado pelo conjunto de equações (8) por se tratarem de problemas lineares com variáveis inteiras, de modo a validar a proposta apresentada nessa pesquisa de melhoria do algoritmo B&B na resolução desse tipo de problema. A próxima seção apresenta alguns tipos de melhoria que podem ser incluídos no algoritmo B&B para aumentar sua eficiência. 2.3 POSSÍVEIS MELHORIAS QUE PODEM SER INCLUÍDAS NO AL- GORITMO BRANCH AND BOUND A eficiência do algoritmo B&B está atrelada a diversos tipos de decisão que devem ser executados durante o processo de resolução do problema. Um algoritmo B&B é eficiente obviamente se gera um número menor de nós na árvore B&B, o que significa chamar um menor número de vezes, no caso de problemas lineares, o algoritmo dedicado na resolução dos PLs advindos de cada subproblema gerado. Para melhorar o desempenho do algoritmo B&B aplicado a um tipo de problema específico, podem ser realizados dois tipos de estratégias: introduzindo melhorias gerais relacionadas com a teoria básica do algoritmo B&B, e introduzindo melhorias relacionadas com as características específicas do tipo de problema. Existem quatro tipos principais de melhorias que estão relacionados com a teoria básica do algoritmo B&B: 1. Determinação de uma solução inteira inicial (incumbente inicial): O algoritmo B&B pode iniciar sem solução incumbente, mas também pode ser implementada alguma estra- tégia heurística, como o AG, para encontrar uma solução incumbente de boa qualidade. Encontrando rapidamente uma solução incumbente de boa qualidade aumenta a eficiência do Teste 1 de sondagem fazendo com que os subproblemas sejam sondados rapidamente, aumentando, consequentemente, a eficiência do algoritmo B&B. 2. Escolha da melhor estratégia e técnica de resolução dos subproblemas gerados: A maior parte do tempo gasto pelo algoritmo B&B está na resolução dos subproblemas gerados; sendo assim, é indispensável escolher a técnica mais adequada e eficiente para resolver esses subproblemas. A principal contribuição dessa pesquisa encaixa-se nesse item. O presente trabalho usa um algoritmo Primal Simplex Canalizado (PSC) para resolver os problemas (1) e (8) com a restrição de integralidade relaxada e, posterior- mente, os subproblemas sucessores são reotimizados usando um algoritmo Dual Simplex Canalizado (DSC). 58 Capítulo 2 OS MODELOS DE TRANSPORTE E LD E A TÉCNICA B&B 3. A variável escolhida para separação: Ao resolver o problema relaxado ou os subpro- blemas gerados, frequentemente aparecem soluções em que algumas variáveis inteiras tenham valores correntes não inteiros. A escolha de cada variável para realizar a separa- ção pode gerar diferentes árvores B&B. Obviamente, existe uma variável que gera a menor árvore B&B, mas não existe uma técnica sistemática para encontrar qual é a melhor va- riável para fazer a separação de um subproblema. Entretanto existem técnicas empíricas, como escolher sempre a variável inteira com valor corrente não inteiro de menor índice, entre outras para a escolha da variável mais atrativa que pode ser usada na separação. 4. Escolha do próximo subproblema a ser analisado: Durante a execução do algoritmo B&B em certo momento pode haver muitos subproblemas a serem analisados, e a escolha de cada subproblema para ser resolvido gera uma árvore B&B diferente. Certamente existe um desses subproblemas da lista que gera a menor árvore B&B, porque ao resolver esse problema ou um subproblema descendente do mesmo, pode ser encontrada uma solução inteira de ótima qualidade, aumentando a eficiência do Teste 1 de sondagem e fazendo com que muitos dos subproblemas ainda não analisados sejam sondados. Não existe técnica sistemática para a escolha do melhor subproblema a ser resolvido, entretanto, existem técnicas empíricas que auxiliam a escolha do subproblema mais atrativo. Entre essas técnicas empíricas, existe uma técnica muito usual para a escolha do subproblema a ser resolvido que é a regra LIFO, onde sempre é escolhido o último subproblema gerado para ser resolvido primeiro. A regra LIFO permite que continuamente seja escolhido o sucessor do último subproblema resolvido como o próximo a ser resolvido, podendo ser implementado um algoritmo DSC para fazer a reotimização, através do quadro ótimo do subproblema antecessor, resolvendo o subproblema escolhido rapidamente. Essa regra permite resolver com maior velocidade muitos problemas. Para os dois últimos itens apresentados, tam