Optimalisering

TU Delft  / Universiteit Leiden
2016


Mededelingen

Het tentamen is nagekeken en de eindcijfers doorgegeven. Hier zijn de resultaten. Inzien kan op afspraak (bij een docent van je eigen universiteit).


Onderwijsvormen

Het vak bestaat uit hoorcolleges, werkcolleges, opgaven, feedbackopgaven, deeltentamen en eindtentamen.


Locaties en tijden

Hoorcolleges: woensdag 13:45 – 15:30 in Leiden in het Gorlaeus Laboratorium (de disk) afwisselend in zalen C1, C2 of C3, zie de roosters.

Werkcolleges in Leiden: vrijdag 9:00 – 10:45 in zaal 312.

Werkcolleges in Delft: vrijdag 10:45 – 12:30 in zalen H en Pi. Vanaf 18 november van 8:45 tot 10:30.


Feedbackopgaven

Elke week worden opgaven opgegeven die gedeeltelijk tijdens de werkcolleges en gedeeltelijk thuis gemaakt kunnen worden. Elke week wordt één opgave geselecteerd als feedbackopgave. Deze opgave kun je inleveren en wordt dan nagekeken. Je krijgt geen cijfer voor de feedbackopgaven; ze zijn bedoeld om te leren van de feedback. De andere opgaven kunnen niet worden ingeleverd, maar je kunt tijdens de werkcolleges wel om feedback vragen. Voor een goede voorbereiding op het tentamen is het belangrijk om alle opgaven gemaakt te hebben.

Lever je uitwerking van de feedbackopgave in aan het eind van het werkcollege. Als je niet bij het werkcollege aanwezig kunt zijn, of de feedbackopgave niet af krijgt, dan kun je de opgave later inleveren in het postvakje van één van de werkcollegedocenten. Dit kan tot vertraging leiden bij het nakijken.


Cijfers

Het eindcijfer wordt bepaald op basis van het deeltentamen en het eindtentamen. Het eindcijfer wordt als volgt bepaald:

eindcijfer = 0.3 x deeltentamencijfer + 0.7 x eindtentamencijfer

onder de voorwaarde dat het eindtentamencijfer tenminste 5.0 is (anders telt het eindtentamencijfer als eindcijfer).

Indien het hertentamen gemaakt wordt dan geldt het maximum van het hertentamencijfer en het gewogen gemiddelde (0.3 x deeltententamencijfer + 0.7 x hertentamencijfer), wederom onder de voorwaarde dat het hertentamencijfer tenminste 5.0 is.

Het eindtentamen gaat over alle stof.


Docenten

Leo van Iersel: hoorcolleges

Theresia van Essen: werkcolleges Delft

Teun Janssen: werkcolleges Delft


Studentassistenten

Khadija Lachhab (khadijaa_ at live.nl): werkcolleges Leiden

Thomas van Hees (tvanhees at outlook.com): werkcolleges Leiden

Cynthia Slotboom: werkcolleges Delft

Sander Borst: nakijken feedbackopgaven

Judith Leijenhorst: nakijken feedbackopgaven

Neem voor vragen bij voorkeur contact op met één van de docenten.


Studiemateriaal

Dictaat voor week 1: Karen Aardal. Modelling linear and linear integer optimization problems – An introduction

Boek (niet verplicht): Christos H. Papadimitriou, Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Dover Publications, Inc., Mineola, NY, 1998.

Extra materiaal (slides en opgaven) worden hieronder per week beschikbaar gemaakt.

De slides, collegeaantekeningen en het dictaat bevatten samen alle leerstof van het vak (het is dus niet noodzakelijk om het boek te hebben).

Geselecteerde uitwerkingen.

Let op: tijdens de colleges worden bewijzen en voorbeelden vaak op het bord uitgewerkt. Om het vak te leren heb je hier aantekeningen van nodig!

Let op: van de meeste opgaven komen geen uitwerkingen op de website! Het is daarom belangrijk om de werkcolleges te volgen zodat je vragen kunt stellen over de opgaven waar je zelf niet uit komt.


Week 1

Introductie. Modelleren van praktijkproblemen als LP en ILP problemen. DictaatSlidesOpgaven.

Week 2

LP in standaard vorm, basisoplossing, polyeders en polytopen. SlidesOpgaven

Week 3

Oplossen van LP problemen met het Simplexalgoritme. Slides (met aantekeningen), Opgaven

Week 4

Dualiteit. Slides (met aantekeningen), Opgaven

Week 5

Geen college

Week 6

Farkas’ Lemma, Complementary slackness, duale simplex methode. Slides (met aantekeningen), Opgaven

Week 7

Max flow, min cut en kortste paden. Slides (met aantekeningen), Opgaven

Week 8

Analyse van algoritmes. SlidesOpgaven

Week 9

Opspannende bomen. SlidesOpgaven

Week 10

Deeltentamen over de stof van week 1 – 8

Week 11

Geheeltallige optimalisering, totale unimodulariteit. SlidesOpgaven

Week 12

Oplossen van geheeltallige optimaliseringsproblemen met Branch-and-bound (B&B) en cutting planes. SlidesOpgaven

Week 13

Complexiteitstheorie, NP-volledigheid. SlidesOpgaven

Week 14

Benaderingsalgoritmen. SlidesOpgaven

Week 15

Vragenuurtje. Slides


Oude tentamens


Links


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s