SluitenHelpPrint
Switch to English
Cursus: INFOOPT
INFOOPT
Optimalisering en complexiteit
Cursus informatieRooster
CursuscodeINFOOPT
Studiepunten (ECTS)7,5
Categorie / Niveau3 (Bachelor Gevorderd)
CursustypeCursorisch onderwijs
VoertaalNederlands
Aangeboden doorFaculteit Betawetenschappen; Undergraduate School Bètawetenschappen;
Contactpersoondr. J.A. Hoogeveen
Telefoon+31 30 2534089
E-mailJ.A.Hoogeveen@uu.nl
Docenten
Docent
dr. ir. J.M. van den Akker
Feedback en bereikbaarheid
Overige cursussen docent
Docent
dr. J.A. Hoogeveen
Feedback en bereikbaarheid
Overige cursussen docent
Blok
2  (12-11-2012 t/m 01-02-2013)
Aanvangsblok
2
TimeslotA: MA-ochtend, DI-namiddag, WO-ochtend
Onderwijsvorm
Voltijd
Cursusinschrijving geopendvanaf 04-06-2012 t/m 16-11-2012
AanmeldingsprocedureOsiris
Inschrijven via OSIRISJa
Inschrijven voor bijvakkersJa
VoorinschrijvingNee
WachtlijstNee
Plaatsingsprocedureadministratie onderwijsinstituut
Cursusdoelen
-
Inhoud

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.php?stijl=2&vak=INFOOPT

 

 

Ingangseisen
Verplicht materiaal
-
Aanbevolen materiaal
Boek
M.S. Bazaraa, J.J. Jarvis, H.D. Sherali (1990). Linear programming and network flows. Wiley, New York. ISBN: 0-471-48599-3, of 0-471-51284-2 of 0-471-63681-9. Het wordt hoofdzakelijk als naslagwerk gebruikt.
Werkvormen (aanwezigheidsplicht)
Hoorcollege

Werkcollege

Toetsen
Tentamen
Weging100
Minimum cijfer6

Beoordeling
Tentamen plus practicumopgave. Tentamen telt voor 60%; de modelleeropgave telt voor 10%; het local search practicum voor 30%. Op beide opdrachten moet minstens een 6.0 worden gescoord; op het tentamen moet minstens een 5.0 worden gescoord. In verband met de BaMa wordt de houdbaarheid van de deelresultaten beperkt; wie al een onderdeel heeft gehaald wordt verzocht dit jaar toch vooral de resterende onderdelen van het vak te gaan halen.

SluitenHelpPrint
Switch to English