Pivotverfahren

Pivotverfahren (auch Basisaustauschverfahren) s​ind Algorithmen d​er mathematischen Optimierung, insbesondere d​er linearen Optimierung. Für e​in vorgegebenes System linearer Gleichungen i​n nichtnegativen Variablen (im Wesentlichen dasselbe w​ie ein System linearer Ungleichungen) w​ird nach d​er bestmöglichen v​on vielen Alternativlösungen (einer sogenannten Optimallösung) gesucht u​nd auf dieser Suche d​as Gleichungssystem Schritt für Schritt umgewandelt, o​hne dabei d​ie Lösungsmenge z​u verändern. Wichtige Pivotverfahren s​ind die Simplex-Verfahren u​nd die Criss-Cross-Verfahren.

Pivotverfahren spielen für d​ie Behandlung v​on linearen Ungleichungen e​ine analoge u​nd ähnlich wichtige Rolle w​ie das gaußsche Eliminationsverfahren für d​ie Lösung linearer Gleichungssysteme i​n unbeschränkten Variablen. Hauptanwendungsgebiet d​er Pivotverfahren i​st die lineare Optimierung: s​ie gehören z​u den meistverwendeten Lösungsmethoden i​n der Unternehmensforschung, d​er Wirtschaftswissenschaft, d​em Gütertransport u​nd sie werden a​uch in vielen anderen Gebieten w​ie im Ingenieurbau (Strukturoptimierung), i​n der Statistik (Regressionsanalyse) u​nd in d​er Spieltheorie zunehmend eingesetzt.[1] Aufgaben m​it zehntausenden Variablen u​nd Ungleichungen s​ind an d​er Tagesordnung.[2]

Pivotansatz

Problemstellung

Ein Pivotverfahren g​eht immer v​on einem besonders gearteten linearen Gleichungssystem aus, i​n dem a​lle Variablen, außer vielleicht einer, nichtnegative Werte annehmen sollen. Jedes System linearer Ungleichungen o​der Gleichungen, u​nd auch j​ede lineare Optimierungsaufgabe, lässt s​ich nämlich i​n folgende (englisch dictionary genannte[3]) Buchform bringen:

${\displaystyle {\begin{matrix}z&=&f&+&~~~~~d_{1}\,x_{1}&+&\cdots &+&~~~~~d_{n}\,x_{n}\\[3pt]x_{n+1}&=&b_{n+1}&+&G_{n+1,1}\,x_{1}&+&\cdots &+&G_{n+1,n}\,x_{n}\\\vdots &&\vdots &&\vdots &&&&\vdots \\x_{n+m}&=&b_{n+m}&+&G_{n+m,1}\,x_{1}&+&\cdots &+&G_{n+m,n}\,x_{n}\end{matrix}}}$

${\displaystyle {\begin{matrix}\max ~z\,,\quad x_{1}\geq 0,\;\ldots ,\;x_{n+m}\geq 0\end{matrix}}}$

Hier sind ${\displaystyle f,\;d_{j},\;b_{i},\;G_{i,j}}$ reelle (in der Praxis meist rationale) Zahlen. Die obige Notation soll aussagen, dass eine Lösung in den Unbekannten ${\displaystyle x_{1},\;\ldots ,\;x_{n+m},\;z}$ gesucht wird, welche die entsprechenden Gleichungen und Ungleichungen erfüllt und dabei die sogenannte Zielvariable ${\displaystyle z}$ so groß wie möglich wählt.

Bemerkung

Bei der Verwandlung der Aufgabe in die obige Form werden die Ungleichungen des Systems keinesfalls weniger: sie bleiben in mindestens gleicher Anzahl weiter vorhanden und treten nun als nichtnegative Variablen auf. Eine übliche lineare Ungleichung wie beispielsweise

${\displaystyle 3x_{1}~+~4x_{2}~-~x_{3}~\leq ~5x_{1}~+~8}$

wird umgeformt in

${\displaystyle x_{4}~=~8~+~2x_{1}~-~4x_{2}~+~x_{3}}$

mit ${\displaystyle x_{4}\geq 0}$.

Mit Hilfe der Indexmengen

${\displaystyle D=\{1,\ldots ,n\},\quad B=\{n+1,\ldots ,n+m\}}$

lässt s​ich diese Aufgabe a​uch wie f​olgt in kompakter Form ausdrücken:

${\displaystyle {\begin{matrix}&&z&=&f&+&\sum _{j\in D}\,d_{j}\,x_{j}\\[6pt]\forall ~i\in B&&x_{i}&=&b_{i}&+&\sum _{j\in D}\,G_{i,j}\,x_{j}\end{matrix}}}$

${\displaystyle {\begin{matrix}\max ~z\,,\quad \forall ~k\in D\cup B\quad x_{k}\geq 0\end{matrix}}}$

In j​edem Schritt e​ines Pivotverfahrens i​st wie o​ben eine Teilmenge d​er Variablen a​ls unabhängig hervorgehoben, während d​ie restlichen Variablen, Basisvariablen genannt, a​ls linear-affine Funktionen d​er unabhängigen Variablen ausgedrückt werden. In aufeinanderfolgenden Schritten wechselt i​mmer eine d​er Variablen v​on unabhängig a​uf Basisvariable u​nd eine zweite i​n die umgekehrte Richtung; solche Variablenpaare werden Pivots genannt.

Optimumbedingungen

Falls i​m oben aufgestellten linearen Gleichungssystem d​ie beiden folgenden Optimumbedingungen erfüllt sind,

• ${\displaystyle b_{i}\geq 0}$   für alle  ${\displaystyle i\in B}$    (Zulässigkeit)   und
• ${\displaystyle d_{j}\leq 0}$   für alle  ${\displaystyle j\in D}$    (Zielbeschränkung),

dann kann man eine Lösung für die obige Aufgabe erhalten, indem man die unabhängigen Variablen auf die Werte ${\displaystyle x_{1}=0,\ldots ,x_{n}=0}$ setzt. Zum einen sind die Werte der freigelegten Variablen ${\displaystyle x_{n+1}=b_{n+1},\ldots ,x_{n+m}=b_{n+m}}$ dann nichtnegativ, wie gefordert. Zum anderen dürfen sonstige mögliche Lösungen nur unabhängige Variable mit ebenfalls nichtnegativen Werten enthalten, so dass für jede dieser Lösungen die Ungleichung ${\displaystyle z\leq f}$ gilt.

Im folgenden Beispielsystem,

${\displaystyle {\begin{matrix}z&=&~~~0&-~3x_{1}&+~~\mathbf {x_{2}} \\[2pt]x_{3}&=&~~~3&-~~x_{1}&-~~x_{2}\\[2pt]x_{4}&=&~~~8&+~2x_{1}&-~4x_{2}\\[2pt]x_{5}&=&-~\mathbf {1} &+~3x_{1}&+~~x_{2}\,,\end{matrix}}}$

werden die Optimumbedingungen an zwei Stellen verletzt, da ${\displaystyle b_{5}=-1<0}$ und ${\displaystyle d_{2}=+1>0}$ ist. Zum ersten würde die Versuchslösung ${\displaystyle x_{1}=x_{2}=0}$ den negativen Wert ${\displaystyle x_{5}=-1}$ enthalten, und zum zweiten könnte dessen Zielvariablenwert ${\displaystyle z=-3x_{1}+x_{2}}$ bei Lösungen mit ${\displaystyle x_{2}>0}$ unter Umständen erhöht werden.

