Stochastische Modellen in Operations Management (153088)

Stochastische Modellen in Operations Management (153088) S1

S2

X ms

X ms

R1 S0

240 ms

Ack L1

R2

10 ms

Internet

R3

L2

D0

10 ms

D1

D2

Richard Boucherie Stochastische Operations Research – TW, Ravelijn H 219 http://wwwhome.math.utwente.nl/~boucherierj/onderwijs/153088/153088.html

1

Stochastische dynamische programmering •  Fasen n –  aantal opeenvolgende momenten waarop beslissingen moeten worden genomen •  Toestandsruimte Sn –  verzameling van mogelijke toestanden i die kunnen optreden in fase n •  Beslissingsruimte Dn (i) –  verzameling van mogelijk acties d die beschikbaar zijn bij toestand i in fase n •  Directe resultaat rn (i,d) –  Verwachte opbrengst gedurende fase n als gevolg van beslissing d in toestand i •  Overgang j  i,d : pn (j|i,d) –  kans op toestand j als gevolg van beslissing d bij toestand i in fase n

2

Stochastische dynamische programmering •  Doelstelling –  maximaliseer de verwachte resultaten over de gehele planningshorizon :  N  max E  ∑ rn (in , dn )  n= 0  •  Optimale waardefunctie –  definieer € fn(i) als het maximale verwachte resultaat vanaf fase n vanuit toestand i ∈ Sn •  Recurrente betrekkingen

  f n (i) = max  rn (i,d) + ∑ pn ( j | i,d) ⋅ f n +1 ( j) d ∈Dn (i)  j ∈Sn+1 

•  deze werken achterwaarts!

3

4

Vandaag: oneindige horizon •  Wat gaat mis? •  Discontering en contante waarde •  Verwachte resultaat •  Oneindige horizon; deterministische optimalisering •  Voorbeeld •  Optimaliteitsvergelijking

Stochastische dynamische programmering •  Doelstelling –  maximaliseer de verwachte resultaten over de gehele planningshorizon :  N  max E  ∑ rn (in , dn )  n= 0  •  Optimale waardefunctie –  definieer fn(i) als het maximale verwachte resultaat € vanaf fase n vanuit toestand i ∈ Sn •  Recurrente betrekkingen  f n (i) = max  rn (i,d) + d ∈Dn (i) 


 ∑ pn ( j | i,d) ⋅ f n +1( j) j ∈S n+1 

5

6


Discontering en contante waarde (1) •  Kapitaal K0 rentegevend belegd •  Rentevoet i % per jaar •  Na jaar rente, bezit •  Rentevoet constant, dan na t jaar bezit •  Samengestelde interest (rente-op-rente) •  Omgekeerd, kapitaal U, uitgekeerd over t jaren kan nu worden uitgekeerd middels betaling van

•  a < 1 : disconteringsfactor, K : contante waarde lagere rente geeft grotere disconteringsfactor

7

Discontering en contante waarde (2)

8

•  Stel een rij bedragen, waarbij betaald in jaar t. Contante waarde van X, CW(X), is

mits de rij convergeert. •  Indien beslissingscriterium is contante waarde, verkies dan boven indien CW(X)>CW(Y) •  Maakt het mogelijk betalingen in de toekomst te vergelijken

Discontering en contante waarde (3) •  Wanneer betalingen constant zijn, zeg M, disconteringsfactor a ∞

∞

∞

CW (X) = ∑ x t a t = ∑ Ma t = M ∑ a t t= 0

t= 0

M = M(1+ a + a + ...) = 1− a 2

€

t= 0

9

∞

∑ t= 0

1 a = 1− a

Intermezzo: geometrische reeks

10

t

T

∑

a t = 1+ a + a 2 + ...+ aT

t= 0 T

a∑ a = a + a + ...+ a + a t

2

T

T +1

t= 0 T

T

(1− a)∑ a = 1− a t

T +1

t= 0

t= 0 T

∞

∑

a t = lim ∑

t= 0

t= 0

T →∞

⇒∑

T +1

1− a a = 1− a t

T +1 1− a 1 t a = lim = T →∞ 1− a 1− a

(a ≠ 1) (a < 1)

Intermezzo: geometrische reeks ∞

∑

t

2

a = 1+ a + a + ...

t= 0 ∞

a∑ a = a + a + a + ... t

2

3

t= 0 ∞

(1− a)∑ a = 1 (a < 1) t

