Introdução ao Desenvolvimento
de Aplicações Paralelas e
Distribuídas
Djalma M. Falcão
Março-Abril, 2002
Resumo












2
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ção
Computação em Sistemas Elétricos
de Potência
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 complexos
 Possibibidades de solução não usuais
 Deficiência de pessoal
4
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
5
Requisitos





Robustez
Amigabilidade
Integração
Capacidade de Aprendizado
Resposta Rápida





Ferramentas
Inteligentes
Novos Algoritmo
Visualização
Novos Amb. Desenvolvimento
Sistemas Inteligentes
CAD
Ferramentas
de Visualização
Algoritmos
Robustos
Ambiente de Computação de Alto Desempenho
6
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.
7
Á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
8
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
9
Simulação da Dinâmica
Eletromecânica
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
11
G
Modelo Matemático
x  f ( x, z )
0  g ( x, z )
G
G
G
G
A
B
C
G
x : variáveis de estado
z : variáveis das equações algébricas
f , g : funções não-lineares
12
G
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
x  Ax  Bu
I ( E ,V )  YV
u  h( E , V )
13
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
F ( x, V e )  0
G ( x, V e )  0
 Solução pelo Método de Newton
k
 F ( x,V e )
Q R   x 


 V e 
e 
S
Y
G
(
x
,
V
)





14
k 1
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 diagonal
A
 Blocos: áreas
B
 Fora-dos-blocos:
interconexões
C
NBDF
15
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
Rede
Máquina
BBDF
16
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)
17
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
18
Método Híbrido GC-LU
 Baseado no EAI e decomposicão da rede na BBDF
 Formulação:
 I1   Y1
I  
 2 
 
  
I p  
 I s  Y1T

19
Y2
Yp
Y2T
Y pT
Y1   V1 
 
Y2  V2
 
 
 
Y p  V p 
Ys   Vs 
Solução em duas fases
 Fase 1 (Gradiente Conjugado Paralelo)
p
YVs  I s
Ys  Ys   Yi T Yi 1Yi
i 1
p
I s  I s   Yi T Yi 1I i
i 1
 Fase 2 (Fatoração LU em cada processador)
Para i = 1,2,...,p, resolva
20
YiVi  I i  YiVs
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
21
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
22
Formulação
 F1   Q1 R1
G  
 1   S1 Y1
 F2  Q21 R21 Q2 R2
  
0 S 2 Y2
 G2    0
  
  
 Fp  
G  
 p 
23
Q pp1 R pp1 Q p
Sp
0 0
  x1 
  V 
 1 
  x2 



V
 2 




R p   x p 
Y p  V p 
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
24
Decomposição de Redes
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ísticas
 Validação através de testes em ambientes paralelos
26
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
27
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
28
Ponderações
i  
Bl
BlM

Bl
b
li
M
lT
, i  1,...,nb
i : conjunto das barras conectadas ao nó i
T : conjunto dos ramos da rede
Bl : susceptância do ramo l
b : número de ramos da rede
29
Algoritmo (NBDF)
30
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
31
Simulação de Transitórios
Eletromagnéticos
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
33
Modelos
LT
Subestação
Subestação
LT
LT
Subestação
Parâmetros Distribuídos
Parâmetros Concentrados
34
Modelos dos Elementos
Integração Trapezoidal
2L/h
h/2C
I L (t)
I C (t)
Indutor
Capacitor
h : passo de integração
35
Modelo de Linhas
(Travelling Waves)
Retardo ()
A
B
IA (t   )
H
A
Desacoplamento
36
IB (t   )
H
B
Modelo Matemático
S   L  C  H 

G
0
E
F
(
E
)
 A
  A  A A  IA IA IA IA
 0 G  E   F (E )   S    L    C    H 
B   B   B B  IB  IB  IB  IB 