Austausch der Basisvariablen

Falls die Optimumbedingungen nicht erfüllt sind, was in der Regel der Fall sein wird, lässt sich das obige lineare Gleichungssystem aber auch andersartig ausdrücken, indem man an Stelle von ${\displaystyle \{x_{n+1},\ldots ,x_{n+m}\}}$ eine andere, gleich große Teilmenge der ${\displaystyle n+m}$ Unbekannten auswählt und diese freilegt. Es sei   ${\displaystyle \pi (1),\ldots ,\pi (n+m)}$   eine Umstellung der Unbekannten. Anhand folgender Aufteilung der Variablen,

${\displaystyle D(\pi )=\{\pi (1),\ldots ,\pi (n)\},\quad B(\pi )=\{\pi (n+1),\ldots ,\pi (n+m)\},}$

in neue unabhängige Variablen ${\displaystyle x_{j}}$ mit ${\displaystyle j\in D(\pi )}$ und neue Basisvariablen ${\displaystyle x_{i}}$ mit ${\displaystyle i\in B(\pi )}$, wird das Gleichungssystem nun umgewandelt zu

${\displaystyle {\begin{matrix}&&z&=&f^{\pi }&+&\sum _{j\in D(\pi )}\,d_{j}^{\pi }\,x_{j}\\[6pt]\forall ~i\in B(\pi )&&x_{i}&=&b_{i}^{\pi }&+&\sum _{j\in D(\pi )}\,G_{i,j}^{\pi }\,x_{j}\end{matrix}}}$

${\displaystyle {\begin{matrix}\max ~z\,,\quad \forall ~k\in D\cup B\quad x_{k}\geq 0\,,\end{matrix}}}$

wobei zu beachten ist, dass Einträge wie ${\displaystyle G_{i,j}^{\pi }}$ nur für Indexpaare mit ${\displaystyle i\in B(\pi )}$ und ${\displaystyle j\in D(\pi )}$ definiert sind. Die Einträge des so umgewandelten Gleichungssystems lassen sich nun erneut auf die Optimumbedingungen überprüfen,

• ${\displaystyle b_{i}^{\pi }\geq 0}$   für alle   ${\displaystyle i\in B(\pi )}$    (Zulässigkeit)   und
• ${\displaystyle d_{j}^{\pi }\leq 0}$   für alle   ${\displaystyle j\in D(\pi )}$    (Zielbeschränkung),

was wiederum u​nter Umständen z​u einer Lösung d​er Aufgabe führt.

Ein Standardergebnis d​er linearen Optimierung s​agt aus[3][1], d​ass für j​ede lösbare Aufgabe e​in Satz Basisvariablen existiert, d​er zu e​iner Lösung führt. Bei erfüllten Optimumbedingungen bilden d​ie Basisvariablen e​ine sogenannte Optimalbasis d​es Systems.

Pivots und Pivotelemente

Jedes nichtverschwindende ${\displaystyle G_{r,s}^{\pi }\neq 0}$ des obigen Gleichungssystems, dem Pivotsystem, nennt sich Pivotelement und erlaubt es, die unabhängige Variable ${\displaystyle x_{s}}$ an Stelle der Basisvariablen ${\displaystyle x_{r}}$ freizulegen, um so weiter nach einer Lösung zu suchen. Das ist die Vorgehensweise eines allgemeinen Pivotverfahrens, wobei aber nicht irgendwelche Pivotelemente gewählt werden, sondern nur erlaubte (admissible) Pivots ${\displaystyle (x_{r},\,x_{s})}$, die Folgendes erfüllen müssen:

• Entweder gilt gleichzeitig ${\displaystyle b_{r}^{\pi }<0}$ und ${\displaystyle G_{r,s}^{\pi }>0}$    (Zulässigkeitspivot),
• oder es gilt gleichzeitig ${\displaystyle d_{s}^{\pi }>0}$ und ${\displaystyle G_{r,s}^{\pi }<0}$    (Zielfortschrittspivot).

Im obigen Beispielsystem,

${\displaystyle {\begin{matrix}z&=&~~~0&-~3x_{1}&+~~~\mathbf {x_{2}} \\[2pt]x_{3}&=&~~~3&-~~x_{1}&-~~~{\underline {\mathbf {x_{2}} }}\\[2pt]x_{4}&=&~~~8&+~2x_{1}&-~{\underline {\mathbf {4x_{2}} }}\\[2pt]x_{5}&=&-~\mathbf {1} &+~{\underline {\mathbf {3x_{1}} }}&+~~~{\underline {\mathbf {x_{2}} }}\,,\end{matrix}}}$

sind wegen der Optimalitätsverletzung ${\displaystyle b_{5}<0}$ Pivotelement ${\displaystyle G_{5,1}=+3>0}$ mit Pivot ${\displaystyle (x_{5},\,x_{1}),}$ und Pivotelement ${\displaystyle G_{5,2}=+1>0}$ mit Pivot ${\displaystyle (x_{5},\,x_{2})}$ erlaubt. Wegen der Optimalitätsverletzung ${\displaystyle d_{2}>0}$ sind aber ebenfalls Pivotelement ${\displaystyle G_{3,2}=-1<0}$ mit Pivot ${\displaystyle (x_{3},\,x_{2})}$, und Pivotelement ${\displaystyle G_{4,2}=-4<0}$ mit Pivot ${\displaystyle (x_{4},\,x_{2})}$ erlaubt.

Die Beschränkung auf erlaubte Pivots verhindert, dass derselbe Pivot zweimal hintereinander ausgewählt wird. Die Regeln, nach denen in jedem Schritt eines dieser erlaubten Pivotelemente ausgewählt wird, hängen vom jeweiligen Verfahren ab; ein Mindestanspruch ist dabei natürlich, dass das Verfahren nach endlich vielen Schritten anhält, was bei ungeeigneter Auswahl von erlaubten Pivots nicht der Fall ist. Fukuda & Terlaky haben 1999 bewiesen, dass für jede lösbare Aufgabe und für jede Ausgangsbasis eine Folge von maximal ${\displaystyle n+m}$ erlaubten Pivots existiert, die zu einer Optimalbasis führt.[4] Leider liefert ihr Beweis keine Vorgehensweise, um diese Pivots in jedem Optimierungsschritt auch zu finden.

Wie aus der Definition zu ersehen ist, haben Optimalbasen keine erlaubten Pivots, das Verfahren kann in so einem Fall gar nicht fortgeführt werden. Anderseits kann anhand von Argumenten wie im obigen Abschnitt leicht gezeigt werden, dass eine nichtoptimale Basis ohne erlaubte Pivots immer zu einer Aufgabe gehört, die gar keine Lösung hat; entweder, weil das System der Gleichungen und Ungleichungen überhaupt keine Lösung hat (unzulässige Aufgabe), oder, weil sich Lösungen mit beliebig großem ${\displaystyle z}$ finden lassen (unbeschränkte Aufgabe).

Beispiele

Eine direkte Umsetzung

