Lineaire optimalisatie
Les 1: Hoe formuleer je een LO-probleem?
Stappenplan naar een wiskundig model
STAP 1: HOE EEN MOGELIJKE OPLOSSING BESCHRIJVEN?
Wat is het beslissingprobleem? Op basis hiervan onbekenden definiëren
o Bvb. Probleem tafels en stoelen:
Hoeveel tafels zullen we bouwen = Xt
Hoeveel stoelen zullen we bouwen = Xs
STAP 2: WAARAAN MOET EEN OPLOSSING VOLDOEN?
Beperkingen bepalen, negativiteitsvoorwaarden
o Bvb. Probleem tafels en stoelen:
We hebben slechts 8 kleine en 6 grote blokken. Elke tafel heeft 2
kleine en 2 grote blokken nodig, elke stoel heeft 2 kleine en 1 grote
blok nodig. Geen negatief aantal.
2Xt + 2Xs <= 8, 2Xt + Xs <= 6, Xt >= 0, Xs >= 0
STAP 3: HOE KUNNEN WE OPLOSSINGEN VERGELIJKEN?
We bepalen wat we willen maximaliseren of minimaliseren, hoe we gaan
beoordelen welke oplossing beter of slechter is
o Bvb. Probleem tafels en stoelen:
Een tafel resulteert in een winst van 160 euro, een stoel in 100 euro
160Xt + 100Xs is de te maximaliseren functie
Terminologie
In het voorbeeld van de tafels en de stoelen is:
- Xt en Xs een beslissingsvariabele (decision variable)
- 160Xt + 100Xs de doelfunctie (objective function, goal function)
- 2Xt + 2Xs < 8 een voorbeeld van een beperking (constraint)
- Xs > 0 een niet-negativiteitsbeperking (not-negativity constraint), anders is een
variabele onbeperkt in teken (OIT) of unrestricted in sign (UIS)
- Een coëfficiënt in een beperking (zoals 2) noemen we een technologische
coëfficiënt
- Een coëfficient in een doelfunctie (zoals 160) noemen we een
doelfunctiecoëfficiënt
- Een getal aan de rechterkant van een beperking (zoals 6) is een rechterhand
waarde
Hoe kunnen we een LO model oplossen?
- Simplex methode (H4)
- Lindo/ Lingo (zie Toledo)
- Excel Solver
- Andere commerciële solvers
Waardebepaling
Wat is de waarde van één extra onderdeel (bvb. één extra grote blok om een stoel of
tafel te bouwen). We berekenen hoeveel extra winst we hiermee kunnen creëren. We
noemen dit de schaduwprijs.
Wat is een LO-probleem?
Een LO-probleem is een optimalisatiemodel, gekenmerkt door:
- Beslissingsvariabelen
- Een doelfunctie
- Beperkingen
, Het idee is om waardes voor de beslissingsvariabelen te vinden, zodat de
doelfunctie geoptimaliseerd (min/max) wordt, terwijl aan alle beperkingen
voldaan is.
Een LO-probleem moet voldoen aan de volgende drie assumpties:
- Zekerheid (certainty)
- Deelbaarheid (divisibility)
- Lineariteit (linearity)
Modellen die niet voldoen aan al deze drie assumpties kunnen niet opgelost
worden met de methodes aangeleerd in dit vak.
LO-assumpties
Zekerheid = elke parameter (doelfunctiecoëfficiënt, rechterhand, tecnologische
coëfficiënt) is met zekerheid gekend.
Voor elke waarde van de beslissingsvariabelen, kan je met zekerheid zeggen of
er al dan niet voldaan is aan de beperkingen en wat de resulterende
doelfunctiewaarde is ( deterministisch model stochastisch model)
Deelbaarheid = beslissingsvariabelen kunnen elke fractionele waarde aannemen en
zijn dus continu in tegenstelling tot geheeltallig, een breuk is bvb. dus mogelijk.
Indien niet voldaan, komen we in eht domein van geheeltallige programmering
of integer programming. Deze zijn veel moeilijker om op te lossen.
Lineariteit = de doelfunctie is een lineaire functie, alle beperkingen zijn lineaire
(on)gelijkheden.
Een functie f van reële variabelen x1, x2, …, xn gedefinieerd door f(x1,x2,…,xn)
= c1x1 + … + cnxn voor reële parameters c is een lineaire functie.
Bij lineaire optimalisatie:
o Worden beslissingsvariabelen vermenigvuldigd met een constante
o Worden beslissingsvariabelen enkel opgeteld of afgetrokken
o Zijn beperkingen van de vorm <=, = of >=
Modellen zijn niet lineair zodra het variabelen in een niet-lineaire bewerking
bevat (bvb. een kwadraat, een sinus, een wortel, of strikte ongelijkheden)
Les 2: Modelleren
Zie oefeningen slides
Details LINDO
LINDO (Lineair interactive and discrete optimizer) is een software tool voor het
oplossen van lineaire, geheeltallige en kwadratische programmeringsproblemen.
Typ MAX of MIN voor de doelfunctie
Typ SUBJECT TO op de volgende lijn en voeg daarna de beperkingen toe
Syntax toelichtingen:
- LINDO veronderstelt dat het < symbool eigenlijk ≤ is en dit geldt ook voor >.
- Gebruik geen asterix (*) symbool tussen coëfficiënten en variabelen om
vermenigvuldigen aan te geven
- LINDO herkent geen haakjes
- LINDO veronderstelt alle variabelen niet-negatief, dus niet-
negativiteitsbeperkingen zijn niet noodzakelijk
- Alles achter (!) is commentaar/toelichting
Drie meest gemaakte fouten:
1. Een constante in de doelfunctie of de linkerkant van een beperking
2. Een variabele in de rechterhand van een beperking
, 3. Gebruik van asterix of haakjes
Les 3: Modellering
Zie oefeningen slides
Modelleertips
1. Is er iets dubbelzinnigs in de probleemomschrijving?
o Zo ja, hoe kan dit worden verduidelijkt? Verzamel extra informatie of maak
een aanvullende redelijke veronderstelling.
2. Houd de stapsgewijze aanpak in gedachten
o Begin met het definiëren van de beslissingsvariabelen
o Probeer vervolgens beperkingen en doelfunctie te modelleren
3. Check: is het betekenisvol?
o Ga voor een aantal triviale, ontoelaatbare oplossingen na dat niet aan alle
beperkingen voldaan is
Een probleem modelleren vraagt wat creativiteit en ervaring. Enkele tips:
- Oplossen: welke resultaten komen eruit bij oplossing?
o Ontoelaatbaar (infeasible)? Test een triviale oplossing, welke beperkingen
zijng eschonden? Deze is wellicht incorrect.
o Onbegrends (unbounded)? Misschien eentje vergeten.
o Kan je de oplossing verbeteren? Waarom werd deze niet toegelaten door
het model? De gerelateerde beperking kan fout zijn.
- Er zijn vaak meerdere correcte formuleringen, mogelijks met verschillende
keuzes van variabelen.
Les 4:
Oefeningen & Excel solver, zie slides
Les 5: grafische oplossen van LO problemen
Het toelaatbare gebied (feasible region) van een LO probleem is de verzameling van
punten die voldoen aan ALLE beperkingen van het LO probleem.
We bestuderen de grafische methode enkel voor problemen met twee
variabelen, een punt is dan (x1,x2). Dit omdat we deze kunnen voorstellen als
een rechte in een grafiek.
Elke lineaire ongelijkheid verdeelt het vlak in twee delen: punten die niet toelaatbaar
zijn en punten die toelaatbaar zijn, m.b.t. deze beperking. Deze twee delen worden
halfruimten (half-spaces) genoemd.
Wanneer we dus meerdere beperkingen hebben is het toelaatbare gebied de
doorsnede van de twee halfruimten en wordt ook wel een veelvlak (polyhedron)
genoemd.
Als we ons toelaatbare gebied hebben, gebruiken we de doelfunctie als isoprofit lijn.
Deze schuiven we steeds hoger en hoger tot we uiteindelijk het verste hoekpunt
bereiken. Dit hoekpunt is een snijpunt tussen twee beperkingen. We vinden dan het
optimale punt door deze 2 beperkingen op te lossen via een stelsel.
Hoe verloopt dus zo’n grafische methode?
1. Teken het toelaatbaar gebied
2. Trek een isoprofit of een isokot lijn
3. Verschuif deze lijn in de richting waarin de doelfunctie verbetert
4. De laatste lijn met een niet-lege doorsnede met het toelaatbaar gebied bepaalt
de optimale waarde (en een optimale oplossing)
Les 1: Hoe formuleer je een LO-probleem?
Stappenplan naar een wiskundig model
STAP 1: HOE EEN MOGELIJKE OPLOSSING BESCHRIJVEN?
Wat is het beslissingprobleem? Op basis hiervan onbekenden definiëren
o Bvb. Probleem tafels en stoelen:
Hoeveel tafels zullen we bouwen = Xt
Hoeveel stoelen zullen we bouwen = Xs
STAP 2: WAARAAN MOET EEN OPLOSSING VOLDOEN?
Beperkingen bepalen, negativiteitsvoorwaarden
o Bvb. Probleem tafels en stoelen:
We hebben slechts 8 kleine en 6 grote blokken. Elke tafel heeft 2
kleine en 2 grote blokken nodig, elke stoel heeft 2 kleine en 1 grote
blok nodig. Geen negatief aantal.
2Xt + 2Xs <= 8, 2Xt + Xs <= 6, Xt >= 0, Xs >= 0
STAP 3: HOE KUNNEN WE OPLOSSINGEN VERGELIJKEN?
We bepalen wat we willen maximaliseren of minimaliseren, hoe we gaan
beoordelen welke oplossing beter of slechter is
o Bvb. Probleem tafels en stoelen:
Een tafel resulteert in een winst van 160 euro, een stoel in 100 euro
160Xt + 100Xs is de te maximaliseren functie
Terminologie
In het voorbeeld van de tafels en de stoelen is:
- Xt en Xs een beslissingsvariabele (decision variable)
- 160Xt + 100Xs de doelfunctie (objective function, goal function)
- 2Xt + 2Xs < 8 een voorbeeld van een beperking (constraint)
- Xs > 0 een niet-negativiteitsbeperking (not-negativity constraint), anders is een
variabele onbeperkt in teken (OIT) of unrestricted in sign (UIS)
- Een coëfficiënt in een beperking (zoals 2) noemen we een technologische
coëfficiënt
- Een coëfficient in een doelfunctie (zoals 160) noemen we een
doelfunctiecoëfficiënt
- Een getal aan de rechterkant van een beperking (zoals 6) is een rechterhand
waarde
Hoe kunnen we een LO model oplossen?
- Simplex methode (H4)
- Lindo/ Lingo (zie Toledo)
- Excel Solver
- Andere commerciële solvers
Waardebepaling
Wat is de waarde van één extra onderdeel (bvb. één extra grote blok om een stoel of
tafel te bouwen). We berekenen hoeveel extra winst we hiermee kunnen creëren. We
noemen dit de schaduwprijs.
Wat is een LO-probleem?
Een LO-probleem is een optimalisatiemodel, gekenmerkt door:
- Beslissingsvariabelen
- Een doelfunctie
- Beperkingen
, Het idee is om waardes voor de beslissingsvariabelen te vinden, zodat de
doelfunctie geoptimaliseerd (min/max) wordt, terwijl aan alle beperkingen
voldaan is.
Een LO-probleem moet voldoen aan de volgende drie assumpties:
- Zekerheid (certainty)
- Deelbaarheid (divisibility)
- Lineariteit (linearity)
Modellen die niet voldoen aan al deze drie assumpties kunnen niet opgelost
worden met de methodes aangeleerd in dit vak.
LO-assumpties
Zekerheid = elke parameter (doelfunctiecoëfficiënt, rechterhand, tecnologische
coëfficiënt) is met zekerheid gekend.
Voor elke waarde van de beslissingsvariabelen, kan je met zekerheid zeggen of
er al dan niet voldaan is aan de beperkingen en wat de resulterende
doelfunctiewaarde is ( deterministisch model stochastisch model)
Deelbaarheid = beslissingsvariabelen kunnen elke fractionele waarde aannemen en
zijn dus continu in tegenstelling tot geheeltallig, een breuk is bvb. dus mogelijk.
Indien niet voldaan, komen we in eht domein van geheeltallige programmering
of integer programming. Deze zijn veel moeilijker om op te lossen.
Lineariteit = de doelfunctie is een lineaire functie, alle beperkingen zijn lineaire
(on)gelijkheden.
Een functie f van reële variabelen x1, x2, …, xn gedefinieerd door f(x1,x2,…,xn)
= c1x1 + … + cnxn voor reële parameters c is een lineaire functie.
Bij lineaire optimalisatie:
o Worden beslissingsvariabelen vermenigvuldigd met een constante
o Worden beslissingsvariabelen enkel opgeteld of afgetrokken
o Zijn beperkingen van de vorm <=, = of >=
Modellen zijn niet lineair zodra het variabelen in een niet-lineaire bewerking
bevat (bvb. een kwadraat, een sinus, een wortel, of strikte ongelijkheden)
Les 2: Modelleren
Zie oefeningen slides
Details LINDO
LINDO (Lineair interactive and discrete optimizer) is een software tool voor het
oplossen van lineaire, geheeltallige en kwadratische programmeringsproblemen.
Typ MAX of MIN voor de doelfunctie
Typ SUBJECT TO op de volgende lijn en voeg daarna de beperkingen toe
Syntax toelichtingen:
- LINDO veronderstelt dat het < symbool eigenlijk ≤ is en dit geldt ook voor >.
- Gebruik geen asterix (*) symbool tussen coëfficiënten en variabelen om
vermenigvuldigen aan te geven
- LINDO herkent geen haakjes
- LINDO veronderstelt alle variabelen niet-negatief, dus niet-
negativiteitsbeperkingen zijn niet noodzakelijk
- Alles achter (!) is commentaar/toelichting
Drie meest gemaakte fouten:
1. Een constante in de doelfunctie of de linkerkant van een beperking
2. Een variabele in de rechterhand van een beperking
, 3. Gebruik van asterix of haakjes
Les 3: Modellering
Zie oefeningen slides
Modelleertips
1. Is er iets dubbelzinnigs in de probleemomschrijving?
o Zo ja, hoe kan dit worden verduidelijkt? Verzamel extra informatie of maak
een aanvullende redelijke veronderstelling.
2. Houd de stapsgewijze aanpak in gedachten
o Begin met het definiëren van de beslissingsvariabelen
o Probeer vervolgens beperkingen en doelfunctie te modelleren
3. Check: is het betekenisvol?
o Ga voor een aantal triviale, ontoelaatbare oplossingen na dat niet aan alle
beperkingen voldaan is
Een probleem modelleren vraagt wat creativiteit en ervaring. Enkele tips:
- Oplossen: welke resultaten komen eruit bij oplossing?
o Ontoelaatbaar (infeasible)? Test een triviale oplossing, welke beperkingen
zijng eschonden? Deze is wellicht incorrect.
o Onbegrends (unbounded)? Misschien eentje vergeten.
o Kan je de oplossing verbeteren? Waarom werd deze niet toegelaten door
het model? De gerelateerde beperking kan fout zijn.
- Er zijn vaak meerdere correcte formuleringen, mogelijks met verschillende
keuzes van variabelen.
Les 4:
Oefeningen & Excel solver, zie slides
Les 5: grafische oplossen van LO problemen
Het toelaatbare gebied (feasible region) van een LO probleem is de verzameling van
punten die voldoen aan ALLE beperkingen van het LO probleem.
We bestuderen de grafische methode enkel voor problemen met twee
variabelen, een punt is dan (x1,x2). Dit omdat we deze kunnen voorstellen als
een rechte in een grafiek.
Elke lineaire ongelijkheid verdeelt het vlak in twee delen: punten die niet toelaatbaar
zijn en punten die toelaatbaar zijn, m.b.t. deze beperking. Deze twee delen worden
halfruimten (half-spaces) genoemd.
Wanneer we dus meerdere beperkingen hebben is het toelaatbare gebied de
doorsnede van de twee halfruimten en wordt ook wel een veelvlak (polyhedron)
genoemd.
Als we ons toelaatbare gebied hebben, gebruiken we de doelfunctie als isoprofit lijn.
Deze schuiven we steeds hoger en hoger tot we uiteindelijk het verste hoekpunt
bereiken. Dit hoekpunt is een snijpunt tussen twee beperkingen. We vinden dan het
optimale punt door deze 2 beperkingen op te lossen via een stelsel.
Hoe verloopt dus zo’n grafische methode?
1. Teken het toelaatbaar gebied
2. Trek een isoprofit of een isokot lijn
3. Verschuif deze lijn in de richting waarin de doelfunctie verbetert
4. De laatste lijn met een niet-lege doorsnede met het toelaatbaar gebied bepaalt
de optimale waarde (en een optimale oplossing)
