Lineair programmeren is niet alleen maar abstracte wiskunde. Het is de motor achter logistiek, toeleveringsketens en hulpbronnenbeheer. De kern is de simplexmethode. Deze standaardtechniek vindt de best mogelijke uitkomst in een systeem dat wordt gedefinieerd door beperkingen en een objectieve functie.
Denk er zo over na. Je hebt een doel. Misschien maximaliseert het de winst of minimaliseert het de kosten. Je hebt ook grenzen. Machine-uren. Grondstoffen. Werk. De simplexmethode navigeert door deze limieten om de piek te vinden. Het raadt niet. Het berekent.
Waarom we een systematische aanpak nodig hebben
Je zou kunnen denken dat je gewoon twee variabelen in een grafiek kunt zetten en kunt zien waar ze elkaar kruisen. Dat werkt voor eenvoudige problemen. Een fabriek die twee producten maakt. Je tekent lijnen. Je vindt de hoek waar de winst piekt. Het is visueel. Het is intuïtief.
Maar de werkelijkheid is zelden tweedimensionaal. Bij echte problemen zijn honderden vergelijkingen en duizenden variabelen betrokken. Het aantal mogelijke oplossingen wordt astronomisch. Een grafiek tekenen voor duizend variabelen is onmogelijk. Je hebt dimensies nodig die je niet kunt waarnemen.
George Dantzig loste dit in 1947 op. Hij werkte als wiskundig adviseur voor de Amerikaanse luchtmacht. Het leger had enorme logistieke problemen. Ze moesten de aanvoerroutes en de toewijzing van middelen optimaliseren. Dantzig bedacht de simplex-methode om de ruis te doorbreken.
De methode beperkt het aantal extreme punten dat moet worden onderzocht. Het maakt van een onmogelijke taak een beheersbare taak. Het blijft tegenwoordig het standaardalgoritme op computers. Een van de nuttigste tools ooit uitgevonden.
Hoe de Simplex-methode stap voor stap werkt
Het proces is systematisch. Het gaat van de ene mogelijkheid naar de andere. Hier ziet u hoe het zich in de praktijk ontvouwt.
Ten eerste gaat het ervan uit dat je een startpunt hebt. Een extreem punt. Als je die niet hebt, vindt een variant genaamd Fase I een haalbaar startpunt of stelt vast dat er geen oplossing bestaat.
Vervolgens test de methode dat punt. Is het optimaal? De algebraïsche specificatie van het probleem voert deze controle uit. Als de test mislukt, verplaatst het algoritme zich naar een aangrenzend uiterste punt. Het beweegt langs een rand. Het kiest de richting waarin de doelfunctie het snelst toeneemt.
Soms neemt de functie onbeperkt toe. De procedure stopt en identificeert de rand waar de waarde naar positief oneindig gaat. Je hebt een grenzeloze oplossing gevonden.
Als dat niet gebeurt, beland je op een nieuw extreem punt. Dit punt heeft een minstens even hoge waarde als het vorige. De reeks herhaalt zich. Het gaat door totdat het een optimaal punt vindt of onbegrensdheid identificeert.
In theorie zouden de stappen exponentieel kunnen groeien met het aantal extreme punten. In de praktijk verloopt de convergentie snel. Meestal is er slechts een klein veelvoud van het aantal extreme punten nodig.
Een concreet voorbeeld: het maximaliseren van de fabriekswinst
Laten we eens naar een tastbaar geval kijken. Een fabriek produceert twee producten. We noemen ze x1 en x2. De winst op het tweede type is tweemaal zo groot als die van het eerste. De totale winst wordt weergegeven door de vergelijking:
x1 + 2×2
Dit is je objectieve functie. Je wilt het maximaliseren.
Natuurlijk zou je slechts x2 willen maken. Het levert per eenheid meer geld op. Maar er zijn beperkingen. Je kunt niet zomaar oneindig produceren.
Dit zijn de echte limieten:
- Grondstof voor x2 beperkt de productie tot vijf eenheden per batch (x2 ≤ 5).
- Grondstof voor x1 beperkt de productie tot acht eenheden per batch (x1 ≤ 8).
- Machinetijd maakt maximaal tien totale eenheden mogelijk (x1 + x2 ≤ 10).
- Je kunt geen negatieve bedragen produceren (x1 ≥ 0 en x2 ≥ 0).
De simplexmethode vindt de waarden van x1 en x2 die de winst binnen deze grenzen maximaliseren. Elke oplossing is een paar getallen (x1, x2). Het produceren van drie van x1 en zes van x2 is bijvoorbeeld een geldig punt (3, 6).
Wanneer deze beperkingen in een grafiek worden uitgezet, vormen ze een veelhoekig gebied. Dit is de haalbare oplossingsset. Punten buiten dit gebied schenden een of meer beperkingen.
Om te zien hoe de simplexmethode het optimale hoekpunt identificeert, beschouw de objectieve functie x1 + 2×2 = k. Als je k op 4 instelt, krijg je een lijn in de grafiek. Naarmate je k vergroot, krijg je parallelle lijnen. De hoogste waarde van k die nog steeds het haalbare gebied raakt, is de maximaal mogelijke winst.
In dit voorbeeld raakt de lijn voor k = 15 het gebied op het punt (5, 5). Als k hoger is, valt de lijn buiten de haalbare verzameling. De optimale oplossing is het produceren van gelijke hoeveelheden van elk product.
Waarom hoekpunten belangrijk zijn bij lineaire programmering
Het resultaat is geen toeval. Bij lineaire problemen vindt de optimale oplossing altijd plaats in een hoekpunt. Een extreem punt.
Dit is een fundamentele eigenschap van lineair programmeren. De functie is lineair. De beperkingen zijn lineair. De vorm is een convexe veelhoek (of veelvlak in hogere dimensies). De piek van een lineaire functie over een convexe verzameling bevindt zich altijd in een hoek.
U hoeft niet elk punt in het haalbare gebied te controleren. U hoeft alleen de hoekpunten te controleren. De simplexmethode doet precies dit. Het springt van hoekpunt naar hoekpunt. Het beklimt het oppervlak van het haalbare gebied. Het stopt als het niet hoger kan.
Soms is het optimale niet uniek. Een hele rand kan dezelfde maximale waarde opleveren. Maar de simplexmethode zal nog steeds een van die optimale punten vinden. Het geeft je een concreet antwoord. Bruikbare gegevens.
Voor zowel studenten als professionals is het begrijpen van dit mechanisme van cruciaal belang. Het gaat niet alleen om het oplossen van vergelijkingen. Het gaat erom dat je weet hoe je met beperkte middelen door complexe systemen moet navigeren. De simplexmethode levert het pad.
De simplexmethode raadt niet alleen antwoorden. Het loopt langs de randen van een haalbaar gebied en controleert de hoekpunten totdat het de beste vindt. Het begint met het opschonen van de wiskunde. Je neemt die rommelige lineaire ongelijkheden en verandert ze in schone gelijkheden. U doet dit door ‘slappe variabelen’ toe te voegen.
Beschouw speling als overgebleven capaciteit. Als je een beperking hebt zoals $x_1 \le 8$, voeg je een variabele $x_3$ toe zodat $x_1 + x_3 = 8$. En onthoud: $x_3$ moet groter zijn dan of gelijk zijn aan nul. Dit doe je voor elke beperking.
- $x_1 + x_3 = 8$ (met $x_3 \ge 0$)
- $x_2 + x_4 = 5$ (met $x_4 \ge 0$)
- $x_1 + x_2 + x_5 = 10$ (met $x_5 \ge 0$)
Je hebt ook een variabele nodig voor de doelfunctie zelf. Laten we het $x_0$ noemen. Als het je doel is om $x_0 = x_1 + 2x_2$ te maximaliseren, herschrijf je het als $x_1 + 2x_2 – x_0 = 0$.
Nu is het probleem eenvoudiger. Zoek niet-negatieve waarden voor $x_1$ tot en met $x_5$. Maak $x_0$ zo groot mogelijk.
Beginnend bij de oorsprong
Waar begin je? De gemakkelijkste plek is de oorsprong. Zet alle beslissingsvariabelen op nul. $x_1 = 0$. $x_2 = 0$.
Dit is een geldige oplossing. Het is een extreem punt. In feite is het de starthoek. De objectieve waarde $x_0$ is eveneens nul. Niet geweldig, maar het is een legale zet.
Kunnen wij het beter doen? Ja. Als u een van de variabelen vanaf nul verhoogt terwijl u de andere op nul houdt, gaat $x_0$ omhoog. De vraag is welke variabele u de meeste waar voor uw geld geeft.
Kijk naar de objectieve vergelijking: $x_1 + 2x_2 – x_0 = 0$. Herschikken voor $x_0$, je krijgt $x_0 = x_1 + 2x_2$.
Het verhogen van $x_1$ voegt 1 toe aan het totaal. Het verhogen van $x_2$ voegt 2 toe. $x_2$ is de duidelijke winnaar. Het levert de grootste stijging op van $x_0$ per eenheidsverandering. Dus je kiest $x_2$ en duwt het omhoog.
Het bereiken van de eerste beperking
Je kunt $x_2$ niet eeuwig verhogen. De variabelen moeten niet-negatief blijven. Als je $x_2$ voorbij de 5 duwt, gaat er iets kapot. Kijk specifiek naar de tweede beperking: $x_2 + x_4 = 5$.
Als $x_2 = 6$, dan wordt $x_4$ -1. Dat is niet toegestaan. De niet-negativiteitsvereiste fungeert als een harde stop. De limiet is 5.
Je stelt dus $x_2 = 5$ in. Hoe ziet de oplossing er nu uit?
- $x_2 = 5$
- $x_1 = 0$ (nog steeds nul)
- $x_4 = 0$ (deze variabele heeft de limiet bereikt, dus deze is nu nul)
- $x_3 = 8$ (sinds $0 + 8 = 8$)
- $
