Programação Dinâmica Estocástica. Solução Backward: Suponha 3 Estágios Programação Dinâmica Estocástica 12 3 Estágios: m=1,2,3 Estado: x m Decisão: D

ProgramaProgramaçãção Dino Dinââmica Estocmica Estocáásticastica

Solução Backward: Suponha 3 Estágios

Programação Dinâmica Estocástica

1 2 3

Estágios: m=1,2,3Estado: xm

Decisão: Dm

Variável Aleatória: km

Custo Elementar: ),,( 1 mmmm kDxc


tesindependenamenteestatístic

adesprobabiliddeõesDistribuiç

kpk

kpk

kpk

xTkDxCTotalCusto

xTTerminalCusto

kDxgxEstadodoTransiçãodeEquação

mmmmm

mmmmm

)(

)(

)(

)(),,( :

)( :

),,( :

333

222

111

33

3

11

33

1

A qualidade de uma política 3210 ,,, DDDx é medida pelo seu

Custo Total

)(),,(

),,(),,(),,,,,,(

333323

2212110132132100

xTkDxC

kDxCkDxCkkkDDDxQ


Dado que o custo é aleatório há necessidade de trabalhar com médias.

),,(),(

),,( ),,(

),,().().(.)(),(

0000

321321

0033221100

1 2 3

kDxQDxQ

kkkkDDDDcom

kDxQkpkpkpDxQ

k

k k k

A qualidade de uma política é avaliada pela Esperança Matemática do seu custo.


Equação Recursiva

Por analogía:

)(),,(),,().().().(

),,().().().(),(

:

,),,,,(),,(

)(),,( ),,(),,,,(

3333232212332211

110133221100

323211,

3211

3333232212323211

1 2 3

1 2 3

32

xTkDxCkDxCkpkpkp

kDxCkpkpkpDxQ

quetemos

kkDDxQDDxQe

xTkDxCkDxCkkDDxQ

k k k

k k k

kk


Continuando:

),,(),,()(),(

:

),,,,(),,,,(.)().(

1)( 1)(

321111011100

3232113232113322

3322

1

2 3

32

DDxQkDxCkpDxQ

temos

kkDDxQkkDDxQkpkp

ekpekp

como

k

k k

kk

1 2 3

)().().,,().(),( 332211011100k k k

kpkpkDxCkpDxQ

1 2 3

),,,,(.)().().( 323211332211k k k

kkDDxQkpkpkp


Passando à Otimização, define-se:

),,,()( 32100,,

00321

DDDxQMinxFDDD

Por analogia: ),,()( 3211,

1132

DDxQMinxFDD

É claro que:

),,( ),,()()(

),,(),,()()(

3211,

11011100

3211110111,,

00

321

1

1321

DDxQMinkDxCkpMinxF

DDxQkDxCkpMinxF

DDk

D

kDDD

Programação Dinâmica EstocásticaSegue-se:

),,(

)(),,()()(

11011

1111011100

11

kDxgxcom

xFkDxCkpMinxFk

D

De forma idêntica, não há dificuldade para estabelecer que:

),,(

)(),,(),,(

),,(.)()(

1

11

111

mmmmm

mmmmmmmmmm

mmmmk

mmD

mm

kDxgxe

xFkDxCkDxH

com

kDxHkpMinxFm

m


Exercício: Considere o seguinte sistema hidrotérmico

ny

nx

nung

nd

211

1

)( ; 40

30 ; 50

)5,1,3,6,4()4,3,2,1,0(

ggcu

gx

nd

n

n

n

Existe uma afluência aleatória de energia ao reservatório yn com aseguinte distribuição de probabilidade:

00,250,25004

00,250,500,253

0,50,50,250,250,52

0,25000,50,251

0,25000,2500

43210 n

Y


Se o sistema não atender a demanda, incorrerá num custo de deficit:

atendidanãodemandagonde

gggc

10)(

2

22222

Existe um custo associado à energia armazenada no reservatório no final do horizonte x5 dada por:

4816284464F5(x5)

543210x5

Fazer o planejamento otimizado da operação, considerandox0=3 U.E.


3

)(,min0

30

40

50

4,...,1,0

..

)()()(

0

12

1

21

1

4

05521

x

ugddg

g

u

x

ndugg

yuxx

as

xFgcgcMin

nnn

n

n

nn

nnnn

n

nn

n

nn

nn

Programação Dinâmica EstocásticaA geração térmica e déficit podem ser representados por uma únicavariável ‘g’.

3 g

g2

g1

9

C(g)

)2)(6(124

)3(10)3(9)( 3

9)( 3

)( 30

2

2

21

gggg

gggcgPara

gcgPara

ggcgggPara

3 / )2)(6(

3 / )(

2

gpgg

gpggc

g 0 1 2 3 4 5 6

C(g) 0 1 4 9 20 33 48


A formulação fica:

4,...,1,0

3

40

50

..

)()(

0

1

4

055

n

x

u

x

dug

yuxx

as

xFgcMin

n

n

nnn

nnnn

nn

4,...,1,0

3

40

50

..

)()(

0

1

4

055

n

x

u

x

yuxx

as

xFudcMin

n

n

nnnn

nnn


Como a variável yn é aleatória, busca-se minimizar o custo esperado:

4,...,1,0

3

40

50

..

)()(

0

1

4

055

n

x

u

x

yuxx

as

xFudcMin

n

n

nnnn

nnn

yu nn


)()(min)( 5 4 5544444

44

xFudcxFdnyu

X4 F4 (X4) U4*

0

1

2

3

4

5

X5 F5(X5)

0 64

1 44

2 28

3 16

4 8

5 4


)()(min)( 1 3 4433333

33

xFudcxFdnyu

X3 F3 (X3) U3*

0

1

2

3

4

5

X4 F4(X4)

0

1

2

3

4

5


)()(min)( 3 2 3322222

22

xFudcxFdnyu

X2 F2 (X2) U2*

0

1

2

3

4

5

X3 F3(X3)

0

1

2

3

4

5

)()()( 6 1 2211111

11

xFudcminxFdnyu


X1 F1 (X1) U1*

0

1

2

3

4

5

X2 F2(X2)

0

1

2

3

4

5

)()(min)( 4 0 1100000

00

xFudcxFdnyu


X0 F0 (X0) U0*

0

1

2

3

4

5

X1 F1(X1)

0

1

2

3

4

5


Simulação para: )2,4,4,2,3( 30 yx

A política ótima é:

)3,5,4,3,5,3(

)0,2,0,0,0(

)1,0,0,2,3(

)4,1,3,4,1(

x

v

g

u

1

0 32

x

5

4

1

2

3

4 5 n

1

4

2

3

n0 32

5

1 4 5

u,g,y,v

ProgramaProgramaçãção Dino Dinââmica mica EstocEstocáástica Markovianastica Markoviana

Programação Dinâmica Estocástica Markoviana

A aleatoriedade depende também do passado recente

)/( 1iii kkp

A caracterização do estado vai exigir informação sobre este passado

1 2 3

Estágios: m=1,2,3Estado: xm , km

Decisão: Dm

Variável Aleatória: km

Custo Elementar: ),,( 1 mmmm kDxc


A qualidade de uma política 32100 ,,),,( DDDkx é uma variável alea-

tória avaliada pela expectativa de custo total

),,( ),,(

)(),,(),,,(

321321

33

3

11000

kkkkDDDD

xTkDxckDkxQm

mmmm

dascondiciona adesprobabilid de ãoDistribuiç

)2

/3

(33

)1

/2

(22

)0

/1

(11

)3

(3

1),,

1(:TotalCusto

)3

(:terminalCusto

),,1

(:estadodetransiçãodeEquação

kkpk

kkpk

kkpk

xTm

mkmDm

xmc

xTmkmD

mxmgmx


1 2 3

231201

),,()/()/()/(),,(

),,(),,(

00233122011000

00///

000

k k k

kkkkkk

DkxQkkpkkpkkpDkxQ

DkxQDkxQ

Equação Recursiva (Backward) : Por analogia

1

2312

),,,(),,()/(),,(

),,,,,(),,,(

)(),,(),,,,,(

321111101011010

3232111//

32111

33

3

213232111

k

kkkk

mmmmm

DDkxQkDxckkpDkxQ

queseDeduz

kkDDkxQDDkxQ

e

xTkDxckkDDkxQ

Programação Dinâmica Estocástica MarkovianaFase de Otimização

),,(

),(),,()/(),(

quededuzir sepode atropelos, sem Também,

),,,(),(

analogiaPor

),,,,(),(

11011

1111101011000

32111,

111

321000,,

000

11

32

321

kDxgxcom

kxFkDxckkpMinkxF

DDkxQMinkxF

DDDkxQMinkxF

kD

DD

DDD

É claro que: ),( 00*1

*1 kxDD


De maneira geral temos que:

),,(

e

),(),,(),,(

),,()/(),(

1

11

11111

mmmmm

mmmmmmmmmmm

mmmmk

mmmD

mmm

kDxgx

kxFkDxckDxH

com

kDxHkkpMinkxFm

m

Observação:

Uma sofisticação é termos: ),()( 333 kxTxT

Maldição da Dimensionalidade

Comecemos promovendo uma comparação entre esforços computacionaisrequeridos em Programação Dinâmica e na Enumeração Completa.Para fixarmos idéia, vamos supor o problema:

decisãoou controle de variáveis -

estado de variáveis -

),(

..

)(),(

1

1

0

devetoru

devetorx

Uu

Xx

uxgx

as

xTuxJFMinimizar

k

k

kk

kk

kkkk

N

N

kkkk

Resolver Backward

N – n° de estágiosNe - n° de estados em cada estágioNc - n° de controles em cada estado

Equação Recursiva

)()(

.1,.....,1,0

)( )(),()( 11

nnn

kkkkku

kk

xTxIe

Nkpara

xIuxJMinxIk

(mostra que para o estado fixado, temos necessidade de umaadição por controle


Por estado Nc adições

Por estágio Nc*Ne adições

No total N*Nc*Ne adições

Em cada estado realizamos (Nc-1) comparaçõesNo total N*Ne*(Nc-1) comparações

Enumeração Completa

Neestados

°°

°

°

°

°°

°

°

°

°°

°

°

°

°°

°

°

°

°°

°

°

°

Nccontroles

estágio0 1 2 N-1 N


A partir de cada x0 teremos: Nc*Nc*.........*Nc*Nc trajetoriasComo temos Ne valores diferentes para x0, resultam:

Ne*NcN trajetórias distintas

O custo de cada trajetória é calculado fazendo a soma de N+1 fatoresJ0+ J1+..........+ JN-1+T

N*Ne*NcN adições

Para obter a solução ótima, devemos comparar os custos das trajetórias duas a duas:

(Ne*NcN-1) comparações


(Programação Dinâmica) x (Enumeração completa)

Vamos suporN=12Nc=10Ne=100Tsoma=Tcomparação=10-9s

15 dias10*e1412*e14E.C.

23 us1080012000P.D.

TempoComparaçõesAdições


Número de variáveis de estado

Número de

variáveis

de controle

Ne Nc Adições Comparações Tempo

1 1 100 25 30000 28800 34 us

2 2 104 625 75 106 75 106 150 ms

3 3 106 15.625 1875 104 1875 108 6 min

4 4 108 390.625 4,7 1014 4,7 1014 260 H

Esta é a Maldição da Dimensionalidade

Para N=12 façamos um estudo para um número crescentede variáveis de estado e de variáveis de controle.


Exercício: Considere o mesmo problema hidrotérmico do exercício anterior e resolva para uma afluência Yn aleatória com distribuição de probabilidade markoviana, conforme a seguinte tabela.

-Considere Yn-1=1-Fazer o planejamento otimizado de operação. Com as tabelas de decisões efetuarsimulações com hidrologia baixa, média e alta. Considere x0=3


Yn-1\Yn 1 2 3

1 0,50 0,25 0,25

2 0,25 0,50 0,25

3 0,25 0,25 0,50

Documents

Programação Dinâmica Estocástica. Solução Backward: Suponha 3 Estágios Programação Dinâmica Estocástica 12 3 Estágios: m=1,2,3 Estado: x m Decisão: D