Omschrijving
Vele problemen in de wiskunde en in de praktijk kunnen worden gemodelleerd als optimaliseringsproblemen. Onderwerpen die aan bod komen in dit vak zijn:
Inleiding optimalisering, convexiteit.
Modelleren.
Lineair optimaliseren: Simplexmethode, dualiteit.
Primaal-duaal algrotime.
Netwerkoptimalisering: kortste pad, max flow, bomen, matroiden.
Geheeltallig programmeren: Totaal unimodulaire matrices, Branch-and-bound, Gomorysneden.
Analyse van algoritmen en complexiteit.
Benaderingsalgoritmen.
Tentaminering
Er is een deeltentamen en een eindtentamen.
Het eindcijfer word als volgt bepaald:
0.3 x deeltentamencijfer + 0.7 x eindtentamencijfer
Onder de voorwaarde dat het eindtentamencijfer tenminste 5.0 is. Anders telt het eindtentamencijfer als eindcijfer.
Het deeltentamencijfer blijft geldig gedurende het lopend academisch jaar.
Verplichte literatuur
Christos H. Papadimitriou, Kenneth Steiglitz. “Combinatorial Optimization: Algorithms and Complexity. Dover Publications, Inc. Mineola, NY, 1998. Paperback. Dit boek is niet verplicht, maar wordt wel aanbevolen.
Vakcode TUD
TW2020
Voorkennis
Lineaire Algebra 1, Analyse 2
Onderwijsvorm
Hoorcollege, werkcollege en huiswerkopgaven
Contacturen
4 uur per week