Stochastische Modellen in Operations Management (153088)

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, Ravelijn H 219

http://wwwhome.math.utwente.nl/~boucherierj/onderwijs/153088/153088.html

Mededelingen • Rooster hoorcollege: zie website voor zalen • Rooster werkcollege: zie website data in rooster zijn correct (was fout op website) • Op werkcollege: beantwoorden vragen NIET: voormaken van de opgaven • Werkcollege start morgen Docenten: Judith Vink-Timmer, Laurence Groot Bruinderink • Transparanten als pdf op website

Last time on …. SMOM • 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

Markov keten voor beurskoersen • Markov keten voor koersen beleggingsrekening – pi,i+1=p, pi,i-1=1-p – Dronkemanswandeling (random walk) – http://www.math.uah.edu/stat/ – Bepaal de n staps overgangskansen

⎛n⎞ k Pij (n) = ⎜⎜ ⎟⎟ p (1 − p ) n − k , ⎝k ⎠ j − i = k − (n − k ), of k = (n + j − i ) / 2

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?

RJ10

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 6 RJ10

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

Vandaag: • • • • • •

Voorbeeld: Cola voorbeeld uit boek Classificatie toestanden Evenwichtsverdeling Toepassing Markov ketens in beslissingsproblemen Terugkeertijden Samenvatting Markov ketens

Cola voorbeeld: gedrag MK •

•

Stel twee soorten cola (is aanname voor voorbeeld), personen wisselen voorkeur met mate, alle personen statistisch gelijk (willekeurig individu). Een persoon die cola 1 koopt zal volgende keer met kans 90% weer cola 1 kopen. Een persoon die cola 2 koopt zal volgende keer met kans 80% weer cola 2 kopen. 1. Wanneer een persoon nu cola 2 drinker is, wat is de kans dat hij/zij bij tweede aankoop na nu cola 1 koopt? 2. Wanneer een persoon nu cola X drinker is, wat is de kans dat hij/zij bij tweede aankoop na nu cola 1 koopt? 3. Wat is het toekomstig marktaandeel van cola 1?

•

Vragen die van groot belang zijn voor bijvoorbeeld de beurskoers, of voor beslissingen van management voor inzet extra reclamemiddelen (waarom?)

The Cola Example • Modelleer aankoop van een persoon als Markov keten met toestand op ieder moment de soort cola die de persoon als laatste heeft gekocht. • Cola aankoop dan modelleren als Markov keten met twee toestanden – Toestand 1 = persoon heeft als laatste cola 1 gekocht – Toestand 2 = persoon heeft als laatste cola 2 gekocht • Laat Xn het type cola gekocht door persoon bij nde aankoop, dan is X0, X1, … een Markov keten met overgangs matrix: Cola1 Cola 2 cola 1 Ækans 90% weer cola 1 cola 2 Ækans 80% weer cola 2

⎤ ⎡ Cola 1 ⎢ .90 .10 ⎥ P= Cola 2 ⎢ .20 .80 ⎥ ⎥⎦ ⎢⎣

Cola

⎡ Cola 1 Cola 2 ⎤ Cola 1 ⎢ .90 .10 ⎥ P= Cola 2 ⎢ .20 .80 ⎥ ⎢⎣ ⎥⎦

Hiermee kunnen we vragen 1 en 2 beantwoorden.

1. Wanneer een persoon nu cola 2 drinker is, wat is de kans dat hij/zij bij tweede aankoop na nu cola 1 koopt? We zoeken P(X2 = 1|X0 = 2) = P21(2) = element 21 van P2:

⎡.90 P =⎢ ⎣.20 2

.10 ⎤ ⎡.90 .80 ⎥⎦ ⎢⎣.20

.10 ⎤ ⎡.83 =⎢ ⎥ .80 ⎦ ⎣.34

.17 ⎤ .66 ⎥⎦

Dus, P21(2) =.34. De kans dat een cola 2 drinker na twee aankopen cola 1 koopt is .34 – We kunnen dit antwoord ook vinden mbv elementaire kansrekening

Cola 2. Wanneer een persoon nu cola X drinker is, wat is de kans dat hij/zij bij tweede aankoop na nu cola 1 koopt? We weten nu niet welke cola persoon drinkt, en moeten daarom aanname doen over de fractie personen die nu cola 1 drinkt (bijvoorbeeld via marktonderzoek). We vinden zo q=[q1, q2] de beginverdeling De gezochte kans is

i =2

∑ q P (2) i =1

voor j=1

i ij

