Benutzer:Heinrich Puschmann/Simplexbeispiel

zum Artikel Simplex-Verfahren#Mathematische Beschreibung
Simplexbeschreibung

zum Artikel Simplex-Verfahren#Beispielrechnung
Syntaxbeispiele

Geordnete Liste der Belege:

Die Schritte eines Simplexverfahrens lassen sich am einfachsten anhand von Beispielen beschreiben; mathematische Formeln dazu können wie weiter unten meist leicht aus diesen abgeleitet werden.

Beispielrechnung 1

Anhand eines einfachen Beispiels zur Produktionsplanung mit zwei Variablen soll der Lösungsweg Schritt für Schritt gezeigt werden. In diesem einfachen Fall ist eine Optimallösung leicht zu finden; in der Praxis können Optimierungsaufgaben leicht aus hunderttausenden Variablen und Nebenbedingungen bestehen, so dass man ihnen nicht einmal die Existenz einer Lösung und schon gar nicht den bestmöglichen Lösungswert unmittelbar ansehen kann.

Eine Firma stelle 2 verschiedene Produkte her. Es stehen 3 Maschinen A, B, 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 Mengeneinheit (ME) von Produkt 1 liefert einen Deckungsbeitrag von 300 Euro, eine ME von Produkt 2 dagegen 500 Euro. Fertigt man 1 ME von Produkt 1 an, benötigt man dafür zunächst 1 Stunde die Maschine A und danach 1 Stunde die Maschine B. 1 ME von Produkt 2 dagegen belegt nacheinander 2 Stunden Maschine A, 1 Stunde Maschine B und 3 Stunden Maschine C.

Daraus erhält man folgende Bedingungen:

${\begin{matrix}1\cdot x_{1}&+&2\cdot x_{2}&\leq &170&{\mbox{(Maschine A)}}\\[2pt]1\cdot x_{1}&+&1\cdot x_{2}&\leq &150&{\mbox{(Maschine B)}}\\[2pt]0\cdot x_{1}&+&3\cdot x_{2}&\leq &180&{\mbox{(Maschine C)}}\\[2pt]\end{matrix}}$

$x_{1}\geq 0,\ x_{2}\geq 0$

Die Firma möchte den Deckungsbeitrag $z\,$ maximieren, mit

$z=10000+300\cdot x_{1}+500\cdot x_{2}$

Diese Funktion ist die sogenannte Zielfunktion, und $z\,$ ist die Zielvariable.

Überführung in die Buchform

Für das Simplex-Verfahren werden die Ungleichungen zunächst in Gleichungen überführt, wobei

1. sämtliche Variablen des Systems nichtnegative Werte annehmen müssen
2. eine Teilmenge der Variablen bezüglich der restlichen Variablen freigelegt sein soll

Eine Aufgabestellung in dieser Form nennt sich Aufgabestellung in Buchform (englisch dictionary form, Benennung von Chvátal), das dazugehörige Gleichungssystem ist in parametrischer Form.

Falls wie in der obigen Aufgabe die Strukturvariablen bereits nichtnegativ sein müssen und die Nebenbedingungen ausschließlich aus Ungleichungen bestehen, ist das besonders einfach, indem man sogenannte Schlupfvariablen $x_{A}\,$, $x_{B}\,$ und $x_{C}\,$ einführt, welche hier die nicht genutzten Zeiten der einzelnen Maschinen darstellen. Offensichtlich dürfen Schlupfvariablen nicht negativ sein. Nun lässt sich das Problem unmittelbar so formulieren, dass die Schlupfvariablen bezüglich der ursprünglichen Variablen freilegt sind.

Maximiere die Zielvariable $z\,$ unter den Nebenbedingungen:

${\begin{matrix}z&=&10000&+~300\,x_{1}&+~500\,x_{2}\\[3pt]x_{A}&=&~~~170&-~~~~1\,x_{1}&-~~~~2\,x_{2}\\[2pt]x_{B}&=&~~~150&-~~~~1\,x_{1}&-~~~~1\,x_{2}\\[2pt]x_{C}&=&~~~180&+~~~~0\,x_{1}&-~~~~3\,x_{2}\end{matrix}}$

$x_{1}\geq 0,\ x_{2}\geq 0,\$  $x_{A}\geq 0,\ x_{B}\geq 0,\ x_{C}\geq 0$

Bestimmung eines zulässigen Ausgangssystems (Phase I)

Auch eine zulässigen Ausgangslösung ist in diesem Beispiel bereits gegeben, da die konstanten Größen des obigen Gleichungssystems keine negativen Werte enthalten.

In so einem Fall kann man die unabhängigen Variablen des Gleichungssystems (Nichtbasisvariablen) auf Null setzen und so eine triviale zulässige Lösung angeben, mit der direkt die Phase II gestartet werden kann:

$x_{1}=0,\ x_{2}=0\qquad x_{A}=170,\ x_{B}=150,\ x_{C}=180$

Die Variablen $x_{A},\,x_{B},\,x_{C}$ bilden eine zulässige Basis $B\,$; die zugehörige Basislösung entspricht dem Fall, dass nichts produziert wird. Die Restkapazität der Maschinen, die durch die Werte der $x_{A}=170,\,x_{B}=150,\,x_{C}=189$ angegeben wird ist hier deren Gesamtkapazität, da die Maschinen nicht genutzt werden.

Verbesserung der Ausgangslösung (Phase II)

Da die soeben berechnete Ausgangslösung unbefriedigend ist, wird nun in Phase II versucht, bessere zulässige Lösungen zu finden.

Auswahl eines Pivotelements:

In einer Simplex-Iteration wird eine Basisvariable gegen eine der unabhängigen Variablen ausgetauscht. In Frage kommen Nichtbasisvariablen mit positivem Zielfunktionskoeffizienten, da deren Aufnahme in die Basis den Zielfunktionswert verbessern kann. Diese Variable soll soweit erhöht werden, bis eine oder mehrere der Basisvariablen auf 0 stoßen. Eine beliebige dieser Basisvariablen verlässt dann die Basis und wird gegen die Nichtbasisvariable ausgetauscht.

Variable $x_{1}\,$ hat den positiven Zielfunktionskoeffizienten 300; indem sie erhöht wird, lässt sich die Zielfunktion $z\,$ vergrößern; sie kommt also als basis-eintretende Pivotvariable in Frage. Solange $x_{1}\,$ die einzige erhöhte Nichtbasisvariable ist, soll diese Erhöhung ${\bar {x}}_{1}\,$ durch folgende Bedingungen eingeschränkt werden:

${\begin{matrix}0\leq {\bar {y}}_{A}=170-1\,{\bar {x}}_{1}&\quad {\text{(zu Basisvariable }}y_{A}{\text{)}}\\[2pt]0\leq {\bar {y}}_{B}=150-1\,{\bar {x}}_{1}&\quad {\text{(zu Basisvariable }}y_{B}{\text{)}}\\[2pt]\end{matrix}}$

In anderen Worten,

${\bar {x}}_{1}\leq {\frac {170}{1}},\quad {\bar {x}}_{1}\leq {\frac {150}{1}}$  oder  ${\bar {x}}_{1}\leq \min {\Bigl \{}{\frac {170}{1}},\ {\frac {150}{1}}{\Bigr \}}=\min\{170,150\}=150$

Die erste der Basisvariablen, die in diesem Fall auf Null stößt, erhält man über den Quotienten $150/1\,$ und ist $y_{B}\,$. Diese ist die Variable, die gegebenenfalls gegen $x_{1}\,$ ausgetauscht werden müsste. Der neue Wert der Zielfunktion wäre dann ${\bar {z}}=300\cdot (150/1)=45000$.

