Benutzer:Heinrich Puschmann/Pivotverfahren

( Für die hier unter meinem Benutzernamen geführten Seite (Bilder ausgenommen) übernehme ich als Autor die inhaltliche Verantwortung. Sie weicht naturgemäß etwas von der veröffentlichten Seite ab, auf welche wie in jedem Wikipedia-Artikel verschiedene Autoren Zugriff haben. --Heinrich Puschmann 08:46, 21. Dez. 2007 (CET) )

<-- Geordnete Liste der Literaturnachweise:   '   -->

---

---

Pivotverfahren (auch Basisaustauschverfahren) sind Algorithmen der mathematischen Optimierung, insbesondere der linearen Optimierung. Für ein vorgegebenes System linearer Gleichungen in nichtnegativen Variablen (im Wesentlichen dasselbe wie ein System linearer Ungleichungen) wird nach der bestmöglichen von vielen Alternativlösungen (einer sogenannten Optimallösung) gesucht, und auf dieser Suche das Gleichungssystem Schritt für Schritt umgewandelt ohne dabei die Lösungsmenge zu verändern.  Wichtige Pivotverfahren sind die Simplexverfahren und die Criss-Cross-Verfahren.

Pivotverfahren spielen für die Behandlung von linearen Ungleichungen eine analoge und ähnlich wichtige Rolle wie das Gaußsche Eliminationsverfahren für die Lösung linearer Gleichungssysteme in unbeschränkten Variablen. Hauptanwendungsgebiet der Pivotverfahren ist die lineare Optimierung: sie gehören zu den meistverwendeten Lösungsmethoden in der Unternehmensforschung, der Wirtschaftswissenschaft, dem Gütertransport, und sie werden auch in vielen anderen Gebieten wie im Ingenieurbau (Strukturoptimierung), in der Statistik (Regressionsanalyse) und der Spieltheorie zunehmend eingesetzt. Aufgaben mit zehntausenden Variablen und Ungleichungen sind an der Tagesordnung.

Pivotansatz

Problemstellung

Ein Pivotverfahren geht immer von einem besonders gearteten linearen Gleichungssystem aus, in dem alle Variablen, außer vielleicht einer, nichtnegative Werte annehmen sollen. Jedes System linearer Ungleichungen oder Gleichungen, und auch jede lineare Optimierungsaufgabe, lässt sich nämlich in folgende (englisch dictionary genannte ) Buchform bringen:

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

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

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

( 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

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

wird umgeformt in

$x_{4}~=~8~+~2x_{1}~-~4x_{2}~+~x_{3},\quad x_{4}\geq 0$   )

Mit Hilfe der Indexmengen

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

lässt sich diese Aufgabe auch wie folgt in gedrungener Form ausdrücken:

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

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

In jedem Schritt eines Pivotverfahrens ist wie oben eine Teilmenge der Variablen als unabhängig hervorgehoben, während die restlichen Variablen, sogenannte Basisvariablen, als lineare Funktionen der unabhängigen Variablen ausgedrückt werden; in aufeinanderfolgenden Schritten wechselt immer eine der Variablen von unabhängig auf Basisvariable und eine zweite in die umgekehrte Richtung; solche Variablenpaare werden Pivots genannt.

Optimumbedingungen

Falls im oben aufgestellten linearen Gleichungssystem beide folgende Optimumbedingungen erfüllt sind,

• $b_{i}\geq 0\,$  für alle  $i\in B$   (Zulässigkeit)  und
• $d_{j}\leq 0\,$  für alle  $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 $\,x_{1}=0,\ldots ,x_{n}=0\,$ setzt. Zum einen sind die Werte der freigelegten Variablen  $\,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  $\,z\leq f\,$  gilt.

( Im folgenden Beispielsystem,

${\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  $b_{5}=-1<0$  und  $d_{2}=+1>0$  ist. Zum ersten würde die Versuchslösung  $x_{1}=x_{2}=0$  den negativen Wert  $x_{5}=-1$  enthalten, und zum zweiten könnte dessen Zielvariablenwert  $z=-3x_{1}+x_{2}$  bei Lösungen mit  $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 $\{x_{n+1},\ldots ,x_{n+m}\}$ eine andere, gleich große Teilmenge der $n+m$ Unbekannten auswählt und diese freilegt. Es sei   $\pi (1),\ldots ,\pi (n+m)$   eine Umstellung der Unbekannten,

$\{\pi (1),\ldots ,\pi (n+m)\}~=~\{1,\ldots ,n+m\}.$

Anhand folgender Aufteilung der Variablen,

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

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

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

${\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 $G_{i,j}^{\pi }$ nur für Indexpaare mit $i\in B(\pi )$ und $j\in D(\pi )$ definiert sind. Die Einträge des so umgewandelten Gleichungssystems lassen sich nun erneut auf die Optimumbedingungen überprüfen,

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

was wiederum unter Umständen zu einer Lösung der Aufgabe führt.

Ein Standardergebnis der linearen Optimierung sagt aus, dass für jede lösbare Aufgabe ein Satz Basisvariablen existiert, der zu einer Lösung führt. Bei erfüllten Optimumbedingungen bilden die Basisvariablen eine sogenannte Optimalbasis des Systems.

Pivots und Pivotelemente

Jedes nichtverschwindende $\,G_{r,s}^{\pi }\neq 0\,$ des obigen Gleichungssystems, dem Pivotsystem, nennt sich Pivotelement, und erlaubt es, die unabhängige Variable $\,x_{s}\,$ an Stelle der Basisvariablen $\,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 sogenannte erlaubte (admissible) Pivots, $(x_{r},\,x_{s})$ die Folgendes erfüllen müssen:

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

( Im obigen Beispielsystem,

${\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  $b_{5}<0$  Pivotelement  $G_{5,1}=+3>0$  mit Pivot $(\,x_{5},\,x_{1}\,),$  und Pivotelement  $G_{5,2}=+1>0$  mit Pivot $(\,x_{5},\,x_{2}\,)$  erlaubt. Wegen der Optimalitätsverletzung  $d_{2}>0$  sind aber ebenfalls Pivotelement  $G_{3,2}=-1<0$  mit Pivot $(\,x_{3},\,x_{2}\,)$,  und Pivotelement  $G_{4,2}=-4<0$  mit Pivot $(\,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 $\,n+m\,$ erlaubten Pivots existiert, die zu einer Optimalbasis führt. 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 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 $z\,$ finden lassen (unbeschränkte Aufgabe).

Beispiele

Direkte Umsetzung

Um Rundungsfehler zu vermeiden, arbeiten wir in den folgenden Beispielen mit Bruchzahlen und wählen einen gemeinsamen Nenner für sämtliche Einträge. Um in jedem Schritt einen gemeinsamen Nenner für das Gesamtsystem zu finden, müssen wir die Einträge nicht zusätzlich untersuchen. 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 die Einträge des Folgesystems mit diesem gemeinsamen Nenner multipliziert werden, erhält man ganzzahlige Werte. Bei der Aufstellung des Folgesystems veraltet der gemeinsame Nenner des Vorgängersystems, weshalb sämtliche Einträge des Folgesystems ungeprüft durch diesen veralteten Nenner gekürzt werden können.

Eine Tabelle mit den Einträgen eines Pivotsystems wird oftmals Tableau genannt. Das folgende Schema zeigt an, wie sich die Einträge des Pivotsystems von einem Schritt auf den nächsten verändern:

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

Das Zeichen $\delta \,$ steht hier 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.

Die Bilder zu den Schritten in den folgenden Beispielen zeigen alle dasselbe Gleichungssystem in verschiedenen orthogonalen Koordinaten; dabei gilt:

• Die grün umrandete Fläche ist der zulässige Bereich, in dem alle Variablen nichtnegative Werte haben.
• Koordinatenachsen entsprechen den Gleichungen $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 $\,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  $\,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 $(x_{r},\,x_{s})$ nach folgender Regel wählen:

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

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

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

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

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

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

Wir erhalten nun das folgende, umgewandelte Gleichungssystem:

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

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

Basis 1 zu Basis 2

Wir erhalten das System

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

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

Basis 2 zu Basis 3

Nun erhalten wir:

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

Da dieses System die Optimalitätsbedingungen erfüllt (und dem entsprechend auch keine erlaubten Pivots hat), erhalten wir die Lösung:

$x_{1}=6/11=0.55\,,\quad ~$  $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 $\,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 $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 $s=\min\{j\in D(\pi )~|~G_{r,j}^{\pi }>0\}$.

Um zu zeigen, dass so etwas falsch gehen kann, starten wir mit dem System:

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

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

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

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

${\begin{matrix}2\,x_{1}&=&~~~0&-~3x_{3}&-~~x_{4}\\[2pt]2\,x_{2}&=&~~~4&+~7x_{3}&+~~x_{4}\\[2pt]2\,x_{5}&=&-~\mathbf {2} &+~~{\underline {\mathbf {x_{3}} }}&+~~x_{4}\\[2pt]2\,x_{6}&=&~~~6&-~7x_{3}&-~3x_{4}\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 $\,x_{5}\,$ um an deren Stelle $\,x_{3}\,$ freizulegen erhalten wir:

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

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

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

Dieses Gleichungssystem hat wieder dieselben Einträge wie das Startsystem; weil diese aber immer noch anderen Variablen zugeordnet sind, ist der Kreislauf nach diesen 4 Schritten noch nicht beendet. Dennoch ist leicht zu überprüfen, dass der Algorithmus in insgesamt 6 Schritten zum Startsystem in vertauschter Reihenfolge und in 12 Schritten zum genauen Startsystem zurückkehrt. Das Gesamtsystem von Gleichungen und Ungleichungen hat in Wirklichkeit gar keine Lösung, doch kann das Pivotverfahren das mit der oberen Pivotwahl nicht herausfinden.

Die Reihenfolge, in der Variable und Gleichungen eines Pivotsystems aufgelistet werden ist grundsätzlich willkürlich. Dennoch wurden die ersten Pivotauswahl-Strategien, die Variablen und Gleichungen unabhängig von deren Darstellung im Pivotsystem behandeln (und dazu noch leicht umsetzbar waren), erst 1977 von Bland  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  $k\!\in \!\{n+1,\ldots ,n+m\}$   mit   $b_{\pi (k)}^{\pi }=\min _{i}^{\,}\{b_{\pi (i)}^{\pi }\}<0$,
2. Danach wähle das kleinste  $l\!\in \!\{1,\ldots ,n\}$   mit   $G_{\pi (k),\pi (l)}^{\pi }>0\,$,
3. Der Pivot sei $(x_{\pi (k)},\,x_{\pi (l)})$,

doch führt diese beim obigen Beispiel in genau dieselbe endlose Schleife.

Eine kreislaufanfällige Pivotauswahlregel (veraltet)

Es folgt nun ein Beispiel einer ungeeigneten Pivotauswahl. Es sei wieder $\,z=0+0\,x_{1}+0\,x_{2}\,$.  Bei ungeeigneter Pivotwahl kann ein Pivotverfahren in einen unendlichen Kreislauf (eine Endlosschleife) geraten, wenn wir beispielsweise wie bei folgender Regel einfach die erste der in Frage kommenden Zeilen und Spalten auswählen:

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

Wir starten mit dem System:

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

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

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

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

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

Dieses Gleichungssystem hat bereits dieselben Einträge wie das Startsystem. Nach Auswahl der Basisvariablen $\,x_{5}\,$ um an deren Stelle $\,x_{3}\,$ freizulegen erhalten wir:

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

Darauf wählen wir $\,x_{6}\,$, legen an Stelle dessen $\,x_{4}\,$ frei, und erhalten:

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

Jetzt werden wir angehalten, $\,x_{2}\,$ zu wählen und an Stelle dessen $\,x_{5}\,$ freizulegen, aber nach der kreissicheren Regel im vorherigen Beispiel müssten wir dafür $\,x_{1}\,$ und $\,x_{5}\,$ wählen. Die Einträge des Gleichungssystems sind wieder die des Startsystems, nach 6 Schritten wiederholen sich die Startgleichungen in umgestellter Reihenfolge, und nach 12 Schritten wiederholt sich das Startsystem genau. Das Gesamtsystem von Gleichungen und Ungleichungen hat in Wirklichkeit gar keine Lösung, doch kann das Pivotverfahren mit der oberen Pivotwahl das nicht herausfinden.

Dualität

Duale Optimierungsaufgaben

Jeder linearen Optimierungsaufgabe lässt sich, von der obigen Buchform abhängig, eine zweite Optimierungsaufgabe zuordnen; die Koeffizientenmatrix dieser sogenannten dualen Aufgabe ist die negative Transponierte der Koeffizientenmatrix der ursprünglichen Aufgabe:

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

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

In gedrungener Form wird das zu

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

${\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   $\max \,z,\;\max \,w$   nicht durch   $\min \,z,\;\min \,w$   ersetzt werden!   Oftmals wird die duale Aufgabe auch mit der Zielfunktion $\min \,(-w)$ anstelle von $\max \,w$ definiert, was zwar machbar, aber auch unübersichtlicher ist.)

Offenbar führt die duale Umwandlung einer dualen Aufgabe wieder zur ursprünglichen Aufgabe; das ist aber nur dann leicht ersichtlich, wenn die Aufgabe in die hier verwendete Form gebracht wurde. Wie gleich gezeigt wird, ist das Maximum der Dualaufgabe (soweit vorhanden) genau das negative Maximum der Primalaufgabe.

Schrittweise Umwandlung

Die obige Beziehung der Koeffizienten zwischen Primalaufgabe und Dualaufgabe gilt nicht etwa nur für die Ausgangsbasis, sondern bleibt erhalten, solange die Basisvariablen nach denselben Pivots umgewandelt werden. Es gilt

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

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

Diese Dualitätsbeziehung lässt sich am leichtesten an einem Pivotsystem betrachten, das ausschließlich zwei unabhängige Unbekannte und zwei freigelegte Unbekannte enthält. Wir erhalten dasselbe System, wenn wir zuerst zwei der Unbekannten austauschen und danach die duale Aufgabe herleiten, oder wenn wir diese Schritte in umgekehrter Reihenfolge tun:

${\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}}$
$-\,[\cdots ]^{\,T}$		$-\,[\cdots ]^{\,T}$
${\begin{matrix}\delta \,y_{j}&\!=\!&(-\alpha )&\!\!\!y_{i}&\!+\!&(-\zeta )&\!\!\!y_{r}\\[6pt]\delta \,y_{s}&\!=\!&(-\sigma )&\!\!\!y_{i}&\!+\!&(-p)&\!\!\!y_{r}\\\end{matrix}}$	${y_{s}\leftrightarrow y_{r}}$	${\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 der Dualbeziehung folgt, dass ein Optimalsystem für die Primalaufgabe auch ein Optimalsystem für die duale Aufgabe liefert.

Zur Aufgabe im ersten Rechenbeispiel gehört folgende duale Aufgabe (wegen $z=0+0x_{1}+0x_{2}$  ist hier $f=d_{1}=d_{2}=0$ ):

${\begin{matrix}~1\,w~&=&+~~\mathbf {2y_{3}} &+~~4y_{4}&-~~9y_{5}\\[2pt]1\,y_{1}&=&+~~7y_{3}&+~~5y_{4}&-~~2y_{5}\\[2pt]1\,y_{2}&=&-~~{\underline {\mathbf {2y_{3}} }}&-~~2y_{4}&+~~3y_{5}\end{matrix}}$

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

Das Optimalystem dazu ist, wie erwartet,

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

und die optimale Lösung dazu ist natürlich $x_{k}=0$ für alle $k\in D\cup B$.   Die Primalaufgabe hatte eine implizite Zielfunktion $z=0$; sämtliche Optimallösungen der primalen und auch der dualen Aufgabe hätten deshalb, soweit vorhanden, einen Zielwert $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 $w$ und somit gar keine Optimallösung geben können.

Komplementärer Schlupf

Falls für eine lineare Optimierungsaufgabe nur eine optimale Lösung, aber keine optimale Basis bekannt ist, dann lässt sich trotzdem "schnell" über ein lineares Gleichungssystem eine optimale Lösung für die entsprechende duale Aufgabe finden. Dazu verhilft der Satz vom komplementären Schlupf: jedes Paar optimaler Lösungen (falls ein solches existiert) erfüllt die zusätzlichen Bedingungen

$\forall ~k\in D\cup B\qquad x_{k}\,y_{k}~=~0,$

eine Eigenschaft, die unmittelbar aus der Existenz einer optimalen Basis folgt.

Ausgeschrieben besagt das

${\begin{matrix}\forall ~j\in D\qquad x_{j}\,{\bigl (}\!-d_{j}-\sum _{i\in B}G_{i,j}\,y_{i}{\bigr )}~=~0\\[3pt]\forall ~i\in B\qquad {\bigl (}\,b_{i}+\sum _{j\in D}G_{i,j}\,x_{j}{\bigr )}\,y_{i}~=~0\end{matrix}}$

und daraus folgt das Gleichungssystem

${\begin{matrix}\forall ~j\in \{k\in D~{\big |}~x_{k}>0\}\qquad d_{j}~+~\sum _{i\in B}\,G_{i,j}\,y_{i}~=~0\\[3pt]\forall ~i\in \{k\in B~{\big |}~b_{i}+\sum _{j\in D}G_{k,j}x_{j}>0\}\qquad y_{i}~=~0\end{matrix}}$

Lösungspaarsuche

Eine weitere 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 $w$ ist das Negative des Optimalwerts von $z\,.$ Für zulässige Lösungspaare der beiden Aufgaben gilt demzufolge

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

und für optimale Lösungspaare gilt

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

Daraus folgt, dass die optimalen Lösungen beider Aufgaben genau die Lösungen der obigen Gleichungssysteme mit folgenden Ungleichungen sind:

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

Ausgeschrieben ist das

${\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 der Praxis ist so ein Vorgehen freilich nur dann konkurrenzfähig, wenn die gemeinsame Datenstruktur beider Aufgaben auch ausgenützt wird.

Besondere Pivotverfahren

Aufgabenbereiche

Die einfachsten aller Pivotverfahren gehören zu den Criss-Cross-Verfahren, die in den 80er Jahren für Aufgabenstellungen im Kontext orientierter Matroide entwickelt wurden. Die wesentlich komplexeren Simplexverfahren wurden aber bereits 1947 von George Dantzig für die Lösung linearer Optimierungsprobleme veröffentlicht und haben danach dank ihrer weiten Verbreitung die Suche nach Criss-Cross-Verfahren maßgeblich motiviert. Weitere Pivotverfahren wurden für das lineare Komplementaritätsproblem mit suffizienten Matrizen (einschließlich quadratischer Programmierung) und für linear-fraktionale Optimierungsprobleme entwickelt.

Bei der Ausarbeitung verschiedener Pivotverfahren geht es in der Hauptsache darum, die Anzahl der Pivotschritte und damit auch die Laufzeit des Verfahrens gering zu halten. Während die derzeit bekannten Simplexverfahren alle eine überpolynomial beschränkte Laufzeit beanspruchen - das ist eine Laufzeit, die sich nicht durch ein Polynom in der Datenspeichergröße beschränken lässt - sind Laufzeitschranken für die Criss-Cross-Verfahren ein (bis 2010) noch offenes Forschungsthema. Zusammenfassend lässt sich darüber sagen, dass Criss-Cross-Verfahren mehr Freiheitsgrade aufweisen als Simplexverfahren, und dass ein Criss-Cross-Verfahren genau aus diesem Grund bei einer guten Pivotauswahl schneller und bei einer schlechten Pivotauswahl langsamer als Simplexverfahren sein kann.

Primale Simplexverfahren

→ Hauptartikel: Simplex-Verfahren

Primale Simplexverfahren  (meist nur Simplexverfahren genannt) waren die ersten Pivotverfahren für die Linear${\begin{matrix}y_{1}\geq 0,\ y_{2}\geq 0,\ y_{3}\geq 0,\ y_{4}\geq 0,\ y_{5}\geq 0,\ \max ~w\end{matrix}}$e Optimierung, und wurden 1947 von George Dantzig veröffentlicht. Diese Pivotverfahren gehen von einer sogenannten zulässigen Basis mit  $b_{i}^{\pi }\geq 0$ für alle $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 $f^{\pi }\,$, mit jedem Schritt monoton anwächst; würde er streng monoton anwachsen, wäre die Endlichkeit des Verfahrens gesichert. Ein primales Simplexverfahren muss seine Pivots $(x_{r},\,x_{s})$ wie folgt wählen:

1. Wähle ein beliebiges $s\in D(\pi )$, das $d_{s}^{\pi }>0$ erfüllt.  Zum Beispiel, suche das kleinste $s\in D(\pi )$ mit dieser Eigenschaft (Bland-Regel ).
2. Wähle ein beliebiges $r\in B(\pi )$, das $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 ${\begin{matrix}y_{1}\geq 0,\ y_{2}\geq 0,\ y_{3}\geq 0,\ y_{4}\geq 0,\ y_{5}\geq 0,\ \max ~w\end{matrix}}$Beispiel, suche das kleinste $r\in B(\pi )$ mit dieser Eigenschaft (Bland-Regel).

Um eine zulässige Ausgangsbasis zu erhalten, muss in einer sogenannten Phase 1 eine Hilfsaufgabe gelöst werden.

Ein Standardergebnis der lineare Optimierung|Linearen Optimierung besagt, dass für jede lösbare Aufgabe und für jede zulässige Basis eine Folge erlaubter Pivots existiert, die über ausschließlich zulässige Basen zu einer Optimalbasis führt; unbekannt ist dagegen, ob es eine Folge dieser Art gibt, deren Länge sich polynomial in der Speichergröße der Daten beschränken lässt.

Beispiel zum primalen Simplexverfahren

Im folgenden Beispiel sollen Werte für die Variablen $\,x_{1}\geq 0,\ldots \ x_{5}\geq 0\,$ gefunden werden, die das Gleichungssystem

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

erfüllen und dabei die zusätzliche Zielvariable $z\,$ auf ein Maximum bringen. Da bei dieser besonderen Aufgabe sämtliche Zulässigkeitsbedingungen bereits erfüllt sind, $\forall ~i\in B~~b_{i}\geq 0$, können wir uns die Suche nach einer zulässigen Basislösung sparen und ein primales Simplexverfahren direkt anwenden; wir benutzen dazu die oben angeführten Bland-Regeln um die Pivots auszuwählen.

Im Sinne allgemeiner Pivotverfahren wären in unserem Ausgangssystem sämtliche Pivots erlaubt; damit aber die folgende Basislösung weiterhin die Zulässigskeitsbedingungen erfüllt schreibt die Auswahlregel von Bland vor, dass wir $\,x_{1}\,$ freilegen und gegen $\,x_{5}\,$ austauschen:

Das führt zum neuen Gleichungssystem:

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

Hier sind $(x_{2},\,x_{3})$, $(x_{2},\,x_{4})$ und $(x_{2},\,x_{1})$ allgemein erlaubte Pivots; anhand der Auswahlregel müssen wir aber $\,x_{2}\,$ an Stelle von $\,x_{3}\,$ freilegen:

Wir erhalten das System:

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

Die erlaubten Pivots dieses Gleichungssystems wären $(x_{5},\,x_{4})$ und $(x_{5},\,x_{1})$; wir legen davon $\,x_{5}\,$ an Stelle von $\,x_{4}\,$ frei:

Nun erhalten wir das System;

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

Dieses Gleichungssystem ist optimal; die Werte der Unbekannten für die dazugehörige Lösung sind

$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\,.$

Duale Simplexverfahren

Duale Simplexverfahren sind Pivotverfahren, die von einer sogenannten dual-zulässigen Basis mit  $d_{j}^{\pi }\leq 0$ für alle $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 $(x_{r},\,x_{s})$ wie folgt:

1. Wähle ein beliebiges $r\in B(\pi )$, das $b_{r}^{\pi }<0$ erfüllt.  Zum Beispiel, suche das kleinste $r\in B(\pi )$ mit dieser Eigenschaft (Bland-Regel ).
2. Wähle ein beliebiges $s\in D(\pi )$, das $(-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 $s\in D(\pi )$ mit dieser Eigenschaft (Bland-Regel).

Duale Simplexverfahren erzeugen die gleichen Pivotfolgen wie die auf die duale Aufgabe angewandten primalen Simplexverfahren, und haben deshalb auch grundsätzlich die gleichen Eigenschaften wie die primalen Verfahren. Dass sie für die Lösung vieler angewandter Aufgaben trotzdem den Primalverfahren vorgezogen werden liegt daran, dass es für viele angewandte Aufgaben leichter ist, eine dual-zulässige Ausgangsbasis zu finden.

Criss-Cross-Verfahren

Criss-Cross-Verfahren (englisch: kreuz und quer) sind allgemeine Pivotverfahren, die von einer beliebigen Basis ausgehen; 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 aller Criss-Cross-Verfahren erweitert die Kleinster-Index Pivotauswahl  aus dem ersten Beispiel. Dafür werden die Unbekannten in einer mehr oder weniger festen Reihenfolge angeordnet und die Pivots wie folgt ausgewählt (wie üblich, sei das Minimum der leeren Menge unendlich groß):

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

Das lässt natürlich die Frage offen, wie die Variablen angeordnet werden sollen.

Beispiel zu einem Criss-Cross-Verfahren

Im folgenden Beispiel sollen Werte für die Variablen $\,x_{1}\geq 0,\ldots \ x_{5}\geq 0\,$ gefunden werden, die das Gleichungssystem

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

erfüllen und dabei die zusätzliche Zielvariable $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 $\,x_{1}\,$ freilegen und gegen $\,x_{3}\,$ austauschen:

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

Das führt zum neuen Gleichungssystem:

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

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

Basis 1 zu Basis 2

Wir erhalten das System:

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

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

Basis 2 zu Basis 3

Nun erhalten wir das System;

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

Dieses Gleichungssystem ist optimal; die Werte der Unbekannten für die dazugehörige Lösung sind

$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 der Pivotverfahren für praktische Aufgaben ist oft weit von trivial entfernt. Die Einträge großer Gleichungssysteme – mit zehntausenden von Variablen – weisen so gut wie immer irgendeine Struktur auf, die es auszunutzen gilt, um die Berechnung derselben schnell und rundungsfehlerarm durchzuführen:

• Im Startsystem großer Aufgaben (nicht in den umgewandelten Gleichungssystemen) ist die überwältigende Mehrheit dieser 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, wurden besonders effiziente Umsetzungen entwickelt, und diese Sonderstrukturen sind oft eingebettet in größere Systeme.

Nichtdestominder kommen auch in der Praxis auch kleinere Aufgaben vor, für welche die oben beschriebene Direktumsetzung durchaus sinnvoll ist.

Literatur

Obwohl viele Texte der linearen Optimierung auf dem Markt zu finden sind, erreichen wenige die übersichtliche Klarheit und den zugänglichen Lesestil der Bücher von Chvátal und von Vanderbei. Beide wurden vielfach empfohlen und das letztere in der Auflage von 2007 aktualisiert. Das Geschichtswerk vom Begründer der linearen Optimierung, George Dantzig, liefert dazu viele lesenswerte Einzelheiten, ist aber für eine Einführung in das Thema weniger geeignet.

• George B. Dantzig: Lineare Programmierung und Erweiterungen.  Deutsche Auflage 1966
• Vašek Chvátal: Linear Programming.  Auflage 1983
• Robert J. Vanderbei: Linear Programming. Foundations and Extensions.  Revidierte 3. Auflage 2007

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.