Modulo 4 - Curso de Otimizacao Linear

Prévia do material em texto

Pontifícia Universidade Católica do Rio de Janeiro (PUC-Rio)
Departamento de Engenharia Elétrica (DEE)
l i bwww.ele.puc-rio.br
Curso de Otimização Linear
aplicado ao Setor Elétricoaplicado ao Setor Elétrico
Módulo 4Módulo 4
Prof. Alexandre Street
1
Setembro de 2010
AgendaAgenda
Módulo 1 – Modelagem de problemas de PL
Módulo 2 – Propriedades das soluções e o Método SimplexMódulo 2 – Propriedades das soluções e o Método Simplex
Módulo 3 – Teoria de dualidade e análise de sensibilidade
Módulo 4 – Decomposição de Benders e PDDE 
decomposição de problemas de dois estágios: operação ótima de um 
reservatório em dois períodos e o cálculo do valor da água e do custo marginal 
de operação do sistema;p ç
Exercício no Excel: sistema hidro-térmico
o caso multiestágio estocástico: despacho ótimo no setor elétrico brasileiro.
2
Decomposição de Benders: 2 estágiosDecomposição de Benders: 2 estágios
Suponha o seguinte problema de minimização onde o vetor de variáveis x1
representa decisões de um primeiro estágio e x2 do segundo:
Por exemplo, x1 é a geração, turbinamento e volume final armazenado de usinas 
de um sistema hidrotérmico no período 1 e x2 no período 2.∗ = Min, ⋅ + ⋅ (6). : ⋅ ≥ (6.1)⋅ + ⋅ ≥ (6 2)
 
