Simplex-Verfahren

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Das Simplex-Verfahren läuft von einer Ecke eines LP-Polyeders zur nächsten, bis keine Verbesserung mehr möglich ist.

Das Simplex-Verfahren (auch Simplex-Algorithmus) ist im Operations Research ein Optimierungsverfahren zur Lösung linearer Programme (LPs). Es löst ein solches Problem nach endlich vielen Schritten exakt oder stellt dessen Unlösbarkeit oder Unbeschränktheit fest. Die Grundidee des Simplex-Verfahrens wurde 1947 von George Dantzig vorgestellt. Seitdem hat es sich durch zahlreiche Verbesserungen zum wichtigsten Lösungsverfahren der linearen Optimierung in der Praxis entwickelt.

Obwohl bisher für jede Variante des Verfahrens ein Beispiel konstruiert werden konnte, bei dem der Algorithmus exponentielle Laufzeit benötigt, läuft der Simplex-Algorithmus in der Praxis meist schneller als andere Verfahren. Zwar gibt es zur Lösung einzelner linearer Programme auch andere konkurrenzfähige Methoden, z. B. Innere-Punkte-Verfahren. Der große Vorteil des Simplex-Algorithmus liegt jedoch darin, dass er bei leichter Veränderung des Problems – beispielsweise dem Hinzufügen einer zusätzlichen Bedingung – einen „Warmstart“ von der letzten verwendeten Lösung durchführen kann und daher meist nur wenige Iterationen zur erneuten Lösung benötigt, während andere Verfahren von vorne beginnen müssen. Darüber hinaus nutzt das Simplex-Verfahren die engen Zusammenhänge zwischen einem linearen Programm und seinem dualen LP aus und löst grundsätzlich beide Probleme gleichzeitig. Beide Eigenschaften sind in der nichtlinearen oder ganzzahligen linearen Optimierung von Bedeutung, wo sehr viele ähnliche LPs in Folge gelöst werden müssen.

Die geometrische Grundidee des Algorithmus besteht darin, von einer beliebigen Ecke des Polyeders, das durch das lineare Programm definiert wird, entlang seiner Kanten zu einer optimalen Ecke zu laufen. Der Name des Verfahrens rührt daher, dass die nichtnegativen Linearkombinationen der Basisspalten in jeder Iteration einen simplizialen Kegel beschreiben. Ein Namensvetter dieses Verfahrens namens Downhill-Simplex-Verfahren basiert ebenfalls auf einem Simplex, ist aber ein iteratives Verfahren zur nichtlinearen Optimierung.

Inhaltsverzeichnis

1 Geschichte
2 Grundidee des Simplex-Verfahrens
3 Laufzeit
4 Mathematische Beschreibung des Verfahrens
- 4.1 Bestimmung einer Startlösung (Phase I)
- 4.2 Bestimmung einer Optimallösung (Phase II)
5 Duale Information im Tableau
6 Varianten und Verbesserungen des Simplex-Verfahrens
7 Beispielrechnung
8 Quellen
9 Literatur
10 Weblinks

[Bearbeiten] Geschichte

Die Grundlagen der linearen Optimierung wurden 1939 von dem russischen Mathematiker Leonid Witaljewitsch Kantorowitsch in seinem Buch „Mathematische Methoden in der Organisation und Planung der Produktion“ gelegt. Kurz danach präsentierte der Amerikaner F.L. Hitchcock eine Arbeit zu einem Transportproblem. Im Jahre 1947 veröffentlichte George Dantzig das Simplex-Verfahren, mit dem lineare Programme erstmals systematisch gelöst werden konnten. Eine der ersten dokumentierten Anwendungen der neuen Methode war das Diäten-Problem von G.J. Stigler, dessen Ziel eine möglichst kostengünstigste Nahrungszusammensetzung für Soldaten war, die bestimmte Mindest- und Höchstmengen an Vitaminen und anderen Inhaltsstoffen erfüllte. An der optimalen Lösung dieses linearen Programms mit neun Ungleichungen und 77 Variablen waren damals neun Personen beschäftigt, die zusammen etwa 120 Manntage Rechenarbeit benötigten.^[1] Interesse an dieser Arbeit zeigte zunächst das amerikanische Militär, speziell die US Air Force, die militärische Einsätze optimieren wollte. In den Folgejahren entwickelten John von Neumann und Oskar Morgenstern das Verfahren weiter.

Mit dem Aufkommen von Computern Mitte der 1950er Jahre konnte man auch größere Probleme lösen. Man entwickelte spezielle Varianten der Simplexmethode wie das revidierte Simplex-Verfahren, das sehr sparsam mit dem damals knappen und teuren Hauptspeicher umging. Im Jahre 1954 brachte William Orchard-Hays die erste kommerzielle Implementierung dieses Verfahrens auf den Markt. Im selben Jahr veröffentlichten Lemke und Beale das duale Simplex-Verfahren, das sich heute – nach weiteren Verbesserungen – zu einer der Standardmethoden zur Lösung linearer Programme entwickelt hat.

Die theoretische Komplexität des Simplex-Verfahrens war lange Zeit unklar. Erst im Jahre 1972 konstruierten V. Klee und G.J. Minty ein Beispiel, bei dem der Algorithmus alle exponentiell vielen Ecken eines Polyeders abläuft, und zeigten damit die exponentielle Laufzeit des Verfahrens. Ähnliche Beispiele wurden bisher für alle bekannten Varianten des Verfahrens gefunden.

Ab den 1970er Jahren profitierte der Simplex-Algorithmus – wie auch andere Verfahren der Linearen Optimierung – von algorithmischen Fortschritten der numerischen linearen Algebra, insbesondere bei der Lösung großer linearer Gleichungssysteme. Vor allem die Entwicklung numerisch stabiler LR-Zerlegungen für dünnbesetzte Matrizen trugen maßgeblich zum Erfolg und der Verbreitung des Simplex-Verfahrens bei.

Seit Mitte der 1970er bis Anfang der 1990er Jahre wurde das Verfahren durch die Entwicklung neuer Pivotstrategien deutlich verbessert. Vor allem die wachsende Bedeutung der ganzzahligen linearen Optimierung in den 1980er Jahren sowie die Entwicklung des dual steepest edge pricing in der Implementierung von Forrest und Goldfarb (1992) machten das duale Simplex-Verfahren zum ernsthaften Konkurrenten für andere Lösungsmethoden. Umgekehrt hatte diese Verbesserung des dualen Simplex-Algorithmus einen maßgeblichen Anteil am Erfolg von Schnittebenenverfahren und Branch-and-Cut zur Lösung ganzzahliger linearer Programme. Darüber hinaus sorgten neue Preprocessing-Methoden in den 1990er Jahren dafür, dass immer größere LPs gelöst werden konnten. Unter der – in praktischen Anwendungen fast immer erfüllten – Voraussetzung, dass die auftretenden LP-Matrizen dünnbesetzt sind, können heute lineare Programme mit mehreren Hunderttausend Variablen oder Ungleichungen innerhalb weniger Stunden optimal gelöst werden.

