zum Artikel Simplex-Verfahren#Mathematische Beschreibung

Grundidee (160801)

Bearbeiten

Die Simplex-Verfahren dienen zur Lösung linearer Optimierungsaufgaben, das ist die Suche nach reellen Variablenwerten, die ein System linearer Ungleichungen und Gleichungen erfüllen und dabei eine lineare Zielfunktion maximieren oder minimieren.

Ausgegangen wird dabei von der Form

(LP)   

wobei   eine Matrix mit reellen Einträgen ist,   der sogenannte Zielfunktionsvektor, und   ein Spaltenvektor mit nichtnegativen Einträgen  .   Ziel ist es, einen Punkt   zu finden, der das lineare Ungleichungssystem erfüllt und einen möglichst hohen Zielfunktionswert   hat.

Jedes lineare Programm kann durch einfache Umformungen in die Form

(LP)   

gebracht werden, bei welcher die Vorzeichen in   freilich immer noch beliebig sind. Das geschieht wie folgt:

  • Ein Minimierungsproblem kann durch Multiplikation der Zielfunktion mit   in ein Maximierungsproblem verwandelt werden.
  • Ungleichungen   können auch   geschrieben werden.
  • Vorhandene Gleichungsgruppen   können in Ungleichungsgruppen   mit   aufgespalten werden.
  • Variablengruppen   mit beliebigem Wertebereich können über eine zusätzliche Variable und   durch nichtnegativen Variablen   ersetzt werden.

In Gegensatz zu diesen Umformungen ist die stets vorausgesetzte Startbedingung   nur über die Lösung einer Hilfsaufgabe in einer sogenannten "Phase 1" zu erreichen; dabei ist diese Hilfsaufgabe grundsätzlich ebenso aufwändig wie die eigentliche Optimierung.

Mathematische Beschreibung des Verfahrens

Bearbeiten

Die folgende Beschreibung ist eher ausführlich gehalten; eine knappere Beschreibung für eine allgemeinere Algorithmengruppe befindet sich unter Pivotverfahren.

Das (primale) Simplex-Verfahren setzt sich aus zwei Phasen zusammen:

  • In einer Vorphase wird eine beliebige, nicht unbedingt nichtnegative Basislösung der Aufgabe erstellt.
  • Phase 1 bestimmt eine zulässige Startlösung oder stellt fest, dass das Problem keine Lösung besitzt.
  • Phase 2 verbessert eine bestehende Lösung immer weiter, bis keine Verbesserung der Zielfunktion mehr möglich ist oder die Unbeschränktheit des Problems festgestellt wird.


Bestimmung einer Startbasis (Vorphase)

Bearbeiten

Als erster Schritt eines Simplexverfahrens muss die lineare Optimierungsaufgabe so dargestellt werden, dass sie ausschließlich lineare Gleichungen in nichtnegativen Unbekannten und der Zielvariablen enthält. Das ist immer möglich; im Falle des obigen Systems erhalten wir

Maximiere     so dass  ,       und


 


Dieses Gleichungssystem ist in besonderer Form, der sogenannten Basisform, bei welcher eine Teilmenge ausgewählter Spalten eine Einheitsmatrix bilden. Die Spalten der Einheitsmatrix müssen aber nicht unbedingt die Spalten der sogenannten Schlupfvariablen   sein. Die Information des obigen Gleichungssystems lässt sich in einem sogenannten Tableau speichern; ein Simplextableau ("Simplextafel") ist nichts weiter als eine Datenstruktur für das Gleichungssystem:

*   *   *   *  
       
       



Die obige Darstellung ist die klassische Darstellungsform einer Optimierungsaufgabe. Nun lässt sich das Gleichungssystem der Optimierungsaufgabe aber auch etwas knapper und symmetrischer in sogenannter Dictionary-Form darstellen. Aus der obigen Aufgabestellung folgt nämlich auch

Maximiere     so dass  ,       und


 

Das entsprechende Dictionary-Tableau dazu ist

*   *  
     
     

In der Literatur über Lineare Optimierung gibt noch es eine Vielzahl weiterer Arten, eine allgemeine lineare Optimierungsaufgabe darzustellen; hier sollen diese beiden Varianten als repräsentative Beispiele dienen.

In der folgenden Ausführung wird stillschweigend vorausgesetzt, dass die Zielvariable maximiert (nicht minimiert) wird und dass für eine zulässige Lösung der Optimierungsaufgabe sämtliche Unbekannte außer der Zielvariablen nichtnegativ zu sein haben; diese Bedingungen werden nicht mehr besonders erwähnt.


Übergang auf die Darstellung einer Nachbarbasis

Bearbeiten

Das folgende Schema zeigt, wie sich die Einträge des klassischen Tableaus von einem Schritt auf den nächsten verändern. Das lässt sich am leichtesten an einem Pivotsystem betrachten, das nur eine einzige Basisvariable und eine einzige Nichtbasisvariable hat:

 

     

 

Natürlich hat ein Pivotsystem viele weitere Unbekannte, doch deren Einträge verändern sich genauso wie die Einträge der Zielbeitragszeile oder der Basiswertspalte. Hier steht   für das Pivotelement,   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.

Es folgt eine Matrixbeschreibung des klassischen Tableaus. Die Matrix   sei nun eine beliebige Spaltenumstellung der Matrix  , für welche die sogenannte Basismatrix   umkehrbar sein muss. Die den Spalten von   zugeordneten Variablen   heißen Basisvariablen oder einfach Basis. Wir können also als Startbasis   mit  ,     auswählen. Es gilt nun

 


 


 

Das klassische Tableau für eine beliebige Basis ist

*   *   *   *  
       
       



Das folgende Schema zeigt, wie sich die Einträge des Dictionary-Tableaus von einem Schritt auf den nächsten verändern. Das lässt sich am leichtesten an einem Pivotsystem betrachten, das nur eine einzige unabhängige Unbekannte und eine einzige freigelegte Unbekannte hat:

 

     

 

Das Pivotsystem hat viele weitere Unbekannte, doch deren Einträge verändern sich genauso wie die Einträge der Zielbeitragszeile oder der Basiswertspalte. Hier steht   für das Pivotelement,   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.

Für eine Matrixbeschreibung des Dictionary-Tableaus müssen die Variablen umgestellt werden, so dass die Nichtbasisvariablen an erster Stelle stehen, gefolgt von den Basisvariablen. Wir erhalten

 


 


 

Das dazugehörende Dictionary-Tableau ist natürlich

*   *  
     
     



Bestimmung einer zulässigen Basis (Phase 1)

Bearbeiten

Zunächst muss eine zulässige Startlösung berechnet werden, bevor man die Phase II starten kann. Eine Möglichkeit dafür ist, für jede Zeile   eine künstliche Variable   einzuführen und dann folgendes lineare Programm zu betrachten:

(LP1)  

In einer Optimallösung dieses Hilfsproblems sind die künstlichen Variablen so klein wie möglich, wobei sie immer nichtnegativ bleiben müssen. Das ursprüngliche Problem (LP) besitzt genau dann eine zulässige Lösung, wenn es eine Lösung des Hilfsproblems mit   gibt, bei der also keine künstlichen Variablen verwendet werden.

Das Hilfsproblem (LP1) besitzt für   eine einfache zulässige Startlösung, nämlich  . Darüber hinaus gilt für jede zulässige Lösung des Hilfsproblems  , so dass die Zielfunktion nach oben durch   beschränkt ist. Dieses lineare Programm besitzt also eine Optimallösung, die ausgehend von der Startlösung   mit Phase II des Hilfsproblems bestimmt werden kann. Findet man dabei eine Optimallösung   mit  , ist   offensichtlich eine zulässige Startlösung für das Ausgangsproblem (LP), mit der dessen Phase II gestartet werden kann. Gelingt dies nicht, so ist das Ausgangsproblem nicht lösbar und man kann aufhören.

Bestimmung einer Optimumbasis (Phase 2)

Bearbeiten

Phase II ist ein iteratives Verfahren, das in jedem Schritt versucht, aus einer zulässigen Lösung eine neue Lösung mit besserem Zielfunktionswert zu konstruieren, bis dies nicht mehr möglich ist. Dies entspricht im wesentlichen der wiederholten Lösung eines linearen Gleichungssystems mit Hilfe des Gaußschen Eliminationsverfahrens. Dabei kann auch evtl. Unbeschränktheit des Optimierungsproblems festgestellt werden. Zur Erklärung dieser Phase ist die Definition einiger Begriffe notwendig.


Verschiedenes

Bearbeiten

Basen, Basislösungen und Ecken

Bearbeiten

In der Phase II des Simplex-Verfahrens spielt der Begriff der Basis eine wesentliche Rolle. Eine Basis   von   ist eine Teilmenge der Spalten von  , die eine reguläre, also invertierbare Untermatrix   bilden.   wird dabei als Indexvektor über die Spalten von   dargestellt. Die Variablen, die zu den Basisspalten gehören, also in   enthalten sind, heißen Basisvariablen, die anderen Nichtbasisvariablen. Die Basislösung zu einer gegebenen Basis   ist der eindeutige Vektor  , dessen Basisvariablen sich als   ergeben und dessen Nichtbasisvariablen alle den Wert 0 haben. Solch eine Basislösung ist also eine zulässige Lösung des Gleichungssystems   mit höchstens   Nicht-Null-Einträgen. In dem Fall, dass alle Komponenten von   nichtnegativ sind, ist   auch eine zulässige Lösung von (LP), also ein Punkt des Polyeders  .

Man kann zeigen, dass jede zulässige Basislösung einer Ecke (Extremalpunkt) des Polyeders entspricht und umgekehrt. Eine Basislösung heißt nicht degeneriert, wenn sie genau   Nicht-Null-Einträge besitzt. In diesem Fall gibt es eine eindeutige zugehörige Basis. Sind alle Basislösungen nicht degeneriert, gibt es also eine bijektive Abbildung zwischen Basen der Matrix   und Ecken des Polyeders  .

Ist eine Basislösung dagegen degeneriert, so hat sie weniger als   Nicht-Null-Einträge und kann zu mehreren Basen gehören. In diesem Fall definiert also jede Basis der Matrix   genau eine Ecke des Polyeders  , aber nicht umgekehrt. Dieser Fall tritt auf, wenn eine Ecke von mehr als   Ungleichungen definiert wird, was bei praktischen Planungsproblemen so gut wie immer der Fall ist.

Iterative Simplexschritte

Bearbeiten

Die Phase II versucht iterativ in jedem Austauschschritt, aus einer bestehenden Basislösung, wie sie z. B. in Phase I bestimmt wurde, eine neue Basislösung mit mindestens genauso gutem Zielfunktionswert zu konstruieren, indem sie eine Basisvariable aus der Basis entfernt und dafür eine bisherige Nichtbasisvariable in die Basis aufnimmt. Dies wird so lange wiederholt, bis kein verbessernder Austausch mehr möglich ist.

In dieser Phase gibt es zu Beginn jeder Iteration ein sogenanntes Simplextableau zur aktuellen Basis  , in dem die Berechnungen durchgeführt werden. Es entspricht im wesentlichen dem linearen Gleichungssystem  ,    , nach einer Basistransformation in die aktuelle Basis.

Simplextableau

Bearbeiten

Für die Formulierung des Simplextableaus gibt es unterschiedliche Möglichkeiten; die hier vorgestellte Version basiert auf [1].


Jeder Simplexschritt geht von einer zulässigen Basis   aus. Zu Beginn des Schrittes hat das zugehörige Simplextableau die folgende Form:

 

Hierbei sind zur Vereinfachung der Darstellung die Spalten so umsortiert worden, dass alle Nichtbasisspalten links stehen und alle Basisspalten rechts.    ist die  -dimensionale Einheitsmatrix. Die  -dimensionale Matrix   und die restlichen obigen Einträge sind definiert durch

 
 
 
 

Dabei ist

  •   die reguläre Untermatrix von  , die aus den Spalten der aktuellen Basis   besteht,
  •   die (meistens nicht quadratische) Untermatrix von  , die aus den Nichtbasisspalten besteht,
  •   die Teile des Zielfunktionsvektors  , die aus den Basisspalten bestehen, und
  •   die Teile des Zielfunktionsvektors  , die aus den Nichtbasisspalten bestehen.

Die rechte Seite   enthält die Werte der Basisvariablen von der zu   gehörenden Basislösung;   ist der Zielfunktionswert dieser Basislösung. Zu Beginn der Phase I bilden die Variablen   eine zulässige Basis mit der Einheitsmatrix als Basismatrix und der zugehörigen Basislösung  . Daher steht am Anfang auf der rechten Seite einfach der Vektor  .

Die Einträge des Vektors   heißen reduzierte Kosten der Nichtbasisvariablen. Der Wert   gibt die Verbesserung der Zielfunktion an, wenn Variable   um eine Einheit erhöht wird. Sind zu Beginn eines Simplexschrittes alle reduzierten Kostenkoeffizienten negativ oder 0, sind daher die aktuelle Basis und die zugehörige Basislösung optimal, da die Aufnahme einer bisherigen Nichtbasisvariable in die Basis den Zielfunktionswert verschlechtern würde. Gibt es dagegen Nichtbasisvariablen mit positiven reduzierten Kosten, wird im nächsten Simplexschritt eine von ihnen in die Basis aufgenommen und dafür eine andere Variable aus der Basis entfernt. Wenn die neue Variable innerhalb der Nebenbedingungen   erhöht werden kann, verbessert sich der Zielfunktionswert.

Ein einzelner Simplexschritt

Bearbeiten

Für den eigentlichen Simplexschritt wählt man nun eine Spalte   der einzufügenden Nichtbasisvariable und eine Zeile   der aus der Basis zu entfernenden Basisvariablen. Seien   die (Matrix-) Elemente des aktuellen Simplextableaus. Dann heißt   das Pivotelement des Simplextableaus. Die Spalte   heißt Pivotspalte, die Zeile   heißt Pivotzeile. Ein Austauschschritt entspricht exakt einem Schritt beim Lösen eines linearen Gleichungssystems, bei dem man die Pivotzeile   nach der Variablen   auflöst und dann   in die restlichen Gleichungen einsetzt. Bei einem Austauschschritt berechnet sich das neue Simplextableau folgendermaßen:

Pivotelement:

 

Pivotzeile für j ungleich s:

 
 

Pivotspalte für i ungleich r:

 
 

Restliche Elemente der Matrix und reduzierte Kosten:

 
 

Rechte Seite:

 

Diese Rechenschritte entsprechen der Anwendung des Gaußschen Eliminationsverfahrens, um die Pivotspalte s im Tableau in einen Einheitsvektor zu transformieren. Dadurch wird die inverse Matrix   zur neuen Basis   nicht komplett neu berechnet, sondern durch Modifikation der alten Basisinversen   konstruiert.

