Benutzer:Heinrich Puschmann/Pivotverfahren (Kladde)

<-- Geordnete Liste der Belege:

-->

---

---

Pivotverfahren (auch Basisaustauschverfahren) sind Algorithmen der mathematischen Optimierung. Für ein vorgegebenes System linearer Gleichungen in nichtnegativen Variablen 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 Gleichungen; Hauptanwendungsgebiet 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.

---

Pivotverfahren, oder pivotbasierter Optimierungsalgorithmus kann sich jeder Algorithmus nennen, der für seine Suche nach einem Optimum ein lineares Gleichungssystem aufstellt und in jedem Schritt strategisch ausgewählte Variablen bezüglich der Restvariablen freilegt, wobei sich aufeinanderfolgend freigelegte Variablensätze in nur einer Variable unterscheiden. Wichtige Pivotverfahren sind die Simplex-Verfahren  und die Criss-Cross-Verfahren  in der linearen Optimierung.

---

Pivotansatz

Allgemeine Vorgehensweise

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}x_{1}\geq 0,\ \ldots \ x_{n+m}\geq 0,\quad \max ~z\end{matrix}}$

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

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

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}x_{1}\geq 0,\ \ldots \ x_{n+m}\geq 0,\quad \max ~z\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.

Falls nun beide folgende Optimumbedingungen erfüllt sind, nämlich

• $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 aber 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.

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$ eine Umstellung der Unbekannten $x_{1},\ldots ,x_{n+m},$  also eine Indexfunktion die

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

erfüllt. Für neue Indexmengen

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

erstellen wir dann das Gleichungssystem:

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

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

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

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

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

Die Menge $\{x_{\pi (n+1)},\ldots ,x_{\pi (n+m)}\}$ wird Menge der Basisvariablen oder einfach Basis genannt. 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.

Jedes nichtverschwindende $\,G_{k,l}^{B}\neq 0\,$ des obigen Gleichungssystems, dem Pivotsystem, nennt sich Pivotelement, und erlaubt es, die unabhängige Variable $\,x_{l}~(l\in D)\,$ an Stelle der Basisvariablen $\,x_{k}~(k\in B),\,$ 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 zulässige Pivots $(x_{k},\,x_{l})$, die folgendes erfüllen müssen:

• entweder gilt gleichzeitig  $\,b_{k}^{B}<0\,$   und   $\,G_{k,l}^{B}>0\,$   (Zulässigkeitspivot),
• oder es gilt gleichzeitig  $\,d_{l}^{B}>0\,$   und   $\,G_{k,l}^{B}<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}\,)$  zulässig. 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}\,)$  zulässig.

Die Beschränkung auf zulässige Pivots verhindert, dass derselbe Pivot zweimal hintereinander ausgewählt wird. Die Regeln, nach denen in jedem Schritt eines dieser zulässigen 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 zulässigen 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\,$ zulässigen 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 zulässigen 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 zulässige 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).

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 (nicht negative) 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 zulässigen Pivot $(x_{k},\,x_{l})$ nach folgender Regel wählen:

1. Wähle   $k=\min\{i\in B(\pi )~|~b_{i}^{B}<0\}$,
2. Danach wähle   $l=\min\{j\in D(\pi )~|~G_{k,j}^{B}>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 zu einer Optimalbasis führt.

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

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

Die zulässigen Pivots im obigen Gleichungssystem sind $(x_{3},\,x_{2})$ und $(x_{4},\,x_{2})$; wir legen $\,x_{2}\,$ an Stelle von $\,x_{3}\,$ frei:

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

Das neue System ist

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

Die zulässigen Pivots sind nun $(x_{4},\,x_{1})$ und $(x_{4},\,x_{3})$; jetzt legen wir $\,x_{1}\,$ an Stelle von $\,x_{4}\,$ frei:

Basis 1 zu Basis 2

Wir erhalten das System

${\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 zulässige Pivot hier ist $(x_{5},\,x_{3})$; wir legen deshalb $\,x_{3}\,$ an Stelle von $\,x_{5}\,$ frei:

Basis 2 zu Basis 3

Nun erhalten wir

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

Da dieses System die Optimalitätsbedingungen erfüllt (und dem entsprechend auch keine zulässigen 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$

Eine kreislaufanfällige Pivotauswahlregel

Die Reihenfolge, in welcher Variable und Gleichungen eines Pivotsystems aufgelistet werden ist grundsätzlich willkürlich. Dennoch wurden die ersten Pivotauswahl-Strategien, welche 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, wurden Pivotauswahl-Strategien eher anhand von Datenstrukturen (sogenannte "Tableaus") beschrieben, und bei dieser Art Strategien konnte die Endlichkeit des Verfahrens ohne Zusatzberechnungen meist nicht gewährleistet werden. Es folgt ein Beispiel einer solchen ungeeigneten Pivotauswahl.

Es sei wieder $\,z=0+0\,x_{1}+0\,x_{2}\,$.  Bei ungeeigneter Pivotwahl kann ein Pivotverfahren in einen unendlichen Kreislauf oder Endlosschleife geraten. Als Beispiel für eine naheliegende, aber dennoch ungeeignete, Pivotwahl betrachten wir folgende Regel, die dem weitverwendeten dualen Simplexverfahren nachempfunden ist:

1. Wähle das kleinste  $r\!\in \!\{n+1,\ldots ,n+m\}$   mit   $b_{\pi (r)}^{B}=\min _{i}\{b_{\pi (i)}^{B}\}$,
2. Danach wähle das kleinste  $s\!\in \!\{1,\ldots ,n\}$   mit   $G_{\pi (r),\pi (s)}^{B}>0\,$.

Wir starten mit dem System:

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

${\begin{matrix}x_{1}\geq 0,\ x_{2}\geq 0,\ x_{3}\geq 0,\ x_{4}\geq 0,\ x_{5}\geq 0,\ x_{6}\geq 0\end{matrix}}$

Wir wählen $\,x_{4}\,$ und legen an Stelle dessen $\,x_{2}\,$ frei (nach der kreissicheren Regel im vorherigen Beispiel hätten wir $\,x_{3}\,$ und $\,x_{2}\,$ gewählt). Wir erhalten das System:

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

Wir wählen $\,x_{3}\,$, legen an Stelle dessen $\,x_{1}\,$ frei, und erhalten:

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

Aber dieses Gleichungssystem ist -abgesehen von der Benennung der Veränderlichen- identisch mit dem Startsystem. Die Zahleneinträge des Systems wiederholen sich alle 2 Schritte, nach 6 Schritten wiederholen sich die Gleichungen des Systems in umgestellter Form, und nach insgesamt 12 Schritten wiederholt sich das Startsystem genau, mit den Gleichungen und Unbekannten am ursprünglichen Ort. 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 Grundform abhängig, eine zweite, duale Optimierungsaufgabe zuordnen; die Koeffizientenmatrix dieser sogenannten dualen Aufgabe ist die negative Transposition 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}y_{1}\geq 0,\ \ldots \ y_{m+n}\geq 0,\quad \max ~w\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}y_{1}\geq 0,\ \ldots \ y_{n+m}\geq 0,\quad \max ~w\end{matrix}}$

(Vorsicht: Bei der Herleitung über diese Formulierung dürfen   $\max \,z,\ \max \,w$   nicht durch   $\min \,z,\ \min \,w$   ersetzt werden!)

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.

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^{B})&+&\sum _{i\in B(\pi )}\,(-b_{i}^{B})\,y_{i}\\[6pt]\forall ~j\in D(\pi )&&y_{j}&=&(-d_{j}^{B})&+&\sum _{i\in B(\pi )}\,(-G_{i,j}^{B})\,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}&\!=\!&({\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}&\!=\!&({\frac {\zeta \sigma \,-\,\alpha p}{\delta }})&\!\!\!y_{i}&\!+\!\!&(~~\zeta )&\!\!\!y_{s}\\[6pt]p\,y_{r}&\!=\!&(~-\sigma ~)&\!\!\!y_{i}&\!+\!\!&(-\delta )&\!\!\!y_{s}\\\end{matrix}}$

Dieses Schema zeigt auch an, wie sich die Einträge des Pivotsystems von einem Schritt auf den nächsten verändern. Das Zeichen $\delta \,$ steht 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.

Beispiel zur Dualität

Die Aufgabe im obigen Beispiel hat folgende duale Aufgabe (die Nullen stammen von $z=0+0x_{1}+0x_{2}\,$):

${\begin{matrix}~w~&=&(&0&+~~\mathbf {2y_{3}} &+~~4y_{4}&-~~9y_{5}&)~/~1\\[2pt]y_{1}&=&(&0&+~~7y_{3}&+~~5y_{4}&-~~2y_{5}&)~/~1\\[2pt]y_{2}&=&(&0&-~~{\underline {\mathbf {2y_{3}} }}&-~~2y_{4}&+~~3y_{5}&)~/~1\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}}$

Bei der ursprünglichen Aufgabe hatten wir $\,x_{2}\,$ an Stelle von $\,x_{3}\,$ freigelegt. Wenn wir im dualen Gleichungssystem $\,y_{3}\,$ an Stelle von $\,y_{2}\,$ freilegen, erhalten wir:

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

Wenn wir nun $\,y_{4}\,$ an Stelle von $\,y_{1}\,$ freilegen, erhalten wir:

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

Wenn wir $\,y_{5}\,$ an Stelle von $\,y_{3}\,$ freilegen, erhalten wir:

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

