Discrete optimalisering

Vakcode:WIDO04
Studiepunten:5.72 ECTS (=4 oude studiepunten)
Periode:periode 4 (week 11 t/m 18, dwz 10-3-2003 t/m 2-5-2003; herkansing week 28)
Deelnemers:tot nu toe 21 inschrijvingen
Rooster:Dit is een oud rooster!
vormgroeptijdweekzaaldocent
college   di 13-1511-17 BBL-430 Marjan van den Akker
  
vr 13-1511-15, 17 BBL-430
werkcollege   ma 11-1312-16 BBL-508
do 13-1511-17 BBL-508
Inhoud:Veel problemen binnen bijvoorbeeld produktie- en distributielogistiek en netwerkontwerp kunnen geformuleerd worden als discrete optimaliseringsproblemen. In een netwerkontwerp-probleem is een mogelijke vraagstelling: "hoe moet een telecommunicatienetwerk ontworpen worden zodanig dat het netwerk niet te gevoelig is voor kabelbreuk, en zodanig dat de som van de kosten voor het aanleggen van het netwerk en de gespreksrouteringskosten minimaal zijn".

Geïnspireerd door een aantal toepassingen uit de gebieden logistiek en netwerkontwerp wordt een aantal modellen van optimaliseringsproblemen besproken. De vraag hierbij is steeds om een oplossing te vinden die aan de gegeven voorwaarden voldoet en waarvoor de kosten minimaal zijn. We bestuderen hierbij lineaire programmering en geheeltallig lineaire programmering. Basisalgoritmen zoals de simplex methode, branch-and-bound, dynamisch programmeren en local search worden beschreven, en voorbeelden van benaderingsalgoritmen met prestatiegaranties worden gegeven.

Wij leren onderscheid te maken tussen 'gemakkelijke' en 'moeilijke' problemen en laten zien hoe de structuur van een probleem gebruikt kan worden bij het ontwerpen van algoritmen om het probleem op te lossen.

Literatuur:Notes bschikbaar via de webpagina.

Bij de eerste 7 colleges is het boek M.S. Bazaraa, J.J. Jarvis, H.D. Sherali: Linear programming and network flows. (uitgeverij Wiley) een nuttig naslagwerk. De stof komt uit de hoofdstukken 1, 3, 4 en 6.

Werkvorm:Hoorcollege, werkcollege en een project.
Toetsvorm:Tentamen, inleveropgaven, en verslag van het project.
Inspanningsverplichting voor aanvullende toets:Om aan de aanvullende toets te mogen meedoen is ontbreken van ten hoogte 1 toetsactiviteit toegestaan.
wijzigen?