Lineaire Optimalisatie
0. Les 0: Inleiding
Wat is lineair programmeren? Het oplossen van een beslissingsprobleem: kies één
oplossing uit een (mogelijk oneindig) aantal opties. Houd rekening met een aantal
beperkingen t.g.v. een beperkte beschikbaarheid van hulpmiddelen (tijd, personeel, geld, ...).
Optimalisatie: zo optimaal (goed) mogelijk, volgens een gegeven criterium.
1. Les 1: Hoe formuleer je een LO probleem?
Om een LO probleem te formuleren moeten we ons probleem proberen vertalen naar een
wiskundig model. Daarbij stellen we een doelfunctie op die we moeten maximaliseren of
minimaliseren (bv de winst die max moet zijn of de kosten die min moeten zijn), in die functie
noemen we de variabelen de beslissingsvariabelen. We stellen verder ook beperkingen op
(constraints), dit zijn de voorwaarden waaraan ons probleem is onderworpen. Een mogelijke
beperking die we daarbij nog kunnen toevoegen is de niet-negativiteitsbeperking, deze legt
het teken van de variabelen vast op positief. Binnen de beperkingen zullen we coëfficiënten
toekennen aan de variabelen die we de technische coëfficiënten noemen, als we deze in de
doelfunctie doen dan spreken we van een doelfunctiecoëfficiënt. Ten slotte is de voorwaarde
waaraan een bepaalde beperking moet voldoen de rechterhand: bv 2𝑥𝑇 + 𝑥𝑆 ≤ 6, hierbij is 6
de rechterhand.
Schaduwprijs: de bijkomende waarde die één additionele eenheid van een van de variabele
zou creëren.
Een LO problem moet voldoen aan 3 assumpties:
- Zekerheid (Certainty): elke parameter is met zekerheid gekend, we moeten met
zekerheid kunnen zeggen of een voorwaarde voldaan is of niet. We veronderstellen
dus een deterministisch model.
- Deelbaarheid (Divisibility): beslissingsvariabelen kunnen elke factionele waarde
aannemen en zijn dus continu.
- Lineariteit (Linearity): de doelfunctie is een lineaire functie, alle beperkingen zijn
lineaire (on)gelijkheden (≤,≥ of =).
, 2. Les 2: Modelleren en Lindo
We formuleren een LO-probleem met 3 elementen: de doelfunctie, de beperkingen en de
tekenbeperkingen. Daarbij zijn 4 componenten:
- Parameters: inputs, gegevens/data.
- Variabelen: zaken die je kan kiezen.
- Beperkingen: beschrijft de limieten.
- Doel: maximaliseer winst, minimaliseer kosten.
Er zijn veel verschillende soorten LO-problemen die elks als voorbeelden in de les worden
behandeld (zie slides):
- Een dieetprobleem
- Een personeelsplanningprobleem
- Een investeringsprobleem
- Korte termijn financiële planning
- Mengproblemen
- Productieproces modellen
- Een snijprobleem
- Voorraadproblemen
- Meerdere perioden financiële planning
- Meerdere perioden personeelsplanningsprobleem
- Transportprobleem
- Toewijzingsprobleem
- Overslagprobleem
We nemen een voorbeeld (hier een personeelsplanning probleem):
, Verder zien we ook dat we niet LO-modellen toch LO kunnen maken door te herformuleren.
Dit kunnen we doen door bv een parameter uit de noemer te verwerken of dingen
herschrijven, een voorbeeld:
Na de herformulering krijgen we dan:
LINDO (Linear Interactive and Discrete Optimizer): een software tool die we kunnen
gebruiken om LO-problemen op te lossen, ze kan echter ook verschillende andere typen
problemen oplossen. We bespreken hier enkele van de commando’s:
- MIN of MAX voor de doelfunctie.
- SUBJECT TO om de beperkingen aan te geven.
- Gebruik geen “*” om vermenigvuldigingen aan te geven tussen variabelen en
coëfficiënten.
- Lindo herkent geen haakjes.
- Ze gaat uit dat > ⇒ ≥ en andersom < ⇒ ≤.
- De niet-negativiteitsbeperking is niet nodig, lindo neemt dit standaard aan.
- Alles achter “!” is commentaar en wordt dus niet uitgevoerd.
- Om een model op te lossen druk je op de dartsknop of gebruik het
SOLVE commando.
- Op het einde van de code zetten we “end” om aan te geven dat de
code eindigt.
0. Les 0: Inleiding
Wat is lineair programmeren? Het oplossen van een beslissingsprobleem: kies één
oplossing uit een (mogelijk oneindig) aantal opties. Houd rekening met een aantal
beperkingen t.g.v. een beperkte beschikbaarheid van hulpmiddelen (tijd, personeel, geld, ...).
Optimalisatie: zo optimaal (goed) mogelijk, volgens een gegeven criterium.
1. Les 1: Hoe formuleer je een LO probleem?
Om een LO probleem te formuleren moeten we ons probleem proberen vertalen naar een
wiskundig model. Daarbij stellen we een doelfunctie op die we moeten maximaliseren of
minimaliseren (bv de winst die max moet zijn of de kosten die min moeten zijn), in die functie
noemen we de variabelen de beslissingsvariabelen. We stellen verder ook beperkingen op
(constraints), dit zijn de voorwaarden waaraan ons probleem is onderworpen. Een mogelijke
beperking die we daarbij nog kunnen toevoegen is de niet-negativiteitsbeperking, deze legt
het teken van de variabelen vast op positief. Binnen de beperkingen zullen we coëfficiënten
toekennen aan de variabelen die we de technische coëfficiënten noemen, als we deze in de
doelfunctie doen dan spreken we van een doelfunctiecoëfficiënt. Ten slotte is de voorwaarde
waaraan een bepaalde beperking moet voldoen de rechterhand: bv 2𝑥𝑇 + 𝑥𝑆 ≤ 6, hierbij is 6
de rechterhand.
Schaduwprijs: de bijkomende waarde die één additionele eenheid van een van de variabele
zou creëren.
Een LO problem moet voldoen aan 3 assumpties:
- Zekerheid (Certainty): elke parameter is met zekerheid gekend, we moeten met
zekerheid kunnen zeggen of een voorwaarde voldaan is of niet. We veronderstellen
dus een deterministisch model.
- Deelbaarheid (Divisibility): beslissingsvariabelen kunnen elke factionele waarde
aannemen en zijn dus continu.
- Lineariteit (Linearity): de doelfunctie is een lineaire functie, alle beperkingen zijn
lineaire (on)gelijkheden (≤,≥ of =).
, 2. Les 2: Modelleren en Lindo
We formuleren een LO-probleem met 3 elementen: de doelfunctie, de beperkingen en de
tekenbeperkingen. Daarbij zijn 4 componenten:
- Parameters: inputs, gegevens/data.
- Variabelen: zaken die je kan kiezen.
- Beperkingen: beschrijft de limieten.
- Doel: maximaliseer winst, minimaliseer kosten.
Er zijn veel verschillende soorten LO-problemen die elks als voorbeelden in de les worden
behandeld (zie slides):
- Een dieetprobleem
- Een personeelsplanningprobleem
- Een investeringsprobleem
- Korte termijn financiële planning
- Mengproblemen
- Productieproces modellen
- Een snijprobleem
- Voorraadproblemen
- Meerdere perioden financiële planning
- Meerdere perioden personeelsplanningsprobleem
- Transportprobleem
- Toewijzingsprobleem
- Overslagprobleem
We nemen een voorbeeld (hier een personeelsplanning probleem):
, Verder zien we ook dat we niet LO-modellen toch LO kunnen maken door te herformuleren.
Dit kunnen we doen door bv een parameter uit de noemer te verwerken of dingen
herschrijven, een voorbeeld:
Na de herformulering krijgen we dan:
LINDO (Linear Interactive and Discrete Optimizer): een software tool die we kunnen
gebruiken om LO-problemen op te lossen, ze kan echter ook verschillende andere typen
problemen oplossen. We bespreken hier enkele van de commando’s:
- MIN of MAX voor de doelfunctie.
- SUBJECT TO om de beperkingen aan te geven.
- Gebruik geen “*” om vermenigvuldigingen aan te geven tussen variabelen en
coëfficiënten.
- Lindo herkent geen haakjes.
- Ze gaat uit dat > ⇒ ≥ en andersom < ⇒ ≤.
- De niet-negativiteitsbeperking is niet nodig, lindo neemt dit standaard aan.
- Alles achter “!” is commentaar en wordt dus niet uitgevoerd.
- Om een model op te lossen druk je op de dartsknop of gebruik het
SOLVE commando.
- Op het einde van de code zetten we “end” om aan te geven dat de
code eindigt.
