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.
Les avantages d'acheter des résumés chez Stuvia:
Qualité garantie par les avis des clients
Les clients de Stuvia ont évalués plus de 700 000 résumés. C'est comme ça que vous savez que vous achetez les meilleurs documents.
L’achat facile et rapide
Vous pouvez payer rapidement avec iDeal, carte de crédit ou Stuvia-crédit pour les résumés. Il n'y a pas d'adhésion nécessaire.
Focus sur l’essentiel
Vos camarades écrivent eux-mêmes les notes d’étude, c’est pourquoi les documents sont toujours fiables et à jour. Cela garantit que vous arrivez rapidement au coeur du matériel.
Foire aux questions
Qu'est-ce que j'obtiens en achetant ce document ?
Vous obtenez un PDF, disponible immédiatement après votre achat. Le document acheté est accessible à tout moment, n'importe où et indéfiniment via votre profil.
Garantie de remboursement : comment ça marche ?
Notre garantie de satisfaction garantit que vous trouverez toujours un document d'étude qui vous convient. Vous remplissez un formulaire et notre équipe du service client s'occupe du reste.
Auprès de qui est-ce que j'achète ce résumé ?
Stuvia est une place de marché. Alors, vous n'achetez donc pas ce document chez nous, mais auprès du vendeur adamloots. Stuvia facilite les paiements au vendeur.
Est-ce que j'aurai un abonnement?
Non, vous n'achetez ce résumé que pour €6,98. Vous n'êtes lié à rien après votre achat.