IS : Fontes de corrente independentes
IL: Fontes de corrente no circ. eqv. dos indutores
IC : Fontes de corrente no circ. eqv. dos capacitores
IH : 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
37
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
38
Resultados
 Implemetações paralelas no computador:
– NCP1: hipercubo, 8 nós, Transputer T800
 Sistemas Testes:
Caso
A
B
Barras
561
1026
Ramos
1115
2457
Linhas Sub-redes
66
48
146
77
 Eficiências alcançadas (%):
Caso
A
B
39
Número de Processadores
2
4
8
98
89
51
98
96
86
Estimação de Estado
Formulação
CENTRO
DE
CONTROLE
~
COMUNICAÇÕES
~
41
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
42
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
43
Modelos Integrados
 Modelo completo
z  h(x)  
 Modelo desacoplado
z p  h p ( , v)   p
z q  hq ( , v)   q
44
Modelo Distribuído
z kp  h pk ( k , v k )   kp ,k  1,...,r
zqk  hqk ( k , v k )   qk ,k  1,...,r
r: número de áreas
xk: vetor de estado da área k
zk: vetor de medidas da área k
45
Restrições de Acoplamento
Area 1
Area 2
Restrições de acoplamento:
Area 3
A1
A2
 1 
 2
A3    0
 3 
 
Linha não-nula de Ai corresponde às restrições de
acoplamento da área i
46
Formulação do Problema
M
minimize1 / 2{[ z kp  h pk (.)]T [ R pk ]1[ z kp  h pk (.)]
k 1
 [ zqk  hqk (.)]T [ Rqk ]1[ zqk  hq (.)]}
M
sujeitoa
k k
A
 p  0
k 1
M
 ApkV k
k 1
47
0
Algoritmo Básico (Modelo Ativo)
Estimativa sLocais
~k
 (i  1)   k (i )  [C pk ]1[ H pk ][R pk ]1[ z kp  h pk (...)],k  1,...,M
Coordenaçã o
 p (i  1) 
N pk
N p1
M

k 1
~
k k
Ap  (i  1)
M
  Apk [C pk ]1[ Apk ]T
k 1
 Aplicação dasrestrições deacoplament o
~
k
 (i  1)   (i  1)  [C pk ]1[ Apk ]1 p (i  1),k  1,...,M
k
48
Algoritmo Básico (Modelo Ativo)
Deprezando elementos fora da diagonal de
~
k
~
k
 k (i  1)   (i  1)    (i  1)
~
k
~
~
g rrk
k
k
  (i  1)   k
[

(
i

1
)


(i  1)]
r
r
j
g rr  g rr
g krr eg rrj sãoelem entosdiagonaisdainversadas
m atrizesganhodasáreasie j
49
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




50
Avaliação da Segurança Dinâmica
em Tempo Real
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
52
Configuração do Software
SCADA
Estimação
de Estado
Previsão de Carga
Fluxo de Potência Continuado
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
Seleção de Contingências
Simulação no Tempo
Simulação no Tempo
Análise dos Resultados
Medidas Corretivas
53
•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
Configuração do Hardware
W3
W2
W1
Wn
Anel de Fibra
Ótica
Ambiente
DEC Alpha
Sistema Computacional
Principal do EMS de Furnas
Servidor
Network
Hub
Servidor
Cliente 1
Cliente 2
Ambiente de PCs
54
Cliente 5
Ambiente Computacional
 Hardware
–
–
–
–
Três (seis) PCs Pentium 200 MHz
Fast Ethernet Network (100 Mbs)
Arquiitetura mestre-escravo
Conexão física: estrela
 Software
–
–
–
–
55
MS Windows NT Server and NT Workstation v. 4.0
Message Passing Interface (MPI)
Compilador Fortran PowerStation
Modelo de programação: mestre-escravo
Configuração da Rede para Teste
Servidor
Pentium 200 MHz
128 Mb RAM
2.1 Gb HD
Escravo 1
Pentium 200 MHz
64 Mb RAM
2.1 Gb HD
56
Hub
3COM Office Connect
8/TP100
Fast Ethernet
Escravo 2
Pentium 200 MHz
64 Mb RAM
2.1 Gb HD
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)
57
Resultados
Experiência I - Rede com 3 PCs
Tarefa
Seleção de Contingências
Simulação Dinâmica
Tempo (min)
Seqüencial
Paralelo
3,70
1,98
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.
58
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
59
OTIMIZAÇÃO
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
61
Fluxo de Potência Ótimo com
Restrições de Segurança
(FPORS)
Formulação do FPO
min f (u , x)
sujeito a
g i (u , x)  0
hi (u , x)  0
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
63
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
64
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
65
Formulação Preventiva do FPORS
min f (u0 , x0 )
sujeito a
g i (u0 , xi )  0, i  0,1,2,..., n
hi (u0 , xi )  0, i  0,1,2,..., n
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
66
Formulação Preventiva do FPORS
min f (u0 , x0 )
sujeito a
g i (u0 , xi )  0, i  0,1,2,..., n
hi (u0 , xi )  0, i  0,1,2,..., n
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
67
Formulação Corretiva do FPORS
min f (u0 , x0 )
sujeito a
g i (ui , xi )  0, i  0,1,2,..., n
Restrições de
Acoplamento
hi (ui , xi )  0, i  0,1,2,..., n
 i (ui  u0 )  i , i  0,1,2,..., n
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.
68
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
69
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
Variável Chave
Subproblema 1
70
Problema Mestre
Subproblema 2
Corte de Benders
...
Subproblema n
Problema Mestre
min f (u0 , x0 )
sujeito a
g i (u0 , x0 )  0
Cortes de Benders
hi (u0 , x0 )  0,
 i*  Ti (u0  u0* )  0, i  1,2,..., n
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
71
Subproblemas
min  i  d s
sujeito a
g i (ui , xi )  0
hi (ui , xi )  0
u0  ui  s  i
s0
d : constante positiva
u0* : variável chave (valor
atual das variáveis de
controle do caso base)
 : norma Euclidiana
72
 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).
Algoritmo
1. 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.
73
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
74
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
75
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.
76
Planejamento da Expansão de
Sistemas de Transmissão
Introdução aos Algoritmos Genéticos
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.)
78
Formulação matemática (modelo DC)
 ckl xkl
min z 
klC
ckl :custo do ramo kl
sujeito a
 f kl0   f kl1  g k  d k , k  N
lCk
lEk
f kl0   kl0 ( k   l )  0, kl  E
Nãolinear
f kl1

xkl  1kl ( k
  l )  0, kl  C
f kl0  f kl0 , kl  E
f kl1  f kl1 xkl , kl  C
0  gk  gk , k  N
Variável
binária
79
xkl  0,1, k  C
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
Solução candidata
ˆ
rk
 Para uma candidata a solução min z  k
N
^x, obtida por algum
sujeito a
procedimento (heurístico?),
o problema reduz-se a um
 f kl0   f kl1  g k  rk  d k , k  N
lCk
lEk
problema de programação
linear
f kl0   kl0 ( k   l )  0, kl  E
f kl1  xˆkl  1kl ( k   l )  0, kl  C
^rk: carga não-suprida nó k
f kl0  f kl0 , kl  E
^z : total de carga não suprida
para a solução ^x; pode ser
f kl1  f kl1 xˆkl , kl  C
utilizado como uma medida da
inviabilidade da solução
80
0  gk  gk , k  N
0  rk  d k , k  N
Métodos de Solução
 Métodos de otimização combinatória: eg
Branch&Bound: difícil
 Procedimentos heurísticos
 Metaheurísticas