Cola • Wat is het toekomstig marktaandeel van cola 1? Stel nu dat we de toestand van de Markov keten niet kennen op tijdstip 0. We willen toch weten wat toekomstig marktaandeel is van cola 1. • We bekijken eerst de n-staps overgangsmatrix voor verschillende waarden van n. • Voor grote n lijkt (blijkt) de kans op cola 1 aankoop .67 te zijn onafhankelijk van de voorkeur op tijdstip 0 n 1 2 3 4 5 10 20 30 40

P 11(n) .90 .83 .78 .75 .72 .68 .67 .67 .67

P 12(n) .10 .17 .22 .25 .28 .32 .33 .33 .33

P 21(n) .20 .34 .44 .51 .56 .65 .67 .67 .67

P 22(n) .80 .66 .56 .49 .44 .35 .33 .33 .33

Cola • Wat is het toekomstig marktaandeel van cola 1? Stel nu dat we de toestand van de Markov keten niet kennen op tijdstip 0. We willen toch weten wat toekomstig marktaandeel is van cola 1. • We bekijken eerst de n-staps overgangsmatrix voor verschillende waarden van n. • Voor grote n lijkt (blijkt) de kans op cola 1 aankoop .67 te zijn onafhankelijk van de voorkeur op tijdstip 0 n 1 2 3 4 5 10 20 30 40

P 11(n) .90 .83 .78 .75 .72 .68 .67 .67 .67

P 12(n) .10 .17 .22 .25 .28 .32 .33 .33 .33

P 21(n) .20 .34 .44 .51 .56 .65 .67 .67 .67

Verklaring / intuïtie? Formeel?

P 22(n) .80 .66 .56 .49 .44 .35 .33 .33 .33

Vandaag: • • • • • •


RJ5

Markov keten: classificatie toestanden

• • • • •

0 0 0⎤ ⎡0.4 0.6 0 ⎢0.5 0.5 0 ⎥ 0 0 0 ⎢ ⎥ ⎢0 0 0.3 0.7 0 0⎥ P=⎢ ⎥ 0 0 0 . 5 0 . 4 0 . 1 0 ⎢ ⎥ ⎢0 0 0 0.8 0.2 0 ⎥ PLAATJE ⎢ ⎥ 0 0 0.4 0 0.6⎥⎦ ⎢⎣ 0 j bereikbaar vanuit i als er pad is van i naar j i en j communiceren als j bereikbaar vanuit i en i bereikbaar vanuit j Set toestanden S gesloten set als geen toestand buiten S bereikbaar vanuit toestand in S Toestand i absorberende toestand als pii=1

Slide 15 RJ5

plaatjes uit boek op bord tekenen! Boucherie; 25-11-2003

RJ12

Markov keten: classificatie

0 0 0⎤ ⎡0.4 0.6 0 toestanden ⎢⎢0.5 0.5 0 0 0 0 ⎥⎥ ⎢0 0 0.3 0.7 0 0⎥ P=⎢ ⎥ 0 0 0 . 5 0 . 4 0 . 1 0 ⎢ ⎥ ⎢0 0 0 0. 8 0. 2 0 ⎥ ⎢ ⎥ 0 0 0.4 0 0.6⎥⎦ ⎢⎣ 0

• Toestand i transiënt als er toestand j is die bereikbaar is vanuit i, maar i niet bereikbaar vanuit j • Recurrente toestand = niet transiënte toestand • Toestand i periodiek met periode k>1 als k is kleinste getal waarvoor alle paden van i naar i lengte hebben die veelvoud is van k. • Aperiodiek: recurrente toestand die niet periodiek is • Ergodische Markov keten: alle toestanden communiceren, zijn recurrent, en aperiodiek

Slide 16 RJ12

plaatjes uit boek op bord tekenen! Boucherie; 25-11-2003

Vandaag: • • • • • •


RJ6

Markov keten: evenwichtsverdeling • Evenwichtsverdeling beschrijft gedrag van de Markov keten op de lange duur • Stelling 1: Laat P de transitie matrix van een ergodische Markov keten met s toestanden. Er bestaat een unieke vector π = [π1 π2 … πs] zo dat

⎡π 1 π 2 L π s ⎤ ⎢π π L π ⎥ s⎥ 2 lim P n = ⎢ 1 n →∞ ⎢M M M⎥ ⎢ ⎥ π π L π s⎦ 2 ⎣ 1

Slide 18 RJ6

geef voorbeeld weerman op bord kansstromen uitleggen

Boucherie; 1-12-2003

RJ13

Markov keten: evenwichtsverdeling • Ofwel

lim P ( X n = j | X 0 = i ) = Pij (n) = π j n →∞

