Simplexmethode

Van Wikipedia

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 lineaire optimaliseringsprobleem in een eindig aantal stappen op, of stelt de onoplosbaarheid van het probleem vast. In theoretisch 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.

Inhoud

1 Geschiedenis
2 Definitie van het lineair optimalisatieprobleem
3 Voorbeeld
4 Alternatief tableau
5 Algoritme in pseudocode

[bewerk] Geschiedenis

De Russische wiskundige Leonid Kantorovich behandelde 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 waardeerde 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 wou de militaire acties optimaliseren. De daaropvolgende jaren ontwikkelden John von Neumann en O. 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.

[bewerk] 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   $x$ .

De doelfunctie wordt ook wel objectief genoemd, de nevenvoorwaarden ook wel restricties.

$A x$ is hier de notatie van een matrixvermenigvuldiging. De ongelijkheden $Ax \leq b$ en $x \geq 0$ moeten component per component opgevat worden, bijvoorbeeld $x\geq 0$ betekent hetzelfde als $x_1\geq 0,\dots, x_n\geq 0$ .

Die punten x 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 geldig verzameling oplossingen niet leeg is, zijn er twee mogelijkheden:

De doelfunctie G heeft in de toegelaten punten x 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 $+\infty$ 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 wel 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 $H = - G$ in, en men maximaliseert deze.

[bewerk] 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.

[bewerk] 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.

[bewerk] Wiskundige formulering met ongelijkheden

Stel dat het bedrijf per maand x₁ eenheden van product 1 en x₂ eenheden van product 2 vervaardigt, dan bedraagt de opbrengst (winst of verlies)

    G = 300x₁ + 500x₂ - 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 x₁ en x₂ af:

    1•x₁ + 2•x₂ ≤ 170   machine A
    1•x₁ + 1•x₂ ≤ 150   machine B
    0•x₁ + 3•x₂ ≤ 180   machine C

Negatieve productiehoeveelheden zijn niet mogelijk, dus gelden nog de nevenvoorwaarden

    x₁ ≥ 0
    x₂ ≥ 0

[bewerk] Omzetten in gelijkheden

Omdat het met stelsels gelijkheden gemakkelijker rekenen is, worden de ongelijkheden in gelijkheden omgezet. Daartoe voert men de zogenoemde slackvariabelen y_A, y_B en y_C in, die de niet benutte tijd van de respectievelijke machines voorstellen. Men vormt bijvoorbeeld de nevenvoorwaarde voor machine A in volgende gelijkheid om

    y_A + x₁ + 2•x₂ = 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  - 300x₁ - 500x₂ = - 36.000
    y_A +    x₁ +   2x₂ =      170
    y_B +    x₁ +    x₂ =      150
    y_C         +   3x₂ =      180

    y_A, y_B, y_C, x₁, x₂ ≥ 0

[bewerk] 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 (x₁, x₂) heten niet-basisvariabelen, de variabelen in de eerste kolom basisvariabelen (Y_A, Y_B, Y_C). De getallen in "rij G" - de vergelijking van de doelfunctie - zijn de coëfficiënten van de doelfunctie. De variabelen b₁, b₂ en b₃ bevatten de waarde van de rechterleden.

[bewerk] Bepaling van een geldige beginoplossing

Vervolgens bepaalt men een geldige oplossing. Dat zijn waarden voor x₁ en x₂ die aan alle nevenvoorwaarden voldoen.

Men kan in dit geval onmiddellijk een triviale oplossing geven, namelijk

    x₁ = 0
    x₂ = 0

Deze oplossing wordt in het bovenstaande tableau opgenomen. x₁ en x₂ 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: Y_A = 170, Y_B = 150, Y_C = 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.

[bewerk] 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 verwisslingsstap.

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 x_k en dan x_s in de rest van de gelijkheden inzet. Stel a_ij een matrix-element uit de simplex-tableau, dan heet a_rk 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:

$a_{rk} := {1 \over a_{rk}}$ (Formule 1)

Pivotrij voor j $\neq$ k:

$a_{rj} := {a_{rj} \over a_{rk}}$ (2)

$b_{r} := {b_{r} \over a_{rk}}$ (3)

Pivotkolom voor i $\neq$ r:

$a_{ik} := {-{a_{ik} \over a_{rk}}}$ (4)

overige elementen:

$a_{ij} := {a_{ij} - { a_{ik} a_{rj} \over a_{rk} } }$ (5)

$b_{j} := {b_{j} - { a_{ik} a_{rj} \over a_{rk} } }$ (6)

[bewerk] 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 men index k negatief is, en waarvan de waarde van

$G := G - {a_{0k}\, b_j \over a_{rk}}$

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

${b_j \over a_{rk}}$ met $a_{rs}\neq 0$

binnen een kolom minimaal wordt.

Kolom 1 heeft een negatieve coëfficiënt van de doelfunctie van -300, en komt als pivotklolom 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:  a₃₁ = 0, daar geen quotiënt berekenbaar.

Het kleinste quotiënt 150 krijgt men dus in rij 2. Met pivotelement a_2,1 berekent men de nieuwe waarde van de doelfunctie als

$G = -36000 - {(-300)\cdot 150 \over 1} = 9000$ .

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 a_3,2 berekent men de nieuwe waarde van de doelfunctie als

$G = -36000 - {(-500)\cdot 180 \over 3} = -6000$ .

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 met 9000.

[bewerk] Uitvoeren van een verwisselingsstap

In de verwisselingsstap wordt de basisvariabele Y_B met de niet-basisvariabele x₁ verwisseld.

Het simplex-tableau wordt volgens de bovenstaande regels omgerekend.

Het pivotelement is a_2,1 = 1.

Berekening van de pivotelementen:    a_2,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:      a_2,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:      a_1,1 = - (1 / 1) = -1 (met formule (4))
        Rij 2 is de pivotrij en werd reeds berekend
        Rij 3:      a_3,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:       a_1,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:       a_3,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

[bewerk] Het nieuwe simplex-tableau

Na omrekening verkrijgt men een nieuw simplex-tableau:

      ----------------------------
      |  YB     x2   | rechterlid
  --------------------------------
  G   |  300   -200  |     9000
  --------------------------------
  YA  |  -1      1   |       20  = b1
  x1  |   1      1   |      150  = b2
  YC  |   0      3   |      180  = b3

De variabele x₁ is tot de basis toegetreden, de variabele Y_B verschijnt in de titelrij en is dus een niet-basisvariabele.

Deze oplossing betekent: er worden 150 eenheden van product 1 gemaakt (rechterlid van de rij met x₁). Van product 2 wordt niets vervaardigd (x₂ is een niet-basisvariabele). Daarmee heeft het bedrijf een opbrengst van 9000 euro. Machine A staat 20 uur per maand stil (draait slechts 150 van de 170 mogelijke uren). Machine B draait niet. Machine C staat 180 uur stil, ze wordt dus helemaal niet gebruikt. Dit kan men ook afleiden uit de opgave: machine C wordt enkel bij de productie van product 2 gebruikt. Aangezien dit product niet vervaardigd wordt, gebruikt men machine C dan ook niet.

[bewerk] Verdere verbetering van de oplossing

Aangezien de doelfunctie in het nieuwe simplex-tableau nog een negatieve coëfficiënt heeft, kan men die oplossing verder verbeteren. Dit gebeurt door een volgende simplex-iteratie.

Bij de keuze van de pivotelementen komt enkel kolom k = 2 in aanmerking, aangezien enkel hier de coëfficiënt van de doelfunctie negatief is. De pivotrij kiest men volgens het minimum van de coëfficiënten "rechterlid/kolom 2", dus het minimum uit

       20 / 1 =  20
      150 / 1 = 150
      180 / 3 =  60

Men kiest dus rij r = 1 als pivotrij. Het pivotelement is a_1,2 = 1, en de basisvariabele Y_A wordt met de niet-basisvariabele x₂ verwisseld.

Na analoge berekeningen als hierboven wordt het nieuwe simplex-tableau:

      ----------------------------
      |  YB     YA   | rechterlid
  --------------------------------
  G   |  100    200  |    13000
  --------------------------------
  x2  |  -1      1   |       20 
  x1  |   2     -1   |      130 
  YC  |   3     -3   |      120

[bewerk] De optimale oplossing

Aangezien de doelfunctie geen negatieve coëfficiënten meer bevat, is de optimale oplossing bereikt.

Er worden 130 eenheden van product 1 en 20 eenheden van product 2 gefabriceerd. Daarmee behaalt het bedrijf een winst van 13.000 euro. Machine A en B worden ten volle benut. Machine C draait 60 uur, en heeft dus nog een onbenutte capaciteit van 120 uur (in het tableau is Y_C = 120).

[bewerk] Opmerking over de keuze van het pivotelement

In het voorbeeld wordt het pivotelement zodanig gekozen, dat de waarde van de doelfunctie bij de iteratiestap zo groot mogelijk wordt. Dit noemt men de Greatest-Change-Methode.

Alternatief kan men ook die kolom als pivotkolom nemen, waarvoor de coëfficiënt van de doelfunctie negatief en in absolute waard het grootst is. Aangezien deze coëfficiënt een soort toename voorstelt, spreekt men van de Steepest-Unit-Ascent-Methode.

Vaak - maar niet altijd - levert de Greatest-Change-Methode met weinig simplex-iteraties een optimale oplossing.

[bewerk] Grafische oplossing

Grafische voorstelling van een 2-dimensionaal lineair probleem

In dit eenvoudige voorbeeld kent het probleem twee variabele parameters, in dat geval kan de oplossing grafisch voorgesteld worden in een 2-dimensionale figuur. Op de figuur worden de ongelijkheden voorgesteld als halfvlakken. De grensrechte wordt telkens afgebeeld. De doorsnede van deze halfvlakken bepaalt de regio met geldige oplossingen. Dit gebied is op de figuur geel gekleurd. De doelfunctie vormt ook steeds een rechte waarop het objectief eenzelfde waarde heeft, op de figuur zijn de rechten weergeven voor G = 0 en G = 13.000, in feite kan men een continue verzameling rechten tekenen. Bemerk dat al deze rechten die de doelfunctie voorstellen evenwijdig zijn, hoe groter G, hoe verder de rechte van de oorsprong ligt in dit geval. Men kan dan ook besluiten dat men zal wil nastreven deze rechte zo ver mogelijk van de oorsprong te krijgen, maar de rechte moet wel nog een punt binnen de geldige regio hebben, aangezien aan de nevenvoorwaarden moet voldaan zijn. Aangezien deze regio een convexe figuur is, ligt het maximum op één van de hoekpunten, dit is het snijpunt met de rechte waar G = 13.000, waar men x₁ = 130 en x₂ is 20 kan aflezen.

Op de figuur valt ook de werking van de simplex-iteraties grafisch te volgen. Het algoritme begon met beginoplossing (x₁=0, x₂=0), wat overeenkomt met het punt A. Dit is tevens het snijpunt van de rechten bepaald door de niet-negativiteitsvoorwaarden, namelijk de rechten met vergelijkingen x₁=0 en x₂=0. In tweede iteratie werd x₁ aan de basis toegevoegd, Y_B werd nu een niet-basisvariabele. Wanneer men nu het snijpunt neemt van de rechten behorend bij deze niet-basisvariabelen, namelijk de rechte x₂ = 0 en de rechte B, dan bekomt men het punt B(150,0), en dit blijkt inderdaad ook de oplossing te zijn die men vindt bij de tweede iteratiestap. Bemerk dat vanuit punt B, men de doelfunctie enkel kan doen toenemen wanneer men zich verplaatst langs rechte B, wanneer men zich verplaatst langs de x-as, daalt de doelfunctie. Het is dan ook inderdaad Y_B die uit de basis gehaald werd. In de derde iteratiestap zijn dan ook Y_A en Y_B niet-basisvariabelen: het snijpunt van de bijhorende rechten is opnieuw de oplossing van deze iteratiestap. Op deze manier loopt het simplex-algoritme langs de zijden van het geldig gebied, zolang er een zijde beschikbaar is langswaar de doelfunctie stijgend is, tot een maximum bereikt is.

[bewerk] Alternatief tableau

Het simplex-tableau kan op een alternatieve manier ingedeeld worden, waarbij men alle variabelen (zowel basis- als niet-basisvariabelen) in de hoofding plaatst. Daaronder noteert men dan de doelfunctie en de nevenvoorwaarden, komt een variabele niet voor, dan schrijft men er een 0.

De oorspronkelijke tableau ziet er dan als volgt uit:

      --------------------------------------------------
      |  x1     x2     YA     YB     YC   | rechterlid
  ------------------------------------------------------
  G   | -300   -500     0      0      0   |   
  ------------------------------------------------------
  YA  |   1      2      1      0      0   |      170  = b1
  YB  |   1      1      0      1      0   |      150  = b2
  YC  |   0      3      0      0      1   |      180  = b3

