Lexikon der Mathematik: Das Simplexverfahren
Allgemeines. Das Simplexverfahren, auch Simplexalgorithmus, 1951 eingeführt von Georg B. Dantzig, ist ein Verfahren zur Minimierung einer linearen Funktion \(x\to {c}^{T}\). x auf einem Polyeder \(M\subseteq {{\mathbb{R}}}^{n}.\)
Es sei M kompakt oder im nicht-negativen Orthanten von \({{\mathbb{R}}}^{n}\) enthalten. Dann besagt der Eckensatz, daß der Minimalwert von \(x\to {c}^{T}.\,\,x\)(falls existent) in einer Ecke von M angenommen wird. Die Idee des Simplexverfahrens besteht darin, von einer Ecke über eine Kante zu einer solchen benachbarten Ecke zu laufen, in der der Zielfunktionswert echt kleiner als in der Ausgangsecke ist. Man setzt dann das Verfahren iterativ fort, diesmal mit der neuen Ecke als Ausgangspunkt. Die Verbindungslinie der beiden beteiligten Ecken nennt man auch eine Abstiegskante.
Falls das lineare Optimierungsproblem lösbar ist, gelangt man nach endlich vielen solcher Ecken- austauschschritte zur optimalen Ecke. Die Bestimmung einer Abstiegskante zu einer (einfachheitshalber nichtentarteten) Ecke läßt sich folgendermaßen realisieren. In einer Umgebung der Ecke wird das Polyeder M in neuen (affin linearen) Koordinaten beschrieben und dadurch in einen nichtnegativen Orthanten transformiert. Dabei gehe die Ecke in den Ursprung sowie die mit ihr inzidierenden Kanten in die jeweiligen Koordinatenachsen des neuen Koordinatensystems über. Man betrachtet jetzt die partiellen Ableitungen der transformierten Zielfunktion im Ursprung. Jede Koordinatenachse, die eine negative partielle Ableitung liefert, entspricht einer Kante, über die die Zielfunktion streng monoton fällt.
Algorithmische Beschreibung
Zur algorithmischen Beschreibung betrachten wir das folgende Standard Lineare Optimierungsproblem (SLO), wobei A eine reelle (m − n)-Matrix vom Rang m sei:
Nichtentartete Ecken
Zunächst beschreiben wir den Eckenaustausch für den Fall einer nichtentarteten Ecke \(\bar{x}\) Es sind dann genau m Komponenten von \(\bar{x}\) positiv. Setze \(Z:=\{i|\bar{{x}_{i}}\gt 0\}\) und \(NZ:=\{1, 2,\mathrm{\ldots},n\}\backslash Z.\) Die Menge Z heißt Basis zur Ecke \(\bar{x}\) und die entsprechenden Komponenten von \(\bar{x}\) Basisvariablen. Ein Vektor \(x\in {{\mathbb{R}}}^{n}\) wird in den Basisanteil xZ und den Nichtbasisanteil xNZ aufgeteilt. Analog werden der Zielvektor c und die Matrix A partitioniert. Die Gleichung A · x = b geht dabei in die Gleichung
Die Komponenten des Vektors p sind gerade die partiellen Ableitungen der transformierten Zielfunktion im Ursprung. Wegen der Konvexität des Optimierungsproblems (SLO) ist die Ecke \(\bar{x}={({\bar{x}}_{Z}^{T},0)}^{T}\) genau dann optimal, wenn p ≥ 0 ist.
Zur numerischen Bestimmung von p (vgl. (4)) muß man im wesentlichen das folgende lineare Gleichungssystem lösen:
Nachdem der Index j gewählt ist, laufen wir in positiver Richtung der j-ten Koordinate und setzen
Falls \({q}^{j}\le 0,\) dann bleiben die Komponenten xk(t) nichtnegativ für alle t ≥ 0; somit ist ein Halbstrahl in der zulässigen Menge M enthalten, auf dem die Zielfunktion cT · x nicht nach unten beschränkt ist. Folglich ist (SLO) in diesem Fall nicht lösbar. Sonst ist eine Komponente \({q}_{k}^{j}\gt 0\) für ein k ∈ Z. Es wird nun das maximale t bestimmt, für das alle Basisvariablen nichtnegativ sind:
Beachte, daß \({\bar{x}}_{j}\gt 0\) und \({\bar{x}}_{\ell}=0.\) Es zeigt sich, daß die Spaltenvektoren \({a}^{k},k\in {Z}{^{\prime}}\) von A linear unabhängig sind; somit definiert die Indexmenge Z’ eine neue Ecke. Hiermit ist der Eckenaustausch beschrieben.
Wir bemerken noch, daß in der obigen Durchführung des Eckenaustauschs im wesentlichen zwei Gleichungssysteme ((5) und (6)) gelöst werden müssen. In beiden Systemen tritt die Matrix Az auf. Die neue Basismatrix AZ′ unterscheidet sich von Az nur in einer Spalte. Somit ist \({A}_{{Z}{^{\prime}}}={A}_{Z}+u\cdot {v}^{T},\)wobei u und v Vektoren aus \({{\mathbb{R}}}^{m}\) sind (Rang-1 Update). Es kann nun prinzipiell \({A}_{{Z}{^{\prime}}}^{-1}\) mit Hilfe der sogenannten Sherman-Morrison Formel berechnet werden, sofern \({A}_{Z}^{-1}\) bekannt ist.
Entartete Ecken
Im Falle einer entarteten Ecke \(\bar{x}\) sind r< m Komponenten des Vektors \(\bar{x}\) positiv. Zu den entsprechenden r linear unabhängigen Spalten von A nimmt man dann noch m-r zusätzliche Spalten dazu und formt so eine Basis Z von m linear unabhängigen Vektoren. Jetzt ist allerdings die Basis Z nicht mehr eindeutig bestimmbar. Es ist \(\bar{x}\) genau dann eine optimale Ecke, wenn es dazu eine Basis Z so gibt, daß der entsprechende Vektor p der partiellen Ableitungen (vgl. (4)) nichtnegativ ist. Falls der zu der aktuellen Basis Z gehörende Vektor p negative Komponenten hat, gelangt man wie oben beschrieben an die Stelle, wo tmax zu bestimmen ist (vgl. (7)). Es kann jetzt aber vorkommen, daß tmax = 0 ist (weil nicht alle \({\bar{x}}_{k}\gt 0\) sind). Man führt dann zwar einen Basisaustausch \(Z\to {Z}{^{\prime}}\) aus, bleibt aber in der Ecke x stehen.
So könnte es geschehen, daß man nach einigen solchen Schritten, bei denen man die Ecke \(\bar{x}\) nicht verläßt, zu einer Basis gelangt, die man bereits früher behandelt hat; man läuft dann in einen Zyklus. Mittels einer Zusatzvorschrift läßt sich das Auftreten solcher Zyklen vermeiden. Zum Beispiel könnte man bei der Auswahl der zwei entscheidenden Pivotindizes j und \(\ell \) (vgl. (8)) immer die kleinstmöglichen wählen. Dies ist die sogenannte Strategie von Bland.
Bestimmung einer Startecke
Zur Bestimmung einer Startecke betrachten wir zu (SLO) das folgende höherdimensionale Hilfsproblem (HP) :
Ohne Einschränkung der Allgemeinheit sei b ≥ 0. Man überlegt sich, daß (x, y) := (0, b) eine Ecke für (HP) ist. Ferner kann man zeigen, daß eine nach unten beschränkte lineare Funktion auf einem Polyeder ihr Minimum annimmt. Somit ist (HP) lösbar. Der Simplexalgorithmus, angewandt auf (HP), liefert somit eine optimale Ecke (\(\bar{x}\), \(\bar{y}\)). Falls \(\bar{y}\ne 0\) ist, so ist die zulässige Menge M für (SLO) leer. Falls \(\bar{y}=0\) ist, so ist \(\bar{x}\) eine Ecke für M. Falls in dieser Situation \(\bar{x}\) nichtentartet ist, dann ist die Ausgangsbasis Z für das Simplexverfahren eindeutig bestimmt, ansonsten muß man zur Bestimmung einer solchen Ausgangsbasis so vorgehen, wie es oben bereits im Falle entarteter Ecken beschrieben wurde.
Zur Komplexität des Simplexverfahrens
Im schlechtesten Falle (sogenannte worst-case Analyse) hat der Simplexalgorithmus einen exponentiellen Aufwand. Allerdings zeigte K.H. Borgwardt 1982, daß im Mittel (sogenannte average-case Analyse) ein polynomialer Aufwand erwartet werden kann. Bezüglich auch im schlechtesten Fall polynomialer Algorithmen zur Lösung linearer Optimierungsprobleme vergleiche die Beiträge zu Ellipsoidmethoden und zu Innere-Punkte Methoden.
Literatur
[1] Dantzig, G.B.: Maximization of a linear function of variables subject to linear inequalities. In Koopmann, T.C. (Hrsg.): Activity Analysis of Production and Allocation. Wiley New York, 1951.
[2] Klee, V., Minty, G.J.: How good is the simplex algorithm?. In Shisha, O.(Hrsg.): Inequalities III, Academic Press New York, 1972.
[3] Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York, 1986.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.