Simplex-Algorithmus
Über diese App
Den Simplex-Algorithmus Schritt für Schritt verstehen — Tableau, Pivotwahl und Gauß-Elimination interaktiv nachvollziehen.
Wie der Simplex-Algorithmus arbeitet
Der Simplex-Algorithmus löst lineare Optimierungsaufgaben, indem er von Ecke zu Ecke des zulässigen Bereichs wandert und dabei den Zielwert nie verschlechtert. Rechnerisch geschieht das im Simplex-Tableau. Jede Iteration hat drei Teile: Die Pivotspalte bestimmt die Variable, die neu in die Basis kommt, typischerweise die mit dem negativsten Eintrag in der Zielzeile. Der Quotiententest wählt die Pivotzeile und damit die Variable, die die Basis verlässt. Eine Gauß-Elimination macht die Pivotspalte zum Einheitsvektor. Sind alle Einträge der Zielzeile nicht negativ, ist die Lösung optimal.
Was die App zeigt
Du gibst ein Problem mit zwei Variablen ein: Zielfunktion und Nebenbedingungen. Das Tableau-Panel zeigt jede Iteration mit markierter Pivotspalte, Pivotzeile und den Quotienten. Im Hintergrund ist der zulässige Bereich als grünes Vieleck zu sehen, der aktuelle Eckpunkt als roter Punkt. Am Ende erscheint die Optimallösung mit z*, x₁ und x₂. Sind alle Einträge der Pivotspalte ≤ 0, meldet die App, dass es keine beschränkte Optimallösung gibt.
Selbst ausprobieren
Mit „Schritt“ gehst du einen Teilschritt weiter, mit „Iteration“ einen ganzen Pivotschritt, „Zurück“ macht jeden Schritt rückgängig. Verfolge, wie der rote Punkt bei jeder Iteration zur nächsten Ecke springt und der Zielwert wächst. Ändere die Zielfunktion und vergleiche, wie viele Iterationen nötig sind. Lass dir beim Quotiententest Zeit: Er sorgt dafür, dass der Punkt im zulässigen Bereich bleibt.
Häufige Fragen
- Wie funktioniert der Simplex-Algorithmus einfach erklärt?
- Er beginnt an einer Ecke des zulässigen Bereichs und geht entlang einer Kante zu einer Nachbarecke mit besserem Zielwert. Das wiederholt er, bis keine Kante mehr Verbesserung bringt. Diese Ecke ist optimal.
- Wie wählt man Pivotspalte und Pivotzeile?
- Nach der klassischen Regel ist die Pivotspalte die Spalte mit dem negativsten Eintrag in der Zielzeile (bei Maximierung in der Form z − c·x = 0). Die Pivotzeile ist die Zeile mit dem kleinsten nicht negativen Quotienten aus rechter Seite und positivem Eintrag der Pivotspalte.
- Woran erkennt man im Simplex-Tableau, dass die Lösung optimal ist?
- Wenn in der Zielzeile kein negativer Eintrag mehr steht, lässt sich der Zielwert durch keinen weiteren Pivotschritt verbessern. Dann ist die aktuelle Basislösung optimal. Ist ein Eintrag genau null, kann es weitere optimale Lösungen geben.
- Kann ich in der App Schritte zurücknehmen?
- Ja. „Zurück“ macht jeden Teilschritt rückgängig, „Reset“ startet neu. So kannst du einzelne Pivotschritte mehrfach ansehen.
Fach: Operations Research
Mehr aus Operations Research
- Big M: Nebenbedingungen an- und ausschalten
- Dijkstra-Algorithmus
- Ganzzahlig ist anders: LP gegen IP
- Konvexe Mengen, Hülle und Ecken
- Lineare Probleme anschaulich
- Nebenbedingungen verschärfen (Tightening)
- Simplex im Raum
- Tabu Search am kleinen TSP
Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps