Robert Sedgewick: Algorithmen

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


43. Lineare Programmierung



Implementation

Die Implementation der Simplexmethode für den oben beschriebenen Fall ergibt sich unmittelbar aus der Beschreibung. Zunächst ist das Programm für die erforderliche Prozedur des Pivotierens ähnlich zu unserer Implementation des Gaußschen Eliminationsverfahrens in Kapitel 37:

    procedure pivot(p,q: integer);
      var j,k: integer;
      begin
      for j:=0 to N do
        for k:=M+1 downto 1 do
          if (j<>p) and (k<>q) then
            a[j,k]:=a[j,k]-a[p,k]*a[j,q]/a[p,q];
      for j:=0 to N do if j<>p then a[j,q]:=0;
      for k:=1 to M+1 do if k<>q then a[p,k]:=a[p,k]/a[p,q];
      a[p,q]:=1
      end;

Dieses Programm realisiert die Addition derartiger Vielfacher von Zeile p zu jeder Zeile, daß in der Spalte q überall Nullen erzeugt werden, mit Ausnahme einer 1 in der Zeile p. Wie in Kapitel 37 ist es erforderlich, darauf zu achten, daß der Wert von a[p,q] nicht verändert wird, solange wir ihn noch verwenden.

Beim Gaußschen Eliminationsverfahren verarbeiteten wir bei der Vorwärts-Elimination nur Zeilen unterhalb von p in der Matrix, und bei der Anwendung des Gauß-Jordan-Verfahrens während des Rückwärts-Einsetzens nur Zeilen oberhalb von p. Ein System aus N linearen Gleichungen mit N Unbekannten könnte gelöst werden, indem pivot(i,i) für i von 1 bis N und dann nochmals rückwärts bis 1 aufgerufen wird.

Der Simplex-Algorithmus besteht dann einfach darin, die Werte von p und q in der oben beschriebenen Weise zu ermitteln und pivot aufzurufen, wobei dieser Prozeß so lange zu wiederholen ist, bis das Optimum erreicht ist oder ermittelt worden ist, daß das Simplex unbeschränkt ist:

    repeat
      q:=0; repeat q:=q+1 until (q=M+1) or (a[0,q]<0);
      p:=0; repeat p:=p+1 until (p=N+1) or (a[p,q]>0);
      for i:=p+1 to N do
        if a[i,q]>0 then
          if (a[i,M+1]/a[i,q])<(a[p,M+1]/a[p,q]) then p:=i;
      if (q<M+1) and (p<N+1) then pivot(p,q)
    until (q=M+1) or (p=N+1);

Falls das Programm mit q = M + 1 abbricht, wurde eine optimale Lösung gefunden; der erreichte Zielfunktionswert wird durch a [0,M + 1] angegeben, und die Werte der Variablen können aus der Basis entnommen werden. Falls das Programm mit p = N + 1 abbricht, so ist eine unbeschränkte Situation ermittelt worden.

Die Frage der Vermeidung von Zyklen wird in diesem Programm nicht berücksichtigt. Um die Methode von Bland zu implementieren, ist es erforderlich, die Spalte zu registrieren, die die Basis verlassen würde, wenn ein Pivotieren unter Benutzung von Zeile p vorgenommen würde. Dies ist leicht möglich, indem nach jedem Pivotieren outb[p]:=q gesetzt wird. Danach kann die Schleife zur Berechnung von p dergestalt modifiziert werden, daß auch dann p:=i gesetzt wird, wenn bei dem Vergleich der Quotienten Gleichheit gilt und außerdem outb[p] < outb[q] ist. Eine andere Möglichkeit wäre, ein zufälliges Element auszuwählen, indem eine zufällige ganze Zahl x erzeugt wird und jede Bezugnahme auf das Feld a[p,q] (oder a[i,q]) durch a[(p+x) mod (N+1),q] (oder a[(i+x) mod (N+1),q]) ersetzt wird. Dies hat zur Folge, daß die Spalte q in der gleichen Weise wie zuvor durchsucht wird, wobei jedoch statt am Anfang an einem zufälligen Punkt begonnen wird. Die gleiche Methode könnte benutzt werden, um eine zufällige Spalte (mit einem negativen Element in der Zeile 0) für das Pivotieren auszuwählen.