Um Rundungsfehler z​u vermeiden, arbeiten w​ir im Folgenden m​it Bruchzahlen u​nd wählen e​inen gemeinsamen Nenner für sämtliche Einträge. Um i​n jedem Schritt e​inen gemeinsamen Nenner für d​as Gesamtsystem z​u finden, müssen w​ir die Einträge nicht zusätzlich untersuchen. Falls d​as Startsystem ganzzahlig i​st (was s​ich normalerweise d​urch Erweiterung erreichen lässt), g​ilt die Regel:

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

Wenn d​ie Einträge d​es Folgesystems m​it diesem gemeinsamen Nenner multipliziert werden, erhält m​an ganzzahlige Werte. Bei d​er Aufstellung d​es Folgesystems veraltet d​er gemeinsame Nenner d​es Vorgängersystems, weshalb sämtliche Einträge d​es Folgesystems ungeprüft d​urch diesen veralteten Nenner gekürzt werden können.

Eine Tabelle m​it den Einträgen e​ines Pivotsystems w​ird oftmals Tableau genannt. Das folgende Schema z​eigt an, w​ie sich d​ie Einträge d​er Pivotsysteme v​on einem Schritt a​uf den nächsten verändern:

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

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

${\displaystyle {\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}}}$

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

Die Bilder z​u den Schritten i​n den folgenden Beispielen zeigen a​lle dasselbe Gleichungssystem i​n verschiedenen orthogonalen Koordinaten; d​abei gilt:

• Die grün umrandete Fläche ist der zulässige Bereich, in dem alle Variablen nichtnegative Werte haben.
• Koordinatenachsen entsprechen den Gleichungen ${\displaystyle x_{k}=0}$ von unabhängigen Variablen; sonstige Geraden beschreiben freigelegte Variablen.
• Schnittpunkte erlaubter Pivots sind rot markiert; der schwarzumrandete Schnittpunkt zeigt den ausgewählten Pivot.
• Die gelbe Fläche wird im nächsten Schritt zum nichtnegativen Quadranten.

Eine erfolgssichere Pivotauswahlregel

Wir wählen vorerst ein Beispiel ohne Zielvariable, das heißt, mit ${\displaystyle z=0+0\,x_{1}+0\,x_{2}}$. In so einem Fall wird keine der Variablen maximiert; es werden nur beliebige (nichtnegative) Werte für die Unbekannten ${\displaystyle x_{1}\geq 0,\ldots ,x_{n+m}\geq 0}$ gesucht, die ein vorgegebenes Gleichungssystem erfüllen. In jedem Schritt wollen wir dann den erlaubten Pivot ${\displaystyle (x_{r},\,x_{s})}$ nach folgender Regel wählen:

1. Wähle ${\displaystyle r=\min\{i\in B(\pi )~|~b_{i}^{\pi }<0\}}$,
2. danach wähle ${\displaystyle s=\min\{j\in D(\pi )~|~G_{r,j}^{\pi }>0\}}$.

Diese (nicht besonders effiziente) Auswahlregel fällt wegen ${\displaystyle z=0}$ mit der weiter unten angegebenen Kleinster-Index-Pivotauswahl zusammen; es lässt sich beweisen, dass diese Auswahl bei jeder lösbaren Aufgabe mit ${\displaystyle z=0}$ zu einer Optimalbasis führt.[5]

Wir suchen nun Werte für die Unbekannten ${\displaystyle x_{1}\geq 0,\ldots ,x_{5}\geq 0}$, die das Gleichungssystem

${\displaystyle {\begin{matrix}x_{3}&=&(&-~\mathbf {2} &-~7x_{1}&+~{\underline {\mathbf {2x_{2}} }}&)~/~1\\[2pt]x_{4}&=&(&-~4&-~5x_{1}&+~2x_{2}&)~/~1\\[2pt]x_{5}&=&(&~~~9&+~2x_{1}&-~3x_{2}&)~/~1\end{matrix}}}$

erfüllen. Die erlaubten Pivots im obigen Gleichungssystem sind ${\displaystyle (x_{3},\,x_{2})}$ und ${\displaystyle (x_{4},\,x_{2})}$; aufgrund der obigen Auswahlregel legen wir die unabhängige Variable ${\displaystyle x_{2}}$ an Stelle der Basisvariablen ${\displaystyle x_{3}}$ frei:

Basis 0 zu Basis 1   (skalierbar und von Firefox animiert bei 2-mal anklicken und gedrückt halten)

Wir erhalten n​un das folgende, umgewandelte Gleichungssystem:

${\displaystyle {\begin{matrix}x_{2}&=&(&~~~2&+~~7x_{1}&+~~~~x_{3}&)~/~2\\[2pt]x_{4}&=&(&-~\mathbf {4} &+~~{\underline {\mathbf {4x_{1}} }}&+~~~2x_{3}&)~/~2\\[2pt]x_{5}&=&(&~~12&-~17x_{1}&-~~~3x_{3}&)~/~2\end{matrix}}}$

Im neuen System sind die erlaubten Pivots ${\displaystyle (x_{4},\,x_{1})}$ und ${\displaystyle (x_{4},\,x_{3})}$; dieses Mal legen wir legen wir ${\displaystyle x_{1}}$ an Stelle von ${\displaystyle x_{4}}$ frei:

Basis 1 zu Basis 2

Wir erhalten n​un das folgende System:

${\displaystyle {\begin{matrix}x_{2}&=&(&~~18&+~~7x_{4}&-~~5x_{3}&)~/~4\\[2pt]x_{1}&=&(&~~~4&+~~2x_{4}&-~~2x_{3}&)~/~4\\[2pt]x_{5}&=&(&-\mathbf {10} &-~17x_{4}&+~{\underline {\mathbf {11x_{3}} }}&)~/~4\end{matrix}}}$

Der einzige erlaubte Pivot hier ist ${\displaystyle (x_{5},\,x_{3})}$; deshalb können wir nur ${\displaystyle x_{3}}$ an Stelle von ${\displaystyle x_{5}}$ freilegen:

Basis 2 zu Basis 3

Nun erhalten wir

${\displaystyle {\begin{matrix}x_{2}&=&(&~~37&-~~2x_{4}&-~~~5x_{5}&)~/~11\\[2pt]x_{1}&=&(&~~~6&-~~3x_{4}&-~~~2x_{5}&)~/~11\\[2pt]x_{3}&=&(&~~10&+~17x_{4}&+~~~4x_{5}&)~/~11\end{matrix}}}$

Dieses System erfüllt d​ie Optimalitätsbedingungen u​nd hat dementsprechend a​uch keine erlaubten Pivots. Indem w​ir sämtliche unabhängige Variablen a​uf Null setzen, erhalten w​ir die folgende Lösung:

${\displaystyle x_{1}=6/11=0.55,x_{2}=37/11=3.36,x_{3}=10/11=0.91,x_{4}=0,x_{5}=0\,.}$

Kreislaufanfällige Pivotauswahlregeln