t= 0

€

11

12


Verwachte resultaat •  Doelstelling –  Verwachte resultaten over de gehele planningshorizon :

N −1   1 E  lim ∑ rn (in ,dn )  N →∞ N n= 0 

13

Stochastische dynamische programmering •  Doelstelling –  maximaliseer de verwachte resultaten over de gehele planningshorizon :  ∞  n max E  ∑ rn (in , dn )a   n= 0  •  Optimale waardefunctie –  definieer fn€ (i) als het maximale verwachte resultaat vanaf fase n vanuit toestand i ∈ Sn •  Recurrente betrekkingen

 f n (i) = max  rn (i,d) + d ∈Dn (i) 


 ∑ pn ( j | i,d) ⋅ f n +1( j) j ∈Sn+1 

14

15


16

Oneindige horizon; deterministisch •  Toepassingen –  beslissingsproblemen over een oneindige horizon waarbij de beslismomenten geordend zijn in de tijd •  Probleemstructuur –  analoog aan dynamische programmeringsproblemen, maar nu over een oneindige horizon

Oneindige horizon; deterministisch

17

•  Definities Politiek / Strategie –  Indien voor iedere toestand i∈S op tijdstip t een beslissing δt(i) voorgeschreven is, noemen we de functie δt een beslisregel –  De oneindige rij π=(δ0, δ1,…) noemen we een politiek of strategie –  een stationaire politiek π=(δ, δ,…) is een voorschrift dat op ieder tijdstip aan iedere toestand i∈S dezelfde beslissing δ(i)∈D(i) toekent

Oneindige horizon; deterministisch •  Opbrengst –  Indien in toestand i∈S op tijdstip t een beslissing δt(i) =j∈S wordt genomen geeft dit directe opbrengst r(i,δt(i))=r(i,j). •  Criteria voor vergelijken politieken –  maximale contante waarde (verdisconteerde resultaat) over een oneindige horizon, startend in i∈S :

–  maximale gemiddelde resultaat per tijdseenheid over een oneindige horizon, startend in i∈S :

–  Vπ(.) waarde functie behorende bij politiek π

18

Oneindige horizon; deterministisch

19

20


Voorbeeld: eenvoudig netwerk

•  Systeem met twee toestanden: S={1,2} •  Directe opbrengst r(i,j) bij transitie i naar j als in figuur •  Gezocht politiek die (voor iedere begintoestand) de contante waarde maximaliseert over oneindige horizon

21

Voorbeeld: eenvoudig netwerk •  Willekeurige politiek

•  Startend in 1 pad (1,1,2,2,1,1,…) opbrengsten (4,5,3,2,4,5,…)

niet-stationaire politiek

22

Voorbeeld: eenvoudig netwerk •  Stationaire politieken

•  Politiek 1 beter dan politiek 2 als

23

Voorbeeld: eenvoudig netwerk •  Stationaire politieken

•  Politiek 1 beter dan politiek 2 als

24


∈

€

25

26


Optimaliteitsvergelijkingen •  •  •  • 

Algemeen systeem Toestandsruimte S We beperken ons tot stationaire politieken Actieruimte D(i), i ∈ S

•  Optimaliteitsvergelijkingen

€ •  Hoe vind je de onbekende waardefunctie V die oplossing is van deze functionaalvergelijking? –  Waarde-iteratie of successieve approximatie –  Politiek of strategie iteratie –  Lineaire programmering

27

Waarde-iteratie

28


29

Waarde-iteratie

∈

€

30


31

Next on SMOM… •  •  •  • 

Toestandsruimte S Actieruimte D(i), i ∈ S Strategie / politiek Contante waarde

•  Optimaliteitsvergelijkingen

€

•  Hoe vind je de onbekende waardefunctie V die oplossing is van deze functionaalvergelijking? –  Waarde-iteratie of successieve approximatie –  Politiek of strategie iteratie –  Lineaire programmering •  En voor stochastische systemen?

32

Oneindige horizon; deterministisch •  Contante waarde •  Optimaliteitsvergelijkingen

•  Vervangen de recursie voor eindige horizon

•  Waarde-iteratie

33

Oneindige horizon; stochastisch •  Contante waarde •  Optimaliteitsvergelijkingen

•  Vervangen de recursie voor eindige horizon

•  Waarde-iteratie

34

Stochastische Modellen in Operations Management (153088)

Recommend Documents