Basismodellen uit operationeel onderzoek
Opbouw van de cursus
- Doelstelling van de cursus: wiskundige optimaliseringsproblemen oplossen en analyseren
o Lineaire programmering en de simplexmethode
▪ Hoofdstuk 3, 4 en 5/ deel 1, 2 en 3
o Niet-lineaire programmering
▪ Hoofdstuk 11/ deel 4
o Veel voorkomende typeproblemen
▪ Hoofdstuk 7,8 en 9 / deel 5,6 en 7
Inleiding tot het operationeel onderzoek
1. Inleiding
A. Wat is OR?
- Operationeel onderzoek / operationele research (OR)
o = Een wiskundige ondersteuning voor beslisssingen bij praktijkproblemen
o Onderzoek kan gedaan worden via gebonden of ongebonden
optimalisering
o Voorbeelden:
▪ Productieplanning
▪ Dieet
▪ Samenstelling portfolio
2. Een inleiding op LP
A. Wat is een LP problem?
- Een probleem waarbij
o Een lineaire doesltelling geoptimaliseerd (maximum of minimum) wordt
o Onder lineaire beperkingen (technoligische beperkingen,
vraagbeperkingen)
o En waarbij met elke beslissingvariable een tekenbeperking geassocieerd is
(bv. mag niet negatief zijn)
- Beslssingsvariabelen (⇒ moeten voldaan zijn opdat een LP een realsitisch
voorstelling biedt van het beslissingsprobleem)
1) Proportionaliteit
• De bijdrage tot de doelfunctie (=functie die de optimalisatie
voorsteld) van elke beslissingvariabele is proportyioneel aan de
waarde van de beslissingsvariabele
o bv. De bijdrage van 4 geproduceerde eenheden is 4 keer de
bijdrage van 1 geproduceerd eenheid
, Analoog: de bijdrage van elk beslissingsvariabele van een beperking
•
(technologiscg, vraag,…) is proportioneel tot de waarde van de
beslissingswaarde
2) Additiviteit
• De bijdrage tot de doelfunctie van elke beslissingsvariabele is
onafhankelijk van de andere beslissingsvariabelen
o M.a.w. je kan de beslissingsvariabelen optellen
• Analoog: de bijdrage van elke beslissingsvariabele van een
beperking is onafhankelijk van de waarden van de andere
beslissingsvariabelen
3) Deelbaarheid
• We werken met continue beslissingsveranderlijken
• Probleem: vaak niet realistisch om enkel gehele getallen uit te
komen, daarom ronden we niet-gehele uitkomsten af.
4) Zekerheid
• Alle coëfficiënten zijn gekend met zekerheid
o Soorten coëfficiënten
▪ Doelfunctiecoëfficiënten: bijdragen tot de doelfunctie
▪ Technologische coëfficiënten: bijdragen tot linkerzijde
van de vergelijking
- Haalbaarheidsverzameling
o De verzameling van alle punten die voldoen aan de LP-verzameling en de
tekenbeperking
- Optimale oplossing
o Voor een maximaliseringsprobleem/minimaliseringsprobleem, is de optimale
oplossing het punt in de haalbaarheidsverzameling met de hoogste/laagste
doelfunctiewaarde
o Manieren de optimale oplossing te berekenen:
▪ Grafisch
▪ Procedureel
▪ Software
B. Grafische oplossing van een maximaliseringsprobleem met 2 variabelen
- Haalbaarheidsverzameling
o Door een vergelijking van de rechte van de beperking op te stellen
bekomen we een gedeelte op de grafiek die:
▪ Haalbaar is (gebied onder de rechte)
, ▪ Niet-haalbaar is (gebied boven de rechte)
- Optimum
o We kunnen het optimum berekenen aan de hand van isowinstlijnen of
isokostlijnen
▪ Isowinstlijn: Maximaliseringsprobleem (= opbrengsten optimaliseren)
▪ Isokostenlijn: Minimaliseringsprobleem (= kosten optimaliseren)
o Deze isowinstlijnen en isokostenlijn zijn evenwijdig
▪ De vergelijking van deze lijn wordt afgeleidt uit de doelfunctie z
▪ De zien in die vergelijking dat enkel de interecept afhankelijk is van z en
de hellingsgraad dus niet verandert bij een aanpassing
⇒ M.a.w. de isowinstlijnen en isokostlijnen zijn altijd evenwijdig
o Het optimum is de dat punt in de haalbaarheidsverzameling dat
geassocieerd is met de hoogste isowinstlijn of de laagste isokostlijn
Voorbeeld van een LP-probleem
, Onthoud:
Iso-winstcurve = niveaucurve
Alle iso-winstcurves (‘niveaucurves’) lopen evenwijdig
Hoe tekenen we een iso-winstcurve?
Neem een willekeurig punt (𝑥1, 𝑥2) in de oplossingsruimte en bereken de bijhorende z-waarde (‘winst’)!
bv. Als we het punt (4 , 0) nemen, dan is de bijhorende z-waarde (‘winst’) gelijk aan 12. Het punt (4 , 0)
ligt dus op de iso-winstcurve 𝑧 = 3x1 + 2x2 = 12
We kunnen dit herschrijven naar 𝑥2 = z/2 – 3/2 x1 .
De richtingscoëfficiënt is dus 3/2. We kunnen deze iso-winstcurve bijgevolg tekenen.
Omdat alle iso-winstcurves van de vorm 3x1 + 2x2 = 𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡𝑒 zijn, hebben alle iso-winstcurves dezelfde
richtingscoëfficiënt. Dit betekent dat we alle iso- winstcurves kunnen vinden door eenvoudigweg de
reeds getekende iso-winstcurve evenwijdig te verschuiven.
Elementaire begrippen
- Bindende beperkingen
o De linkerzijde en rechterzijde van de bperkingen zijn gelijk bij de optimale oplossing
- Niet-bindende beperkingen
o De linkerzijde en rechterzijde van de bperkingen zijn ongelijk bij de optimale oplossing
Bij ons voorbeeld: (1) en (2) zijn bindend, (3) niet-bindend
- Convexe verzameling
o Een verzameling S is covex als het lijnsegment dat éénder welk puntenpaar AB in S
verbindt ook volledig tot de verzameling S behoort
▪ We zien dus ook dat de haalbaarheidsverzameling van een LP probleem steeds
een convexe verzameling is
o Een extreempunt of hoekpunt
▪ Voor een convexe verzameling S is een punt P een extreem punt als elk
lijnsegment dat volledig in S ligt en het punt P omvat, P als eindpunt heeft
▪ M.a.w. een extreem punt P is een punt in S dat niet kan gereconstueerd worden
als een convexe combinatie van 2 andere punten in S
Opbouw van de cursus
- Doelstelling van de cursus: wiskundige optimaliseringsproblemen oplossen en analyseren
o Lineaire programmering en de simplexmethode
▪ Hoofdstuk 3, 4 en 5/ deel 1, 2 en 3
o Niet-lineaire programmering
▪ Hoofdstuk 11/ deel 4
o Veel voorkomende typeproblemen
▪ Hoofdstuk 7,8 en 9 / deel 5,6 en 7
Inleiding tot het operationeel onderzoek
1. Inleiding
A. Wat is OR?
- Operationeel onderzoek / operationele research (OR)
o = Een wiskundige ondersteuning voor beslisssingen bij praktijkproblemen
o Onderzoek kan gedaan worden via gebonden of ongebonden
optimalisering
o Voorbeelden:
▪ Productieplanning
▪ Dieet
▪ Samenstelling portfolio
2. Een inleiding op LP
A. Wat is een LP problem?
- Een probleem waarbij
o Een lineaire doesltelling geoptimaliseerd (maximum of minimum) wordt
o Onder lineaire beperkingen (technoligische beperkingen,
vraagbeperkingen)
o En waarbij met elke beslissingvariable een tekenbeperking geassocieerd is
(bv. mag niet negatief zijn)
- Beslssingsvariabelen (⇒ moeten voldaan zijn opdat een LP een realsitisch
voorstelling biedt van het beslissingsprobleem)
1) Proportionaliteit
• De bijdrage tot de doelfunctie (=functie die de optimalisatie
voorsteld) van elke beslissingvariabele is proportyioneel aan de
waarde van de beslissingsvariabele
o bv. De bijdrage van 4 geproduceerde eenheden is 4 keer de
bijdrage van 1 geproduceerd eenheid
, Analoog: de bijdrage van elk beslissingsvariabele van een beperking
•
(technologiscg, vraag,…) is proportioneel tot de waarde van de
beslissingswaarde
2) Additiviteit
• De bijdrage tot de doelfunctie van elke beslissingsvariabele is
onafhankelijk van de andere beslissingsvariabelen
o M.a.w. je kan de beslissingsvariabelen optellen
• Analoog: de bijdrage van elke beslissingsvariabele van een
beperking is onafhankelijk van de waarden van de andere
beslissingsvariabelen
3) Deelbaarheid
• We werken met continue beslissingsveranderlijken
• Probleem: vaak niet realistisch om enkel gehele getallen uit te
komen, daarom ronden we niet-gehele uitkomsten af.
4) Zekerheid
• Alle coëfficiënten zijn gekend met zekerheid
o Soorten coëfficiënten
▪ Doelfunctiecoëfficiënten: bijdragen tot de doelfunctie
▪ Technologische coëfficiënten: bijdragen tot linkerzijde
van de vergelijking
- Haalbaarheidsverzameling
o De verzameling van alle punten die voldoen aan de LP-verzameling en de
tekenbeperking
- Optimale oplossing
o Voor een maximaliseringsprobleem/minimaliseringsprobleem, is de optimale
oplossing het punt in de haalbaarheidsverzameling met de hoogste/laagste
doelfunctiewaarde
o Manieren de optimale oplossing te berekenen:
▪ Grafisch
▪ Procedureel
▪ Software
B. Grafische oplossing van een maximaliseringsprobleem met 2 variabelen
- Haalbaarheidsverzameling
o Door een vergelijking van de rechte van de beperking op te stellen
bekomen we een gedeelte op de grafiek die:
▪ Haalbaar is (gebied onder de rechte)
, ▪ Niet-haalbaar is (gebied boven de rechte)
- Optimum
o We kunnen het optimum berekenen aan de hand van isowinstlijnen of
isokostlijnen
▪ Isowinstlijn: Maximaliseringsprobleem (= opbrengsten optimaliseren)
▪ Isokostenlijn: Minimaliseringsprobleem (= kosten optimaliseren)
o Deze isowinstlijnen en isokostenlijn zijn evenwijdig
▪ De vergelijking van deze lijn wordt afgeleidt uit de doelfunctie z
▪ De zien in die vergelijking dat enkel de interecept afhankelijk is van z en
de hellingsgraad dus niet verandert bij een aanpassing
⇒ M.a.w. de isowinstlijnen en isokostlijnen zijn altijd evenwijdig
o Het optimum is de dat punt in de haalbaarheidsverzameling dat
geassocieerd is met de hoogste isowinstlijn of de laagste isokostlijn
Voorbeeld van een LP-probleem
, Onthoud:
Iso-winstcurve = niveaucurve
Alle iso-winstcurves (‘niveaucurves’) lopen evenwijdig
Hoe tekenen we een iso-winstcurve?
Neem een willekeurig punt (𝑥1, 𝑥2) in de oplossingsruimte en bereken de bijhorende z-waarde (‘winst’)!
bv. Als we het punt (4 , 0) nemen, dan is de bijhorende z-waarde (‘winst’) gelijk aan 12. Het punt (4 , 0)
ligt dus op de iso-winstcurve 𝑧 = 3x1 + 2x2 = 12
We kunnen dit herschrijven naar 𝑥2 = z/2 – 3/2 x1 .
De richtingscoëfficiënt is dus 3/2. We kunnen deze iso-winstcurve bijgevolg tekenen.
Omdat alle iso-winstcurves van de vorm 3x1 + 2x2 = 𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡𝑒 zijn, hebben alle iso-winstcurves dezelfde
richtingscoëfficiënt. Dit betekent dat we alle iso- winstcurves kunnen vinden door eenvoudigweg de
reeds getekende iso-winstcurve evenwijdig te verschuiven.
Elementaire begrippen
- Bindende beperkingen
o De linkerzijde en rechterzijde van de bperkingen zijn gelijk bij de optimale oplossing
- Niet-bindende beperkingen
o De linkerzijde en rechterzijde van de bperkingen zijn ongelijk bij de optimale oplossing
Bij ons voorbeeld: (1) en (2) zijn bindend, (3) niet-bindend
- Convexe verzameling
o Een verzameling S is covex als het lijnsegment dat éénder welk puntenpaar AB in S
verbindt ook volledig tot de verzameling S behoort
▪ We zien dus ook dat de haalbaarheidsverzameling van een LP probleem steeds
een convexe verzameling is
o Een extreempunt of hoekpunt
▪ Voor een convexe verzameling S is een punt P een extreem punt als elk
lijnsegment dat volledig in S ligt en het punt P omvat, P als eindpunt heeft
▪ M.a.w. een extreem punt P is een punt in S dat niet kan gereconstueerd worden
als een convexe combinatie van 2 andere punten in S
