Simplex-Methode bei mehr als zwei Variablen – wie fange ich systematisch an?

Moin Tim, das Prinzip bleibt bei drei (oder zehn) Variablen genau gleich wie bei zwei, nur die Übersicht wird kniffliger. Ich mach's immer stur nach Schema F, dann verwirrt einen nichts mehr 😄

Zum Starttableau: Nimm an, du maximierst Z = c1x1 + c2x2 + c3x3 unter Nebenbedingungen der Form "≤". Dann gehst du so vor:

• Jede NB bekommt genau eine eigene Schlupfvariable (s1, s2, s3, ...), damit wird aus der Ungleichung eine Gleichung. Also NB1: a11x1+a12x2+a13x3+s1 = b1, usw.
• Die Spaltenreihenfolge im Tableau ist immer: erst alle echten Variablen (x1, x2, x3), dann alle Schlupfvariablen in der Reihenfolge der NBs, dann die rechte Seite (RHS/b-Spalte).
• Jede Zeile im Tableau entspricht genau einer NB – die Koeffizienten stehen 1:1 so da wie in der Gleichung.
• Ganz unten kommt die Zielfunktionszeile, und zwar in der Form Z - c1x1 - c2x2 - c3x3 = 0, also mit umgedrehtem Vorzeichen der Koeffizienten.
• Die Startbasis sind die Schlupfvariablen (die stehen ja quasi schon "gelöst" da, deshalb ist das Starttableau automatisch zulässig, wenn alle b_i ≥ 0 sind).

Merksatz: Variablen zuerst, Schlupf danach, Z-Zeile ganz unten mit Minuszeichen. Wenn du das sauber hinschreibst, ist der Rest (Pivotwahl, Abbruchkriterium) nur noch Rechnerei nach festen Regeln – dazu schreib ich gleich noch was, falls es dich interessiert.

Moin Tim, Marco hat den Aufbau schon top erklärt, ich ergänz noch den Teil zur Pivotwahl, weil da bei mir am Anfang auch der Knoten war.

Bei Maximierung (Zielfunktionszeile mit umgedrehtem Vorzeichen, wie Marco geschrieben hat) gehst du so vor:

• Pivotspalte: Du suchst in der Z-Zeile den kleinsten (also betragsmäßig größten) negativen Wert. Diese Spalte kommt als nächstes in die Basis. Stehen nur noch Nullen oder positive Werte in der Z-Zeile, bist du fertig – das ist dein Abbruchkriterium.
• Pivotzeile: Hier kommt der Teil, an dem die meisten (auch ich früher) Fehler machen: Du bildest für jede Zeile den Quotienten b_i / a_i aus der Pivotspalte – aber NUR, wenn a_i positiv ist! Negative oder Null-Koeffizienten in der Pivotspalte ignorierst du komplett, sonst kriegst du negative oder unsinnige Quotienten raus. Die Zeile mit dem kleinsten nichtnegativen Quotienten ist deine Pivotzeile.
• Das Element im Schnittpunkt von Pivotspalte und Pivotzeile ist dein Pivotelement. Darauf normierst du die Zeile (durch das Pivotelement teilen) und machst anschließend die restliche Spalte mit Zeilenumformungen zu Null – inklusive Z-Zeile.

Typischer Flüchtigkeitsfehler: Man vergisst, auch die Z-Zeile bei jedem Schritt mit umzuformen, und wundert sich dann, warum das Tableau nie "sauber" aufgeht. Ich rechne mir deshalb jedes Tableau komplett neu auf, lieber einmal mehr schreiben als sich verzetteln.

Marco und Robert haben das Gerüst wirklich sauber zusammengefasst, da gibt's fachlich nichts zu ergänzen. Ich schreib trotzdem noch was zur Abbruchbedingung dazu, weil mich das in der Klausur am meisten Zeit gekostet hat, bis ich einen festen Reflex dafür hatte.

Ich geh in der Klausur immer so vor: Nach jedem Umformungsschritt lese ich NUR die Z-Zeile von links nach rechts durch den Variablenbereich (also bis zur RHS-Spalte, die zählt nicht mit). Sobald dort alle Einträge ≥ 0 sind, ist Schluss – fertig optimiert. Ich markiere mir dabei testweise negative Werte mit einem Minuszeichen am Rand, dann sehe ich auf einen Blick, ob noch was zu tun ist, ohne die ganze Zeile nochmal gedanklich durchzugehen.

Ein Punkt, der mir in der Klausur Zeit gespart hat: Ich prüfe die Abbruchbedingung VOR der Quotientenregel, nicht erst danach. Wenn die Z-Zeile schon sauber ist, spare ich mir die ganze Pivotzeilen-Rechnung im letzten Schritt komplett.

Noch ein Tipp aus eigener Erfahrung: Am Ende immer kurz die Lösung in die ursprünglichen Nebenbedingungen einsetzen und die Probe machen. Mir ist in der Klausur einmal ein Vorzeichenfehler in der Z-Zeile durchgerutscht, und ohne Probe hätte ich das nicht gemerkt – das Tableau sah "fertig" aus, war aber falsch umgeformt.