Caso não existisse a restrição (6 2) o problema (6) poderia ser resolvido de
+ ≥ (6.2)⋅ ≥ (6.3)
Caso não existisse a restrição (6.2), o problema (6) poderia ser resolvido de 
maneira separada (em x1 e x2):
1∗ = Min ⋅. : ⋅ ≥ +∗ = 2∗ = Min ⋅. : ⋅ ≥ 
3
Decomposição de Benders: 2 estágiosDecomposição de Benders: 2 estágios
Esse acoplamento em forma de escada na matriz impossibilita a 
decomposição do problema em subproblemas menores (com menos variáveis 
cada um):
00
0
Matriz de restrições:
0
4
Decomposição de Benders: 2 estágiosDecomposição de Benders: 2 estágios
Esse acoplamento em forma de escada na matriz impossibilita a 
decomposição do problema em subproblemas menores (com menos variáveis 
cada um):
Matriz de restrições:
∗( ) = Min∗ = Min +∗ = 2 ( ) = Min ⋅. : ⋅ ≥ − ⋅⋅ ≥1
= Min ⋅. : ⋅ ≥ +=
5
Decomposição de Benders: 2 estágiosDecomposição de Benders: 2 estágios
Se conhecêssemos a função de custo do segundo estágio C2*(x1), então 
poderíamos resolver o problema apenas selecionando a decisão do primeiro 
estágio (x1): ∗ = Min ⋅ + 2∗( ). : ⋅ ≥ 
Mas para cada x1 , C2*(x1) é a solução (valor da f.obj.) de um problema de PL!
. : ≥
Contudo, conhecemos as seguintes propriedades desta função :
é convexa;
é linear por partes
(R$)2∗( 1)é linear por partes.
Ex. da operação ótima
2 1
c2=-15012.250,0p ç
10.000,0 c1=-100
6
115 v1 (hm3)15
Decomposição de Benders: 2 estágiosDecomposição de Benders: 2 estágios
Se conhecêssemos a função de custo do segundo estágio C2*(x1), então 
poderíamos resolver o problema apenas selecionando a decisão do primeiro 
estágio (x1): ∗ = Min ⋅ + 2∗( ). : ⋅ ≥ 
Sabemos então que essa função é o máximo entre funções afins:
. : ≥
Vd é o conjunto de vértices duais
2∗( ) = max ( ) ⋅ + ( ) y é obtido através
w1
2( ) maxi∈Vd ( ) + ( )
y1
y é obtido através
da variável dual da
restrição em que
x1 está no RHS:
w2
w3
y2
x1 está no RHS:= 2∗( ) 
7
x1
w3
Decomposição de Benders: 2 estágiosDecomposição de Benders: 2 estágios
Só podemos calcular C2*(x1) ponto a ponto: para um ponto conhecido x1(k), de 
uma iteração k qualquer do método, podemos obter o valor da função da sua 
derivada (localmente).2∗ ( ) = Min ⋅ ≥ . : ⋅ ≥ − ⋅ ( ) :⋅ ≥∗ ∗( )
∗( ) + é b id é( )
= 2∗ ( ) = 2∗( ) ⋅ ( ) = ⋅ (− ) 
w1
2∗( ) = maxi∈Vd ( ) ⋅ + ( )
y1
y é obtido através
da variável dual da
restrição em que
tá RHS
w2
1 y1
y2
x1 está no RHS:
( ) = 2∗ ( )
8
x1
w3
( )
Decomposição de Benders: 2 estágiosDecomposição de Benders: 2 estágios
Podemos facilitar a obtenção do gradiente de C2*(x1) no ponto x1(k) inserindo 
x1 como uma variável no problema e fixando o seu valor em x1(k):
2∗ ( ) = Min, ⋅: ⋅ + ⋅ ≥ . : ⋅ + ⋅ ≥⋅ ≥= ( ) :
2∗( ) = max ( ) ⋅ + ( ) y é obtidadiretamente como
w1
2( ) maxi∈Vd ( ) + ( )
y1
diretamente como
uma variável dual 
da restrição em
que x1 está fixado
w2
w3
y2
que x1 está fixado
em x1(k):
( ) = 2∗ ( )
9
x1
w3 ( )
Decomposição de Benders: 2 estágiosDecomposição de Benders: 2 estágios
Se conhecêssemos a função de custo do segundo estágio C2*(x1), então 
poderíamos resolver o problema apenas selecionando a decisão do primeiro 
estágio (x1): ∗ = Min ⋅ + 2∗( ): ⋅ ≥ 
E que pode ser modelada por um problema de PL:
. : ≥
2∗( ) = Mint. : ≥ ( ) ⋅ + ( ) ∀ ∈
w1 t
( ) ( )
w2
w3
10
x1
w3
x1*
Decomposição de Benders: 2 estágiosDecomposição de Benders: 2 estágios
Como Vd, em geral, é muito grande, podemos criar um Limite Inferior Cinf para o 
valor ótimo nosso problema original C*, utilizando um subconjunto U ⊆ Vd de 
planos que caracterizam C *(x ):planos que caracterizam C2 (x1): ∗ = Min ⋅ + 2∗( ): ⋅ ≥ = Min,t ⋅ +: ⋅ ≥ ≤
Como a função de segundo estágio não é mais a mesma, o ótimo deve mudar. Na 
i ã k d é d d ó i k l j U l ã ó i
. : ≥. : ≥≥ ( ) ⋅ + ( ) ∀ ∈
iteração k do método, onde só existam k planos no conjunto U, a solução ótima
vale x1(k). 2 ( ) Aproximação inferior
P C* ( ) tili
w1 t
Para C 2(x1): utiliza um 
subconjunto U de planos 
dentre todos os que 
caracterizam a função original.
w3
ç g
11
x1
w3
x*1x1(k)
Decomposição de Benders: 2 estágiosDecomposição de Benders: 2 estágios
Para criar um Limite Superior Csup para o valor ótimo nosso problema original 
C*, basta utilizar a solução x1(k) encontrada no processo de obtenção do Limite Inferior 
e avaliá-lo na função original do segundo estágio: C*2(x1(k)).
≤ ≤= Min,t ⋅ + ∗ = Min ⋅ + 2∗( )≥ = ⋅ ( ) + 2∗( ( )) . : ⋅ ≥≥ ( ) ⋅ + ( ) ∀ ∈ . : ⋅ ≥
2∗ ( ) = Min ⋅: ⋅ ≥ − ⋅ ( )
w1 t
x1(k)
. : ⋅ ≥ − ⋅ ( )⋅ ≥
w3
12
x1
w3
x1*x1(k)
Decomposição de Benders: 2 estágiosDecomposição de Benders: 2 estágios
O limite inferior é obtido pelo ótimo obtido com a função aproximada por
baixo (quando U={1,2}). A solução obtida neste processo é subótima para o 
problema original (que contem todos os planos) Assim ao avaliarmos o custoproblema original (que contem todos os planos). Assim, ao avaliarmos o custo
total nessa solução, obteremos um limite superior (Csup) para o valor ótimo C*
≤ ≤= Min ⋅ + ∗ = Min ⋅ + 2∗( ) = ⋅ ( ) + 2∗( ( ))Min,t +. : ⋅ ≥≥ ( ) ⋅ + ( ) ∀ ∈
2 ( ). : ⋅ ≥ ( ) + 2 ( ( )) 
As funções desta figura
w1
ç g
representam a função custo
total (dos dois períodos) em
função de x1
i=1i=2
i=3Csup
1
+ 2∗( ) 
C*
U={1,2}
i=3
Cinf
Csup + 2 ( )
13
x1x1*x1(k)
{ , }
Decomposição de Benders: 2 estágiosDecomposição de Benders: 2 estágios
Caso o GAP de otimalidade, dado por GAP = Csup - Cinf, seja insatisfatório: 
devemos incluir um plano a mais no conjunto U, referente ao ponto encontrado no 
processo de limite inferior. Para isso, usamos as informações das variáveis duais do 
problema do segundo estágio.
A expressão do plano é obtida pelo valor da função no ponto em que a avaliamos, 
C2*(x1(k)), mais um desvio deste ponto para um ponto genérico x1 multiplicado 
pela taxa de variação local da função: ≥ 2∗ ( ) + ( ) ⋅ − ( )
2 ( )
≥ 2 ( ) + ( ) ( )≥ ( ) ⋅ + 
w1
2 ( ) 
yk = - πkTD ou diretamente da 
restrição de fixação do valor de x1
C *( ) T
w
C2*(x1(k)) yk
wk = C2*(x1(k)) – ykT⋅x1(k)
formam um novo plano a ser 
considerado em uma próxima 
14
x1
w3
x1(k) x1*
co s de ado e u a p ó a
iteração k+1.
Benders 2 estágios (Resumo do algoritmo)Benders 2 estágios (Resumo do algoritmo)
Inicialização: Obtenha uma solução inicial para o primeiro estágio (x1(1))
Pode-se resolver o problema do primeiro estágio limitando t a um piso conhecido (zero no 
exemplo do custo mínimo).
Neste caso o conjunto U={1} começa apenas com um plano constante
k=1 (contador de iterações)
Passo 1: Encontrar um Limite Inferior para o custo mínimo
k=k+1
Resolver o problema do primeiro estágio utilizando a aproximação inferior dada pelos planos do 
conjunto U e fazer Cinf ser o valor de sua função objetivo no ótimo encontrado.
Neste passo serão obtidos o limite inferiorCinfk e um ponto subótimo x1(k)
Passo 2: Encontrar um Limite Superior para o custo mínimo
Resolver o problema do segundo estágio para o ponto x1(k) obtido no passo anterior:
• Calcule o custo deste estágio C2*(x1(k)) ;
• Calcule Csupk = cT⋅x1(k)+ C2*(x1(k))k 1(k) 2 ( 1(k))
• Obter a derivada (gradiente) yk = ∂C2*(x1)/∂x1 no ponto x1(k) através da variável dual.
• Calcule wk = C2*(x1(k)) – ykT⋅x1(k)
• Se Csupk – Cinfk > tol., então: Inclua o plano encontrado (yk e wk), U=U∪{k} e volte ao passo 1.
15
k k , p (yk k), { } p
• Caso contrário: PARE! Ótimo encontrado.
AgendaAgenda
Módulo 1 – Modelagem de problemas de PL
Módulo 2 – Propriedades das soluções e o Método SimplexMódulo 2 – Propriedades das soluções e o Método Simplex
Módulo 3 – Teoria de dualidade e análise de sensibilidade
Módulo 4 – Decomposição de Benders e PDDE 
decomposição de problemas de dois estágios: operação ótima de um 
reservatório em dois períodos e o cálculo do valor da água e do custo marginal 
de operação do sistema;p ç
Exercício no Excel: sistema hidro-térmico
o caso multiestágio estocástico: despacho ótimo no setor elétrico brasileiro.
16
Exercício: Sistema HidroExercício: Sistema Hidro--Térmico (Térmico (handshands onon))
Despacho ótimo de duas horas consecutivas (períodos = horas)
Suponha um rendimento de 1 MWh/hm3 para a turbina da hidrelétrica
Potência máxima da hidrelétrica igual a 200 MW
Afluências em cada período de a1 = 20 hm3 e a2 = 5 hm3
Demanda igual a 120 MWh nos dois períodos
Volume inicial v0 = 100 hm3
O potencial hídrico é: 125 MWh
No período 1: (v0 + a1)⋅ρ = 120 MWh 
No período 2: (a2)⋅ρ = 5 MWh 
id i é i d d l d é i d lConsidere o sistema térmico dado pelas duas térmicas do exemplo
anterior custos de 100 e 150 R$/MWh e Potência disponível 100 e 50 
MW respectivamente. 
17
Exercício: Sistema HidroExercício: Sistema Hidro--TérmicoTérmico
Passo 1 (k=1): Despacho ótimo no primeiro período, sem função de custo 
futuro, é dado pelo seguinte problema de PL:
= Min≥ 100 ⋅ 11 + 150 ⋅ 12 + 500 ⋅ 1 + v1,u1,s1,r1≥0. : 11 + 12 + 1 ⋅ 1 + 1 ≥ 1201 + 1 + 1 = 100 + 201 + 1 + 1 +0 ≤ 1 ≤ 500 ; 0 ≤ 1 ≤ 100 ; 0 ≤ 1 ≤ 2001 ⋅ 1 ≤ 2001 2 5
A solução ótima é turbinar toda a água do reservatório atendendo à
0 ≤ 11 ≤ 100 ; 0 ≤ 12 ≤ 50≥ 0
A solução ótima é turbinar toda a água do reservatório, atendendo à 
demanda e deixando o reservatório vazio para o próximo período.
O custo deste período é zero.
18
O limite inferior do custo total obtido nesta iteração (k=1) é Cinf = 0 
Exercício: Sistema HidroExercício: Sistema Hidro--Térmico (Planilha Excel)Térmico (Planilha Excel)
19
Exercício: Sistema HidroExercício: Sistema Hidro--TérmicoTérmico
Passo 2 (k=1): No segundo período, o problema que devemos resolver é: dado 
que temos 0 hm3 no reservatório + 5 das chuvas deste período, devemos 
utilizá-lo por completo e atender o resto da carga com térmicas:
2∗(0) = Min≥ ≥0 100 ⋅ 21 + 150 ⋅ 22 + 500 ⋅ 2 v2,u2,s2,r2≥0v1. : 21 + 22 + 2 + 2 ≥ 1202 + 2 + 2 − 1 = 51 = 00 ≤ 2 ≤ 500 ; 0 ≤ 2 ≤ 100 ; 0 ≤ 2 ≤ 2000 ≤ 21 ≤ 100 ; 0 ≤ 22 ≤ 50
A solução ótima é turbinar 5 hm3 e zerar o reservatório.
O despacho ótimo das térmicas será: g1 = 100 g2 = 15 MWhO despacho ótimo das térmicas será: g1 = 100, g2 = 15 MWh
O custo do segundo período será 12,250.00 R$
A variável dual da restrição de demanda vale y(1) = -150 R$/MWh 
20
( )
O limite superior para o custo total é Csup = C1* + C2*(0) = 12,250.00
Exercício: Sistema HidroExercício: Sistema Hidro--TérmicoTérmico
Chegamos no fim da primeira iteração com um GAP = 12.250,0
Algoritmot = 1 t = 2
Custo: 100 150 0 Custo: 100 150 0
k g1 g2 u1 v1 Custo1 Custo fut k g1 g2 u2 v2 Custo2 k Cinf Csup GAP y w
1 0 0 120 0 -$ -$ 1 100 15 5 0 12,250.00$ 1 -$ 12,250.00$ 12,250.00$ -150 12,250.00$ 
Logo, devemos incluir um plano para aproximar a função de custo futuro
obtido neste ponto e retornar ao Passo 1.p
(R$)2∗( 1)
y(1)=-15012.250,0
21
v1 (hm3)0 81.7
Exercício: Sistema HidroExercício: Sistema Hidro--TérmicoTérmico
Passo 1 (k=2): Despacho ótimo no primeiro período, com a função de custo 
futuro aproximada por um segmento:= Min≥v1,u1,s1,r1≥0 100 ⋅ 11 + 150 ⋅ 12 + 500 ⋅ 1 +1 2 . : 11 + 12 + 1 ⋅ 1 + 1 ≥ 1201 + 1 + 1 = 100 + 200 ≤ 1 ≤ 500 ; 0 ≤ 1 ≤ 100 ; 0 ≤ 1 ≤ 2000 ≤ 1 ≤ 500 ; 0 ≤ 1 ≤ 100 ; 0 ≤ 1 ≤ 2001 ⋅ 1 ≤ 2000 ≤ 11 ≤ 100 ; 0 ≤ 12 ≤ 50
Agora a solução ótima é turbinar 38 3 hm3 e deixar 81 7 hm3 de a água do
≥ 0≥ −150 ⋅ 1 + 12,250.0
Agora, a solução ótima é turbinar 38.3 hm3 e deixar 81.7 hm3 de a água do 
reservatório, atendendo o resto da demanda com a térmica 1 (g1* = 81.67 MWh).
O custo deste período é 8,166.70 R$ e o custo futuro zero.
22
O limite inferior do custo total obtido nesta iteração (k=2) foi Cinf = 8,166.70 R$ 
Exercício: Sistema HidroExercício: Sistema Hidro--TérmicoTérmico
Passo 2 (k=2): No segundo período, o problema que devemos resolver é: dado 
que temos 81,7 hm3 no reservatório + 5 das chuvas deste período, devemos 
utilizá-lo por completo e atender o resto da carga com térmicas:
2∗(81.67) = Min≥ ≥0 100 ⋅ 21 + 150 ⋅ 22 + 500 ⋅ 2 v2,u2,s2,r2≥0v1. : 21 + 22 + 2 + 2 ≥ 1202 + 2 + 2 − 1 = 52 2 2 11 = 81.670 ≤ 2 ≤ 500 ; 0 ≤ 2 ≤ 100 ; 0 ≤ 2 ≤ 2000 ≤ 21 ≤ 100 ; 0 ≤ 22 ≤ 50
A solução ótima é turbinar 86.67 hm3 e zerar o reservatório.
O despacho ótimo das térmicas será: g1 = 33 33 e g2 = 0 MWh
2 2
O despacho ótimo das térmicas será: g1 = 33.33 e g2 = 0 MWh
O custo do segundo período será 3,333.00 R$
A variável dual da restrição de demanda vale y(2) = -100 R$/MWh 
23
( )
O limite superior para o custo total é Csup = C1* + C2*(81.67) = 11,500.00
Exercício: Sistema HidroExercício: Sistema Hidro--TérmicoTérmico
Chegamos no fim da segunda iteração com um GAP = 3,333.33 R$, 29% da 
melhor solução.
Custo: 100 150 0 Custo: 100 150 0
k g1 g2 u1 v1 Custo1 Custo fut k g1 g2 u2 v2 Custo2 k Cinf Csup GAP y w
1 0 0 120 0 -$ -$ 1 100 15 5 0 12,250.00$ 1 -$ 12,250.00$ 12,250.00$ -150 12,250.00$
Algoritmot = 1 t = 2
Logo, devemos incluir um plano para aproximar a função de custo futuro
$ $ ,$ $ ,$ ,$ ,$
2 81.7 0.0 38.333 81.7 8,166.67$ -$ 2 33.3 0.0 86.7 0.0 3,333.33$ 2 8,166.67$ 11,500.00$ 3,333.33$ -100 11,500.00$ 
g , p p p ç
obtido neste ponto e retornar ao Passo 1.
(R$)2∗( 1)
y(1)=-15012.250,0
11.500,0
y(2)=-100
24
v1 (hm3)0 81.7
Exercício: Sistema HidroExercício: Sistema Hidro--TérmicoTérmico
Passo 1 (k=3): Despacho ótimo no primeiro período, com a função de custo 
futuro aproximada por 2 segmentos:= Min≥v1,u1,s1,r1≥0 100 ⋅ 11 + 150 ⋅ 12 + 500 ⋅ 1 +: 1 + 2 + 1 ⋅ 1 + ≥ 120
 
. : 1 + 1 + 1 ⋅ 1 + 1 ≥ 1201 + 1 + 1 = 100 + 200 ≤ 1 ≤ 500 ; 0 ≤ 1 ≤ 100 ; 0 ≤ 1 ≤ 2001 ≤ 2001 ⋅ 1 ≤ 2000 ≤ 11 ≤ 100 ; 0 ≤ 12 ≤ 50≥ 0
Agora a solução ótima é turbinar 20 hm3 e deixar 100 hm3 de a água do
≥ −150 ⋅ 1 + 12,250.0≥ −100 ⋅ 1 + 11,500.0
Agora, a solução ótima é turbinar 20 hm3 e deixar 100 hm3 de a água do 
reservatório, atendendo o resto da demanda com a térmica 1 (g1* = 100 MWh).
O custo deste período é 10,000.00 R$ e o custo futuro 1,500.00
25
O limite inferior do custo total obtido nesta iteração (k=3) foi Cinf = 11,500.00 R$ 
Exercício: Sistema HidroExercício: Sistema Hidro--TérmicoTérmico
Passo 2 (k=2): No segundo período, o problema que devemos resolver é: dado 
que temos 100 hm3 no reservatório + 5 das chuvas deste período, devemos 
utilizá-lo por completo e atender o resto da carga com térmicas:
2∗(100) = Min≥ ≥0 100 ⋅ 21 + 150 ⋅ 22 + 500 ⋅ 2 v2,u2,s2,r2≥0v1. : 21 + 22 + 2 + 2 ≥ 1202 + 2 + 2 − 1 = 52 2 2 11 = 1000 ≤ 2 ≤ 500 ; 0 ≤ 2 ≤ 100 ; 0 ≤ 2 ≤ 2000 ≤ 21 ≤ 100 ; 0 ≤ 22 ≤ 50
A solução ótima é turbinar 105 hm3 e zerar o reservatório.
O despacho ótimo das térmicas será: g1 = 15 e g2 = 0 MWh
2 2
O despacho ótimo das térmicas será: g1 = 15 e g2 = 0 MWh
O custo do segundo período será 1,500.00 R$
A variável dual da restrição de demanda vale y(3) = -100 R$/MWh 
26
( )
O limite superior para o custo total é Csup = C1* + C2*(100) = 11,500.00
Exercício: Sistema HidroExercício:Sistema Hidro--TérmicoTérmico
Chegamos no fim da terceira iteração com um GAP = 0 R$, 0% da melhor 
solução: Pare, solução ótima encontrada! A solução é dada pela operação 
ótima encontrada na iteração 3.
Custo: 100 150 0 Custo: 100 150 0
k g1 g2 u1 v1 Custo1 Custo fut k g1 g2 u2 v2 Custo2 k Cinf Csup GAP y w
Algoritmot = 1 t = 2
k g1 g2 u1 v1 Custo1 Custo fut k g1 g2 u2 v2 Custo2 k Cinf Csup GAP y w
1 0 0 120 0 -$ -$ 1 100 15 5 0 12,250.00$ 1 -$ 12,250.00$ 12,250.00$ -150 12,250.00$ 
2 81.7 0.0 38.3 81.7 8,166.67$ -$ 2 33.3 0.0 86.7 0.0 3,333.33$ 2 8,166.67$ 11,500.00$ 3,333.33$ -100 11,500.00$ 
3 100 0 20 100 10,000.00$ 1,500.00$ 3 15.0 0.0 105.0 0.0 1,500.00$ 3 11,500.00$ 11,500.00$ -$ -100 11,500.00$ 
$12,000.00 
$14,000.00 
Convergência - Benders 2 estágios
$6,000.00 
$8,000.00 
$10,000.00 
R$
$-
$2,000.00 
$4,000.00 
1 2 3
Csup
Cinf
27
1 2 3
Iterações
AgendaAgenda
Módulo 1 – Modelagem de problemas de PL
Módulo 2 – Propriedades das soluções e o Método SimplexMódulo 2 – Propriedades das soluções e o Método Simplex
Módulo 3 – Teoria de dualidade e análise de sensibilidade
Módulo 4 – Decomposição de Benders e PDDE 
decomposição de problemas de dois estágios: operação ótima de um 
reservatório em dois períodos e o cálculo do valor da água e do custo marginal 
de operação do sistema;p ç
Exercício no Excel: sistema hidro-térmico
o caso multiestágio estocástico: despacho ótimo no setor elétrico brasileiro.
28
Dados do despacho centralizado do ONS Dados do despacho centralizado do ONS 
Parâmetros do Modelo:
Informação hidrológica
Custo do déficit
41
38 40
42
44 46
48
51
54 56
59
61
20
30
40
50
60
70
GW average
Cenário de demanda (5 anos)
Custo do déficit
Curva de Aversão ao Risco
Critério de Convergência, etc…
0
10
20
2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011
- Dados técnicos e operativos das 
usinas 
Transmissão:
Topologia da Rede
- Cronograma de expansão das 
unidades geradoras (5 anos)
Limites e disponibilidades
•CMO 
•Despacho das Usinas
Gt πt
29
t
Despacho Físico: Sistema HT Despacho Físico: Sistema HT -- FormulaçãoFormulação
Minimizar E(∑t ∑j gTj,t⋅cj + deft⋅cdef)
s.a:
Atendimento à demanda:
∑iturbi,t⋅ρ + ∑jgTj,t⋅cj + deft = dt ∀t
Balanço Hídrico:
vi,t = vi,t-1 + ai,t-1 + ∑k ∈m(i)(turbk,t-1+vertk,t-1) - turbi,t-1 - verti,t-1 ∀i,t
Limites e capacidades:
vimin ≤ vi,t ≤ vimax ∀i,t
i TGjmin ≤ gTj,t ≤ Gjmax ∀i,t
Limites de transmissão:
…
Dificuldades:
ai,t é um processo estocástico com dependência periódica nos lags passados: PAR(p)
30
,
As restrições de Balanço Hídrico tornam o problema ACOPLADO temporalmente 
Despacho Físico: Sistema HT Despacho Físico: Sistema HT -- AfluênciasAfluências
As afluências são (no Brasil) modeladas através de um modelo Autorregressivo
periódico multivariado
S j [ ] t d d d t g i iódiSeja p = [p1,...,pn] o vetor de ordens de um autorregressivo periódico com n 
períodos sazonais, por exemplo, n = 12
O Vetor de afluências at em cada posto de vazão (usinas) é modelado por:
ε = Φ (L) (a μ ) logN(0 ∑ )εt = Φm(t)(L)⋅(at - μm(t)) ~ logN(0,∑m(t))
m(t) ∈ {1, ..., n} é o período sazonal de t (para séries mensais corresponde ao mês 
da etapa t)
Φm(t)(L) é a matriz de polinômios que relacionam o período t com os pm(t) lagsm(t)( ) p q p pm(t) g
anteriores de cada combinação de posto de afluência
∑m(t) e μm(t) são respectivamente a matriz de covariância dos resíduos e o vetor de 
médias do período sazonal m(t)
NO
NE
∑3 e μ3
SE m(t)1 2 3 12 1 2 3 12
p3 = 2 p2 = 1p1 = 1
31
SU t1 2 3 12 25 26 27 36
m(t)1 2 3 12 1 2 3 12
Despacho Físico: Sistema HT Despacho Físico: Sistema HT -- DecomposiçãoDecomposição
O problema multi-estágio pode ser decomposto em problemas de um 
estágio dependente do estado atual: função de custo futuro
FCFt(vt,at-1,...,at-p) = 1/B ∑b Minimizar ∑j gTj,t⋅cj + deft⋅cdef + FCFt+1(vt+1,at,b,..., at-p+1)
s.a:
Atendimento à demanda:Atendimento à demanda:
∑iturbi,t⋅ρ + ∑j gTj,t⋅cj + deft = dt(ignorando a rede de transmissão por simplicidade)
Balanço Hídrico: (vt e at estão do lado direito - fixados)
vi,t+1 - ∑k ∈m(i)(turbk,t+vertk,t) + turbi,t + verti,t = vi,t + ai,t,b(at-1,...,at-p) ∀i
Limites e capacidades:
vimin ≤ vi,t ≤ vimax ∀i
Gjmin ≤ gTj,t ≤ Gjmax ∀i
Como at pode ser escrito como função dos lags passados, que são as variáveis de estado, 
a FCF representa o valor esperado condicionado a t-1, t-2, ..., t-p
B é o número de cenários condicionais simulados (conhecidos como cenários Backward)
32
B é o número de cenários condicionais simulados (conhecidos como cenários Backward)
Despacho Físico: Sistema HT Despacho Físico: Sistema HT –– Programação Dinâmica Programação Dinâmica 
DualDualuaua
Afluências 
“Backwards”
Simulação inicial
{a }
Volume inicial
Supor FCFT+1 = 0
Backwards
final
{ats} 
100%
CmédioT,s=1
πmédioT,s=1
CmédioT,s
πmédioT,s
vfinal
50%
tTT-11 2
FCFT10%
tTT 11 2
33
Despacho Físico: Sistema HT Despacho Físico: Sistema HT –– Programação Dinâmica Programação Dinâmica 
DualDualuaua
Calculo de FCFT-1:
Volume inicial
Considera FCFT
CmédioT-1,s= Min FCIT-1,s +FCFT(vT)
final
CmédioT-1,s
πmédioT-1,s
vfinal
tTT-11 2
FCFT-1
tTT 11 2
34
Despacho Físico: Sistema HT Despacho Físico: Sistema HT –– Programação Dinâmica Programação Dinâmica 
DualDual
Solução Ótima Hoje: LIMITE INFERIOR (CInf)
C édi Mi FCI FCF ( )
uaua
Calculo de FCF1:
Cmédio Mi FCI FCF ( )Cmédio0= Min FCI0 +FCF1(v1)
Vol. ini Considera FCF1
final
Cmédio1,s= Min FCI1 +FCF2(v2)
Cmédio1,s
πmédio1,s
vfinal
tTT-11 2
FCF1
tTT 11 2
35
Despacho Físico: Sistema HT Despacho Físico: Sistema HT –– Programação Dinâmica Programação Dinâmica 
DualDualuaua
Cálculo do Limite Superior (CSUP)
Simulação Forward do Sistema 
FCF’ d it ã t i
Volume inicial
com as FCF’s da iteração anterior
FCI1 + FCI2 + ... ... + FCITFCI0 + = CSUP
tTT-11 2
FCF1 FCF2 FCFT
tTT 11 2
36
Despacho Físico: Sistema HT Despacho Físico: Sistema HT –– Programação Dinâmica Programação Dinâmica 
DualDual
CSUP
uaua
Custo Total
Convergência
CINF iterações
1
2
3
n
tTT-11 2
FCF1 FCF2 FCFT
37
tTT-11 2
Cenários de Preço e Geração FuturaCenários de Preço e Geração Futura
Para se determinar a operação ótima e o preço spot de hoje (t=0)
É necessário simular a operação ótima do sistema no médio prazo (5 anos)
Assim, as incertezas na geração e preços futuros são caracterizados pelos 
cenários de operação ótima simulados pelo ONS/CCEE : 
ξ = { ξts = [Gts, πts]T , ∀ t = 1, ...,T e s=1,...,S } com Prob({ξts}t) = 1/S, ∀s
Prob({ξts}t) = 1/S
ξ11
ξ12
ξ21
ξ22
ξT1
ξξ12
ξ1S
ξ22
ξ2S
ξT2
ξTS
tTT-11 2
38
Características do PLDCaracterísticas do PLD
Alta volatilidade com longos períodos de preços muito baixos, devido à sobre 
capacidade instalada hidrelétrica (custo imediato baixo), necessária para 
garantir o suprimento em condições adversas intercalados de período degarantir o suprimento em condições adversas, intercalados de período de 
preços explosivos decorrentes de instabilidades conjunturais ou de secas 
inesperadas
Histórico de PLD (Carga Média)
700
800 NE: suprimento 
de gás SU-SE: 
hidrologia
SU-SE: 
hidrologia
Todos os sub. 
Hidrologia + 
termo de 
compromisso 
(oferta de gás)
500
600
700
W
h SE
SU: CIEN + 
hidrologia
hidrologiahidrologia ( g )
200
300
400
R$
/M
W
SU
NE
NO
0
100
-0
1
-0
1
-0
1
-0
2
-0
2
-0
2
-0
2
-0
3
-0
3
-0
3
-0
3
-0
4
-0
4
-0
4
-0
4
-0
5
-0
5
-0
5
-0
5
-0
6
-0
6
-0
6
-0
6
-0
7
-0
7
-0
7
-0
7
39
Ju
n-
Se
p-
D
ec
-
M
a
r-
Ju
n-
Se
p-
D
ec
-
M
a
r-
Ju
n-
Se
p-
D
ec
-
M
a
r-
Ju
n-
Se
p-
D
ec
-
M
a
r-
Ju
n-
Se
p-
D
ec
-
M
a
r-
Ju
n-
Se
p-
D
ec
-
M
a
r-
Ju
n-
Se
p-
D
ec
-
Semanas
Overview dos preços de curto prazoOverview dos preços de curto prazo
Voláteis e com correlação negativa com a geração total (MRE)
Proporcionam o double-side risk na contratação:
Short em contractos: Longo período vendendopor preços baixos
Long em contratos: Períodos curtos comprando por preços altos
90%
100%
700
800
50%
60%
70%
80%
M
ax
im
um
)
400
500
600
ice
 (R
$/
M
W
h)
20%
30%
40%
50%
St
or
ag
e 
(%
 
200
300
400
Sh
or
t-t
er
m
 pr
0%
10%
Ja
n-
00
Ap
r-0
0
Ju
l-0
0
Oc
t-0
0
Ja
n-
01
Ap
r-0
1
Ju
l-0
1
Oc
t-0
1
Ja
n-
02
Ap
r-0
2
Ju
l-0
2
Oc
t-0
2
Ja
n-
03
Ap
r-0
3
Ju
l-0
3
Oc
t-0
3
Ja
n-
04
Ap
r-0
4
Ju
l-0
4
Oc
t-0
4
Ja
n-
05
Ap
r-0
5
Ju
l-0
5
Oc
t-0
5
Ja
n-
06
Ap
r-0
6
Ju
l-0
6
Oc
t-0
6
Ja
n-
07
Ap
r-0
7
Ju
l-0
7
Oc
t-0
7
Ja
n-
08
Ap
r-0
8
Ju
l-0
8
Oc
t-0
8
Ja
n-
09
Ap
r-0
9
-
100
40
Storage (Brazil) Short-term price (SE/CW)
RiscoRisco nana contrataçãocontratação
Hydroelectric Generation vs Spot Prices
SE zone - Simulated data for 2011
y = -2.43E-09x3 + 2.78E-06x2 - 0.00118x + 1.159
R² = 0.982
115%
The
105%
110%
FE
C
)
e Low
er is
100%
on
 (%
 to
ta
l F
s the prod
95%G
en
er
at
i
The Higher is the price
duction
90%
0 100 200 300 400 500 600
SE Spot Prices (R$/MWh)
The Higher is the price
41
SE Spot Prices (R$/MWh)