onafhankelijk begintoestand • De vector π = [π1 π2 … πs] noemen we stationaire verdeling of evenwichtsverdeling van de Markov keten • Stationair: wanneer we starten met beginverdeling π dan blijft de verdeling π. We kunnen π bepalen uit

π = πP

π = lim qP = πP n

n →∞

met normeringsvoorwaarde π1 +… + πs = 1.

Slide 19 RJ13



RJ14

Markov keten: evenwichtsverdeling • Stationaire verdeling Chapman-Kolmogorov vergelijkingen: s

Pij (n + 1) = ∑ Pik (n) pkj k =1

Voor grote n Invullen geeft

Pij (n + 1) ≈ Pij (n) ≈ π j s

π j = ∑ π k pkj k =1

Interpretatie?

Slide 20 RJ14



Transiënt gedrag & Intuïtie • Gedrag Markov keten voor stationair of evenwicht transiënt (korte termijn) gedrag. • Intuïtie evenwichtsvergelijkingen

π j = ∑ π k p kj k

∑π k

j

p jk = ∑ π k p kj k

• In evenwicht is de kansstroom naar iedere toestand gelijk aan de kansstroom uit iedere toestand.

Vandaag: • • • • • •


Evenwichtsverdeling voor beslissingen: Cola • Neem aan dat iedere persoon 1 maal per week cola koopt. • Stel 100 miljoen cola drinkers (kopers) • Verkopen van een fles cola kost de verkoper $1 aan productiekosten; fles wordt verkocht voor $2. • Advertentiebedrijf garandeert dat zij voor $500 miljoen per jaar de kans dat een cola 1 drinker wisselt naar cola 2 kan terugbrengen van 10% naar 5%. • Is het verstandig voor bedrijf dat cola 1 verkoopt (produceert) om het advertentiebedrijf in te huren?

Analyse • Momenteel is fractie π1 = ⅔ van alle cola aankopen van type cola 1. • Elke cola 1 aankoop geeft $1 winst. Momenteel is jaarlijkse winst 52*2/3*100.000.000*$1=$3,466,666,667. • Advertentiebedrijf biedt aan de matrix P veranderen in

⎡.95 P1 = ⎢ ⎣.20

.05 ⎤ .80 ⎥⎦

• Voor P1, vinden we de evenwichtsvergelijkingen π1 = .95π1+.20π2 π2 = .05π1+.80π2 met normeringsvoorwaarde π1 + π2 = 1 • Oplossen geeft π1=.8 en π2 = .2. • Met deze verdeling is de jaarlijkse winst voor bedrijf cola 1 52*0.8*100,000,000*$1-$500000000=$3,660,000,000 (na aftrek kosten $500 miljoen voor advertentiebedrijf) • Dit is meer dan $3,466,666,667. • Dus cola 1 bedrijf doet er verstandig aan advertentie bedrijf in te huren.

Vandaag: • • • • • •


Terugkeertijden • Voor ergodische Markov keten, laat mij = verwachte aantal transities nodig om j voor het eerst te bereiken vanuit i • mij is mean first passage time van i naar j. • Neem aan dat we nu in i zitten. Met kans pij hebben we 1 stap nodig om van i naar j te gaan. Voor k ≠ j moeten we eerst met kans pik naar toestand k. In dit geval hebben we 1 + mkj stappen nodig om van i naar j te komen. • We vinden zo

mij = 1 pij + ∑ (1 + mkj ) pik k≠ j

= pij + ∑ pik (mkj ) k≠ j

• We kunnen stelsel oplossen

m ij = 1 + ∑ p ik m kj k≠ j

• In het bijzonder kunnen we de terugkeertijd bepalen, waarvoor we tevens kunnen laten zien dat

m ii =

1

πi

• Waarom? Interpretatie evenwichtsverdeling

Samenvatting Markov ketens • Markov eigenschap (Markov proces)

P( X n +1 = in +1 | X n = in ,..., X 1 = i1 , X 0 = i0 )= P( X n +1 = in +1 | X n = in ) • Overganskansen

pij = P( X n +1 = j | X n = i )

• n-staps overgangskansen

Pij ( n ) = P ( X

m+n

= j|X

m

= i) = P ( X

n

= j|X

0

= i)

• Classificatie toestanden • Evenwichtsverdeling

π j = lim Pij (n) n →∞

π j = ∑ π k p kj k

• Terugkeertijden

m ij = 1 + ∑ p ik m kj k≠ j

•

πi

m ii =

fractie aantal stappen (‘tijd’) in toestand i

1

πi

Stochastische Modellen in Operations Management (153088)

Recommend Documents