Desenvolvimento de técnicas eficientes de programação linear na utilização de metaheurísticas para o problema de planejamento da expansão de sistemas de transmissão

Abstract

Neste trabalho apresenta-se uma estratégia de programação linear especializada para resolver, de forma eficiente, o problema de planejamento da expansão de sistemas de transmissão de energia elétrica usando o algoritmo de busca em vizinhança variável (VNS). O modelo matem´atico para este problema é um modelo de programação linear inteira mista. A solução deste modelo através de metaheurísticas, dependendo do sistema elétrico sob análise, pode exigir a solução de centenas de milhares de problemas de programação linear (PL) que exigem elevado esforço computacional e consomem a maior parte do tempo de CPU exigido pela metaheurística. A ideia fundamental deste artigo consiste em identificar soluções básicas adequadas para iniciar o processo de solução do problema de planejamento da transmissão e os inúmeros problemas de PL exigidos pela metaheurística, fazendo que os problemas de PL sejam resolvidos de forma eficiente computacionalmente. A solução básica adequada consiste na definição uma base dual factível específica para o problema que permite que novos problemas de PL resultantes das alterações de alguns parâmetros do problema de planejamento possam ser resolvidos usando um algoritmo dual simplex canalizado. A metodologia proposta foi validada e testada em um sistema de médio porte

This paper presents a linear programming expert strategy to solve efficiently the energy transmission network expansion planning problem using the variable neighborhood search algorithm (VNS). The mathematical model used is a mixed integer linear programming problem. Solution of this model using different metaheuristics, depending on the electrical system under analysis, may require hundreds of thousands of linear programming problems (LP) which require high computational effort and consume almost all of the CPU time required by the metaheuristic. The basic idea of this paper is to identify appropriate basic solutions which help to start the process and speed up the solution of the many subsequent subproblems generated during a typical run, solving the LP problems efficiently. The starting basic solution is defined as an appropriate dual feasible basis for the specific problem, new LP problems resulting from changes in some parameters of the planning problem are solved using a bounded dual simplex algorithm. The proposed methodology was validated and tested in a system of medium size