|
Bij dit vak draait het om modelleren en
optimaliseren. In allerlei (productie)situaties spelen optimaliseringsproblemen
een rol, waarbij niet alleen een oplossing moet worden gevonden, maar bij
voorkeur zelfs de beste. Voorbeelden hiervan zijn dieetproblemen,
mengproblemen, maar ook het zogenaamde glassnijprobleem,
waarbij uit zo min mogelijk glasplaten van standaard formaat (6.00 x 3.21) de bestelde ruiten (van willekeurige afmetingen) moeten
worden gesneden.
De hoofdmoot van het vak wordt gevormd door
lineaire programmering. Verder wordt nog behandeld hoe je geheeltallige
lineaire programmeringsproblemen op kunt lossen en er
wordt kort behandeld hoe de techniek van `local
search' werkt. In grote lijnen zal het college er als volgt uit gaan zien
- Behandeling van de
techniek van local search. Een van de twee
opdrachten die jullie krijgen (dit is de grootste van de
twee) betreft het vinden van een zo goed mogelijke oplossing voor een
instantie van het bepalen van een zo goed mogelijk cyclisch
dienstroosters voor de chauffeurs van Connexxion.
Gegeven zijn een aantal (zeg n) chauffeurs, die
met z'n allen een gegeven verzameling diensten moeten verzorgen. Jullie
moeten een schema opstellen dat bestaat uit n weekroosters, met een
ordening erbij. De weekroosters rouleren onder de chauffeurs; na afloop
van de week krijgt een chauffeur het volgende
weekrooster op de lijst. Het doel is zoveel mogelijk de wensen van de
chauffeurs te honoreren, waarbij je natuurlijk moet voldoen aan de CAO-eisen (en iedere dienst moet worden bezet). Voor
deze opdracht wordt een echte praktijkinstantie gebruikt: `match your skills with the masters'.
- Inleiding Lineaire
Algebra (vooral het rekenen met matrices). Hierna is een ieder die geen
Lineaire Algebra heeft gehad voldoende voorbereid op hetgeen
er gaat komen; het is dus niet nodig om Lineaire Algebra dan wel Graphics nieuwe stijl gevolgd te hebben.
- Formuleren van een
probleem als een (geheeltallig) lineair programmeringsprobleem, zodat je het door een solver
(zoals CPLEX) op kunt laten lossen. Hier krijgen jullie een opdracht over.
- Behandeling van een
simpele versie van het Simplex algoritme, dat wordt gebruikt om lineaire programmeringsproblemen op te lossen.
- Dualiteit en
gevoeligheidsanalyse. Hierbij gaat het erom dat je een indruk krijgt hoe
de oplossing van een probleem gaat veranderen wanneer je het probleem
enigszins verandert, zonder natuurlijk het aangepaste probleem weer van
`scratch' op te hoeven lossen. Dit wordt geillustreerd
met een praktijktoepassing: afstudeeronderzoek `Online capacity
planning of repairs'.
- Twee efficientere implementaties van de
simplex methode en de methode van kolomgeneratie.
- Het oplossen van geheeltallige lineaire programmeringsproblemen
met behulp van branch-and-bound.
- Twee
praktijktoepassingen: het `gate-assignment'
probleem en het `seriegrootte' probleem. Het eerste
probleem speelt op Schiphol: de binnenkomende en vertrekkende vliegtuigen
hebben een gate nodig; de vraag is natuurlijk
welke. Een probleem hierbij is dat de werkelijke aankomst- en
vertrektijden van vliegtuigen vaak een beetje van de planning afwijken, en
je wilt dan natuurlijk zo min mogelijk aan je huidige oplossing
veranderen. Het tweede probleem komt van Grolsch, en het gaat hier om de
vraag hoeveel je van een bepaald product moet produceren en wanneer, zodat
je uit voorraad kunt leveren zonder dat de voorraden uit het magazijn
puilen.
http://www.cs.uu.nl/education/vak/opt
|
|
|