Pivotverfahren

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 Simplex-Verfahren 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 in 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:

Hier sind reelle Zahlen (in der Praxis meist Bruchzahlen). Die obige Notation soll aussagen, dass eine Lösung in den Unbekannten gesucht wird, welche die entsprechenden Gleichungen und Ungleichungen erfüllt und dabei die sogenannte Zielvariable 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

wird umgeformt in

mit  )

Mit Hilfe der Indexmengen

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

In jedem Schritt eines Pivotverfahrens ist wie oben eine Teilmenge der Variablen als unabhängig hervorgehoben, während die restlichen Variablen, Basisvariablen genannt, als linear-affine 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 die beiden folgenden Optimumbedingungen erfüllt sind,   für alle      (Zulässigkeit)   und   für alle      (Zielbeschränkung), dann kann man eine Lösung für die obige Aufgabe erhalten, indem man die unabhängigen Variablen auf die Werte setzt. Zum einen sind die Werte der freigelegten Variablen 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 gilt.

( Im folgenden Beispielsystem,

werden die Optimumbedingungen an zwei Stellen verletzt, da und ist. Zum ersten würde die Versuchslösung den negativen Wert enthalten, und zum zweiten könnte dessen Zielvariablenwert bei Lösungen mit 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 eine andere, gleich große Teilmenge der Unbekannten auswählt und diese freilegt. Es sei     eine Umstellung der Indizes. Anhand folgender Aufteilung der Variablen,

in neue unabhängige Variablen mit und neue Basisvariablen mit , wird das Gleichungssystem nun umgewandelt zu

wobei zu beachten ist, dass Einträge wie nur für Indexpaare mit und definiert sind. Die Einträge des so umgewandelten Gleichungssystems lassen sich nun erneut auf die Optimumbedingungen überprüfen,   für alle      (Zulässigkeit)   und   für alle      (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 des obigen Gleichungssystems, dem Pivotsystem, nennt sich Pivotelement und erlaubt es, die unabhängige Variable an Stelle der Basisvariablen 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 , die Folgendes erfüllen müssen:

Entweder gilt gleichzeitig und    (Zulässigkeitspivot), oder es gilt gleichzeitig und    (Zielfortschrittspivot).

( Im obigen Beispielsystem,

sind wegen der Optimalitätsverletzung Pivotelement mit Pivot und Pivotelement mit Pivot erlaubt. Wegen der Optimalitätsverletzung sind aber ebenfalls Pivotelement mit Pivot , und Pivotelement mit Pivot 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 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 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 finden lassen (unbeschränkte Aufgabe).

Rundungsfehlerfreie Umsetzung Um Rundungsfehler zu vermeiden, kann mit Bruchzahlen und gemeinsamen Nenner für sämtliche Einträge gearbeitet werden. 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 der Pivotsysteme von einem Schritt auf den nächsten verändern:

Das Zeichen steht hier für den gemeinsamen Nenner des Gleichungssystems, das Zeichen für den Zähler des Pivotelements, für einen sonstigen Eintrag der Pivotzeile, für einen sonstigen Eintrag der Pivotspalte, und für einen beliebigen Eintrag abseits von Pivotzeile und Pivotspalte. Einträge der Zielbeitragszeile () und der Basiswertspalte () werden nach denselben Regeln umgewandelt.

Beispiele Zur grafischen Darstellung 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 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 . In so einem Fall wird keine der Variablen maximiert; es werden nur beliebige (nichtnegative) Werte für die Unbekannten gesucht, die ein vorgegebenes Gleichungssystem erfüllen. In jedem Schritt wollen wir dann den erlaubten Pivot nach folgender Regel wählen:

Wähle , danach wähle .

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

Wir suchen nun Werte für die Unbekannten , die das Gleichungssystem

erfüllen. Die erlaubten Pivots im obigen Gleichungssystem sind und ; aufgrund der obigen Auswahlregel legen wir die unabhängige Variable an Stelle der Basisvariablen frei:

mini|ohne|x360px|alt=Skalierbare animierte Darstellung eines Pivotverfahren-Schrittes|Basis 0 zu Basis 1 (animiertes SVG, nach Öffnung erneut anklicken und gedrückt halten; funktioniert nicht in allen Browsern)

Wir erhalten nun das folgende, umgewandelte Gleichungssystem:

Im neuen System sind die erlaubten Pivots und ; dieses Mal legen wir legen wir an Stelle von frei:

mini|ohne|x360px|alt=Skalierbare animierte Darstellung eines Pivotverfahren-Schrittes|Basis 1 zu Basis 2 (animiertes SVG, nach Öffnung erneut anklicken und gedrückt halten; funktioniert nicht in allen Browsern)

Wir erhalten nun das folgende System:

Der einzige erlaubte Pivot hier ist ; deshalb können wir nur an Stelle von freilegen:

mini|ohne|x360px|alt=Skalierbare animierte Darstellung eines Pivotverfahren-Schrittes|Basis 2 zu Basis 3 (animiertes SVG, nach Öffnung erneut anklicken und gedrückt halten; funktioniert nicht in allen Browsern)

Nun erhalten wir

Dieses System erfüllt die Optimalitätsbedingungen und hat dementsprechend auch keine erlaubten Pivots. Indem wir sämtliche unabhängige Variablen auf Null setzen, erhalten wir die folgende Lösung:

Kreislaufanfällige Pivotauswahlregel 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 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: Wähle ,

danach wähle .

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

Wir wählen hier und legen an Stelle dessen frei. Dadurch erhalten wir das System:

Wir wählen Basisvariable , legen an deren Stelle frei, und erhalten:

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 um an deren Stelle freizulegen erhalten wir:

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