Der Simplex-Algorithmus verständlich erklärt

Wer knappe Mittel auf mehrere Aufgaben verteilen muss, sucht die Verteilung mit dem größten Gewinn. Sie liegt in einer Ecke des Bereichs aller erlaubten Verteilungen, und der Simplex-Algorithmus findet sie, indem er von Ecke zu Ecke läuft und anhält, wenn keine Nachbarecke besser ist. Diese Seite erklärt das zuerst an einem Bild ohne Formeln und danach für Fachleute mit Modell, Formeln, Messwerten und Grenzen. Die Demo lässt Sie den Weg Schritt für Schritt verfolgen.

Zuletzt aktualisiert: 28. Oktober 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Ein Grundstück am Hang

Stellen Sie sich ein Distributionszentrum vor, das zwei Dienste anbietet, etwa Express-Pakete und Palettenversand. Jeder Dienst bringt je Einheit einen Gewinn, den Deckungsbeitrag (was nach Abzug der direkten Kosten übrig bleibt). Er braucht aber knappe Mittel: Zeit an der Rampe, Arbeitsstunden beim Kommissionieren (Zusammenstellen der Ware für einen Auftrag), Platz im Lager. Von jedem Mittel gibt es nur einen festen Vorrat. Die Frage lautet: Wie viel soll von jedem Dienst angeboten werden, damit der Gewinn möglichst groß wird und kein Vorrat überschritten wird?

Stellen Sie sich dazu ein Grundstück vor. Jeder Punkt darin steht für eine Mischung der beiden Dienste: Je weiter nach Osten, desto mehr vom einen, je weiter nach Norden, desto mehr vom anderen. Jeder Vorrat zieht einen Zaun, den die Mischung nicht überschreiten darf. Was innerhalb der Zäune liegt, ist machbar; dieses Grundstück heißt zulässiger Bereich. Es liegt an einem gleichmäßig geneigten Hang: Je höher ein Punkt liegt, desto größer der Gewinn. Gesucht ist der höchste Punkt innerhalb der Zäune. Eine solche Aufgabe nennen Fachleute ein Lineares Programm, weil Gewinn und Verbrauch im gleichen Verhältnis zur Menge wachsen.

Der höchste Punkt sitzt in einer Ecke

Auf einem gleichmäßig geneigten Hang gibt es mitten im Grundstück keine Kuppe. Wer irgendwo im Inneren steht, kann immer noch ein Stück bergauf gehen. Erst ein Zaun hält ihn auf. Am Zaun entlang geht es weiter bergauf, bis der Weg an einer Ecke endet, wo zwei Zäune zusammentreffen.

Daraus folgt: Man muss das Innere des Grundstücks nicht absuchen. Es genügt, die Ecken zu betrachten. Verläuft ein Zaun zufällig genau quer zum Gefälle, liegt die ganze Kante gleich hoch; auch dann ist eine ihrer Ecken mindestens so gut wie jeder andere Punkt.

Von Ecke zu Ecke

Das Simplex-Verfahren nutzt genau das. Es beginnt in einer Ecke, im einfachsten Fall dort, wo noch nichts angeboten wird. Dann schaut es auf die Nachbarecken, die man an einem Zaun entlang erreicht, und geht zu einer, die mehr Gewinn bringt. Einen solchen Schritt nennt man Pivot: Man löst sich an der Ecke von einem der beiden Zäune und läuft am anderen entlang bis zur nächsten Ecke. Das Verfahren hört auf, wenn von der aktuellen Ecke aus keine Nachbarecke besser ist.

Warum darf es dann aufhören? Angenommen, irgendwo im Grundstück läge ein höherer Punkt. Das Grundstück hat keine Einbuchtungen, also könnten Sie von Ihrer Ecke geradlinig dorthin gehen, ohne einen Zaun zu überschreiten. Auf einem gleichmäßigen Hang ginge es auf diesem ganzen Weg bergauf, schon im ersten Schritt. Dieser Schritt zeigt in eine Richtung zwischen den beiden Zäunen der Ecke. Das kann nur bergauf gehen, wenn mindestens einer der beiden Zäune selbst bergauf führt. Dann wäre aber eine Nachbarecke besser gewesen. Gibt es keine, gibt es auch keinen höheren Punkt irgendwo sonst. In der Zeichnung der Demo sieht man den Weg als orangefarbene Linie von Ecke zu Ecke.

Mehr als zwei Dienste und die Rechentabelle

Ein Grundstück lässt sich nur bei zwei Diensten zeichnen. Bei vielen Diensten und vielen Mitteln gibt es nichts mehr zu zeichnen, aber die Idee bleibt dieselbe. Die Rechnung führt dann eine Tabelle mit, das Tableau: Darin steht, welche Grenzen an der aktuellen Ecke gelten und was ein Schritt zur Nachbarecke bringen würde. Bei jedem Pivot wird diese Tabelle neu gerechnet.