[Bearbeiten] Grundidee des Simplex-Verfahrens

Das Simplex-Verfahren dient zur Lösung linearer Programme der Form

(LP) $\max \{ c^T x \;|\; Ax = b,\; x \geq 0 \}$ ,

wobei $A \in \mathbb{R}^{m \times n}$ eine Matrix mit reellen Einträgen, $c \in \mathbb{R}^n$ der sogenannte Zielfunktionsvektor und $b \in \mathbb{R}^m$ ein Vektor mit Beschränkungen ist. Ziel ist es, einen Punkt $x$ zu finden, der das lineare Gleichungssystem erfüllt und einen möglichst hohen Zielfunktionswert $G (x) = c T x$ hat.

Jedes lineare Programm kann durch einfache Umformungen in diese Form gebracht werden. Insbesondere lässt sich ein Minimierungsproblem durch Multiplikation der Zielfunktion mit (-1) in ein Maximierungsproblem verwandeln. Meist wird noch vorausgesetzt, dass alle Einträge von $b$ nichtnegativ sind, was sich immer durch Multiplikation einzelner Zeilen des Gleichungssystems mit (-1) erreichen lässt.

Geometrisch lässt sich die Menge der zulässigen Lösungen, also die Menge der Punkte mit nichtnegativen Koordinaten, die das lineare Gleichungssystem $A x = b$ erfüllen, als konvexes Polyeder (mehrdimensionales Vieleck) $P$ interpretieren, dessen Dimension durch die Anzahl der Variablen nach oben begrenzt ist. Ziel ist es, einen Punkt $x$ in $P$ mit möglichst hohem Zielfunktionswert $G (x)$ zu finden. Anschaulich entspricht dies der Verschiebung der Hyperebene $c T x = 0$ soweit wie möglich in Richtung des Vektors $c$ , so dass sie gerade noch das Polyeder berührt. Alle Berührungspunkte sind dann optimal.

Für die Menge der zulässigen Lösungen gibt es drei Möglichkeiten:

das LP besitzt keine zulässigen Lösungen, d. h. das Polyeder ist leer (z. B. $\max\{ x \;|\; x \leq 1, \; x \geq 2 \ \}$ ).
das LP ist unbeschränkt, d. h. es gibt Lösungen mit beliebig hohem Zielfunktionswert (z. B. $\max\{ x \;|\; x \geq 0 \}$ ).
es gibt genau eine oder unendliche viele Optimallösungen, die dann alle auf einer gemeinsamen Seitenfläche (Ecke, Kante,...) des Polyeders $P$ liegen.

Man kann zeigen, dass es immer eine optimale Ecke gibt, falls das Optimierungsproblem überhaupt zulässige Lösungen besitzt und beschränkt ist. Man kann sich also bei der Suche nach Optimallösungen auf die Ecken des Polyeders beschränken, von denen es allerdings sehr viele geben kann.

Die anschauliche Grundidee des Simplex-Verfahrens besteht nun darin, sich schrittweise von einer Ecke des Polyeders zur einer benachbarten Ecke mit besserem Zielfunktionswert zu hangeln, bis es keinen besseren Nachbarn mehr gibt. Da es sich bei der linearen Optimierung um ein konvexes Optimierungsproblem handelt, ist die so gefundene lokal optimale Ecke dann auch global optimal, d. h. es gibt in ganz $P$ keine andere Ecke mit besserem Zielfunktionswert mehr.

[Bearbeiten] Laufzeit

Die Zahl der Ecken eines Polyeders kann exponentiell in der Anzahl der Variablen und Ungleichungen sein. Beispielsweise lässt sich der $n$ -dimensionale Einheitswürfel durch $2 n$ lineare Ungleichungen beschreiben, besitzt aber $2 n$ Ecken. Klee und Minty konstruierten im Jahre 1972 einen verzerrten Einheitswürfel, den sogenannten Klee-Minty-Würfel, bei dem die von Dantzig vorgestellte Variante des Simplex-Verfahrens auch tatsächlich alle diese Ecken besuchte.^[2] Ähnliche Beispiele wurden bisher für alle Zeilen- und Spaltenauswahlregeln gefunden. Dies bedeutet, dass der Simplex-Algorithmus in allen bisher bekannten Varianten im schlechtesten Fall exponentielle Laufzeit besitzt.

Bei degenerierten linearen Programmen, wie sie in der Praxis häufig auftreten, kann es sogar zum sogenannten Zykeln kommen, bei dem das Simplex-Verfahren immer wieder dieselbe Ecke betrachtet und dadurch nicht terminiert. Dies lässt sich aber durch Anwendung der lexikographischen Zeilenauswahlregel oder durch absichtliche numerische Störungen verhindern.

Aus theoretischer Sicht ist das Simplex-Verfahren daher beispielsweise den Innere-Punkte-Verfahren mit polynomialer Laufzeit unterlegen. Aus praktischer Sicht hat es sich aber in vielen Fällen als schneller erwiesen. Der größte Vorteil des Simplex-Algorithmus gegen über anderen Verfahren liegt jedoch darin, dass es bei kleinen Änderungen der Eingabedaten im Laufe des Algorithmus einen „Warmstart“ erlaubt, also die letzte berechnete Basis als Ausgangspunkt für wenige weitere (primale oder duale) Iterationen nehmen kann, während beispielsweise Innere-Punkte-Verfahren in solch einem Fall von vorne anfangen müssen. Dieser Fall tritt sehr häufig auf, wenn sehr viele ähnliche lineare Programme in Folge gelöst werden müssen, beispielsweise im Rahmen von Schnittebenenverfahren, Branch-and-Bound oder Branch-and-Cut.

In der Praxis hängt die Laufzeit des Simplex-Verfahren oft im wesentlichen linear von der Anzahl der Zeilen ab. Tatsächlich zeigten Borgwardt und andere in den 1980er Jahren, dass solche Fälle wie der Klee-Minty-Würfel extrem selten sind und dass einige Varianten des Simplex-Algorithmus unter bestimmten Annahmen an den Input im Mittel nur polynomiale Laufzeit benötigen. Es ist aber bis heute unklar, ob es eine Variante mit polynomialer Laufzeit für alle Instanzen gibt.