Der größtmögliche Wert für die Zielvariable ist somit $w=0\,$. Das ist derselbe Wert, den auch schon die Anfangslösung hatte, doch war das aus dem ersten Gleichungssystem nicht ersichtlich und ist selbstverständlich nicht immer der Fall.

Criss-Cross-Verfahren

Criss-Cross-Verfahren (englisch: kreuz und quer) sind kombinatorische Pivotverfahren, das heißt Pivotverfahren, welche nur die Vorzeichen der Systemkoeffizienten und nicht die Koeffizienten selber für die Pivotauswahl in Betracht ziehen. Ihren Ursprung hatten Criss-Cross-Verfahren bei der Untersuchung orientierter Matroiden.

Aufgabenbereich und Forschungsziele

Die einfachsten aller Pivotverfahren gehören zu den Criss-Cross-Verfahren, welche in den 80er-Jahren für Aufgabestellungen von orientierten Matroiden 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 entwickelt für das lineare Komplementaritätsproblem mit suffizienten Matrizen (einschließlich quadratischer Programmierung) und für linear-fraktionale Optimierungsprobleme.

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 Laufzeitschranken für allgemeine Pivotverfahren, und insbesondere für Criss-Cross-Verfahren, ein noch (2010) offenes Forschungsthema sind, beanspruchen die derzeit schon länger bekannten Simplexverfahren alle eine überpolynomial beschränkte Laufzeit, das ist eine Laufzeit, die sich nicht durch ein Polynom in der Datenspeichergröße beschränken lässt. Zusammenfassend lässt sich 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.

Besondere Criss-Cross-Verfahren

Das Kleinster-Index-Pivotverfahren ist das bekannteste aller Criss-Cross-Verfahren und 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 einer 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.

Das Häufigster-Index-Pivotverfahren (englisch most frequent index) wählt als seine beiden Pivotvariablen immer diejenige zulässige Variable, welche bis zu diesem Schritt am öftesten für einen Pivot ausgewählt wurde (bei gleicher Prio darf beliebig ausgewählt werden).

Das Criss-Cross-Verfahren mit Stackauswahl (englisch Last-In_First-Out, LIFO) wählt als seine beiden Pivotvariablen immer diejenige zulässige Variable, welche als letzte für einen Pivot ausgewählt wurde (gleiche Prio kann hier nicht vorkommen).

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, welche das Gleichungssystem

${\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 $z\,$ auf ein Maximum bringen. Wir benutzen dazu die oben angeführte Pivotauswahl des kleinsten Index.

In unserem Ausgangssystem sind sämtliche Pivots zulässig; 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 2mal anklicken und gedrückt halten)

Das führt zum neuen System

${\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 $(x_{2},\,x_{1})$, $(x_{2},\,x_{4})$ und $(x_{5},\,x_{2})$, $(x_{5},\,x_{3})$ zulässig; anhand der Auswahlregel legen wir $\,x_{2}\,$ an Stelle von $\,x_{1}\,$ frei:

Basis 1 zu Basis 2

Wir erhalten das System

${\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 zulässigen Pivots dieses Gleichungssystems sind $(x_{4},\,x_{1})$ und $(x_{4},\,x_{3})$; wir legen $\,x_{1}\,$ an Stelle von $\,x_{4}\,$ frei:

Basis 2 zu Basis 3

Nun erhalten wir

${\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 ist optimal, die entsprechenden Werte der Unbekannten 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$

Simplex-Verfahren

→ Hauptartikel: Simplex-Verfahren

Simplexverfahren waren die ersten Pivotverfahren für die Lineare Optimierung, und wurden 1947 von George Dantzig veröffentlicht und seitdem vielfach weiterentwickelt. Die Suche nach einer Pivotauswahl, welche sowohl durchschnittlich schnell und in Extremfällen auch sicher zum Ziel kommen soll, führte zu immer komplexeren Auswahlregeln, die in der Praxis nicht immer streng eingehalten werden, und wegen unvermeidlicher Rundungsfehler meist nicht streng eingehalten werden können.

Primale Simplexverfahren

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

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

Ein Standardergebnis der Linearen Optimierung besagt, dass für jede lösbare Aufgabe und für jede zulässige Basis eine Folge zulässiger 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.

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. 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.

Symmetrische Simplexverfahren

Symmetrische oder primal-duale Simplexverfahren suchen eine zulässige Lösung für das aus primalen und dualem System bestehendes Aufgabenpaar. Um beide Aufgaben auch effizient zu behandeln wird aber nur eine Datentabelle verwendet und die wechselseitige Beziehung dualer Aufgaben ausgenützt. Bei symmetrischen Simplexverfahren entfällt die Aufteilung in Phase 1 und Phase 2.

Weiterführende Hinweise

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.

Interaktives Applet

Robert Vanderbei's interaktives Pivotverfahren-Applet von 1997 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.