zum Artikel Simplex-Verfahren#Mathematische Beschreibung

Grundidee (160801)[Bearbeiten | Quelltext bearbeiten]

Die Simplex-Verfahren dienen zur Lösung linearer Optimierungsaufgaben, das ist die Suche nach reellen Variablenwerten, die ein System linearer Ungleichungen und Gleichungen erfüllen und dabei eine lineare Zielfunktion maximieren oder minimieren.

Ausgegangen wird dabei von der Form

(LP)

\max _{x\in \mathbb {R} ^{n}}\left\{c^{T}x\mid \;Ax\leq b,\;x\geq 0\right\}\,,

wobei $A\in \mathbb {R} ^{m\times n}$ eine Matrix mit reellen Einträgen ist, $c\in \mathbb {R} ^{n}$ der sogenannte Zielfunktionsvektor, und $b\in \mathbb {R} ^{m}\!,~b\geq 0$ ein Spaltenvektor mit nichtnegativen Einträgen $b_{i}\geq 0$ . Ziel ist es, einen Punkt $x$ zu finden, der das lineare Ungleichungssystem erfüllt und einen möglichst hohen Zielfunktionswert $F(x)=c^{T}x$ hat.

Jedes lineare Programm kann durch einfache Umformungen in die Form

(LP)

\max _{x\in \mathbb {R} ^{n}}\left\{c^{T}x\mid \;Ax\leq b,\;x\geq 0\right\}

gebracht werden, bei welcher die Vorzeichen in $b\in \mathbb {R} ^{m}$ freilich immer noch beliebig sind. Das geschieht wie folgt:

Ein Minimierungsproblem kann durch Multiplikation der Zielfunktion mit $(-1)$ in ein Maximierungsproblem verwandelt werden.
Ungleichungen $\textstyle {\sum _{j}A_{ij}x_{j}\geq b_{i}}$ können auch $\textstyle {\sum _{j}(-A_{ij})x_{j}\leq -b_{i}}$ geschrieben werden.
Vorhandene Gleichungsgruppen $\forall i~~\textstyle {\sum _{j}A_{ij}x_{j}=b_{i}}$ können in Ungleichungsgruppen $\forall i~~\textstyle {\sum _{j}A_{ij}x_{j}\leq b_{i}}$ mit $\textstyle {\sum _{j}{\big (}-\sum _{i}A_{ij}{\big )}x_{j}\leq -b_{i}}$ aufgespalten werden.
Variablengruppen $x_{j}$ mit beliebigem Wertebereich können über eine zusätzliche Variable und $x_{j}=u_{j}-w$ durch nichtnegativen Variablen $u_{j}\geq 0,w\geq 0$ ersetzt werden.

In Gegensatz zu diesen Umformungen ist die stets vorausgesetzte Startbedingung $b\geq 0$ nur über die Lösung einer Hilfsaufgabe in einer sogenannten "Phase 1" zu erreichen; dabei ist diese Hilfsaufgabe grundsätzlich ebenso aufwändig wie die eigentliche Optimierung.

Mathematische Beschreibung des Verfahrens[Bearbeiten | Quelltext bearbeiten]

Die folgende Beschreibung ist eher ausführlich gehalten; eine knappere Beschreibung für eine allgemeinere Algorithmengruppe befindet sich unter Pivotverfahren.

Das (primale) Simplex-Verfahren setzt sich aus zwei Phasen zusammen:

In einer Vorphase wird eine beliebige, nicht unbedingt nichtnegative Basislösung der Aufgabe erstellt.
Phase 1 bestimmt eine zulässige Startlösung oder stellt fest, dass das Problem keine Lösung besitzt.
Phase 2 verbessert eine bestehende Lösung immer weiter, bis keine Verbesserung der Zielfunktion mehr möglich ist oder die Unbeschränktheit des Problems festgestellt wird.

Bestimmung einer Startbasis (Vorphase)[Bearbeiten | Quelltext bearbeiten]

Als erster Schritt eines Simplexverfahrens muss die lineare Optimierungsaufgabe so dargestellt werden, dass sie ausschließlich lineare Gleichungen in nichtnegativen Unbekannten und der Zielvariablen enthält. Das ist immer möglich; im Falle des obigen Systems erhalten wir

Maximiere

z\,

so dass

x_{A}\geq 0

