- De student weet bepaalde problemen te modelleren als lineaire programmeringsproblemen.
- De student doorgrondt de simplexmethode en kan deze toepassen.
- De student kan het duale lineair programmeringsprobleem opstellen, heeft kennis van de dualiteitsstelling en kan hieruit conclusies trekken.
- De student is bekend met variaties van en alternatieven voor de simplexmethode.
|
|
Een belangrijk onderwerp van Operations Research zijn economische optimalisatieproblemen zoals machineplanning, transportproblemen, dienstregeling bij het openbaar vervoer, inrichting van communicatienetwerken etc. In veel gevallen laten deze problemen zich formuleren als het optimaliseren van een lineaire functie onder randvoorwaarden die gegeven zijn door een aantal lineaire vergelijkingen en/of ongelijkheden. Dit soort problemen noemt men lineaire programmeringsproblemen en het oplossen hiervan werd voor grootschalige problemen pas haalbaar door de 1947 door G.B. Dantzig voorgestelde simplex methode.
We zullen in deze cursus bekijken hoe zich uiteenlopende problemen als lineaire programmeringsproblemen laten formuleren. Naast economische optimalisatieproblemen zijn dit ook vraagstukken uit de speltheorie of grafentheorie. Een centraal onderwerp is de simplex methode voor het oplossen van lineaire programmeringsproblemen, hiervan zullen we zowel theoretische als praktische aspecten voor het voetlicht brengen. Een belangrijk hulpmiddel - zowel voor theoretische als praktische doeleinden - is het bij een gegeven probleem behorende duale probleem en we zullen zien hoe we uit de combinatie van het originele en het duale probleem conclusies kunnen trekken.
In de praktijk is de toepassing van de simplex methode zeer efficient, alhoewel de complexiteit in principe exponentieel met het aantal variabelen groeit. Het is mogelijk voorbeelden de construeren waarop de simplex methode zlecht presteert (ook al zijn die enigszins kunstmatig), daarom is het interessant naar alternatieven voor de simplex methode te kijken. Zo'n alternatief is de inwendige punten methode die we aan het einde van de cursus zullen toelichten.
Werkvormen
|
|
|
|
Calculus A, Calculus B, Lineaire Algebra A, Lineaire Algebra B |
|
Schriftelijk tentamen en huiswerkopdrachten
|
|
De cursus wordt in het jaar 2021-2022 niet aangeboden.
|
|