Linear Optimisation Samenvatting | 15/20 EERSTE ZIT HIR
10 views 0 purchase
Course
Linear Optimisation (D0H45A)
Institution
Katholieke Universiteit Leuven (KU Leuven)
Deze samenvatting bevat alle leerstof uit de lessen Lineaire Optimalisatie, gegeven door Jeroen Belien aan de tweedejaars studenten HIR. Ik behaalde met deze samenvatting een 15/20 in mijn eerste zit. Ze is gebaseerd op notities uit de lessen, aangevuld met de powerpoints.
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.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller adamloots. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.48. You're not tied to anything after your purchase.