Auch Variable $x_{2}\,$ hat mit 500 einen positiven Zielfunktionskoeffizienten, kommt also ebenfalls als eintretende Nichtbasisvariable in Frage. Nach der obigen Vorgehensweise erhalten wir

${\begin{matrix}0\leq {\bar {x}}_{A}=170-2\,{\bar {x}}_{2}&\quad {\text{(zu Basisvariable }}x_{A}{\text{)}}\\[2pt]0\leq {\bar {x}}_{B}=150-1\,{\bar {x}}_{2}&\quad {\text{(zu Basisvariable }}x_{B}{\text{)}}\\[2pt]0\leq {\bar {x}}_{C}=180-3\,{\bar {x}}_{2}&\quad {\text{(zu Basisvariable }}x_{C}{\text{)}}\\[2pt]\end{matrix}}$

und somit

${\bar {x}}_{2}\leq \min {\Bigl \{}{\frac {170}{2}},\ {\frac {150}{1}},\ {\frac {180}{3}}{\Bigr \}}=\min\{85,150,60\}=60$

Der minimale Quotient $(180/3)\,$ gehört zur Basisvariable $y_{C}\,$. Der neue Wert der Zielfunktion wäre ${\bar {z}}=500\cdot (180/3)=30000$.

Für den Zuwachs der Zielfunktion in diesem Schritt ist es also am günstigsten, den ersten Fall zu wählen und die unabhängige Variable $x_{1}\,$ anstelle der Basisvariablen $y_{B}\,$ freizulegen.

Durchführung eines Austauschschrittes:

Mit dem Austauschschritt wird die Basisvariable $y_{B}\,$ gegen die Nichtbasisvariable $x_{1}\,$ ausgetauscht. Zuerst legen wir in der Gleichung für $y_{B}\,$ die unabhängige Unbekannte $x_{1}\,$ frei,

${\begin{matrix}y_{B}~=~150-1\,x_{1}-1\,x_{2}\qquad \qquad \qquad \qquad \qquad \\[3pt]\Longrightarrow \quad x_{1}~=~150-1\,y_{B}-1\,x_{2}\end{matrix}}$

und anschließend ersetzen wir $x_{1}\,$ in den restlichen Gleichungen für den so erhaltenen Ausdruck:

${\begin{matrix}z&~=~&~~~~0&+~300\,(150-1\,y_{B}-1\,x_{2})&+~500\,x_{2}\\[2pt]y_{A}&~=~&~170&-~~~~1\,(150-1\,y_{B}-1\,x_{2})&-~~~~2\,x_{2}\\[2pt]y_{C}&~=~&~180&+~~~~0\,(150-1\,y_{B}-1\,x_{2})&-~~~~3\,x_{2}\end{matrix}}$

Das führt zu den oben beschriebenen Verwandlungsregeln für das Simplex-Tableau nach dem Pivotelement $a_{21}=1$. Wenn $x_{1}\,$ die Zeile von $y_{B}\,$ besetzt und $y_{B}\,$ die Spalte von $x_{1}\,$, dann ist das neue Gleichungssystem

${\begin{matrix}z&=&45000&-~300\,y_{B}&+~200\,x_{2}\\[2pt]y_{A}&=&~~~~20&+~~~~1\,y_{B}&-~~~~1\,x_{2}\\[2pt]x_{1}&=&~~~150&-~~~~1\,y_{B}&-~~~~1\,x_{2}\\[2pt]y_{C}&=&~~~180&+~~~~0\,y_{B}&-~~~~3\,x_{2}\end{matrix}}$

Die Unbekannte $x_{1}\,$ ist in die Basis gerückt, die jetzt unabhängige Unbekannte $y_{B}\,$ ist eine Nichtbasisvariable und erscheint in der Kopfzeile.

Diese Lösung bedeutet: Es werden $150\,$ ME von Produkt 1 (Gleichung mit freigelegtem $x_{1}\,$) produziert. Von Produkt 2 wird nichts gefertigt ($x_{2}=0\,$ ist Nichtbasisvariable). Damit erzielt die Firma einen Gesamtdeckungsbeitrag von 45.000 Euro. Maschine A steht $20\,$ Stunden pro Monat still (sie läuft nur 150 der 170 möglichen Stunden). Maschine B hat keine Leerlaufzeit. Maschine C steht $180\,$ Stunden still, das heißt, sie wird überhaupt nicht benötigt. Dies ergibt sich auch direkt aus der Aufgabenstellung: Maschine C wird nur bei der Herstellung von Produkt 2 benötigt. Da dieses nicht gefertigt wird, braucht man Maschine C noch nicht.

Wiederholung der Simplexschritte:

Da die Zielfunktion im entstandenen Simplex-Tableau noch einen positiven Koeffizienten enthält, kann man die Lösung noch verbessern. Dies geschieht mittels einer weiteren Simplex-Iteration. Bei der Auswahl des Pivotelementes kommt nur die Unbekannte $x_{2}\,$ in Frage, da nur hier der Zielfunktionskoeffizient positiv ist. Die Basisvariable des Pivots ergibt sich aus

${\begin{matrix}0\leq {\bar {y}}_{A}=~20-1\,{\bar {x}}_{2}&\quad {\text{(zu Basisvariable }}y_{A}{\text{)}}\\[2pt]0\leq {\bar {x}}_{1}=150-1\,{\bar {x}}_{2}&\quad {\text{(zu Basisvariable }}x_{1}{\text{)}}\\[2pt]0\leq {\bar {y}}_{C}=180-3\,{\bar {x}}_{2}&\quad {\text{(zu Basisvariable }}y_{C}{\text{)}}\\[2pt]\end{matrix}}$

und somit

${\bar {x}}_{2}\leq \min \left\{{\frac {20}{1}},\ {\frac {150}{1}},\ {\frac {180}{3}}\right\}=\min\{20,150,60\}=20$

Damit ist Zeile $y_{A}\,$ die einzige Basisunbekannte, die für einen Pivot in Frage kommt. Die Basisvariable $y_{A}\,$ wird gegen die Nichtbasisvariable $x_{2}\,$ ausgetauscht; das Pivotelement ist $1\,$. Mit den gleichen Umrechnungen wie oben erhält man als neues Gleichungssystem

${\begin{matrix}z&=&49000&-~100\,y_{B}&-~200\,y_{A}\\[2pt]x_{2}&=&~~~~20&+~~~~1\,y_{B}&-~~~~1\,y_{A}\\[2pt]x_{1}&=&~~~130&-~~~~2\,y_{B}&+~~~~1\,y_{A}\\[2pt]y_{C}&=&~~~120&-~~~~3\,y_{B}&+~~~~3\,y_{A}\end{matrix}}$

Da die Zielfunktion nun keine positiven Koeffizienten mehr enthält, ist eine optimale Lösung erreicht. Es werden $130\,$ ME von Produkt 1 und $20\,$ ME von Produkt 2 hergestellt. Damit erzielt die Firma einen Gesamtdeckungsbeitrag von 49.000 Euro. Maschine A und Maschine B sind voll ausgelastet. Maschine C läuft 60 Stunden und hat daher noch eine ungenutzte Kapazität von $y_{C}=120\,$ Stunden.

Datenstrukturen und Umwandlungsformeln

Das parametrische Gleichungssystem

${\begin{matrix}z&=&10000&+~300\,x_{1}&+~500\,x_{2}\\[3pt]x_{A}&=&~~~170&-~~~~1\,x_{1}&-~~~~2\,x_{2}\\[2pt]x_{B}&=&~~~150&-~~~~1\,x_{1}&-~~~~1\,x_{2}\\[2pt]x_{C}&=&~~~180&+~~~~0\,x_{1}&-~~~~3\,x_{2}\end{matrix}}$

kann man auch über eine Simplextafel, auch Simplex-Tableau genannt, darstellen:

	${\begin{matrix}~~~1&~~~x_{1}&~~~x_{2}\end{matrix}}$
${\begin{matrix}z\\[4pt]x_{A}\\[4pt]x_{B}\\[4pt]x_{C}\end{matrix}}$	${\begin{matrix}10000&300&500\\[4pt]170&-1&-2\\[4pt]150&-1&-1\\[4pt]180&0&-3\end{matrix}}$

Die Umwandlung der Einträge des Simplextableaus von einem Schritt auf den nächsten ist wie oben im Beispiel leicht abzuleiten und lässt sich in folgendem Schema zusammenfassen:

${\begin{matrix}\delta \,x_{i}&\!=\!&(~~\alpha )&\!\!\!x_{j}&\!+\!&(~~\sigma )&\!\!\!x_{s}\\[6pt]\delta \,x_{r}&\!=\!&(~~\zeta )&\!\!\!x_{j}&\!+\!&(~~p)&\!\!\!x_{s}\end{matrix}}$

${x_{r}\leftrightarrow x_{s}}$

${\begin{matrix}p\,x_{i}&\!=\!&(\textstyle {\frac {\alpha p\,-\,\zeta \sigma }{\delta }})&\!\!\!x_{j}&\!+\!\!&(~\sigma )&\!\!\!x_{r}\\[6pt]p\,x_{s}&\!=\!&(~-\zeta ~)&\!\!\!x_{j}&\!+\!\!&(~\delta )&\!\!\!x_{r}\\\end{matrix}}$

Hier steht das Zeichen $\delta \,$ für den gemeinsamen Nenner des Gleichungssystems, das Zeichen $p\,$ für den Zähler des Pivotelements, $\zeta \,$ für einen sonstigen Eintrag der Pivotzeile, $\sigma \,$ für einen sonstigen Eintrag der Pivotspalte, und $\alpha \,$ für einen beliebigen Eintrag abseits von Pivotzeile und Pivotspalte. Einträge der Zielbeitragszeile ($x_{i}\!=\!z\,$) und der Basiswertspalte ($x_{j}\!=\!1\,$) werden nach denselben Regeln umgewandelt.

Über die große Anzahl von Lehrbüchern verteilt findet sich auch eine große Anzahl verschiedener Darstellungen einer linearen Optimierungsaufgabe, und die Meinungen über die Zweckmäßigkeit der jeweils ausgewählten Darstellung gehen weit auseinander. Als Beispiel einer aufgeblähten und eher umständlichen, aber trotzdem weit verbreiteten Darstellung sei folgendes Spaltenbasistableau angeführt:

${\begin{matrix}~~~~~1\,x_{1}&+~~~~2\,x_{2}&+x_{A}&&&&=&170\\[2pt]~~~~~1\,x_{1}&+~~~~1\,x_{2}&&+x_{B}&&&=&150\\[2pt]~~~~~0\,x_{1}&+~~~~3\,x_{2}&&&+x_{C}&&=&180\\[3pt]-~300\,x_{1}&-~500\,x_{2}&&&&+z&=&10000\end{matrix}}$

	${\begin{matrix}x_{1}&x_{2}&(x_{A})&(x_{B})&(x_{C})&(z)&(=)&1\end{matrix}}$
${\begin{matrix}(x_{A})\\[4pt](x_{B})\\[4pt](x_{C})\\[4pt](z)\end{matrix}}$	${\begin{matrix}+1&+2&+1&0&0&0&(=)&170\\[4pt]+1&+1&0&+1&0&0&(=)&150\\[4pt]0&+3&0&0&+1&0&(=)&180\\[4pt]-300&-500&0&0&0&+1&(=)&10000\end{matrix}}$

wobei die Bedeutung der einzelnen Einträge keineswegs festgeschrieben und sorgfältig zu dokumentieren ist. Zum Beispiel:

	${\begin{matrix}~~x_{1}&~~x_{2}&~(x_{A})&~(x_{B})&~(x_{C})&~~(z)&(=)&~~K\end{matrix}}$
