BASISMODELLEN UIT OPERATIONEEL
ONDERZOEK
Inhoud
H1: inleiding op LP...................................................................................................................... 2
Wat is een LP probleem?......................................................................................................... 2
Grafische oplossing van een maximaliseringsprobleem met 2 variabelen..............................3
Grafische oplossing van een minimaliseringsprobleem met 2 variabelen...............................4
Speciale gevallen.................................................................................................................... 4
H2: Procedureel oplossen van LP problemen: Het simplex algoritme.........................................5
LP probleem omzetten in standaardformaat...........................................................................5
Inleiding op het simplex algoritme.......................................................................................... 5
Elk LP met een optimale oplossing heeft een optimale BFS....................................................6
Simplex algoritme:.................................................................................................................. 6
Simplex algoritme bij minimaliseringsprobleem......................................................................7
Een inleiding op de M-techniek = penaliseringsmethode........................................................7
Een inleiding op Goal Programming........................................................................................ 8
Pre-emptive goal programming............................................................................................... 8
H3: Gevoeligheidsanalyse.......................................................................................................... 8
Een grafische inleiding op gevoeligheidsanalyse....................................................................8
Gevoeligheidsanalyse op de computer................................................................................. 10
Management-toepassingen van schaduwprijzen...................................................................11
Een inleiding op dualiteit in LP.............................................................................................. 12
H4 : Niet-lineaire programmering............................................................................................. 12
Inleidende concepten............................................................................................................ 12
Convexe en concave functies................................................................................................ 13
NLP met 1 variabele.............................................................................................................. 14
Lagrange Multiplicatoren....................................................................................................... 15
Kuhn-Tucker voorwaarden.................................................................................................... 16
Kwadratische programmering............................................................................................... 18
H5: Transport-, toewijzings- en transitoproblemen...................................................................19
Transportproblemen.............................................................................................................. 19
Evenwichtige problemen:................................................................................................... 20
Voorraadproblemen........................................................................................................... 21
Toewijzingsproblemen........................................................................................................... 21
Hongaarse methode........................................................................................................... 22
1
, Transitoproblemen................................................................................................................ 23
H6 : Netwerkmodellen.............................................................................................................. 23
Elementaire begrippen.......................................................................................................... 23
Kortste-pad-problemen (‘shortest-path problems’)...............................................................24
Maximale-stroom-problemen (‘maximum-flow problems’)....................................................24
Kritieke-pad-methode (‘critical path method: CPM)..............................................................25
1e methode : elementaire concepten................................................................................. 25
2e methode : via LP............................................................................................................ 27
Minimaal-opspannende-boom-probleem (‘minimum spanning tree problems’)....................27
H7 : Geheeltallige programmering........................................................................................... 28
Een inleiding op geheeltallige programmering......................................................................28
Formulering van geheeltallige programmeringsproblemen..................................................29
De branch-en-bound methode.............................................................................................. 31
H1: INLEIDING OP LP
Operationeel onderzoek = wiskundige ondersteuning voor beslissingen bij praktijkproblemen
-> gebonden optimalisering en ongebonden optimalisering
WAT IS EEN LP PROBLEEM?
Stap 1: bepaal de beslissingsveranderlijken
Stap 2: formuleer de doelstelling en beperkingen in termen van de
beslissingsveranderlijken
= een optimeringsprobleem waarbij een lineaire doelstelling geoptimaliseerd wordt onder
lineaire beperkingen en waarbij met elke beslissingsveranderlijke al dan niet een
tekenbeperking geassocieerd is
- Doelfunctie met doelfunctiecoëfficiënten
- Beperkingen met technologische coëfficiënten
Voorwaarden die moeten voldaan zijn opdat een LP een realistische voorstelling biedt van het
beslissingsprobleem: => altijd deze 4 verantwoorden!!!
1. Proportionaliteit
= de bijdrage tot de doelfunctie van elke beslissingsvariabele is proportioneel
aan de waarde van de beslissingsvariabele
= de bijdrage van elke beslissingsvariabele tot de linkerzijde van een beperking
is proportioneel tot de waarde van de beslissingsvariabele
=>zowel voor de doelstelling als voor de beperkingen motiveren
Er zijn geen leereffecten, de meerkost of meeropbrengst is constant
2. Additiviteit
= de bijdrage tot de doelfunctie van elke beslissingsvariabele is onafhankelijk
van de waarden van de andere beslissingsvariabelen
Je kan de beslissingsvariabelen apart beschouwen, ze zijn onafhankelijk
= de bijdrage van elke beslissingsvariabele tot de linkerzijde van een beperking
is onafhankelijk van de waarden van de andere beslissingsvariabelen
=> zowel voor de doelstelling als voor de beperkingen motiveren
2
, Bv. geen kruiselingse productie effecten
3. Deelbaarheid
= we werken met continue beslissingsveranderlijken
Vaak niet realistisch, vaak biedt afronding van de optimale oplossing dan een
redelijke oplossing
Bv. het is mogelijk 1,5 soldaten te maken
4. Zekerheid
= alle coëfficiënten zijn gekend met zekerheid
Bv. we kennen de bijdrage tot de doelfunctie
Haalbaarheidsverzameling
= de verzameling van alle punten die voldoen aan de LP-beperkingen en de
tekenbeperkingen
Optimale oplossing
= voor een maximaliseringsprobleem, het punt in de haalbaarheidsverzameling met de
hoogste doelfunctiewaarde
= voor een minimaliseringsprobleem, het punt in de haalbaarheidsverzameling met de
laagste doelfunctiewaarde
Bepalen van de optimale oplossing:
- Grafisch
- Procedureel (simplex,…)
- Software (excell-solver, lindo, lingo,…)
GRAFISCHE OPLOSSING VAN EEN MAXIMALISERINGSPROBLEEM MET 2 VARIABELEN
Voor elke beperking afzonderlijk kunnen we een gebied met haalbare en niet-haalbare punten
onderscheiden
Stap 1: maak van de beperking een rechte
Stap 2: alle punten onder deze rechte zijn haalbaar, alle punten boven deze rechte zijn
niet haalbaar
Haalbare punten voldoen simultaan aan alle beperkingen
Optimum
- We werken met lijnen die alle punten omvatten met een zelfde doelfunctiewaarde
Max probleem: isowinstlijn <-> Min probleem: isokostenlijn
- Zoek dus dat punt in de haalbaarheidsverzameling dat geassocieerd is met de hoogste
isowinstlijn/laagste isokostenlijn
- Begin bij de initiële isowinstlijn -> = 0
Elementaire begrippen
Bindende beperking = de linkerhandzijde en de rechterhandzijde van de beperking zijn
gelijk bij de optimale oplossing
Karakteriseren de optimale oplossing
Niet-bindende beperking = de linkerhandzijde en de rechterhandzijde van de beperking
zijn ongelijk bij de optimale oplossing
Convexe verzameling => een verzameling S is convex als het lijnsegment dat éénder
welk puntenpaar in S verbindt ook volledig tot de verzameling S behoort
3
, De haalbaarheidsverzameling van een LP probleem is steeds een convexe
verzameling!
Extreem punt P = een punt in S dat niet kan gereconstrueerd worden als een convexe
combinatie van 2 andere punten in S
Enkel convexe verzamelingen kunnen extreme punten hebben
Voor een convexe set S, is P een extreem punt als elk lijnsegment dat volledig in
S ligt en het punt P omvat het punt P als eindpunt heeft
Het optimaal punt is ook een extreem punt
Extreme punten = hoekpunten -> het aantal extreme punten is dus eindig
Elk LP-probleem dat een optimale oplossing heeft, heeft een extreem
punt dat optimaal is
GRAFISCHE OPLOSSING VAN EEN MINIMALISERINGSPROBLEEM MET 2 VARIABELEN
Laagste isokostenlijn
Vb. minimale kost berekenen
Haalbaar nu de punten boven de rechte
Ook al zijn de basisveronderstellingen niet realistisch (bv. bij bepalen van optimale
reclamestrategie) => wel een nuttige benadering van de werkelijkheid
SPECIALE GEVALLEN
Voorgaande: een unieke optimale oplossing = standaard geval
1: een oneindig aantal optimale oplossing = alternatieve optimale oplossing
helling isowinstlijn = helling van de beperkingsrechte
G? na verschuiving vallen die twee samen, op het
gemeenschappelijk deel zijn alle optimale
oplossingen gesitueerd
Hier zijn meerdere hoekpunten optimaal, de
eindepunten van het blauwe lijnstuk maar ook alle
convexe punten ertussen => meerdere extreme
punten optimaal en ook alle convexe combinaties
ervan
- Via verdere criteria (secundaire criteria) kan je de punten verder discrimineren
2: geen haalbare oplossingen = een onmogelijk LP probleem
- Heeft een ledige haalbaarheidsverzameling
- Kan nergens aan alle beperkingen simultaan voldaan worden
3: haalbare oplossingen met een oneindig hoge waarde voor de doelfunctie= onbegrensd LP
probleem
= optimale oplossing is niet bepaald, oplossingswaarde is oneindig
- Is niet gelijk aan een onbegrensde
haalbaarheidsverzameling
- Max probleem: haalbare punten die
corresponderen met een oneindig hoge waarde
voor de doelfunctie
4
ONDERZOEK
Inhoud
H1: inleiding op LP...................................................................................................................... 2
Wat is een LP probleem?......................................................................................................... 2
Grafische oplossing van een maximaliseringsprobleem met 2 variabelen..............................3
Grafische oplossing van een minimaliseringsprobleem met 2 variabelen...............................4
Speciale gevallen.................................................................................................................... 4
H2: Procedureel oplossen van LP problemen: Het simplex algoritme.........................................5
LP probleem omzetten in standaardformaat...........................................................................5
Inleiding op het simplex algoritme.......................................................................................... 5
Elk LP met een optimale oplossing heeft een optimale BFS....................................................6
Simplex algoritme:.................................................................................................................. 6
Simplex algoritme bij minimaliseringsprobleem......................................................................7
Een inleiding op de M-techniek = penaliseringsmethode........................................................7
Een inleiding op Goal Programming........................................................................................ 8
Pre-emptive goal programming............................................................................................... 8
H3: Gevoeligheidsanalyse.......................................................................................................... 8
Een grafische inleiding op gevoeligheidsanalyse....................................................................8
Gevoeligheidsanalyse op de computer................................................................................. 10
Management-toepassingen van schaduwprijzen...................................................................11
Een inleiding op dualiteit in LP.............................................................................................. 12
H4 : Niet-lineaire programmering............................................................................................. 12
Inleidende concepten............................................................................................................ 12
Convexe en concave functies................................................................................................ 13
NLP met 1 variabele.............................................................................................................. 14
Lagrange Multiplicatoren....................................................................................................... 15
Kuhn-Tucker voorwaarden.................................................................................................... 16
Kwadratische programmering............................................................................................... 18
H5: Transport-, toewijzings- en transitoproblemen...................................................................19
Transportproblemen.............................................................................................................. 19
Evenwichtige problemen:................................................................................................... 20
Voorraadproblemen........................................................................................................... 21
Toewijzingsproblemen........................................................................................................... 21
Hongaarse methode........................................................................................................... 22
1
, Transitoproblemen................................................................................................................ 23
H6 : Netwerkmodellen.............................................................................................................. 23
Elementaire begrippen.......................................................................................................... 23
Kortste-pad-problemen (‘shortest-path problems’)...............................................................24
Maximale-stroom-problemen (‘maximum-flow problems’)....................................................24
Kritieke-pad-methode (‘critical path method: CPM)..............................................................25
1e methode : elementaire concepten................................................................................. 25
2e methode : via LP............................................................................................................ 27
Minimaal-opspannende-boom-probleem (‘minimum spanning tree problems’)....................27
H7 : Geheeltallige programmering........................................................................................... 28
Een inleiding op geheeltallige programmering......................................................................28
Formulering van geheeltallige programmeringsproblemen..................................................29
De branch-en-bound methode.............................................................................................. 31
H1: INLEIDING OP LP
Operationeel onderzoek = wiskundige ondersteuning voor beslissingen bij praktijkproblemen
-> gebonden optimalisering en ongebonden optimalisering
WAT IS EEN LP PROBLEEM?
Stap 1: bepaal de beslissingsveranderlijken
Stap 2: formuleer de doelstelling en beperkingen in termen van de
beslissingsveranderlijken
= een optimeringsprobleem waarbij een lineaire doelstelling geoptimaliseerd wordt onder
lineaire beperkingen en waarbij met elke beslissingsveranderlijke al dan niet een
tekenbeperking geassocieerd is
- Doelfunctie met doelfunctiecoëfficiënten
- Beperkingen met technologische coëfficiënten
Voorwaarden die moeten voldaan zijn opdat een LP een realistische voorstelling biedt van het
beslissingsprobleem: => altijd deze 4 verantwoorden!!!
1. Proportionaliteit
= de bijdrage tot de doelfunctie van elke beslissingsvariabele is proportioneel
aan de waarde van de beslissingsvariabele
= de bijdrage van elke beslissingsvariabele tot de linkerzijde van een beperking
is proportioneel tot de waarde van de beslissingsvariabele
=>zowel voor de doelstelling als voor de beperkingen motiveren
Er zijn geen leereffecten, de meerkost of meeropbrengst is constant
2. Additiviteit
= de bijdrage tot de doelfunctie van elke beslissingsvariabele is onafhankelijk
van de waarden van de andere beslissingsvariabelen
Je kan de beslissingsvariabelen apart beschouwen, ze zijn onafhankelijk
= de bijdrage van elke beslissingsvariabele tot de linkerzijde van een beperking
is onafhankelijk van de waarden van de andere beslissingsvariabelen
=> zowel voor de doelstelling als voor de beperkingen motiveren
2
, Bv. geen kruiselingse productie effecten
3. Deelbaarheid
= we werken met continue beslissingsveranderlijken
Vaak niet realistisch, vaak biedt afronding van de optimale oplossing dan een
redelijke oplossing
Bv. het is mogelijk 1,5 soldaten te maken
4. Zekerheid
= alle coëfficiënten zijn gekend met zekerheid
Bv. we kennen de bijdrage tot de doelfunctie
Haalbaarheidsverzameling
= de verzameling van alle punten die voldoen aan de LP-beperkingen en de
tekenbeperkingen
Optimale oplossing
= voor een maximaliseringsprobleem, het punt in de haalbaarheidsverzameling met de
hoogste doelfunctiewaarde
= voor een minimaliseringsprobleem, het punt in de haalbaarheidsverzameling met de
laagste doelfunctiewaarde
Bepalen van de optimale oplossing:
- Grafisch
- Procedureel (simplex,…)
- Software (excell-solver, lindo, lingo,…)
GRAFISCHE OPLOSSING VAN EEN MAXIMALISERINGSPROBLEEM MET 2 VARIABELEN
Voor elke beperking afzonderlijk kunnen we een gebied met haalbare en niet-haalbare punten
onderscheiden
Stap 1: maak van de beperking een rechte
Stap 2: alle punten onder deze rechte zijn haalbaar, alle punten boven deze rechte zijn
niet haalbaar
Haalbare punten voldoen simultaan aan alle beperkingen
Optimum
- We werken met lijnen die alle punten omvatten met een zelfde doelfunctiewaarde
Max probleem: isowinstlijn <-> Min probleem: isokostenlijn
- Zoek dus dat punt in de haalbaarheidsverzameling dat geassocieerd is met de hoogste
isowinstlijn/laagste isokostenlijn
- Begin bij de initiële isowinstlijn -> = 0
Elementaire begrippen
Bindende beperking = de linkerhandzijde en de rechterhandzijde van de beperking zijn
gelijk bij de optimale oplossing
Karakteriseren de optimale oplossing
Niet-bindende beperking = de linkerhandzijde en de rechterhandzijde van de beperking
zijn ongelijk bij de optimale oplossing
Convexe verzameling => een verzameling S is convex als het lijnsegment dat éénder
welk puntenpaar in S verbindt ook volledig tot de verzameling S behoort
3
, De haalbaarheidsverzameling van een LP probleem is steeds een convexe
verzameling!
Extreem punt P = een punt in S dat niet kan gereconstrueerd worden als een convexe
combinatie van 2 andere punten in S
Enkel convexe verzamelingen kunnen extreme punten hebben
Voor een convexe set S, is P een extreem punt als elk lijnsegment dat volledig in
S ligt en het punt P omvat het punt P als eindpunt heeft
Het optimaal punt is ook een extreem punt
Extreme punten = hoekpunten -> het aantal extreme punten is dus eindig
Elk LP-probleem dat een optimale oplossing heeft, heeft een extreem
punt dat optimaal is
GRAFISCHE OPLOSSING VAN EEN MINIMALISERINGSPROBLEEM MET 2 VARIABELEN
Laagste isokostenlijn
Vb. minimale kost berekenen
Haalbaar nu de punten boven de rechte
Ook al zijn de basisveronderstellingen niet realistisch (bv. bij bepalen van optimale
reclamestrategie) => wel een nuttige benadering van de werkelijkheid
SPECIALE GEVALLEN
Voorgaande: een unieke optimale oplossing = standaard geval
1: een oneindig aantal optimale oplossing = alternatieve optimale oplossing
helling isowinstlijn = helling van de beperkingsrechte
G? na verschuiving vallen die twee samen, op het
gemeenschappelijk deel zijn alle optimale
oplossingen gesitueerd
Hier zijn meerdere hoekpunten optimaal, de
eindepunten van het blauwe lijnstuk maar ook alle
convexe punten ertussen => meerdere extreme
punten optimaal en ook alle convexe combinaties
ervan
- Via verdere criteria (secundaire criteria) kan je de punten verder discrimineren
2: geen haalbare oplossingen = een onmogelijk LP probleem
- Heeft een ledige haalbaarheidsverzameling
- Kan nergens aan alle beperkingen simultaan voldaan worden
3: haalbare oplossingen met een oneindig hoge waarde voor de doelfunctie= onbegrensd LP
probleem
= optimale oplossing is niet bepaald, oplossingswaarde is oneindig
- Is niet gelijk aan een onbegrensde
haalbaarheidsverzameling
- Max probleem: haalbare punten die
corresponderen met een oneindig hoge waarde
voor de doelfunctie
4
