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
Schriftelijk tentamen plus huiswerkopgaven van 1-2 studenten en schriftelijk eindtentamen. Het eindcijfer wordt als volgt bepaald:
max{0.2 x huiswerkcijfer + 0.25 x deeltentamencijfer + 0.55 x eindtentamencijfer, eindtentamencijfer}.
Het eindcijfer moet tenminste 6 (afgerond) zijn, en het eindtentamencijfer moet tenminste 5,5 zijn.
Het huiswerkcijfer en het deeltentamencijfer blijven 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.
Vakcode TUD
TW2020
Voorkennis
Lineaire Algebra 1, Analyse 2
Onderwijsvorm
Hoorcollege/oefeningen + huiswerk in groepen van 2 studenten.
Contacturen
4 uur per week