06/12/2022
De dagen worden korter, Sinterklaas is sinds vandaag weer het land uit en we zijn toe aan wat winterse gezelligheid. Tijd om de kerstboom in huis te halen! De kerstboomverkoper is al het hele jaar bezig geweest met het laten groeien van prachtige kerstbomen en elk jaar heeft hij weer voldoende aanbod voor jou om uit te kiezen. Maar hoe bepaalt hij eigenlijk welke bomen (en hoeveel!) hij gaat verbouwen? Het zijn nou eenmaal geen oliebollen, waarvan je er zo een paar bij bakt… In deze blog leggen we het je uit aan de hand van Linear Programming & het Kerstbomenbedrijf van Meneer S. Claus!
Linear Programming & Meneer S. Claus
Linear Programming houdt in dat we een proces proberen te vatten in een aantal formules en dat we deze set van formules vervolgens oplossen om tot een optimaal resultaat te komen. Dat betekent dat er een formule voor de doelfunctie is (altijd een minimalisatie of maximalisatie) en een formule voor elke verschillende restrictie die je tegenkomt in het proces.
In het voorbeeld van Meneer S. Claus weten we dat hij een eigen Kerstbomenbedrijf heeft en dat hij drie soorten kerstbomen verkoopt. Er is een aantal opvallende zaken:
- Hij heeft grote en kleine kerstbomen. Als hij een grote kerstboom verkoopt maakt hij 15 euro winst, als hij een kleine kerstboom verkoopt, 10 euro.
- Claus heeft ook een luxe paradepaardje in de aanbieding: een kerstboom waarvan de naalden gegarandeerd niet uitvallen. Als hij deze boom verkoopt maakt hij natuurlijk wat meer winst: 20 euro.
Claus wil zijn winst graag maximaliseren. Deze omzet kunnen we alvast in een formule gieten: hierbij noteren we met G het aantal grote kerstbomen, met K het aantal kleine kerstbomen en met L het aantal luxe kerstbomen. Het vergroten van de winst van Claus kunnen we dan vatten in de volgende formule, die onze doelfunctie wordt:
10 * K + 15 * G + 20 * L
Beperkte middelen Claus en Linear Programming
De kerstbomenmarkt is zo populair dat Claus ervan uit kan gaan dat hij alle bomen kan verkopen. Hij heeft echter niet onbeperkt middelen tot zijn beschikking. Er geldt bijvoorbeeld een restrictie op hoeveel mest Claus mag gebruiken. De luxe kerstboom wordt niet vanzelf zo bijzonder, daar is een grote hoeveelheid mest voor nodig, namelijk 700 gram. De kleine kerstbomen hebben 300 gram mest nodig, de grote varianten 400 gram. Claus mag in totaal 200 kilo mest gebruiken. Dit is de eerste restrictie die we tegenkomen in het productieproces van Claus. De formule voor deze mestrestrictie wordt dan:
0,2 * K + 0,3 * G + 0,7 * L < 200
Santa Claus & zijn grond
Uiteraard hebben kerstbomen ook grond nodig om te kunnen groeien. De kleine kerstboom heeft 2 vierkante meter nodig. De grote kerstboom en de luxe kerstboom hebben beide 3 vierkante meter nodig. Claus heeft 1000 vierkante meter grond in zijn bezit. Hij kan echter besluiten om van zijn buurman 300 vierkante meter extra grond te huren. Dat kost hem 700 euro. De beslissing of hij de grond huurt noteren we met H. H is gelijk aan 1 als de grond wordt gehuurd en aan 0 als de grond niet wordt gehuurd. Deze grondrestrictie kunnen we dus vatten in de volgende formule:
2 * K + 3 * G + 3 * L < 1000 + 300 * H, ofwel 2 * K + 3 * G + 3 * L – 300 * H < 1000.
Meneer S. Claus’ reputatie
We moeten niet vergeten de kosten van de huur op te nemen in onze doelfunctie. Deze moet namelijk van de totale winst op de kerstbomen af worden gehaald, om de daadwerkelijke winst te krijgen. De formule van de doelfunctie passen we dus iets aan naar:
10 * K + 15 * G + 20 * L – 700 * H
Claus wil daarnaast een goede reputatie hebben en daarom wil hij dat de klant keuze heeft. Om die reden produceert hij van elke soort minimaal 50 bomen. Ofwel een minimale productierestrictie:
K ≥ 50, G ≥ 50, L ≥ 50
Claus’ winst bepalen met Linear Programming
Met de formules hierboven kunnen we de aantallen van elke kerstboom bepalen, zodat meneer Claus weet wat hij moet verbouwen om zoveel mogelijk winst te behalen. We willen dus de waarden van K, G, L en H vaststellen zodat de winst zo hoog mogelijk is, gegeven de restricties. Dit doen we met behulp van een ‘solver’. Dit is wiskundige software waarmee Linear Programs kunnen worden opgelost. In deze solver vullen we de doelfunctie en de restricties in. De solver rekent voor ons uit hoeveel kerstbomen er geproduceerd moeten worden, of het extra land gehuurd moet worden en wat de winst is.
Zo komen we erachter dat Claus 51 kleine, 322 grote en 116 bijzondere, luxe kerstbomen moet produceren om de meeste winst te behalen en dat hij daarvoor het extra land wel moet huren. Meneer S. Claus is blij: uit de oplossing van Linear Programming blijkt ook dat hij dit jaar een winst maakt van 6.660 euro!
Wil jij aan de slag met Linear Programming?
Bij CQM kunnen we op deze manier (en nog via vele andere mogelijkheden!) bijna alle vraagstukken omzetten naar wiskunde (en dus oplossen), ook als de vragen moeilijker worden dan de kerstbomenhandel van meneer Claus. Denk bijvoorbeeld aan het creëren van een zo efficiënt mogelijk productieproces, de optimale inzet van personeel en materieel, de kortste route om pakketjes te bezorgen of een zo goed mogelijke inrichting van een warehouse.
Welke vraag je ook hebt, Heleen van Beek kijkt graag samen met jou naar de beste oplossing!
P.S. Dit omzetten van een proces naar wiskunde is trouwens zelfs inzetbaar op je dagelijkse leven: hoe zorg je dat je zo snel mogelijk klaar bent met koken? Wat is de meest efficiënte volgorde om je familie te bezoeken in het weekend, onder de voorwaarde dat zij óók op dat tijdstip kunnen? Wat is de kortste route in de supermarkt om al je boodschappen te verzamelen? Ja, onze CQM’ers optimaliseren graag zoveel mogelijk ;-)
CQM op LinkedIn volgen en nooit meer iets missen?
Wil je op de hoogte blijven van het laatste nieuws van CQM, volg ons op LinkedIn of meld je aan voor onze digitale nieuwsbrief.
Fotocredit: Pixabay.
