2DD15: Optimalisering

Algemene informatie is te vinden op OWinfo.
Collegestof en opgaven.
Tentamenstof.
Oude tentamens.

Deze webpagina in PDF formaat.

LET OP: Dit jaar is er GEEN open-boek tentamen!

Dit vak is bedoeld als inleiding in de mathematische modellering van Optimaliseringsproblemen en met name Lineaire Optimaliseringsproblemen. De nadruk ligt in dit college op de oplossingsmethoden en dus niet op de modellering. Het doel is dat de student aan het eind van het college doorheeft welk soort problemen in principe opgelost kunnen worden, hetgeen zeer belangrijk is bij het formuleren van praktijkproblemen. Het heeft geen zin om een model voor een praktijkprobleem op te stellen dat toch niet opgelost kan worden. De student wordt tijdens dit college dus bekend gemaakt met oplossingsmethoden voor met name lineaire optimaliseringsproblemen. Daarnaast zal ook aandacht geschonken worden aan problemen waarbij onoverkomelijk oplossingen geheeltallig moeten zijn.

Lineaire programmering: het modelleren en oplossen van een verbaal omschreven probleem in termen van oplossingen van een stelsel van lineaire vergelijkingen met de beste waarde. De simplex-methode borduurt voort op het oplossen van stelsels vergelijkingen. Verschil met lineaire algebra is dat er ook onder- en bovengrenzen op variabelen worden gegeven, en dat men van alle oplossingen de "beste" wil hebben. Een extra moeilijke variant is die waarbij sommige van de variabelen geheeltallige waarden moeten aannemen. Doel van dit onderdeel is het herkennen dat een verbaal omschreven probleem een LP-probleem is, het kennen van de simplex-methode om deze op te lossen, de antwoorden te interpreteren en op basis van gevoeligheidsanalyse conclusies voor het onderliggende probleem en zijn oplossing te trekken. De oplossingsmethode is beschikbaar in computerpakketten zoals Excel-Solver (voor studie problemen) of CPLEX (voor grote praktijkproblemen). Voor de stof van dit college worden gebruikt:

Boek: F.S. Hillier, G.J. Lieberman. Introduction to operations research. McGraw Hill, New York.
Collegeaantekeningen. Aan het einde van de collegeaantekeningen staat wat er verteld is tijdens het desbetreffende college.
Op studyweb staan verder nog collegeaantekeningen van de vorige docent. Deze aantekeningen zijn gedeeltelijk in het Engels en gedeeltelijk in het Nederlands.

Alle opgaven en verwijzingen naar het boek verwijzen naar de 8ste druk. Zie opgaven editie 7 welke opgaven in editie 7 corresponderen met deze opgaven.

· College 1 (26 januari): Het Lineaire Programmerings Probleem

Collegestof

H&L geheel hoofdstuk 3, behalve 3.5.
H&L 4.1, 4.2.

Opgaven

Huiswerk: 3.1-1, 3.2-3, 3.4-11(a,b), 4.6-3, 4.6-14(a).
Instructie: 3.4-8(a), 3.4-14(a), 4.6-13(a,b), 4.6-16(a), 4.7-3(a).

Collegeaantekeningen van College 1, in PDF formaat.

· College 2 (2 februari): De Simplex methode

Collegestof

H&L 4.1 t/m 4.4.
H&L 5.1.

Opgaven

Huiswerk: 4.4-3(a), 4.4-7, 4.4-8, 5.1-9.
Instructie: 4.4-4, 4.5-4, 4.5-8, 4.6-14 (a,b), 5.1-4, 5.1-10, 5.1-11.

Slides van College 2: de Simplex methode. (Tijdens het college stonden een aantal foutjes op de slides. Deze heb ik verbeterd. Indien je nog steeds fouten tegenkomt, hoor ik het graag.)

· College 3 (9 februari): De Simplex methode (vervolg) en Dualiteit

Collegestof

H&L 4.6.
H&L 6.1.

Opgaven

Huiswerk: 4.6-6, 4.6-7, 6.1-3, 6.1-5, 6.1-7.
Instructie: 4.5-8, 4.6-9(a,b), 4.6-16(a,b,c), 6.1-4.

Slides van College 3: vervolg Simplex methode en Dualiteit.

· College 4 (16 februari): Dualiteit

Collegestof

H&L 6.1, 6.3, 6.4.

Opgaven

Huiswerk: 5.3-1, 5.3-2, 6.3-1.
Instructie: 5.2-1, 5.3-3, 5.3-5, 6.1-14, 6.3-6, 6.4-2.

Slides van College 4: vervolg Dualiteit en gevoeligheidsanalyse (zal deze slides verbeteren).

· Colleges 5 (16 maart): Gevoeligheidsanalyse

Collegestof

H&L geheel hoofdstuk 6.

Opgaven

Huiswerk: 6.6-1, 6.7-1 (onderdeel (i) niet), 6.7-2, 6.7-11.
Instructie: 6.7-3, 6.7-5 (onderdeel (g) niet), 6.7-16.

Collegeaantekeningen van Colleges 5, in PDF formaat. Slides gevoeligheidsanalyse.

· Colleges 6 (23 maart): Modelleren met geheeltallig lineair programmeren

Collegestof

H&L 11.1 t/m 11.4.

Opgaven

o Huiswerk: 11.1-1, 11.3-1, 11.3-2, 11.5-2.

o Instructie: 11.1-2, 11.3-3, 11.4-2.

· Collegeaantekeningen van Colleges 6, in PDF formaat.

· Colleges 7 (30 maart): Geheeltallig Lineair Programmeren (Branch-and-Bound)

Collegestof

H&L 11.5 t/m 11.7.

Opgaven

o Huiswerk: 11.6-2, 11.7-7.

o Instructie: 11.6-1, 11.6-6, 11.7-8.

· Slides van College 7: Branch-and-Bound.

· College 8 (6 april): Dynamisch Programmeren

· Collegestof

o H&L 10.1 t/m 10.3 pagina 457.

· Opgaven

o Huiswerk: 10.2-2, 10.3-1, 10.3-3.

o Instructie: 10.2-4, 10.3-2, 10.3-7.

Slides van College8: Dynamisch programmeren.

Oude tentamens

Tentamen 18 juni 2008 met uitwerkingen in PDF formaat.
Tentamen 28 april 2008 met uitwerkingen in PDF formaat.
Tentamen 9 juli 2007 met uitwerkingen in PDF formaat.
Tentamen 11 mei 2007 met uitwerkingen in PDF formaat.
Tentamen 28 juni 2006 met uitwerkingen in PDF formaat.
Tentamen 10 mei 2006 met uitwerkingen in PDF formaat.

Terug naar boven.

Tentamenstof en voorwaarden

LET GOED OP: DIT JAAR WORDT HET TENTAMEN GEEN OPEN BOEK TENTAMEN!!! Er mogen dus alleen schrijfwaren meegenomen worden naar het tentamen! Ook geen zakrekenmachines!

Een generieke inhoudsopgave van mogelijke tentamenvragen luidt:

het vertalen van een woordelijke omschrijving van een praktijkprobleem in een LP-formulering;
het toepassen van de Big-M en de 2-fasen methoden voor het vinden van een startoplossing;
het interpreteren van een tussentableau, en het aangeven van een simplex-iteratie;
het dualiseren van een gegeven LP-probleem en het vinden van informatie over de optimale oplossing van het duale probleem;
het interpreteren in termen van gevoeligheidsanalyse van een eindtableau;
modelleren met geheeltallige variabelen, zoals enkele van meerdere restricties waar aan voldaan moet worden, stuksgewijs lineaire functies, fixed charge, etc. ;
Branch-and-Bound methode voor 0-1 Geheeltallig Lineair Programmeren;
Branch-and-Bound methode voor (Gemengd) Geheeltallig Lineair Programmeren;
Branch-and-Bound methode voor het Knapzak probleem;
het vertalen van een woordelijke omschrijving van een praktijkprobleem in een dynamisch programmeringsprobleem en het oplossen van het probleem.

Terug naar boven.

Het vak Optimalisering (2DD15) voor de opleiding bedrijfskunde wordt verzorgd door de sectie Combinatorische Optimalisering van de Vakgroep Wiskunde.

Docent is dr. Hein van der Holst, HG.9.31, tel. 2299, email h.v.d.holst@tue.nl. Instructeurs zijn Drs. J.H. Sinkovic email J.Sinkovic@tue.nl, Dr. A.H. Löpker email lopker@eurandom.tue.nl, Drs. M. Firat email m.firat@tue.nl.
College wordt gegeven op maandagochtend, het 3de en 4de uur; Instructies zijn op woensdagmiddag, het 3de en 4de uur.

Deze pagina is opgesteld door Hein van der Holst en laatst aangepast op 9 januari 2009.