Als manager van een bedrijf heb je altijd eindige of beperkte middelen, en het topmanagement verwacht dat jij daar het maximale uithaalt. Van tijdsproductiviteit tot kapitaalbenutting, land tot arbeid, en van supplychain tot productie—bijna alles wat je doet, draait om het optimaliseren van de productiviteit.
Veel luchtvaartmaatschappijen optimaliseren vluchtschema’s om de hoogste opbrengst en de laagste kosten te realiseren. Deze schema’s omvatten tal van situaties en beperkingen, zoals het aantal vliegtuigen op een bepaalde locatie, brandstof, bemanning en het type route (populaire en winstgevende routes). Deze situaties en beperkingen staan bekend als de constraints voor het vliegen op de meest populaire en winstgevende route. Lineaire programmering wordt gebruikt om de oplossing te vinden voor het gegeven, begrensde probleem.
In deze tutorial leer je over lineaire programmering en komen de volgende onderwerpen aan bod:
Wiskundig gezien optimaliseert lineaire programmering (minimaliseert of maximaliseert) de lineaire doelstelling van meerdere variabelen, onder de gegeven voorwaarden/constraints die voldoen aan een stel lineaire ongelijkheden. Lineaire programmering kan worden toegepast bij het plannen van economische activiteiten, zoals het vervoer van goederen en diensten, het produceren van producten, het optimaliseren van elektrische energiesystemen en netwerkstromen. LP-problemen kunnen worden opgelost met verschillende technieken, zoals de grafische methode, de simplex-methode en de methode van Karmarkar.
Basale concepten van LPP
Laten we de basisbegrippen van lineaire programmering bekijken:
Beslissingsvariabelen zijn de variabelen die gebruikt worden als functie in de doelstellingsfunctie. Deze variabelen bepalen je uitkomst. De beslisser kan de waarde van een doelstellingsfunctie sturen met de beslissingsvariabele. Als je een probleem in lineaire programmering oplost, moet je eerst de beslissingsvariabelen identificeren.
Constraints zijn een reeks beperkingen of situationele voorwaarden. Constraints kunnen gelijkheden of ongelijkheden zijn. Ze begrenzen de waarde van beslissingsvariabelen.
De doelstellingsfunctie is een winst- of kostfunctie die je maximaliseert of minimaliseert. Het is het hoofddoel van het nemen van beslissingen.
De optimale oplossing is een van de toelaatbare oplossingen waarbij de doelstellingsfunctie óf maximaal óf minimaal is, bijvoorbeeld maximale winst of minimale kosten. Het is de beste waarde van de doelstellingsfunctie.
Een toelaatbare oplossing is de set mogelijke waarden voor beslissingsvariabelen die aan alle constraints voldoet. Een LP-probleem is toelaatbaar als er ten minste één oplossing toelaatbaar is.
De niet-toelaatbare oplossing is de set mogelijke waarden voor beslissingsvariabelen die niet aan alle constraints voldoet; er is dus geen optimale oplossing. Een LP-probleem is niet-toelaatbaar als er geen oplossing bestaat die aan alle constraints voldoet.
De toelaatbare regio is een gebied dat wordt afgebakend door alle mogelijke sets waarden die aan de constraints voldoen, ofwel de doorsnede van alle constraints. Het omvat alle ongelijkheden, gelijkheden en integer-constraints.
Niet-negativiteitsconstraints voor beslissingsvariabelen accepteren alleen niet-negatieve waarden. Dergelijke constraints zijn groter dan of gelijk aan nul.
LPP-probleemformulering (met voorbeeld)
Het formuleren van modellen voor lineaire programmering omvat de volgende stappen:
Identificeer de beslissingsvariabelen
Bepaal de doelstellingsfunctie
Identificeer de constraints
Definieer de niet-negativiteitsconstraints
In een probleem van lineaire programmering moeten de beslissingsvariabelen, de doelstellingsfunctie en de constraints allemaal lineaire functies zijn
Probleembeschrijving: Een meubelhandelaar handelt in slechts twee artikelen—tafels en stoelen. Hij heeft 50.000 roepies om te investeren en opslagruimte voor maximaal 60 stuks. Een tafel kost 2.500 roepies en een stoel 500 roepies. Hij schat dat hij met de verkoop van één tafel 250 roepies winst kan maken en met de verkoop van één stoel 75 roepies winst. Hij wil weten hoeveel tafels en stoelen hij moet kopen met het beschikbare geld om zijn totale winst te maximaliseren, ervan uitgaande dat hij alle gekochte items kan verkopen. (Bron)
In dit voorbeeld zie je dat —
De handelaar zijn geld kan investeren in het kopen van tafels of stoelen of een combinatie van beide. Verder behaalt hij verschillende winsten bij verschillende investeringsstrategieën. (Bron)
Zijn investering is beperkt tot maximaal 50.000 roepies en hetzelfde geldt voor zijn opslagruimte, die maximaal 60 stuks bedraagt. (Bron)
Wiskundige formulering:
Stel dat hij besluit alleen tafels te kopen en geen stoelen. Dan kan hij 50000/2500 = 20 tafels kopen. In dit geval verdient hij een winst van 250 x 20 = 5.000 roepies. Of hij besluit alleen stoelen te kopen en geen tafels. Dan kan hij 50000/500 = 100 stoelen kopen.
In dit geval verdient hij een winst van 75 x 60 = 4.500 roepies.
Er zijn veel combinaties van tafels en stoelen mogelijk die hij kan kopen.
Stel dat hij X tafels en Y stoelen koopt. Dan moeten X en Y niet-negatief zijn.
De handelaar heeft maximaal 50.000 roepies om tafels en stoelen te kopen, dus —
2500 X + 500 Y <= 50000 (investeringsconstraints) of 5 * X + Y <= 100 .................................................................. Verg.1
Het maximale aantal stuks dat hij kan opslaan is 60.
X + Y <= 60 .................................................................. Verg.2
De handelaar wil in zulke hoeveelheden inkopen dat hij zijn winst Z kan maximaliseren; de vergelijking wordt dus —
Stap 1: Laten we de functie in Excel schrijven zoals hieronder getoond.
Stap 2: Nadat je de doelstellingsfunctie en constraints in de spreadsheet hebt gezet, berekenen we de waarden voor constraints C1 en C2. Je kunt waarden berekenen door de andere variabele op nul te zetten. Bijvoorbeeld voor C1: bij X = 0 is de waarde van Y gelijk aan Y = 100 en bij Y = 0 is de waarde van X gelijk aan X = 20. Vergelijkbaar voor constraints C2.
Stap 3: Nu we de waarden hebben berekend, plotten we de grafiek. Selecteer de waarden van constraint C1, ga naar Invoegen en maak een spreidingsdiagram met vloeiende lijnen. Je grafiek kan er zo uitzien.
Als het er zo uitziet, geen zorgen—volg de onderstaande stappen om dit te wijzigen. Klik met de rechtermuisknop op de grafiek, ga naar Gegevens selecteren; je ziet daar twee reeksen, verwijder Reeks 2 en bewerk Reeks 1.
Noem de reeks C1 en wijzig de X-waarde in de A-kolomwaarden van C1 en de Y-waarde in de B-kolomwaarden van C1. Klik op OK. Je grafiek ziet er nu uit zoals hieronder:
Stap 4: Ga opnieuw naar Gegevens selecteren door met de rechtermuisknop op de grafiek te klikken en voeg een andere reeks toe. Noem deze C2 en selecteer bij X-waarden de X-kolomwaarden van constraint C2 en bij Y-waarden de Y-kolomwaarden van C2. Je grafiek zal er nu zo uitzien:
Stap 5: Nu is de grafiek geplot en moet je kijken naar de toelaatbare regio:
Je hebt nu 4 punten (O, A, B, C) in het gebied van de toelaatbare regio. Je moet de waarden van de doelstellingsfunctie op alle punten berekenen om te zien welk punt je de maximale waarde van de doelstelling geeft.
Stap 6: Volg de onderstaande stappen om de waarden van de doelstellingsfunctie te berekenen:
Bereken de doelstellingsfunctie voor elke puntwaarde:
Bij punt O zijn de coördinaten van (X, Y) gelijk aan (0, 0). De waarde van de doelstellingsfunctie is dus = (2500+750) = 0
Bij punt A zijn de coördinaten van (X, Y) gelijk aan (0, 60). De waarde van de doelstellingsfunctie is dus = (2500+753) = 4500
Bij punt B zijn de coördinaten van (X, Y) gelijk aan (20, 0). De waarde van de doelstellingsfunctie is dus = (2503+750) = 5000
Bij punt C: om de coördinaten bij punt Z te vinden, moet je het snijpunt van de lijnen van constraints C1 en C2 bepalen. Je gebruikt de functies MMULT() en MINVERSE() om het snijpunt van twee vergelijkingen te berekenen.
MMULT(MINVERSE(array),array) # Dit geeft de waarden van de oplossing van vergelijkingen met twee variabelen. Of: =MMULT(MINVERSE(AB17:AC18), AE17:AE18). Selecteer, voordat je deze formule gebruikt, de cellen voor X- en Y-waarden (geel gemarkeerde cellen) en gebruik deze functie om het snijpunt van twee vergelijkingen te berekenen en druk op CTRL+SHIFT+ENTER
De uiteindelijke waarden van Z:
Zoals je hier ziet in dit lineaire maximalisatieprobleem, krijg je de maximale waarde van Z bij punt B, en de maximale waarde is 6.250 roepies. Om de winst te maximaliseren, moet de handelaar dus 10 tafels en 50 stoelen kopen.
Use-cases van LPP
Lineaire programmering wordt toegepast om optimale oplossingen te vinden voor operations research. LP kan de meest optimale oplossing vinden binnen gegeven constraints en beperkingen. LP is toepasbaar op allerlei problemen, zoals economische activiteiten in landbouw, techniek, productie, energie, logistiek en supplychain.
Ingenieurs passen lineaire programmering toe in de maak- en productie-industrie om beschikbare middelen te optimaliseren, waardoor maximale winst mogelijk wordt.
De logistieke en transportsector gebruikt lineaire programmering om het kortste pad/de kortste route, reistijd en prijsstrategie te bepalen.
Ingenieurs passen lineaire programmering toe in de energiesector. Ze optimaliseren de elektrische belasting, de kortste distributielijnen en ook het ontwerp van het elektriciteitsnet.
In de landbouwsector kan lineaire programmering door ingenieurs worden gebruikt om het type en de hoeveelheid gewas te bepalen die ze moeten telen om de opbrengst efficiënt te verhogen.
In de voedingsindustrie kan lineaire programmering gezondheidsmanagers en diëtisten helpen om dieetbehoeften en een set voedingsmiddelen met lage kosten te plannen, om niet-overdraagbare ziekten te voorkomen.
Conclusie
Gefeliciteerd, je bent aan het einde van deze tutorial gekomen!
Je hebt veel details over lineaire programmering behandeld. Je leerde wat lineaire programmering is, basisconcepten en terminologie in LP, de formulering van LP-problemen, het oplossen van LP-problemen met de grafische methode en use-cases van LP.
Hopelijk kun je nu de concepten van lineaire programmering gebruiken om beslissingen te nemen in jouw organisatie of je resultaten te optimaliseren voor besluitvormers. Bedankt voor het lezen van deze tutorial!
%22%3E%3Cpath%20d%3D%22m-369%200h408v79h-408z%22%20fill%3D%22%237933ff%22%2F%3E%3Cpath%20d%3D%22m-148%200h306v45h-306z%22%20fill%3D%22%23974dff%22%2F%3E%3C%2Fg%3E%3C%2Fsvg%3E)
%22%2F%3E%3C%2FclipPath%3E%3Cg%20clip-path%3D%22url(%23a)%22%3E%3Cpath%20d%3D%22m76%200h484v36h-484z%22%20fill%3D%22%23974dff%22%2F%3E%3Cpath%20d%3D%22m0%200h384v24h-384z%22%20fill%3D%22%2306bdfc%22%20transform%3D%22matrix(1%200%200%20-1%200%2060)%22%2F%3E%3C%2Fg%3E%3C%2Fsvg%3E)
Adel Nehme · 15 min
Als manager van een bedrijf heb je altijd eindige of beperkte middelen, en het topmanagement verwacht dat jij daar het maximale uithaalt. Van tijdsproductiviteit tot kapitaalbenutting, land tot arbeid, en van supplychain tot productie—bijna alles wat je doet, draait om het optimaliseren van de productiviteit.
Veel luchtvaartmaatschappijen optimaliseren vluchtschema’s om de hoogste opbrengst en de laagste kosten te realiseren. Deze schema’s omvatten tal van situaties en beperkingen, zoals het aantal vliegtuigen op een bepaalde locatie, brandstof, bemanning en het type route (populaire en winstgevende routes). Deze situaties en beperkingen staan bekend als de constraints voor het vliegen op de meest populaire en winstgevende route. Lineaire programmering wordt gebruikt om de oplossing te vinden voor het gegeven, begrensde probleem.
In deze tutorial leer je over lineaire programmering en komen de volgende onderwerpen aan bod:
Introductie tot lineaire programmering
Wiskundig gezien optimaliseert lineaire programmering (minimaliseert of maximaliseert) de lineaire doelstelling van meerdere variabelen, onder de gegeven voorwaarden/constraints die voldoen aan een stel lineaire ongelijkheden. Lineaire programmering kan worden toegepast bij het plannen van economische activiteiten, zoals het vervoer van goederen en diensten, het produceren van producten, het optimaliseren van elektrische energiesystemen en netwerkstromen. LP-problemen kunnen worden opgelost met verschillende technieken, zoals de grafische methode, de simplex-methode en de methode van Karmarkar.
Basale concepten van LPP
Laten we de basisbegrippen van lineaire programmering bekijken:
Beslissingsvariabelen zijn de variabelen die gebruikt worden als functie in de doelstellingsfunctie. Deze variabelen bepalen je uitkomst. De beslisser kan de waarde van een doelstellingsfunctie sturen met de beslissingsvariabele. Als je een probleem in lineaire programmering oplost, moet je eerst de beslissingsvariabelen identificeren.
Constraints zijn een reeks beperkingen of situationele voorwaarden. Constraints kunnen gelijkheden of ongelijkheden zijn. Ze begrenzen de waarde van beslissingsvariabelen.
De doelstellingsfunctie is een winst- of kostfunctie die je maximaliseert of minimaliseert. Het is het hoofddoel van het nemen van beslissingen.
De optimale oplossing is een van de toelaatbare oplossingen waarbij de doelstellingsfunctie óf maximaal óf minimaal is, bijvoorbeeld maximale winst of minimale kosten. Het is de beste waarde van de doelstellingsfunctie.
Een toelaatbare oplossing is de set mogelijke waarden voor beslissingsvariabelen die aan alle constraints voldoet. Een LP-probleem is toelaatbaar als er ten minste één oplossing toelaatbaar is.
De niet-toelaatbare oplossing is de set mogelijke waarden voor beslissingsvariabelen die niet aan alle constraints voldoet; er is dus geen optimale oplossing. Een LP-probleem is niet-toelaatbaar als er geen oplossing bestaat die aan alle constraints voldoet.
De toelaatbare regio is een gebied dat wordt afgebakend door alle mogelijke sets waarden die aan de constraints voldoen, ofwel de doorsnede van alle constraints. Het omvat alle ongelijkheden, gelijkheden en integer-constraints.
Niet-negativiteitsconstraints voor beslissingsvariabelen accepteren alleen niet-negatieve waarden. Dergelijke constraints zijn groter dan of gelijk aan nul.
LPP-probleemformulering (met voorbeeld)
Het formuleren van modellen voor lineaire programmering omvat de volgende stappen:
In een probleem van lineaire programmering moeten de beslissingsvariabelen, de doelstellingsfunctie en de constraints allemaal lineaire functies zijn
Probleembeschrijving: Een meubelhandelaar handelt in slechts twee artikelen—tafels en stoelen. Hij heeft 50.000 roepies om te investeren en opslagruimte voor maximaal 60 stuks. Een tafel kost 2.500 roepies en een stoel 500 roepies. Hij schat dat hij met de verkoop van één tafel 250 roepies winst kan maken en met de verkoop van één stoel 75 roepies winst. Hij wil weten hoeveel tafels en stoelen hij moet kopen met het beschikbare geld om zijn totale winst te maximaliseren, ervan uitgaande dat hij alle gekochte items kan verkopen. (Bron)
In dit voorbeeld zie je dat —
Wiskundige formulering:
Stel dat hij besluit alleen tafels te kopen en geen stoelen. Dan kan hij 50000/2500 = 20 tafels kopen. In dit geval verdient hij een winst van 250 x 20 = 5.000 roepies. Of hij besluit alleen stoelen te kopen en geen tafels. Dan kan hij 50000/500 = 100 stoelen kopen.
In dit geval verdient hij een winst van 75 x 60 = 4.500 roepies.
Er zijn veel combinaties van tafels en stoelen mogelijk die hij kan kopen.
Stel dat hij X tafels en Y stoelen koopt. Dan moeten X en Y niet-negatief zijn.
De handelaar heeft maximaal 50.000 roepies om tafels en stoelen te kopen, dus —
2500 X + 500 Y <= 50000 (investeringsconstraints) of 5 * X + Y <= 100 .................................................................. Verg.1
Het maximale aantal stuks dat hij kan opslaan is 60.
X + Y <= 60 .................................................................. Verg.2
De handelaar wil in zulke hoeveelheden inkopen dat hij zijn winst Z kan maximaliseren; de vergelijking wordt dus —
Max Z : 250 X + 75 Y
Doelstellingsfunctie: Max Z: 250 X + 75 Y
Onderworpen aan constraints:
Bron: http://ncert.nic.in/ncerts/l/lemh206.pdf
Grafische methode om LPP op te lossen in een spreadsheet
Voorbeeld van lineaire programmering
Doelstellingsfunctie: Max Z: 250 X + 75 Y
Onderworpen aan constraints:
Stap 1: Laten we de functie in Excel schrijven zoals hieronder getoond.
Stap 2: Nadat je de doelstellingsfunctie en constraints in de spreadsheet hebt gezet, berekenen we de waarden voor constraints C1 en C2. Je kunt waarden berekenen door de andere variabele op nul te zetten. Bijvoorbeeld voor C1: bij X = 0 is de waarde van Y gelijk aan Y = 100 en bij Y = 0 is de waarde van X gelijk aan X = 20. Vergelijkbaar voor constraints C2.
Stap 3: Nu we de waarden hebben berekend, plotten we de grafiek. Selecteer de waarden van constraint C1, ga naar Invoegen en maak een spreidingsdiagram met vloeiende lijnen. Je grafiek kan er zo uitzien.
Als het er zo uitziet, geen zorgen—volg de onderstaande stappen om dit te wijzigen. Klik met de rechtermuisknop op de grafiek, ga naar Gegevens selecteren; je ziet daar twee reeksen, verwijder Reeks 2 en bewerk Reeks 1.
Noem de reeks C1 en wijzig de X-waarde in de A-kolomwaarden van C1 en de Y-waarde in de B-kolomwaarden van C1. Klik op OK. Je grafiek ziet er nu uit zoals hieronder:
Stap 4: Ga opnieuw naar Gegevens selecteren door met de rechtermuisknop op de grafiek te klikken en voeg een andere reeks toe. Noem deze C2 en selecteer bij X-waarden de X-kolomwaarden van constraint C2 en bij Y-waarden de Y-kolomwaarden van C2. Je grafiek zal er nu zo uitzien:
Stap 5: Nu is de grafiek geplot en moet je kijken naar de toelaatbare regio:
Je hebt nu 4 punten (O, A, B, C) in het gebied van de toelaatbare regio. Je moet de waarden van de doelstellingsfunctie op alle punten berekenen om te zien welk punt je de maximale waarde van de doelstelling geeft.
Stap 6: Volg de onderstaande stappen om de waarden van de doelstellingsfunctie te berekenen:
Bereken de doelstellingsfunctie voor elke puntwaarde:
Bij punt C: om de coördinaten bij punt Z te vinden, moet je het snijpunt van de lijnen van constraints C1 en C2 bepalen. Je gebruikt de functies MMULT() en MINVERSE() om het snijpunt van twee vergelijkingen te berekenen.
MMULT(MINVERSE(array),array) # Dit geeft de waarden van de oplossing van vergelijkingen met twee variabelen. Of: =MMULT(MINVERSE(AB17:AC18), AE17:AE18). Selecteer, voordat je deze formule gebruikt, de cellen voor X- en Y-waarden (geel gemarkeerde cellen) en gebruik deze functie om het snijpunt van twee vergelijkingen te berekenen en druk op CTRL+SHIFT+ENTER
De uiteindelijke waarden van Z:
Zoals je hier ziet in dit lineaire maximalisatieprobleem, krijg je de maximale waarde van Z bij punt B, en de maximale waarde is 6.250 roepies. Om de winst te maximaliseren, moet de handelaar dus 10 tafels en 50 stoelen kopen.
Use-cases van LPP
Lineaire programmering wordt toegepast om optimale oplossingen te vinden voor operations research. LP kan de meest optimale oplossing vinden binnen gegeven constraints en beperkingen. LP is toepasbaar op allerlei problemen, zoals economische activiteiten in landbouw, techniek, productie, energie, logistiek en supplychain.
Ingenieurs passen lineaire programmering toe in de maak- en productie-industrie om beschikbare middelen te optimaliseren, waardoor maximale winst mogelijk wordt.
De logistieke en transportsector gebruikt lineaire programmering om het kortste pad/de kortste route, reistijd en prijsstrategie te bepalen.
Ingenieurs passen lineaire programmering toe in de energiesector. Ze optimaliseren de elektrische belasting, de kortste distributielijnen en ook het ontwerp van het elektriciteitsnet.
In de landbouwsector kan lineaire programmering door ingenieurs worden gebruikt om het type en de hoeveelheid gewas te bepalen die ze moeten telen om de opbrengst efficiënt te verhogen.
In de voedingsindustrie kan lineaire programmering gezondheidsmanagers en diëtisten helpen om dieetbehoeften en een set voedingsmiddelen met lage kosten te plannen, om niet-overdraagbare ziekten te voorkomen.
Conclusie
Gefeliciteerd, je bent aan het einde van deze tutorial gekomen!
Je hebt veel details over lineaire programmering behandeld. Je leerde wat lineaire programmering is, basisconcepten en terminologie in LP, de formulering van LP-problemen, het oplossen van LP-problemen met de grafische methode en use-cases van LP.
Hopelijk kun je nu de concepten van lineaire programmering gebruiken om beslissingen te nemen in jouw organisatie of je resultaten te optimaliseren voor besluitvormers. Bedankt voor het lezen van deze tutorial!
Bekijk ook onze tutorial Grafieken in spreadsheets.
Als je meer wilt leren over spreadsheets, volg dan de volgende DataCamp-cursussen: