Problema De Fluxo De Potência Ótimo DC Com Grafo Generalizado via Método De Pontos Interiores Com Restrições Adicionais

XXXIII

SBPO

Simpósio Brasileiro de Pesquisa Operacional

A pesquisa Operacional e o Meio Ambiente 6 a 9 de novembro de 2001 - Campos do Jordão - SP

PROBLEMA DE FLUXO DE POTÊNCIA ÓTIMO DC COM GRAFO GENERALIZADO VIA MÉTODO DE PONTOS INTERIORES COM RESTRIÇÕES ADICIONAIS Aníbal Tavares de Azevedo FEEC - UNICAMP [email protected] Aurelio Ribeiro Leite de Oliveira FEEC - UNICAMP [email protected] Marcius Fabius Carvalho ITI - Campinas [email protected] Secundino Soares Filho FEEC - UNICAMP [email protected]

Resumo Os métodos de pontos interiores primal-dual e preditor-corretor são desenvolvidos para um modelo de fluxo de potência ótimo DC onde as leis de Kirchhoff são representadas por um problema de fluxo em redes com restrições adicionais. Além disso, é introduzido o grafo generalizado na matriz que representa a estrutura da rede por onde os fluxos de potência passam, de modo que o modelo possa levar em conta as perdas resultantes da transmissão. Resultados numéricos com implementação em MATLAB são apresentados para sistemas testes do IEEE. O método de pontos interiores se mostra bastante robusto, convergindo rapidamente para os casos testados. Palavras chave: Fluxo de potência ótimo, Método de pontos interiores, Grafo Generalizado.

Abstract The primal-dual and predictor-corrector versions of interior point methods are developed for an optimal DC power flow model where Kirchhoff law´s are represented by a network flow model wirh surrogate constraints. In addition to this, a generalized graph is used in the matrix that represents the network structure used by the power flow. So, the model takes in account the transmission loses. Numerical results with MATLAB implementation are presented for IEEE test systems. The interior point method shows to be robust, achieving fast convergence in the instances tested. Keywords: Optimal power flow, Interior point methods, Generalized graph.

1. Introdução O problema de fluxo de potência ótimo tem aplicações em diversos problemas de análise e operação de sistemas de potência, tais como despacho econômico, análise de sensibilidade de geração e transmissão, análise de segurança, planejamento da expansão da geração e transmissão, e programação da geração à curto prazo. Devido a sua simplicidade e ao grau satisfatório de precisão do seus resultados adotamos para a maior parte destas aplicações a representação linearizada (DC) do fluxo de potência. 1454

XXXIII

SBPO

Simpósio Brasileiro de Pesquisa Operacional

A pesquisa Operacional e o Meio Ambiente 6 a 9 de novembro de 2001 - Campos do Jordão - SP

Podemos descrever o despacho ótimo de potência ativa através de modelo DC por um modelo de fluxo em redes com restrições adicionais [3]. Uma vantagem é que, com representação independente das leis de Kirchhoff, os fluxos de potência são representados explicitamente, permitindo a consideração direta dos limites de transmissão como restrições e das perdas de transmissão como critério de desempenho. Em relação as técnicas de pontos interiores, estas tem sido estudadas e utilizadas em diversas áreas, sendo uma delas sistemas de potência. Em particular, a resolução de problemas de problemas de fluxo de potência ótimo AC [6], obtendo excelente desempenho tanto em termos de eficiência como de robustez [11,14]. Por último, a utilização de grafos generalizados em diversos exemplos, que levem em conta a perda ou o ganho de fluxo nos arcos de uma rede, pode ser vista em [1, 7, 8]. Para sistemas de potência isto é particularmente interessante, dado que o grafo generalizado pode representar as perdas que ocorrem nas linhas transmissão. Este artigo apresenta um modelo de despacho de potência ativa com critério quadrático separável usando métodos de pontos interiores e considerando perdas nas linhas de transmissão. A abordagem busca combinar as vantagens da formulação do modelo DC por fluxo em redes com a eficiência e robustez dos métodos de pontos interiores e a consideração de perdas na transmissão com o grafo generalizado. Ela explora em profundidade a estrutura matricial particular do problema, reduzindo o sistema linear a ser resolvido à dimensão do número de barras ou de laços independentes. Em ambos os casos, a matriz resultante é invariante durante as iterações, podendo ser fatorada a priori. Uma heurística eficiente foi também desenvolvida para obter uma matriz de laços esparsa para representar a segunda lei de Kirchhoff. Esta matriz também é calculada a priori. Resultados numéricos envolvendo sistemas testes do IEEE e do sistema elétrico brasileiro são apresentados. Foi realizada uma comparação entre as soluções fornecidas para a abordagem sem grafo generalizado e a abordagem com grafo generalizado. Os resultados mostram que ambas as versões convergem para todos os testes realizados, indicando que a consideração de grafo generalizado permite ter uma ferramenta eficiente e robusta para o despacho ótimo de potência ativa.

