Operationeel Onderzoek
Operationeel onderzoek: het gebruik van wiskundige technieken voor optimalisatie en voor
analyse van ‘operaties’. Operaties = het gebruik van hulpmiddelen – kapitaal, materialen,
technologie, menselijke vaardigheden/kennis, . . . – bij de productie en distributie van
goederen en diensten.
=> Kijk voor het starten van deze cursus naar de herhaling bundels over het vak LO van
vorig jaar.
1.Deel 1: Geheeltallige Programmering
1.1 Geheeltallige variabelen
Geheeltallige programmering = integer programming (IP): als in een scenario de gewoonlijke
deelbaarheidsassumptie (de variabelen mogen eender welk reëel getal zijn) niet opgaat dan
moeten we expliciet vermelden dat Σ𝑖𝑥𝑖 ∈ {...., − 1, 0, 1,...}. We gebruiken dit bij problemen
waarbij we enkel gehele waarden als antwoord mogen bekomen, bv men kan geen halve
tafel produceren. Als we deze geheeltalligheidseis weglaten dan spreken we van een
LP-relaxatie.
Standaardvorm: een LP met variabelen 𝑥𝑖 is in standaardvorm als:
- Alle 𝑥𝑖 ≥ 0 zijn.
- Op de tekenbeperkingen na, alle beperkingen gelijkheden zijn.
- Alle rechterleden ≥ 0 zijn.
De kanonieke vorm van een lineair programmeringsprobleem is wanneer:
- Je een maximalisatieprobleem hebt,
- Alle restricties zijn gelijkheden (dus niet ≤ of ≥, maar gewoon =),
- Alle variabelen zijn niet-negatief (𝑥𝑖 ≥ 0).
BV (basisvariabele) komen voor met als kolom een eenheidsvector: 0’en en één keer 1. Er is
dus één individuele rij per B.
=> Een toelaatbare b.o. (tbo) heeft alle variabelen ≥ 0.
=> Stelling: Elk extreem punt van de LP-oplossingsruimte is een tbo, en omgekeerd.
De oplossingsruimte van een IP is niet convex; het concept van ‘extreem punt’ is hier zelfs
niet gedefinieerd. . . Kunnen we LP gebruiken om het IP op te lossen?
- Afronden zal niet altijd een optimum leveren (zelfs een toelaatbare vinden kan lastig
zijn).
- Wat indien de oplossing van de LP-relaxatie geheeltallig is?
, - De oplossingsruimte van een IP is een deelverzameling van de oplossingsruimte van
* *
de LP-relaxatie. Bijgevolg is: min-probleem: 𝑍 ≥ 𝑍𝐿𝑃; max-probleem: 𝑍𝐿𝑃 ≥ 𝑍 ; met
*
𝑍𝐿𝑃 de optimale doelfunctiewaarde van de LP-relaxatie en 𝑍 de waarde voor het
IP-optimum. We hebben dus een beneden-, resp. bovengrens.
- Eender welk toelaatbaar punt heeft 𝑥1 ≤ 3 ofwel 𝑥1 ≥ 4. Partitioneren van de
zoekruimte: branching (vertakken).
=> Branch-and-bound (B&B; ‘vertak-en-begrens’):
- Los LP-relaxatie op, indien geheeltallig stop.
- Opsplitsen (branching) van de oplossingsruimte van de LP-relaxatie in
deelverzamelingen door beperkingen toe te voegen op de waarden van de
geheeltallige beslissingsvariabelen (wederzijds exclusief en gezamenlijk exhaustief,
of dus een ‘partitie’ van de oplossingsruimte).
- Los een LP op over één deelverzameling (simplex niet meer te kennen).
- Indien geheeltallig, bewaar de best gevonden geheeltallige oplossing (=
kandidaat-oplossing, ‘incumbent’, momenteel beste GLB= global lower bound) en
backtrack. Anders moet je verder vertakken, behalve indien een LP-relaxatie (lokale
bovengrens) een slechtere (of dezelfde) doelfunctiewaarde heeft dan de huidige
incumbent: dan moet je niet verder opsplitsen en kan je deze tak elimineren in de
zoekboom (= ‘fathomed’ = afgewerkt), want de doelfunctiewaarde zal lager in de
boom nooit verbeteren.
- Je kan ook met toleranties werken: bvb. fathom een tak ook als de LP-relaxatie beter
is dan de huidige incumbent, maar op slechts 5% of minder daarvan ligt.
=> LUB geeft aan wat de hoogste doelfunctiewaarde kan zijn in een gegeven tak!!
=> De beste keuze voor zowel de vertakking beslissing als de keuze van volgorde van
oplossen van sub-problemen is probleem-afhankelijk.
Vertakkingsschema van voorbeeld op pagina 10:
,Zelfde stappenplan als net besproken maar makkelijker verwoord door ChatGPT:
- Los het gewone LP op (relaxatie):
- Negeer even de eis dat variabelen integer moeten zijn.
*
- Vind een optimale oplossing 𝑥 met LP.
- Controleer:
*
- Is 𝑥 integer? → Klaar! Dit is je oplossing.
*
- Is 𝑥 niet-integer? → Dan moet je branch-en.
- Branch:
- Kies een variabele die een niet-geheel getal is, bv. 𝑥1 = 2, 5.
- Maak 2 nieuwe deelproblemen:
- 𝑥1 ≤ 2
- 𝑥1 ≥ 3
- Bound:
- Los elk deelprobleem op met LP:
- Als de oplossing slechter is dan wat je al had (bij maximalisatie:
lagere waarde), verwerp die tak.
- Als de oplossing beter is en integer, update je beste oplossing.
- Als de oplossing beter maar niet-integer is, branch opnieuw.
- Herhaal totdat je overal integeroplossingen hebt gevonden, of ziet dat een tak niet
beter kan zijn.
1.2 Knapzak
0/1-knapzak: Je moet objecten kiezen: Elk object: neem je volledig of helemaal niet (dus
𝑥𝑖 ∈ {0, 1}). Je wil maximale waarde en de totale massa mag de capaciteit van de knapzak
niet overschrijden (zoals het investeringsprobleem in de cursus). Het is eigenlijk een
geheeltallige versie van het klassieke knapzakprobleem, we nemen een object volledig mee
of niet (0/1).
1.3 Set covering/packing/partitioning
(Set=verzameling)
Brandweerstation-probleem (set-covering-probleem): Lokaliseer
brandweerstations zodat elk district een brandweer-station heeft, of
vlak naast zo’n district ligt. Minimaliseer het aantal benodigde stations.
De beperkingen in dit probleem zullen we bekomen door voor elke
gemeente de beperking op te stellen dat er minstens één
brandweerstation moet zijn in de gemeente zelf of in een omliggende
gemeente: bv voor gemeente 1: 𝑥1 + 𝑥2 + 𝑥4 + 𝑥5 ≥ 1:
=> De coefficientenmatrix die we bekomen bij de beperkingen noemen
we een incidentiematrix.
=> Set-covering-probleem: we hebben objecten (hier de gemeentes) in kolommen en
deelverzamelingen in rijen (potentiële kazernes). In essentie minimaliseren we de
, hoeveelheid rijen die we moeten nemen terwijl we ervoor zorgen dat elke kolom minstens
één keer voorkomt.
Multicriteria beslissingsanalyse: = multi-attribuut beslissingsanalyse = beslissen
(/optimalisatie) met meerdere doelfuncties = multi-objectieve optimalisatie. Tot nu toe
hebben we modellen besproken met één objectieffunctie.
Een oplossing A voor een multi-objectief optimalisatieprobleem domineert oplossing B als A
even goed doet op alle doelfuncties en strikt beter op minstens één doelfunctie.
Een oplossing A is Pareto-optimaal als geen andere oplossing bestaat die even goed doet
als A op alle doelfuncties en strikt beter op minstens één. Een oplossing is dus
Pareto-optimaal als ze niet gedomineerd is. De verzameling van alle Pareto-optimale punten
wordt het Pareto-front of “efficient frontier”genoemd; voor LP bekom je zo een trade-off
curve.
=> Hoe kunnen we deze punten nu vinden?
- Stapsgewijs: preëmptieve programmering (er is een hiërarchie in de doelfuncties)
optimaliseer één objectieffunctie, dan optimaliseer je de tweede met bijkomende
beperking dat objectief 1 de bekomen waarde heeft. Hierna gaan we telkens de
tweede functie blijven optimaliseren gegeven dat objectieffunctie 1
≤ 𝑤𝑎𝑎𝑟𝑑𝑒𝑛 𝑖𝑛 𝑑𝑒 𝑏𝑢𝑢𝑟𝑡 𝑣𝑎𝑛 ℎ𝑒𝑡 𝑔𝑒𝑣𝑜𝑛𝑑𝑒𝑛 𝑜𝑝𝑡𝑖𝑚𝑢𝑚 (bij een minimalisatieprobleem).
- Gewogen gemiddelde doelfunctie.
We spreken van een cover als de unie van alle deelverzamelingen gelijk is aan de
hoofdverzameling (elk element van de hoofdverzameling komt dus voor in een
deelverzameling) 𝐴𝑥 ≥ 1. We spreken van een packing als er geen elementen overlappen
tussen de deelverzamelingen (elk element zit in maar in maximum één verzameling, denk
aan potentiële boekingen bij een airline, elke stoel kan maar bij één boeking horen (of leeg
zijn en dus tot geen enkele boeking behoren)) 𝐴𝑥 ≤ 1. We spreken van partitie als het
zowel een cover als een pakking is (dus elk element komt exact één keer voor in de
deelverzamelingen, denk maar aan een klaslokaal opdelen in groepjes studenten) 𝐴𝑥 = 1.
Operationeel onderzoek: het gebruik van wiskundige technieken voor optimalisatie en voor
analyse van ‘operaties’. Operaties = het gebruik van hulpmiddelen – kapitaal, materialen,
technologie, menselijke vaardigheden/kennis, . . . – bij de productie en distributie van
goederen en diensten.
=> Kijk voor het starten van deze cursus naar de herhaling bundels over het vak LO van
vorig jaar.
1.Deel 1: Geheeltallige Programmering
1.1 Geheeltallige variabelen
Geheeltallige programmering = integer programming (IP): als in een scenario de gewoonlijke
deelbaarheidsassumptie (de variabelen mogen eender welk reëel getal zijn) niet opgaat dan
moeten we expliciet vermelden dat Σ𝑖𝑥𝑖 ∈ {...., − 1, 0, 1,...}. We gebruiken dit bij problemen
waarbij we enkel gehele waarden als antwoord mogen bekomen, bv men kan geen halve
tafel produceren. Als we deze geheeltalligheidseis weglaten dan spreken we van een
LP-relaxatie.
Standaardvorm: een LP met variabelen 𝑥𝑖 is in standaardvorm als:
- Alle 𝑥𝑖 ≥ 0 zijn.
- Op de tekenbeperkingen na, alle beperkingen gelijkheden zijn.
- Alle rechterleden ≥ 0 zijn.
De kanonieke vorm van een lineair programmeringsprobleem is wanneer:
- Je een maximalisatieprobleem hebt,
- Alle restricties zijn gelijkheden (dus niet ≤ of ≥, maar gewoon =),
- Alle variabelen zijn niet-negatief (𝑥𝑖 ≥ 0).
BV (basisvariabele) komen voor met als kolom een eenheidsvector: 0’en en één keer 1. Er is
dus één individuele rij per B.
=> Een toelaatbare b.o. (tbo) heeft alle variabelen ≥ 0.
=> Stelling: Elk extreem punt van de LP-oplossingsruimte is een tbo, en omgekeerd.
De oplossingsruimte van een IP is niet convex; het concept van ‘extreem punt’ is hier zelfs
niet gedefinieerd. . . Kunnen we LP gebruiken om het IP op te lossen?
- Afronden zal niet altijd een optimum leveren (zelfs een toelaatbare vinden kan lastig
zijn).
- Wat indien de oplossing van de LP-relaxatie geheeltallig is?
, - De oplossingsruimte van een IP is een deelverzameling van de oplossingsruimte van
* *
de LP-relaxatie. Bijgevolg is: min-probleem: 𝑍 ≥ 𝑍𝐿𝑃; max-probleem: 𝑍𝐿𝑃 ≥ 𝑍 ; met
*
𝑍𝐿𝑃 de optimale doelfunctiewaarde van de LP-relaxatie en 𝑍 de waarde voor het
IP-optimum. We hebben dus een beneden-, resp. bovengrens.
- Eender welk toelaatbaar punt heeft 𝑥1 ≤ 3 ofwel 𝑥1 ≥ 4. Partitioneren van de
zoekruimte: branching (vertakken).
=> Branch-and-bound (B&B; ‘vertak-en-begrens’):
- Los LP-relaxatie op, indien geheeltallig stop.
- Opsplitsen (branching) van de oplossingsruimte van de LP-relaxatie in
deelverzamelingen door beperkingen toe te voegen op de waarden van de
geheeltallige beslissingsvariabelen (wederzijds exclusief en gezamenlijk exhaustief,
of dus een ‘partitie’ van de oplossingsruimte).
- Los een LP op over één deelverzameling (simplex niet meer te kennen).
- Indien geheeltallig, bewaar de best gevonden geheeltallige oplossing (=
kandidaat-oplossing, ‘incumbent’, momenteel beste GLB= global lower bound) en
backtrack. Anders moet je verder vertakken, behalve indien een LP-relaxatie (lokale
bovengrens) een slechtere (of dezelfde) doelfunctiewaarde heeft dan de huidige
incumbent: dan moet je niet verder opsplitsen en kan je deze tak elimineren in de
zoekboom (= ‘fathomed’ = afgewerkt), want de doelfunctiewaarde zal lager in de
boom nooit verbeteren.
- Je kan ook met toleranties werken: bvb. fathom een tak ook als de LP-relaxatie beter
is dan de huidige incumbent, maar op slechts 5% of minder daarvan ligt.
=> LUB geeft aan wat de hoogste doelfunctiewaarde kan zijn in een gegeven tak!!
=> De beste keuze voor zowel de vertakking beslissing als de keuze van volgorde van
oplossen van sub-problemen is probleem-afhankelijk.
Vertakkingsschema van voorbeeld op pagina 10:
,Zelfde stappenplan als net besproken maar makkelijker verwoord door ChatGPT:
- Los het gewone LP op (relaxatie):
- Negeer even de eis dat variabelen integer moeten zijn.
*
- Vind een optimale oplossing 𝑥 met LP.
- Controleer:
*
- Is 𝑥 integer? → Klaar! Dit is je oplossing.
*
- Is 𝑥 niet-integer? → Dan moet je branch-en.
- Branch:
- Kies een variabele die een niet-geheel getal is, bv. 𝑥1 = 2, 5.
- Maak 2 nieuwe deelproblemen:
- 𝑥1 ≤ 2
- 𝑥1 ≥ 3
- Bound:
- Los elk deelprobleem op met LP:
- Als de oplossing slechter is dan wat je al had (bij maximalisatie:
lagere waarde), verwerp die tak.
- Als de oplossing beter is en integer, update je beste oplossing.
- Als de oplossing beter maar niet-integer is, branch opnieuw.
- Herhaal totdat je overal integeroplossingen hebt gevonden, of ziet dat een tak niet
beter kan zijn.
1.2 Knapzak
0/1-knapzak: Je moet objecten kiezen: Elk object: neem je volledig of helemaal niet (dus
𝑥𝑖 ∈ {0, 1}). Je wil maximale waarde en de totale massa mag de capaciteit van de knapzak
niet overschrijden (zoals het investeringsprobleem in de cursus). Het is eigenlijk een
geheeltallige versie van het klassieke knapzakprobleem, we nemen een object volledig mee
of niet (0/1).
1.3 Set covering/packing/partitioning
(Set=verzameling)
Brandweerstation-probleem (set-covering-probleem): Lokaliseer
brandweerstations zodat elk district een brandweer-station heeft, of
vlak naast zo’n district ligt. Minimaliseer het aantal benodigde stations.
De beperkingen in dit probleem zullen we bekomen door voor elke
gemeente de beperking op te stellen dat er minstens één
brandweerstation moet zijn in de gemeente zelf of in een omliggende
gemeente: bv voor gemeente 1: 𝑥1 + 𝑥2 + 𝑥4 + 𝑥5 ≥ 1:
=> De coefficientenmatrix die we bekomen bij de beperkingen noemen
we een incidentiematrix.
=> Set-covering-probleem: we hebben objecten (hier de gemeentes) in kolommen en
deelverzamelingen in rijen (potentiële kazernes). In essentie minimaliseren we de
, hoeveelheid rijen die we moeten nemen terwijl we ervoor zorgen dat elke kolom minstens
één keer voorkomt.
Multicriteria beslissingsanalyse: = multi-attribuut beslissingsanalyse = beslissen
(/optimalisatie) met meerdere doelfuncties = multi-objectieve optimalisatie. Tot nu toe
hebben we modellen besproken met één objectieffunctie.
Een oplossing A voor een multi-objectief optimalisatieprobleem domineert oplossing B als A
even goed doet op alle doelfuncties en strikt beter op minstens één doelfunctie.
Een oplossing A is Pareto-optimaal als geen andere oplossing bestaat die even goed doet
als A op alle doelfuncties en strikt beter op minstens één. Een oplossing is dus
Pareto-optimaal als ze niet gedomineerd is. De verzameling van alle Pareto-optimale punten
wordt het Pareto-front of “efficient frontier”genoemd; voor LP bekom je zo een trade-off
curve.
=> Hoe kunnen we deze punten nu vinden?
- Stapsgewijs: preëmptieve programmering (er is een hiërarchie in de doelfuncties)
optimaliseer één objectieffunctie, dan optimaliseer je de tweede met bijkomende
beperking dat objectief 1 de bekomen waarde heeft. Hierna gaan we telkens de
tweede functie blijven optimaliseren gegeven dat objectieffunctie 1
≤ 𝑤𝑎𝑎𝑟𝑑𝑒𝑛 𝑖𝑛 𝑑𝑒 𝑏𝑢𝑢𝑟𝑡 𝑣𝑎𝑛 ℎ𝑒𝑡 𝑔𝑒𝑣𝑜𝑛𝑑𝑒𝑛 𝑜𝑝𝑡𝑖𝑚𝑢𝑚 (bij een minimalisatieprobleem).
- Gewogen gemiddelde doelfunctie.
We spreken van een cover als de unie van alle deelverzamelingen gelijk is aan de
hoofdverzameling (elk element van de hoofdverzameling komt dus voor in een
deelverzameling) 𝐴𝑥 ≥ 1. We spreken van een packing als er geen elementen overlappen
tussen de deelverzamelingen (elk element zit in maar in maximum één verzameling, denk
aan potentiële boekingen bij een airline, elke stoel kan maar bij één boeking horen (of leeg
zijn en dus tot geen enkele boeking behoren)) 𝐴𝑥 ≤ 1. We spreken van partitie als het
zowel een cover als een pakking is (dus elk element komt exact één keer voor in de
deelverzamelingen, denk maar aan een klaslokaal opdelen in groepjes studenten) 𝐴𝑥 = 1.
