Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


43. Lineare Programmierung



Die Simplexmethode

Die Simplexmethode ist die üblicherweise verwendete Bezeichnung zur Beschreibung eines allgemeinen Ansatzes für die Lösung linearer Optimierungsaufgaben unter Anwendung des Pivotierens, der gleichen grundlegenden Operation, die beim Gaußschen Eliminationsverfahren benutzt wurde. Es erweist sich, daß das Pivotieren in natürlicher Weise der geometrischen Operation der Bewegung von einem Eckpunkt des Simplex zum anderen bei der Suche nach der Lösung entspricht. Die verschiedenen Algorithmen, die gewöhnlich angewandt werden, unterscheiden sich in wesentlichen Details, die mit der Reihenfolge zusammenhängen, in der die Eckpunkte des Simplex durchsucht werden. Das heißt, daß der gut bekannte »Algorithmus« für dieses Problem exakter als eine generische Methode beschrieben werden kann, die sich auf mehrere verschiedene Weisen verbessern läßt. Diese Situation lag schon früher hin und wieder vor, zum Beispiel beim Gaußschen Eliminationsverfahren (Kapitel 37) oder beim Algorithmus von Ford-Fulkerson (Kapitel 33).

Zunächst einmal ist klar, daß lineare Optimierungsaufgaben in vielen verschiedenen Formen vorliegen können. Zum Beispiel enthält die obige lineare Optimierungsaufgabe für das Problem des Flusses in einem Netzwerk sowohl Gleichungen als auch Ungleichungen, während in den obigen geometrischen Beispielen nur Ungleichungen auftreten. Es ist zweckmäßig, die Anzahl der Möglichkeiten etwas zu verringern, indem man fordert, daß alle linearen Optimierungsaufgaben in der gleichen Standardform formuliert werden müssen. Bei dieser sind alle Beziehungen Gleichungen, mit Ausnahme von je einer Ungleichung für jede Variable, die aussagt, daß sie nichtnegativ ist. Dies mag zunächst als eine starke Einschränkung erscheinen, doch in Wirklichkeit ist es nicht schwer, allgemeine lineare Optimierungsaufgaben in diese Standardform umzuwandeln. Die folgende lineare Optimierungsaufgabe ist die Standardform für das in Abbildung 43.2 angegebene dreidimensionale Beispiel:

Maximiere x1 + x2 + x3
unter Berücksichtigung der Nebenbedingungen

-x1 + x2 + y1 = 5
x1 + 4x2 + y2 = 45
2x1 + x2 + y3 = 27
3x1 - 4x2 + y4 = 24
x3 + x5 = 4
x1, x2, x3, y1, y2, y3, y4, y5 >= 0.

Jede Ungleichung, in der mehr als eine Variable auftritt, wird durch Aufnahme einer neuen Variablen in eine Gleichung umgewandelt. Die Variablen y werden Schlupfvariable genannt, da sie den Spielraum (Schlupf) ausdrücken, den die Ungleichung gestattet. Jede Ungleichung, die nur eine Variable enthält, kann durch einfaches Umbenennen der Variablen in die standardmäßige Nichtnegativitätsbedingung umgewandelt werden. Zum Beispiel könnte eine Nebenbedingung von der Art x3 <= -1 behandelt werden, indem x3 überall dort, wo es auftritt, durch -1 - x'3 ersetzt wird.

Um die folgenden Rechnungen etwas übersichtlicher zu halten, haben wir - abweichend von dieser Regel - für die Ungleichung x3 <= 4 die Variable x3 nicht durch x3' mit der Bedeutung -x3 - 4 substituiert, sondern eine zusätzliche Variable y5 eingeführt.

Diese Formulierung macht die Parallelen zwischen linearer Programmierung und Gleichungssystemen deutlich. Es liegen N Gleichungen mit M unbekannten Variablen vor, die alle positiv sein müssen. Beachten Sie, daß in diesem Falle N Schlupfvariablen vorhanden sind, eine für jede Gleichung (da ursprünglich nur Ungleichungen vorlagen). Wir setzen voraus, daß M > N ist, was zur Folge hat, daß viele Lösungen des Gleichungsystems existieren; das Problem besteht darin, diejenige zu finden, die die Zielfunktion maximiert.