Ein Simplexschritt, der von einer nicht degenerierten Basislösung ausgeht, führt auf jeden Fall zu einer neuen Basislösung und damit auch zu einer neuen Ecke des Polyeders mit besserem Zielfunktionswert. Ist dagegen die Basislösung degeneriert, kann es passieren, dass die neue Basis nach dem Simplexschritt zur selben Basislösung und damit auch zur selben Ecke gehört, so dass der Zielfunktionswert sich nicht ändert. Bei unvorsichtiger Wahl der Pivotelemente kann es zu sogenannten Zyklen kommen, bei der reihum immer wieder dieselben Basen besucht werden, so dass der Algorithmus in eine Endlosschleife läuft. Dies lässt sich aber beispielsweise durch eine geeignete Auswahl der Pivotzeile verhindern. In der Praxis ist eine weitere Methode, mit Zykeln umzugehen, eine absichtliche Perturbation (numerische Störung) der Daten, die nach einigen Iterationen wieder rausgerechnet wird, wenn der Algorithmus die betreffende Ecke verlassen hat.

Für die Wahl des Pivotelements gibt es meist mehrere Möglichkeiten. Die ursprünglich von Dantzig vorgeschlagene Methode wählt eine der Spalten mit dem größten reduzierten Kostenwert und eine beliebige Zeile, bei der nach dem Simplexschritt wieder eine zulässige (insbesondere nichtnegative) Basislösung entsteht. Dazu muss bei gegebener Pivotspalte   eine Pivotzeile gewählt werden, bei der das Minimum

 

angenommen wird. Sind alle Einträge in Spalte   negativ, ist das Optimierungsproblem unbeschränkt, da man Lösungen mit beliebig gutem Zielfunktionswert konstruieren könnte. In diesem Fall kann man aufhören.

Im Normalfall gibt es sowohl mehrere Spalten mit positiven reduzierten Kosten als auch mehrere Zeilen, bei denen das Minimum   angenommen wird, so dass eine Wahlmöglichkeit besteht. Da die Wahl des Pivotelements einen großen Einfluss auf die Rechenzeit haben kann, sind innerhalb der letzten 60 Jahre zahlreiche verbesserte Pivotstrategien gegenüber der Lehrbuchvariante entwickelt worden (siehe unten).


Allgemeine Pivotverfahren

Bearbeiten
 
Allgemeine Pivotverfahren durchlaufen Schnittpunkte der Nebenbedingungen, bis sie an einer Ecke mit der Optimallösung ankommen.

siehe Hauptartikel: Pivotverfahren

Im Gegensatz zu Simplexverfahren durchlaufen allgemeine Pivotverfahren beliebige, nicht unbedingt zulässige oder dual-zulässige Basislösungen, also Schnittpunkte der durch Nebenbedingungen definierten Ebenen. Die aufeinanderfolgend besuchten Basislösungen werden dabei (1) sich in nur einer Schnittpunktebene unterscheiden, entweder (2) eine bis dann verletzte Nebenbedingung befriedigen, oder aber (3) einen verbesserten Zielfunktionswert aufweisen.

Theoretisch gesehen lässt sich beweisen, dass sich mit so einem Pivotverfahren immer in einer linear beschränkten Anzahl von Schritten eine Optimallösung erreichen lässt. In der Praxis jedoch lässt sich dieses Ergebnis nur für die durchschnittliche Schrittzahl umsetzen, und es ist derzeit (2011) noch keine Variante gefunden worden, die diese Schranke auch im ungünstigsten Fall einhält.


Arbeitsvorlagen

Bearbeiten

Startsystem

Bearbeiten
 


*   *   *   *  
       
       


 


Dictionary-Tafel:

 


 


*   *  
     
     


Abgewandelt

Bearbeiten
 


 


 


*   *   *   *  
       
       



 


Dictionary-Tafel:

 


 


 


*   *  
     
     


 

Sonstige Matrixbeziehungen

Bearbeiten

 



 


Beispiel

Bearbeiten
 


*   *   *   *   *   *   *  
1 2 1 0 0 0 170
1 1 0 1 0 0 150
0 3 0 0 1 0 180
-300 -500 0 0 0 1 0

Dictionary-Tafel:

 


*   *   *  
  0 300 500
  170 -1 -2
  150 -1 -1
  180 0 -3


  1. Martin Grötschel, Vorlesungsskript Algorithmische Diskrete Mathematik II: Lineare Optimierung (pdf)