Simplex erklärt: Der beste London-Paris-Urlaub

Eleanor Finch

Hey everyone, welcome to the show! Ich bin Eleanor Finch. Und heute starten wir mit einer Frage, die Sie sich vielleicht auch schon mal vor dem Urlaub gestellt haben: [warmly] Wie plane ich die perfekte Städtereise, wenn die Zeit knapp und das Geld limitiert ist? Stellen wir uns vor, Sie haben genau 7 Tage Zeit und ein Spesenbudget von 400 Pfund. Zur Auswahl stehen zwei absolute Klassiker: London und Paris.

Eleanor Finch

Ein Tag in London kostet Sie 80 Pfund, bringt Ihnen aber einen persönlichen Zufriedenheits- oder Präferenzwert von 8. Paris ist mit 40 Pfund pro Tag deutlich günstiger, liefert Ihnen aber immer noch einen stolzen Präferenzwert von 6. Das ist unser echtes Lebensproblem. Und genau dieses Problem übersetzen wir jetzt in die Sprache der Mathematik -- in ein lineares Programm. [matter-of-fact]

Eleanor Finch

[measured] Als Erstes brauchen wir die Entscheidungsvariablen. Nennen wir x1 die Anzahl der Tage in London und x2 die Anzahl der Tage in Paris. Was genau wollen wir? Wir wollen unser Glück maximieren! Das ist unsere Zielfunktion: Wir wollen den Wert F gleich 8 mal x1 plus 6 mal x2 maximieren. Das ist das große Ziel.

Eleanor Finch

Aber natürlich können wir nicht unendlich lange reisen oder unendlich viel Geld ausgeben. Hier kommen die Restriktionen oder Nebenbedingungen ins Spiel. Die erste ist die Zeit: x1 plus x2 muss kleiner oder gleich 7 Tage sein. Die zweite ist das Budget: 80 mal x1 für London plus 40 mal x2 für Paris muss kleiner oder gleich 400 Pfund sein. Und natürlich können wir keine negativen Tage verreisen -- also gilt die Nichtnegativitätsbedingung: x1 und x2 müssen größer oder gleich null sein. [pauses]

Eleanor Finch

[chuckles] Klingt logisch, oder? Aber um das Ganze mit dem Simplex-Verfahren mathematisch zu lösen, stören uns diese "kleiner-gleich"-Ungleichungen. Der Simplex liebt Gleichungen! Also führen wir einen genialen Trick ein: sogenannte Schlupfvariablen. Denken Sie bei einer Schlupfvariable einfach an ungenutzte Kapazitäten.

Eleanor Finch

Für die Zeitbedingung führen wir s1 ein. Unsere neue Gleichung heißt: x1 plus x2 plus s1 ist gleich 7. Wenn s1 am Ende zum Beispiel 2 ist, bedeutet das einfach, dass wir 2 Tage ungenutzt lassen und symbolisch "zu Hause bleiben". Für das Budget führen wir s2 ein: 80 x1 plus 40 x2 plus s2 ist gleich 400. Wenn s2 größer als null ist, bleibt Geld im Portemonnaie übrig. [reflective]

Eleanor Finch

[pauses] Jetzt sind wir bereit für das Starttableau. Stellen Sie sich vor, wir starten unsere Planung in Gedanken komplett auf dem Sofa -- wir bleiben also symbolisch erst mal ganz zu Hause. Das bedeutet, unsere echten Urlaubstage x1 und x2 sind null. Sie sind unsere Nichtbasisvariablen. Die Schlupfvariablen s1 und s2 dagegen übernehmen den vollen Wert unserer Kapazitäten: s1 ist gleich 7 und s2 ist gleich 400. Sie sind unsere Basisvariablen.

Eleanor Finch

Unser aktueller Zielfunktionswert F ist in diesem Moment natürlich genau null. Wir haben keinen Urlaub gemacht, also auch kein Urlaubsglück. In der Zielfunktionszeile -- oft auch F-Zeile genannt -- steht mathematisch umgeformt: F minus 8 x1 minus 6 x2 ist gleich null. Und diese negativen Werte vor den Variablen zeigen uns sofort: Da ist noch verdammt viel Luft nach oben! [excited]

Eleanor Finch

[thoughtfully] Bevor wir jetzt wild rechnen, lassen Sie uns das Ganze kurz visualisieren. Wenn wir diese Bedingungen zweidimensional aufzeichnen, entsteht ein geometrischer Körper -- ein sogenanntes Polyeder, in unserem Fall eine flache, mehreckige Fläche. Und jetzt kommt eine fundamentale Erkenntnis der linearen Optimierung: Die optimale Lösung liegt niemals irgendwo verloren in der Mitte der Fläche. Sie befindet sich immer auf einer der Ecken!

Eleanor Finch

Das Simplex-Verfahren ist im Grunde ein geometrischer Tanz auf diesen Ecken. Wir starten an der Ecke "Sofa" -- also am Nullpunkt -- und wollen uns nun zur nächsten, besseren Ecke hangeln. Aber in welche Richtung gehen wir zuerst? [curious]

Eleanor Finch

[excited] Dafür bestimmen wir die Pivotspalte. Wir schauen in die Zielfunktionszeile nach dem steilsten Anstieg, also dem negativsten Koeffizienten. Da steht minus 8 bei x1 -- dem London-Urlaub -- und minus 6 bei x2, Paris. Da die minus 8 noch negativer ist, verspricht uns London pro Tag den größeren Glückszuwachs. x1 wird also unsere Pivotspalte. Diese Variable will in die Basis aufgenommen werden.

Eleanor Finch

Aber wie viele Tage London können wir uns maximal erlauben, bevor uns Zeit oder Geld ausgehen? Das ermitteln wir über den sogenannten Engpass-Quotiententest, auch Minimum-Ratio-Test genannt. Wir teilen die rechte Seite durch die Werte in der Pivotspalte. [deliberate]

Eleanor Finch

Für die Zeit gilt: 7 Tage geteilt durch 1 ist gleich 7. Für das Budget gilt: 400 Pfund geteilt durch 80 Pfund pro Tag ist gleich 5. Der kleinere Wert gewinnt, denn er zeigt uns den härtesten Engpass. Das Budget limitiert uns hier zuerst! Die Budgetzeile wird also unsere Pivotzeile. Und der Schnittpunkt von Pivotspalte und Pivotzeile liefert uns das Pivotelement: die Zahl 80.

Eleanor Finch

[measured] Jetzt führen wir den mathematischen Basistausch durch. Das Ziel ist es, das Pivotelement durch Zeilenoperationen auf den Wert 1 zu bringen und alle anderen Werte in dieser Spalte zu nullen. Wir teilen also die gesamte Budgetzeile durch 80. Dadurch wird x1 zu einer Basisvariablen mit dem Wert 5.

Eleanor Finch

Wenn wir diese neue Zeile mit den anderen Zeilen verrechnen, wandern wir mathematisch zur nächsten Ecke unseres geometrischen Körpers: 5 Tage Londonurlaub, die restlichen 2 Tage verbringen wir zu Hause, Paris wird gar nicht besucht, und unser Budget ist komplett aufgebraucht. Unser Urlaubsglück F ist damit von null auf stolze 40 gestiegen! [laughs] Ein riesiger Fortschritt im Vergleich zum Sofa.

Eleanor Finch

[calm] Aber sind wir damit schon am Ziel? Wenn wir unser neues Tableau betrachten, sehen wir in der F-Zeile unter der Spalte für Paris immer noch einen negativen Wert: minus 2. Das bedeutet, jeder Tag in Paris, den wir jetzt noch irgendwie einbauen, würde unser Glück um weitere 2 Einheiten steigern. Wir müssen also einen zweiten Simplex-Schritt machen.

Eleanor Finch

Wir wiederholen das Spiel: Paris, also x2, wird die neue Pivotspalte. Durch den Engpass-Quotiententest stellen wir fest, dass uns diesmal die Zeit -- also s1 -- beschränkt. Nach den nächsten Zeilenoperationen erreichen wir schließlich das finale Tableau. [rising excitement]