${\begin{matrix}(x_{A})\\[4pt](x_{B})\\[4pt](x_{C})\\[4pt](z)\end{matrix}}$	${\begin{matrix}+1&+2&+1&0&0&0&(=)&170\\[4pt]+1&+1&0&+1&0&0&(=)&150\\[4pt]0&+3&0&0&+1&0&(=)&180\\[4pt]-300&-500&0&0&0&+1&(=)&10000\end{matrix}}$

	$x_{1}$	$x_{2}$	$x_{A}$	$x_{B}$	$x_{C}$	$z$	$(=)$	$K$
$(x_{A})$	$+1$	$+2$	$+1$	$0$	$0$	$0$	$(=)$	$170$
$(x_{B})$	$+1$	$+1$	$0$	$+1$	$0$	$0$	$(=)$	$150$
$(x_{C})$	$0$	$+3$	$0$	$0$	$+1$	$0$	$(=)$	$180$
$(z)$	$-300$	$-500$	$0$	$0$	$0$	$+1$	$(=)$	$10000$

"In der Kopfzeile stehen die Nichtbasisvariablen $x_{1},\,x_{2}$ mit dem Wert 0, während die Basisvariablen $y_{i}\,$ in der ersten Spalte stehen. In der obersten Zeile – der Gleichung für die Zielfunktion – stehen die Zielfunktionskoeffizienten $c_{i}\,$, also 300 und 500. Auf der rechten Seite steht die aktuelle Basislösung, was in diesem Fall genau $b\,$ ist. In der obersten Zeile der rechten Seite steht das Negative des Zielfunktionswertes für die aktuelle Basislösung, im Beispiel also das Negative des Gesamtdeckungsbeitrags."

Der einzige Vorteil dieser Darstellung scheint darin zu liegen, dass sich ihre Umwandlung von einem Schritt auf den nächsten als Matrizenmultiplikation beschreiben lässt:

Die Variablen $y_{i}\,$ bilden eine zulässige Basis $B\,$, deren Basismatrix $A_{B}\,$ die Einheitsmatrix ist. Die zugehörige Basislösung ist also $A_{B}^{-1}b=b$. Diese Lösung entspricht dem Fall, dass nichts produziert wird ($x_{i}=0\,$). Die Restkapazität der Maschinen, die durch die Werte der $y_{i}\,$ angegeben wird, ist hier deren Gesamtkapazität (170, 150 und 180), da die Maschinen nicht genutzt werden.

Einträge in Bruchzahlform

Das obige Beispiel wurde in algebraischer Notation gelöst, indem man im Gleichungssystem die Basisvariablen bezüglich der restlichen, unabhängigen Variablen freilegt. Um Rundungsfehler zu vermeiden, kann man mit Bruchzahlen arbeiten und einen gemeinsamen Nenner für das gesamte Gleichungssystem wählen (dass dieser Nenner oben immer $1\,$ war, ist Zufall). Um in jedem Schritt den gemeinsamen Nenner für das Gesamtsystem zu finden, müssen wir die Einträge nicht zusätzlich analysieren. Falls das Startsystem ganzzahlig ist (was sich normalerweise durch Erweiterung erreichen lässt), gilt die Regel:

• Der Zähler des gewählten Pivotelements ist ein gemeinsamer Nenner für das darauffolgende System

Wenn wir die neuen Tableau-Einträge mit diesem gemeinsamen Nenner multiplizieren, erhalten wir stets ganzzahlige Zähler. Bei der Berechnung dieser Zähler für die neuen Tableau-Einträge wird dann ungeprüft durch den alten Nenner geteilt, wobei das Ergebnis ganzzahlig sein muss.

Als Beispiel für diese Vorgehensweise lösen wir dieselbe Aufgabe wie oben noch einmal mit Dantzigs Pivotauswahl; hierbei wird als eingehende Pivotvariable diejenige mit größtem Zielfunktionskoeffizienten gewählt:

${\begin{matrix}z&=&(&~~~~~~~0&+~300\,x_{1}&+~500\,x_{2}&)~/~1\\[2pt]y_{A}&=&(&~~~~170&-~~~~~\,x_{1}&-~~~~2\,x_{2}&)~/~1\\[2pt]y_{B}&=&(&~~~~150&-~~~~~\,x_{1}&-~~~~~\,x_{2}&)~/~1\\[2pt]y_{C}&=&(&~~~~180&+~~~~0\,x_{1}&-~~~~\mathbf {3\,x_{2}} &)~/~1\end{matrix}}$

Durch Erhöhung der unabhängigen Variable $x_{2}\,$ lässt sich die Zielfunktion $z\,$ vergrößern; die erste der Basisvariablen, die in diesem Fall auf Null stößt, ist $y_{C}\,$. Folglich kann man $x_{2}\,$ anstelle von $y_{C}\,$ freilegen und erhält folgendes System mit ${\bar {z}}=30000$:

${\begin{matrix}z&=&(&~90000&+~900\,x_{1}&-~500\,y_{C}&)~/~3\\[2pt]y_{A}&=&(&~~~~150&-~~~~\mathbf {3\,x_{1}} &+~~~~2\,y_{C}&)~/~3\\[2pt]y_{B}&=&(&~~~~270&-~~~~3\,x_{1}&+~~~~~\,y_{C}&)~/~3\\[2pt]x_{2}&=&(&~~~~180&+~~~~0\,x_{1}&-~~~~~\,y_{C}&)~/~3\end{matrix}}$

Wenn man die unabhängige Variable $x_{1}\,$ erhöht, vergrößert man die Zielfunktion; die erste der Basisvariablen, die dann auf Null stößt, ist $y_{A}\,$. Folglich legt man $x_{1}\,$ anstelle von $y_{A}\,$ frei und erhält folgendes System mit ${\bar {z}}=45000$:

${\begin{matrix}z&=&(&135000&-~900\,y_{A}&+~100\,y_{C}&)~/~3\\[2pt]x_{1}&=&(&~~~~150&-~~~~3\,y_{A}&+~~~~2\,y_{C}&)~/~3\\[2pt]y_{B}&=&(&~~~~120&+~~~~3\,y_{A}&-~~~~~\mathbf {\,y_{C}} &)~/~3\\[2pt]x_{2}&=&(&~~~~180&+~~~~0\,y_{A}&-~~~~~\,y_{C}&)~/~3\end{matrix}}$

Wenn man die unabhängige Variable $y_{C}\,$ erhöht, vergrößert man die Zielfunktion; die erste der Basisvariablen, die dann auf Null stößt, ist $y_{B}\,$. Folglich legt man ${y_{C}\,}$ anstelle von $y_{B}\,$ frei und erhält folgendes System mit ${\bar {z}}=49000$:

${\begin{matrix}z&=&(&~49000&-~200\,y_{A}&-~100\,y_{B}&)~/~1\\[2pt]x_{1}&=&(&~~~~130&+~~~~~\,y_{A}&-~~~~2\,y_{B}&)~/~1\\[2pt]y_{C}&=&(&~~~~120&+~~~~3\,y_{A}&-~~~~3\,y_{B}&)~/~1\\[2pt]x_{2}&=&(&~~~~~20&-~~~~~\,y_{A}&+~~~~~\,y_{B}&)~/~1\end{matrix}}$

Die Zielfunktion hat Wert ${\bar {z}}=49000\,$ und lässt sich nicht mehr erhöhen; die Lösung ist wie oben ${\bar {x}}_{1}=130,\,{\bar {x}}_{2}=20$.  Wir beobachten nebenher, dass Dantzigs Pivotauswahl im Vergleich zur anfangs gewählten Alternative einen Schritt mehr gebraucht hat, um zur Lösung zu gelangen.