Stochastic Operations Research I (2014/2015) Selection of exercises from book and previous exams.
Chapter 4: Continuous-time Markov Chains (Part I) 1.1 Book pp 179–185 These are useful exercises to learn the topic. 4.1; 4.2; 4.3; 4.4(a); 4.5(a); 4.6(a); 4.7(a); 4.8(a);
1.2 Uit Tentamens Opgave 1 [December 2013] Containerschepen met een lading van 100 containers varen naar de buitenhaven van Gotham City volgens een Poisson proces met intensiteit λ. Aan de havenkade kunnen slechts drie containerschepen aangemeerd liggen. Als de kapitein van een binnenvarend schip ziet dat de kade volledig bezet is, vaart hij door naar een concurrerende haven. Van de schepen die aan de kade liggen, wordt degene die het eerst was aangemeerd gelost. Zo gauw alle containers zijn gelost, verlaat dat schip de haven zodat er weer een plaats vrij komt aan de kade. Voor het lossen zijn 20 vrachtwagens beschikbaar. Het lossen van een container uit het schip op een vrachtwagen duurt een exponenti¨ele tijd met verwachting 1/µ. Containers worden ´e´en voor ´e´en na elkaar uit het schip gelost, en iedere vrachtwagen kan slechts ´e´en container vervoeren. Zo gauw een container op een vrachtwagen ligt, brengt deze zijn lading naar de bestemming in de containeropslag, en keert dan weer leeg terug naar de kade. Zo een rondrit (inclusief het afladen in de containeropslag) duurt een exponenti¨ele tijd met verwachting 1/α. De lege vrachtwagens wachten in aankomstvolgorde bij de kade voor een volgende container. (a). Formuleer een continue-tijds Markov-keten om de situatie van dit lossen van containers bij de haven te analyseren. Specificeer duidelijk wat de toestandsruimte I is, wat een toestand i voorstelt. Kies kenmerkende toestanden i en geef de bijbehorende overgangsintensiteiten qij . Bijvoorbeeld de toestand behorende bij de situatie dat er 2 schepen aangemeerd liggen, het voorste schip heeft nog 72 containers te lossen, en er staan 5 lege vrachtwagens bij de kade. En als er 1 schip ligt met nog 1 container en 5 vrachtwagens. Bedenk zelf andere toestanden die speciale aandacht eisen. (b). Geef voor de eerste toestand genoemd bij onderdeel (a) aan hoe je de overgangsintensiteiten qij hebt afgeleid uit de twee bekende regels (rule (a) en rule (b)) van een continue-tijds Markov-keten. (c). Volgende week:
1
(i). Wat is de lange-termijn fractie van de tijd dat er geen lege vrachtwagens bij de kade zijn, maar wel een schip met te lossen containers? Formuleer de stelling die je toepast voor deze prestatiemaat, en geef dan duidelijk aan hoe je die toepast. (ii). Wat is de lange-termijn fractie van potenti¨ele schepen die naar andere havens varen? Beredeneer deze fractie op twee manieren: • Pas een variant van de stelling van (c) toe. Formuleer deze, en geef dan duidelijk aan hoe je die toepast. • Pas PASTA toe. Wat betekent deze acroniem? Leg uit hoe je het toepast. (iii). Een aangemeerd schip betaalt 1000 euro liggeld per tijdseenheid. Hoe hoog zijn de lange-termijn gemiddelde inkomsten per tijdseenheid van de haven? Opgave 2 [Maart 2013] In Isra¨el rijden zogenaamde sheruts rond. Dit zijn goedkope taxi’s die plaatsbieden aan zeven passagiers en pas vertrekken zodra alle zeven plaatsen bezet zijn. In het kleine stadje Atlit zijn drie sheruts en ´e´en standplaats (bij het busstation). Bij de standplaats komen potenti¨ele passagiers aan volgens een Poisson proces met parameter λ. Een passagier die bij aankomst geen sherut aantreft, gaat naar elders en heeft verder geen invloed op het systeem. Een sherutrit duurt een stochastische expontieel verdeelde tijd met verwachting 1/µ. Na afloop van de rit keert de sherut terug naar de standplaats. (a). Formuleer een continue-tijds Markovketen om de situatie bij de standplaats te analyseren. Specificeer duidelijk wat de toestandsruimte I is, wat een toestand i voorstelt, en wat de overgangsintensiteiten qij zijn. Geef eventueel een toestandtransitiediagram. (b). Geef aan hoe je de overgangsintensiteiten qij hebt afgeleid uit de twee bekende regels (rule (a) en rule (b)) van een continue-tijds Markovketen. (c). Volgende week: (i) Wat is de lange-termijn fractie van de tijd dat er geen passagiers wachten maar wel een of meer sheruts aanwezig zijn? Formuleer de stelling die je toepast voor deze prestatiemaat, en geef dan duidelijk aan hoe je die toepast. (ii) Wat is de lange-termijn fractie van potenti¨ele passagiers die naar elders gaan? Geef aan hoe je de stelling van (i) hebt toegepast en/of hebt aangepast. (iii) Een sherutrit kost 50 shekels per passagier (shekel is de munteenheid van Isra¨el; ´e´en shekel is ongeveer 18 eurocent waard). Hoe hoog is de lange-termijn gemiddelde opbrengst per tijdseenheid? Opgave 3 [December 2012]
2
In Isra¨el rijden zogenaamde sheruts rond. Dit zijn goedkope taxi’s die plaats bieden aan zeven passagiers en pas vertrekken zodra alle zeven plaatsen bezet zijn. Het kleine stadje Ramla heeft ´e´en standplaats voor twee sheruts. Potenti¨ele passagiers arriveren volgens een Poisson proces met parameter λ. Een passagier die bij aankomst geen sherut aantreft maar wel zeven wachtenden, besluit een ander transportmiddel te gebruiken en heeft verder geen invloed op het systeem. Een rit van een sherut duurt een exponenti¨ele tijd met verwachting 1/µ om alle zeven klanten op de plaats van bestemming te brengen en om weer terug te keren naar een standplaats. (a). Formuleer een continue-tijds Markovketen om dit systeem te analyseren. Specificeer duidelijk wat de toestandsruimte I is, wat een toestand i voorstelt, en wat de overgangsintensiteiten qij zijn. Geef eventueel een toestand-transitiediagram. (b). Geef aan hoe je de overgangsintensiteiten qij hebt beredeneerd. (c). Volgende week: (i) Specificeer de evenwichtvergelijkingen voor de stationaire verdeling. (ii) Wat is de lange-termijn fractie van potenti¨ele passagiers die naar elders gaan? Beredeneer deze fractie op twee manieren: • Gebruik een opbrengst/kosten stelling. Formuleer deze stelling, en geef dan duidelijk aan hoe je die toepast. • Pas PASTA toe. Wat betekent deze acroniem? Leg uit hoe je het toepast. (iii) Wat is het gemiddeld aantal wachtende sheruts (dwz; op een willekeurig tijdstip). Geef aan welke eigenschap je toepast. (iv) Een sherutrit kost 50 shekels per passagier (shekel is de munteenheid van Isra¨el; ´e´en shekel is ongeveer 20 eurocent waard). Hoe hoog zijn de langetermijn gemiddelde opbrengst per tijdseenheid per sherut? Opgave 4 [Maart 2012] Beschouw een bedrijf met een productiehal waar n > 3 machines staan opgesteld voor het omzetten van grondstoffen en ruw materiaal in een aantal gewenste producten. Gereedgekomen producten worden afgehandeld en doorgestuurd naar de transport-afdeling voor verzending naar de klanten. Daarnaast beschikt het bedrijf over een reparatie-afdeling om kapotte machines te repareren. De “levensduren” van functionerende machines zijn onafhankelijke stochastische variabelen met een exponenti¨ele kansverdeling met intensiteit λ. Een kapotte machine vereist een hoeveelheid reparatiewerk dat exponentieel verdeeld is met verwachting 1/µ. De reparatie-afdeling verdeelt haar capaciteit gelijkelijk over alle kapotte machines. Dat wil zeggen, als er k kapotte machines zijn, dan wordt ieder gerepareerd met intensiteit 1/k. Een gerepareerde machine is weer “als nieuw”. Productie vindt plaats zolang er machines functioneren. Maar als er drie of minder machines functioneren, kan de afhandeling niet uitgevoerd worden waardoor de producten niet worden doorgestuurd naar de transport-afdeling. In dat geval stapelt zich een
3
voorraad gereedgekomen producten op die pas worden doorgestuurd als er weer vier (of meer) machines functioneren. Noem voor het gemak deze periode waarin de afhandeling stilligt de down-periode. Neem aan dat op tijdstip 0 alle n machines functioneren. We zijn ge¨ınteresseerd in de kansverdeling van de tijd tot de eerste down-periode. (a). Formuleer een geschikte continue-tijds Markov-keten om deze kansverdeling te kunnen berekenen. Specificeer de toestandsruimte I, de betekenis van een toestand i, en de overgangsintensiteiten qij . Geef eventueel een toestands-transitiediagram. (b). Volgende week: (i) Geef aan hoe de gevraagde kansverdeling berekend kan worden, en bespreek de uniformisatie methode als numerieke methode om dat uit te voeren. Beargumenteer waarom men uniformisatie toepast. (ii) Neem nu aan dat de productiehal al een zeer lange tijd in bedrijf is, en ook in bedrijf zal blijven. Dan zijn we ge¨ınteresseerd in de (lange-termijn) fractie van de tijd waarin de productiehal down is. Geef aan hoe die fractie berekend kan worden. Opgave 5 [Maart 2011] In een productie-voorraad systeem komen identieke producten ´e´en voor ´e´en gereed met tussentijden die onafhankelijk zijn en exponentieel verdeeld met verwachting 1/µ. Een gereed product wordt in voorraad genomen en is bestemd voor verkoop. Klanten voor het product komen aan volgens een Poisson proces met parameter λ, waarbij µ < λ. Als het product voorradig is, neemt de klant ´e´en product mee; anders gaat de klant naar elders, en gaat zijn vraag ‘verloren’. De opslagruimte voor de voorraad gereed product is onbeperkt. (a). Formuleer een geschikte continue-tijds Markovketen om dit productie-voorraad systeem te beschrijven. Specificeer de toestandsruimte I, de betekenis van een toestand i, en de overgangsintensiteiten qij . Geef eventueel een toestands-transitiediagram. (b). Geef aan hoe je de overgangsintensiteiten qij hebt afgeleid uit de twee bekende regels (rule (a) en rule (b)) van een continue-tijds Markovketen. (c). Volgende week: (i) Specificeer het (oneindig grote) stelsel lineaire vergelijkingen waaraan de evenwichtsverdeling voldoet, en laat vervolgens zien hoe de evenwichtskansen recursief berekend kunnen worden. (ii) Wat is de lange-termijn fractie van potenti¨ele passagiers die naar elders gaan? Formuleer de stelling of stellingen die je toepast voor deze prestatiemaat, en geef dan duidelijk aan hoe je die toepast.
4
(iii) Wat is de gemiddelde tijd dat een product in voorraad is alvorens het verkocht wordt? Opgave 6 [December 2010] In Isra¨el rijden zogenaamde sheruts rond. Dit zijn goedkope taxi’s die plaatsbieden aan zeven passagiers en pas vertrekken zodra alle zeven plaatsen bezet zijn. Beschouw een gegeven sherutstandplaats met plaats voor niet meer dan twee sheruts. Bij deze standplaats komen sheruts langs volgens een Poisson proces met parameter µ en een sherut stopt alleen dan bij de standplaats als daar geen sherut of slechts ´e´en sherut staat. Bij de standplaats komen potenti¨ele passagiers aan volgens een Poisson proces met parameter λ. Een passagier die bij aankomst geen sherut aantreft, gaat naar elders en heeft verder geen invloed op het systeem. (a). Formuleer een continue-tijds Markovketen om de situatie bij de standplaats te analyseren. Specificeer duidelijk wat de toestandsruimte I is, wat een toestand i voorstelt, en wat de overgangsintensiteiten qij zijn. Geef eventueel een toestandtransitiediagram. (b). Geef aan hoe je de overgangsintensiteiten qij hebt afgeleid uit de twee bekende regels (rule (a) en rule (b)) van een continue-tijds Markovketen. (c). Volgende week: (i) Wat is de long-run fractie van de tijd dat er geen passagiers wachten maar wel een of twee sheruts aanwezig zijn? Formuleer de stelling die je toepast voor deze prestatiemaat, en geef dan duidelijk aan hoe je die toepast. (ii) Wat is de long-run fractie van potenti¨ele passagiers die naar elders gaan? Geef aan hoe je de stelling van (i) hebt toegepast en/of hebt aangepast. (iii) Een sherutrit kost 50 shekels per passagier (shekel is de munteenheid van Isra¨el; ´e´en shekel is ongeveer 20 eurocent waard). Hoe hoog is de long-run gemiddelde opbrengst per tijdseenheid?
5
