Embed Size (px)
Citation preview
O Método de Pontos Interiores Aplicado ao Problema do Despacho
Hidrotérmico
Mariana Kleina, Luiz Carlos Matioli,
Programa de Pós Graduação em Métodos Numéricos em Engenharia, UFPR
Departamento de Matemática e Construção Civil, 81531-990, Curitiba, PR
E-mail: [email protected], [email protected]
Débora Cintia Marcilio, Ana Paula Oening,
Instituto de Tecnologia para o Desenvolvimento (Lactec), 81531-980, Curitiba, PR
E-mail: [email protected], [email protected]
Resumo: Este artigo apresenta uma modelagem do problema de otimização do despacho
hidrotérmico. O objetivo geral do modelo é a minimização dos custos envolvidos na geração de
energia elétrica, que engloba o custo de geração térmica e custo de déficit. A metodologia
proposta para resolução deste problema é o Método de Pontos Interiores, o qual é bastante
utilizado em problemas de grande porte, combinado com as ideias do bem conhecido método de
Gauss-Newton em programação não linear. A metodologia é aplicada para um sistema teste
brasileiro, apresentando resultados satisfatórios e ótimo desempenho computacional.
Introdução Neste trabalho é apresentado uma nova metodologia que envolve dois métodos importantes
e bem conhecidos na literatura. A saber, Método de Gauss-Newton [1] e o Método de Pontos
Interiores [9]. O primeiro é, em geral, aplicado na minimização do resíduo em quadrados
mínimos, que é equivalente a um problema de minimização irrestrita (ou na resolução de um
sistema de equações não lineares). Já o segundo tem sido aplicado com sucesso em problemas
lineares e não lineares com restrições. Ambos utilizam o método de Newton. O primeiro faz
uma aproximação da direção de Newton desprezando o termo que envolve a matriz Hessiana da
função objetivo, e em problemas em que a matriz Hessiana não tem grande influência, estes tem
obtido muito sucesso. O segundo utiliza o Método de Newton para resolver o sistema não linear
gerado a cada iteração.
A metodologia proposta consiste no método de Pontos Interiores para a solução do problema
hidrotérmico para o sistema brasileiro. O problema, após modelado, é não linear, não convexo e
envolve restrições de igualdades, desigualdades e limites nas variáveis. Adicionalmente, o
problema apresenta uma restrição, aqui chamada de atendimento a demanda, que é não linear,
com matriz Hessiana difícil de ser calculada analiticamente e sua aproximação é
computacionalmente inviável para a dimensão do problema a ser resolvido. Devido à estrutura
de grafo do modelo, esta matriz é bastante esparsa e em vários testes realizados, constatou-se
que possui pouca influência nos resultados numéricos finais. Portanto, ao desprezar o termo que
envolve a Hessiana da restrição não linear no método de Pontos Interiores faz-se uma espécie de
Gauss-Newton para resolução de sistemas não lineares. Isto não comprometerá a convergência
do método de Pontos Interiores como será analisado no decorrer deste trabalho.
Características do Modelo Hidrotérmico Brasileiro O Brasil é um país privilegiado em termos de disponibilidade de recursos hídricos; em
números [3], 73,60% da produção de energia provém de sistemas hidrelétricos, 26,14% de
sistemas termelétricos e 0,26% de demais sistemas geradores. A água não possui custo e é um
recurso renovável. Entretanto, somente a geração hidrelétrica não atende a demanda dos
consumidores, sendo necessária a utilização das termelétricas, o que envolve um custo de
geração elevado devido ao alto preço dos combustíveis (carvão, gás, petróleo, entre outros).
O sistema elétrico brasileiro é interligado em sua quase totalidade e essa condição de
intercâmbio entre os subsistemas exige um equilíbrio entre a geração térmica e hidrelétrica nas
diversas usinas, visando a operação como um todo, reduzindo assim os custos envolvidos.
81
ISSN 1984-8218
Contudo, a geração hidrotérmica traz consigo um risco associado tanto com incertezas na
demanda de energia quanto nas afluências naturais.
A questão a ser respondida é: quanto gerar de energia através das hidrelétricas a fim de
economizar com combustíveis nas termelétricas e quanto gerar de energia através das
termelétricas a fim de preservar o nível dos reservatórios hidrelétricos?
Atualmente, para médio prazo (5 anos), no caso brasileiro é utilizado o modelo NEWAVE
como base para o despacho hidrotérmico. Porém, este modelo faz diversas simplificações,
devido a metodologia utilizada e a dimensão do sistema brasileiro. Por isso, surgiu a
necessidade de novas tecnologias, que respondam mais realisticamente a situação do parque
brasileiro com relação ao despacho hidrotérmico brasileiro. Esta pesquisa faz parte desta nova
proposta e é financiada pela ANEEL através do Projeto Estratégico de Pesquisa e
Desenvolvimento – ANEEL PE-6491-0108/2009, “Otimização do Despacho Hidrotérmico”,
com o apoio das concessionárias COPEL, DUKE, CGTF, CDSA, BAESA, ENERCAN, CPFL
PAULISTA, CPFL, PIRATININGA, RGE, AES TIETÊ, AES URUGUAIANA,
ELETROPAULO, CEMIG e CESP.
Modelagem Matemática O modelo de programação não linear para o problema de otimização energética é:
(1)
Sujeito à:
(2)
(3)
(4)
(5)
As variáveis envolvidas na descrição do modelo estão relacionadas a seguir:
– geração da usina térmica durante o período [ ];
- volume armazenado no reservatório para o período [ ];
– vazão turbinada do reservatório durante o período [ ];
– vazão vertida do reservatório durante o período [ ];
- intercâmbio de energia na linha i no período [ ];
– déficit do subsistema durante o período [ ].
A função objetivo (1) é de minimização do valor presente dos custos de geração térmica
( é uma função que representa o custo da usina térmica para o período [ ], depende do
tipo de combustível utilizado na usina e é aproximada por um polinômio de grau 2) e de déficit
( é uma função de custo de déficit do subsistema s [ ], representa o impacto causado pelo
não suprimento da demanda de energia e é representada por um polinômio de grau 2), onde é
o coeficiente de valor presente para o período .
82
ISSN 1984-8218
A restrição de balanço hídrico (2) relaciona o volume de um reservatório com o volume do
período anterior, as afluências ao reservatório e as perdas, onde representa a afluência
natural ao reservatório durante o período [ ], representa o conjunto de reservatórios
imediatamente a jusante do reservatório . Para que seja possível realizar as operações
matemáticas em (2), é necessária uma mudança de unidades, transformando o volume de
para . Dessa maneira o volume é multiplicado por , onde e
corresponde ao número de segundos no mês.
A restrição de atendimento a demanda de energia (3) tem por objetivo garantir o
atendimento da carga do subsistema, onde é a demanda de energia no subsistema no
período [ ], representa o conjunto de subsistemas diretamente conectados ao
subsistema , o conjunto de usinas térmicas no subsistema , o conjunto de usinas
hidráulicas no subsistema e é a energia gerada no reservatório r no período t.
A restrição de defluência mínima total para o reservatório (4) garante a utilização dos
recursos hídricos para outras atividades além da geração de eletricidade, como controle de
cheias, navegabilidade de rios, irrigação, etc., onde representa a vazão total mínima de
defluência do reservatório no período [ ].
A restrições de limite das variáveis (5) significam as limitações de: geração termelétrica,
volumes dos reservatórios hidrelétricos, volumes de turbinagem e vertimento, intercâmbio de
energia entre subsistemas e déficit de energia de cada subsistema, respectivamente.
O Método de Pontos Interiores O problema do despacho hidrotérmico, com as características abordadas nessa pesquisa,
quando escrito matematicamente tem o seguinte formato:
(6)
onde é o vetor das variáveis de decisão, que para essa modelagem envolvem: geração
térmica, vazões vertida e turbinada, volume do reservatório, intercâmbio entre subsistemas e
déficit, é a função objetivo não linear, são restrições não lineares que
representam o atendimento à demanda, e são restrições lineares que
representam respectivamente o balanço hídrico e defluência total, e finalmente
representam os limites inferior e superior das variáveis de decisão,
O método adotado para resolver o problema energético é o Método de Pontos Interiores para
programação não linear. Primeiramente, acrescentam-se variáveis de folga não negativas r, s, t
nas desigualdades no problema original (8), assim como em [7] e [8].
(7)
Penalizam-se as variáveis que devem ser não negativas acrescentando a função Barreira
logarítmica na função objetivo do problema:
(8)
onde é o parâmetro barreira e tende a zero quando se aproxima da solução ótima.
A função Lagrangeana associado ao problema penalizado é:
83
ISSN 1984-8218
(9)
onde são os multiplicadores de lagrange,
As condições de otimalidade de primeira ordem, também conhecidas como condições de
Karush-Kuhn-Tucker (KKT), [5], [6] e [9], são condições necessárias que uma solução ótima
deve satisfazer, são aplicadas ao problema, resultando num sistema não linear. O método de
Newton é então aplicado, resultando em um sistema linear a ser resolvido:
(10)
onde d é a direção de Newton, é o gradiente da função Lagrangeana (9), , é a matriz Jacobiana da restrição , , , , , e são
matrizes diagonais, com os elementos diagonais dados, respectivamente, pelas componentes do
vetores , , , , e , e representa a matriz identidade de tamanho apropriado.
Após alguns cálculos, reduz-se o sistema (10) no seguinte sistema linear:
(11)
onde F é um vetor constante, ,
(12)
onde é uma matriz diagonal composta pelos elementos do vetor . As matrizes
são definidas de modo análogo. Resolvendo o sistema (11), encontram-se e
. Com isso, encontram-se as demais direções.
Depois de encontrada a direção de Newton, calcula-se o comprimento do passo que será
dado nessa direção a fim não violar a não negatividade de algumas variáveis. Por último,
atualiza-se o parâmetro barreira , onde na literatura existem heurísticas que sugerem fórmulas
alternativas para sua atualização (ver [7] e [8]). Neste trabalho está sendo utilizada a seguinte
fórmula:
(13)
Repete-se o processo, até que o ponto encontrado satisfaça algum critério de parada.
Uma grande dificuldade em se aplicar o método ao problema do despacho, como descrito
acima, é o cálculo da matriz Hessiana das restrições não lineares (2). Esta restrição é a soma de
dois polinômios de quarto grau, um calculado no volume médio e o outro na soma das variáveis
vazões vertida e turbinada; o polinômio resultante é multiplicado pela variável vazão turbinada.
Logo, o cálculo exato da matriz Hessiana é bastante complexo, sendo este feito por
aproximação. Porém, esse cálculo aproximado exige um esforço computacional muito grande e
é requerido em cada iteração do método de Pontos Interiores, deixando o método lento e
conforme a dimensão do problema aumenta, a resposta é cada vez mais demorada.
84
ISSN 1984-8218
Sabe-se que se a matriz dos coeficientes em (11) é inversível, então o sistema têm solução e
ela é única. Segundo [4], para que isto ocorra, deve ser positiva definida (o que, conforme
a proposta apresentada a seguir, será provado) e deve ter posto coluna completo, o que neste
trabalho estará sendo suposto como verdadeiro.
A proposta feita aqui é usar a ideia do método de Gauss-Newton, que desconsidera
informações de segunda ordem do problema, isto é, elimina-se o termo que envolve a matriz
Hessiana das restrições não lineares na equação (12), isto é
(14)
Lema 1: Sejam , , , ,
e com dados respectivamente em (7),
(9) e (10); a função objetivo dada em (1) e a matriz dos coeficientes das
restrições de desigualdades lineares do problema (7). Então os seguintes itens são verdadeiros:
i. e , ou seja, são matrizes positivas definidas;
ii. , ou seja, é positiva definida;
iii. , ou seja, a matriz Hessiana de é positiva definida.
Prova:
i. e são matrizes diagonais com elementos positivos, logo são positivas
definidas ;
ii. Seja , então:
iii. é positiva definida pois a função é a soma de dois polinômios de segundo
grau com os coeficientes do termo quadrático sendo positivos. Logo é convexa e sua
matriz Hessiana é positiva definida.
Teorema 1: A matriz do sistema reduzido (11), dada na relação (14), é positiva definida.
Prova: De fato, seja e , então por (21):
Do Lema 1, segue que é a soma de matrizes positivas definidas, logo
Testes Computacionais e Análise dos Resultados Nesta seção, será abordada a implementação da metodologia proposta nesta pesquisa. Uma
vez que o Teorema 1 garante que a direção de Newton pode ser determinada, o sistema reduzido
(11) e consequentemente, o sistema (10) terá solução, a menos de erros de arredondamentos
(computacionais). Toda a modelagem matemática, assim como o Método de Pontos Interiores
foram implementados em Matlab® 7.10.0 (R2010a).
Neste trabalho, os resultados que serão apresentados referem-se a um sistema teste
composto por 21 usinas hidrelétricas, 32 térmicas e 3 subsistemas. O período considerado foi de
janeiro de 1952 a janeiro de 1957, que foi um período de afluências baixas. O subsistema 1 é
composto por 10 hidrelétricas, 18 térmicas com demanda total de 13740 MWmês. O subsistema
2 é composto por 10 hidrelétricas, 14 térmicas com demanda total de 9918 MWmês. O
subsistema 3 não possui demanda pois é composto apenas pela usina hidrelétrica de Itaipu, a
qual somente gera energia, que pode ser utilizada no subsistema 1 e subsistema 2.
O ponto para o método segue a premissa de que toda a afluência é turbinada. Os volumes
iniciais dos reservatórios são tomados como sendo o volume máximo e os volumes finais devem
ficar entre 70% e 100% do volume máximo. Os parâmetros usados na implementação do
algoritmo são: , os multiplicadores de Lagrange e as variáveis de folga são
inicializadas como vetores de 1’s de tamanhos apropriados. As condições de KKT ou um
número máximo de iterações foram adotados como critério de parada. Os gráficos a seguir são
dados em Energia (MWmês) x Tempo (mês).
85
ISSN 1984-8218
Figura 1. Soma da geração hidráulica no Figura 2. Soma da geração hidráulica no
subsistema 1. subsistema 2.
Figura 3: Geração hidráulica do subsistema 3.
o volume turbinado está no máximo. Percebe-se também que em períodos que antecedem
grandes afluências, os reservatórios são esvaziados para acomodar as afluências futuras ou se as
afluências futuras serão escassas, o nível dos reservatórios é preservados de modo a garantir a
geração de energia através das usinas hidráulicas.
Figura 4. Soma da geração térmica no Figura 5. Soma da geração térmica no
subsistema 1. subsistema 2.
As Figuras 4 e 5 mostram a geração térmica dos subsistemas 1 e 2 respectivamente, que em
vários períodos gerou o máximo possível de energia para atender a demanda. Isso se justifica
pois como já mencionado, o período considerado é de afluências baixas.
Figura 6. Intercâmbio de energia entre os
subsistemas 1 e 2.
0
500
1000
1500
2000
2500
3000
1 7 13 19 25 31 37 43 49 55
Geração ótima Geração máxima
0
2000
4000
6000
8000
10000
12000
1 7 13 19 25 31 37 43 49 55
Geração ótima Geração máxima
0
2000
4000
6000
8000
10000
12000
14000
16000
1 7 13 19 25 31 37 43 49 55
Geração ótima Geração máxima
1500
2000
2500
3000
3500
4000
4500
5000
5500
6000
1 7 13 19 25 31 37 43 49 55
Geração ótima Geração mínima
Geração máxima
500
1000
1500
2000
2500
3000
1 7 13 19 25 31 37 43 49 55
Geração ótima Geração mínima
Geração máxima
-6000
-4000
-2000
0
2000
4000
6000
1 7 13 19 25 31 37 43 49 55
Intercâmbio ótimo Intercâmbio máximo
Intercâmbio mínimo
A Figura 6 mostra o intercâmbio de
energia elétrica (energia hidráulica e energia
térmica) entre os subsistemas 1 e 2. Valores
positivos do intercâmbio representam
energia saindo do subsistema 1 e chegando
no subsistema 2. Valores negativos
representam justamente o contrário, isto é,
energia saindo do subsistema 2 para o
subsistema 1.
As Figuras 1, 2 e 3 representam,
respectivamente , a soma da energia elétrica
gerada pelas usinas hidráulicas dos
subsistemas 1, 2 e 3. É importante lembrar
que as usinas estão sendo consideradas
individualmente e a geração das usinas foi
somada somente para melhor visualização.
Quando os reservatórios das usinas são
analizados individualmente, tem-se que o
vertimento de água ocorre quando os
reservatórios estão em seu limite superior e
86
ISSN 1984-8218
Figura 7. Intercâmbio de energia entre os Figura 8. Intercâmbio de energia entre os
subsistemas 1 e 3. subsistemas 2 e 3.
A Figuras 7 e 8 mostram o intercâmbio de energia entre o subsistema 3 e os subsistemas 1 e
2. Como o subsistema 3 é puramente gerador, composto somente pela usina de Itaipu, não há
energia chegando neste subsistema, somente saindo.
Conclusão Muitos trabalhos em despacho hidrotérmico tendem a simplificar o problema com o
objetivo de alcançar um modelo mais simples, possivelmente linear. Para resolver o
problema de despacho hidrotérmico não linear, como é o caso deste, buscou-se um
algoritmo eficiente que dê respostas rápidas e precisas. O método de Pontos Interiores,
combinado com ideias dos métodos de Gauss-Newton, mostrou-se bastante eficaz quando
aplicado a este problema. Não trabalhar com informações de segunda ordem da restrição não
linear não afetou a convergência do método, conforme visto, e fez com que o método obtivesse
ótimo desempenho computacional. A metodologia proposta nesta pesquisa foi testada para
diversos períodos e demandas de energia diferentes e os resultados obtidos foram muito bons e
o objetivo principal é aplicá-la a todo sistema elétrico brasileiro.
Referências [1] J. E. Dennis, R. B. Shnabel, "Numerical methods for Unconstrained Optimization and
Nonlinear Equations", SIAM, Philadelphia, 1983.
[2] A. S. El-Bakry, R. A. Tapia, T. Tsuchiya, Y. Zhang, On the formulation and theory of the
Newton Interior-Point method for nonlinear programming, J. Optim. Theory Appl., vol. 89, pp.
507-541, (1996).
[3] EPE - Empresa de Pesquisa Energética (Brasil), Brazilian Energy Balance 2011. Disponível
em: https://ben.epe.gov.br/downloads/Relatorio_Final_BEN_2011.pdf, acesso em 18/11/2011.
[4] G. H. Golub, C. F. Van Loan, "Matrix Computations", Johns Hopkins Studies in the
Mathematical Sciences, Baltimore e Londres, 1996.
[5] D. G. Luenberger, "Linear and Nonlinear Programming", Springer, Nova York, 2005.
[6] J. Nocedal, S. Wright, "Numerical Optimization", Springer, Nova York, 2005.
[7] V. H. Quintana, G. L. Torres, On a nonlinear multiple-centrality-corrections interior-
point method for optimal power flow, IEEE Transactions on Power Systems, vol.16 , pp.
222-228, (2001).
[8] R. J. Vanderbei, D. F. Shanno, An Interior-Point Algorithm for Nonconvex Nonlinear
Programming, Comp. Optim. Appl., vol 13, pp. 231-252, (1999).
[9] S. J. Wright, "Primal-Dual Interior-Point Methods", SIAM, Philadelphia, 1997.
0
2000
4000
6000
8000
10000
12000
14000
1 7 13 19 25 31 37 43 49 55
Intercâmbio ótimo Intercâmbio máximo
0
500
1000
1500
2000
2500
1 7 13 19 25 31 37 43 49 55
Intercâmbio ótimo Intercâmbio máximo
87
ISSN 1984-8218
