Pivotverfahren

Pivotverfahren, oder pivotbasierter Suchalgorithmus der Linearen Optimierung, nennt sich jeder Algorithmus, der für seine Suche ein lineares Gleichungssystem aufstellt und in jedem Schritt strategisch ausgewählte Variablen bezüglich der Restvariablen freilegt, wobei die aufeinanderfolgend freigelegten Variablensätze sich in nur einer Variable unterscheiden. Wichtige Pivotverfahren sind die verschiedenen Simplexverfahren ^[1] und die Criss-Cross-Verfahren^[2].

Pivotansatz

Jedes System linearer Ungleichungen und jedes Lineare Optimierungsproblem lässt sich in folgende, englisch dictionary genannte^[1] Grundform bringen:

$\begin{matrix} z & = & f_0 & + & d_1\,x_1 & + & \cdots & + & d_n\,x_n \\[3pt] x_{n+1} & = & b_1 & + & G_{11}\,x_1 & + & \cdots & + & G_{1n}\,x_n \\ \vdots & & \vdots & & \vdots & & & & \vdots \\ x_{n+m} & = & b_m & + & G_{m1}\,x_1 & + & \cdots & + & G_{mn}\,x_n \end{matrix}$

$\begin{matrix} x_1\ge0,\ \ldots\ x_{n+m}\ge0,\ \max~z \end{matrix}$

Diese Darstellung soll aussagen, dass eine Lösung in den Unbekannten $\,x_1, \ldots x_{n+m},\ z\,$ gesucht wird, welche die obige Gleichungen beziehungsweise Ungleichungen erfüllt und dabei die sogenannte Zielvariable $\,z$ so groß wie möglich wählt.

Falls nun die Optimalitätsbedingungen $\,b_1\ge0, \ldots, b_m\ge0\,$ und $\,d_1\le0, \ldots, d_n\le0\,$ erfüllt sind, 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_1, \ldots, x_{n+m}=b_m\,$ dann nichtnegativ, wie gefordert, zum anderen dürfen sonstige mögliche Lösungen nur unabhängige Variablen mit ebenfalls nichtnegativen Werten enthalten, sodass für jede dieser Lösungen die Ungleichung $\,z\le f_0\,$ gilt.

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 eine andere, gleichgroße Teilmenge $\,B\,$ der $\,n+m\,$ Unbekannten als sogenannte Basisvariablen definiert und diese freilegt. Es sei $x_{\pi(1)},\ldots x_{\pi(n+m)}$ eine neue Anordnung der Unbekannten $x_1,\ldots x_{n+m}$. Dann wählt man die Teilmenge

$\begin{matrix} B=\{x_{\pi(n+1)},\ldots x_{\pi(n+m)}\} \\[3pt] \end{matrix}$

der Unbekannten als Basis oder Menge der Basisvariablen aus und stellt folgendes neue System auf:

$\begin{matrix} z & = & f^B_0 & + & d^B_1\,x_{\pi(1)} & + & \cdots & + & d^B_n\,x_{\pi(n)} \\[3pt] x_{\pi(n+1)} & = & b^B_1 & + & G^B_{11}\,x_{\pi(1)} & + & \cdots & + & G^B_{1n}\,x_{\pi(n)} \\ \vdots & & \vdots & & \vdots & & & & \vdots \\ x_{\pi(n+m)} & = & b^B_m & + & G^B_{m1}\,x_{\pi(1)} & + & \cdots & + & G^B_{mn}\,x_{\pi(n)} \end{matrix}$

Die Koeffizienten des so abgewandelten Gleichungssystems lassen sich erneut auf die Optimumbedingungen $\,b^B_1\ge0, \ldots, b^B_m\ge0\,$ und $\,d^B_1\le0, \ldots, d^B_n\le0\,$ prüfen, 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.

Jedes nichtverschwindende $\,G^B_{kl}\ne0\,$ des obigen Gleichungssystems nennt sich Pivotelement, und erlaubt es, die unabhängige Variable $\,x_{\pi(l)}\,$ an Stelle der Basisvariablen $\,x_{\pi(n+k)}\,$ 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_{\pi(n+k)},\,x_{\pi(l)}\,)$, die folgendes erfüllen müssen:

• entweder gilt (a) gleichzeitig $\,b^B_k<0\,$ und $\,G^B_{kl}>0\,$,  oder es gilt (b) gleichzeitig $\,d^B_l>0\,$ und $\,G^B_{kl}<0\,$

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 und 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.^[3]

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 unendlich großem $z\,$ finden lassen (unbeschränkte Aufgabe).

Beispiel

In folgendem Beispiel sei $\,z = 0 + 0\,x_1 + 0\,x_2\,$. In diesem Falle wird keine der Variablen maximiert, sondern eine beliebige Lösung in den Unbekannten $\,x_1,\ldots\ x_5\,$ gesucht, die folgende Gleichungen und Ungleichungen erfüllen soll:

$\begin{matrix} x_3 & = &( &- ~4 &- ~7x_1 &+ ~2x_2 &)~/~1 \\[2pt] x_4 & = &( &- ~3 &- ~3x_1 &+ ~~x_2 &)~/~1 \\[2pt] x_5 & = &( &~~ ~9 &+ ~7x_1 &- ~3x_2 &)~/~1 \end{matrix}$

$\begin{matrix} x_1\ge0,\ x_2\ge0,\ x_3\ge0,\ x_4\ge0,\ x_5\ge0 \end{matrix}$

Um Rundungsfehler zu vermeiden, arbeiten wir im folgenden mit rationalen Zahlen und wählen einen gemeinsamen Nenner für sämtliche Einträge. In jedem Schritt wird der zulässige Pivot $(\pi(n+k),\,\pi(l))$ nach folgender Regel gewählt:

Wähle $\pi(n+k)=\min_i\{\pi(n+i)~|~b^B_i<0\}$ und danach $\pi(l)=\min_j\{\pi(j)~|~G^B_{kj}>0\}$.

Für den Fall von $\,z=0\,$ lässt sich beweisen,^[2] dass diese einfache (nicht besonders effiziente) Auswahlregel bei jeder lösbaren Aufgabe zu einer Optimalbasis führt.

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 und erhalten:

$\begin{matrix} x_2 & = &( &~~ ~4 &+ ~7x_1 &+ ~~x_3 &)~/~2 \\[2pt] x_4 & = &( &- ~2 &+ ~~x_1 &+ ~~x_3 &)~/~2 \\[2pt] x_5 & = &( &~~ ~6 &- ~7x_1 &- ~3x_3 &)~/~2 \end{matrix}$

Die zulässigen Pivots sind nun $(x_4,\,x_1)$ und $(x_4,\,x_3)$; wir legen $\,x_1\,$ an Stelle von $\,x_4\,$ 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 & = &( &- ~4 &- ~7x_4 &+ ~2x_3 &)~/~1 \end{matrix}$

Der einzige zulässige Pivot hier ist $(x_5,\,x_3)$; wir legen $\,x_3\,$ an Stelle von $\,x_5\,$ frei und erhalten:

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

Wir erhalten die Lösung:

$\begin{matrix} x_1=0,\ x_2=3,\ x_3=2,\ x_4=0,\ x_5=0 \end{matrix}$

Kreislaufanfällige Pivotwahl

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:

Wähle das erste $k\,$ mit $b^B_k=\min_i\{b^B_i\}$, und danach das erste $l\,$ mit  $G^B_{kl}>0\,$.

Wir starten mit dem System:

$\begin{matrix} x_3 & = &(& -~ 3 &-~ 3x_1 &+~ ~x_2 &)~/~1 \\[2pt] x_4 & = &(& -~ 4 &-~ 7x_1 &+~ \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\ge0,\ x_2\ge0,\ x_3\ge0,\ x_4\ge0,\ x_5\ge0,\ x_6\ge0 \end{matrix}$

Wir wählen $\,x_4\,$ und legt an Stelle dessen $\,x_2\,$ frei (nach der kreissicheren Regel im vorherigen Beispiel hätte man $\,x_3\,$ und $\,x_2\,$ gewählt). Wir erhalten das System:

$\begin{matrix} x_3 & = &(& -~ 2 &+~ ~\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 & = &(& -~ 4 &-~ 7x_3 &+~ \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 zwei Schritte, nach sechs Schritten wiederholen sich die Gleichungen des Systems in umgestellter Form, und nach insgesamt zwölf Schritten wiederholt sich das Startsystem genau, mit den Gleichungen und Unbekannten am ursprünglichen Ort. Das Gesamtsystem von Gleichungen und Ungleichungen hat in Wirklichkeit keine Lösung, doch kann das Pivotverfahren mit der obigen Pivotwahl das nicht herausfinden.

Dualität

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_0 & - & b_1\,y_{n+1} & - & \cdots & - & b_m\,y_{n+m} \\[3pt] y_1 & = & -d_1 & - & G_{11}\,y_{n+1} & - & \cdots & - & G_{m1}\,y_{n+m} \\ \vdots & & \vdots & & \vdots & & & & \vdots \\ y_n & = & -d_n & - & G_{1n}\,y_{n+1} & - & \cdots & - & G_{mn}\,y_{n+m} \end{matrix}$

$\begin{matrix} y_1\ge0,\ \ldots\ y_{m+n}\ge0,\ \max~w \end{matrix}$

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

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:

$\begin{matrix} B=\{y_{\pi(1)},\ldots y_{\pi(n)}\}\subset\{y_1,\ldots y_{n+m}\} \\[3pt] \end{matrix}$

$\begin{matrix} w & = & -f^B_0 & - & b^B_1\,y_{\pi(n+1)} & - & \cdots & - & b^B_m\,y_{\pi(n+m)} \\[3pt] y_{\pi(1)} & = & -d^B_1 & - & G^B_{11}\,y_{\pi(n+1)} & - & \cdots & - & G^B_{m1}\,y_{\pi(n+m)} \\ \vdots & & \vdots & & \vdots & & & & \vdots \\ y_{\pi(n)} & = & -d^B_n & - & G^B_{1n}\,y_{\pi(n+1)} & - & \cdots & - & G^B_{mn}\,y_{\pi(n+m)} \end{matrix}$

Daraus folgt, dass jede Optimalbasis der ursprünglichen Aufgabe auch unmittelbar eine Optimalbasis für die duale Aufgabe liefert.

Die Dualitätsbeziehung lässt sich am leichtesten an einem Pivotsystem betrachten, das ausschließlich zwei unabhängige Unbekannte und zwei freigelegte Unbekannte enthält. Man erhält dasselbe System, wenn man zuerst zwei der Unbekannten austauscht und danach die duale Aufgabe herleitet oder wenn man diese Schritte in umgekehrter Reihenfolge tut:

$\begin{matrix} x_i &\!=\!& (~~\alpha) &\!\!\!x_j &\!+\!& (~~\sigma) &\!\!\!x_s \\[6pt] x_r &\!=\!& (~~\zeta) &\!\!\!x_j &\!+\!& (~~\pi) &\!\!\!x_s \end{matrix}$	${x_r\leftrightarrow x_s}$	$\begin{matrix} x_i &\!=\!& (~~{\scriptstyle\alpha}-\frac{\zeta\sigma}{\pi}) &\!\!\!x_j &\!+\!\!& (~~\frac{\sigma}{\pi}) &\!\!\!x_r \\[6pt] x_s &\!=\!& (~~~-\frac{\zeta}{\pi}~) &\!\!\!x_j &\!+\!\!& (~~\frac{1}{\pi}) &\!\!\!x_r \\ \end{matrix}$
$-\,[\cdots]^{\,T}$		$-\,[\cdots]^{\,T}$
$\begin{matrix} y_j &\!=\!& (-\alpha) &\!\!\!y_i &\!+\!& (-\zeta) &\!\!\!y_r \\[6pt] y_s &\!=\!& (-\sigma) &\!\!\!y_i &\!+\!& (-\pi) &\!\!\!y_r \\ \end{matrix}$	${y_s\leftrightarrow y_r}$	$\begin{matrix} y_j &\!=\!& (-{\scriptstyle\alpha}+\frac{\zeta\sigma}{\pi}) &\!\!\!y_i &\!+\!\!& (~~\frac{\zeta}{\pi}) &\!\!\!y_s \\[6pt] y_r &\!=\!& (~~~~-\frac{\sigma}{\pi}~) &\!\!\!y_i &\!+\!\!& (-\frac{1}{\pi}) &\!\!\!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 $\pi\,$ steht für das Pivotelement, $\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 &+ ~4y_3 &+ ~3y_4 &- ~9y_5 &)~/~1 \\[2pt] y_1 & = &( & 0 &+ ~7y_3 &+ ~3y_4 &- ~7y_5 &)~/~1 \\[2pt] y_2 & = &( & 0 &- ~2y_3 &- ~~y_4 &+ ~3y_5 &)~/~1 \end{matrix}$

$\begin{matrix} y_1\ge0,\ y_2\ge0,\ y_3\ge0,\ y_4\ge0,\ y_5\ge0,\ \max~w \end{matrix}$

Bei der ursprünglichen Aufgabe hatten wir $\,x_2\,$ an Stelle von $\,x_3\,$ freigelegt. Wenn man im dualen Gleichungssystem $\,y_3\,$ an Stelle von $\,y_2\,$ freilegt, erhält man:

$\begin{matrix} ~w~ & = &( & 0 &- ~4y_2 &+ ~2y_4 &- ~6y_5 &)~/~2 \\[2pt] y_1 & = &( & 0 &- ~7y_2 &- ~~y_4 &+ ~7y_5 &)~/~2 \\[2pt] y_3 & = &( & 0 &- ~~y_2 &- ~~y_4 &+ ~3y_5 &)~/~2 \end{matrix}$

Wenn man nun $\,y_4\,$ an Stelle von $\,y_1\,$ freilegt, erhält man:

$\begin{matrix} ~w~ & = &( & 0 &- ~9y_2 &- ~2y_1 &+ ~4y_5 &)~/~1 \\[2pt] y_4 & = &( & 0 &- ~7y_2 &- ~2y_1 &+ ~7y_5 &)~/~1 \\[2pt] y_3 & = &( & 0 &+ ~3y_2 &+ ~~y_1 &- ~2y_5 &)~/~1 \end{matrix}$

Wenn man $\,y_5\,$ an Stelle von $\,y_3\,$ freilegt, erhält man:

$\begin{matrix} ~w~ & = &( & 0 &- ~6y_2 &+ ~0y_1 &- ~4y_3 &)~/~2 \\[2pt] y_4 & = &( & 0 &+ ~7y_2 &+ ~3y_1 &- ~7y_3 &)~/~2 \\[2pt] y_5 & = &( & 0 &+ ~3y_2 &+ ~~y_1 &- ~~y_3 &)~/~2 \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.

Besondere Pivotverfahren

Simplexverfahren (auch Primale Simplexverfahren genannt) waren die ersten Pivotverfahren für die Lineare Optimierung und wurden 1947 von George Dantzig veröffentlicht. Diese Pivotverfahren gehen von einer sogenannten zulässigen Basis mit $\,b_1\ge0, \ldots, b_m\ge0\,$ 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_0^B\,$, 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 wie folgt wählen:

1. Wähle ein beliebiges $\pi(s)\,$, welches $d^B_s>0$ erfüllt. Zum Beispiel (Bland ^[1]), suche das kleinste $\pi(s)\,$ mit dieser Eigenschaft.
2. Wähle ein beliebiges $\pi(n+r)\,$, welches $b^B_r/(-G^B_{rs})=\min_i\{b^B_i/(-G^B_{is})~|~G^B_{is}<0\}$ erfüllt. Zum Beispiel (Bland), suche das kleinste $\pi(n+r)\,$ 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 sind Pivotverfahren, die von einer sogenannten dual-zulässigen Basis mit $\,d_1\le0, \ldots, d_n\le0\,$ 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 gute dual-zulässige Ausgangsbasis zu finden.

Criss-Cross-Verfahren (englisch: kreuz und quer) sind allgemeine Pivotverfahren, die von einer beliebigen Basis ausgehen. Ein wichtiger Ansatz bei der Pivotauswahl in den Criss-Cross-Verfahren besteht darin, die Unbekannten in einer mehr oder weniger festen Reihenfolge anzuordnen. Das einfachste aller Criss-Cross-Verfahren verwendet folgende Kleinster-Index-Pivotauswahl^[2] (wie üblich, ist das Minimum einer leeren Menge unendlich groß):

1. Suche $\pi(n+r)=\min_i\{\pi(n+i)~|~b^B_i<0\}$   und   $\pi(s)=\min_j\{\pi(j)~|~d^B_j>0\}$.
2. Falls $\pi(n+r)<\pi(s)\,$ ist, wähle Pivot $(x_{\pi(n+r)},\,x_{\pi(l)})$ mit $\pi(l)=\min_j\{\pi(j)~|~G^B_{rj}>0\}$.
3. Falls $\pi(s)<\pi(n+r)\,$ ist, wähle Pivot $(x_{\pi(n+k)},\,x_{\pi(s)})$ mit $\pi(n+k)=\min_i\{\pi(n+i)~|~G^B_{is}<0\}$.

Die Veränderlichen dürfen beliebig geordnet werden, sollen aber die Anfangsordnung beibehalten.

Während die bekannten Simplexverfahren alle eine überpolynomial beschränkte Laufzeit beanspruchen, sind Laufzeitschranken für die Criss-Cross-Verfahren ein noch (2004) offenes Forschungsthema.^[3][4]

Einzelnachweise

1. ↑ ^{a b c} z. B. in: Vašek Chvátal: Linear Programming. W. H. Freeman and Company, New York, 1983, ISBN 0-716-71587-2
2. ↑ ^{a b c} Komei Fukuda & Tamás Terlaky (1997): Criss-Cross Methods: A Fresh View on Pivot Algorithms
3. ↑ ^{a b} Komei Fukuda & Tamás Terlaky (1999): On the Existence of a Short Admissible Pivot Sequences for Feasibility and Linear Optimization Problems
4. ↑ Komei Fukuda & Bohdan Kaluzny (2004): The criss-cross method can take Ω(n^d) pivots