INHOUDSOPGAVE LEERGANG BESLISKUNDE L.C.M. KALLENBERG UNIVERSITEIT LEIDEN
TEN GELEIDE
Deze ’Leergang Besliskunde’ bevat de dictaten die ik heb geschreven voor de diverse besliskundecolleges die door mij zijn gegeven. Het betreft de colleges: I.
Caleidoscoop (onderdeel besliskunde)
II.
Besliskunde 1
III.
Besliskunde 2
IV.
Besliskunde 3
V.
Besliskunde 4
VI.
Markov Decision Processes
Hieronder een overzicht met enkele gegevens over deze colleges. EC’s
Caleidoscoop
1-ste jaar
1
49
0
24
Besliskunde 1
2-de jaar
6
267
114
149
Besliskunde 2
3-de jaar
6 of 10 ∗∗∗
265
71
90
Besliskunde 4 Markov Decision Processes
3-de of 4-de jaar 3-de of 4-de jaar Master of PhD
6 of
12 ∗∗∗∗
Vragen
Opgaven
∗∗
Jaar
Besliskunde 3
Pagina’s
∗
Vak
248
60
93
4 tot 16
∗∗∗∗∗
509
137
156
4 tot 12
∗∗∗∗∗
437
0
118
∗
De oplossingen van de vragen staan achterin de dictaten.
∗∗
De oplossingen van de opgaven staan in aparte dictaten die voor docenten op aanvraag beschikbaar zijn.
∗∗∗
6 EC als alleen de eerste drie hoofdstukken worden gedaan.
∗∗∗∗
6 EC als alleen de eerste vijf hoofdstukken worden gedaan.
∗∗∗∗∗
Het aantal EC’s is afhankelijk van het aantal hoofdstukken dat wordt gedaan.
Het geheel bevat 2239 pagina’s, 1775 pagina’s stof inclusief de oplossingen van de vragen en 464 pagina’s met oplossingen van de opgaven. De stof is deels ontleend aan een groot aantal boeken, dictaten en ander materiaal dat door de auteur is geraadpleegd. De auteur stelt verbeteringen, aanvullingen en opmerkingen zeer op prijs.
Leiden, december 2009 Lodewijk Kallenberg
[email protected]
DEEL I: ONDERDEEL BESLISKUNDE IN CALEIDOSCOOP (45 pagina’s) 1. INLEIDING (7 pagina’s) 1.1 Wat is besliskunde? 1.2 Geschiedenis 1.3 Voorbeeld 1.4 Overzicht van een aantal besliskundige modellen 1.5 Opgaven 2. MATHEMATISCHE PROGRAMMERING (17 pagina’s) 2.1 Lineaire programmering 2.2 Geheeltallige lineaire programmering 2.3 Niet-lineaire programmering 2.3.1 Onbeperkte optimalisering 2.3.2 Beperkte optimalisering 2.4 Opgaven 3. NETWERK OPTIMALISATIE (7 pagina’s) 3.1 Dijkstra’s algoritme voor het kortste pad probleem 3.2 Ford-Fulkerson algoritme voor het maximale-stroom-probleem 3.3 Opgaven 4. MARKOV (BESLISSINGS)KETENS (14 pagina’s) 4.1 Markov ketens 4.2 Markov beslissingsketens 4.3 Opgaven
DEEL II: BESLISKUNDE 1 (265 pagina’s) 1. COMPLEXITEITSTHEORIE (16 pagina’s) 1.1 Inleiding 1.2 De klassen P en N P 1.3 Opgaven 2. GRAFENTHEORIE (50 pagina’s) 2.1 Inleiding 2.1.1 Niet-gerichte grafen 2.1.2 Gerichte grafen 2.1.3 Opgaven 2.2 Bomen 2.2.1 Algemeen 2.2.2 Binaire bomen 1
2.2.3 Huffman code 2.2.4 Depth-first Search en Breadth-First Search 2.2.5 Streng samenhangende componenten 2.2.6 Minimale opspannende boom 2.2.7 Opgaven 2.3 Euler en Hamilton grafen 2.3.1 Euler grafen 2.3.2 Hamilton grafen 2.3.3 Opgaven 3. COMBINATORIEK EN ENUMERATIE (52 pagina’s) 3.1 Permutaties, combinaties, rangschikkingen en partities 3.1.1 Permutaties 3.1.2 Combinaties 3.1.3 Rangschikkingen 3.1.4 Partities 3.1.5 Opgaven 3.2 Recurrente betrekkingen en voortbrengende functies 3.2.1 Homogene recurrente betrekkingen 3.2.2 Fibonacci-getallen 3.2.3 Inhomogene recurrente betrekkingen 3.2.4 Voortbrengende functies 3.2.5 Opgaven 3.3 Het principe van inclusie en exclusie 3.3.1 Zeefformule 3.3.2 Torenveelterm 3.3.3 De functies van Euler en M¨ obius 3.3.6 Opgaven 3.4 Het tellen van grafen; multinomiaalco¨effici¨enten 3.4.1 Grafen met genummerde knooppunten 3.4.2 Multinomiaalco¨effici¨enten 3.4.3 Opspannende bomen met genummerde knooppunten 3.4.4 Opgaven 3.5 Burnside’s Lemma en de theorie van Polya 3.5.1 Het Lemma van Burnside 3.5.2 De theorie van Polya 3.5.3 Het tellen van niet-isomorfe grafen 3.5.4 Opgaven
2
4. LINEAIRE OPTIMALISERING (56 pagina’s) 4.1 Model en toepassingen 4.1.1 Het model 4.1.2 Enkele toepassingen 4.1.3 Opgaven 4.2 Lineaire (on)gelijkheden en polyhedra 4.2.1 Theorie van de lineaire (on)gelijkheden 4.2.2 Polyhedra 4.2.3 Opgaven 4.3 Dualiteit 4.3.1 Zwakke en sterke dualiteit 4.3.2 Stricte complementariteit 4.3.3 Gelijkheden en vrije variabelen 4.3.4 Complexiteit 4.3.5 Economische interpretatie 4.3.6 Enkele resultaten afgeleid via dualiteit 4.3.7 Opgaven 4.4 De simplex methode 4.4.1 Inleiding en voorbeeld 4.4.2 Fase I - fase II techniek 4.4.3 Degeneratie: de regel van BLand 4.4.4 Complexiteit 4.4.5 Opgaven 5. DISCRETE MARKOV KETENS (42 pagina’s) 5.1 Inleiding en voorbeelden 5.2 Klassificatie van toestanden 5.3 Het limietgedrag van de overgangsmatrix Opgaven 6. VERNIEUWINGSTHEORIE (18 pagina’s) 6.1 Inleiding 6.2 Vernieuwingsvergelijking en Vernieuwingsstelling 6.3 Markov ketens met aftelbare toestandsruimte (vervolg) 6.4 Opgaven OPLOSSING VAN DE VRAGEN (26 pagina’s) INDEX (5 pagina’s)
3
DEEL III: BESLISKUNDE 2 (272 pagina’s) 1. LINEAIRE OPTIMALISERING (deel 2) (30 pagina’s) 1.1 Inleiding 1.2 Implementatie aspecten 1.2.1 Begrensde variabelen 1.2.2 Herziene simplex methode en de productvorm 1.2.3 Opgaven 1.3 Gevoeligheidsanalyse 1.3.1 Veranderingen in ´e´en co¨effici¨ent van de doelfunctie 1.3.2 Veranderingen in ´e´en co¨effici¨ent van het rechterlid 1.3.3 Veranderingen in meer co¨effici¨entenan het rechterlid (of de doelfunctie) 1.3.4 Veranderingen in een kolom van een niet-basisvariabele 1.3.5 Toevoegen van een nieuwe activiteit/variabele 1.3.6 Parametrische programmering 1.3.7 Opgaven 1.4 De duale en de primale-duale simplex methode 1.4.1 De duale simplex methode 1.4.2 De primale-duale methode 1.4.3 Opgaven 2. GEHEELTALLIGE LINEAIRE OPTIMALISERING (44 pagina’s) 2.1 Model, formuleringen en voorbeelden 2.1.1 Model en formuleringen 2.1.2 Voorbeelden 2.1.3 Opgaven 2.2 Branch-and-bound 2.2.1 Het generieke algoritme 2.2.2 Behandeling van en opsplitsing in deelproblemen 2.2.3 Opgaven 2.3 Sneden 2.3.1 Gomory’s fractie-snede algoritme 2.3.2 Gomory’s snede voor gemengd geheeltallige optimalisering 2.3.3 Opgaven 2.4 Handelsreizigersprobleem 2.4.1 Inleiding en formuleringen 2.4.2 Branch-and-Bound methode 2.4.3 Heuristieken 2.4.4 Opgaven
4
3. NIET- LINEAIRE OPTIMALISERING (64 pagina’s) 3.1 Inleiding 3.1.1 Klassificatie van niet-lineaire optimaliseringsproblemen 3.1.2 Voorbeelden 3.1.3 Afgeleiden 3.1.4 Optimaliteitsvoorwaarden 3.1.5 Convexiteit 3.1.6 OPgaven 3.2 Onbeperkte optimalisering 3.2.1 Inleiding 3.2.2 E´endimensionale optimalisatie 3.2.3 Meerdimensionale optimalisatie 3.2.4 Opgaven 3.3 Beperkte optimalisering: theorie 3.3.1 Inleiding 3.3.2 Lagrange multipliers bij gelijkheidsbeperkingen 3.3.3 Karush-Kuhn-Tucker voorwaarden bij gelijkheden en ongelijkheden 3.3.4 Fritz John voorwaarden 3.3.5 Convexe optimalisering en dualiteit 3.3.6 Opgaven 3.4 Beperkte optimalisering: methoden 3.4.1 Kwadratische optimalisering 3.4.2 Methode van toelaatbare richtingen 3.4.3 Gereduceerde gradi¨ent methode 3.4.4 Gegeneraliseerde gereduceerde gradi¨ent methode 3.4.5 Barri`erre methode 3.4.6 Opgaven 4. NETWERK OPTIMALISERING (50 pagina’s) 4.1 Kortste paden 4.1.1 Inleiding 4.1.2 Methode van Dijkstra 4.1.3 Methode van Bellman en Ford 4.1.4 Methode van Floyd en Warshall 4.1.5 De kortste gemiddelde ronde 4.1.6 Enkele toepassingen 4.1.7 Opgaven 4.2 Netwerkstromen 4.2.1 Maximale stromen 4.2.2 Minmale kostenstromen
5
4.2.3 Enkele toepassingen 4.2.4 Opgaven 5. SCHEDULING (24 pagina’s) 5.1 Inleiding 5.2 E´en machine 5.2.1 Model A: 1||Lmax P 5.2.2 Model B: 1|| nj=1 wj Cj P 5.2.3 Model C: 1|| nj=1 wj Uj 5.3 Twee machines 5.3.1 Model D: O2 ||Cmax 5.3.2 Model E: F2 ||Cmax 5.3.3 Model F: J2 ||Cmax 5.4 Parallelle machines 5.5 Verbanden met het handelsreizigersprobleen 5.5.1 Model K: 1|sjk |Cmax 5.5.2 Model L: Fm |no − wait|Cmax 5.6 Opgaven 6. SPELTHEORIE (20 pagina’s) 6.1 Inleiding 6.2 Tweepersonen nulsomspel 6.3 Bi-matrix spelen 6.4 Co¨operatieve spelen 6.5 Opgaven OPLOSSING VAN DE VRAGEN (35 pagina’s) INDEX (5 pagina’s)
DEEL IV: BESLISKUNDE 3 (253 pagina’s) 1. SPECIALE LINEAIRE MODELLEN (34 pagina’s) 1.1 Unimodulariteit en totaal unimodulariteit 1.2 Grafen en lineaire algebra 1.3 Transportprobleem 1.3.1 Inleiding 1.3.2 Tableau en startoplossing 1.3.3 Algemene iteratiestap 1.3.4 Gevoeligheidsanalyse 1.3.5 Toepassing
6
1.3.6 Het overslagprobleem 1.4 Toewijzingsprobleem 1.4.1 Probleemstelling en LP-formulering 1.4.2 Huwelijksstelling en transversalen 1.4.3 De Hongaarse methode 1.5 Opgaven 2. KNAPZAKPROBLEEM (28 pagina’s) 2.1 Inleiding 2.2 Het fractionele knapzakprobleem 2.3 Het 0-1 knapzakprobleem 2.3.1 Complexiteit 2.3.2 Dynamische programmering 2.3.3 Branch-and-bound 2.3.4 Het gretige algoritme 2.3.5 Polynomiale approximaties 2.4 Het begrensde knapzakprobleem 2.4.1 Transformatie tot een 0-1 knapzakprobleem 2.4.2 LP-relaxatie 2.4.3 Dynamische programmering 2.4.4 Branch-and-bound 2.4.5 Approximaties 2.5 Het onbegrensde knapzakprobleem 2.6 Bin-packing probleem 2.6.1 Inleiding 2.6.2 De Next-Fit heuristiek 2.6.3 De First-Fit en Best-Fit heuristieken 2.6.4 De First-Fit Decreasing en Best-Fit Decreasing heuristieken 2.7 Opgaven 3. PROJECT PLANNING (18 pagina’s) 3.1 Probleemstelling en modellering 3.2 Berekening van het kritieke pad 3.3 Bepaling van het kritieke pad met lineaire programmering 3.4 Het PERT-model 3.5 Projectplanning met kosten 3.6 Een alternatief model 3.7 Opgaven
7
4. DYNAMISCHE PROGRAMMERING (12 pagina’s) 4.1 Inleiding 4.2 Terminologie 4.3 Deterministische dynamische programmering 4.4 Stochastische dynamische programmering 4.5 Opgaven 5. CONTINUE MARKOV KETENS (24 pagina’s) 5.1 Inleiding 5.2 Differentiaalvergelijkingen en transi¨ent gedrag 5.3 Geboorte-sterfte processen 5.4 Stationair gedrag 5.5 Reversibiliteit 5.6 Uniformizatie 5.7 Opgaven 6. WACHTTIJDTHEORIE (34 pagina’s) 6.1 Inleiding 6.2 Wachttijdparadox 6.3 De formule van Little en PASTA 6.4 Geboorte-sterfte processen (vervolg) 6.5 Modellen gebaseerd op het geboorte-sterfte proces 6.6 Met M/G/1 model 6.7 Netwerken van wachtrijen 6.7.1 De tandem wachtrij 6.7.2 Open netwerk van wachtrijen (Jackson netwerken) 6.7.3 Gesloten netwerken van wachtrijen 6.8 Opgaven 7. MARKOV BESLISSINGSTHEORIE (48 pagina’s) 7.1 Inleiding 7.1.1 Het model 7.1.2 Strategi¨en en optimaliteitscriteria 7.1.3 Voorbeelden 7.2 Eindige horizon en totale opbrengsten 7.3 Oneindige horizon en verdisconteerde opbrengsten 7.3.1 Contraherende en monotone afbeeldingen 7.3.2 Strategie verbetering 7.3.3 Lineaire programmering 7.3.4 Waarde iteratie 7.4 Oneindige horizon en totale opbrengsten 8
7.4.1 Inleiding 7.4.2 Rood-zwart casino model 7.4.3 Optimaal stoppen 7.5 Gemiddelde opbrengsten over een oneindige horizon 7.5.1 Inleiding 7.5.2 Optimaliteitsvergelijking 7.5.3 Strategie verbetering 7.5.4 Lineaire programmering 7.5.5 Waarde iteratie 7.6 Opgaven 8. SIMULATIE (24 pagina’s) 8.1 Inleiding 8.2 Statistische verwerking van gegevens 8.3 Voorbeelden van simulaties 8.4 Aselecte getallen en aselecte trekkingen 8.5 Variantie reducerende technieken
8.5.1 Stratificatie
8.5.2 Complementaire aselecte getallen 8.6 Opgaven OPLOSSING VAN DE VRAGEN (23 pagina’s) TABELLEN (5 pagina’s) INDEX (3 pagina’s)
DEEL V: BESLISKUNDE 4 (509 pagina’s) 1. GRAFENTHEORIE (deel 2) (86 pagina’s) 1.1 Grafen en matrices 1.1.1 Grafen en vectorruimtes 1.1.2 De incidentiematrx 1.1.3 De kringenmatrix 1.1.4 De snedenmatrix 1.1.5 De padenmatrix 1.1.6 De structuurmatrix 1.1.7 Opgaven 1.2 Vlakke en duale grafen 1.2.1 Vlakke grafen en Euler’s veelvlakkenformule 1.2.2 Scheidingspunten 1.2.3 Separabiliteit en blokken
9
1.2.4 Stelling van Kuratowski 1.2.5 Algoritme om te bepalen of een graaf vlak is 1.2.6 Rechte grafen en driehoeksgrafen 1.2.7 Minimum en maximum aantal snijpunten 1.2.8 Duale grafen 1.2.9 Opgaven 1.3 Kleurproblemen 1.3.1 Het kleuren van takken 1.3.2 Het kleuren van knooppunten 1.3.3 Het kleuren van gebieden in een vlakke graaf: het vierkleurenprobleem 1.3.4 Het kleurenpolynoom 1.3.5 Opgaven 2. NETWERK OPTIMALISERING (deel 2) (50 pagina’s) 2.1 Netwerkstromen 2.1.1 Disjuncte paden en de Stelling van Menger 2.1.2 Maximale stromen en minmale sneden 2.1.3 Circulatiestromen met minimale kosten 2.1.4 Opgaven 2.2 Netwerk simplex methode 2.2.1 Inleiding 2.2.2 Bases en opspannende bomen 2.2.3 Algoritme voor problemen zonder capaciteiten 2.2.4 Problemen met onder- en bovengrenzen 2.2.5 Duale netwerk simplex methode 2.2.6 De netwerk simplex methode voor het kortste pad probleem 2.2.7 Maximale stroom probleem 2.2.8 Opgaven 3. KOPPELINGEN (52 pagina’s) 3.1 Algemene theorie 3.1.1 Eigenschappen in algemene grafen 3.1.2 Eigenschappen in bipartiete grafen 3.1.3 Equivalente combinatorische resultaten 3.1.4 Opgaven 3.2 Algoritmen voor bipartiete grafen 3.2.1 Koppeling met maximale cardinaliteit in een bipartiete graaf 3.2.2 Koppeling met maximaal gewicht in een bipartiete graaf 3.2.3 Gilmore-Gomory en Gale-Shapley koppelingen 3.2.4 Opgaven 3.3 Algoritmen voor algemene grafen 10
3.3.1 Koppeling met maximale cardinaliteit in een willekeurige graaf 3.3.2 Koppeling met maximaal gewicht in een willekeurige graaf 3.3.3 Opgaven 4. MATRO¨ IDEN (50 pagina’s) 4.1 Inleiding en definities 4.2 Duale matro¨ıde 4.3 Voorbeelden van matro¨ıden 4.4 Grafen en matro¨ıden 4.5 Het gretige algoritme 4.6 Onafhankelijkheidssystemen 4.7 Doorsnede van matro¨ıden 4.7.1 Inleiding 4.7.2 Onafhankelijke verzameling met maximale cardinaliteit 4.7.3 Onafhankelijke verzameling met maximaal gewicht 4.8 Grafo¨ıden 4.9 Representeerbaarheid van matro¨ıden 4.10 Polymatro¨ıden 4.11 Opgaven 5. INWENDIGE PUNT METHODEN (66 pagina’s) 5.1 Inleiding 5.2 De methode van Karmarkar 5.2.1 Het idee van projectieve schaling 5.2.2 Het algoritme 5.3 De affiene schaling methode 5.3.1 De primale affiene schaling methode 5.3.2 De duale affiene schaling methode 5.3.3 De duale-primale affiene schaling methode 5.4 Potentiaal reductie methode 5.5 Pad-volgende methoden 5.5.1 Primale pad-volgende methode 5.5.2 Primale-duale pad-volgende methode 5.5.3 Predictor-corrector methode 5.5.4 Vergelijking van de richtingen van diverse inwendige punt methoden 6. VOORAADTHEORIE (34 pagina’s) 6.1 Inleiding 6.2 Continue deterministische modellen met ´e´en product 6.3 Continue deterministische modellen met meer producten 6.3.1 De afwegingskromme 11
6.3.2 Een cyclisch productieproces 6.4 Periodieke deterministische modellen 6.4.1 Geen tekorten toegestaan 6.4.2 Wel tekorten toegestaan 6.4.3 Silver-Meal heuristiek 6.5 Continue stochastische modellen 6.6 Periodieke stochastische modellen 6.6.1 E´en periode en geen vaste bestelkosten:(krantenjongenprobleem) 6.6.2 E´en periode, vaste bestelkosten en een beginvoorraad 6.6.3 Oneindig veel perioden en geen vaste bestelkosten 6.7 Opgaven 7. BESLISSINGSTHEORIE (10 pagina’s) 7.1 Inleiding 7.2 Beslissen zonder kansen 7.3 Beslissen met kansen 7.4 Beslissingsbomen 7.5 Opgaven 8. BETROUWBAARHEIDSTHEORIE (24 pagina’s) 8.1 Structuurfuncties 8.2 Betrouwbaarheidsfuncties 8.3 Levensduur van het systeem 8.4 De verwachte levensduur 8.5 Systemen met reparatie 8.6 Opgaven 9. SPECIALE TECHNIEKEN (50 pagina’s) 9.1 Decompositie technieken 9.1.1 Dantzig-Wolfe decompositie 9.1.2 Benders decompositie 9.1.3 Opgaven 9.2 Lagrange relaxatie 9.2.1 Inleiding en voorbeelden 9.2.2 Beste Lagrange relaxatie 9.2.3 Opgaven 9.3 Kolomgeneratie voor geheeltallige problemen 9.3.1 Inleiding 9.3.2 Dantzig-Wolfe decompositie van een geheeltallig LP-probleem 9.3.3 LP-relaxatie van het masterprobleem 9.3.4 Branch-and-price agoritme voor 0-1 problemen 12
9.3.5 Opgaven 10. BOMEN (deel 2), SORTEREN EN HET CHINESE POSTBODEPROBLEEM (48 pagina’s) 10.1 Bomen (deel 2) 10.1.1 Boomwandelingen 10.1.2 Binaire zoekbomen 10.1.3 Steiner bomen 10.2 Sorteren 10.2.1 Bubble sort 10.2.2 Insertion sort 10.2.3 Merge sort 10.2.4 Quick sort 10.3 Het Chinese postbodeprobleem 10.3.1 Ongerichte versie 10.3.2 Gerichte versie 10.3.3 Gemengde versie 10.4 Opgaven OPLOSSING VAN DE VRAGEN (52 pagina’s) TABELLEN (2 pagina’s) INDEX (5 pagina’s)
DEEL VI: MARKOV DECISION PROCESSES (437 pagina’s) 1. INTRODUCTION (28 pagina’s) 1.1 The MDP model 1.2 Policies and optimality criteria 1.2.1 Policies 1.2.2 Optimality criteria 1.3 Examples 1.3.1 Red-black gambling 1.3.2 Gaming: How to serve in tennis 1.3.3 Optimal stopping 1.3.4 Replacement problems 1.3.5 Maintenance and repair 1.3.6 Production control 1.3.7 Optimal control of queues 1.3.8 Stochastic scheduling
13
1.3.9 Multi-armed bandit problem 1.4 Bibliographic notes 1.5 Exercises 2. FINITE HORIZON (10 pagina’s) 2.1 Introduction 2.2 Backward induction 2.3 An equivalent stationary infinite horizon model 2.4 Monotone optimal policies 2.5 Bibliographic notes 2.6 Exercises 3. DISCOUNTED REWARDS (50 pagina’s) 3.1 Introduction 3.2 Monotone contraction mappings 3.3 The optimality equation 3.4 Policy iteration 3.5 Linear programming 3.6 Value iteration 3.7 Modified policy iteration 3.8 Bibliographic notes 3.9 Exercises 4. TOTAL REWARD (36 pagina’s) 4.1 Introduction 4.2 Equivalent statements for contracting 4.3 The contracting model 4.4 Positive MDPs 4.5 Negative MDPs 4.6 Convergent MDPs 4.7 Special models 4.7.1 Red-black gambling 4.7.2 Optimal stopping 4.8 Bibliographic notes 4.9 Exercises 5. AVERAGE REWARD - GENERAL CASE (42 pagina’s) 5.1 Introduction 5.2 Classification of MDPs 5.2.1 Definitions 5.2.2 Classification of Markov chains
14
5.2.3 Classification of Markov decision chains 5.3 Stationary, fundamental and deviation matrix 5.3.1 The stationary matrix 5.3.2 The fundamental matrix and the deviation matrix 5.4 Extension of Blackwell’s theorem 5.5 The Laurent series expansion 5.6 The optimality equation 5.7 Policy iteration 5.8 Linear programming 5.9 Value iteration 5.10 Bibliographic notes 5.11 Exercises 6. AVERAGE REWARD - SPECIAL CASES (36 pagina’s) 6.1 The irreducible case 6.1.1 Optimality equation 6.1.2 Policy iteration 6.1.3 Linear programming 6.1.4 Value iteration 6.1.5 Modified policy iteration 6.2 Unichain case 6.2.1 Optimality equation 6.2.2 Policy iteration 6.2.3 Linear programming 6.2.4 Value iteration 6.2.5 Modified policy iteration 6.3 Communicating case 6.3.1 Optimality equation 6.3.2 Policy iteration 6.3.3 Linear programming 6.3.4 Value iteration 6.3.5 Modified policy iteration 6.4 Bibliographic notes 6.5 Exercises 7. MORE SENSITIVE OPTIMALITY CRITERIA (44 pagina’s) 7.1 Introduction 7.2 Eqiuvalence between n-discount and n-average optimality 7.3 Stationary optimal policies and optimality equations 7.4 Lexicographic ordering of Laurent series 7.5 Policy iteration for n-discount optimality 15
7.6 Linear programming and n-discount optimality (irreducible case) 7.6.1 Average optimality 7.6.2 Bias optimality 7.6.3 n-discount optimality 7.7 Blackwell optimality and linear programming 7.8 Bias optimality and linear programming 7.8.1 The general case 7.8.2 The unichain case 7.9 Overtaking and average overtaking optimality 7.10 Bibliographic notes 7.11 Exercises 8. SPECIAL MODELS (86 pagina’s) 8.1 Replacement problems 8.1.1 A general replacement model 8.1.2 A replacement model with increasing deterioration 8.1.3 Skip to the right model with failure 8.1.4 A separable replacement model 8.2 Maintenance and repair problems 8.2.1 A surveillance-maintenance-replacement problem 8.2.2 Optimal repair allocation in a series system 8.3 Production and inventory control 8.3.1 No backlogging 8.3.2 Backlogging 8.3.3 Inventory control and single-critical-number policies 8.3.4 Inventory control and (s, S)-policies 8.4 Optimal control of queues 8.4.1 The single-server queue 8.4.2 Parallel queues 8.5 Stochastic scheduling 8.5.1 Maximizing finite-time returns on a single processor 8.5.2 Optimality of the µc-rule 8.5.3 Optimality of threshold policies 8.5.4 Optimality of join-the-shortest-queue policies 8.5.5 Optimality of LEPT and SEPT policies 8.5.6 Maximizing finite-time returns on two processors 8.5.7 Tandem queues 8.6 Multi-armed bandit problems 8.6.1 Introduction 8.6.2 A single project with a terminal reward
16
8.6.3 Multi-armed bandits 8.6.4 Methods for the computation of the Gittins indices 8.7 Separable problems 8.7.1 Introduction 8.7.2 Examples (part 1) 8.7.3 Discounted rewards - unichain case 8.7.4 Discounted rewards - general case 8.7.5 Examples (part 2) 8.8 Bibliographic notes 8.9 Exercises 9. OTHER TOPICS (32 pagina’s) 9.1 Additional constraints 9.1.1 Introduction 9.1.2 Infinite horizon and discounted rewards 9.1.3 Infinite horizon and average rewards 9.2 Multiple objectives 9.2.1 Discounted rewards 9.2.2 Average rewards 9.3 Mean-variance tradeoffs 9.3.1 Formulations of the problem 9.3.2 A unifying framework 9.3.3 Determination of an optimal solution 9.3.4 Determination of an optimal policy 9.4 Bibliographic notes 9.5 Exercises 10. STOCHASTIC GAMES (54 pagina’s) 10.1 Introduction 10.1.1 The model 10.1.2 Optimality criteria 10.1.3 Matrix games 10.2 Discounted rewards 10.2.1 Value and optimal policies 10.2.2 Mathematical programming 10.2.3 Iterative methods 10.2.4 Finite methods 10.3 Average rewards 10.3.1 Value and optimal policies 10.3.2 The Big Match 10.3.3 Mathematical programming 17
10.3.4 Perfect information and irreducible games 10.3.5 Finite methods 10.4 Bibliographic notes 10.5 Exercises BIBLIOGRAPHY (16 pagina’s) INDEX (3 pagina’s)
18