,

x_{I}\geq 0

und

{\begin{bmatrix}A&I&0\\[3pt]-c_{A}&0&1\end{bmatrix}}{\begin{bmatrix}x_{A}\\x_{I}\\z\end{bmatrix}}={\begin{bmatrix}b\\[3pt]f\end{bmatrix}}

Dieses Gleichungssystem ist in besonderer Form, der sogenannten Basisform, bei welcher eine Teilmenge ausgewählter Spalten eine Einheitsmatrix bilden. Die Spalten der Einheitsmatrix müssen aber nicht unbedingt die Spalten der sogenannten Schlupfvariablen $x_{I}\,$ sein. Die Information des obigen Gleichungssystems lässt sich in einem sogenannten Tableau speichern; ein Simplextableau ("Simplextafel") ist nichts weiter als eine Datenstruktur für das Gleichungssystem:

* ${\boldsymbol {x_{A}}}$	* ${\boldsymbol {x_{I}}}$	* ${\boldsymbol {z}}$	* ${\boldsymbol {1}}$

$A\,$	$I\,$	$0\,$	$b\,$
$-c_{A}\,$	$0\,$	$1\,$	$f\,$

Die obige Darstellung ist die klassische Darstellungsform einer Optimierungsaufgabe. Nun lässt sich das Gleichungssystem der Optimierungsaufgabe aber auch etwas knapper und symmetrischer in sogenannter Dictionary-Form darstellen. Aus der obigen Aufgabestellung folgt nämlich auch

Maximiere

z\,

so dass

x_{A}\geq 0

,

x_{I}\geq 0

und

{\begin{bmatrix}z\\x_{I}\end{bmatrix}}={\begin{bmatrix}f&c_{A}\\[3pt]b&-A\end{bmatrix}}{\begin{bmatrix}1\\x_{A}\end{bmatrix}}

Das entsprechende Dictionary-Tableau dazu ist

	* $\,{\boldsymbol {1}}$	* $\,{\boldsymbol {x_{A}}}$

$z\,$	$f\,$	$c_{A}\,$
$x_{I}\,$	$b\,$	$-A\,$

In der Literatur über Lineare Optimierung gibt noch es eine Vielzahl weiterer Arten, eine allgemeine lineare Optimierungsaufgabe darzustellen; hier sollen diese beiden Varianten als repräsentative Beispiele dienen.

In der folgenden Ausführung wird stillschweigend vorausgesetzt, dass die Zielvariable maximiert (nicht minimiert) wird und dass für eine zulässige Lösung der Optimierungsaufgabe sämtliche Unbekannte außer der Zielvariablen nichtnegativ zu sein haben; diese Bedingungen werden nicht mehr besonders erwähnt.

Übergang auf die Darstellung einer Nachbarbasis[Bearbeiten | Quelltext bearbeiten]

Das folgende Schema zeigt, wie sich die Einträge des klassischen Tableaus von einem Schritt auf den nächsten verändern. Das lässt sich am leichtesten an einem Pivotsystem betrachten, das nur eine einzige Basisvariable und eine einzige Nichtbasisvariable hat:

${\begin{matrix}(\pi )&\!\!\!x_{s}&+&(1)&\!\!\!x_{r}&+&(0)&\!\!\!z&=&(~~\varrho )\\[6pt](\sigma )&\!\!\!x_{s}&+&(0)&\!\!\!x_{r}&+&(1)&\!\!\!z&=&(~~\alpha )\\\end{matrix}}$

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

${\begin{matrix}(1)&\!\!\!x_{r}&+&(~~~{\frac {1}{\pi }})&\!\!\!x_{r}&+&(0)&\!\!\!z&=&(~~~~~{\frac {\varrho }{\pi }}~)\\[6pt](0)&\!\!\!x_{r}&+&(-{\frac {\sigma }{\pi }})&\!\!\!x_{r}&+&(1)&\!\!\!z&=&({\scriptstyle \alpha }-{\frac {\varrho \sigma }{\pi }})\\\end{matrix}}$

Natürlich hat ein Pivotsystem viele weitere Unbekannte, doch deren Einträge verändern sich genauso wie die Einträge der Zielbeitragszeile oder der Basiswertspalte. Hier steht $\pi \,$ für das Pivotelement, $\varrho \,$ 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.