Manchmal ist der Startpunkt, an dem nichts angeboten wird, gar nicht erlaubt, etwa weil ein Mindestbedarf erfüllt werden muss. Dann sucht das Verfahren zuerst irgendeine erlaubte Ecke und beginnt erst von dort mit dem Verbessern. In den Beispielen der Demo braucht der Simplex weniger Pivots als es knappe Mittel gibt, solange der Startpunkt erlaubt ist. Muss erst eine erlaubte Ecke gesucht werden, braucht er mindestens so viele. Die Zahlen stehen im Fachteil.

Wie ernst ist das Modell zu nehmen?

Die Demo ist ein stark vereinfachtes Modell. Die Aufgaben sind erzeugt, nicht aus einem echten Distributionszentrum gemessen. Gewinn und Verbrauch wachsen genau im gleichen Verhältnis zur Menge, es gibt keine Mengenrabatte und keine ganzen Stückzahlen. Echte Aufgaben dieser Art sind größer und stärker strukturiert. Die Demo zeigt, wie der Simplex arbeitet, nicht wie ein bestimmter Betrieb planen sollte.

Was Sie mitnehmen: An der gefundenen Ecke sehen Sie, welche Vorräte voll ausgeschöpft sind. Nur bei diesen Engpässen würde zusätzliche Kapazität den Gewinn steigern, jedenfalls bei kleinen Änderungen. Vorräte, von denen Rest übrig bleibt, begrenzen in diesem Modell nichts. Das gilt nur, solange das Modell stimmt: Verbrauch und Gewinn müssen wirklich im gleichen Verhältnis zur Menge wachsen und die Vorräte richtig angesetzt sein.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst die formale Beschreibung der Demo zusammen; die vollständige Fassung steht im Expander „📐 Mathematische Formulierung“ der Demo.

• Modell: Auslastungsplanung eines Distributionszentrums als Lineares Programm \(\max c^\top x\) mit Bedingungen \(A x \le / \ge / = b\) und \(x \ge 0\). Eine Basis liefert eine Basislösung; ist sie zulässig, entspricht sie einer Ecke der Zulässigkeitsmenge. Jeder Pivot tauscht eine Variable der Basis aus.
• Verfahren: Standardform mit Schlupf-, Überschuss- und künstlichen Variablen, dichtes Tableau mit Zielzeile \(r = z - c\), Dantzig-Regel (kleinstes \(r\), bei Gleichstand der kleinste Index), Quotiententest mit Toleranz, Zwei-Phasen-Start, Schattenpreise aus der Zielzeile und die Bland-Regel als Notbremse gegen Zyklen.
• Instanzen: ein Lehrbuchbeispiel und drei feste Sonderfälle (entartet, unzulässig, unbeschränkt) sowie drei regelbare Zufallstypen: nur ≤-Bedingungen, eine Mischung mit ≥- und =-Bedingungen und ein Typ mit Ressourcen, die Summen anderer Ressourcen sind.
• Aufwand: Gezählt werden die Gleitkomma-Operationen des dichten Tableaus, keine Laufzeit. Die Demo prüft ihr Ergebnis außerdem ohne fremden Löser (Primal- und Dual-Zulässigkeit, Lücke zwischen Zielwert und dualem Wert).

Die Formeln

Das Lineare Programm in Standardform mit Schlupf: Zielfunktion und Nebenbedingungen.

\[\max\; c^\top x\]

\[A x + s = b,\; x, s \ge 0\]

Eine Basis \(B\) aus \(m\) linear unabhängigen Spalten legt die Basislösung fest; die übrigen Variablen sind null (\(x_N = 0\)). Ist \(x_B \ge 0\), ist sie zulässig und eine Ecke des Polyeders \(\{x \ge 0 : A x \le b\}\):

\[x_B = B^{-1} b\]

Das Tableau enthält \(B^{-1}[A\;|\;b]\) und die Zielzeile mit den reduzierten Kosten. Sind alle \(r_j \ge 0\), ist die Basislösung optimal; eine Spalte mit \(r_j < 0\) würde den Zielwert erhöhen:

\[r_j = c_B^\top B^{-1} a_j - c_j\]

Tritt eine Spalte \(j\) ein, bestimmt der Quotiententest die austretende Zeile \(i^{*}\): die Zeile, die zuerst bindend wird, bevor eine Bedingung verletzt wäre. Gibt es keinen positiven Eintrag \(t_{ij}\), ist das Problem unbeschränkt.

\[\arg\min_{i:\,t_{ij} > 0} t_{i,\mathrm{rhs}} / t_{ij}\]

Im Optimum enthält die Zielzeile unter den Schlupfspalten die Schattenpreise \(y = c_B^\top B^{-1}\), und es gilt starke Dualität \(c^\top x = b^\top y\). Ein Pivot im dichten Tableau mit \(m\) Zeilen und \(N\) Spalten kostet in der Zählung der Demo:

\[(N + 1) + 2 m (N + 1)\]

Ist der Ursprung nicht zulässig (Bedingungen mit ≥ oder =), löst Phase 1 ein Hilfsproblem mit künstlichen Variablen: Sie minimiert deren Summe. Endet sie bei null, liefert die Endbasis eine zulässige Ecke für Phase 2; sonst ist die Instanz unzulässig.

Befunde

