A maior rede de estudos do Brasil

Grátis
41 pág.
Modulo 4 - Curso de Otimizacao Linear

Pré-visualização | Página 1 de 4

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 inferior

Crie agora seu perfil grátis para visualizar sem restrições.