In unserem Beispiel existiert eine triviale Lösung des Gleichungssystems: Man setze x1 = x2 = x3 = 0 und weise dann den Schlupfvariablen geeignete Werte zu, so daß die Gleichungen erfüllt werden. Dies ist möglich, da in diesem Beispiel (0, 0, 0) ein Punkt des Simplex ist. Obwohl dies im allgemeinen nicht so sein muß, wollen wir uns bei der Erläuterung der Simplexmethode einstweilen auf die Betrachtung linearer Optimierungsaufgaben beschränken, für die bekannt ist, daß dieser Fall gilt. Dies ist immer noch eine sehr umfangreiche Klasse linearer Optimierungsaufgaben; wenn zum Beispiel alle Zahlen auf der rechten Seite der Gleichungen in der Standardform der linearen Optimierungsaufgabe positiv sind und alle Schlupfvariablen positive Koeffizienten besitzen (d.h. wie in unserem Beispiel nur als positive Summanden in Erscheinung treten), so existiert in jedem Falle eine Lösung, bei der alle ursprünglichen Variablen den Wert null haben. Wir werden später zum allgemeinen Fall zurückkehren.

Wenn eine Lösung gegeben ist, bei der M - N Variablen den Wert null haben, erweist es sich, daß wir eine andere Lösung mit der gleichen Eigenschaft finden können, indem wir eine uns bekannte Operation ausführen, das Pivotieren. Im wesentlichen ist dies die gleiche Operation wie beim Gaußschen Eliminationsverfahren: In der durch die Gleichungen definierten Koeffizientenmatrix wird ein Element a[p,q] ausgewählt; dann wird die p-te Zeile so mit einer geeigneten Konstanten multipliziert und zu allen anderen Zeilen addiert, daß in der q-ten Spalte überall Nullen erzeugt werden, mit Ausnahme des Elements in der p-ten Zeile, das den Wert 1 erhält. Wir betrachten die folgende Matrix, die die oben angegebene lineare Optimierungsaufgabe darstellt:

Formel

Diese Matrix der Dimension (N + 1) x (M + 1) enthält die Koeffizienten der linearen Optimierungsaufgabe in der Standardform, wobei die (M + 1)-te Spalte die Werte der rechten Seiten der Gleichungen (wie beim Gaußschen Eliminationsverfahren) und die 0-te Zeile die Koeffizienten der Zielfunktion mit umgekehrtem Vorzeichen enthält. Die Bedeutung der 0-ten Zeile wird weiter unten erläutert; einstweilen werden wir sie genau wie jede andere Zeile behandeln.

Für unser Beispiel führen wir alle Berechnungen auf zwei Dezimalstellen genau aus. Dabei werden offensichtlich Aspekte wie die Rechengenauigkeit und die kumulierten Fehler vernachlässigt, die hier ebenso wichtig sind wie im Falle des Gaußschen Eliminationsverfahrens.

Die Variablen, die einer Lösung entsprechen, werden Basisvariablen genannt, und die, die für die Lösung gleich 0 gesetzt werden, heißen Nicht-Basisvariablen. In der Matrix enthalten die Spalten, die Basisvariablen entsprechen, genau eine Eins und ansonsten nur Nullen, während Nicht-Basisvariablen Spalten entsprechen, in denen mehr als ein Element von null verschieden ist.

Nehmen wir nun an, daß wir diese Matrix für p = 4 und q = 1 pivotieren möchten. Das heißt, daß ein geeignetes Vielfaches der vierten Zeile zu jeder anderen Zeile addiert wird, so daß in der ersten Spalte überall Nullen erzeugt werden, mit Ausnahme einer 1 in der vierten Zeile. Dies führt zu dem folgenden Ergebnis:

Formel

Diese Operation bewirkt das Entfernen der siebenten Spalte aus der Basis und die Aufnahme der ersten Spalte in die Basis. Es wird genau eine Basisspalte entfernt, da genau eine Basisspalte eine 1 in der Zeile p enthält.

Per Definition können wir eine Lösung der linearen Optimierungsaufgabe erhalten, indem wir alle Nicht-Basisvariablen gleich null setzen und dann die in der Basis angegebene triviale Lösung benutzen. In der Lösung, die der obigen Matrix entspricht, haben sowohl x2 als auch x3 den Wert null, da sie Nicht-Basisvariablen sind, und es ist x1 = 8, so daß die Matrix dem Punkt (8, 0, 0) des Simplex entspricht. (Die Werte der Schlupfvariablen sind für uns uninteressant.) Beachten Sie, daß die rechte obere Ecke der Matrix (Zeile 0, Spalte M + 1) den Wert der Zielfunktion in diesem Punkt enthält. Wie wir bald sehen werden, ist dies durch den Aufbau des Verfahrens bedingt.