Eleanor Finch

Und siehe da: Auf der rechten Seite lesen wir ab: x1 ist gleich 3 und x2 ist gleich 4. Das bedeutet: 3 Tage London und 4 Tage Paris! Die Schlupfvariablen s1 und s2 sind beide null -- wir haben also weder Zeit noch Geld übriggelassen. Und unser maximales Urlaubsglück liegt jetzt bei 48! Da in der gesamten F-Zeile keine negativen Werte mehr stehen, wissen wir absolut sicher: Das ist das globale Optimum. Besser wird es nicht mehr.

Eleanor Finch

[thoughtfully] Aber das Simplex-Tableau verrät uns noch viel mehr, wenn wir zwischen den Zeilen lesen. Es liefert uns die sogenannten reduzierten Kosten und die Schattenpreise.

Eleanor Finch

Die reduzierten Kosten zeigen uns, was es uns "kostet", eine unvorteilhafte Entscheidung zu treffen. Wenn wir zum Beispiel unbedingt einen Tag mehr in London verbringen wollten, als es das Optimum vorsieht, müssten wir dafür Paris-Tage opfern und unser Gesamtnutzen würde sinken. [sober]

Eleanor Finch

Noch spannender sind die Schattenpreise, die wir direkt unter den Schlupfvariablen im Optimaltableau ablesen können. Sie beschreiben den Grenznutzen einer zusätzlichen Ressourceneinheit. Unser Schattenpreis für die Zeit beträgt hier beispielsweise 4. Das bedeutet: Wenn wir unseren Urlaub um nur einen einzigen Tag verlängern könnten -- also auf 8 Tage -- würde unser Urlaubsglück sofort um 4 Einheiten auf 52 steigen! Der Schattenpreis für das Budget zeigt uns analog, wie viel ein zusätzliches Pfund wert wäre. Es sind die verborgenen ökonomischen Werte unseres Modells. [excited]

Eleanor Finch

[measured] Zum Abschluss sollten wir noch erwähnen, dass die mathematische Welt nicht immer so perfekt aufgeht wie in unserem Urlaub. Es gibt drei berühmte Sonderfälle, auf die man in der Praxis stößt.

Eleanor Finch

Erstens: die Degeneriertheit. Das passiert, wenn eine Basisvariable den Wert null annimmt. In diesem Fall kann es passieren, dass der Simplex-Algorithmus im Kreis tanzt -- er führt einen Basistausch nach dem anderen durch, ohne dass sich der Zielfunktionswert jemals verbessert. [sighs]

Eleanor Finch

Zweitens: die Unbeschränktheit. Wenn wir in unserem Modell keine Budget- oder Zeitgrenzen definiert hätten, könnten wir unendlich lange Urlaub machen und unser Glück wäre unbeschränkt im Unendlichen. Im Tableau erkennt man das daran, dass in der Pivotspalte keine positiven Elemente mehr für den Quotiententest übrig sind.

Eleanor Finch

Und drittens: die Unzulässigkeit. Stellen Sie sich vor, Ihr Partner verlangt, dass Sie mindestens 5 Tage in London verbringen, aber gleichzeitig dürfen Sie absolut nicht mehr als 200 Pfund ausgeben. Das ist bei 80 Pfund pro Tag in London schlicht unmöglich! Es gibt keinen Bereich, in dem alle Bedingungen gleichzeitig erfüllt sind -- das Problem ist mathematisch unzulässig. [firmly]

Eleanor Finch

[reflective] Ob im Urlaub oder im globalen Lieferketten-Management: Am Ende zeigt uns der Simplex-Algorithmus, dass uns Grenzen nicht nur einschränken, sondern uns auch den exakten Weg zu unserer besten Entscheidung weisen können.

Eleanor Finch

Vielen Dank fürs Zuhören bei dieser mathematischen Reise. Bis zum nächsten Mal bei Operations Research! Ich bin Eleanor Finch. Machen Sie es gut! [warmly]