Stochastische Modellen in Operations Management (153088)

S1

S2 X ms

X ms

Stochastische Modellen in Operations Management (153088)

R1

S0

240 ms

Ack

Internet

R2

L1

R3

L2

10 ms

1

10 ms

D1

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

D2

Karakteristieken Dynamische Programmering •  •  •  • 

Probleem kan worden opgedeeld in fasen Elke fase is geassocieerd met een aantal toestanden Actie / beslissing in toestand legt volgende toestand vast Gegeven huidige toestand mag beslissing voor volgende fasen niet afhangen van eerdere fasen (principe van optimaliteit, Bellman) •  Er is een recursie die verwachte kosten / opbrengst van fasen n, n+1, …, T relateert aan kosten van fasen n+1, …, T

Kosten zijn zeker, volgende toestand is zeker Kosten zijn onzeker, volgende toestand is zeker Kosten zijn onzeker, volgende toestand is onzeker

2

Variabelen •  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 –  Overgang naar toestand j als gevolg van beslissing d bij toestand i in fase n

3

4

Vandaag: •  Beleggen in opties •  Stochastisch dynamische programmering •  Dobbelspelletje •  Beslisbomen •  Samenvatting •  How to gamble if you must

Beleggen in opties (1) •  Situatieschets –  je bezit een optie om gedurende de komende N dagen een hoeveelheid aandelen te kopen tegen een vaste prijs van c Euro per aandeel –  je maakt een winst van max{0,i-c} Euro per aandeel als de koers gelijk is aan i Euro op de dag van aankoop –  de huidige koers van het aandeel is s, maar verandert per dag met +1, -1 of 0, met bijbehorende kansen p, q en 1-p-q •  Gevraagd –  de optimale strategie en de maximale verwachte winst per aandeel •  Opgave (N=5, s=c=50, p=q=1/3) –  Bepaal de optimale strategie

5

Beleggen in opties (2) •  Fasen –  opeenvolgende dagen : n = 0,...,N •  Toestand –  koers v/h aandeel : in ∈ {s - n,...,s + n} •  Beslissing –  kopen of niet kopen? •  Optimale waardefunctie –  definieer fn(i) als de maximale verwachte winst indien de koers i Euro bedraagt als er n dagen verstreken zijn •  Recurrente betrekkingen ?

6

Beleggen in opties (3) •  Optimale waardefunctie –  definieer fn(i) als de maximale verwachte winst indien de koers i gulden bedraagt als er n dagen verstreken zijn •  Recurrente betrekkingen –  na N dagen is de optie verlopen, d.w.z. fN (i) = max{0,i-c} voor alle i –  voor 0≤ n< N geldt het volgende:

7

Beleggen in opties (4) •  Voorbeeld (N=5, s=c=50, p=q=1/3) –  de optimale strategie laat zich eenvoudig aflezen uit de volgende tabel (rood = beslissing kopen):

–  de maximale verwachte winst bedraagt hierbij f0(50)=72 cent per aandeel (is waarde optie op tijdstip 0)

8

9


10

Deterministische Stochastische Dynamische Programmering •  Toepassingen –  beslissingsproblemen over een eindige horizon waarbij de beslismomenten geordend zijn (doorgaans in de tijd)

•  Probleemstructuur –  optimale strategie m.b.v. recursie

fase n toestand in ∈ Sn