Nehmen wir nun an, daß wir die Pivot-Operation für p = 3 und q = 2 ausführen:

Formel

Dadurch wird die Spalte 6 aus der Basis entfernt und die Spalte 2 aufgenommen. Indem wir Nicht-Basisvariablen gleich null setzen und wie zuvor nach Basisvariablen auflösen, sehen wir, daß diese Matrix dem Punkt (12, 3, 0) des Simplex entspricht, für den die Zielfunktion den Wert 15 hat. Wir bemerken, daß der Zielfunktionswert stetig wächst. Wie wir bald sehen werden, ist auch das durch das Verfahren bedingt.

Wie entscheiden wir, welche Werte von p und q für das Pivotieren zu verwenden sind? An dieser Stelle kommt die Zeile 0 ins Spiel. Für jede Nicht-Basisvariablen enthält die Zeile 0 den Betrag mit umgekehrtem Vorzeichen, um den sich der Zielfunktionswert erhöhen würde, wenn diese Variable von 0 nach 1 geändert würde. (Das Vorzeichen ist umgekehrt, damit die Zeile 0 bei der standardmäßigen Pivot-Operation unverändert erhalten bleibt.) Ein Pivotieren unter Verwendung der Spalte q entspricht der Änderung des Wertes der entsprechenden Variablen von 0 in einen gewissen positiven Wert, so daß wir sicher sein können, daß sich der Zielfunktionswert erhöht, wenn wir irgendeine Spalte mit einem negativen Element in Zeile 0 verwenden.

Nun bewirkt zwar das Pivotieren mit Hilfe einer beliebigen Zeile mit einem positiven Element in dieser Spalte eine Erhöhung des Zielfunktionswerts, doch wir müssen auch sicherstellen, daß dadurch eine Matrix erzeugt wird, die einem Punkt des Simplex entspricht. Dabei besteht die Hauptschwierigkeit darin, daß eines der Elemente in der Spalte M + 1 negativ werden könnte. Dies kann verhindert werden, indem unter den positiven Elementen in der Spalte q (ausgenommen Zeile 0) dasjenige bestimmt wird, das den kleinsten Wert ergibt, wenn es durch das (M + 1)-te Element in der gleichen Zeile dividiert wird. Wenn wir als p die Nummer der Zeile wählen, die dieses Element enthält, und pivotieren, können wir sicher sein, daß sich der Zielfunktionswert erhöht, und daß keines der Elemente in der Spalte M + 1 negativ wird; damit ist gewährleistet, daß die sich ergebende Matrix einem Punkt des Simplex entspricht.

Bei dieser Methode zur Bestimmung der Pivotzeile können zwei Schwierigkeiten auftreten. Erstens, was ist zu tun, wenn die q-te Spalte keine positiven Elemente enthält? Dies ist eine widersprüchliche Situation: Das negative Element in Zeile 0 besagt, daß der Zielfunktionswert erhöht werden kann, doch es gibt keine Möglichkeit, ihn zu erhöhen. Es erweist sich, daß diese Situation dann und nur dann eintritt, wenn der Simplex unbeschränkt ist, so daß der Algorithmus abbrechen und das Problem melden kann. Eine ernstere Schwierigkeit tritt in dem entarteten Fall auf, wenn das (M + 1)-te Element in einer bestimmten Zeile (mit einem positiven Element in der Spalte q) den Wert 0 hat. Dann wird diese Zeile ausgewählt, doch der Zielfunktionswert erhöht sich um 0. An und für sich ist das keine Schwierigkeit; die Komplikation tritt dann auf, wenn zwei solcher Zeilen vorhanden sind. Verschiedene natürliche Strategien für die Auswahl zwischen solchen Zeilen führen zu einem Zyklus: einer unendlichen Folge von Pivot-Operationen, die den Zielfunktionswert nicht erhöhen. Wir haben solche Schwierigkeiten wie das Auftreten von Zyklen in unserem Beispiel vermieden, um die Beschreibung der Methode übersichtlich zu gestalten, doch es muß betont werden, daß solche entarteten Fälle in der Praxis recht häufig eintreten können. Die Vielseitigkeit, die bei linearer Programmierung gewährleistet ist, hat zur Folge, daß entartete Fälle des allgemeinen Problems bei der Lösung spezieller Probleme auftreten können.

