Schlupfvariable
Voraussetzung: Eckpunkt
Der Simplex-Algorithmus rechnet mit Gleichungen, nicht mit Ungleichungen. Eine Nebenbedingung wie \(5x_1+2x_2\le 40\) sagt aber nur, dass der Verbrauch höchstens \(40\) beträgt. Damit eine Gleichung daraus wird, fügst du den Rest bis zur Kapazität als neue Variable hinzu. Diese Variable heißt Schlupfvariable. Voraussetzung sind die kanonische Form und das Einsetzen eines Punktes in eine Nebenbedingung.
Aus der Nebenbedingung \(a_{i1}x_1+\dots+a_{in}x_n\le b_i\) wird die Gleichung
\[ a_{i1}x_1+\dots+a_{in}x_n+S_i=b_i,\qquad S_i\ge 0. \]
Jede Nebenbedingung bekommt ihre eigene Schlupfvariable \(S_i\). Der Schlupf ist die Kapazität minus der Verbrauch: Er sagt, wie viel von der Ressource noch frei ist. Er kann nicht negativ sein, denn die Nebenbedingung verlangt Verbrauch \(\le\) Kapazität.
Im Starttableau des Simplex-Algorithmus ist jede Entscheidungsvariable \(0\), man steht im Ursprung. Dort wird nichts verbraucht, und jede Schlupfvariable hat den vollen Wert ihrer Kapazität, \(S_i=b_i\). Die Schlupfvariablen sind die Basisvariablen, die Entscheidungsvariablen sind Nichtbasisvariablen mit dem Wert \(0\). Das ist der Grund, warum die rechten Seiten nichtnegativ sein müssen.
Wann eine Nebenbedingung bindend ist
Ist der Schlupf einer Nebenbedingung \(0\), wird die Kapazität vollständig genutzt. Die Nebenbedingung heißt dann bindend, und der Punkt liegt auf ihrer Grenzgeraden. Ist der Schlupf positiv, liegt der Punkt im Innern des erlaubten Bereichs und es bleibt Kapazität übrig. Diese Lesart brauchst du, wenn du am Ende des Verfahrens das Optimum deutest.
Ein zweites Beispiel, zwei Nebenbedingungen
Zu \(3x_1+4x_2\le 36\) und \(2x_1+x_2\le 14\) gehören \(3x_1+4x_2+S_1=36\) und \(2x_1+x_2+S_2=14\). Das System hat vier Variablen: \(x_1,\ x_2,\ S_1,\ S_2\). Im Ursprung ist \(S_1=36\) und \(S_2=14\). Am Punkt \((4,2)\) ist der Verbrauch der ersten Zeile \(12+8=20\), also \(S_1=16\), und der der zweiten \(8+2=10\), also \(S_2=4\).