[Bearbeiten] Mathematische Beschreibung des Verfahrens

Das Simplex-Verfahren setzt sich aus zwei Phasen zusammen:

Phase I bestimmt eine zulässige Startlösung oder stellt fest, dass das Problem keine Lösung besitzt,
Phase II verbessert eine bestehende Lösung immer weiter, bis keine Verbesserung der Zielfunktion mehr möglich ist oder die Unbeschränktheit des Problems festgestellt wird.

[Bearbeiten] Bestimmung einer Startlösung (Phase I)

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 $i$ eine künstliche Variable $z i$ einzuführen und dann folgendes lineare Programm zu betrachten:

(LP1) $\min \left\lbrace\left. \sum_{i=1}^{m} z_i \;\right|\; Ax + z = b, \; x,z \geq 0 \right\rbrace$ .

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 $z = 0$ gibt, bei der also keine künstlichen Variablen verwendet werden.

Das Hilfsproblem (LP1) besitzt für $b \geq 0$ eine einfache zulässige Startlösung, nämlich $(x, z) = (0, b)$ . Darüber hinaus gilt für jede zulässige Lösung des Hilfsproblems $z \leq b$ , so dass die Zielfunktion nach oben durch $\sum_{i=1}^{m} b_i$ beschränkt ist. Dieses lineare Programm besitzt also eine Optimallösung, die ausgehend von der Startlösung $(0, b)$ mit Phase II des Hilfsproblems bestimmt werden kann. Findet man dabei eine Optimallösung $(x *, z *)$ mit $z * = 0$ , ist $x *$ 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.

[Bearbeiten] Bestimmung einer Optimallösung (Phase II)

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.

[Bearbeiten] Basen, Basislösungen und Ecken

In der Phase II des Simplex-Verfahrens spielt der Begriff der Basis eine wesentliche Rolle. Eine Basis $B$ von $A$ ist eine Teilmenge der Spalten von $A$ , die eine reguläre, also invertierbare Untermatrix $A B$ bilden. Die Variablen, die zu den Basisspalten gehören, heißen Basisvariablen, die anderen Nichtbasisvariablen. Die Basislösung zu einer gegebenen Basis $B$ ist der eindeutige Vektor $x$ , dessen Basisvariablen sich als $A_{B}^{-1} b$ ergeben und dessen Nichtbasisvariablen alle den Wert 0 haben. Solch eine Basislösung ist also eine zulässige Lösung des Gleichungssystems $A x = b$ mit höchstens $m$ Nicht-Null-Einträgen. In dem Fall, dass alle Komponenten von $x$ nichtnegativ sind, ist $x$ auch eine zulässige Lösung von (LP), also ein Punkt des Polyeders $P$ .

Man kann zeigen, dass jede zulässige Basislösung einer Ecke des Polyeders entspricht und umgekehrt. Eine Basislösung heißt nicht degeneriert, wenn sie genau $m$ 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 $A$ und Ecken des Polyeders $P$ .

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

[Bearbeiten] Iterative Simplexschritte

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 $B$ , in dem die Berechnungen durchgeführt werden. Es entspricht im wesentlichen dem linearen Gleichungsystem $Ax = b, \; c^T x = G$ , nach einer Basistransformation in die aktuelle Basis.

[Bearbeiten] Simplextableau

Für die Formulierung des Simplextableaus gibt es unterschiedliche Möglichkeiten; die hier vorgestellte Version basiert auf ^[3]. Jeder Simplexschritt geht von einer zulässigen Basis $B$ aus. Zu Beginn des Schrittes hat das zugehörige Simplextableau die folgende Form:

$\left[ \left. \begin{matrix} \bar{c} & 0 \\ \bar{A} & I \end{matrix} \; \right| \; \begin{matrix} G \\ \bar{b} \end{matrix} \right]$ .

Hierbei sind zur Vereinfachung der Darstellung die Spalten so umsortiert worden, dass alle Nichtbasisspalten links stehen und alle Basisspalten rechts. Der $(n - m)$ -dimensionale Vektor $\bar{c}$ und die $m$ x $(n - m)$ -dimensionale Matrix $\bar{A}$ sind definiert durch

$\bar{c} = c_{N}^{T} - c_{B}^{T} A_{B}^{-1} A_{N}$ ,

$\bar{A} = A_{B}^{-1} A_{N}$ und

$\bar{b} = A_{B}^{-1} b$ .

Dabei ist

$A B$ die reguläre Untermatrix von $A$ , die aus den Spalten der aktuellen Basis $B$ besteht,
$A N$ die (meistens nicht quadratische) Untermatrix von $A$ , die aus den Nichtbasisspalten besteht,
$c B$ bzw. $c N$ die Teile des Zielfunktionsvektors $c$ , die aus den Basis- bzw. Nichtbasisspalten bestehen,
$I$ die m-dimensionale Einheitsmatrix,
$G$ der Zielfunktionswert der aktuellen Basislösung.

Die rechte Seite $\bar{b}$ ist die aktuelle Basislösung, die zur Basis $B$ gehört. Zu Beginn der Phase I bilden die Variablen $z i$ eine zulässige Basis mit der Einheitsmatrix als Basismatrix und der zugehörigen Basislösung $(x, z) = (0, b)$ . Daher steht am Anfang auf der rechten Seite einfach der Vektor $b$ .

Die Einträge des Vektors $\bar{c}$ heißen reduzierte Kosten der Nichtbasisvariablen. Der Wert $\bar{c}_j$ gibt die Verbesserung der Zielfunktion an, wenn Variable $x j$ 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 $A x = b$ erhöht werden kann, verbessert sich der Zielfunktionswert.

[Bearbeiten] Ein einzelner Simplexschritt

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

Pivotelement:

$\bar{a}_{rs} := \frac{1}{\bar{a}_{rs}}$ (Formel 1)

Pivotzeile für j ungleich s:

$\bar{a}_{rj} := \frac{\bar{a}_{rj}}{\bar{a}_{rs}}$ (2)

$\bar{b}_{r} := \frac{\bar{b}_{r}}{\bar{a}_{rs}}$ (3)

Pivotspalte für i ungleich r:

$\bar{a}_{is} := - \frac{\bar{a}_{is}}{\bar{a}_{rs}}$ (4)

Restliche Elemente der Matrix und reduzierte Kosten:

$\bar{a}_{ij} := \bar{a}_{ij} - \frac{\bar{a}_{is} \bar{a}_{rj}}{\bar{a}_{rs}}$ (5a)

$\bar{c}_{j} := \bar{c}_{j} - \frac{\bar{c}_{s} \bar{c}_{j}}{\bar{a}_{rs}}$ (5b)