Um das Auftreten von Zyklen zu vermeiden, stehen mehrere Möglichkeiten zur Verfügung. Eine Methode besteht darin, beim Auftreten gleicher Werte zufällige Unterbrechungen vorzusehen. Dadurch wird das Auftreten von Zyklen äußerst unwahrscheinlich (allerdings nicht mathematisch unmöglich). Eine andere Strategie, die Zyklen verhindert, wird nachfolgend beschrieben.

In unserem Beispiel können wir erneut mit q = 3 (wegen des Wertes -1 in Zeile 0 und Spalte 3) und p = 5 (da 1 der einzige positive Wert in der Spalte 3 ist) pivotieren. Dies ergibt die folgende Matrix:

Formel

Dies entspricht dem Punkt (12, 3, 4) des Simplex, für den der Zielfunktionswert 19 beträgt.

Im allgemeinen Fall können in der Zeile 0 mehrere negative Elemente enthalten sein, und es wurden mehrere unterschiedliche Strategien für die Auswahl unter ihnen vorgeschlagen. Wir sind nach einer der am weitesten verbreiteten Methoden vorgegangen, der Methode des größten Zuwachses: Man wähle immer die Spalte mit dem kleinsten (also betragsmäßig größten) Wert in der Zeile 0. Dies führt nicht notwendigerweise zu dem größten Zuwachs beim Zielfunktionswert, da entsprechend der ausgewählten Zeile p noch eine Multiplikation mit einer Konstanten ausgeführt werden muß. Falls diese Spaltenauswahlstrategie mit der Zeilenauswahlstrategie (die darin besteht, im Falle des Auftretens gleicher Werte diejenige Zeile zu verwenden, die das Entfernen der Spalte mit der kleinsten Nummer aus der Basis bewirkt) kombiniert wird, so ist kein Auftreten von Zyklen möglich. (Diese Strategie der Verhinderung von Zyklen stammt von R. G. Bland.) Eine andere Möglichkeit für die Auswahl der Spalte ist, für jede Spalte den Betrag, um den sich der Zielfunktionswert erhöhen würde, tatsächlich zu berechnen, und dann diejenige Spalte zu benutzen, die das größte Ergebnis liefert. Dies wird die Methode des steilsten Abstiegs genannt. Noch eine andere interessante Möglichkeit besteht darin, unter den zur Wahl stehenden Spalten zufällig zu wählen.

Schließlich gelangen wir nach einer weiteren Pivot-Operation für p = 2 und q = 7 zu der Lösung:

Formel

Dies entspricht dem Punkt (9, 9, 4) des Simplex, für den der maximale Zielfunktionswert 22 erreicht wird. Alle Elemente in Zeile 0 sind nichtnegativ, so daß jedes Pivotieren nur dazu führen würde, daß sich der Zielfunktionswert wieder verkleinert.

Das obige Beispiel illustriert die Simplexmethode für die Lösung linearer Optimierungsaufgaben. Kurz gesagt, wenn wir mit einer Koeffizientenmatrix beginnen, die einem Eckpunkt des Simplex entspricht, können wir eine Reihe von Pivot-Schritten ausführen, die zu benachbarten Eckpunkten des Simplex führen, wobei der Zielfunktionswert jedesmal erhöht wird, bis das Maximum erreicht wird.

Eine grundlegende Tatsache, die noch nicht erwähnt wurde, ist für die einwandfreie Arbeitsweise dieses Verfahrens entscheidend: Sobald wir einen Punkt erreichen, in dem keine einzige Pivot-Operation eine Verbesserung des Zielfunktionswerts bewirken kann (ein »lokales« Maximum), haben wir das »globale« Maximum erreicht. Dies ist die Grundlage für den Simplex-Algorithmus. Wie bereits erwähnt wurde, würde der zugehörige Beweis (und der vieler anderer Tatsachen, die aufgrund der geometrischen Interpretation offensichtlich zu sein scheinen) im allgemeinen Fall weit über den Rahmen dieses Buches hinausgehen. Doch der Simplex-Algorithmus läuft für den allgemeinen Fall im wesentlichen genauso ab wie für das oben betrachtete einfache Problem.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]