Das Programm und das obige Beispiel beziehen sich auf einen einfachen Fall, der das dem Simplex-Algorithmus zugrunde liegende Prinzip veranschaulicht, aber die erheblichen Komplikationen umgeht, die bei realen Anwendungen auftreten können. Die hauptsächliche Unzulänglichkeit besteht darin, daß es für das Programm erforderlich ist, daß die Matrix eine zulässige Basis besitzt: eine Menge von Zeilen und Spalten, die so permutiert werden kann, daß sich die Einheitsmatrix ergibt. Zu Beginn des Programms wird von den Voraussetzungen ausgegangen, daß eine Lösung existiert, für die die M - N Variablen, die in der Zielfunktion auftreten, den Wert null haben, und daß die Teilmatrix der Dimension N x N, die den Schlupfvariablen entspricht, »aufgelöst« worden ist, so daß diese Teilmatrix zur Einheitsmatrix wird. Dies läßt sich für den angegebenen speziellen Typ linearer Optimierungsaufgaben (bei denen alle Ungleichungen positiven Variablen entsprechen) leicht erreichen, doch im allgemeinen Fall müssen wir irgendeinen Eckpunkt des Simplex finden. Wenn wir einmal eine Lösung gefunden haben, können wir geeignete Transformationen durchführen (die diesen Punkt auf den Ursprung abbilden), um die Matrix in die geforderte Form zu bringen, doch zu Beginn wissen wir nicht einmal, ob eine Lösung existiert.

Tatsächlich ist gezeigt worden, daß die Feststellung, ob eine Lösung existiert, numerisch ebenso schwierig ist wie die Bestimmung der optimalen Lösung, wenn bekannt ist, daß eine existiert. Daher ist es nicht überraschend, daß die Methode, die gewöhnlich angewandt wird, um festzustellen, ob eine Lösung existiert, der Simplex-Algorithmus selbst ist! Wir führen nämlich eine weitere Menge künstlicher Variablen s1, s2, ..., sN ein und fügen die Variable si zur i-ten Gleichung hinzu. Dies geschieht einfach in der Weise, daß zu der Matrix N Spalten hinzugefügt werden, die die Einheitsmatrix bilden. Hierdurch erhält man sofort eine zulässige Basis für diese neue lineare Optimierungsaufgabe. Der Trick besteht darin, den obigen Algorithmus mit der Zielfunktion - s1 - s2 - ... - sN ausführen zu lassen. Falls die ursprüngliche lineare Optimierungsaufgabe eine Lösung besitzt, so kann diese Zielfunktion den maximalen Wert null erreichen. Falls das erreichte Maximum nicht gleich null ist, so besitzt die ursprüngliche lineare Optimierungsaufgabe keine zulässige Lösung. Falls das Maximum gleich null ist, so liegt im Normalfall die Situation vor, daß alle Variablen s1, s2, ..., sN zu Nicht-Basisvariablen geworden sind, so daß wir eine zulässige Basis für die ursprüngliche lineare Optimierungsaufgabe berechnet haben. In entarteten Fällen können einige der künstlichen Variablen noch in der Basis enthalten sein, so daß es erforderlich ist, weitere Pivot-Operationen auszuführen, um sie zu entfernen (ohne die Kosten zu verändern).

Zusammenfassend kann gesagt werden, daß für die Lösung allgemeiner linearer Optimierungsaufgaben normalerweise ein aus zwei Phasen bestehender Prozeß zur Anwendung kommt. Zuerst lösen wir eine lineare Optimierungsaufgabe, in der die künstlichen Variablen s auftreten, um einen Eckpunkt des Simplex für unser Ausgangsproblem zu erhalten. Danach entfernen wir die Variablen s und benutzen wieder unsere ursprüngliche Zielfunktion, um von diesem Punkt zur Lösung zu gelangen.

Die Analyse der Laufzeit der Simplexmethode ist äußerst kompliziert, und nur wenige Ergebnisse sind bekannt. Die »beste« Strategie der Auswahl des Pivotelements ist unbekannt, da keine Ergebnisse vorliegen, die aussagen, wie viele Pivot-Schritte für irgendeine sinnvolle Klasse von Problemen zu erwarten sind. Es ist möglich, künstliche Beispiele zu konstruieren, für die die Laufzeit der Simplexmethode sehr groß ist (eine Exponentialfunktion der Variablenzahl). Wer den Algorithmus bereits für praktische Anwendungen benutzt hat, bestätigt jedoch einhellig seine Effizienz bei der Lösung realer Probleme.

Die von uns betrachtete einfache Variante des Simplex-Algorithmus ist, obwohl sie sehr nützlich ist, nur ein Teil einer allgemeinen und sehr schönen mathematischen Theorie, die eine vollständige Menge von Werkzeugen liefert, die eingesetzt werden können, um eine Vielzahl sehr wichtiger praktischer Probleme zu lösen.


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