WikiDer > Simplex-Methode

Simplexmethode

Das Simplex-Methode (wenn es Simplex-Algorithmus) ist eine Methode im mathematische Optimierung (siehe auch operatives recherchieren). Die Technik war 1947 durch George Dantzig entwickelt. Die Simplex-Methode löst a lineares Optimierungsproblem in endlich vielen Schritten oder bestimmt die Unlöslichkeit des Problems. In theoretischen Fällen können Zyklen auftreten, die das Finden der optimalen Lösung verhindern. Der Name kommt daher, dass die Gleichungen des Problems a Simplex beschreiben, dessen Rand bei der Lösungsfindung beschrieben wird.

Geschichte

Das Russisch Mathematiker Leonid Kantorowitsch behandelt in 1939 als erste lineare Optimierung in seinem Buch "Mathematische Methoden in der Organisation und Planung der Produktion". Kurz darauf ist die amerikanisch F. L. Hitchcock eine Arbeit über ein Transportproblem. Damals wurde die Bedeutung dieser Arbeit jedoch noch nicht erkannt.

Der Durchbruch für die Simplex-Methode gelang George Dantzig im 1947, als er auch eine Arbeit über lineare Optimierung veröffentlichte. Zunächst war die US-Armee, insbesondere die US-Luftwaffe, Interesse an dieser Arbeit - sie wollten die militärischen Aktionen optimieren. Die folgenden Jahre entwickelt John von Neumann und Oskar Morgenstern den Algorithmus weiter.

Mit dem Aufstieg von Computers halb durch die 50er Jahre größere Probleme lösen könnte. Es wurden spezielle Varianten des Simplex-Verfahrens entwickelt, die an die Eigenschaften der damaligen Computer angepasst wurden. So gingen sie beispielsweise sehr sparsam mit dem Hauptspeicher um.

Gleichzeitig – nach 1950 – entdeckte die Industrie, dass die Simplex-Methode auch Optimierungsprobleme in ihrem Bereich lösen kann. Insbesondere verwenden Ölraffinerien die Methode. Im 1960 W. Knödel optimierte die Versorgung der Zuckerfabriken im Österreich. Dabei reduzierte er die Transportkosten um rund 10 Prozent.

Definition des linearen Optimierungsproblems

Maximieren Sie die Zielfunktion

{displaystyle G:mathbb {R} ^{n} oder mathbb {R} ,;xmapto a^{T}x}

unter den zusätzlichen Bedingungen

{displaystyle Axleq b}

und

{displaystyle xgeq 0}

.

In Ergänzung,

A: m×n-Matrix

a: n-dimensionaler Vektor

b: m-dimensionaler Vektor

gegebener Parameter und die Zielfunktion

{displaystyle a^{T}x=langle a,xangle =sum _{i=1}^{n}a_{i}x_{i}}

als Skalarprodukt ist eine lineare Funktion in

{Anzeigestil x}

.

Das Zielfunktion wird auch genannt objektiv genannt, die zusätzliche Bedingungen ebenfalls Beschränkungen.

${displaystyle Axt}$ hier ist die notation von a Matrix-Multiplikation. Die „Ungleichheiten“ ${displaystyle Axleq b}$ und ${displaystyle xgeq 0}$ muss z.B. Komponente für Komponente verstanden werden ${displaystyle xgeq 0}$ , mit ${displaystyle x=(x_{1},x_{2},Punkte,x_{n})^{T}}$ , bedeutet dasselbe wie ${displaystyle x_{1}geq 0,dots ,x_{n}geq 0}$ .

Diese Punkte (Vektoren) ${Anzeigestil x,}$ die alle Nebenbedingungen gleichzeitig erfüllen (dies sind gültige Lösungen des Problems) Form a konvex Polyeder in dem nein-dimensionaler Raum, ein sogenannter Simplex Wenn es keine gültigen Lösungen gibt, widersprechen sich die Nebenbedingungen und das Problem ist nicht lösbar.

Wenn die Menge der gültigen Lösungen nicht leer ist, gibt es zwei Möglichkeiten:

Die Zielfunktion G hat in der erlaubte Punkte ${Anzeigestil x,}$ ein Obergrenze:
Hier sieht man, dass das Maximum der Zielfunktion von einem Punkt am Rand der gültigen Menge, nämlich von einer Ecke, eingenommen wird. Ausgehend von einer gültigen Anfangslösung bewegt sich der Simplex-Algorithmus entlang der Ecken des Polyeders zu seiner optimalen Lösung.
Die Zielfunktion G ist nicht auf die Spitze beschränkt:
In diesem Fall wird festgestellt, dass es eine unendlich lange Seite des Polyeders mit unendlich ansteigender Zielfunktion gibt. Man sagt, dass der optimale Wert der Zielfunktion ${displaystyle infty }$ und es kann keine optimale Lösung angegeben werden.

Wenn keine gültige Anfangslösung bekannt ist, kann ein leicht modifiziertes lineares Optimierungsproblem verwendet werden, um eine Anfangslösung zu finden und die Löslichkeit des Problems zu bestimmen. (Die sogenannte Phase I mit künstlichen Variablen).

In vielen Problemstellungen kommt es vor, dass die Zielfunktion G will nicht maximieren, sondern minimieren. Zum Beispiel bei a Transportproblem die Transportkosten sind so gering wie möglich oder die Wege müssen so kurz wie möglich sein. In diesem Fall führt man einfach eine neue Zielfunktion aus ${Anzeigestil H=-G}$ ein, und es wird maximiert.

Beispiel

Anhand eines einfachen Beispiels wird die Lösungsmethode Schritt für Schritt gezeigt. Reale Probleme können mehr als tausend Voraussetzungen haben, in denen man mögliche Widersprüche nicht sofort erkennen kann, oder somit nicht sofort die Existenz einer gültigen Ausgangslösung finden kann.

Problemstellung in Worten

Ein Unternehmen bietet 2 verschiedene Produkte an. Es stehen 3 Maschinen A, B und C zur Verfügung. Maschine A hat eine maximale monatliche Laufzeit (Kapazität) von 170 Stunden, Maschine B von 150 Stunden und Maschine C von 180 Stunden. Eine Einheit von Produkt 1 ergibt einen Gewinnbeitrag von 300 Euro, eine Einheit von Produkt 2 hingegen 500 Euro. Die Fixkosten betragen 36.000 Euro pro Monat.
Wenn Sie 1 Einheit von Produkt 1 herstellen, wird 1 Stunde von Maschine A verwendet und dann 1 Stunde von Maschine B. 1 Einheit von Produkt 2 benötigt 2 Stunden von Maschine A, 1 Stunde von Maschine B und 3 Stunden von Maschine C.

Mathematische Formulierung mit Ungleichungen

Angenommen, das Unternehmen pro Monat x₁ Einheiten von Produkt 1 und x₂ produziert Einheiten von Produkt 2, dann ist der Umsatz (Gewinn oder Verlust)

    G = 300x₁   500x₂ - 36.000

Diesen Ertrag will das Unternehmen maximieren.

Da die Kapazität der Maschinen begrenzt ist, ist es nicht möglich beliebig große Stückzahlen zu produzieren. Aus den Belegungszeiten werden folgende Nebenbedingungen für x abgeleitet:₁ und x₂ aus:

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

Negative Produktionsmengen sind nicht möglich, daher gelten weiterhin die Nebenbedingungen

    X₁ 0 x₂ ≥ 0

In Gleichheiten umwandeln

Da mit Gleichheitssystemen einfacher zu rechnen ist, werden die Ungleichungen in Gleichheiten umgerechnet. Zu diesem Zweck wird das sogenannte Slack-Variablen ja_ein, ja_B Andy_C in, die die ungenutzte Zeit der jeweiligen Maschinen darstellen. Beispielsweise wird die Nebenbedingung für Maschine A in folgende Gleichheit umgewandelt:

    ja_ein   X₁   2•x₂ = 170

Offensichtlich dürfen die Slack-Variablen nicht negativ sein (Nicht-Negativitätsbedingung).

Das Problem lässt sich nun wie folgt formulieren:

Maximieren Sie die Zielfunktion G unter folgenden Nebenbedingungen:

    G - 300x₁ - 500x₂ = - 36.000 Jahre_ein      X₁     2x₂ = 170 Jahre_B      X₁      X₂ = 150 Jahre_C             3x₂ =      180

    ja_ein, ja_B, ja_C, x₁, x₂ ≥ 0

Das Simplex-Tableau

Diese Gleichungen werden in ein sogenanntes Simplex-Tableau, die eine abgekürzte Darstellung des zugehörigen Gleichungssystems ist. Alle folgenden Operationen sind mathematische Berechnungen mit dem Gleichungssystem.

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

Die Variablen in der Titelzeile (x₁, x₂) werden genannt Nicht-Basisvariablen, die Variablen in der ersten Spalte Basisvariablen (Y_ein, Ja_B, Ja_C). Die Zahlen in "Reihe G" - der Gleichung der Zielfunktion - sind die Koeffizienten der Zielfunktion. Die Variablen b₁, b₂ und B₃ enthalten den Wert der richtigen Mitglieder.

Bestimmung einer gültigen Anfangslösung

Dann wird eine gültige Lösung bestimmt. Das sind Werte für x₁ und x₂ die alle Nebenbedingungen erfüllen.

Man kann in diesem Fall sofort eine triviale Lösung angeben, nämlich

    X₁ = 0 x₂ = 0

Diese Lösung ist im obigen Tableau enthalten. X₁ und x₂ sind die Nicht-Basisvariablen und haben immer den Wert "0". Das Basisvariablen haben den Wert der ungenutzten Maschinenlaufzeiten. Da mit der Anfangslösung nichts erzeugt wird: Y_ein = 170, Y_B = 150, Y_C = 180. Diese Anfangslösung ist natürlich unbefriedigend: Es gibt keine Produktion, die Ausbeute G beträgt -36.000 Euro, was einen Verlust bedeutet. Daher sollte man versuchen, bessere valide Lösungen zu finden.

Verbesserung der Lösung durch eine Simplex-Iteration

In einer Iteration des Simplex-Algorithmus ist a Basisvariable jetzt sofort Nicht-Basisvariable getauscht. Dies ist ein Austauschschritt.

Zulässig sind nicht basische Variablen, die einen negativen Koeffizienten in der Zielfunktion haben. Unter diesen Variablen sucht man die Variable, die beim Austausch den größten Anstieg der Zielfunktion ergibt. Sei k die Spaltennummer der zu vertauschenden Nicht-Basisvariablen und r die Zeilennummer der zu vertauschenden Basisvariablen. Der Austauschschritt entspricht nur einem Schritt beim Lösen eines Gleichungssystems, bei dem man Zeile r zu den Variablen x solve löst_k und dann x_so wetten Sie in den Rest der Gleichheiten. stelle ein_ij ein Matrixelement aus dem Simplextableau, dann heißt a_rk es Drehelement des Tableaus. Spalte k ist die Pivot-Spalte, Zeile r ist die Pivot-Zeile.

Im Austauschschritt wird das neue Tableau wie folgt berechnet:

Drehelement:

{displaystyle a_{rk}:={1 über a_{rk}}}

(Formel 1)

Drehreihe für dich ${displaystyle eq }$ k:

{displaystyle a_{rj}:={a_{rj} über a_{rk}}}

(2)

{displaystyle b_{r}:={b_{r} über a_{rk}}}

(3)

Pivot-Spalte für i ${displaystyle eq }$ r:

{displaystyle a_{ik}:={-{a_{ik} über a_{rk}}}}

(4)

andere Elemente:

{displaystyle a_{ij}:={a_{ij}-{a_{ik}a_{rj} über a_{rk}}}}

(5)

{displaystyle b_{j}:={b_{j}-{a_{ik}a_{rj} über a_{rk}}}}

(6)

Auswahl an Drehelementen

Formel (6) bestimmt die Wahl der Pivot-Reihe r und die Pivot-Spalte k. Diese Werte werden für waarden gesucht r und k für die der Koeffizient der Zielfunktion mit Index k negativ ist und dessen Wert von

{displaystyle G:=G-{a_{0k},b_{j} über a_{rk}}}

wird so groß wie möglich. Dabei ist zu beachten, dass nach dem Austausch die resultierende Lösung noch gültig sein muss, dh alle Nebenbedingungen müssen erfüllt bleiben. Dazu wählt man r und k so dass der Quotient

{displaystyle {b_{j} über a_{rk}}}

mit

{displaystyle a_{rs}eq 0}

innerhalb einer Spalte wird minimal.

Spalte 1 hat einen negativen Zielfunktionskoeffizienten von -300 und kommt als Pivot-Spalte k berechtigt.
Berechnung der Koeffizienten dieser Spalte 1:

 Reihe 1: 170 / 1 = 170 Reihe 2: 150 / 1 = 150 Reihe 3: a₃₁ = 0, da kein Quotient berechnet werden kann.

Damit ergibt sich in Zeile 2 der kleinste Quotient 150. Mit Pivotelement a_2,1 berechnet man den neuen Wert der Zielfunktion als

{Displaystil G=-36000-{(-300)cdot 150 über 1}=9000}

.

Spalte 2 hat auch einen negativen Koeffizienten in der Zielfunktion mit -500 und kommt auch als Pivot-Spalte k berechtigt.
Die Berechnungen der Koeffizienten dieser Spalte 2:

 Reihe 1: 170 / 2 = 85 Reihe 2: 150 / 1 = 150 Reihe 3: 180 / 3 = 60

Den kleinsten Quotienten 60 findet man in Zeile 3. Mit dem möglichen Pivotelement a_3,2 berechnet man den neuen Wert der Zielfunktion als

{Displaystil G=-36000-{(-500)cdot 180 über 3}=-6000}

.

Es ist daher günstiger, die erste Zahl aus Zeile getal als Pivot-Element zu verwenden r = 2 und Spalte k = 1, da dies die Zielfunktion am stärksten erhöht, nämlich von -36000 auf 9000.

Austauschschritt durchführen

Im Swap-Schritt wird die Basisvariable Y_B mit der Nichtbasisvariablen x₁ getauscht.

Das Simplex-Tableau wird nach den obigen Regeln konvertiert.

Das Pivot-Element ist a_2,1 = 1.

Berechnung der Pivot-Elemente: a_2,1 = 1 / 1 = 1 (mit Formel (1))

Berechnung der Pivot-Reihe r = 2: Jedes Element wird durch das Pivot-Element geteilt. Spalte 1 enthält das Pivot-Element und wurde gerade berechnet. Spalte 2: a_2,2 = 1 / 1 = 1 (mit Formel (2))        rechte Seite: b2 = 150 / 1 = 150 (mit Formel (3))

Berechnung der Pivot-Spalte k = 1: Jedes Element wird durch das Pivot-Element geteilt, das Vorzeichen wird umgekehrt. Zielfunktion: - (-300 / 1) = 300 Zeile 1: a_1,1 = - (1 / 1) = -1 (mit Formel (4))        Zeile 2 ist die Pivot-Zeile und wurde bereits berechnet Zeile 3: a_3,1 = (- (0 / 1) = 0

Berechnung der anderen Werte - Spalte 2, da Spalte 1 bereits berechnet wurde: Zielfunktion Spalte 2: -500 - (-300 × 1) /1 = -200 Zeile 1 Spalte 2: a_1,2 = 2 - 1×1 / 1 = 1 (mit Formel (5))       Zeile 2 Spalte 2 gehört zur Pivot-Zeile und wurde bereits berechnet. Zeile 3 Spalte 2: a_3,2 = 3 - 0×1 / 1 = 3

rechte Seite: Zielfunktion: G = -36000 - (-300 × 150) / 1 = 9000

       Reihe 1: b1 = 170 - 1×150 / 1 = 20 (mit Formel (6))       Zeile 2 gehört zur Pivot-Zeile und wurde bereits berechnet Zeile 3: b3 = 180 - 0×150 / 1 = 180

Das neue Simplex-Tableau

Nach der Konvertierung erhält man ein neues Simplex-Tableau:

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

Die Variable x₁ mit der Basis verbunden ist, die Variable Y_B erscheint in der Titelzeile und ist somit eine Nicht-Basisvariable.

Diese Lösung bedeutet: Es werden 150 Einheiten von Produkt 1 hergestellt (rechte Seite der Reihe mit x₁). Produkt 2 wird nicht hergestellt (x₂ ist eine Nicht-Basisvariable). Damit erzielt das Unternehmen einen Umsatz von 9.000 Euro. Maschine A ist 20 Stunden im Monat im Leerlauf (läuft nur 150 der 170 möglichen Stunden). Maschine B läuft auf Hochtouren. Maschine C steht 180 Stunden lang still, wird also überhaupt nicht verwendet. Dies lässt sich auch aus der Aussage ableiten: Maschine C wird nur zur Herstellung von Produkt 2 verwendet. Da dieses Produkt nicht hergestellt wird, wird Maschine C nicht verwendet.

Weitere Verbesserung der Lösung

Da die Zielfunktion im neuen Simplextableau noch einen negativen Koeffizienten hat, kann diese Lösung weiter verbessert werden. Dies geschieht durch eine anschließende Simplex-Iteration.

Bei der Auswahl der Pivot-Elemente nur Spalte k = 2, da nur hier der Koeffizient der Zielfunktion negativ ist. Die Pivot-Reihe wird nach dem Minimum der Koeffizienten "rechte Seite/Spalte 2" gewählt, d.h. das Minimum aus

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

Also wählt man Reihe r = 1 als Pivot-Reihe. Das Pivot-Element ist a_1,2 = 1, und die Basisvariable Y_ein wird mit der Nicht-Basisvariablen x . verwendet₂ getauscht.

Nach analogen Berechnungen wie oben wird das neue Simplex-Tableau zu:

       -------------- ------------ | YB YA | rechte Seite ---- -------------- ------------ G | 100 200 | 13000 ---- -------------- ------------ x2 | -1 1 | 20 x1 | 2 -1 | 130 Jahre | 3 -3 | 120

Die optimale Lösung

Da die Zielfunktion keine negativen Koeffizienten mehr enthält, ist die optimale Lösung erreicht.

Es werden 130 Einheiten von Produkt 1 und 20 Einheiten von Produkt 2 hergestellt. Damit erzielt das Unternehmen einen Gewinn von 13.000 Euro. Maschine A und B sind voll ausgelastet. Maschine C läuft 60 Stunden und hat somit eine ungenutzte Kapazität von 120 Stunden (im Tableau Y . is_C = 120).

Hinweis zur Wahl des Pivot-Elements

Im Beispiel wird das Pivot-Element so gewählt, dass der Wert der Zielfunktion im Iterationsschritt möglichst groß wird. Das nennt man Greatest-Change-Methode.

Alternativ kann man auch diejenige Spalte als Pivotspalte nehmen, für die der Koeffizient der Zielfunktion negativ und absolut am größten ist. Da dieser Koeffizient eine Art Erhöhung darstellt, sprechen wir vom Steilste-Einheit-Aufstiegsmethode.

Oft - aber nicht immer - bietet die Greatest-Change-Methode mit wenigen Simplex-Iterationen eine optimale Lösung.

Grafische Lösung

Grafische Darstellung eines 2-dimensionalen linearen Problems

In diesem einfachen Beispiel hat das Problem zwei variable Parameter, wobei die Lösung grafisch in einer 2-dimensionalen Figur dargestellt werden kann. In der Abbildung sind die Ungleichungen dargestellt als Halbflugzeuge. Die Grenzlinie wird immer dargestellt. Der Querschnitt dieser Halbebenen bestimmt den Bereich mit gültigen Lösungen. Dieser Bereich ist in der Abbildung gelb eingefärbt. Die Zielfunktion bildet auch immer eine Linie, auf der das Ziel den gleichen Wert hat, in der Abbildung sind die Linien für G = 0 und G = 13.000 dargestellt, tatsächlich kann man eine kontinuierliche Liniensammlung zeichnen. Beachten Sie, dass alle diese Linien, die die Zielfunktion darstellen, parallel sind, je größer G, desto weiter ist die Linie in diesem Fall vom Ursprung entfernt. Es kann daher entschieden werden, dass diese Linie so weit wie möglich vom Ursprung entfernt werden soll, die Linie jedoch noch einen Punkt innerhalb des gültigen Bereichs haben muss, da die Nebenbedingungen erfüllt sein müssen. Da dieser Bereich eine konvexe Figur ist, liegt das Maximum auf einem der Eckpunkte, dem Schnittpunkt mit der Geraden mit G = 13.000, wobei eins x . ist₁ = 130 und x₂ ist 20 lesen können.

Die Abbildung zeigt auch den Ablauf der Simplex-Iterationen grafisch. Der Algorithmus begann mit der Anfangslösung (x₁=0, x₂=0), was dem Punkt A entspricht. Dies ist auch der Schnittpunkt der durch die Nichtnegativitätsbedingungen bestimmten Geraden, nämlich der Geraden mit den Gleichungen x₁=0 und x₂=0. In der zweiten Iteration wurde x₁ zur Basis hinzugefügt, Y_B wurde jetzt eine nicht-Basisvariable. Nimmt man nun den Schnittpunkt der Geraden dieser Nicht-Basisvariablen, nämlich die Gerade x₂ = 0 und der Geraden B, dann erhält man den Punkt B(150,0), und das stellt sich tatsächlich als die Lösung heraus, die man im zweiten Iterationsschritt findet. Beachten Sie, dass man ab Punkt B die Zielfunktion nur erhöhen kann, wenn man sich entlang der Linie B bewegt, wenn man sich entlang der x-Achse bewegt, nimmt die Zielfunktion ab. Es ist in der Tat Y_B die von der Basis genommen wurde. Im dritten Iterationsschritt sind Y. also_ein Andy_B Nicht-Basisvariablen: Der Schnittpunkt der zugehörigen Geraden ist wieder die Lösung dieses Iterationsschritts. Auf diese Weise läuft der Simplex-Algorithmus entlang der Seiten des gültigen Bereichs, solange eine Seite verfügbar ist, entlang der die Zielfunktion aufsteigend ist, bis ein Maximum erreicht ist.

Alternatives Tableau

Das Simplex-Tableau kann auf alternative Weise organisiert werden, indem alle Variablen (sowohl Basis- als auch Nicht-Basisvariablen) in der Kopfzeile platziert werden. Darunter sind die Zielfunktion und die Nebenbedingungen notiert, ist eine Variable nicht vorhanden, wird eine 0 darauf geschrieben.

Das Originaltableau sieht dann so aus:

       ----------------------- -------------- | x1 x2 YA YB YC | rechtes Mitglied ---- ---------------------------------- --------- - --- 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

Wir sehen, dass die Zeilen/Spalten Y_ABC eine Einheitsmatrix bilden. Diese Tabelle zeigt die Lösung { x₁ = 0, x₂ = 0, Y_ein = 170, Y_B = 150, Y_C = 180}. Analog zu vorher wird Spalte 2 gewählt, da -500 der absolute Wert ist und eine Änderung von x2 daher eine potentiell größere Änderung der Zielfunktion bewirken kann. Als Pivot-Reihe wählt man die Reihe YC. Dies ergibt sich wiederum aus der Berechnung von rechter Seite/x₂. Für die Reihe YA erhalten wir 170/2 = 85, für die Reihe YB 150/1 = 150, für die Reihe YC 180/3 = 60. Es ist jedoch zu sehen, dass bei einer für x₂ den Wert 85 verwenden würde, könnte die Nebenbedingung der Zeile YC nie wieder erfüllt werden. Immerhin füllt man x = 85 in 3 x₂ Ja_C = 255 Y_C, dann sieht man, dass diese Summe niemals kleiner als 180 sein kann, da Y_C positiv, und somit konnte die Ungleichung niemals erfüllt werden. Deshalb wählt man die Reihe, in der das Verhältnis rechts/x₂ am kleinsten ist, oder so Zeile YC. Auch hier werden elementare Zeilenoperationen auf der Matrix durchgeführt, was zu folgendem Tableau führt:

       ----------------------- -------------- | x1 x2 YA YB YC | rechtes Mitglied ---- ---------------------------------- --------- - --- 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

Wieder ist zu sehen, dass x₂ ist jetzt eine Basisvariable. Die Einheitsmatrix kann auch wieder gefunden werden, mit Y_{a, b} und x₂ In der vorläufigen Lösung gilt x₂ der Wert 60. Die erste Spalte hat jetzt ein negatives Element, Zeile YA hat das kleinste Spaltenverhältnis, Pivot ergibt:

       ----------------------- -------------- | x1 x2 YA YB YC | rechtes Mitglied ---- ---------------------------------- --------- - --- 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

Da eine Spalte mit negativem Koeffizienten übrig bleibt, ergibt ein abschließender Pivot mit Zeile YB:

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

Am Ende liest man dieselbe Lösung x₁ = 130 und x₂ = 20 aus.

Algorithmus im Pseudocode

In diesem Code wird die Starttabelle als Matrix "Tab" dargestellt, wobei G die unterste Zeile und nicht die oberste ist. Für das Beispiel sieht die Matrix so aus:

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

Programm simplex() int r, k, i, j, Pivot Eingabe: "Zeile?", r Eingabe: "Spalte?", k Pivot = tab[r,k] Für i von 1 bis ZahlRows(tab) Für j von 1 to numberColumns(tab) Wenn i != r und j != k dann tab[i,j] = tab[i,j]-tab[i,k]*tab[r,j]/p EndIf EndBefore EndBefore Before j from 1 to numberColumns(tab) tab[r,j] = tab[r,j]/p EndFor For i from 1 to numberRows(tab) Wenn i != r dann tab[i,k] = 0 EndIf EndFor Output : tabEndProgramm

Navigation