Stof
De hoofdstukken 1, 2, 3, 5 en 6 (deel) uit het boek "Operationele
Analyse: een inleiding in modellen en methoden" (auteur H.C.
Tijms;
Epsilon Uigaven no. 54, Utrecht, 2e druk 2004; ISBN 90-5041-075-8)
worden behandeld.
Software
Voor het oplossen van LP-problemen kan gebruik worden gemaakt van het
de hier
te downloaden software
Planning
12 februari - 5 maart: Hoofdstuk 1
- 12 februari: paragrafen 1.1 t/m 1.3
- 19 februari: geen college
- 26 februari: paragrafen 1.4 en 1.5
- 5 maart: paragrafen 1.6 en 1.7
12 maart - 26 maart: Hoofdstuk 2
- 12 maart: paragrafen 2.1, 2.2 en 2.3
- 19 maart: paragrafen 2.4 en 2.5
- 26 maart: paragrafen 2.6, 2.7 en 2.8
2 - 16 april: Hoofdstuk 3
- 2 april: paragrafen 3.1 en 3.2
- 9 april: geen college
- 16 april: paragrafen 3.3, 3.4 en 3.5
23 april - 7 mei:: Hoofdstuk 5
- 23 april: 5.1, 5.2, 5.3, 5.4 en 5.5
- 30 april: geen college
- 7 mei: paragrafen 5.6, 5.7 en 5.8
14 en 21 mei: Hoofdstuk 6
- 14 mei: paragrafen 6.1, 6.2 en 6.3 (deel)
- 21 mei: vervalt
4 juni: bespreken oefententamen en vragen
11 juni: tentamen
Tentameneisen
Wekelijks moeten opgaven worden ingeleverd. Verder krijgt iedere
student een
wat grotere opdracht, waarbij gebruik mag worden gemaakt van het pakket
OR-Stat. Daarnaast is er een schriftelijk open boek tentamen op 11
juni. De opgaven, de
opdracht en het schriftelijk tellen voor 30%, 30% resp. 40% mee voor
het
eindcijfer, met als randvoorwaarde dat voor ieder onderdeel minstens
een 5 moet
worden gescoord.
In te leveren opgaven met antwoorden of aanwijzingen
Serie 1: opgaven 1.1, 1.7, 1.9 en 1.12; inleverdatum 5 maart
Opgave 1.1 : Optimaal is 50 liter Spicy Gonzales en 20 liter
Cool Gringo
per week te maken.
Opgave 1.7 : Optimaal is 1250 kg mozarella en 750 kg ricotto
per dag te
maken.
Opgave 1.9 : De kwadratische curve is: 0.1132x^2 -0.3951x
+1.1963; de
logaritmische curve: 0.51 + 5.7035 log x.
Opgave 1.12: De optimale oplossing luidt: x1 = 1.8, x2 = 1.3, x3 = 0;
de
optimale oplossing van het duale probleem is: u1 = u2 = 0.5.
Serie 2: opgaven 1.16, 1.20, 1.22a en 1.24; inleverdatum 12 maart
Opgave 1.16: a. optimum wordt 461 (bij 87) of hoogstens 395
(bij 65); b.
optimum wordt 458; c. 90 euro; d. 10 euro; e. ja; f. nee
Opgave 1.20: a. 1500; b. zelfde oplossing, optimum 400 hoger; c. zonder
eis
optimum 1600 lager; met eis minstens 525 optimum minstens 500 hoger; d.
optimum
500 lager; e. nee; f. nee
Opgave 1.22: a. in maand 1 wordt 600 voor maand 1 en 50 voor
maand 2 in
normale werktijd geproduceerd; in maand 2 wordt 750 voor maand 2 in
normale
werktijd geproduceerd; in maand 3 wordt 750 voor maand 3 in normale
werktijd
geproduceerd en 150 door overwerk.
Opgave 1.24: a. optimale oplossing: 15 ton product 1 en 42 ton product
2; b.
aanbod is niet aantrekkelijk; c. willekeurig.
Serie 3: opgaven 2.3, 2.7 en 2.12; inleverdatum 26 maart
Opgave 2.3: het optimum geeft waarde 410: vrachtwagen 1 levert aan de klanten 1 en 7; vrachtwagen 2 levert aan de klanten 2, 4 en 6; vrachtwagen 3 levert aan geen enkele klant; vrachtwagen 4 levert aan de klanten 3 en 5 (er zijn meer optimale oplossingen).
Opgave 2.7: a. 26 kwartjes, 26 guldens en 27 rijksdaalders; b. 24 kwartjes, 24 guldens en 28 rijksdaalders.
Opgave 2.12: er is een oplossing
waarbij slechts 1 bewaker
niet vrij heeft op twee opeenvolgende dagen.
Serie 4: opgaven 2.16, 2.21 en 2.23; inleverdatum 2 april
Opgave 2.16: neem binaire variabelen xij waarbij xij = 1 betekent dat in de steden i en j een centrale wordt gebouwd; bepaal verder de reistijd van een stad k naar de dichtstbijzijnde centrale, gegeven dat in i en j een centrale staat; maak hiermee een geheeltallig optimaliseringsprobleem en los het op met ORSTAT; de oplossing is om in de plaatsen 1 en 5 een centrale te bouwen.
Opgave 2.21 (de eerste versie met de Clarke en Wright heuristiek wordt gevraagd; in het boek staan twee opgaven 2.21): de oplossing met deze heuristiek geeft twee routes: O-D-A-E-B-G-O en O-C-F-O met totale reistijd van 328.
Opgave 2.23 (pas deze constructie heuristiek toe zonder het eliminatie-deel): kies eerst stad 2, dan stad 4 en tenslotte stad 5; de niet gekozen steden 1, 3, 6 en 7 worden aan de faciliteit in stad 2 toegewezen. Totale afstand is 7534 (blijkt bij het exact oplossen ook de optimale oplossing te zijn).
Serie 5: opgaven 3.2, 3.6 en
3.8; inleverdatum 16 april
Opgave 3.2: de goedkoopste verbinding van 1 naar 7 is de route
[1,2,5,6,7].
Opgave 3.6: in de opgave staat een fout: 9000 liter per uur voor
raffinaderij
17,000 liter per uur moet zijn: 9000 liter per uur
voor raffinaderij 1,
7000 liter per uur voor raffinaderij 2. De optimale bevoorrading is:
van
olieveld 1 1000 liter per uur naar raffinaderij 1 en 7.500 liter per
uur naar
raffinaderij 3 en van olieveld 2 8000 liter per uur naar raffinaderij 1
en 7000
liter per uur naar raffinaderij 2.
Opgave 3.8: de route van A via B naar D geeft het minste verlies
(96,03%).
Serie 6: opgaven 3.10 (oude
druk 3.12), 3.14 (oude druk
3.16) en 3.15 (oude druk 3.18); inleverdatum 23 april
Opgave 3.10: Pad A-C-E-G.
Opgave 3.14: Kritieke pad: A-C-D-F-H
Opgave 3.15: Docent 1 ggen vak, docent 2 vak 4, docent 3 vak 1, docent 4 vak 2 en docent 5 vak 3.
Serie 7: opgaven 5.6, 5.8 (oude druk 5.9) en 5.14 (oude druk
5.15);
inleverdatum 14 mei
Opgave 5.6: Zoals aangegeven te bewijzen met volledige inductie.
Opgave 5.8: De rijnaak wordt beladen met de vracht van de bedrijven 3 en 6.
Opgave 5.14: x1 = 6, x2 = 2 en x3 = 2.
Serie 8: opgaven 5.15 (oude druk 5.16), 5.18 (oude druk 5.20)
en
5.22 (oude druk 5.23 en daarin staat in de eerste regel een fout: 5.21
moet 5.22 zijn); inleverdatum 21 mei
Opgave 5.15: de minimale kosten zijn 33.
Opgave 5.18: de minimale kosten zijn 9300 euro
Opgave 5.22: de optimale strategie is
om altijd
door te spelen (als dat is toegestaan), behalve als vraag 4 goed is
beantwoord en in de vragen 1 t/m 3 een fout is gemaakt.
Serie 9: opgaven 6.1 (oude en nieuwe druk); inleverdatum 4 juni
Opgave 6.1: optimale bestelgrootte is 216.
Stof schriftelijk tentamen (open boek)
Hoofdstuk 1:
- Formuleringen (algemeen, met absolute waarden)
- Simplex methode
- Dualiteit en interpretatie
- Gevoeligheidsanalyse
Hoofdstuk 2:
- Formuleringen met geheeltallige en binaire variabelen
- Branch-and-bound methode
- Heuristieken voor handelsreizigersprobleem
- Clarke en Wright heuristiek voor routeringsprobleem
Hoofdstuk 3:
- Kortste pad probleem: model + methode Dijkstra + meest betrouwbare
pad
- Maximale stromen: model + algoritme + minimale snede
- Minimale opspannende boom: model + methode Prim + minmax probleem
- Projectmanagement: CPM en PERT
- Minimale-kosten stroomprobleem: model + Hongaarse methode voor
toewijzingsprobleem
Hoofdstuk 5:
- De techniek van de dynamische programmering (toestand definitie en
opstellen
recursie) kennen, zowel voor deterministische als stochastische
problemen
- Recursie door kunnen rekenen en daarna optimale strategie bepalen
- Toepassen van deze techniek, bijv. op kortste pad problemen,
knapzakproblemen
en optimale stopproblemen
Hoofdstuk 6:
- Determistische voorraadmodellen: EOQ- en EPQ-model (geen
kwantumkorting en
afwegingskromme)
- Silver-Meal heuristiek
- Krantenjongenprobleem voor discrte kansverdeling
Oefententamen
Hier treft u een oefententamen
Vragen
Indien u vragen heeft kunt u deze stellen:
- telefonisch 071 - 5277130
- per e-mail kallenberg@math.leidenuniv.nl