Lineare Programmierung erklärt
Ein Distributionszentrum plant seine Auslastung: welche Dienste in welcher Menge, damit der Deckungsbeitrag maximal wird und keine knappe Ressource (Kommissionierstunden, Lagerfläche, Rampenzeit) überschritten wird. Das ist ein Lineares Programm, und LP-Löser stecken in fast jedem Optimierungsmodell dieses Portfolios, meist als Black Box. Diese Linie öffnet die Box: Der Tableau-Simplex ist die Wurzel; die übrigen Stücke fragen, wie er wählt und wann er scheitert, wie er billiger rechnet, was die Duale sagen, wie man nach einer Änderung weiterrechnet und was ganz andere Verfahren (Ellipsoid, Innere Punkte, PDLP) leisten, bis das Crossover aus dem Inneren wieder eine Ecke macht.
Alle elf Demos rechnen auf demselben erzeugten Vehikel, der Auslastungsplanung, mit eigenen numpy-Lösern; HiGHS dient nur in den Tests als Gegenprobe. Verglichen wird in Pivots und Rechenoperationen statt in Laufzeit, und jede Demo hält auch fest, was sich nicht bestätigt hat: mehrere Vorab-Erwartungen (etwa die Zahl der Pivots je Ressource oder der Vorteil des Warmstarts) sind in der Messung gefallen.
In short: Covers linear programming (LP) solvers: the simplex method, duality and shadow prices, the ellipsoid method, interior point methods, PDLP and crossover. Interactive demos use implementations written from scratch and report measured findings.
Hintergrund zum Thema: Netzwerkdesign · Lagerlogistik.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
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.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Zum Nachlesen: erst einfach, dann fachlich
Der Simplex-Algorithmus verständlich erklärt
Warum die beste Lösung eines Planungsproblems mit knappen Ressourcen in einer Ecke liegt und wie der Simplex von Ecke zu Ecke läuft: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Die elf Stücke im Überblick
Die Linie hat eine Wurzel und vier Äste. Der Tableau-Simplex ist die Wurzel. Pivotregeln und Klee-Minty fragen, wie er wählt und wie schlecht es im schlimmsten Fall kommt; Revised Simplex und Präsolve fragen, wie er billiger und robuster rechnet; Dualität und der duale Simplex machen aus den Nebenprodukten das Thema und rechnen nach einer Änderung von der alten Basis weiter. Das Ellipsoid ist der Kontrast: polynomial, aber weit hinter dem Simplex.
Die Inneren Punkte lösen die Langsamkeit des Ellipsoids, PDLP die Faktorisierungskosten der Inneren Punkte. Beide enden im Inneren ohne Ecke und ohne Basis; das Crossover führt sie zurück zur Ecke und ist der Zusammenfluss der Linie.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Gegenstück: derselbe Zweck, andere Bauweise (kein Fix)
- übernimmt nur eine Idee
- Zusammenfluss mehrerer Stränge
Gestrichelte Doppelpfeile sind Kontraste (Ellipsoid gegen Simplex); der gepunktete Pfeil übernimmt nur die Idee (Skalierung aus dem Präsolve-Stück). Die Stücke lassen sich in beliebiger Reihenfolge lesen, ein Pfeil ist keine vorgeschriebene Reihenfolge.
Verwandt in anderen Linien
- Netzwerkfluss — Auf Netzen ist die Basis ein Spannbaum: der Netzwerksimplex der Netzwerkfluss-Linie ist derselbe Simplex, nur ohne dichtes Tableau, so wie der Tableau-Simplex ihn allgemein zeigt.
- Exakte Suche — Jeder Schnitt und jede Verzweigungsschranke macht die alte Basis primal unzulässig, und genau dort rechnet der duale Simplex von der alten Basis weiter; die Schranken selbst zeigen die Cutting-Planes-Demo und Branch & Cut der Exakte-Suche-Linie.
- Graphen und Netzwerke — Warum echte Löser dünn statt dicht rechnen, zeigt die Bandbreite einer Matrix: die Bandbreite-Demo der Graphen-und-Netzwerke-Linie misst, wie nah Cuthill-McKee an das Optimum kommt. Es ist dieselbe Auffüll-Motivation, die Revised Simplex und die Innere-Punkte-Demo hier zu einer dünnbesetzten Faktorisierung zwingt.
- Mehrkriterien-Ranking — Zwei Stücke der Linie Mehrkriterien-Ranking sind angewandte LPs: Die DEA löst je Alternative ein LP, dessen Multiplikatoren Schattenpreise sind, und die robuste ordinale Regression fragt per LP nach allen verträglichen Wertfunktionen.
Tableau-Simplex: von Ecke zu Ecke, Pivot für Pivot
Verfolgen Sie, wie der Simplex ein Lineares Programm löst, indem er von Ecke zu Ecke des zulässigen Bereichs läuft und bei jedem Pivot eine Variable der aktuellen Ecke austauscht. Ein Schritt-Slider durch Zeichnung und Tableau zeigt jeden Pivot einzeln. Der Haken: Auf Zufallsinstanzen mit m = n = 60 sind es im Median 32,5 Pivots, doch jeder rechnet im dichten Tableau die ganze Tabelle neu (14 641 Operationen).
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Pivotregeln und Entartung: klügere Wahl, seltene Zyklen
Sehen Sie, wie fünf Regeln unterschiedlich wählen, welche Variable beim Pivot eintritt. Ein Vergleich auf derselben Instanz und das Beispiel von Beale zeigen live, was die klügere Wahl spart und ob der Simplex an einer entarteten Ecke im Kreis läuft. Der Haken: Kreisen gibt es nur auf diesem konstruierten Beispiel, in 2000 erzeugten Instanzen kein einziges Mal, und auf dem Lehrbuchbeispiel ist Steepest Edge sogar teurer als Dantzig.
Demo starten →Klee-Minty: der Würfel, der Dantzig überlistet
Sehen Sie, wie die Dantzig-Regel auf einem verformten Würfel von Ecke zu Ecke über alle Ecken läuft. Ein Regelvergleich auf demselben Würfel zeigt live, wie viele Pivots jede Regel braucht. Der Haken: Bei n = 14 sind es genau 16 383 Pivots, aber der Würfel ist ein schlimmster Fall für die Dantzig-Regel, nicht für den Simplex: Steepest Edge löst ihn mit einem einzigen Pivot.
Demo starten →Revised Simplex: derselbe Pfad, ein anderer Aufwand
Sehen Sie, wie der Revised Simplex dieselben Pivots wie das Tableau macht, aber die Ausgangsmatrix unverändert hält und je Pivot nur rechnet, was dieser Pivot braucht. Ein Vergleich der Rechenoperationen zeigt live, wo das lohnt. Der Haken: Gegen das dichte Tableau gewinnt er klar (0,07 der Operationen bei Zufall 60 × 480), zählt man das Tableau aber nur auf Nichtnullen, verliert er bei kurzen Läufen.
Demo starten →Präsolve und Skalierung: Aufräumen vor dem Lösen
Sehen Sie, wie Präsolve ein verschmutztes LP vor dem Lösen aufräumt, etwa doppelte und überflüssige Zeilen, und Skalierung Daten in sehr verschiedenen Einheiten angleicht. Ein Regler für Verschmutzung und Einheiten-Spanne zeigt live, was beides bringt. Der Haken: Präsolve allein repariert die Skalierung nicht, denn bei Spanne 10¹⁴ löst der einfache Simplex nur 3 von 5 Instanzen richtig; mit geometrischer Skalierung oder Zweierpotenzen sind es alle 5.
Demo starten →Dualität und Sensitivität: Schattenpreise gelten nur im Bereich
Verfolgen Sie, was ein Schattenpreis sagt: den Wert einer zusätzlichen Einheit einer knappen Ressource, etwa einer Stunde mehr Kommissionierung. Ein Regler für die Erweiterung der Lagerfläche vergleicht die Vorhersage mit der Neulösung. Der Haken: Der Schattenpreis ist eine Steigung und gilt nur in einem Bereich; bei +75 % Lagerfläche sagt er einen Gewinn von 75 voraus, die Neulösung findet 8,75.
Demo starten →Dualer Simplex: von der alten Basis weiterrechnen
Ändern Sie eine Kapazität und sehen Sie, wie der duale Simplex von der alten Basis weiterrechnet, statt neu anzufangen: Die alte Lösung ist dann nicht mehr zulässig, erfüllt aber die Optimalitätsbedingungen noch. Ein Vergleich warm gegen kalt zählt die Pivots beider Wege. Der Haken: Der Warmstart ist nicht immer besser, bei einem starken Schnitt (Zufall 10 × 10) ist der Neustart in 26 % der Fälle nicht schlechter.
Demo starten →Ellipsoid-Methode: polynomial, aber weit hinter dem Simplex
Sehen Sie, wie ein Ellipsoid, das die Lösung sicher enthält, Iteration für Iteration durch Nebenbedingungen angeschnitten und verkleinert wird, mit nachweislich polynomialem Aufwand. Ein Vergleich mit dem Simplex zählt die Operationen. Der Haken: Auf Zufallsinstanzen liegt es bis n = 20 weit zurück (bei n = 20 das 1650-Fache), nur auf dem Klee-Minty-Würfel gewinnt es, und das nur gegen die Dantzig-Regel.
Demo starten →Innere Punkte: durch das Innere, in wenigen Iterationen
Sehen Sie, wie Innere-Punkte-Verfahren nicht am Rand entlang, sondern mitten durch die zulässige Menge dem Optimum entgegenlaufen, wobei jede Iteration ein lineares Gleichungssystem löst. Vier Varianten treten auf derselben Instanz an. Der Haken: Mehrotra braucht bei n = 40 nur 9 Iterationen, doch auf Zufallsinstanzen bleibt der Simplex im Operationsmodell vorn (bei n = 40 ist das Innere 20,0-mal so teuer).
Demo starten →PDLP: fünf Bausteine machen PDHG brauchbar
Sehen Sie, wie PDLP große LPs ohne Zerlegen von Matrizen löst, nur mit Matrix-Vektor-Produkten, was bei riesigen dünnen Modellen die teure Zerlegung vermeidet. Fünf Schalter für die Bausteine zeigen, was jeder bringt. Der Haken: Die einfache Grundform braucht auf einer Zufallsinstanz der Größe 12 × 12 bis zur gewünschten Genauigkeit 12 888 Iterationen, PDLP 152, doch im gemessenen Bereich schlägt PDLP den Simplex im Operationsmodell nie.
Demo starten →Crossover: aus dem Inneren zurück zur exakten Ecke
Geben Sie dem Verfahren eine Näherung aus dem Inneren und sehen Sie, wie Crossover daraus eine Basis erkennt und mit wenigen Simplex-Pivots zur exakten Ecke aufräumt. Ein Vergleich mit dem Simplex allein zählt die Operationen. Der Haken: Auf Zufallsinstanzen lohnt es sich im Operationsmodell nie (bei 40 × 40 das 15,2-Fache des Simplex), auf dem Klee-Minty-Würfel dagegen schon: bei n = 14 ein Pivot statt 16 383.
Demo starten →Welches Stück passt zu meiner Aufgabe?
Ein Entscheidungsbaum über alle elf Stücke, entlang der Frage, was an der Aufgabe im Mittelpunkt steht: den Simplex verstehen, ein großes LP lösen, Preise und Änderungen auswerten oder aus einer Näherung eine Ecke gewinnen. Alle Antworten stützen sich auf Messungen in den Demos.
Welches Stück passt zu meiner Aufgabe?
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Was der Baum nicht zeigt: Die Stücke sind nicht alle gleichrangig (das Ellipsoid ist ein Kontrast, kein Verfahren für die Praxis), und die Antworten gelten für die erzeugten Instanzen der Demos und die dort gemessenen Größen; die eigenen Löser sind dicht und klein, kein Ersatz für einen echten Löser wie HiGHS.
Weitere Linien in diesem Bereich
Exakte Suche
Bewiesen beste statt nur guter Lösungen: zwei Linien, Rucksack und Cutting Stock, von Branch & Bound bis Column Generation und Branch & Price.
Nichtlineare Optimierung
Wie findet man ein Minimum, wenn nichts linear ist? Acht Stücke vom ersten Schritt bergab über Krümmung und Nebenbedingungen bis zur Brücke ins Deep Learning, jedes mit gemessenem statt behauptetem Befund.
Populations-Metaheuristiken
Wie durchsucht eine ganze Population den Lösungsraum? Elf Verfahren von der Kreuzung über Kovarianzmatrizen bis zu Pheromonspuren, jedes mit seiner gemessenen Grenze.
Trajektorien-Metaheuristiken
Wie kommt eine einzelne Lösung über ihr erstes lokales Optimum hinaus? Zwölf Verfahren von Verschlechterungen akzeptieren bis Destroy-and-Repair, jedes mit seiner gemessenen Grenze.
Heuristische Baumsuche
Was bleibt von der Suche, wenn man das Optimum nicht abwarten kann? Acht Verfahren von der gierigen Suche bis Monte Carlo Tree Search, jedes mit seiner gemessenen Grenze.
Novelty Search und Quality-Diversity
Ein Hof-Roboter im täuschenden Labyrinth, zwölf Stücke: von der Sackgasse der Fitness über Novelty Search und MAP-Elites bis zu Go-Explore, Routing und POET.
Standortplanung
Welche Standorte eröffnen, wenn jeder Kunde zum nächsten offenen geht? Sechs Stücke von der einfachen Fixkosten-Entscheidung über Kapazität, Maximum statt Summe und Lagerbestand bis zum Wettbewerb zweier Spieler und zum Hub mit Rabatt.
Klassische Scheduling-Theorie
Ein wachsendes Beispiel von einer Maschine bis zum allgemeinen Ressourcenmodell: elf Stücke, jedes hebt genau eine Annahme des vorigen auf.
Warteschlangentheorie und Simulation
Ein Terminal-Gate, dreizehn Stücke und ein Zusatzstück: jedes hebt genau eine Annahme der Formel davor auf, bis zum Netz aus Gate, Kran und Stapel und seinem Ersatzmodell.
Mittelwerte und Lagemaße
Welche Zahl steht für die Mitte der Daten, wie genau rechnet man sie, und was geschieht bei Ausreißern, Quotienten, Uhrzeiten und Standorten in der Ebene? Sieben Stücke vom Mittelwert bis zur Mitte im Raum.
Optimierung unter Unsicherheit
Eine Kapazität, die vor der unbekannten Nachfrage gewählt wird, sechs Stücke: vom Wert der Information über Stichprobe, CVaR, Robustheit und Garantie bis zur rollierenden Planung.
Bayessche Optimierung und Gauß-Prozesse
Eine teure Simulation, sieben Stücke: vom Gauß-Prozess und der erwarteten Verbesserung über Rauschen und Nebenbedingungen bis zu hohen Dimensionen, parallelen Läufen und mehreren Genauigkeiten.
Mehrkriterien-Ranking
Eine neutrale Entscheidungsmatrix, fünfzehn Stücke: von der Pareto-Dominanz über Gewichte, AHP, TOPSIS und Outranking bis zu unsicheren Gewichten, DEA, Gruppen und dem Verfahrensvergleich.
Komplexitätsklassen
Was sagt es aus, wenn ein Problem als NP-schwer gilt, und welcher Ausweg passt zu welchem Grund der Härte? Zehn Stücke über Reduktionen, typische Instanzen, große Zahlen, Garantien, Parameter, Zufall, Zählen, Spiele und lokale Optima.