Es folgt eine Matrixbeschreibung des klassischen Tableaus. Die Matrix $[N~B]$ sei nun eine beliebige Spaltenumstellung der Matrix $[A~I]$ , für welche die sogenannte Basismatrix $B\,$ umkehrbar sein muss. Die den Spalten von $B\,$ zugeordneten Variablen $x_{B}\,$ heißen Basisvariablen oder einfach Basis. Wir können also als Startbasis $x_{B}=x_{I}\,$ mit $B=I\,$ , $N=A\,$ auswählen. Es gilt nun

{\begin{bmatrix}B&0\\[3pt]-c_{B}&1\end{bmatrix}}^{-1}{\begin{bmatrix}A&I&0\\[3pt]-c_{A}&0&1\end{bmatrix}}{\begin{bmatrix}x_{A}\\x_{I}\\z\end{bmatrix}}={\begin{bmatrix}B&0\\[3pt]-c_{B}&1\end{bmatrix}}^{-1}{\begin{bmatrix}b\\[3pt]f\end{bmatrix}}

{\begin{bmatrix}B^{-1}&0\\[3pt]c_{B}B^{-1}&1\end{bmatrix}}{\begin{bmatrix}A&I&0\\[3pt]-c_{A}&0&1\end{bmatrix}}{\begin{bmatrix}x_{A}\\x_{I}\\z\end{bmatrix}}={\begin{bmatrix}B^{-1}&0\\[3pt]c_{B}B^{-1}&1\end{bmatrix}}{\begin{bmatrix}b\\[3pt]f\end{bmatrix}}

{\begin{bmatrix}B^{-1}\!A&B^{-1}&0\\[3pt]c_{B}B^{-1}\!A-c_{A}&c_{B}B^{-1}&1\end{bmatrix}}{\begin{bmatrix}x_{A}\\x_{I}\\z\end{bmatrix}}={\begin{bmatrix}b\\[3pt]f\end{bmatrix}}

Das klassische Tableau für eine beliebige Basis ist

* ${\boldsymbol {x_{A}}}$	* ${\boldsymbol {x_{I}}}$	* ${\boldsymbol {z}}$	* ${\boldsymbol {1}}$

$B^{-1}\!A$	$B^{-1}\,$	$0\,$	$B^{-\!1}b$
$c_{B}B^{-1}\!A-c_{A}$	$c_{B}B^{-1}\,$	$1\,$	$c_{B}B^{-\!1}b+f$

Das folgende Schema zeigt, wie sich die Einträge des Dictionary-Tableaus von einem Schritt auf den nächsten verändern. Das lässt sich am leichtesten an einem Pivotsystem betrachten, das nur eine einzige unabhängige Unbekannte und eine einzige freigelegte Unbekannte hat:

${\begin{matrix}z&=&(~~\alpha )&+&(~~\sigma )&\!\!\!x_{s}\\[6pt]x_{r}&=&(~~\varrho )&+&(~~\pi )&\!\!\!x_{s}\\\end{matrix}}$

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

${\begin{matrix}z&=&(~~{\scriptstyle \alpha }-{\frac {\varrho \sigma }{\pi }})&+&(~~{\frac {\sigma }{\pi }})&\!\!\!x_{r}\\[6pt]x_{s}&=&(~~~-{\frac {\varrho }{\pi }}~)&+&(~~{\frac {1}{\pi }})&\!\!\!x_{r}\\\end{matrix}}$

Das Pivotsystem hat viele weitere Unbekannte, doch deren Einträge verändern sich genauso wie die Einträge der Zielbeitragszeile oder der Basiswertspalte. Hier steht $\pi \,$ für das Pivotelement, $\varrho \,$ 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.

Für eine Matrixbeschreibung des Dictionary-Tableaus müssen die Variablen umgestellt werden, so dass die Nichtbasisvariablen an erster Stelle stehen, gefolgt von den Basisvariablen. Wir erhalten

{\begin{bmatrix}1&-c_{B}\\[3pt]0&B\end{bmatrix}}{\begin{bmatrix}z\\x_{B}\end{bmatrix}}~=~{\begin{bmatrix}f&c_{N}\\[3pt]b&-N\end{bmatrix}}{\begin{bmatrix}1\\x_{N}\end{bmatrix}}