2. Fluxo de Potência Ótimo DC O modelo de fluxo de potência ótimo DC pode ser expresso como o seguinte problema de fluxo em redes: Min D

1 1 f‘Rf + E p’Hp + cp 2 2

S.A.: Af = p – d, Xf = 0 min max min f d f d f , p d p d pmax

(1) (2) (3)

onde: f representa o vetor de fluxo de potência ativa; p representa o vetor de geração de potência ativa; R representa a matriz diagonal das resistências das linhas; H representa a componente quadrática do custo de geração; C representa a componente linear do custo de geração; A representa a matriz de incidência da rede de transmissão; X representa a matriz de reatância da rede de transmissão; d representa o vetor de demanda de potência ativa; fmin, fmax, pmin, pmax são os vetores de limites de fluxo e de geração de potência ativa; D e E são ponderações dos objetos a minimizar.

1455

XXXIII

Simpósio Brasileiro de Pesquisa Operacional

SBPO

A pesquisa Operacional e o Meio Ambiente 6 a 9 de novembro de 2001 - Campos do Jordão - SP

O sistema de transmissão é representado por um fluxo de carga DC com limites no fluxo das linhas. Para que as variáveis de geração e transmissão possam ser expressas simultaneamente no modelo, as leis de Kirchhoff para nós e ramos (2) são apresentadas separadamente [3]. Portanto, o conjunto de restrições para este problema é linear onde, as equações em (2) representam a rede de geração/transmissão e as equações (3) representam as capacidades de geração e transmissão do sistema. No modelo utilizado as duas componentes da função objetivo (1) são quadráticas com variáveis separáveis, a primeira representando o valor econômico das perdas de transmissão e a segunda representando o custo de geração das usinas tanto térmicas quanto hidroelétricas [15].

3. Método de Solução Para simplificar o desenvolvimento do método faremos as seguintes alterações no modelo (1, 2 e 3): ~

~

x As mudanças de variáveis f = f – fmin e p = p – pmin; x As ponderações D e E terão valor unitário. Vale notar que a adaptação do método a ser obtido para o referido modelo é trivial. Com estas alterações, obtemos o seguinte problema: Min

~ ~ ~ 1~ 1 ~ ~ ~ f ´R f  c' f f  p ' H p  c' p p 2 2 ~

~

~

S.A.: A f  p ~

~ max

0d f d f onde c f

~

Rf

~

~

li , X f

min

lv ~

~ max

,0 d p d p

, cp

~

Hp min , l i

 d  Af

min

~

 p min e l v

 Xf

min

Introduzindo as variáveis de folga das restrições de capacidade obtemos (por simplicidade de notação eliminamos os tils): Min

1 1 f’Rf + c’f f + p’Hp + c’p p 2 2

S.A.: Af – p = li, Xf = lv f + sf = fmax, p + sp = pmax (f, sf) t 0, (p, sp) t 0.

(4)

Associado ao problema primal (4) temos o seguinte problema dual já com as variáveis de folga zf e zp introduzidas: Max l’y – (fmax)’wf –

1 1 f’Rf –(pmax)’wp – p’Hp 2 2

S.A.: B’y + zf – wf – Rf = cf , (5) – y(p) + zp – wp – Hp = cp , (zp, wp) t 0, (zf, wf) t 0 onde B

§ A· ¨¨ ¸¸; l ©X¹

§ li · ¨¨ ¸¸ e y ( p) são os elementos da variável dual y correspodentes às barras de © lv ¹

geração. 1456

XXXIII

SBPO

Simpósio Brasileiro de Pesquisa Operacional

A pesquisa Operacional e o Meio Ambiente 6 a 9 de novembro de 2001 - Campos do Jordão - SP

As condições de otimalidade para os problemas (4) e (5) são dadas pela factibilidade primal e dual e pelas condições de complementariedade:

Factibilidade primal

­ Af  p li , Xf l v ° f max , p  s p p max ®f  sf °( f , s ) t 0, ( p, s ) t 0 f p ¯

Factibilidade dual

­ B' y  z f  w f  Rf c f ° ®  y p  z p  w p  Hp c p °( z , w ) t 0, ( z , w ) t 0 f f ¯ p p ­ FZ f e 0, PZ p e 0 ¯S f W f e 0, S p w p e 0

Condições de Complementariedade ®

onde e representa o vetor em que todos elementos tem valor unitário e a notação F = diag(f) para matrizes diagonais é utilizada.

3.1 Método de Pontos Interiores Primal-Dual O primeiro método de pontos interiores polinomial para programação linear foi desenvolvido por Karmarkar [9]. Após alguma controvérsia sobre o desempenho do método, diversos trabalhos mostraram que variações deste método apresentavam desempenho computacional superior ao método simplex [2, 12]. Atualmente, os métodos primais-duais são considerados os mais eficientes [17] e o desempenho destes métodos para problemas quadráticos convexos com variáveis separáveis é similar ao desempenho apresentado para problemas lineares [16]. Em particular, o esforço por iteração é praticamente o mesmo. O método de pontos interiores primal-dual pode ser desenvolvido através da aplicação do método de Newton às condições de otimalidade desconsiderando-se as restrições de não-negatividade e incluindo uma perturbação (P) nas condições de complementariedade. O método parte de um ponto estritamente positivo e não permite que as variáveis se tornem negativas. Obtemos, assim, o seguinte método onde utilizamos os vetores x = (f, p, sf, sp) e t = (zf, zp, wf, wp): Método 3.1 (Método Primal-Dual) Dados (x0, t0) > 0 e y0 Para k = 0, 1, 2, ..., faça

§J k ¨ (1) Escolha V  [0,1) e faça P = V ¨ n © k

k

k

· ¸¸ , onde, n é a dimensão do vetor x e Jk = (xk)’tk. ¹

(2) Calcule a direção de Newton ('x k, 'y k, 't k). (3) Calcule o tamanho dos passos primal e dual para permanecer em um ponto interior Dk = min(1,

W k U pk , W k U dk ) onde Wk  (0,1), U pk

1 § 'xik min i ¨¨ k © xi 1457

· ¸¸ ¹

e U dk

1 § 't ik min i ¨¨ k © ti

· ¸¸ ¹

.

XXXIII

SBPO

Simpósio Brasileiro de Pesquisa Operacional

A pesquisa Operacional e o Meio Ambiente 6 a 9 de novembro de 2001 - Campos do Jordão - SP

(4) Calcule o novo ponto x k 1

x k  D pk 'x k e ( y k 1 , t k 1 )

( y k , t k )  D dk ('y k , 't k ) .

Os parâmetros V e W e o novo ponto inicial serão discutidos mais adiante. A direção de Newton é definida pelo seguinte sistema linear (o índice k será desconsiderado para maior clareza):

­ A'f  'p ri ° X'f r v ° °'f  's f r f ° °'p  's p rp °° B' 'y  'z f  'w f  R'f ry ® ° 'y ( p )  'z p  'w p  H'p rg ° z f 'f  F'z f rzf ° ° z p 'p  P'z p rzp °w f 's f  S f 'w f rwf ° °¯w p 's p  S p 'w p rwp onde os resíduos são dados por

­ri °r °v °r f ° °r p °°ry ® °rg °rzf ° °rzp °rwf ° °¯rwp

l i  Af  p l v  Xf f max  f  s f p max  p  s p c f  B' y  z f  w f  Rf c p  y ( p )  z p  w p  Hp P e  FZ f e P e  PZ p e Pe  S f W f e P e  S pW p e

3.2 Método Preditor-Corretor No método preditor-corretor dois sistemas lineares determinam as direções. Primeiramente é ~

~

~

calculada a direção afim ( ' x, ' y, ' t ) resolvendo o sistema linear (6) com P = 0. Em seguida, a direção desejada é obtida resolvendo o seguinte sistema linear [10]:

1458

XXXIII

SBPO

Simpósio Brasileiro de Pesquisa Operacional

A pesquisa Operacional e o Meio Ambiente 6 a 9 de novembro de 2001 - Campos do Jordão - SP

­ A'f  'p ri ° X'f r v ° °'f  's f r f ° °'p  's p rp ° B ' 'y  'z f  'w f  R'f ry °° ® 'y ( p)  'z p  'w p  H'p rg ~ ° '  ' z f F z r f zf ° f ~ ° ° z p 'p  P'z p rzp ~ ° w s S w r '  ' f f f f wf ° ~ ° °¯w p 's p  S p 'w p rwp onde os novos resíduos são dados por:

­~ °rzf °r~ ° zp ® ~ °rwf ° ~ °¯rwp

~

~

~

~

P e  FZ f e  ' F ' Z f e P e  PZ p e  ' P ' Z p e ~

~

P e  S f W f e  'S f 'W f e ~

~

P e  S pW p e  ' S p ' W p e

3.3 Detalhes de Implementação Na implementação dos métodos de pontos interiores foram os seguintes parâmetros têm valor fixo:

§~· ¨J ¸ W = 0.99995 e V = n-1/2. Para o método preditor-corretor, P é dado pela seguinte relação: ¨ ¸ ¨J ¸ © ¹ 2 ~ ~ ~ J onde J ( x  ' x)' (t  ' t ) . Entretanto, se J < 1 então P = 2 para ambos os métodos. n

2

§ ~ · ¨J ¸ ¨¨ n 2 ¸¸ © ¹

O seguinte ponto inicial foi adotado:

f0 3.3.1

s 0f

f

max

2

; p0

s 0p

p max ; y0 2

0; z 0f

w 0f

( R  I )e; z 0p

w 0p

e.

Detalhes de Implementação e Resolução

Uma vantagem da equação X f = 0 é a possibilidade de reescalar os valores das reatâncias dev cada linha sem nenhuma preocupação quanto à dimensão utilizada. Em outras palavras, cada linha da matriz X pode ser multiplicada por uma constante com o único objetivo de se obter melhor estabilidade numérica dos métodos de pontos interiores. Experimentos com esta idéia deverão realizados em futuros trabalhos.

1459

XXXIII

SBPO

Simpósio Brasileiro de Pesquisa Operacional

A pesquisa Operacional e o Meio Ambiente 6 a 9 de novembro de 2001 - Campos do Jordão - SP

Maiores detalhes quanto a resolução do sistema linear, um estudo mais aprofundado da estrutura matricial deste problema, a utitilização de uma árvore geradora e a formação da matriz de reatância podem ser vistos em [4, 13, 15, 16].

4. Grafo Generalizado A utilização do grafo generalizado é uma tentativa de que o modelo matemático leve em conta as perdas que ocorrem no processo de transmissão. Maiores detalhes sobre a utilização de grafo generalizado em [7,8]. Porém, como a perda depende do fluxo existente em um arco, contabilizaremos as perdas nos arcos da seguinte forma: (1) Calcule o valor dos fluxos de potência ótimo (FPO) sem levar em conta as perdas. (2) A partir dos valores dos fluxos, calcule os ganhos associados a estes fluxos pela fórmula para os arcos i = 1,...,n: x Pperda (i) = R(i)*(f(i)^2); x perda(i) = (n*Pperda(i)) / ((¦R(i))*(¦f(i)^2)) onde Pperda(i) é a potência perdida no arco i, perda(i) é a perda em valores percentuais do arco i dado o fluxo de potência f(i) neste arco. (3) Insira na matriz A os valores das perdas obtidas e resolva novamente o FPO. (4) Com a nova solução de (3), obtenha novos valores de perdas como em (2). (5) Repita (3) e (4) até que a norma da diferença entre os fluxos ótimos seja menor que H.

Embora não seja se tenha como provar formalmente que o procedimento computacional anterior convirja, como veremos a seguir, a convergência ocorreu para todos os casos testados. 5. Resultados Numéricos Todos os testes foram realizados em uma SUN ULTRA 1 utilizando o software MATLAB. A precisão adotada é de 10-8. Estes experimentos visam mostrar como estes métodos obtém bom desempenho, principalmente, quanto à velocidade e robustez. O método utilizado é o preditor-corretor, dado que seu desempenho é superior ao primal-dual para o caso sem ganhos [13]. Sistema Barra Carga(MW) Total Iterações 30 283 28 IEEE 118 4242 24 IEEE 1654 32326 9 SSE 1732 35658 9 SSE Tabela 1: Número de Iterações e tempo de CPU(seg.).

Tempo 2,43 4,29 47,34 52,40

É importante observar que a coluna “Total de Iterações” leva em conta o número de iterações do algoritmo preditor-corretor levou para todas as modificações de valores dos ganhos, usando uma precisão H = 0.1 para a norma da diferença entre os fluxos de potência ótimos. No caso do arquivo “IEEE30”, cada FPO com um dado conjunto de valores de perdas demandou 8 iterações de preditorcorretor, sendo que ocorreram 4 mudanças de perdas. Para o caso do “IEEE118” foram 4 mudanças demandando 7 iterações de preditor-corretor. 1460

XXXIII

SBPO

Simpósio Brasileiro de Pesquisa Operacional

A pesquisa Operacional e o Meio Ambiente 6 a 9 de novembro de 2001 - Campos do Jordão - SP

Já para os exemplos “SSE1654” e “SSE1732” foram 3 mudanças de valores nos ganhos, sendo que cada FPO resultante demandou 3 iterações de preditor-corretor. 6. Conclusões e Trabalhos Futuros

Este trabalho apresenta uma formulação em redes do despacho ótimo de potência ativa e o modelo resultante é resolvido por método de ponto interiores para diversos valores de perdas de fluxo do sistema até um certo critério de convergência H. A resolução dos FPO´s por diversos valores de perdas dos fluxos é uma tentativa para modelar a relação não-linear existente entre as perdas em cada arco da rede e o respectivo fluxo. Duas características apresentadas pelo método de pontos interiores devem ser destacadas. Primeiro é a robustez. Mesmo para problemas de grande porte, o método comverge bem, sem apresentar instabilidade numérica com um precisão maior que a necessária em uma aplicação prática. A segunda característica é a velocidade. O maior número de iterações foi 8 iterações do método preditor-corretor, para um dado valor de perdas, mesmo para sistemas muito carregados. O bom desempenho dos métodos de pontos interiores aplicados ao modelo de potência ótimo DC aponta para a adaptação destes resultados ao problema de pré-despacho como uma continuação natural deste trabalho. Vale destacar, ainda, que os resultados obtidos foram compatíveis com o caso em que a perda do sistema não é considerada [13]. Pode-se observar, ainda, maior geração de potência, o que é coerente com a consideração de perdas para o sistema. Para trabalhos futuros, planeja-se comparar esta forma de avaliação de perdas na rede com outras como, por exemplo: x Considerar as perdas como números fuzzy; x Utilizar perdas lineares por partes ao invés de gerar diversos FPO´s com diferentes valores para as perdas até que a norma da diferença dos fluxos de potência associado aos mesmos seja menor que um valor H [7, 8]; x Comparar com a abordagem não-linear que leva em conta diretamente a perda em função do fluxo de potência; Todas as iniciativas consideradas antes têm o propósito de se estar verificando qual a melhor relação (custo)/(benefício), ou seja, a melhor relação (custo computacional) / (qualidade da solução fornecida pela abordagem) ao considerarmos as perdas de transmissão em problema de fluxo de potência ótimo.

Referências Bibliográficas [1] Ahuja, Ravindra K., Magnanti, Thomas L., Orlin, James B., “Network flows: theory, algorithms and applications”, Upper Saddle River: Prentice Hall, 1993. [2] Adler, I. Resende, M. G. C., Veiga, G. & Karmarkar, N., “An implementation of Karmarkar algorithm for linear programming”, Mathematical Programming 44:297-335, 1989. [3] Carvalho, M. F. Soares, S. & Ohishi, T., “Optimal active power dispatch by network flow approach”, IEEE Transactions on Power Systems 3(3): 1640-1647,1988. [4] Duff, I. S., Erisman, A. M. & Reid, J. K., “Direct Methods for Sparse Matrices”, Claredon Press, Oxford. 1461

XXXIII

SBPO

Simpósio Brasileiro de Pesquisa Operacional

A pesquisa Operacional e o Meio Ambiente 6 a 9 de novembro de 2001 - Campos do Jordão - SP

[5] Franco, P. Carvalho, M. F. & Soares, S. , “A network flow model for short-term hydrodominated hydrotermal scheduling problem”, IEEE Transaction on Power Systems 9(2): 1016-1021, 1994. [6] Granville, S. , “Optimal reactive power dispatch through interior point methods”, IEEE Transactions on Power Systems 9(1): 136-146, 1994. [7] Glover, F., Klingman, D., Phillips, Nancy V., “Network Models in Optimization and Their Applications in Practice”, Wiley-Interscience Series in Discrete Mathematics and Optimization, 1992. [8] Jensen, Paul A., Barnes, J. Wesley, “Network Flow programming”, New York: Wiley, 1980. [9] Karmarkar, N. “A new polinomial-time algorithm for linear programming”, Combinatorica 4(4): 373-395, 1984. [10] Mehrotra, S. “On implementation of a primal-dual interior point methods”, SIAM Journal on Optimization 2(4): 575-601. [11] Momoh, J. A., El-Hawary, M.E. & Adapa, R., “A review of selected optimal power flow literature to 1993, part II newton, linear programming and interior point methods”, IEEE Transactions on Power Systems 14(1): 105-111. [12] Oliveira, A.R.L. & Lyra, C. “Implementação de um método de pontos interiores para programação linear”, Revista SBA: Controle e Automação 3(2): 370-382, 1991. [13] Oliveira, A.R.L., Soares, S. & Nepomuceno, L. “Short Term Hydroelectric Scheduling Combining Network Flow and Interior Point Approaches”, IEEE Transactions on Power Systems 20(1):100-121, 2000. [14] Quintana, V. H. Torres, G. L. & Medina-Palomo, J., “Interior point methods and their applications on power systems: A classification of publications and software codes”, IEEE Transactions on Power Systems 15(1): 170-176, 2000. [15] Soares, S. & Salmazo, C. T., “Minimum loss predispatch model for hydroeletric systems”, IEEE Transactions on Power Systems 12(3): 1220-1228, 1997. [16] Vanderbei, R. J., “Symmetric quasi-definite matrices”, SIAM J. Optimization 5(1): 100113, 1995. [17] Wright, S. J., “Primal-Dual Interior Point Methods”, SIAM Publications, SIAM, Philadelphia, PA, USA, 1996.

1462