overgang overgangskansen |iinn,,ddnn) pinn+1 ( in+1

beslissing dn ∈ Dn ( in )

directe resultaat rn ( in , dn )

SDP (kosten onzeker, volgende toestand onzeker) •  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

•  Overgangskansen pn (j|i,d) –  kans op toestand j als gevolg van beslissing d bij toestand i in fase n

11

12

Optimalisatie

•  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 ∈Sn+1 

•  Stopcriterium –  aan het eind van de planningshorizon ligt alles vast, d.w.z. fN (i) moet gegeven zijn voor alle i ∈ SN

€

Verschillende varianten

13

•  Determistisch vs. stochastisch –  bij deterministische DP problemen zijn de gevolgen van iedere beslissing bekend: pn(j|i,d)=1 voor zekere j bij alle n,i,d –  bij stochastische DP problemen is dat niet (altijd) het geval •  Discreet vs. continu –  bij discrete DP problemen is aantal toestanden aftelbaar –  bij continue DP problemen is aantal toestanden overaftelbaar •  Eén vs. meerdere dimensies –  een toestand uit de toestandsruimte kan soms uit meerdere variabelen bestaan •  Doelstellingen –  maximale verwachtingswaarde van ... –  maximale kans op ...

14


15

Een dobbelspelletje (1) •  Situatieschets –  je mag maximaal N maal werpen met een (zuivere) dobbelsteen –  na elke worp moet je beslissen of je doorgaat of stopt –  de uitbetaling van het spel is het aantal gegooide ogen in de laatste worp •  Gevraagd –  de optimale strategie en de maximale verwachte uitbetaling of `hoeveel wilt u inzetten om mee te doen?’ •  Optimale waardefunctie –  definieer fn(i) als de maximale verwachte uitbetaling indien je n maal gegooid hebt, en het aantal ogen in de laatste worp gelijk is aan i

16

Een dobbelspelletje (2)

•  Fasen –  opeenvolgende worpen : n = 0,...,N •  Toestand –  aantal ogen in laatste worp : i ∈ {1,...,6} •  Beslissing –  stoppen of doorgaan? •  Optimale waardefunctie –  fn(i) max verwachte uitbetaling indien je n maal gegooid hebt, en aantal ogen in de laatste worp is i •  Recurrente betrekkingen –  na N worpen is het spelletje afgelopen fN (i)=i, i=1,…,6 –  voor 0≤ n< N geldt 6    f n (i) = max  i ,  

1 6

∑ j =1

 f n +1 ( j)   

17

Een dobbelspelletje (4) •  Voorbeeld (N=6) –  de optimale strategie laat zich eenvoudig aflezen uit de volgende tabel (rood = beslissing stoppen)

–  de verwachte uitbetaling van het spel bedraagt f0(0)=(5/6)*5.130+(1/6)*6=5.275 gulden

18


Wasmachine fabrikant (1)

19

•  Pilgrim benaderd door het warenhuis D&V met het aanbod om exclusief voor D&V wasmachines te maken. •  Huidige winst van Pilgrim uit eigen verkopen is 1 miljoen euro. •  Accepteert Pilgrim het aanbod dan levert dit een jaarlijkse winstbijdrage van E 250.000,-. •  Door substitutie effecten dalen de eigen verkopen. •  Geschatte winstdaling op de eigen verkopen is 25% met kans 0.1, 30% met kans 0.6 en 35% met kans 0.3. •  Indien Pilgrim aanbod afslaat zal met kans 0.4 een concurrent het aanbod accepteren, in welk geval de hiervoor genoemde winstdaling toch optreedt. •  Pilgrim kan in dit geval echter ook tot actie overgaan, hetzij door de eigen prijs te verlagen, hetzij door meer reclame te maken. •  De extra reclame kost jaarlijks E 100.000,-- en heeft als effect dat de winstdaling minder is en wel 10% met kans 0.2, 15% met kans 0.7 en 20% met kans 0.1. •  Prijsverlaging beperkt de winstdaling tot 10% met kans 0.1, 15% met kans 0.8 en 20% met kans 0.1, mits de concurrent niet ook zijn prijs omlaag doet. Kans dat concurrent met een prijsverlaging reageert als Pilgrim hiertoe besluit is 0.5, met als gevolg dat Pilgrim's winstdaling 10% is met kans 0.1, 15% met kans 0.6 of 20% met kans 0.3. •  Welke politiek moet Pilgrim toepassen opdat zijn verwachte winstdaling zo klein mogelijk is?

20 •  Huidige winst E 1 miljoen uit eigen verkoop •  aanbod warenhuis: maak exclusief machines voor warenhuis •  acceptatie: winstbijdrage E 250.000 maar minder eigen verkopen (substitutie): 25% met kans 0.1, 30% met kans 0.6, 35% met kans 0.3 •  afslaan: concurrent accepteert aanbod met kans 40% dan zelfde winstdaling •  mogelijke actie bij acceptatie aanbod door concurrent: prijs verlagen -- minder eigen verkopen als conc. prijs gelijk: 10% met kans 0.1, 15% met kans 0.8, 20% met kans 0.1 -- als conc. prijs lager (kans hierop 50%): 10% met kans 0.1, 15% met kans 0.6, 20% met kans 0.3 reclame maken (kosten E100.000) -- minder eigen verkopen: 10% met kans 0.2, 15% met kans 0.7, 20% met kans 0.1 niets doen

Wasmachine fabrikant (2) beslisboom

beslissing

realisatie; gevolg omgeving

21

22

Beslisbomen •  Vaak meerdere besluiten •  Aantal besluiten niet altijd vooraf bekend •  Structuur van beslisprobleem vaak gecompliceerd •  Beslisboom geeft structuur aan beslissingsprobleem •  Decompositie in meerdere deelproblemen •  Visualisatie van beslissingsprobleem

Wasmachine fabrikant (3) •  Achterwaarts •  f2 minimale verwachte winstderving in situatie 2 •  f1 minimale verwachte winstderving in situatie 1

Het is optimaal bod te accepteren, met verw. winstderving 60

23

24


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 ∈Sn+1 

•  Beslisbomen: grafische voorstelling •  Extra voorbeelden W 19.1-.4 & dictaat OR II

€

25

Geluidbelasting Schiphol

27

28


29

How to gamble if you must •  U heeft 2 Euro en dringend behoefte uw kapitaal te vergroten tot 16 Euro •  U heeft de mogelijkheid deel te nemen aan een gokspel, met winstkans 40%, verlieskans 60% •  Inzet bij dit spel is ongelimiteerd, maar in hele Euro’s •  Uitbetaling bij winst is twee maal uw inzet •  Bepaal een strategie om uw kans op bereiken doel te maximaliseren

Stochastische Modellen in Operations Management (153088)

Recommend Documents