–
–
–
–
–
–
81
Algoritmos Evolucionários (Genéticos)
Busca Tabu
Simulated Annealing
GRASP
Particle Sworm Optimization (PSO)
Etc.
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
]
]
82
Seleção,
cruzamento e
mutação
Exemplo de Codificação do Problema
Avaliação
População
Função Adequabilidade
2
3
1
1
5
4
2
3
4
5
1 0 0 1 0
z1
1 0 1 1 0
z2
0 0 0 0 1
z3
0 0 0 1 0
z4
1 0 0 1 0
z5
1 1 0 1 1
z6
Cruzamento
1 0 1 1 0
0 0 0 0 1
83
1 0 0 0 1
0 0 1 1 0
Mutação
Alteração aleatória de 1 ou
mais genes
Seleciona
melhores
indivíduos
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
]
]
84
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
85
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 subpopulaçõ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
86
P1
P2
P1
P2
P3
P4
P3
P4
Planejamento da Expansão de
Sistemas de Distribuição
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
88
Exemplo Ilustrativo
SubEstação
Ponto
de Carga
Rede
Existente
89
Previsão de
Expansão
Exemplos de Solução
Restrição: rede radial
90
Formulação
 Minimizar
– Custos de instalação de novos ramos
– Perdas de energia
 Restrições
– Conectividade
– Radialidade
– Queda de tensão
91
Função Adequabilidade
Decodificação
Conexa e
Radial?
Reparo
N
S
Resolve Fluxo
de Potência
Calcula
Aptidão
92
Fluxo de Potência
calcula tensões
nodais e perdas
Aptidão = 0
Aptidão
1/ Custo +  (1/Perdas)
+   (1/Desvio_Tensão)
Formulação Híbrida:
AG + 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
Sistemas Hidrotérmicos
Introdução
Objetivo
 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 Esperado
– Combustíveis das usinas termelétricas
– Penalidades por eventuais não atendimentos à demanda de
energia - Déficit
95
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 multiperí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
96
Decisões Operativas
Afluências
normais
Usar Água
Decisão?
Decisão 1
Não Usar
Água
Cenário
Alternativo 1
secas
secas
Déficit de Energia
(corte de carga)
OK
Cenário
Alternativo 2
Afluências
normais
97
OK
Vertimento
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
98
PLANEJAM ENTO DA OPERAÇÃO
ENERGÉTICA
LONGO PRAZO
Horizonte : 5 anos
Discreti zação : mensal
MÉDIO PRAZO
Horizonte : 1 ano
Discreti zação : semanal
CURTO PRAZO
Horizonte : Semana
Discreti zação :1/2 hora (primei ro dia)
di ária (demai s dias)
Cadeia de Planejamento
Longo Prazo (5 anos)
Geração hidro total
Geração térmica total
Intercâmbio entre
os subsistemas
Despacho
(1 hora)
Tempo Real
Despacho instantâneo
Restrições de segurança
Cada
hora
Pré-Despacho
(1 dia)
Determinação do perfil
de geração que respeita
as restrições elétricas
e energéticas
99
Cada ano ou
menos
Médio Prazo
(1 ano)
Desagregação do total
de geração hidráulica em
metas de geração para as
unidades hidráulicas
Curto Prazo (1 semana)
Desagregação das
metas mensais em
metas horárias para
as usinas hidráulicas
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
100
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
101
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
102
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
103
Exemplo Genérico
104
Funções de Custo Imediato e de
Custo Futuro
FCI
FCF
FCI: 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
Volume Final
105
Problema de um Estágio
Supondo conhecida a FCF: t+1 (v t+1 )
FCI
Min z = c (u t) + t+1 (v t+1 )
sujeito a
v t+1
vt
v t+1 = v t - u t - s t - a t
v t+1  v max
ut
u t  u max
Estágio
106
t
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
107
2
T-1
T
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.
Cenário 1
Cenário 2
Cenário k
T
108
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
FCF
para o
estágio
T-1
T
109
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
110
2
T-1
T
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
111