Alle Zahlen stammen aus der README der Demo (und stehen in deren Tests) und gelten für das erzeugte Distributionszentrum. Die Zufallsbefunde sind Mediane über 30 Instanzen je Größe (Zufalls-Seeds 200000–200029) bzw. über fünf feste Instanzen (Zufalls-Seeds 100000–100004); die Rechnung ist vollständig deterministisch.

Frage	Befund
Stimmt der Löser?	Das Optimum stimmt mit HiGHS überein (nur als Gegenprobe in den Tests) auf über 1000 Instanzen: 720 erzeugte, 300 kleine Zufalls-LPs mit gemischten Vorzeichen (dabei alle drei Status) und 200 konstruierte unzulässige und unbeschränkte. Jedes Ergebnis ist primal und dual zulässig, mit starker Dualität und komplementärem Schlupf.
Wie läuft das Lehrbuchbeispiel?	Zwei Dienste (Deckungsbeitrag 3 und 5), drei Ressourcen: Ecken (0, 0) → (0, 6) → (2, 6), 2 Pivots, Optimum 36. Alle drei Tableaus sind gegen eine von Hand gerechnete Tabelle geprüft; die Schattenpreise sind 0, 1,5 und 1.
Wie viele Pivots bei lauter ≤-Bedingungen?	Bei m = n = 5/10/20/40/60 im Median 3/5,5/10,5/20/32,5, also etwa 0,5 bis 0,6 je Ressource. Es gibt keine Phase 1 und keine Gleichstände.
Und mit ≥- und =-Bedingungen?	Bei m = n = 5/10/20/40/60 im Median 5/13/38/105,5/199, also 1,0 bis 3,3 je Ressource, mit der Größe steigend. 25 bis 39 % der Pivots gehören zur Phase 1 (bei m = n = 60: 25 % von 199).
Führen Gleichstände in den Stillstand?	Bei Ressourcen, die Summen anderer sind, treten im Quotiententest in 16,7/36,4/15,8 % der Pivots Gleichstände auf (m = n = 10/20/40), aber kein einziger Nullschritt. Nullschritte gibt es nur in den Mischinstanzen und selten: 22 in gut 11 000 Pivots auf 720 Instanzen, 19 davon in Phase 1.
Was kostet ein Pivot?	Im dichten Tableau (Spalten + 1) · (1 + 2 m) Rechenoperationen, exakt nachgezählt: 441 bei m = n = 10, 1681 bei m = n = 20 und 14 641 bei m = n = 60. Jeder Pivot rechnet alle Einträge neu.

Eine Vorab-Hypothese des Autors, der Simplex brauche 1 bis 3 Pivots je Ressource, ist auf Zufallsinstanzen mit lauter ≤-Bedingungen widerlegt; nur die Mischinstanzen mit Phase 1 liegen darüber.

Grenzen

• Kein schlimmster Fall: Der exponentielle Fall (Klee-Minty) kommt nicht vor, weil die Instanzen zufällig sind; er ist Thema eines Folgestücks der Reihe.
• Kein Stillstand heißt nicht kein Zyklus: Dass der Zufall keine Nullschritte in den Gleichstands-Instanzen findet, zeigt nicht, dass es keine Zyklen gibt, sondern nur, dass sie hier nicht aufgetreten sind.
• Nur die Dantzig-Regel: Regelvergleiche, Steepest Edge, Bland und Zyklen gehören zu einem Folgestück; die Regel ist in der Demo kein Regler.
• Dichtes Tableau: Jeder Pivot rechnet alle Einträge neu; das behebt der Revised Simplex in einem Folgestück. Der Aufwand ist ein Näherungsmaß, keine Laufzeit.
• Numerik: Feste Toleranz, keine Skalierung, kein Präsolve. Auf den erzeugten, gut skalierten Instanzen stimmt jedes Ergebnis mit HiGHS überein; auf echten, schlecht skalierten Daten würde das nicht genügen.
• Synthetische Instanzen: nichtnegative Verbrauchskoeffizienten und eine dichte Gesamtkapazität; echte LPs sind dünner, größer und strukturierter.
• Keine ganzzahligen Programme: Ganzzahligkeit gehört nicht in diese Demo; die Schattenpreise sind nur eine Vorschau auf das Dualitätsstück.

Quellen

• Dantzig, G. B. (1951): Maximization of a linear function of variables subject to linear inequalities. In T. C. Koopmans (Hrsg.), Activity Analysis of Production and Allocation, 339–347. Wiley.
• Klee, V., & Minty, G. J. (1972): How good is the simplex algorithm? In O. Shisha (Hrsg.), Inequalities III, 159–175. Academic Press (nur als Ausblick auf den schlimmsten Fall).
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/tableau-simplex-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen; die Literaturhinweise stammen aus der README der Demo. Dass bei einem zulässigen, beschränkten Linearen Programm eine optimale Lösung in einer Ecke liegt, ist Standardwissen der Linearen Programmierung und steht nicht in der README. Das Gleiche gilt für die Aussage, dass zusätzliche Kapazität nur bei voll ausgeschöpften Ressourcen den Gewinn steigert (Schattenpreis null bei Ressourcen mit Rest).