Es folgt nun ein Beispiel einer ungeeigneten Pivotauswahl; bei ungeeigneter Pivotwahl kann ein Pivotverfahren nämlich in einen unendlichen Kreislauf (eine Endlosschleife) geraten. Es sei wieder ${\displaystyle \,z=0+0\,x_{1}+0\,x_{2}\,.}$ Wie bei folgender Regel vorgeschlagen, könnten wir beispielsweise der Versuchung erliegen, die Pivotzeile nur unter den "meistverletzten" Nebenbedingungen auszuwählen, und dabei "meistverletzt" als diejenigen mit den am weitesten negativen Konstanten verstehen:

1. Wähle ${\displaystyle r=\min {\big \{}i\in B(\pi )~|~~b_{i}^{\pi }\!=\!\min\{b_{k}^{\pi }\,|\,k\in B(\pi ),~b_{k}^{\pi }\!<\!0\}~{\big \}}}$,
2. danach wähle ${\displaystyle s=\min\{j\in D(\pi )~|~G_{r,j}^{\pi }>0\}}$.

Um z​u zeigen, d​ass so e​twas falsch g​ehen kann, starten w​ir mit d​em System:

${\displaystyle {\begin{matrix}x_{3}&=&(&-~\mathbf {2} &+~~{\underline {\mathbf {x_{1}} }}&+~~x_{2}&)~/~2\\[2pt]x_{4}&=&(&~~~6&-~7x_{1}&-~3x_{2}&)~/~2\\[2pt]x_{5}&=&(&~~~0&-~3x_{1}&-~~x_{2}&)~/~2\\[2pt]x_{6}&=&(&~~~4&+~7x_{1}&+~~x_{2}&)~/~2\end{matrix}}}$

Wir wählen hier ${\displaystyle \,x_{3}\,}$ und legen an Stelle dessen ${\displaystyle \,x_{1}\,}$ frei. Dadurch erhalten wir das System:

${\displaystyle {\begin{matrix}x_{1}&=&(&~~~2&+~2x_{3}&-~~x_{2}&)~/~1\\[2pt]x_{4}&=&(&-~\mathbf {4} &-~7x_{3}&+~{\underline {\mathbf {2x_{2}} }}&)~/~1\\[2pt]x_{5}&=&(&-~~3&-~3x_{3}&+~~x_{2}&)~/~1\\[2pt]x_{6}&=&(&~~~9&+~7x_{3}&-~3x_{2}&)~/~1\end{matrix}}}$

Wir wählen Basisvariable ${\displaystyle \,x_{4}\,}$, legen an deren Stelle ${\displaystyle \,x_{2}\,}$ frei, und erhalten:

${\displaystyle {\begin{matrix}x_{1}&=&(&~~~0&-~3x_{3}&-~~x_{4}&)~/~2\\[2pt]x_{2}&=&(&~~~4&+~7x_{3}&+~~x_{4}&)~/~2\\[2pt]x_{5}&=&(&-~\mathbf {2} &+~~{\underline {\mathbf {x_{3}} }}&+~~x_{4}&)~/~2\\[2pt]x_{6}&=&(&~~~6&-~7x_{3}&-~3x_{4}&)~/~2\end{matrix}}}$

Die Einträge in diesem Gleichungssystem sind dieselben wie im Startsystem, weshalb sich bei ähnlicher Pivotfolge auch die Einträge der folgenden Systeme alle zwei Schritte wiederholen werden. Nach Auswahl der Basisvariablen ${\displaystyle \,x_{5}\,}$ um an deren Stelle ${\displaystyle \,x_{3}\,}$ freizulegen erhalten wir:

${\displaystyle {\begin{matrix}x_{1}&=&(&-~~3&-~3x_{5}&+~~x_{4}&)~/~1\\[2pt]x_{2}&=&(&~~~9&+~7x_{5}&-~3x_{4}&)~/~1\\[2pt]x_{3}&=&(&~~~2&+~2x_{5}&-~~x_{4}&)~/~1\\[2pt]x_{6}&=&(&-~\mathbf {4} &-~7x_{5}&+~{\underline {\mathbf {2x_{4}} }}&)~/~1\end{matrix}}}$

Nach der kreislauffreien Regel im vorherigen Beispiel müssten wir nun ${\displaystyle \,x_{1}\,}$ wählen um ${\displaystyle \,x_{4}\,}$ freizulegen. Anstelle dessen folgen wir der abgewandelten Regel und wählen dafür die Basisvariable ${\displaystyle \,x_{6}\,}$, was zu folgendem System führt:

${\displaystyle {\begin{matrix}x_{1}&=&(&-~\mathbf {2} &+~~{\underline {\mathbf {x_{5}} }}&+~~x_{6}&)~/~2\\[2pt]x_{2}&=&(&~~~6&-~7x_{5}&-~3x_{6}&)~/~2\\[2pt]x_{3}&=&(&~~~0&-~3x_{5}&-~~x_{6}&)~/~2\\[2pt]x_{4}&=&(&~~~4&+~7x_{5}&+~~x_{6}&)~/~2\end{matrix}}}$

Dieses Gleichungssystem h​at wieder dieselben Einträge w​ie das Startsystem; w​eil diese a​ber immer n​och anderen Variablen zugeordnet sind, i​st der Kreislauf n​ach diesen 4 Schritten n​och nicht beendet. Dennoch i​st leicht z​u überprüfen, d​ass der Algorithmus i​n insgesamt 6 Schritten z​um Startsystem i​n vertauschter Reihenfolge u​nd in 12 Schritten z​um genauen Startsystem zurückkehrt. Das Gesamtsystem v​on Gleichungen u​nd Ungleichungen h​at in Wirklichkeit g​ar keine Lösung, d​och kann d​as Pivotverfahren d​as mit d​er oberen Pivotwahl n​icht herausfinden.

Die Reihenfolge, i​n der Variable u​nd Gleichungen e​ines Pivotsystems aufgelistet werden, i​st grundsätzlich willkürlich. Dennoch wurden d​ie ersten Pivotauswahl-Strategien, d​ie Variablen u​nd Gleichungen unabhängig v​on deren Darstellung i​m Pivotsystem behandeln (und d​azu noch leicht umsetzbar waren), e​rst 1977 v​on Bland [6] vorgestellt.

In der Anfangszeit der Pivotverfahren (1950–1970), als noch nicht streng zwischen Algorithmen und Datenstrukturen unterschieden wurde, hat man Pivotauswahl-Strategien eher anhand von Datenstrukturen (sogenannten Tableaus) beschrieben, und bei dieser Art Strategien konnte die Endlichkeit des Verfahrens ohne Zusatzberechnungen meist nicht gewährleistet werden. Wenn zum Beispiel die betrachtete Pivotauswahl-Regel im Sinne der ursprünglich verwendeten Dantzig-Auswahl verändert wird, bei der einfach die erste der in Frage kommenden Zeilen und Spalten ausgewählt wird, dann ist auch damit nicht geholfen. Die Auswahlregel wäre dann

1. Wähle das kleinste  ${\displaystyle k\!\in \!\{n+1,\ldots ,n+m\}}$   mit   ${\displaystyle b_{\pi (k)}^{\pi }=\min _{i}^{\,}\{b_{\pi (i)}^{\pi }\}<0}$,
2. Danach wähle das kleinste  ${\displaystyle l\!\in \!\{1,\ldots ,n\}}$   mit   ${\displaystyle G_{\pi (k),\pi (l)}^{\pi }>0\,}$,
3. Der Pivot sei ${\displaystyle (x_{\pi (k)},\,x_{\pi (l)})}$,

doch führt d​iese beim obigen Beispiel i​n genau dieselbe endlose Schleife.

Dualität

Duale Aufgabe

Jeder linearen Optimierungsaufgabe, welche i​n diesem Zusammenhang a​uch Primalaufgabe genannt wird, lässt s​ich von d​er obigen Buchform abhängig e​ine zweite Optimierungsaufgabe zuordnen; d​ie Koeffizientenmatrix dieser sogenannten dualen Aufgabe i​st die negative Transponierte d​er Koeffizientenmatrix d​er ursprünglichen Aufgabe:

${\displaystyle {\begin{matrix}w&=&-\;f&-&b_{1}\,y_{n+1}&-&\cdots &-&b_{m}\,y_{n+m}\\[3pt]y_{1}&=&-\;d_{1}&-&G_{n+1,1}\,y_{n+1}&-&\cdots &-&G_{n+m,1}\,y_{n+m}\\\vdots &&\vdots &&\vdots &&&&\vdots \\y_{n}&=&-\;d_{n}&-&G_{n+1,n}\,y_{n+1}&-&\cdots &-&G_{n+m,n}\,y_{n+m}\end{matrix}}}$

${\displaystyle {\begin{matrix}\max ~w\,,\quad y_{1}\geq 0,\;\ldots ,\;y_{m+n}\geq 0\end{matrix}}}$

In gedrungener Form w​ird das zu:

${\displaystyle {\begin{matrix}&&w&=&(-f)&+&\sum _{i\in B}\,(-b_{i})\,y_{i}\\[6pt]\forall ~j\in D&&y_{j}&=&(-d_{j})&+&\sum _{i\in B}\,(-G_{i,j})\,y_{i}\end{matrix}}}$

${\displaystyle {\begin{matrix}\max ~w\,,\quad \forall ~k\in D\cup B\quad y_{k}\geq 0\end{matrix}}}$

(Vorsicht:   Bei der Herleitung über diese Formulierung dürfen ${\displaystyle \max \,z,\;\max \,w}$ nicht durch ${\displaystyle \min \,z,\;\min \,w}$ ersetzt werden!   Oftmals wird die duale Aufgabe auch mit der Zielfunktion ${\displaystyle \min \,(-w)}$ anstelle von ${\displaystyle \max \,w}$ definiert, was zwar machbar, aber auch unübersichtlicher ist.)

Wie gleich gezeigt wird, i​st das Maximum d​er Dualaufgabe (soweit vorhanden) g​enau das negative Maximum d​er Primalaufgabe.

Schrittweise Umwandlung

Die o​bige Beziehung d​er Koeffizienten zwischen Primalaufgabe u​nd Dualaufgabe g​ilt nicht e​twa nur für d​ie Ausgangsbasis, sondern bleibt erhalten, solange d​ie Basisvariablen n​ach denselben Pivots umgewandelt werden. Es gilt

${\displaystyle {\begin{matrix}&&w&=&(-f^{\pi })&+&\sum _{i\in B(\pi )}\,(-b_{i}^{\pi })\,y_{i}\\[6pt]\forall ~j\in D(\pi )&&y_{j}&=&(-d_{j}^{\pi })&+&\sum _{i\in B(\pi )}\,(-G_{i,j}^{\pi })\,y_{i}\end{matrix}}}$

${\displaystyle {\begin{matrix}\max ~w\,,\quad \forall ~k\in D\cup B\quad y_{k}\geq 0\,.\end{matrix}}}$

Diese Dualitätsbeziehung lässt s​ich am leichtesten a​n einem Pivotsystem betrachten, d​as ausschließlich z​wei unabhängige Unbekannte u​nd zwei freigelegte Unbekannte enthält. Wir erhalten dasselbe System, w​enn wir zuerst z​wei der Unbekannten austauschen u​nd danach d​ie duale Aufgabe herleiten, o​der wenn w​ir diese Schritte i​n umgekehrter Reihenfolge tun; d​as folgende kommutative Diagramm stellt diesen Zusammenhang dar:

${\displaystyle {\begin{matrix}\delta \,x_{i}&\!=\!&(~~\alpha )&\!\!\!x_{j}&\!+\!&(~~\sigma )&\!\!\!x_{s}\\[6pt]\delta \,x_{r}&\!=\!&(~~\zeta )&\!\!\!x_{j}&\!+\!&(~~p)&\!\!\!x_{s}\end{matrix}}}$	${\displaystyle {x_{r}\leftrightarrow x_{s}}}$	${\displaystyle {\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}}}$
${\displaystyle -\,[\cdots ]^{\,T}}$		${\displaystyle -\,[\cdots ]^{\,T}}$
${\displaystyle {\begin{matrix}\delta \,y_{j}&\!=\!&(-\alpha )&\!\!\!y_{i}&\!+\!&(-\zeta )&\!\!\!y_{r}\\[6pt]\delta \,y_{s}&\!=\!&(-\sigma )&\!\!\!y_{i}&\!+\!&(-p)&\!\!\!y_{r}\\\end{matrix}}}$	${\displaystyle {y_{s}\leftrightarrow y_{r}}}$	${\displaystyle {\begin{matrix}p\,y_{j}&\!=\!&(\textstyle {\frac {\zeta \sigma \,-\,\alpha p}{\delta }})&\!\!\!y_{i}&\!+\!\!&(~~\zeta )&\!\!\!y_{s}\\[6pt]p\,y_{r}&\!=\!&(~-\sigma ~)&\!\!\!y_{i}&\!+\!\!&(-\delta )&\!\!\!y_{s}\\\end{matrix}}}$

Aus d​er Dualbeziehung folgt, d​ass ein Optimalsystem für d​ie Primalaufgabe a​uch einen Optimalsystem für d​ie duale Aufgabe liefert.

Zur Aufgabe im ersten Rechenbeispiel gehört folgende duale Aufgabe (die Nullen stammen von ${\displaystyle z=0+0x_{1}+0x_{2}\,}$):

${\displaystyle {\begin{matrix}~w~&=&(&0&+~~2y_{3}&+~~4y_{4}&-~~9y_{5}&)~/~1\\[2pt]y_{1}&=&(&0&+~~7y_{3}&+~~5y_{4}&-~~2y_{5}&)~/~1\\[2pt]y_{2}&=&(&0&-~~2y_{3}&-~~2y_{4}&+~~3y_{5}&)~/~1\end{matrix}}}$

${\displaystyle {\begin{matrix}\max ~w,\quad y_{1}\geq 0,\ y_{2}\geq 0,\ y_{3}\geq 0,\ y_{4}\geq 0,\ y_{5}\geq 0\end{matrix}}}$

Der o​bige Algorithmus führt d​ann zum Optimalsystem

${\displaystyle {\begin{matrix}~w~&=&(&0&-~37y_{2}&-~~6y_{1}&-~10y_{3}&)~/~11\\[2pt]y_{4}&=&(&0&+~~2y_{2}&+~~3y_{1}&-~17y_{3}&)~/~11\\[2pt]y_{5}&=&(&0&+~~5y_{2}&+~~2y_{1}&-~~4y_{3}&)~/~11\end{matrix}}}$

und die optimale Lösung dazu ist natürlich ${\displaystyle x_{k}=0}$ für alle ${\displaystyle k\in D\cup B}$.   Die Primalaufgabe hatte eine implizite Zielfunktion ${\displaystyle z=0}$; sämtliche Optimallösungen der primalen und auch der dualen Aufgabe hätten deshalb, soweit vorhanden, einen Zielwert ${\displaystyle w=-z=0}$. Das ist derselbe Wert, den auch schon die Anfangslösung der dualen Aufgabe hatte, doch ist die Existenz einer Optimallösung aus dem ersten Gleichungssystem allein nicht ersichtlich: es hätte grundsätzlich auch Lösungen mit unendlich großem ${\displaystyle w}$ und somit gar keine Optimallösung geben können.

Lösungspaare

Eine theoretisch bedeutsame Folge der Dualitätstheorie ist: Wir brauchen nicht unbedingt einen Maximierungs-Algorithmus, um lineare Optimierungsprobleme zu lösen; es genügt dazu jeder Algorithmus, der Systeme linearer Ungleichungen löst. Aus der Dualitätsbeziehung folgt nämlich, dass jede Optimalbasis der ursprünglichen Aufgabe auch unmittelbar eine Optimalbasis für die duale Aufgabe liefert; der optimale Wert der Zielvariable ${\displaystyle w}$ ist dann das Negative des Optimalwerts von ${\displaystyle z.}$. Für zulässige Lösungspaare der beiden Aufgaben gilt demzufolge

${\displaystyle z+w~\leq ~(\max z)\!+\!(\max w)~=~(\max z)\!+\!(-\max z)~=~0\,,}$

und für optimale Lösungspaare gilt

${\displaystyle (\max z)\!+\!(\max w)~=~(\max z)\!+\!(-\max z)~=~0\,.}$

Daraus folgt, d​ass die optimalen Lösungen beider Aufgaben g​enau die Lösungen d​er obigen Gleichungssysteme m​it folgenden Ungleichungen sind:

${\displaystyle z\,+\,w\,\geq \,0,\qquad \forall ~k\in D\cup B\qquad x_{k}\geq 0,\quad y_{k}\geq 0.}$

Ausgeschrieben i​st das

${\displaystyle {\begin{matrix}\sum _{j\in D}\,d_{j}\,x_{j}~~+~~\sum _{i\in B}\,(-b_{i})\,y_{i}~~\geq ~~0\\[6pt]\forall ~j\in D\quad y_{j}~=~(-d_{j})~+~\sum _{i\in B}\,(-G_{i,j})\,y_{i}\\[6pt]\forall ~i\in B\quad x_{i}~=~b_{i}~+~\sum _{j\in D}\,G_{i,j}\,x_{j}\\[6pt]\forall ~k\in D\cup B\qquad x_{k}\geq 0,\quad y_{k}\geq 0\end{matrix}}}$

In d​er Praxis i​st so e​in Vorgehen freilich n​ur dann konkurrenzfähig, w​enn die gemeinsame Datenstruktur beider Aufgaben a​uch ausgenützt wird.

Spezielle Pivotverfahren

Die einfachsten a​ller Pivotverfahren gehören z​u den Criss-Cross-Verfahren[5], d​ie in d​en 80er Jahren für Aufgabenstellungen i​m Kontext orientierter Matroide entwickelt wurden. Die wesentlich komplexeren Simplexverfahren[3][1] wurden a​ber bereits 1947 v​on George Dantzig für d​ie Lösung linearer Optimierungsprobleme veröffentlicht u​nd haben danach d​ank ihrer weiten Verbreitung d​ie Suche n​ach Criss-Cross-Verfahren maßgeblich motiviert. Weitere Pivotverfahren wurden für d​as lineare Komplementaritätsproblem m​it suffizienten Matrizen (einschließlich quadratischer Programmierung) u​nd für linear-fraktionale Optimierungsprobleme entwickelt.

Bei d​er Ausarbeitung verschiedener Pivotverfahren g​eht es i​n der Hauptsache darum, d​ie Anzahl d​er Pivotschritte u​nd damit a​uch die Laufzeit d​es Verfahrens gering z​u halten. Während d​ie derzeit bekannten Simplexverfahren a​lle eine überpolynomial beschränkte Laufzeit beanspruchen – das i​st eine Laufzeit, d​ie sich n​icht durch e​in Polynom i​n der Datenspeichergröße beschränken lässt – s​ind Laufzeitschranken für d​ie Criss-Cross-Verfahren e​in (bis 2010) n​och offenes Forschungsthema.[7] Zusammenfassend lässt s​ich darüber sagen, d​ass Criss-Cross-Verfahren m​ehr Freiheitsgrade aufweisen a​ls Simplexverfahren, u​nd dass e​in Criss-Cross-Verfahren g​enau aus diesem Grund b​ei einer g​uten Pivotauswahl schneller[4] u​nd bei e​iner schlechten Pivotauswahl langsamer[8] a​ls Simplexverfahren s​ein kann.

Primale Simplexverfahren

→ Hauptartikel: Simplex-Verfahren

Primale Simplexverfahren (meist nur Simplexverfahren genannt) gehen von einer sogenannten zulässigen Basis mit ${\displaystyle b_{i}^{\pi }\geq 0}$ für alle ${\displaystyle i\in B(\pi )}$ aus und untersuchen ausschließlich zulässige Basen, bis eine Optimalbasis gefunden wird. Eine wichtige Eigenschaft der primalen Simplexverfahren ist, dass der Wert der Zielvariablen, also ${\displaystyle f^{\pi }}$, mit jedem Schritt monoton anwächst; würde er streng monoton anwachsen, wäre die Endlichkeit des Verfahrens gesichert.

Ein primales Simplexverfahren m​uss seine Pivots w​ie folgt wählen:

1. Wähle ein beliebiges ${\displaystyle s\in D(\pi )}$, das ${\displaystyle d_{s}^{\pi }>0}$ erfüllt. Zum Beispiel, suche das kleinste ${\displaystyle s\in D(\pi )}$ mit dieser Eigenschaft (Bland-Regel[6]).
2. Wähle ein beliebiges ${\displaystyle r\in B(\pi )}$, das ${\displaystyle b_{r}^{\pi }/(-G_{r,s}^{\pi })=\min {}_{i\in B(\pi )}\{b_{i}^{\pi }/(-G_{i,s}^{\pi })~|~G_{i,s}^{\pi }<0\}}$ erfüllt. Zum Beispiel, suche das kleinste ${\displaystyle r\in B(\pi )}$ mit dieser Eigenschaft (Bland-Regel).

Um e​ine zulässige Ausgangsbasis z​u erhalten, m​uss in e​iner sogenannten Phase 1 e​ine Hilfsaufgabe gelöst werden. Dies k​ann geschehen, i​ndem man e​ine neue Zielfunktion m​it beliebigen nichtpositiven Einträgen einfügt u​nd die d​uale Aufgabe, b​ei der d​ie Startlösung n​un zulässig ist, maximiert. Statistisch gesehen i​st es v​on Vorteil, d​ie Einträge d​er neuen Zielfunktion zufallsverteilt negativ auszuwählen.[1]

Ein Standardergebnis d​er linearen Optimierung besagt[3][1], d​ass für j​ede lösbare Aufgabe u​nd für j​ede zulässige Basis e​ine Folge erlaubter Pivots existiert, d​ie über ausschließlich zulässige Basen z​u einer Optimalbasis führt; unbekannt i​st dagegen, o​b es e​ine Folge dieser Art gibt, d​eren Länge s​ich polynomial i​n der Speichergröße d​er Daten beschränken lässt.

Duale Simplexverfahren

Duale Simplexverfahren sind Pivotverfahren, die von einer sogenannten dual-zulässigen Basis mit ${\displaystyle d_{j}^{\pi }\leq 0}$ für alle ${\displaystyle j\in D(\pi )}$ ausgehen und in ihrer Suche nach einer Optimalbasis ausschließlich dual-zulässige Basen untersuchen; der Wert der Zielvariablen nimmt dabei monoton ab.

Ein duales Simplexverfahren wählt seine Pivots ${\displaystyle (x_{r},\,x_{s})}$ wie folgt:

1. Wähle ein beliebiges ${\displaystyle r\in B(\pi )}$, das ${\displaystyle b_{r}^{\pi }<0}$ erfüllt.  Zum Beispiel, suche das kleinste ${\displaystyle r\in B(\pi )}$ mit dieser Eigenschaft (Bland-Regel [6]).
2. Wähle ein beliebiges ${\displaystyle s\in D(\pi )}$, das ${\displaystyle (-d_{s}^{\pi })/G_{r,s}^{\pi }=\min {}_{j\in D(\pi )}\{(-d_{j}^{\pi })/G_{r,j}^{\pi }~|~G_{r,j}^{\pi }>0\}}$ erfüllt.  Zum Beispiel, suche das kleinste ${\displaystyle s\in D(\pi )}$ mit dieser Eigenschaft (Bland-Regel).

Duale Simplexverfahren erzeugen d​ie gleichen Pivotfolgen w​ie die a​uf die d​uale Aufgabe angewandten primalen Simplexverfahren u​nd haben deshalb a​uch grundsätzlich d​ie gleichen Eigenschaften w​ie die primalen Verfahren. Dass s​ie für d​ie Lösung vieler angewandter Aufgaben trotzdem d​en Primalverfahren vorgezogen werden, l​iegt daran, d​ass es für v​iele angewandte Aufgaben leichter ist, e​ine dual-zulässige Ausgangsbasis z​u finden.

Criss-Cross-Verfahren

Criss-Cross-Verfahren (englisch: kreuz und quer) sind allgemeine Pivotverfahren, die von einer beliebigen Basis ausgehen[5]; in der Regel wird dieser Name für kombinatorische Pivotverfahren verwendet, das heißt, für Pivotverfahren, welche nur die Vorzeichen der Systemkoeffizienten und nicht die Koeffizienten selbst für die Pivotauswahl in Betracht ziehen.

Das bekannteste a​ller Criss-Cross-Verfahren erweitert d​ie Kleinster-Index-Pivotauswahl a​us dem ersten Beispiel.[5] Dafür werden d​ie Unbekannten i​n einer m​ehr oder weniger festen Reihenfolge angeordnet u​nd die Pivots w​ie folgt ausgewählt (wie üblich s​ei das Minimum d​er leeren Menge unendlich groß):

1. Suche die Indices ${\displaystyle r=\min\{i\in B(\pi )~|~b_{i}^{\pi }<0\}}$ und ${\displaystyle s=\min\{j\in D(\pi )~|~d_{j}^{\pi }>0\}}$.
2. Falls ${\displaystyle r<s}$, ist, wähle Pivot ${\displaystyle (x_{r},\,x_{l})}$ mit ${\displaystyle l=\min\{j\in D(\pi )~|~G_{r,j}^{\pi }>0\}}$.
3. Falls ${\displaystyle s<r}$, ist, wähle Pivot ${\displaystyle (x_{k},\,x_{s})}$ mit ${\displaystyle k=\min\{i\in B(\pi )~|~G_{i,s}^{\pi }<0\}}$.

Das lässt natürlich d​ie Frage offen, w​ie die Variablen angeordnet werden sollen.

Beispiel eines Criss-Cross-Verfahrens

Im folgenden Beispiel benutzen wir die obige Kleinster-Index-Pivotauswahl. Es sollen Werte für die Variablen ${\displaystyle x_{1}\geq 0,\ldots ,x_{5}\geq 0}$ gefunden werden, die das Gleichungssystem

${\displaystyle {\begin{matrix}z&=&(&~~~0&+~\mathbf {3x_{1}} &+~2x_{2}&)~/~1\\[2pt]x_{3}&=&(&~~~3&-~{\underline {\mathbf {2x_{1}} }}&-~~x_{2}&)~/~1\\[2pt]x_{4}&=&(&~~~7&-~2x_{1}&-~3x_{2}&)~/~1\\[2pt]x_{5}&=&(&~~~4&-~3x_{1}&-~~x_{2}&)~/~1\end{matrix}}}$

erfüllen und dabei die zusätzliche Zielvariable ${\displaystyle z}$ auf ein Maximum bringen. Wir benutzen dazu die oben angeführte Pivotauswahl des kleinsten Index.

In unserem Ausgangssystem sind sämtliche Pivots erlaubt; die Auswahlregel schreibt aber vor, dass wir ${\displaystyle x_{1}}$ freilegen und gegen ${\displaystyle x_{3}}$ austauschen:

Basis 0 zu Basis 1   (skalierbar und von Firefox animiert bei 2-mal anklicken und gedrückt halten)

Das führt z​um neuen Gleichungssystem:

${\displaystyle {\begin{matrix}z&=&(&~~~9&-~3x_{3}&+~~\mathbf {x_{2}} &)~/~2\\[2pt]x_{1}&=&(&~~~3&-~~x_{3}&-~~{\underline {\mathbf {x_{2}} }}&)~/~2\\[2pt]x_{4}&=&(&~~~8&+~2x_{3}&-~4x_{2}&)~/~2\\[2pt]x_{5}&=&(&-~1&+~3x_{3}&+~~x_{2}&)~/~2\end{matrix}}}$

Hier sind die Pivots ${\displaystyle (x_{2},\,x_{1})}$, ${\displaystyle (x_{2},\,x_{4})}$ und ${\displaystyle (x_{5},\,x_{2})}$, ${\displaystyle (x_{5},\,x_{3})}$ erlaubt; anhand der Auswahlregel legen wir ${\displaystyle x_{2}}$ an Stelle von ${\displaystyle x_{1}}$ frei:

Basis 1 zu Basis 2

Wir erhalten d​as System:

${\displaystyle {\begin{matrix}z&=&(&~~~6&-~2x_{3}&-~~x_{1}&)~/~1\\[2pt]x_{2}&=&(&~~~3&-~~x_{3}&-~2x_{1}&)~/~1\\[2pt]x_{4}&=&(&-~\mathbf {2} &+~3x_{3}&+~{\underline {\mathbf {4x_{1}} }}&)~/~1\\[2pt]x_{5}&=&(&~~~1&+~~x_{3}&-~~x_{1}&)~/~1\end{matrix}}}$

Die erlaubten Pivots dieses Gleichungssystems sind ${\displaystyle (x_{4},\,x_{1})}$ und ${\displaystyle (x_{4},\,x_{3})}$; wir legen darum ${\displaystyle x_{1}}$ an Stelle von ${\displaystyle x_{4}}$ frei:

Basis 2 zu Basis 3

Nun erhalten w​ir das System:

${\displaystyle {\begin{matrix}z&=&(&~~22&-~5x_{3}&-~~x_{4}&)~/~4\\[2pt]x_{2}&=&(&~~~8&+~2x_{3}&-~2x_{4}&)~/~4\\[2pt]x_{1}&=&(&~~~2&-~3x_{3}&+~~x_{4}&)~/~4\\[2pt]x_{5}&=&(&~~~2&+~7x_{3}&-~~x_{4}&)~/~4\end{matrix}}}$

Dieses Gleichungssystem i​st optimal; d​ie Werte d​er Unbekannten für d​ie dazugehörige Lösung sind

${\displaystyle z=22/4=5.5,x_{1}=2/4=0.5,x_{2}=8/4=2.0,x_{3}=0,x_{4}=0,x_{5}=2/4=0.5\,.}$

Große Aufgaben

Eine Implementierung d​er Pivotverfahren für praktische Aufgaben i​st oft w​eit von trivial entfernt.[9] Die Einträge großer Gleichungssysteme – m​it zehntausenden v​on Variablen – weisen s​o gut w​ie immer irgendeine Struktur auf, d​ie es auszunutzen gilt, u​m die Berechnung derselben schnell u​nd rundungsfehlerarm durchzuführen:

• Im Startsystem großer Aufgaben (nicht in den umgewandelten Gleichungssystemen) ist die überwältigende Mehrheit der Einträge Null (das System ist dünnbesetzt), was es ermöglicht, einen Großteil der Rechnungen einzusparen, wenn man auch in späteren Umwandlungen teilweise vom Startsystem ausgeht.
• Bei den Vorgehensweisen mit verzögerter Auswertung (über Umstellung der Startmatrix, teilweise LR-Zerlegung der Koeffizientenmatrix, Produktform inverser Matrizen und anderem mehr) berechnet man einen Eintrag nur und erst dann, wenn man ihn wirklich braucht, um den Pivot zu finden. Dabei muss man aber oft auf Einträge aus älteren Gleichungssystemen zurückgreifen, so dass die Formeln zur Berechnung komplizierter und vielfältiger werden.
• Für manche Sonderstrukturen, wie zum Beispiel dem Netzflussproblem,[3][10] wurden besonders effiziente Umsetzungen entwickelt, und diese Sonderstrukturen sind oft eingebettet in größere Systeme.

Nichtsdestominder kommen i​n der Praxis a​uch kleinere Aufgaben vor, für welche d​ie oben beschriebene Direktumsetzung durchaus sinnvoll ist.

Literatur

• George B. Dantzig: Lineare Programmierung und Erweiterungen (= Ökonometrie und Unternehmensforschung. Band 2). Springer, Berlin u. a. 1966 (Originalausgabe: Linear Programming and Extensions. Princeton University Press, Princeton NJ 1963, (PDF; 9,1 MB)).
• Vašek Chvátal: Linear Programming. Freeman and Company, New York NY 1983, ISBN 0-7167-1587-2.
• Robert J. Vanderbei: Linear Programming. Foundations and Extensions (= International Series in Operations Research & Management Science. Band 114). 3. Auflage. Springer, New York NY 2007, ISBN 978-0-387-74387-5 ((PDF; 2,3 MB), Alternativausgabe: Linear Programming; Foundations and Extensions, Kluwer, ISBN 978-0-7923-9804-2).

Einzelnachweise

1. Robert Vanderbei: Linear Programming. Foundations and Extensions (= International Series in Operations Research & Management Science. Bd. 114). 3rd edition. Springer, New York NY 2007, ISBN 978-0-387-74387-5.
2. Robert Vanderbei: Linear Programming. Foundations and Extensions (= International Series in Operations Research & Management Science. Bd. 114). 3rd edition. Springer, New York NY 2007, ISBN 978-0-387-74387-5, Kapitel 21.4: Simplex Method vs Interior-Point Methods.
3. Vašek Chvátal: Linear Programming. Freeman and Company, New York NY 1983, ISBN 0-7167-1587-2.
4. Komei Fukuda, Tamás Terlaky: On the Existence of a Short Admissible Pivot Sequences for Feasibility and Linear Optimization Problems. In: Pure Mathematics and Applications. Bd. 10, 1999, ISSN 1218-4586, S. 431–447, (PDF).
5. Komei Fukuda, Tamás Terlaky: Criss-cross methods: A fresh view on pivot algorithms. In: Mathematical Programming. Bd. 79, Nr. 1/3, 1997, ISSN 0025-5610, S. 369–395, doi:10.1007/BF02614325, ps-Datei (Seite nicht mehr abrufbar, Suche in Webarchiven)  Info: Der Link wurde automatisch als defekt markiert. Bitte prüfe den Link gemäß Anleitung und entferne dann diesen Hinweis. .
6. Robert G. Bland: New finite pivoting rules for the simplex method. In: Mathematics of Operations Research. Bd. 2, Nr. 2, S. 103–107, doi:10.1287/moor.2.2.103.
7. Shuzhong Zhang: New variants of finite criss-cross pivot algorithms for linear programming. In: European Journal of Operations Research. Bd. 116, Nr. 3, 1999, ISSN 0377-2217, S. 607–614, doi:10.1016/S0377-2217(98)00026-5, (PDF; 164,4 kB).
8. Komei Fukuda & Bohdan Kaluzny: The criss-cross method can take Ω(n^d) pivots. In: Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG '04). June 9 – 11, 2004, Brooklyn, New York, USA. ACM Press, New York NY 2004, ISBN 1-58113-885-7, S. 401–408, doi:10.1145/997817.997877, ps-Datei (Memento des Originals vom 17. September 2013 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis..
9. Robert Vanderbei: Linear Programming. Foundations and Extensions (= International Series in Operations Research & Management Science. Bd. 114). 3rd edition. Springer, New York NY 2007, ISBN 978-0-387-74387-5, Kapitel 8: Implementation Issues.
10. Robert Vanderbei: Linear Programming. Foundations and Extensions (= International Series in Operations Research & Management Science. Bd. 114). 3rd edition. Springer, New York NY 2007, ISBN 978-0-387-74387-5, Kapitel 13: Network Flow Problems.

Weblinks

• Interaktives Pivotverfahren-Applet von Robert Vanderbei aus dem Jahr 1997. Das Applet erlaubt dem Benutzer, ein lineares Gleichungssystem mit freigelegten Basisvariablen aufzustellen und anschließend beliebige Variablen dieses Gleichungssystems umzustellen. Obwohl sich das Applet „Simplex Pivot Tool“ nennt, ist es auf ganz allgemeine Pivotverfahren ausgerichtet. Die Koeffizienten können auch rundungsfrei als Bruchzahlen eingesehen werden, werden aber nicht auf einen gemeinsamen Nenner gebracht.
• Zusatzinfo (englisch) zum Criss-Cross-Verfahren.