Rechte Seite:

$\bar{b}_{j} := \bar{b}_{j} - \frac{\bar{b}_{r} \bar{a}_{js}}{\bar{a}_{rs}}$ (6)

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 $A_{B'}^{-1}$ zur neuen Basis $B'$ nicht komplett neu berechnet, sondern durch Modifikation der alten Basisinversen $A_{B}^{-1}$ 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 $s$ eine Pivotzeile gewählt werden, bei der das Minimum

$\lambda := \min \left\lbrace\left. \frac{\bar{b}_{i}}{\bar{a}_{is}} \;\right|\; i=1,\ldots,m, \, \bar{a}_{is} > 0 \right\rbrace$

angenommen wird. Sind alle Einträge in Spalte $s$ 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).

[Bearbeiten] Duale Information im Tableau

Aus dem Simplextableau lässt sich auch die Information zur Lösung des zu dem linearen Programm (LP) gehörigen dualen linearen Programms entnehmen. Zu einer gegebenen Basis $B$ kann man neben der zugehörigen Primallösung $x = \bar{b} = A_{B}^{-1} b$ , die in der rechten Spalte des Tableaus steht, auch eine Duallösung $\pi = c_{B}^{T} A_{B}^{-1}$ berechnen. Diese beiden Vektoren $x$ und $π$ erfüllen immer die Bedingung

π T b = c T x

die für Optimallösungen notwendig ist. Der Vektor $x$ bleibt nach Konstruktion der einzelnen Simplexiterationen immer zulässig für das primale LP, während der Vektor $π$ Bedingungen des dualen LPs verletzen kann. Sind zu einer Basis sowohl die zugehörige Primallösung $x$ als auch die entsprechende Duallösung $π$ zulässig (man spricht dann von einer primal und dual zulässigen Basis), dann sind beide optimal für das primale bzw. duale lineare Programm. Man kann zeigen, dass dies genau dann der Fall ist, wenn der reduzierte Kostenvektor $\bar{c}$ nichtpositiv ist. Obwohl das Ziel des Simplex-Verfahrens eigentlich nur die Berechnung einer optimalen Primallösung ist, fällt also am Ende auch eine optimale Duallösung nebenbei mit ab.

[Bearbeiten] Varianten und Verbesserungen des Simplex-Verfahrens

In der hier vorgestellten Form, die im wesentlichen der ursprünglichen Version von Dantzig entspricht, wird der Simplex-Algorithmus in praktischen Implementierungen heute nicht mehr verwendet. Im Laufe der Zeit sind einige Varianten des Simplex-Verfahrens entwickelt worden, die die Rechenzeit und den Speicherbedarf beim Lösen linearer Programme gegenüber dem Standardverfahren deutlich verkürzen und numerisch deutlich stabiler sind. Die wichtigsten Verbesserungen, die heute zum Standard in guten LP-Lösern gehören, sollen hier kurz vorgestellt werden.

[Bearbeiten] Auswahl des Pivotelementes

Bei der Auswahl des Pivotelements hat man in der Regel einige Freiheiten. Die Pivotspalte $s$ und die Pivotzeile $r$ können beliebig gewählt werden, unter den Bedingungen, dass

die Pivotspalte positive reduzierte Kosten hat und
die Pivotzeile wieder zu einer zulässigen Basislösung führt.

Die Wahl des Pivotelementes hat oft großen Einfluss auf die Anzahl der Iterationen und auf die numerische Stabilität des Verfahrens, insbesondere bei degenerierten Problemen. Die Entwicklung besserer Pivotstrategien, insbesondere zur Spaltenauswahl, haben im Laufe der Zeit große Fortschritte bei der Beschleunigung des Lösungsprozesses bewirkt.

[Bearbeiten] Spaltenauswahl

Für die Auswahl der Pivotspalte (engl. pricing) gibt es verschiedene Strategien, die unterschiedlichen Rechenaufwand erfordern und je nach Eingabedaten unterschiedlich gut funktionieren:^[4]^[5]

Wähle die erste geeignete Spalte. Dies ist die einfachste Variante, die aber oft zu sehr vielen Iterationen führt und daher in der Praxis nicht verwendet wird.
Die ursprünglich von Dantzig vorgeschlagene Methode wählt eine der Spalten mit dem größten reduzierten Kostenwert. Diese Variante kann bei vielen Variablen viel Rechenzeit beanspruchen.
Das steepest-edge pricing ist eine Kombination aus Spalten- und Zeilenwahl, die zusammen den größten Fortschritt für die Zielfunktion bringen. Diese Variante ist in jeder Iteration sehr aufwändig, führt aber oft zu wenigen Iterationen.
Das devex pricing ist eine 1974 von Paula Harris vorgeschlagene Approximation von steepest-edge pricing und eines der Standardverfahren in heutigen LP-Lösern. Hierbei werden die Spalten der Matrix und die reduzierten Kosten vor der Auswahl auf eine einheitliche Norm skaliert, um die Aussagekraft der reduzierten Kosten zu erhöhen.
Beim partial pricing wird die Variablenmenge in Blöcke unterteilt und eines der obigen vorherigen Verfahren auf einen Block angewendet. Erst wenn dort keine geeignete Variable gefunden wird, wird überhaupt der nächste Block betrachtet.
Das multiple pricing sucht einmal eine Menge von geeigneten Variablen heraus, die dann in den nächsten Iterationen bevorzugt als Kandidaten betrachtet werden. Erst wenn keiner dieser Kandidaten mehr positive reduzierte Kosten besitzt, werden die anderen Variablen betrachtet.
Das partial multiple pricing ist eine Kombination der letzten beiden Varianten, die neue Kandidaten immer nur aus einem Teil aller zur Verfügung stehenden Variablen bestimmt. Diese Strategie gehört neben devex pricing heute zu den Standardstrategien.
Beim hybrid pricing werden mehrere Strategien je nach Situation abwechselnd verwendet. Einige LP-Löser wenden zusätzlich noch numerische Kriterien bei der Spaltenauswahl an, um die Probleme durch Rundungsfehler in Grenzen zu halten.

[Bearbeiten] Zeilenauswahl

Gibt es mehrere geeignete Pivotzeilen, hat man die Wahl zwischen mehreren Varianten:

Wähle die erste geeignete Zeile. Diese Variante ist zwar pro Iteration sehr schnell, führt aber insgesamt oft zu vielen Iterationen und ist numerisch instabil.
Die lexikographische Auswahlregel wählt unter allen in Frage kommenden Zeilen die (eindeutige) lexikographisch kleinste Zeile aus. Diese Regel ist unter dem Gesichtspunkt der Geschwindigkeit nicht besonders gut, verhindert aber, dass Tableaus mehrfach besucht werden und der Algorithmus ins Zykeln gerät. Aus diesem Grund kann sie beispielsweise für einige Iterationen verwendet werden, um von einer Basislösung wegzukommen, bevor wieder auf andere Auswahlverfahren umgestellt wird.
Der 1973 von Paula Harris vorgeschlagene Harris-Quotiententest, der heute zu den Standardverfahren zählt, erlaubt aus Gründen der numerischen Stabilität eine leichte Unzulässigkeit der neuen Lösung.

[Bearbeiten] Variablenschranken

In der Praxis müssen häufig obere und untere Schranken für die Variablen berücksichtigt werden. Dies gilt insbesondere dann, wenn lineare Programme beispielsweise im Rahmen eines Branch-and-Cut-Prozesses als Unterproblem gelöst werden. Für solche einfachen Arten von Ungleichungen wie Variablenschranken gibt es das sogenannte Bounded-Simplex-Verfahren, bei dem die Schranken direkt in den einzelnen Simplex-Schritten berücksichtigt werden. Im Gegensatz zur Standardversion, bei dem eine Nichtbasisvariable immer den Wert 0 haben, kann sie jetzt auch den Wert einer ihrer Schranken annehmen. Diese Mitführung der Schranken in den einzelnen Schritten bewirkt eine kleinere Anzahl der Zeilen und damit eine kleinere Basis gegenüber der offensichtlichen Variante, Variablenschranken als Ungleichungen in das LP zu schreiben.

[Bearbeiten] Duales Simplex-Verfahren

Neben einer optimalen Primallösung, also einer Lösung für das gegebene lineare Programm, berechnet das oben beschriebene primale Simplex-Verfahren auch eine optimale Duallösung, also eine Lösung des zugehörigen dualen linearen Programms. Da das duale LP aus dem primalen im wesentlichen durch Vertauschung von Zeilen und Spalten entsteht, lässt sich mit dem Simplex-Verfahren auch das duale Problem lösen, indem man das gegenüber der obigen Variante leicht modifizierte Tucker-Tableau verwendet und im beschriebenen Algorithmus Zeilen und Spalten vertauscht. Diese Variante heißt dann duales Simplex-Verfahren. Es wurde erstmals 1954 von Lemke und Beale beschrieben, ist aber erst seit Anfang der 1990er Jahre fester Bestandteil kommerzieller LP-Löser, als erfolgreiche Pivotstrategien dafür entwickelt wurden, wie das dual steepest-edge pricing in der Version von Forrest und Goldfarb aus dem Jahre 1992.

In der Praxis hängt die Laufzeit des Simplex-Verfahrens oft im wesentlichen von der Anzahl der Zeilen im LP ab. Dies gilt insbesondere für dünnbesetzte Matrizen, wie sie in der Praxis normalerweise auftreten. Wenn ein lineares Programm sehr viele Bedingungen, aber nur wenige Variablen hat, kann es sich daher lohnen, statt dessen das duale LP zu lösen, bei dem Zeilen- und Spaltenzahl vertauscht sind, und sich dabei eine optimale Primallösung mitliefern zu lassen, die nebenbei mitberechnet wird.

Ein weiterer großer Vorteil der primal-dualen Betrachtungsweise ist es, dass primale und duale Simplexschritte abwechselnd im selben Tableau durchgeführt werden können. Anstatt das Tableau explizit zu transponieren, werden einfach im Algorithmus Zeilen- und Spaltenoperationen vertauscht, je nachdem, ob gerade der primale oder der duale Algorithmus benutzt wird. Im Gegensatz zum primalen Simplex-Verfahren, das immer eine zulässige Primallösung behält und erst am Ende eine zulässige Duallösung erreicht, ist es beim dualen Simplex-Verfahren umgekehrt. Wenn also die Primallösung zu einer Basis unzulässig, die zugehörige Duallösung aber zulässig ist, kann man durch duale Simplexschritte versuchen, wieder zu einer primal zulässigen Lösung zu kommen. Dies kann man in mehreren Zusammenhängen ausnutzen, die hier kurz beschrieben werden sollen.

Im Verlauf von Schnittebenenverfahren oder Branch-and-Cut-Verfahren wird sehr oft in einem gerade gelösten LP eine Variablenschranke verändert oder eine Ungleichung hinzugefügt, die von der alten Lösung nicht erfüllt wird, und anschließend das LP neu gelöst. Da die alte Basislösung jetzt nicht mehr zulässig ist, ist eine der Grundbedingungen des primalen Simplextableaus verletzt, so dass das das primale Simplexverfahren von vorne starten muss, um das neue LP zu lösen. Wenn an der Zielfunktion nichts verändert wurde, ist aber die alte Duallösung weiter zulässig, so dass mit einigen dualen Simplexschritten von der alten Startbasis aus meist nach wenigen Iterationen eine Optimallösung für das modifizierte LP gefunden wird. Dieser Unterschied schlägt sich bei großen LPs oft sehr deutlich in der Gesamtlaufzeit nieder.
Wenn im Verlauf des Algorithmus numerische Schwierigkeiten auftreten oder es sehr lange keinen Fortschritt in der Zielfunktion gibt, kann es sinnvoll sein, vorübergehend eine leichte Verletzung von Variablenschranken zu erlauben, um sich aus einer kritischen Ecke des Polytops hinauszubewegen. Dies kann anschließend mit einigen dualen Simplexschritten wieder behoben werden.
Wenn das lineare Programm bestimmte Strukturen aufweist, kann man direkt eine primal unzulässige, aber dual zulässige Startbasis angeben, ohne dafür rechnen zu müssen. In solch einem Fall kann man von dieser Basis aus direkt in Phase II mit dualen Simplexschritten starten und kann sich die Phase I sparen.

[Bearbeiten] Revidiertes Simplex-Verfahren

Obwohl praktisch auftretende lineare Programme mehrere hunderttausend Variablen haben können, arbeitet das Simplex-Verfahren immer nur mit einem kleinen Teil davon, nämlich den Basisvariablen. Lediglich bei der Spaltenauswahl müssen die Nichtbasisspalten betrachtet werden, wobei es – je nach Pivotstrategie – oft ausreicht, nur einen Teil davon zu berücksichtigen. Diese Tatsache macht sich das revidierte Simplex-Verfahren zunutze, das immer nur die aktuelle Basismatrix $A B$ oder deren Inverse speichert, zusammen mit etwas Zusatzinformationen, aus der die aktuelle Basismatrix bzw. deren Inverse berechnet werden kann. Dadurch kommt es mit wesentlich weniger Speicherplatz aus als das ursprüngliche Tableauverfahren. Dieses Verfahren bildet heute die Grundlage mehrerer guter LP-Löser.

In der ersten kommerziellen Implementierung dieses Verfahrens von William Orchard Hays im Jahre 1954 wurde die Basisinverse noch in jedem Schritt komplett neu berechnet, was mit den damaligen Lochkartenrechnern eine Herausforderung darstellte. Wenig später implementierte er die sogenannte Produktform der Inversen nach einer Idee von A. Orden. Dabei wurde nur die erste Basisinverse gespeichert, zusammen mit Update-Vektoren, aus denen die jeweils aktuelle Inverse berechnet werden konnte. Der damalige Rekord lag bei einem linearen Programm mit 71 Variablen und 26 Ungleichungen, das innerhalb von acht Stunden optimal gelöst wurde. In heute verwendeten Implementierungen wird eher die Basismatrix selbst mit Hilfe einer speziellen Form der LR-Zerlegung gespeichert, da die Inverse einer dünnbesetzten Matrix in der Regel nicht dünnbesetzt ist,

[Bearbeiten] LR-Zerlegungen

Im Verlauf des Simplex-Verfahrens werden sehr viele ähnliche lineare Gleichungssysteme gelöst. Da große lineare Gleichungssysteme auch in anderen Zusammenhängen (beispielsweise bei der Lösung von Differentialgleichungen) häufig auftreten, wurden in den 1970er Jahren in der numerischen linearen Algebra Verfahren zur LR-Zerlegung einer Matrix entwickelt. Dabei wird die Matrix in eine untere und eine obere Dreiecksmatrix zerlegt, was es anschließend erlaubt, viele Gleichungssysteme mit derselben Matrix, aber unterschiedlichen rechten Seiten effizient zu lösen.

Im Falle des Simplex-Verfahrens wird diese Methode auf die Basismatrix $A B$ angewandt. Da diese sich im Laufe des Simplex-Algorithmus ständig ändert, muss ihre LR-Zerlegung bei jedem Simplexschritt angepasst werden, beispielsweise mit Hilfe des nach seinen Erfindern benannten Forest-Tomlin-Updates. Diese Anpassung erfordert nur sehr geringen Aufwand im Vergleich zur Berechnung einer komplett neuen LR-Zerlegung, weil sich die Basismatrix in jeder Iteration nur in einer Spalte ändert. In praktischen Implementierungen wird meist aus numerischen Gründen trotzdem alle paar hundert Iterationen eine komplett neue LR-Zerlegung der aktuellen Matrix berechnet. Für die Berechnung der LR-Zerlegung selbst gibt es wieder verschiedene Varianten, von denen sich in der Praxis vor allem die LR-Zerlegung mit dynamischer Markowitz-Pivotisierung durchgesetzt hat, da diese die Dünnbesetztheit von Matrizen bei der Zerlegung weitgehend erhält. Dieses Verfahren hat in den letzten Jahren vor allem für große lineare Programme, die fast immer dünnbesetzt sind, zu starken Reduktionen der Rechenzeit geführt.

[Bearbeiten] Preprocessing

In den letzten zehn Jahren sind durch verbessertes Preprocessing sehr große Fortschritte in den Lösungszeiten erzielt worden. Beispielsweise gibt es oft numerische Probleme, wenn in einem linearen Gleichungssystem sowohl sehr große als auch sehr kleine Zahlen auftreten. In einigen Fällen lässt sich dies durch Vorkonditionierung, also z. B. Äquilibrierung des Gleichungssystems, vor dem Start des eigentlichen Algorithmus vermeiden.

Eine andere Klasse von Methoden des Preprocessing versucht, Redundanzen im linearen Gleichungssystem zu erkennen oder Variablenschranken zu verschärfen, um die Anzahl der Zeilen und Spalten zu reduzieren:

Wenn eine Zeile linear abhängig von anderen Zeilen ist, ist sie überflüssig und kann entfernt werden. Dies ist allerdings – bis auf den Spezialfall, dass eine Zeile ein skalares Vielfaches einer anderen Zeile ist – im allgemeinen schwierig mit vertretbarem Aufwand zu erkennen.
Sehr oft sind Variablen aufgrund von Bedingungen auf einen bestimmten Wertebereich beschränkt oder durch andere Variablen festgelegt. Beispielsweise sind durch die Gleichung $x 1 + x 2 = 1$ und die Nichtnegativitätsbedingungen beide Variablen auf den Bereich $[0,1]$ beschränkt. Die Kenntnis dieser Schranke kann den Lösungsprozess beschleunigen. Darüber hinaus ist der Wert von $x 2$ durch den Wert von $x 1$ festgelegt. Dadurch kann man in allen Bedingungen, in denen $x 2$ vorkommt, diese Variable durch $1 - x 1$ ersetzen und $x 2$ aus dem LP entfernen.
Wenn mehrere Variablen auf einen bestimmten Wertebereich fixiert wurden, kann es sein, dass einige Ungleichungen immer erfüllt sind oder nicht mehr erfüllt werden können. Im ersten Fall kann die Ungleichung entfernt werden, im zweiten Fall ist sofort die Unzulässigkeit des LPs gezeigt, und man kann aufhören.

Mit Hilfe solcher Methoden kann gerade bei sehr großen LPs die Anzahl der Zeilen und Spalten manchmal deutlich reduziert werden, was sich in sehr viel kürzeren Lösungszeiten widerspiegelt.

[Bearbeiten] Beispielrechnung

Veranschaulichung des Beispiels (Erklärung siehe Text)

Anhand eines einfachen Beispiels mit zwei Variablen soll der Lösungsweg Schritt für Schritt gezeigt werden. In diesem einfachen Fall ist eine Optimallösung leicht zu finden. Reale Probleme können dagegen leicht aus mehreren Hunderttausend Variablen und Nebenbedingungen bestehen, so dass man ihnen meistens die Existenz einer Lösung oder den Wert einer Optimallösung nicht unmittelbar ansehen kann.

Gegeben sei das lineare Programm

$\max \; G (x_1, x_2) = 300 x_1 + 500 x_2$

unter den Nebenbedingungen

$\begin{matrix} 1 \cdot x_1 &+& 2 \cdot x_2 &\leq& 170 &\mbox{(Maschine A)}\\ 1 \cdot x_1 &+& 1 \cdot x_2 &\leq& 150 &\mbox{(Maschine B)}\\ 0 \cdot x_1 &+& 3 \cdot x_2 &\leq& 180 &\mbox{(Maschine C)} \end{matrix}$

$x_1, \, x_2 \geq 0$

aus einem Beispiel zur Produktionsplanung. Dabei repräsentieren $x 1$ und $x 2$ die zu bestimmenden Produktionsmengen zweier Produkte mit Stückdeckungsbeitrag 300 bzw. 500 Euro. Der Zielfunktionswert G ist daher der Gesamtdeckungsbeitrag, der sich bei den Produktionsmengen $x 1$ und $x 2$ ergibt. Die Nebenbedingungen ergeben sich aus den beschränkten Laufzeiten dreier Maschinen A, B und C. Ziel ist es, unter allen Produktionsmengen, die unter Einhaltung der Nebenbedingungen möglich sind, solche mit maximalen Gesamtdeckungsbeitrag zu finden. Eventuelle Fixkosten sind unabhängig von der Produktionsmenge und können daher einfach am Ende vom Gesamtdeckungsbeitrag abgezogen werden, um den Gewinn zu erhalten.

[Bearbeiten] Überführung in Gleichungen

Für das Simplex-Verfahren werden die Ungleichungen zunächst in Gleichungen überführt. Dazu führt man so genannte Schlupfvariablen $y A$ , $y B$ und $y C$ ein, welche die nicht genutzten Zeiten der einzelnen Maschinen darstellen. Offensichtlich dürfen die Schlupfvariablen nicht negativ sein. Damit lässt sich das Problem folgendermaßen formulieren:

Maximiere die Zielfunktion G unter den Nebenbedingungen:

    -G + 300 x₁ + 500 x₂ =  0
    y_A +     x₁ +   2 x₂ =     170 
    y_B +     x₁ +     x₂ =     150 
    y_C          +   3 x₂ =     180 
    y_A, y_B, y_C, x₁, x₂  0

[Bearbeiten] Bestimmung einer zulässigen Ausgangslösung (Phase I)

Da alle rechten Seiten $b i$ nichtnegativ sind, kann man sofort eine triviale zulässige Lösung angeben, mit der direkt die Phase II gestartet werden kann:

    (x₁, x₂)     = (0,0)
    (y_A, y_B, y_C) = (170, 150, 180)

Dabei bilden die Variablen $y i$ eine zulässige Basis $B$ , deren Basismatrix $A B$ die Einheitsmatrix ist. Die zugehörige Basislösung ist also $A_{B}^{-1} b = b$ . Diese Lösung entspricht dem Fall, dass nichts produziert wird ( $x i = 0$ ). Die Restkapazität der Maschinen, die durch die Werte der $y i$ angegeben wird, ist hier deren Gesamtkapazität (170, 150 und 180), da die Maschinen nicht genutzt werden.

Die obigen Gleichungen überträgt man in das zugehörige Simplex-Tableau:

  --------------------------------
      |  x₁     x₂   | rechte Seite
  ---------------------------------
  -G  |  300    500  |       0
  ---------------------------------
  y_A  |   1      2   |      170  = b₁
  y_B  |   1      1   |      150  = b₂
  y_C  |   0      3   |      180  = b₃

In der Kopfzeile stehen die Nichtbasisvariablen $x_1, \, x_2$ mit dem Wert 0, während die Basisvariablen $y i$ in der ersten Spalte stehen. In der obersten Zeile – der Gleichung für die Zielfunktion – stehen die Zielfunktionskoeffizienten $c i$ , also 300 und 500. Auf der rechten Seite steht die aktuelle Basislösung, was in diesem Fall genau $b$ ist. In der obersten Zeile der rechten Seite steht das Negative des Zielfunktionswertes für die aktuelle Basislösung, im Beispiel also das Negative des Gesamtdeckungsbeitrag. Dieser ist momentan 0, da nichts produziert wird.

[Bearbeiten] Verbesserung der Lösung mittels einer Simplex-Iteration (Phase II)

Da die soeben berechnete Ausgangslösung unbefriedigend ist, wird nun in Phase II versucht, bessere zulässige Lösungen zu finden.

[Bearbeiten] Auswahl einer Pivotspalte und -zeile

In einer Simplex-Iteration wird eine Basisvariable gegen eine Nichtbasisvariable ausgetauscht. In Frage kommen Nichtbasisspalten $s$ mit positivem Zielfunktionskoeffizienten, da deren Aufnahme in die Basis den Zielfunktionswert verbessern kann. Anschließend muss eine Pivotzeile $r$ ausgewählt werden, die den Quotienten

$\frac{b_j}{a_{rs}}$ mit $a_{rs}\neq 0$

innerhalb der Spalte $s$ minimiert.

Spalte 1 hat den positiven Zielfunktionskoeffizienten 300, kommt also als Pivotspalte $s$ in Frage. Berechnung der Quotienten dieser Spalte 1:

 Reihe 1:  170 / 1 = 170
 Reihe 2:  150 / 1 = 150
 Reihe 3:  a₃₁ = 0, daher kein Quotient berechenbar.

Den minimalen Quotient 150 erhält man also in Reihe 2. Mit dem Pivotelement $a 21$ berechnet sich der neue Wert der Zielfunktion zu

$G = 300 \cdot \frac{150}{1} = 45000$ .

Auch Spalte 2 hat mit 500 einen positiven Zielfunktionskoeffizienten, kommt also als Pivotspalte $s$ in Frage.Berechnung der Quotienten dieser Spalte 2:

 Reihe 1:  170 / 2 =  85
 Reihe 2:  150 / 1 = 150
 Reihe 3:  180 / 3 =  60

Den minimalen Quotient 60 erhält man also in Reihe 3. Mit dem möglichen Pivotelement $a 32$ berechnet sich der neue Wert der Zielfunktion zu

$G = 500 \cdot \frac{180}{3} = 30000$ .

Für den Zuwachs der Zielfunktion in diesem Schritt ist es also am günstigsten, das Pivotelement $a 21$ zu wählen.

[Bearbeiten] Durchführung eines Austauschschrittes

Mit dem Austauschschritt wird die Basisvariable $y B$ gegen die Nichtbasisvariablen $x 1$ ausgetauscht. Das Simplex-Tableau wird mit dem Pivotelement $a 21 = 1$ nach den obigen Regeln umgerechnet.

Umrechnung des Pivotelementes:    a₂₁ = 1 / 1 = 1 (mit Formel (1))

Umrechnung der Pivotzeile r = 2: Jedes Element wird durch das Pivotelement geteilt.
        Spalte 1 ist Pivotelement und wurde eben bereits berechnet.
        Spalte 2:      a₂₂ = 1 / 1 = 1 (mit Formel (2))
        rechte Seite:  b₂ = 150 / 1 = 150 (mit Formel (3))

Umrechnung der Pivotspalte s = 1: Jedes Element wird durch das Pivotelement geteilt, 
das Vorzeichen kehrt sich um.
        Zielfunktion:  - (300 / 1) = -300
        Zeile 1:      a₁₁ = - (1 / 1) = -1 (mit Formel (4))
        Zeile 2 ist Pivotzeile und bereits berechnet
        Zeile 3:      a₃₁ = - (0 / 1) = 0

Umrechnung der restlichen Werte - Spalte 2, da Spalte 1 bereits umgerechnet ist:
       Zielfunktion Spalte 2:  500 - (300 × 1) / 1 = 200
       Zeile 1 Spalte 2:       a₁₂ = 2 - 1 × 1 / 1 = 1 (mit Formel (5))
       Zeile 2 Spalte 2 gehört zur Pivotzeile und ist bereits berechnet.
       Zeile 3 Spalte 2:       a₃₂ = 3 - 0 × 1 / 1 = 3

rechte Seite:
       Zielfunktion:  -G = -(300 × 150) / 1 = -45000
       Zeile 1:       b₁ = 170 - 1 × 150 / 1 = 20 (mit Formel (6))
       Zeile 2 gehört zur Pivotzeile und ist bereits berechnet.
       Zeile 3:       b₃ = 180 - 0 × 150 / 1 = 180

[Bearbeiten] Das neue Simplex-Tableau

Nach der Umrechnung ergibt sich ein neues Simplex-Tableau:

      -----------------------------
      |  y_B     x₂   | rechte Seite
  ---------------------------------
  -G  |  -300   200  |      -45000
  ---------------------------------
  y_A  |  -1      1   |       20  = b₁
  x₁  |   1      1   |      150  = b₂
  y_C  |   0      3   |      180  = b₃

Die Variable $x 1$ ist in die Basis gerückt, die neue Nichtbasisvariable $y B$ erscheint in der Kopfzeile.

Diese Lösung bedeutet: Es werden 150 ME von Produkt 1 (rechte Seite der Zeile mit $x 1$ ) produziert. Von Produkt 2 wird nichts gefertigt ( $x 2 = 0$ ist Nichtbasisvariable). Damit erzielt die Firma einen Gesamtdeckungsbeitrag von 45.000 Euro. Maschine A steht 20 Stunden pro Monat still (sie läuft nur 150 der 170 möglichen Stunden). Maschine B hat keine Leerlaufzeit. Maschine C steht 180 Stunden still, d. h. sie wird überhaupt nicht benötigt. Dies ergibt sich auch direkt aus der Aufgabenstellung: Maschine C wird nur bei der Herstellung von Produkt 2 benötigt. Da dieses nicht gefertigt wird, braucht man Maschine C noch nicht.

[Bearbeiten] Nochmalige Verbesserung der Lösung

Da die Zielfunktion im entstandenen Simplex-Tableau noch einen positiven Koeffizienten enthält kann man die Lösung noch verbessern. Dies geschieht mittels einer weiteren Simplex-Iteration. Bei der Auswahl des Pivotelementes kommt nur Spalte $s = 2$ in Frage, da nur hier der Zielfunktionskoeffizient positiv ist. Die Pivotzeile $r$ ergibt sich aus dem Minimum der Quotienten „rechte Seite / Spalte 2“, also dem Minimum aus

       20 / 1 =  20
      150 / 1 = 150
      180 / 3 =  60

Damit ist Zeile $r = 1$ die einzige in Frage kommende Pivotzeile. Das Pivotelement ist demnach $a 12 = 1$ . Es wird die Basisvariable $y A$ gegen die Nichtbasisvariable $x 2$ ausgetauscht. Mit den gleichen Umrechnungen wie oben erhält man als neues Simplex-Tableau:

      -----------------------------
      |  y_B     y_A   | rechte Seite
  ---------------------------------
  -G  | -100   -200  |   -49000
  ---------------------------------
  x₂  |  -1      1   |       20 
  x₁  |   2     -1   |      130 
  y_C  |   3     -3   |      120

Da die Zielfunktion nun keine positiven Koeffizienten mehr enthält, ist eine optimale Lösung erreicht. Es werden 130 ME von Produkt 1 und 20 ME von Produkt 2 hergestellt. Damit erzielt die Firma einen Gesamtdeckungsbeitrag von 49.000 Euro. Maschine A und Maschine B sind voll ausgelastet. Maschine C läuft 60 Stunden und hat daher noch eine ungenutzte Kapazität von $y C = 120$ Stunden.

[Bearbeiten] Quellen

↑ Robert Bixby: Solving real-world linear programs: A decade and more of progress. In: Operations Research, Band 50, Nr. 1, 2002, S. 3–15.
↑ Harvey J. Greenberg: Klee-Minty Polytope Shows Exponential Time Complexity of Simplex Method. University of Colorado at Denver, 1997 (pdf)
↑ Martin Grötschel, Vorlesungsskript Algorithmische Diskrete Mathematik II: Lineare Optimierung (pdf)
↑ István Maros: A General Pricing Scheme for the Simplex Method. Technical Report 2001/3, Department of Computing, Imperial College, London, März 2001, ISSN 1469-4174. (pdf)
↑ Roland Wunderling: Paralleler und Objektorientierter Simplex-Algorithmus, Dissertation, TU Berlin 1996. (download)

[Bearbeiten] Literatur

George B. Dantzig: Lineare Programmierung und Erweiterungen. Springer-Verlag 1966 (Originalausgabe: Linear Programming and Extensions, Princeton University Press, ISBN 0-691-05913-6.)
V. Klee und G.J. Minty: How Good is the Simplex Algorithm? In: O. Shisha, editor, Inequalities III, Seiten 159-175. Academic Press, New York, 1972
Vašek Chvátal: Linear Programming. W. H. Freeman and Company, New York, 1983, ISBN 0-716-71587-2.
Alexander Schrijver: Theory of Linear and Integer Programming. John Wiley and Sons. 1998, ISBN 0-471-98232-6.
Wolfgang Domschke, Andreas Drexl: Einführung in Operations Research. 6. Auflage. Springer, Berlin 2005, ISBN 3-540-23431-4

[Bearbeiten] Weblinks

Linear Programming FAQ (englisch, mit kommentierten Links zu LP-Lösern)
Hilfreiche OR-Zusammenfassung der TU Kaiserslautern
Beschreibung des Simplex-Verfahrens mit praktischem Hintergrund (PDF)

Von „http://de.wikipedia.org../../../s/i/m/Simplex-Verfahren_de76.html“

Kategorie: Optimierungsalgorithmus