{\begin{bmatrix}z\\x_{B}\end{bmatrix}}~=~{\begin{bmatrix}1&-c_{B}\\[3pt]0&B\end{bmatrix}}^{-1}{\begin{bmatrix}f&c_{N}\\[3pt]b&-N\end{bmatrix}}{\begin{bmatrix}1\\x_{N}\end{bmatrix}}~=~{\begin{bmatrix}1&c_{B}B^{-1}\\[3pt]0&B^{-1}\end{bmatrix}}{\begin{bmatrix}f&c_{N}\\[3pt]b&-N\end{bmatrix}}{\begin{bmatrix}1\\x_{N}\end{bmatrix}}

{\begin{bmatrix}z\\[3pt]x_{B}\end{bmatrix}}={\begin{bmatrix}f+c_{B}B^{-1}b&c_{N}-c_{B}B^{-1}\!N\\[3pt]B^{-1}b&-B^{-1}\!N\end{bmatrix}}{\begin{bmatrix}1\\x_{N}\end{bmatrix}}

Das dazugehörende Dictionary-Tableau ist natürlich

	* $\,{\boldsymbol {1}}$	* $\,{\boldsymbol {x_{N}}}$

$z\,$	$f+c_{B}B^{-1}b\,$	$c_{N}-c_{B}B^{-1}\!N$
$x_{B}\,$	$B^{-1}b\,$	$-B^{-1}\!N$

Bestimmung einer zulässigen Basis (Phase 1)[Bearbeiten | Quelltext bearbeiten]

Zunächst muss eine zulässige Startlösung berechnet werden, bevor man die Phase II starten kann. Eine Möglichkeit dafür ist, für jede Zeile $i$ eine künstliche Variable $z_{i}$ einzuführen und dann folgendes lineare Programm zu betrachten:

(LP1)

\min {\Bigl \{}\left.\sum _{i=1}^{m}z_{i}\;\right|\;Ax+z=b,\;x,z\geq 0{\Bigr \}}~.

In einer Optimallösung dieses Hilfsproblems sind die künstlichen Variablen so klein wie möglich, wobei sie immer nichtnegativ bleiben müssen. Das ursprüngliche Problem (LP) besitzt genau dann eine zulässige Lösung, wenn es eine Lösung des Hilfsproblems mit $z=0$ gibt, bei der also keine künstlichen Variablen verwendet werden.

Das Hilfsproblem (LP1) besitzt für $b\geq 0$ eine einfache zulässige Startlösung, nämlich $(x,z)=(0,b)$ . Darüber hinaus gilt für jede zulässige Lösung des Hilfsproblems $z\leq b$ , so dass die Zielfunktion nach oben durch $\sum _{i=1}^{m}b_{i}$ beschränkt ist. Dieses lineare Programm besitzt also eine Optimallösung, die ausgehend von der Startlösung $(0,b)$ mit Phase II des Hilfsproblems bestimmt werden kann. Findet man dabei eine Optimallösung $(x^{*},z^{*})$ mit $z^{*}=0$ , ist $x^{*}$ offensichtlich eine zulässige Startlösung für das Ausgangsproblem (LP), mit der dessen Phase II gestartet werden kann. Gelingt dies nicht, so ist das Ausgangsproblem nicht lösbar und man kann aufhören.

Bestimmung einer Optimumbasis (Phase 2)[Bearbeiten | Quelltext bearbeiten]

Phase II ist ein iteratives Verfahren, das in jedem Schritt versucht, aus einer zulässigen Lösung eine neue Lösung mit besserem Zielfunktionswert zu konstruieren, bis dies nicht mehr möglich ist. Dies entspricht im wesentlichen der wiederholten Lösung eines linearen Gleichungssystems mit Hilfe des Gaußschen Eliminationsverfahrens. Dabei kann auch evtl. Unbeschränktheit des Optimierungsproblems festgestellt werden. Zur Erklärung dieser Phase ist die Definition einiger Begriffe notwendig.

Verschiedenes[Bearbeiten | Quelltext bearbeiten]

Basen, Basislösungen und Ecken[Bearbeiten | Quelltext bearbeiten]

In der Phase II des Simplex-Verfahrens spielt der Begriff der Basis eine wesentliche Rolle. Eine Basis $B$ von $A$ ist eine Teilmenge der Spalten von $A$ , die eine reguläre, also invertierbare Untermatrix $A_{B}$ bilden. $B$ wird dabei als Indexvektor über die Spalten von $A$ dargestellt. Die Variablen, die zu den Basisspalten gehören, also in $B$ enthalten sind, heißen Basisvariablen, die anderen Nichtbasisvariablen. Die Basislösung zu einer gegebenen Basis $B$ ist der eindeutige Vektor $x$ , dessen Basisvariablen sich als $A_{B}^{-1}b$ ergeben und dessen Nichtbasisvariablen alle den Wert 0 haben. Solch eine Basislösung ist also eine zulässige Lösung des Gleichungssystems $Ax=b$ mit höchstens $m$ Nicht-Null-Einträgen. In dem Fall, dass alle Komponenten von $x$ nichtnegativ sind, ist $x$ auch eine zulässige Lösung von (LP), also ein Punkt des Polyeders $P$ .

Man kann zeigen, dass jede zulässige Basislösung einer Ecke (Extremalpunkt) des Polyeders entspricht und umgekehrt. Eine Basislösung heißt nicht degeneriert, wenn sie genau $m$ Nicht-Null-Einträge besitzt. In diesem Fall gibt es eine eindeutige zugehörige Basis. Sind alle Basislösungen nicht degeneriert, gibt es also eine bijektive Abbildung zwischen Basen der Matrix $A$ und Ecken des Polyeders $P$ .

Ist eine Basislösung dagegen degeneriert, so hat sie weniger als $m$ Nicht-Null-Einträge und kann zu mehreren Basen gehören. In diesem Fall definiert also jede Basis der Matrix $A$ genau eine Ecke des Polyeders $P$ , aber nicht umgekehrt. Dieser Fall tritt auf, wenn eine Ecke von mehr als $n$ Ungleichungen definiert wird, was bei praktischen Planungsproblemen so gut wie immer der Fall ist.

Iterative Simplexschritte[Bearbeiten | Quelltext bearbeiten]

Die Phase II versucht iterativ in jedem Austauschschritt, aus einer bestehenden Basislösung, wie sie z. B. in Phase I bestimmt wurde, eine neue Basislösung mit mindestens genauso gutem Zielfunktionswert zu konstruieren, indem sie eine Basisvariable aus der Basis entfernt und dafür eine bisherige Nichtbasisvariable in die Basis aufnimmt. Dies wird so lange wiederholt, bis kein verbessernder Austausch mehr möglich ist.

In dieser Phase gibt es zu Beginn jeder Iteration ein sogenanntes Simplextableau zur aktuellen Basis $B$ , in dem die Berechnungen durchgeführt werden. Es entspricht im wesentlichen dem linearen Gleichungssystem $[A\;I]\,x=b\,$ , $[c^{T}\;0]\,x=z$ , nach einer Basistransformation in die aktuelle Basis.

Simplextableau[Bearbeiten | Quelltext bearbeiten]

Für die Formulierung des Simplextableaus gibt es unterschiedliche Möglichkeiten; die hier vorgestellte Version basiert auf ^[1].

Jeder Simplexschritt geht von einer zulässigen Basis $B$ aus. Zu Beginn des Schrittes hat das zugehörige Simplextableau die folgende Form:

\left[\left.{\begin{matrix}{\bar {A}}&I&0\\{\bar {c}}&0&1\end{matrix}}\;\right|\;{\begin{matrix}{\bar {b}}\\{\bar {f}}\end{matrix}}\;\right]

Hierbei sind zur Vereinfachung der Darstellung die Spalten so umsortiert worden, dass alle Nichtbasisspalten links stehen und alle Basisspalten rechts. $I$ ist die $(m\!\times \!m)$ -dimensionale Einheitsmatrix. Die $(m\!\times \!n)$ -dimensionale Matrix ${\bar {A}}$ und die restlichen obigen Einträge sind definiert durch

{\bar {A}}=A_{B}^{-1}A_{N}

{\bar {b}}=A_{B}^{-1}b

{\bar {c}}=c_{N}^{T}-c_{B}^{T}A_{B}^{-1}A_{N}

{\bar {f}}=c_{B}^{T}A_{B}^{-1}b

Dabei ist

