Zum Inhalt
Alle Apps

Simplex im Raum

Über diese App

Der Simplex-Algorithmus auf einem gläsernen Körper: Von der Startecke geht es Kante für Kante bergauf, mit Pivotspalte, Quotiententest als Strahl und mitwandernder Zielebene. Fünf Beispiele (darunter Klee-Minty, entartet, mehrdeutig), Würfeln, vier Pivotregeln im Vergleich, Tableau im Gleichschritt.

Mit Erklärmodus: Ein KI-Tutor führt dich durch die App, zeigt in der Szene, worauf es ankommt, und beantwortet deine Fragen.

Simplex als Weg über Ecken

Mit drei Variablen ist der zulässige Bereich eines linearen Programms ein konvexer Körper, ein Polyeder. Jede Ecke entspricht einer Basislösung: Die Flächen, die sich dort treffen, gehören zu den Nichtbasisvariablen, die null sind. Ein Pivotschritt ist ein Gang entlang einer Kante zur Nachbarecke. Die Pivotspalte wählt die Kante, der Quotiententest bestimmt, wie weit man gehen darf, bevor man auf eine neue Fläche stößt. Die Zielfunktion c·x = z ist eine Ebene; im Optimum berührt sie den Körper nur noch in einer Ecke oder liegt auf einer Kante oder Fläche auf.

Was die App zeigt

Der Körper ist gläsern dargestellt, der Weg des Verfahrens läuft von der Startecke im Ursprung Kante für Kante bergauf. Der Quotiententest erscheint als Strahl, die Zielebene wandert mit. Fünf Beispiele stehen bereit: Edelstein, Werkstatt, Klee-Minty-Würfel, ein entartetes Haus mit Pyramidendach und ein mehrdeutiger Fall. Mit „Neuen Körper würfeln“ entsteht ein zufälliges Problem. Vier Pivotregeln sind wählbar: Dantzig, steilste Kante, größter Zuwachs und Bland. Das Tableau läuft im Gleichschritt mit, wahlweise in Brüchen oder dezimal.

Selbst ausprobieren

Lade den Klee-Minty-Würfel und vergleiche die Schrittzahlen der Pivotregeln: Mit Dantzigs Regel läuft das Verfahren dort alle 8 Ecken ab. Im entarteten Beispiel wechselt die Basis, ohne dass sich der Punkt bewegt, weil sich an einer Ecke vier Flächen treffen. Im mehrdeutigen Fall liegt die Zielebene auf einer ganzen Fläche auf. Ein Klick auf eine andere Ecke startet das Verfahren dort, die Zielebene lässt sich durch den Körper schieben.

Häufige Fragen

Was macht der Simplex-Algorithmus geometrisch?
Er läuft entlang der Kanten des zulässigen Polyeders von Ecke zu Ecke, wobei der Zielwert bei jedem Schritt steigt oder gleich bleibt. Er stoppt an einer Ecke, von der keine Kante mehr bergauf führt. Diese Ecke ist optimal.
Was ist der Klee-Minty-Würfel?
Ein verformter Würfel, auf dem der Simplex-Algorithmus mit Dantzigs Pivotregel alle Ecken besucht. In n Dimensionen sind das 2ⁿ Ecken. Das Beispiel zeigt, dass diese Variante im schlechtesten Fall exponentiell viele Schritte braucht.
Was ist Entartung beim Simplex-Verfahren?
Eine Ecke heißt entartet, wenn sich dort mehr Flächen treffen, als die Dimension verlangt. Dann kann ein Pivotschritt die Basis wechseln, ohne dass sich der Punkt bewegt oder der Zielwert steigt. Im ungünstigen Fall kann das Verfahren kreisen; die Regel von Bland verhindert das.
Welche Pivotregeln kann ich in der App vergleichen?
Dantzig (negativster Eintrag der Zielzeile), steilste Kante im Bild, größter Gesamtzuwachs bis zur nächsten Ecke und Bland (kleinster Index). Die Zahl am Knopf zeigt jeweils, wie viele Pivotschritte die Regel braucht.

Fach: Operations Research

Mehr aus Operations Research

Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps