Upload
internet
View
119
Download
13
Embed Size (px)
Citation preview
Introdução ao Introdução ao Desenvolvimento de Desenvolvimento de
Aplicações Paralelas e Aplicações Paralelas e DistribuídasDistribuídas
Djalma M. FalcãoDjalma M. Falcão
Março-Abril, 2002Março-Abril, 2002
2
Resumo Introdução Simulação da dinâmica eletromecânica Simulação de transitórios eletromagnéticos Estimação de estado distribuída Otimização I: FPO/FPORS Otimização II: Metaheurísticas/aplicações Otimização III: Programação Hidrotérmica Avaliação da segurança dinâmica Avaliação da confiabilidade composta (Carmen) Ajuste de estabilizadores usando AGs Método dos elementos finitos (Alvaro) Aplicações reais
IntroduçãoIntrodução
Computação em Sistemas Computação em Sistemas Elétricos de PotênciaElétricos de Potência
4
Cenário Atual
Planejamento e operação – Novo contexto econômico: privatização,
reeestruturação , co-geração, geração distribuída, etc.
– Equipamentos rápidos de controle eletrônico: FACT’s e HVDC– Operação próxima dos limites
Ferramentas computacionais– Poderosa para tratar:
Modelos muito complexosPossibibidades de solução não usuais
Deficiência de pessoal
5
Evolução da Computação em Sistemas Elétricos de Potência Grande desenvolvimento nas últimas três
décadas– Técnicas para manipulação de matrizes esparsas– Introdução de conceitos de engenharia nos algoritmos
Melhorias modestas no desempenho se baseadas em metodologias convencionais– Novos métodos numéricos– Novos processadores
Possibilidade de grandes ganhos– Novos técnicas de desenvolvimento de aplicações– Sistemas inteligentes– Computação de Alto Desempenho
6
Requisitos
Robustez Amigabilidade Integração Capacidade de Aprendizado Resposta Rápida
Novos Algoritmo Visualização Novos Amb.
Desenvolvimento Sistemas Inteligentes CAD
FerramentasInteligentes
Ferramentas de Visualização
AlgoritmosRobustos
Ambiente de Computação de Alto Desempenho
7
CAD em SEP Obviamente paralelizáveis
– Decomposição natural em problemas quase totalmente independentes
– Exemplos: análise de contingências (estática e dinâmica), confiabilidade (simulação Monte Carlo), etc.
Não obviamente paralelizáveis – Requer estudo complicado de decomposição para se
atingir razoável grau de paralelismo nas tarefas (Ax=b)– Exemplos: simulação da dinâmica
Situação intermediária– Exemplos: transitórios eletromagnéticos, estimação de
estado, fluxo de potência com restrições de segurança, etc.
8
Áreas de Aplicação
Controle em Tempo-Real– Avaliação da segurança usando modelos dinâmicos
(estabilidade transitória, peq. perturbações, tensão)– Fluxo de potência ótimo com restrições de segurança
Simuladores em Tempo-Real– Teste de equipamentos e esquemas de controle
Avaliação probabilística– Confiabilidade composta, curto-circuito
Processos automáticos de análise e síntese– Planejamento da expansão sistemas de transmissão
e distribuição
9
Objetivos do Curso
Fornecer uma visão geral dos tipos de problemas e soluções enfrentadas na aplicação de CAD em sistemas elétricos depotência
Tipos de aplicações– Desenvolvidas no grupo da COPPE– Desenvolvida em outros grupos– Idéias para desenvolvimento
Evolução da pesquisa na área– Algumas aplicações descritas de pouco interesse
atual
Simulação da Dinâmica Simulação da Dinâmica EletromecânicaEletromecânica
11
Introdução
Um dos problema mais estudados Motivações principais:
– Avaliação da segurança em tempo-real– Simuladores em tempo-real
Dificuldade– Problema fortemente acoplado (rede)
Resultados obtidos– Razoáveis na primeira geração de computadores
paralelos comerciais– Possibilidade de melhoria substancial com nova
geração de computadores paralelos
12
),(0
),(
zxg
zxfx
Modelo Matemático
A B
C
G
G G
G
G G
x : variáveis de estadoz : variáveis das equações algébricasf , g : funções não-lineares
G
13
Esquema Alternado Implícito
Algebrização das equações diferenciais em cada passo de integração usando método implícito (regra trapezoidal)
Solução alternada dos sistemas de equações algébricas
Representação
),(
),(
VEhu
YVVEI
BuAxx
14
Esquema Simultâneo Implícito
Solução simultânea dos dois conjuntos de equações algébricas em cada passo de integração
Representação
Solução pelo Método de Newton
0),(
0),(
e
e
VxG
VxF
1
),(
),(
k
e
k
e
e
V
x
YS
RQ
VxG
VxF
15
Paralelização do EAI
Equações diferenciais naturalmente desacopladas– Acoplamento apenas na mesma máquina
Equações algébricas acopladas– Requer decomposição para solução paralela– Estrutura da matriz Y
Quase-bloco diagonalBlocos: áreasFora-dos-blocos: interconexões
A
B
C
NBDF
16
Paralelização do ESI
Sistemas de equações em cada iteração do método de Newton é acoplado
Também exige esquema de decomposição Estrutura da matriz de coeficientes
Máquina
Rede
BBDF
17
Métodos Paralelos
Paralelização no espaço– Método VDHN paralelo (Chai,Zhu,Bose,Tylavsky)– Método Newton-Matriz W (Chai,Bose)– Simulador Digital em Tempo-Real (Taoka,Iyoda, e outros)– Híbrido Gradiente Conjugado/Fatoração LU (Decker,
Falcão, Kaszkurewicz)
– Gradiente Conjugado Completo (Decker, Falcão, Kaszkurewicz)
Relaxação de forma de onda (Crow, Ilic)
Paralelização no espaço e no tempo– Gauss-Jacobi/Block-Newton (LaScala, Bose, e outros)– Gradiente Conjugado (Decker, Falcão, Kaszkurewicz)
18
Solução de equações lineares
Métodos Diretos– Eliminação de Gauss– Fatoração LU ou LDU– Matrizes W
Métodos Iterativos– Jacobi– Gauss-Seidel– Gradiente Conjugado
Métodos Híbridos - Bloco Iterativos– Método iterativo considerando blocos como elementos– Solução de cada bloco por método direto
19
Método Híbrido GC-LU
Baseado no EAI e decomposicão da rede na BBDF
Formulação:
s
p
sTp
TTpp
s
p
V
V
V
V
YYYY
YY
YY
YY
I
I
I
I
2
1
21
22
11
2
1
20
Solução em duas fases
Fase 1 (Gradiente Conjugado Paralelo)
Fase 2 (Fatoração LU em cada processador)
ii
p
i
Tiss
ii
p
i
Tiss
IYYII
YYYYY
1
1
1
1
siiii VYIVY Para i = 1,2,...,p, resolva
ss IYV
21
GC Completo
Solução da equação completa da rede pelo método GC (pré-condicionado) paralelo
Matriz decomposta na forma quase-bloco diagonal (NBDF)
Pré-condicionador: matriz bloco-diagonal Vantagem em relação ao híbrido: GC aplicado
a sistema de equações de grande porte
22
Paralelização no tempo e no espaço com GC
Solução de vários passos de integração simultaneamente ( janela de integração)
Cada passo de integração resolvido em um processador
Cada processador pode ser um cluster de q processadores (paralelização no espaço)
Solução dos sistemas lineares:– Método do Gradiente Bi-conjugado (Bi-CG)– Método Bi-CGSTAB
23
Formulação
p
p
pp
pppppp
p
p
V
x
V
x
V
x
YS
RQRQ
YS
RQRQ
YS
RQ
G
F
G
F
G
F
2
2
1
1
11
22
222121
11
11
2
2
1
1
00
00
24
Síntese dos Resultados Implementação paralela:
– NCP1: hipercubo, 8 nós, Transputer T800– Intel iPSC/860: hipercubo, 8 nós, i860
Sistemas Testes:– Região Sul-Sudeste: 88 ger., 616 barras, 995 ramos
Eficiência– 31% a 85%– Influenciada negativamente pelo tipo de computador paralelo
usado(alta relação comunic./proces.)
Gradiente Conjugado– Robusto– Alternativa confiável aos métodos diretos– Busca de pre-condicionadores
Decomposição de RedesDecomposição de Redes
26
Decomposição de Redes Objetivos
– Numero de subredes igual ao número de processadores– Cada subrede deve ter aproximadamente o mesmo grau
de complexidade tendo em vista solução seqüencial– Comunicação entre processadores deve ser minimizada– Assegurar convergência da solução bloco-iterativa
Solução– Difícil se tentada por uma abordagem teórica– Estudada bastante com outros objetivos– Abordagem proposta por Vale, Falcão e Kaszkurewicz:
Combinação de informações teóricas e heurísticasValidação através de testes em ambientes paralelos
27
Método proposto
Princípio
Agregação dos nós das sub-redes a partir de um dado número de nós sementes
Semente
28
Etapas do método
Classificação de nós– Ponderações em função da soma das susceptâncias
dos ramos ligados a este nó
Escolha dos nós sementes– Por experiência ou baseado nas ponderações
(escolhe-se os nós mais fortes)
Formação das sub-redes– Algoritmos para BBDF e NBDF
Seleção das decomposições– Critério para escolher decomposições com melhor
desempenho potencial
29
Ponderações
T
i
l
l
l
bl
M
B
li
b
BM
niB ,...,1,
i : conjunto das barras conectadas ao nó i
T : conjunto dos ramos da rede
Bl : susceptância do ramo lb : número de ramos da rede
30
Algoritmo (NBDF)
31
Resultados
Testada em conjunto com métodos paralelos de simulação da dinâmica vistos anteriormente
Resultados superiores às decomposições obtidas por tentativas de um analista experiente
Vantagem de ser (semi) automática
Simulação de Transitórios Simulação de Transitórios EletromagnéticosEletromagnéticos
33
Simulação de Transitórios Eletromagnéticos
Aplicação– Planejamento (coordenação de isolamento)– Testes para equipamentos e esquemas de controle
(simulador em tempo-real)
Elevados requisitos computacionais Abordagens possíveis
– Simulação analógica (TNA)– Simulação digital (EMTP)– Híbrida
34
Modelos
Subestação Subestação
Subestação
LT
LT LT
Parâmetros Concentrados
Parâmetros Distribuídos
35
Modelos dos Elementos
Integração Trapezoidal
h/2C
I C(t)
2L/h
I L(t)
Indutor Capacitor
h : passo de integração
36
Modelo de Linhas (Travelling Waves)
A
A B
B
Retardo ()
Desacoplamento
I tA
H ( ) I tB
H( )
37
Modelo Matemático
IS : Fontes de corrente independentesIL: Fontes de corrente no circ. eqv. dos indutoresIC : Fontes de corrente no circ. eqv. dos capacitoresIH : Fontes de corrente no circ. eqv. das linhas de
transmissão (determinadas em passos de integração anteriores: t- )
FA(.) e FB(.): elementos não-lineares
HB
HA
CB
CA
LB
LA
SB
SA
BB
AA
B
A
B
A
I
I
I
I
I
I
I
I
EF
EF
E
E
G
G
)(
)(
0
0
38
Implementação Paralela
Decomposição da rede– Utiliza o desacoplamento natural do modelo de
linhas– Decomposição geográfica
Balanço de carga– Etapa decisiva do método– Em geral número de sub-redes maior que o número
de processadores– Foi desenvolvida técnica especial para efetuar esse
balanço automáticamente
39
Resultados Implemetações paralelas no computador:
– NCP1: hipercubo, 8 nós, Transputer T800
Sistemas Testes: Caso Barras Ramos Linhas Sub-
redes A 561 1115 66 48
B 1026 2457 146 77
Eficiências alcançadas (%): Caso Número de Processadores 2 4 8 A 98 89 51 B 98 96 86
Estimação de EstadoEstimação de Estado
41
Formulação
~
~
CENTRO
DE
CONTROLE
COMUNICAÇÕES
42
Estado Atual
Estimação de estado centralizada Intervalo entre estimativas: 5-10 m Intervalo entre varreduras do SCADA: 1-10 s Rede supervisionada: transmissão principal Tendências
– Menor intervalo entre estimativas – Ampliar rede supervisionada
Problema– Realizar estimação de estado em redes com
milhares de barras em alguns segundos– Estimador rápido e robusto
43
Abordagem Distribuída
Estimação de estado é um problema local O estado de uma área é principalmente
determinado por informaçãoes colhidas na própria área
Características da abordagem– Realiza estimações de estado localmente– Combina informações através de técnica de
otimização baseada em restrições de acoplamento– Caso falhe comunicação entre áreas, os estimadores
locais continuam a produzir estimativas
44
Modelos Integrados
Modelo completo
Modelo desacoplado
)(xhz
qqq
ppp
vhz
vhz
),(
),(
45
Modelo Distribuído
r: número de áreasxk: vetor de estado da área kzk: vetor de medidas da área k
rkvhz
rkvhz
kq
kkkq
kq
kp
kkkp
kp
,...,1,),(
,...,1,),(
46
Restrições de Acoplamento
Restrições de acoplamento:
Linha não-nula de Ai corresponde às restrições de acoplamento da área i
Area 1
Area 3Area 2
03
2
1
321
AAA
47
Formulação do Problema
0
0
(.)]}[][(.)][
(.)][][(.)]{[2/1minimize
1
1
1
1
1
kM
k
kp
kM
k
kp
qkq
kq
Tkq
kq
kp
kp
kp
Tkp
M
k
kp
VA
Aasujeito
hzRhz
hzRhz
48
Algoritmo Básico (Modelo Ativo)
MkiACii
ACAN
iANi
MkhzRHCii
pkp
kp
kk
Tkp
kp
M
k
kp
kp
kM
k
kppp
kp
kp
kp
kp
kp
kk
oacoplamentderestriçõesdasAplicação
LocaissEstimativa
,...,1,)1(][][)1()1(
][][
)1()1(
,...,1,(...)][]][[][)()1(
11~
1
1
~
1
1
11~
oCoordenaçã
49
Algoritmo Básico (Modelo Ativo)
Deprezando elementos fora da diagonal de
jeiáreasdasganhomatrizes
dasinversadadiagonaiselementossãoe
iigg
gi
iii
kr
krj
rrkrr
krrk
kkk
jrr
krr
~~~
~~
gg
)]1()1([)1(
)1()1()1(
50
Resultados
Simulação de ambiente distribuído Sistemas testes: IEEE 14, 30, 118 barras Eficiências: 70% a 90% Precisão: erros desprezíveis se comparado ao
esquema integrado Restrições de acoplamento: só importante se
redundância de uma das áreas é baixa
Avaliação da Segurança Avaliação da Segurança Dinâmica em Tempo RealDinâmica em Tempo Real
52
Introdução
Projeto desenvolvido em conjunto por Furnas, Efei e Coppe (97-98)– Furnas: concepção geral, fluxo de potência e
simulador da dinâmica– Efei: previsão de carga em curto-prazo– Coppe: Ambiente de processamento paralelo e
integração de aplicativos
Dotar novo centro de controle de módulo independente para avaliação da segurança dinâmica em tempo-real
53
Configuração do Software
Previsão de Carga
Seleção de Contingências
Simulação no Tempo
Análise dos Resultados
Medidas Corretivas
Seleção de Contingências• Estabilidade Transitória (Função Energia)• Estabilidade de Tensão (Vetor Tangente)• Grande Número de contingência (100)• Avaliação Independente• Execução Paralela
Simulação no Tempo•Apenas para contingências selecionadas(10-20) • Simulação passo-a-passo• Método de ordem e passo variáveis• Simulações independentes• Execução Paralela
Fluxo de Potência Continuado
SCADAEstimação de Estado
54
Configuração do Hardware
NetworkHub
Anel de Fibra Ótica
Servidor Cliente 1 Cliente 2 Cliente 5
Servidor
W1
W2
W3
Wn
Ambiente DEC Alpha
Ambiente de PCs
Sistema ComputacionalPrincipal do EMS de Furnas
55
Ambiente Computacional
Hardware– Três (seis) PCs Pentium 200 MHz– Fast Ethernet Network (100 Mbs)– Arquiitetura mestre-escravo– Conexão física: estrela
Software– MS Windows NT Server and NT Workstation v. 4.0– Message Passing Interface (MPI)– Compilador Fortran PowerStation – Modelo de programação: mestre-escravo
56
Configuração da Rede para Teste
ServidorPentium 200 MHz
128 Mb RAM2.1 Gb HD
Escravo 1Pentium 200 MHz
64 Mb RAM2.1 Gb HD
Escravo 2Pentium 200 MHz
64 Mb RAM2.1 Gb HD
Hub3COM Office Connect
8/TP100Fast Ethernet
57
Teste
Sistema Teste– Sistema Brasileiro da Região Sul-Sudeste – (1772 barras, 2550 ramos, 84 geradores)– 23 contingencias ( 9 contingencies selecionadas )
Programas de Simulação– Fluxo de Potência Continuado (LFLOW - Furnas)– Simulação Dinâmica (POWERSIM - Furnas)
58
Resultados
Experiência I - Rede com 3 PCs
Tarefa Tempo (min)
Seqüencial Paralelo
Seleção de Contingências 3,70 1,98
Simulação Dinâmica 21,75 8,15
J. Jardim, C.A. da S. Neto, A.P. Alves da Silva, A.C. Zambroni de Souza, D.M. Falcão,C.L.T. Borges, and G.N. Taranto, “A Unified Online Security Assessment System“, Proceedings of the 38th CIGRÉ Session - 2000 Session, Paris, França, 27 Ago./1 Set.de 2000.
Resultado mais realista: sistema com 700 barras, 1000 ramos e 80 geradores.Contingências pré-selecionadas: 98. Rede com 5 PCs. Tempo total: 2m30s.
59
Outra Aplicação
Sistemas para avaliação da segurança dinâmica em tempo-real desenvolvido pela Powertech Labs (Vancouver, Canada)– TSAT - Transient Security Assessment Tool– VSAT - Voltage Security Assessment Tool
WEB: http://www.powertechlabs.com
OTIMIZAÇÃOOTIMIZAÇÃO
61
Problemas de Otimização
Fluxo de Potência Ótimo com Restrições de Segurança (FPORS)– Otimização da condição estática de operação
incluindo contingências– Problema de programação não-linear de grande porte
Expansão de Redes de Transmissão e Distribuição– Problema de otimização combinatória– Branch&Bound, Metaheurísticas (AG, SA, BT, etc.)
Operação de Sistemas Hidrotérmicos– Programação dinâmica estocástica
Fluxo de Potência Ótimo com Fluxo de Potência Ótimo com Restrições de Segurança Restrições de Segurança
(FPORS)(FPORS)
63
Formulação do FPO
ui : vetor de variáveis de controle (ger. ativa/reativa, tensão, taps, etc.)
xi : vetor de variáveis de controle (módulo e ângulos de fase das tensões)
f (·) : função objetivo;
gi (·): equações do fluxo de potência;
hi (·): limites operativos
0),(
0),(
),(min
xuh
xug
asujeito
xuf
i
i
64
Solução do FPO
Problema estudado desde a década de 60 Primeiros produtos adequados para utilização
prática disponibilizados no final dos 80s Métodos utilizados em pacotes comerciais:
– Programação Linear Succesiva– Programação Quadrática Seqüencial– Método de Newton– Métodos dos Pontos Interiores
Ferramenta complexa e ainda relativamente pouco difundida no ambiente das empresas de energia elétrica
65
FPORS Otimizar (min./max. critério) ponto de operação (caso base)
incluindo o efeito de contingências (desligamento de linhas, trafos, etc.)
Aplicações: controle em tempo-real, métodos automáticos de planejamento, confiabilidade composta, etc.
Controle Preventivo– O caso base dever ser suficientemente robusto para
garantir a viabilidade dos estados em contingência– Conservativo
Controle Corretivo– Prevê ações corretivas pós-contingências em intervalo de
15-30 minutos– Mais adequado ao ambiente competitivo
66
Formulação Preventiva do FPORS
n: número de contingências (i = 0: caso base; i = 1, …,n: contingências);
ui : vetor de variáveis de controle (ger. ativa/reativa, tensão, taps, etc.)
xi : vetor de variáveis de controle (módulo e ângulos de fase das tensões)
f (·) : função objetivo;
gi (·): equações do fluxo de potência;
hi (·): limites operativos
nixuh
nixug
asujeito
xuf
ii
ii
,...,2,1,0,0),(
,...,2,1,0,0),(
),(min
0
0
00
67
Formulação Preventiva do FPORS
n: número de contingências (i = 0: caso base; i = 1, …,n: contingências);
ui : vetor de variáveis de controle (ger. ativa/reativa, tensão, taps, etc.)
xi : vetor de variáveis de controle (módulo e ângulos de fase das tensões)
f (·) : função objetivo;
gi (·): equações do fluxo de potência;
hi (·): limites operativos
nixuh
nixug
asujeito
xuf
ii
ii
,...,2,1,0,0),(
,...,2,1,0,0),(
),(min
0
0
00
68
Formulação Corretiva do FPORS
i(·): distância no espaço de controles (norma Euclidiana, p.ex.);
i : vetor de limites superiores da variação permitida nas variáveis de controle para corrigir violações no período de tempo considerado.
niuu
nixuh
nixug
asujeito
xuf
iii
iii
iii
,...,2,1,0,)(
,...,2,1,0,0),(
,...,2,1,0,0),(
),(min
0
00
Restrições de Acoplamento
69
Características do FPORS Dimensão Elevada (Exemplo)
– 1.000 barras, 50 contingências– 2.000x51 = 102.000 restrições de igualdade– 4.000x51 = 204.000 restrições de desigualdade
Estrutura– n+1 problemas de PNL fracamente acoplados– grande maioria das restrições de desigualdade não-
ativas na solução
Adequado para solução em paralelo utilizando algum método de decomposição de problemas de PNL
70
Decomposição de Benders
Decomposição em um Problema Mestre e n Subproblemas
Algumas variáveis chaves são mantidas constantes nos Subproblemas e ajustadas no Problema Mestre
Iteração entre Problema Mestre e Subproblema é mantida até a convergência
Problema Mestre
Subproblema nSubproblema 2Subproblema 1 . . .
Variável Chave Corte de Benders
71
Problema Mestre
niuu
xuh
xug
asujeito
xuf
Tii
i
i
,...,2,1,0)(
,0),(
0),(
),(min
*00
*
00
00
00
Cortes de Benders
i* : obtido da solução dos subproblemas;
i : multiplicador de Lagrange associado à i-ésima restrição de acoplamento dos subproblemas
u0* : solução ótima atual para as variáveis de controle do caso base
72
Subproblemas
0
0),(
0),(
min
0
s
suu
xuh
xug
asujeito
sd
ii
iii
iii
i
d : constante positiva
u0* : variável chave (valor atual das variáveis de controle do caso base)
: norma Euclidiana
O único objetivo desse subproblema é garantir a viabilidade da solução para um dado u0* . Portanto, s deve ser nulo na solução final, isto é, i* = 0.
Se i* 0, então u0 deve ser trazido para perto de ui de forma a satisfazer as restrições de acoplamento.
Os multiplicadores de Lagrange i, obtidos na solução desses subproblemas, são as sensibilidades da função objetivo (i* = d.s) a variações nos parâmetros u0* (inviabilidade do subproblema).
73
Algoritmo1. Gere aproximações para os cortes de Benders.
2. Resolva o Problema Mestre com os novos cortes de Benders.
3. Com o valor de u0* obtido no passo anterior, resolva os n Subproblemas.
4. Se i* = 0 em todos os subproblemas, PARE. Os presentes ui*, e correspondentes xi*, são a solução do problema.
Senão, vá para o passo 5.
5. Use os resultados obtidos no passo 3 para gerar n novos cortes de Bender. Vá para o passo 2.
74
Implementação Paralela
Os problemas associados ao caso base e subproblemas são fracamente acoplados
Esses problemas podem ser resolvidos independentemente
Existem implementações síncronas e assíncronas
Várias implementações em máquinas paralelas reais com elevada eficiência
75
Assincronismo
Implementação Síncrona– Todos os subproblemas são resolvidos
completamente e suas soluções são comunicadas ao problema mestre para iniciar uma próxima iteração
Implementação Assíncrona– Utiliza-se o valor mais atual da solução dos
subproblemas, antes mesmo que eses estejam compleamente resolvidos
Implementações assíncronas são mais rápidas porém podem apresentar problemas de convergência
76
Referências S.M. Shahidehpour and V.C. Ramesh, “Nonlinear Programming
Algorithms and Decomposition Strategies for OPF”, IEEE Tutorial Course Optimal Power Flow: Solution Techniques, Requirements, and Challenges, 1996.
A. Monticelli, M.F.V. Pereira, and S. Granville, “Security constrained Optimal Power Flow with Post-Contingency Corrective Rescheduling”, IEEE Transactioms on Power Systems, vol. 2, no. 1, pp. 175-182, February 1987.
HJC Pinto, MVF Pereira and MJ Teixeira, “New parallel algorithms for the security constrained dispatch with postcontingency corrective actions”, Proceedings of the 10th Power Systems Computation Conference, pp. 848-853 Graz, Austria, August 1990.
M. Rodrigues, O.R. Saavedra, and A. Monticelli, “Asynchronous Programming Model for the Concurrent Solution of the Security Constrained Optimal Power Flow Problem”, IEEE Transactioms on Power Systems, vol. 9, no. 4, pp. 2021-2027, November 1994.
Planejamento da Expansão de Planejamento da Expansão de Sistemas de TransmissãoSistemas de Transmissão
Introdução aos Algoritmos Genéticos
78
Formulação
Dada a configuração da rede de transmissão para um determinado ano e a previsão da demanda/geração para um próximo ano, determinar o plano de expansão de custo mínimo (onde, quais e quando novos circuitos devem ser adicionados à rede)
Formulação estática: onde e quais Formulação dinâmica: onde, quais e quando Problema de otimização combinatória mista (varáveis
binárias e reais) não linear Primeiro passo do processo de planejamento: gera
opções de expansão as quais devem ser estudadas com mais detalhes (estabilidade, curto-circuito, etc.)
79
Formulação matemática (modelo DC)
Ckx
Nkgg
Cklxff
Eklff
Cklxf
Eklf
Nkdgff
asujeito
xcz
kl
kk
klklkl
klkl
lkklklkl
lkklkl
kkCl
klEl
kl
klCkl
kl
kk
,1,0
,0
,
,
,0)(
,0)(
,
min
11
00
11
00
10
ckl :custo do ramo kl
E,C: conjuntos dos ramos existentes e candidatos (Ek,Ck subconjuntos dos ramos ligados ao nó k)
N: conjunto de nós da rede
fkl : fluxo de potência no ramo kl
gk : geração no nó k
dk : demanda no nó k
k : ângulo de fase da tensão nó k
kl : susceptância do ramo kl
Não-linear
Variável binária
80
Solução candidata
Nkdr
Nkgg
Cklxff
Eklff
Cklxf
Eklf
Nkdrgff
asujeito
rz
kk
kk
klklkl
klkl
lkklklkl
lkklkl
kkkCl
klEl
kl
Nkk
kk
,0
,0
,ˆ
,
,0)(ˆ
,0)(
,
ˆmin
11
00
11
00
10
Para uma candidata a solução x, obtida por algum procedimento (heurístico?), o problema reduz-se a um problema de programação linear
^
rk: carga não-suprida nó k
z : total de carga não suprida para a solução x; pode ser utilizado como uma medida da inviabilidade da solução
^
^^
81
Métodos de Solução
Métodos de otimização combinatória: eg Branch&Bound: difícil
Procedimentos heurísticos Metaheurísticas
– Algoritmos Evolucionários (Genéticos)– Busca Tabu– Simulated Annealing– GRASP– Particle Sworm Optimization (PSO)– Etc.
82
Algoritmos Genéticos [
Inicie a população Avalie a população inicial Faça_enquanto critério_de_parada não é satisfeito [
Selecione soluções para a próxima população Aplique operadores genéticos Avalie nova população ]
]Seleção,
cruzamento e mutação
83
Exemplo de Codificação do Problema
13 5
4
2
1 0 0 1 0
1 2 3 4 5
1 0 1 1 0
0 0 0 0 1
0 0 0 1 0
1 0 0 1 0
1 1 0 1 1
População AvaliaçãoFunção Adequabilidade
z1
z2
z3
z4
z5
z6Cruzamento
1 0 1 1 0
0 0 0 0 1
1 0 0 0 1
0 0 1 1 0
Seleciona melhores indivíduos
Mutação
Alteração aleatória de 1 ou mais genes
84
Algoritmo [
Inicie a população (candidatos a planos de expansão) Avalie a população inicial ( resolva um PPL para cada indivíduo da população) Faça_enquanto critério_de_parada não é satisfeito [
Selecione soluções para a próxima população (critério: custo da expansão + operação) Aplique operadores genéticos Avalie nova população ]
]
85
AG Paralelos
Essencialmente o mesmo AG porém a avaliação dos indivíduos, e em alguns casos também a aplicação dos operadores genéticos, são paralelizadas
Fácil implementação Ganho de velocidade proporcional ao número
de processadores
86
AGs Distribuídos População divida em algumas poucas sub-populações
as quais são mantidas relativamente isoladas Operador Migração usado para trocar indivíduos entre
sub-populações Vantagens
– Convergência mais rápida (populações menores)– Pode encontrar melhores soluções– Ganho de velocidade se implementado em ambiente
com múltiplos processadores
P1 P2
P3 P4
P1 P2
P3 P4
Planejamento da Expansão de Planejamento da Expansão de Sistemas de DistribuiçãoSistemas de Distribuição
88
Expansão de Redes de Distribuição
Determinar a localização e data de construção de novos trechos de alimentadores primários
Problema de programação combinatória não-linear (modelo de fluxo de potência)
Solução por métodos de programação matemática é bastante difícil e exige esforço computacional muito elevado
89
Exemplo Ilustrativo
RedeExistente Previsão de
Expansão
Ponto de Carga
Sub-Estação
90
Exemplos de SoluçãoRestrição: rede radial
91
Formulação
Minimizar– Custos de instalação de novos ramos– Perdas de energia
Restrições– Conectividade– Radialidade– Queda de tensão
92
Função Adequabilidade
Decodificação
Resolve Fluxo de Potência
Calcula Aptidão
Conexa e Radial?
S
N
Aptidão = 0
Fluxo de Potência calcula tensões nodais e perdas
Aptidão1/ Custo + (1/Perdas)
+ (1/Desvio_Tensão)
Reparo
Formulação Híbrida:Formulação Híbrida:AG + FPOAG + FPO
Javier R. O. Soto, Carlos R. R. Dornellas and Djalma M. Falcão , “Optimal Reactive Power Dispatch Using a Hybrid Formulation: Genetic Algorithms and Interior Point”, Proceedings of the 2001 IEEE Porto Powertech, Porto, Portugal, September 2001.
Planejamento da Operação de Planejamento da Operação de Sistemas HidrotérmicosSistemas Hidrotérmicos
95
Introdução
ObjetivoObjetivo Determinar, a cada período, estratégias de geração
para cada unidade geradora do sistema, de modo a minimizar o custo esperado de operação ao longo de todo o período de planejamento
Custo EsperadoCusto Esperado– Combustíveis das usinas termelétricas– Penalidades por eventuais não atendimentos à
demanda de energia - Déficit
96
Características
Acoplamento Temporal e Espacial: relação entre uma decisão tomada em um estágio e sua conseqüência futura
Natureza Estocástica: impossibilidade de uma perfeita previsão das afluências futuras
Grande Porte: múltiplos reservatórios e otimização multi-período
Não-linear: função de produção das hidrelétricas e custos de operação das termelétricas
Uso Múltiplo da Água: navegação, cheias, irrigação, entre outros
97
Decisões Operativas
Usar Água
Não UsarÁgua
Afluências normais
secas
OK
Déficit de Energia(corte de carga)
Vertimento
OK
Decisão?Decisão 1
Cenário Alternativo 1
Cenário Alternativo 2
secas
Afluências normais
98
Etapas de Planejamento
Divisão em Etapas:
Impossibilidade de englobar todas as complexidades em um modelo matemático único
Necessidade de analisar os efeitos de longo, médio e curto prazos
99
Cadeia de PlanejamentoLongo Prazo (5 anos)
Geração hidro totalGeração térmica totalIntercâmbio entre os subsistemas
Médio Prazo (1 ano)Despacho(1 hora)
Despacho instantâneoRestrições de segurança
Curto PrazoPré-Despacho(1 dia)
Cada ano ou menos
Tempo Real
Cadahora
Desagregação do totalde geração hidráulica em metas de geração para asunidades hidráulicas
(1 semana)
Desagregação dasmetas mensais emmetas horárias paraas usinas hidráulicas
Determinação do perfilde geração que respeita as restrições elétricas e energéticas
100
Problema de Longo Prazo
Características
– Horizonte de Planejamento de 5 anos
– Discretização Mensal
– Difícil conjunção dos fatores: não-linearidades, grande porte e natureza estocástica
– Exige várias simplificações na formulação do problema
Principais Resultados
– Totais de geração e intercâmbios entre subsistemas
– Determinação de riscos no atendimento energético
101
Método de Solução
Programação Dinâmica Estocástica (PDE) Divide o período de estudo em estágios e
determina a melhor decisão a cada estágio, de acordo com o estado em que o problema se encontra– Estágio: variável discreta que divide o período de
estudo em partes elementares, as quais ocorrem modificações no sistema
– Estado: variável que descreve o sistema em um determinado estágio
– Decisão: variável de controle que, aplicada ao sistema no estágio t, determina o estado em que o sistema se encontrará ao final do mesmo
102
Reservatório Equivalente
Elimina a característica de grande porte do problema agregando os diversos reservatórios do sistema em um único reservatório equivalente
Descartam-se variáveis hidráulicas em favor de variáveis energéticas, calculadas para o sistema como um todo
Desvantagens:– Não representa corretamente as restrições
operativas individuais das usinas do sistema– Desconsidera o acoplamento hidráulico existente
entre as usinas– Subestima a capacidade de produção do sistema
hidrelétrico
103
Noções de Programação Dinâmica
Técnica utilizado para resolver problemas de decisão com múltiplos estágios
Técnica de Solução– Princípio de Otimalidade de Bellman: Uma política
ótima deve ser tal que, independentemente da trajetória seguida para chegar a um determinado estágio, as decisões remanescentes devem constituir uma trajetória ótima.
– Faça o melhor que possa onde estiver.
Técnica de Solução– A recursão deve ser realizada no sentido inverso do
tempo
104
Exemplo Genérico
105
Funções de Custo Imediato e de Custo Futuro
Volume Final
FCI FCFFCI: custo da geração térmica no estágio t
FCF: custo esperado da geração térmica do final do estágio t (início de t +1) até ofinal do período de estudo
106
Problema de um Estágio
Supondo conhecida a FCF: t+1 (v t+1 )
v t+1
v tu t
Estágio t
Min z = c (u t) + t+1 (v t+1 )
sujeito a
v t+1 = v t - u t - s t - a t
v t+1 v max
u t u max
FCI
107
Aplicação de PDE
Passo 1: Para cada estágio (t) defina um conjunto de estados (níveis de armazenamento: 100%, 90%, etc.). Suponha o estado inicial conhecido.
1 2 T-1 T
108
Aplicação de PDE
Passo 2: No estágio final (T), resolva um Problema de um Estágio para cada estado (100%, 90%, etc.) e para cada cenário de afluências. Assuma que a FCF é nula.
T
Cenário 1
Cenário 2
Cenário k
109
Aplicação de PDE
Passo 3: Calcule o valor esperado do custo de operação para cada estado. Esses valores são pontos da FCF para o estágio T-1. Interpole
T
FCF para o estágio T-1
110
Aplicação de PDE
Passo 4: Repita o processo para os estados selecionados (de acordo com o princípio da PD) para os estágios T-1, T-2, etc.
1 2 T-1 T
111
Possibilidades de Paralelização
Passo 2: os Problema de um Estágio podem ser resolvidos simultaneamente
Passo 3: supõe-se ser possível a paralelização do cálculo da FCF
Observação: não foi analisado o método PDE Dual o qual é efetivamente utilizado em programas como NEWAVE e DECOMP