De simplexmethode (of het simplexalgoritme) is een methode in de wiskundige optimalisatie (zie ook operationeel onderzoek). De techniek werd in 1947 door George Dantzig ontwikkeld. De simplexmethode lost een lineair-optimaliseringsprobleem in een eindig aantal stappen op, of stelt de onoplosbaarheid van het probleem vast. In theoretische gevallen kunnen cycli optreden, die het vinden van de optimale oplossing verhinderen. De naam komt van het feit dat de vergelijkingen van het probleem een simplex beschrijven, waarvan de rand bij het vinden van de oplossing beschreven wordt.
Geschiedenis De Russische wiskundige Leonid Kantorovich behandelde in 1939 als eerste lineaire optimalisatie in zijn boek "Wiskundige Methoden in de Organisatie en Planning van de Productie". Kort daarna presenteerde de Amerikaan F.L. Hitchcock een werk over een transportprobleem. Toen erkende men echter nog niet de betekenis van dit werk.
De doorbraak voor de simplexmethode kwam er door George Dantzig in 1947, toen ook hij een werk over lineaire optimalisatie publiceerde. In eerste instantie toonden het Amerikaanse Leger, in het bijzonder de US Air Force, interesse in dit werk - men wilde de militaire acties optimaliseren. De daaropvolgende jaren ontwikkelden John von Neumann en Oskar Morgenstern het algoritme verder.
Met de opkomst van computers halverwege de jaren 50 kon men grotere problemen oplossen. Men ontwikkelde speciale varianten van de simplexmethode die op de eigenschappen van de computers uit die tijd afgesteld waren. Ze gingen bijvoorbeeld heel zuinig om met het gebruik van het hoofdgeheugen.
Gelijktijdig - na 1950 - ontdekte de industrie dat men met de simplexmethode ook optimalisatieproblemen in hun domein kon oplossen. In het bijzonder gebruiken olieraffinaderijen de methode. In 1960 optimaliseerde W. Knödel de toelevering van de suikerfabrieken in Oostenrijk. Daarmee verlaagde hij de transportkosten met ongeveer 10 procent.
Definitie van het lineair optimalisatieprobleem Maximaliseer de doelfunctie onder de nevenvoorwaarden en . Daarbij zijn A: m×n-matrix a: n-dimensionale vector b: m-dimensionale vector gegeven parameter, en de doelfunctie is als scalair product een lineaire functie in .
De doelfunctie wordt ook wel objectief genoemd, de nevenvoorwaarden ook wel restricties.
is hier de notatie van een matrixvermenigvuldiging. De 'ongelijkheden' en moeten component per component opgevat worden, bijvoorbeeld , met , betekent hetzelfde als .
Die punten (vectoren) die aan alle nevenvoorwaarden tegelijkertijd voldoen (dit zijn geldige oplossingen van het probleem) vormen een convexe polyeder in de n-dimensionale ruimte, een zogeheten simplex. Wanneer er geen geldige oplossingen zijn, spreken de nevenvoorwaarden elkaar tegen en is het probleem niet oplosbaar.
Wanneer de verzameling geldige oplossingen niet leeg is, zijn er twee mogelijkheden: De doelfunctie G heeft in de toegelaten punten een bovengrens:Hier kan men zien dat het maximum van de doelfunctie door een punt op de rand van de geldige verzameling ingenomen wordt, en wel door een hoekpunt. Het simplexalgoritme verplaatst zich, vertrekkend van een geldige beginoplossing, langs de hoekpunten van de polyeder naar zijn optimale oplossing. De doelfunctie G is niet naar boven begrensd: In dat geval stelt men vast dat er een oneindig lange zijde van de polyeder met oneindige toenemende doelfunctie bestaat. Men zegt dat de optimale waarde van de doelfunctie is, en men kan geen optimale oplossing daarvoor geven.
Wanneer geen geldige beginoplossing gekend is, kan men een lichtjes aangepast lineair optimaliseringsprobleem gebruiken, om een beginoplossing te vinden, en voor de vaststelling van de oplosbaarheid van het probleem. (De zogenoemde Fase I met kunstmatige variabelen).
Bij veel probleemstellingen komt het voor dat men de doelfunctie G niet wil maximaliseren, maar wil minimaliseren. Bijvoorbeeld moeten bij een transportprobleem de transportkosten zo klein mogelijk zijn, of moet de wegen zo kort mogelijk zijn. In dit geval voert men eenvoudigweg een nieuwe doelfunctie in, en men maximaliseert deze.
Voorbeeld Aan de hand van een eenvoudig voorbeeld wordt de oplossingsmethode stap voor stap getoond. Reële problemen kunnen meer dan duizend randvoorwaarden hebben, waar men niet onmiddellijk eventuele tegenstellingen in kan herkennen, of dus niet direct het bestaan van een geldige beginoplossing kan vinden.
Probleemstelling in woorden Een firma biedt 2 verschillende producten aan. Er staan 3 machines A, B en C ter beschikking. Machine A heeft een maximale maandelijkse looptijd (capaciteit) van 170 uur, machine B van 150 uur en machine C van 180 uur. Een eenheid van product 1 geeft een winstbijdrage van 300 euro, een eenheid van product 2 daarentegen 500 euro. De vaste kosten bedragen 36.000 euro per maand. Als men 1 eenheid van product 1 vervaardigt, dan gebruikt men daarvoor 1 uur machine A en daarna 1 uur machine B. 1 eenheid van product 2 vereist achtereenvolgens 2 uur machine A, 1 uur machine B en 3 uur machine C.
Wiskundige formulering met ongelijkheden
Stel dat het bedrijf per maand x1 eenheden van product 1 en x2 eenheden van product 2 vervaardigt, dan bedraagt de opbrengst (winst of verlies)
G = 300x1 + 500x2 - 36.000
Deze opbrengst wil het bedrijf maximaliseren.
Aangezien de capaciteit van de machines begrensd is, kan men geen willekeurig grote hoeveelheden produceren. Uit de bezettingstijden leidt men de volgende nevenvoorwaarden voor x1 en x2 af:
1•x1 + 2•x2 ≤ 170 machine A 1•x1 + 1•x2 ≤ 150 machine B 0•x1 + 3•x2 ≤ 180 machine C
Negatieve productiehoeveelheden zijn niet mogelijk, dus gelden nog de nevenvoorwaarden
x1 ≥ 0 x2 ≥ 0
Omzetten in gelijkheden Omdat het met stelsels gelijkheden gemakkelijker rekenen is, worden de ongelijkheden in gelijkheden omgezet. Daartoe voert men de zogenoemde slackvariabelen yA, yB en yC in, die de niet benutte tijd van de respectievelijke machines voorstellen. Men vormt bijvoorbeeld de nevenvoorwaarde voor machine A in volgende gelijkheid om
yA + x1 + 2•x2 = 170
Vanzelfsprekend mogen de slackvariabelen niet negatief zijn (niet-negativiteitsvoorwaarde).
Het probleem kan nu op volgende manier geformuleerd worden:
Maximaliseer de doelfunctie G onder de volgende nevenvoorwaarden: G - 300x1 - 500x2 = - 36.000 yA + x1 + 2x2 = 170 yB + x1 + x2 = 150 yC + 3x2 = 180
yA, yB, yC, x1, x2 ≥ 0
Het Simplex-Tableau Deze vergelijkingen plaatst men in een zogeheten simplex-tableau, dat een verkorte voorstelling van het bijhorende stelsel van vergelijkingen is. Alle volgende bewerkingen zijn wiskundige berekeningen met het stelsel vergelijkingen.
+--------------+------------- | x1 x2 | rechterlid ----+--------------+------------- G | -300 -500 | -36000 ----+--------------+------------- YA | 1 2 | 170 = b1 YB | 1 1 | 150 = b2 YC | 0 3 | 180 = b3
De variabelen in de titelrij (x1, x2) heten niet-basisvariabelen, de variabelen in de eerste kolom basisvariabelen (YA, YB, YC). De getallen in "rij G" - de vergelijking van de doelfunctie - zijn de coëfficiënten van de doelfunctie. De variabelen b1, b2 en b3 bevatten de waarde van de rechterleden.
Bepaling van een geldige beginoplossing Vervolgens bepaalt men een geldige oplossing. Dat zijn waarden voor x1 en x2 die aan alle nevenvoorwaarden voldoen.
Men kan in dit geval onmiddellijk een triviale oplossing geven, namelijk
x1 = 0 x2 = 0
Deze oplossing wordt in het bovenstaande tableau opgenomen. x1 en x2 zijn de niet-basisvariabelen en hebben steeds de waarde "0". De basisvariabelen hebben de waarde van de onbenutte machinelooptijden. Aangezien met de beginoplossing niets geproduceerd wordt: YA = 170, YB = 150, YC = 180. Deze beginoplossing is natuurlijk onbevredigend: er wordt niet geproduceerd, de opbrengst G bedraagt -36.000 euro, wat verlies betekent. Daarom moet men proberen om betere geldige oplossingen te vinden.
Verbetering van de oplossing door middel van een simplex-iteratie In een iteratie van het simplexalgoritme wordt een basisvariabele met een niet-basisvariabele omgewisseld. Dit is een verwisselingsstap.
In aanmerking komen niet-basisvariabelen die een negatieve coëfficiënt in de doelfunctie hebben. Tussen deze variabelen zoekt men die variabele die bij omwisseling de grootste toename van de doelfunctie levert. Stel k het nummer van de kolom van de te verwisselen niet-basisvariabele, en r het rijnummer van de te verwisselen basisvariabele. De verwisselingsstap komt overeen met juist één stap bij het oplossen van een stelsel van gelijkheden, waarbij men rij r oplost naar de variabelen xk en dan xs in de rest van de gelijkheden inzet. Stel aij een matrix-element uit de simplex-tableau, dan heet ark het Pivotelement van de tableau. Kolom k is de pivotkolom, rij r de pivotrij.
In de verwisselingsstap berekent men het nieuwe tableau op volgende wijze:
Pivotelement: (Formule 1)
Pivotrij voor j k: (2)
(3)
Pivotkolom voor i r: (4)
overige elementen: (5)
(6)
Keuze van de pivotelementen Formule (6) is bepalend voor de keuze van de pivotrij r en de pivotkolom k. Men zoekt die waarden voor r en k waarvoor de coëfficiënt van de doelfunctie met index k negatief is, en waarvan de waarde van
zo groot mogelijk wordt. Daarbij dient men op te merken dat na de verwisseling de ontstane oplossing nog steeds geldig moet zijn, dit betekent dat alle nevenvoorwaarden vervuld moeten blijven. Daartoe kiest men r en k zodanig dat het quotiënt
met
binnen een kolom minimaal wordt.
Kolom 1 heeft een negatieve coëfficiënt van de doelfunctie van -300, en komt als pivotkolom k in aanmerking. Berekening van de coëfficiënten van deze kolom 1: rij 1: 170 / 1 = 170 rij 2: 150 / 1 = 150 rij 3: a31 = 0, daar geen quotiënt berekenbaar. Het kleinste quotiënt 150 krijgt men dus in rij 2. Met pivotelement a2,1 berekent men de nieuwe waarde van de doelfunctie als
.
Ook kolom 2 heeft met -500 een negatieve coëfficiënt in de doelfunctie, en komt eveneens als pivotkolom k in aanmerking.De berekeningen van de coëfficiënten van deze kolom 2: rij 1: 170 / 2 = 85 rij 2: 150 / 1 = 150 rij 3: 180 / 3 = 60 Het kleinste quotiënt 60 wordt gevonden in rij 3. Met het mogelijke pivotelement a3,2 berekent men de nieuwe waarde van de doelfunctie als
.
Het is dus gunstiger om als pivotelement het eerste getal uit rij r = 2 en kolom k = 1 te kiezen, aangezien men daarmee de doelfunctie het meest doet toenemen, namelijk van -36000 naar 9000.
Uitvoeren van een verwisselingsstap In de verwisselingsstap wordt de basisvariabele YB met de niet-basisvariabele x1 verwisseld.
Het simplex-tableau wordt volgens de bovenstaande regels omgerekend.
Het pivotelement is a2,1 = 1.
Berekening van de pivotelementen: a2,1 = 1 / 1 = 1 (met formule (1))
Berekening van de pivotrij r = 2: Elk element wordt door het pivotelement gedeeld. Kolom 1 bevat het pivotelement, en werd zonet berekend. Kolom 2: a2,2 = 1 / 1 = 1 (met formule (2)) rechterlid: b2 = 150 / 1 = 150 (met formule (3))
Berekening van de pivotkolom k = 1: Elk element wordt door het pivotelement gedeeld, het teken wordt omgekeerd. Doelfunctie: - (-300 / 1) = 300 Rij 1: a1,1 = - (1 / 1) = -1 (met formule (4)) Rij 2 is de pivotrij en werd reeds berekend Rij 3: a3,1 = (- (0 / 1) = 0
Berekening van de overige waarden - kolom 2, aangezien kolom 1 reeds berekend is: Doelfunctie kolom 2: -500 - (-300 × 1) /1 = -200 Rij 1 kolom 2: a1,2 = 2 - 1×1 / 1 = 1 (met formule (5)) Rij 2 kolom 2 behoort tot de pivotrij en is reeds berekend. Rij 3 kolom 2: a3,2 = 3 - 0×1 / 1 = 3
rechterlid: doelfunctie: G = -36000 - (-300 × 150) / 1 = 9000
Rij 1: b1 = 170 - 1×150 / 1 = 20 (met formule (6)) Rij 2 behoort tot de pivotrij en is al berekend Rij 3: b3 = 180 - 0×150 / 1 = 180
Het nieuwe simplex-tableau Na omrekening verkrijgt men een nieuw simplex-tableau:
+--------------+------------ | YB x2 | rechterlid ----+--------------+------------