We zien dat de rijen/kolommen Y_a,b,c een eenheidsmatrix vormen. Deze tabel toont de oplossing { x₁ = 0, x₂ = 0, Y_A = 170, Y_B = 150, Y_C = 180 } . Analoog aan voorheen kiest men kolom 2, omdat -500 in absolute waarde het grootst is, en een wijziging van x2 dus een potentieel grotere verandering in de objectieffunctie kan veroorzaken. Men kiest als pivotrij, rij YC. Dit besluit men opnieuw uit de berekening van rechterlid/x₂. Voor rij YA bekomt men 170/2 = 85, voor rij YB 150/1 = 150, voor rij YC 180/3 = 60. Men ziet echter dat wanneer men voor x₂ de waarde 85 zou gebruiken, de nevenvoorwaarde van rij YB nooit meer voldaan zou kunnen worden. Immers, vult men x = 85 in in 3 x₂ + Y_C = 255 + Y_C, dan ziet men dat deze som nooit kleiner kan worden dan 180, aangezien Y_C positief is, en de ongelijkheid zou dus nooit voldaan kunnen worden. Daarom kiest men die rij waar de verhouding rechterlid/x₂ het kleinst is, of dus rij YC. Ook hier voert men nu elementaire rijbewerkingen op de matrix uit, wat leidt tot het volgende tableau:

      --------------------------------------------------
      |  x1     x2     YA     YB     YC   | rechterlid
  ------------------------------------------------------
  G   | -300     0      0      0   166,66 |   
  ------------------------------------------------------
  YA  |   1      0      1      0   -0,666 |      50
  YB  |   1      0      0      1   -0,333 |      90
  x2  |   0      1      0      0    0,333 |      60

Opnieuw is te zien dat x₂ nu een basisvariabele is. De eenheidsmatrix is ook weer terug te vinden, met Y_a,b en x₂ In de voorlopige oplossing heeft x₂ de waarde 60. De eerste kolom heeft nu een negatief element, rij YA heeft de kleinste kolomverhouding, pivoteren levert:

      --------------------------------------------------
      |  x1     x2     YA     YB     YC   | rechterlid
  ------------------------------------------------------
  G   |   0     0      300     0   -33,33 |   
  ------------------------------------------------------
  x1  |   1      0      1      0   -0,666 |      50
  YB  |   0      0     -1      1    0,333 |      40
  x2  |   0      1      0      0    0,333 |      60

Aangezien er nog één kolom met negatieve coëfficiënt blijft, levert een laatste maal pivoteren met rij YB:

      --------------------------------------------------
      |  x1     x2     YA     YB     YC   | rechterlid
  ------------------------------------------------------
  G   |   0     0      200    100     0   |   
  ------------------------------------------------------
  x1  |   1      0     -1      2      0   |     130
  YC  |   0      0     -3      3      1   |     120
  x2  |   0      1      1     -1      0   |      20

Men leest uiteindelijk dezelfde oplossing x₁ = 130 en x₂ = 20 af.

[bewerk] Algoritme in pseudocode

In deze code wordt de begintabel als de matrix "tab" voorgesteld, waarbij G de onderste rij vormt en niet de bovenste. De matrix ziet er voor het voorbeeld als volgt uit:

  +-----+-----+------+
  |  1  |  2  |  170 |
  +-----+-----+------+
  |  1  |  1  |  150 |
  +-----+-----+------+
  |  0  |  3  |  180 |
  +-----+-----+------+
  |-300 |-500 |-36000|
  +-----+-----+------+

Programma simplex()
 int r, k, i, j, pivot
 Invoer: "rij?", r
 Invoer: "kolom?", k
 pivot = tab[r,k]
 Voor i van 1 tot aantalRijen(tab)
   Voor j van 1 tot aantalKolommen(tab)
     Als i != r en j != k dan
       tab[i,j] = tab[i,j]-tab[i,k]*tab[r,j]/p
     EindeAls
   EindeVoor
 EndeVoor
 Voor j van 1 tot aantalKolommen(tab)
   tab[i,j] = tab[r,j]/p
 EndeVoor
 Voor i van 1 tot aantalRijen(tab)
   Als i != r dan
     tab[i,k] = 0
   EindeAls
 EindeVoor
 Uitvoer: tab
EindeProgramma

Categorieën: Algoritme | Operationeel onderzoek