$A_{B}$ die reguläre Untermatrix von $A$ , die aus den Spalten der aktuellen Basis $B$ besteht,
$A_{N}$ die (meistens nicht quadratische) Untermatrix von $A$ , die aus den Nichtbasisspalten besteht,
$c_{B}$ die Teile des Zielfunktionsvektors $c$ , die aus den Basisspalten bestehen, und
$c_{N}$ die Teile des Zielfunktionsvektors $c$ , die aus den Nichtbasisspalten bestehen.

Die rechte Seite ${\bar {b}}$ enthält die Werte der Basisvariablen von der zu $B$ gehörenden Basislösung; ${\bar {f}}$ ist der Zielfunktionswert dieser Basislösung. Zu Beginn der Phase I bilden die Variablen $z_{i}$ eine zulässige Basis mit der Einheitsmatrix als Basismatrix und der zugehörigen Basislösung $(x,z)=(0,b)$ . Daher steht am Anfang auf der rechten Seite einfach der Vektor $b$ .

Die Einträge des Vektors ${\bar {c}}$ heißen reduzierte Kosten der Nichtbasisvariablen. Der Wert ${\bar {c}}_{j}$ gibt die Verbesserung der Zielfunktion an, wenn Variable $x_{j}$ um eine Einheit erhöht wird. Sind zu Beginn eines Simplexschrittes alle reduzierten Kostenkoeffizienten negativ oder 0, sind daher die aktuelle Basis und die zugehörige Basislösung optimal, da die Aufnahme einer bisherigen Nichtbasisvariable in die Basis den Zielfunktionswert verschlechtern würde. Gibt es dagegen Nichtbasisvariablen mit positiven reduzierten Kosten, wird im nächsten Simplexschritt eine von ihnen in die Basis aufgenommen und dafür eine andere Variable aus der Basis entfernt. Wenn die neue Variable innerhalb der Nebenbedingungen $Ax=b$ erhöht werden kann, verbessert sich der Zielfunktionswert.

Ein einzelner Simplexschritt[Bearbeiten | Quelltext bearbeiten]

Für den eigentlichen Simplexschritt wählt man nun eine Spalte $s$ der einzufügenden Nichtbasisvariable und eine Zeile $r$ der aus der Basis zu entfernenden Basisvariablen. Seien ${\bar {a}}_{ij}$ die (Matrix-) Elemente des aktuellen Simplextableaus. Dann heißt ${\bar {a}}_{rs}$ das Pivotelement des Simplextableaus. Die Spalte $s$ heißt Pivotspalte, die Zeile $r$ heißt Pivotzeile. Ein Austauschschritt entspricht exakt einem Schritt beim Lösen eines linearen Gleichungssystems, bei dem man die Pivotzeile $r$ nach der Variablen $x_{s}$ auflöst und dann $x_{s}$ in die restlichen Gleichungen einsetzt. Bei einem Austauschschritt berechnet sich das neue Simplextableau folgendermaßen:

Pivotelement:

{\bar {a}}_{rs}:={\frac {1}{{\bar {a}}_{rs}}}\qquad (1)

Pivotzeile für j ungleich s:

{\bar {a}}_{rj}:={\frac {{\bar {a}}_{rj}}{{\bar {a}}_{rs}}}\qquad (2)

{\bar {b}}_{r}:={\frac {{\bar {b}}_{r}}{{\bar {a}}_{rs}}}\qquad (3)

Pivotspalte für i ungleich r:

{\bar {a}}_{is}:=-{\frac {{\bar {a}}_{is}}{{\bar {a}}_{rs}}}\qquad (4a)

{\bar {c}}_{s}:=-{\frac {{\bar {c}}_{s}}{{\bar {a}}_{rs}}}\qquad (4b)

Restliche Elemente der Matrix und reduzierte Kosten:

{\bar {a}}_{ij}:={\bar {a}}_{ij}-{\frac {{\bar {a}}_{is}{\bar {a}}_{rj}}{{\bar {a}}_{rs}}}\qquad (5a)

{\bar {c}}_{j}:={\bar {c}}_{j}-{\frac {{\bar {c}}_{s}{\bar {a}}_{rj}}{{\bar {a}}_{rs}}}\qquad (5b)

Rechte Seite:

{\bar {b}}_{i}:={\bar {b}}_{i}-{\frac {{\bar {b}}_{r}{\bar {a}}_{is}}{{\bar {a}}_{rs}}}\qquad (6)

Diese Rechenschritte entsprechen der Anwendung des Gaußschen Eliminationsverfahrens, um die Pivotspalte s im Tableau in einen Einheitsvektor zu transformieren. Dadurch wird die inverse Matrix $A_{B'}^{-1}$ zur neuen Basis $B'$ nicht komplett neu berechnet, sondern durch Modifikation der alten Basisinversen $A_{B}^{-1}$ konstruiert.

Ein Simplexschritt, der von einer nicht degenerierten Basislösung ausgeht, führt auf jeden Fall zu einer neuen Basislösung und damit auch zu einer neuen Ecke des Polyeders mit besserem Zielfunktionswert. Ist dagegen die Basislösung degeneriert, kann es passieren, dass die neue Basis nach dem Simplexschritt zur selben Basislösung und damit auch zur selben Ecke gehört, so dass der Zielfunktionswert sich nicht ändert. Bei unvorsichtiger Wahl der Pivotelemente kann es zu sogenannten Zyklen kommen, bei der reihum immer wieder dieselben Basen besucht werden, so dass der Algorithmus in eine Endlosschleife läuft. Dies lässt sich aber beispielsweise durch eine geeignete Auswahl der Pivotzeile verhindern. In der Praxis ist eine weitere Methode, mit Zykeln umzugehen, eine absichtliche Perturbation (numerische Störung) der Daten, die nach einigen Iterationen wieder rausgerechnet wird, wenn der Algorithmus die betreffende Ecke verlassen hat.

Für die Wahl des Pivotelements gibt es meist mehrere Möglichkeiten. Die ursprünglich von Dantzig vorgeschlagene Methode wählt eine der Spalten mit dem größten reduzierten Kostenwert und eine beliebige Zeile, bei der nach dem Simplexschritt wieder eine zulässige (insbesondere nichtnegative) Basislösung entsteht. Dazu muss bei gegebener Pivotspalte $s$ eine Pivotzeile gewählt werden, bei der das Minimum

\lambda :=\min {\Bigl \{}\left.{\frac {{\bar {b}}_{i}}{{\bar {a}}_{is}}}\;\right|\;i=1,\ldots ,m,\,{\bar {a}}_{is}>0{\Bigr \}}

angenommen wird. Sind alle Einträge in Spalte $s$ negativ, ist das Optimierungsproblem unbeschränkt, da man Lösungen mit beliebig gutem Zielfunktionswert konstruieren könnte. In diesem Fall kann man aufhören.

Im Normalfall gibt es sowohl mehrere Spalten mit positiven reduzierten Kosten als auch mehrere Zeilen, bei denen das Minimum $\lambda$ angenommen wird, so dass eine Wahlmöglichkeit besteht. Da die Wahl des Pivotelements einen großen Einfluss auf die Rechenzeit haben kann, sind innerhalb der letzten 60 Jahre zahlreiche verbesserte Pivotstrategien gegenüber der Lehrbuchvariante entwickelt worden (siehe unten).

Allgemeine Pivotverfahren[Bearbeiten | Quelltext bearbeiten]

Allgemeine Pivotverfahren durchlaufen Schnittpunkte der Nebenbedingungen, bis sie an einer Ecke mit der Optimallösung ankommen.

siehe Hauptartikel: Pivotverfahren

Im Gegensatz zu Simplexverfahren durchlaufen allgemeine Pivotverfahren beliebige, nicht unbedingt zulässige oder dual-zulässige Basislösungen, also Schnittpunkte der durch Nebenbedingungen definierten Ebenen. Die aufeinanderfolgend besuchten Basislösungen werden dabei (1) sich in nur einer Schnittpunktebene unterscheiden, entweder (2) eine bis dann verletzte Nebenbedingung befriedigen, oder aber (3) einen verbesserten Zielfunktionswert aufweisen.

Theoretisch gesehen lässt sich beweisen, dass sich mit so einem Pivotverfahren immer in einer linear beschränkten Anzahl von Schritten eine Optimallösung erreichen lässt. In der Praxis jedoch lässt sich dieses Ergebnis nur für die durchschnittliche Schrittzahl umsetzen, und es ist derzeit (2011) noch keine Variante gefunden worden, die diese Schranke auch im ungünstigsten Fall einhält.