Stochastische Modellen in Operations Management (153088)
S1
Ack
S2 X ms
X ms R1
R2 L1
S0
240 ms
R3
L2 10 ms
D0
10 ms
Internet D1
D2
Richard Boucherie Stochastische Operations Research – TW, Citadel 125
http://wwwhome.math.utwente.nl/~boucherierj/onderwijs/153088/153088.html
Stochastische Modellen in Operations Management (153088)
• Doel van het vak / leerdoel – begrip , inzicht en creativiteit in het ontwikkelen van wiskundige modellen ten behoeve van stochastische beslissingsproblemen met behulp van een aantal fundamentele basistechnieken – elk van de behandelde modelleringstechnieken in voldoende mate beheersen, d.w.z. – een model kunnen opstellen, dit model kunnen oplossen, en deze oplossing kunnen interpreteren • Tentamenstof – Winston Hoofdstuk 17-20 Uitreikstukken via website – transparanten, uitwerkingen oefenopgaven, syllabus OR2
Overzicht SMOM • • • • •
Hoor- en werkcolleges (14 HC, 4 WC, 1 vragenuur+oefentent.) Markov ketens (W 17, 2 HC, 1 WC) Stochastische Dynamisch Programmeren (W 19, 3 HC, 1 WC) Markov beslissingstheorie (W 19, 3 HC, 1 WC) Wachttijdtheorie (W 20 + dictaat OR2, 6 HC, 2 WC)
• Tentamen – schriftelijk (4 opgaven) • Literatuur – Winston Hoofdstuk 17-22 – Uitreikstukken op website – Transparanten
Vandaag: • Introductie • Stochastisch process • Markov keten
Stochastisch Proces • Observeer karakteristiek van een systeem op discrete tijdstippen. • Xt is waarde systeem karakteristiek op tijd t. Vaak is Xt niet met zekerheid bekend voor tijd t en kan gezien worden als stochastische variabele. • Een discrete-tijd stochastisch proces is een beschrijving van de relatie tusen de stochastische variabelen X0, X1, X2 ….
• Een continue–tijd stochastisch proces is een stochastisch process waarin de toestand van het systeem op ieder moment kan worden geobserveerd, niet alleen op discrete tijdstippen. • Voorbeeld: aantal klanten in supermarkt t tijdseenheden na winkelopening = continue tijd stochastisch proces. • Voorbeeld: openingskoers AEX = discrete-tijd stochastisch proces koersverloop gedurende dag = continue-tijd stochastisch proces • Verwachting koers aan het eind van het jaar? • Moet ik nu instappen? • Optieprijs?
Stochastisch process voor beurskoersen • Stochastisch process voor koers beleggingsrekening – Observeer openingskoers discrete tijd proces (Xt, t=0,1,2,…) – Evolutie van stochastische variabele – Koers over 100 dagen? P(Xt+1 = it+1|Xt = it, Xt-1=it-1,…,X1=i1, X0=i0) Best lastig probleem
Vandaag: • Introductie • Stochastisch process • Markov keten
Markov Ketens • Speciaal type discrete-tijd stochastisch proces. • Definitie: Een discrete-tijd stochastisch proces met toestandsruimte S is een Markov keten wanneer het, voor t = 0,1,2… en alle toestanden i0, i1, …,it, it+1∈S={0,1,…,s} voldoet aan de Markov eigenschap: P(Xt+1 = it+1|Xt = it, Xt-1=it-1,…,X1=i1, X0=i0) = P(Xt+1=it+1|Xt = it) • De kansverdeling van de toestand op tijdstip t+1 hangt uitsluitend af van de toestand op tijdstip t (it) en niet van de toestanden die de keten eerder heeft bezocht voorafgaande aan bezoek aan it op tijdstip t.
• We zullen verder aannemen dat P(Xt+1 = j|Xt = i) onafhankelijk is van t voor alle toestanden i en j. We noemen zo’n Markov keten homogeen. • P(Xt+1 = j|Xt = i) = pij pij is de kans dat systeem systeem zich in toestand j bevindt op tijdstip t+1 gegeven dat het zich in toestand i bevindt op tijdstip t. • Wanneer systeem zich in een periode beweegt van toestand i naar toestand j zeggen we dat een overgang of transitie van i naar j heeft plaats gevonden. • De pij’s heten overgangskansen voor de Markov keten.
Markov keten voor beurskoersen • Markov keten voor koersen beleggingsrekening – Observeer openingskoers : discrete tijd proces (Xt,t=0,1,2,…) – Evolutie van stochastische variabele – Markov eigenschap (Aanname!!) P(Xt+1 = it+1|Xt = it, Xt-1=it-1,…,X1=i1, X0=i0) =P(Xt+1 = it+1|Xt = i)= pij – Stel pi,i+1=p, pi,i-1=1-p – Dronkemanswandeling Xt is aantal keren kop-munt na t worpen met (on)zuivere munt – http://staff.feweb.vu.nl/aridder/applets/SimRW/default.htm
• • • •
Verwachting koers over 100 dagen? Dit is best te doen!! Moet ik nu instappen? Optieprijs?
• Begin verdeling: qi is de kans dat keten in toestand i op tijdstip 0: P(X0=i) = qi. • Vector q= [q1, q2,…qs] de initiële of begin verdeling. • Overgangskansen matrix P
• Voor iedere i ∈ S
j =s
∑p j =1
ij
=1
⎡ p11 ⎢p P = ⎢ 21 ⎢ M ⎢ ⎣ p s1
p12
K
p 22
K
M ps 2
K
p1s ⎤ p 2 s ⎥⎥ M ⎥ ⎥ p ss ⎦
• Voor alle i,j ∈ S pij ≥ 0. • Dus: alle elementen van de overgangskansen matrix niet negatief, en rijsommen 1 • Karakterisatie overgangskansen matrix.
n-staps overgangskansen • Belangrijke vraag voor Markov ketens: Als Markov keten in toestand i is op tijdstip m, wat is dan de kans dat Markov keten n tijdstippen later in toestand j is? • Deze kans hangt niet af van m, P(Xm+n =j|Xm = i) = P(Xn =j|X0 = i) = Pij(n) Pij(n) is de n-staps overgangskans voor een transitie van toestand i naar toestand j. • Moeilijk te bepalen? • Pij(n) = ij element van Pn
• Bewijs s
Pij (2) = ∑ pik p kj k =1
• Chapman Kolmogorov vergelijkingen s
Pij ( m + n ) = ∑ Pik ( n ) Pkj ( m ) k =1
• Pas nu toe voor m=1, n=0,1,2,…
Markov keten voor beurskoersen • Markov keten voor koersen beleggingsrekening – pi,i+1=p, pi,i-1=1-p – Dronkemanswandeling – http://www.math.uah.edu/stat/ – Bepaal de n staps overgangskansen • Verwachting koersstijging in 100 dagen? • Dit is best te doen!! • Andere voorbeelden? • Algemene uitspraken? • Volgende keer
Samenvatting • Markov keten is een stochastisch proces dat voldoet aan de de Markov eigenschap: P(Xt+1 = it+1|Xt = it, Xt-1=it-1,…,X1=i1, X0=i0) =P(Xt+1=it+1|Xt = it) • Homogeen P(Xt+1 = j|Xt = i) = pij pij overgangskansen voor de Markov keten • Pij(n)= P(Xm+n =j|Xm = i) = P(Xn =j|X0 = i) is de n-staps overgangskans voor een transitie van i naar j. • Pij(n) = ij element van Pn
Food for thought: geheugen in Markov keten? • Weerman: Kans regen hangt af van weer van vandaag (regen of droog) Toestand 1 : regen; toestand 2 : droog p11=P(morgen regen|vandaag regen)= p21=P(morgen regen|vandaag droog)= Xn= toestand weer op dag n Markov keten?
⎡ p11 P=⎢ ⎣ p21
p12 ⎤ ⎡α 1 − α ⎤ =⎢ ⎥ ⎥ p22 ⎦ ⎣ β 1 − β ⎦
Food for thought: geheugen in Markov keten? • Betere weerman ? Kans regen hangt af van weer vandaag en gisteren P(morgen regen|vandaag en gister regen)= 0.7 P(morgen regen|vandaag regen, gister droog)= 0.5 P(morgen regen|vandaag droog, gister regen)= 0.4 P(morgen regen|vandaag en gister droog)= 0.2 Toestand weer op dag n? Markov keten?
RJ9
Food for thought: geheugen in Markov keten? • Betere weerman ? Kans regen hangt af van weer vandaag en gisteren Æ maak Markov keten • Xn= toestand weer op dag n en dag n-1 Toestand 1 : regen vandaag en gisteren Toestand 2 : regen vandaag, droog gisteren Toestand 3: droog vandaag, regen gisteren Toestand 4: droog vandaag en gisteren p11=P(morgen regen|vandaag en gisteren regen)= 0.7 p21=P(morgen regen|vandaag regen, gisteren droog)= 0.5 p32=P(morgen regen|vandaag droog, gisteren regen)= 0.4 p42=P(morgen regen|vandaag en gisteren droog)= 0.2 ⎡ p11 ⎢p P = ⎢ 21 ⎢ ⎢ ⎣ p41
p12 p22 p42
p14 ⎤ ⎡0.7 0 0.3 0 ⎤ p24 ⎥⎥ ⎢⎢0.5 0 0.5 0 ⎥⎥ = ⎥ ⎢ 0 0.4 0 0.6⎥ ⎥ ⎢ ⎥ p44 ⎦ ⎣ 0 0.2 0 0.8⎦
Slide 19 RJ9
let op, bij betere weerman noemen dat voor Xn+1 vandaag en gisteren komt overeen met voor Xn morgen en vandaag!! Geef plaatje betere weerman op bord van Markov keten!! Boucherie; 25-11-2003