Künstliche Variable
Voraussetzung: Schlupf und Überschuss
Nach dem Schlupf und dem Überschuss ist der Ursprung für manche Zeilen immer noch kein Startpunkt. Bei \(x_1-2x_2-S_1=8\) wäre im Ursprung \(S_1=-8\), und das ist nicht erlaubt. Der Simplex braucht aber in jeder Zeile eine Variable, die am Start den Wert der rechten Seite annehmen darf. Dafür gibt es die Eine künstliche Variable ergänzt eine Zeile, die am Ursprung noch nicht zulässig ist. Phase 1 bringt sie auf 0. Dazu: Künstliche Variable. Das ist Schritt 6 und 7 der Zweiphasenmethode. Voraussetzung ist die Gleichung mit Schlupf und Überschuss.
Die Regel hat zwei Teile.
- Jede Zeile, die ursprünglich \(\ge\) oder \(=\) war, bekommt eine künstliche Variable \(A\ge 0\) mit dem Koeffizienten \(+1\).
- Jede Zeile mit \(\le\) bekommt keine, ihr Schlupf kann die Basis bilden.
Dieselbe Aufgabe wie in den Schritten davor: Maximiere \(Z=3x_1+2x_2\) unter \(x_1-2x_2\ge 8\) und \(x_1+3x_2\le 10\). Die Zeilen lauten jetzt
\[ x_1-2x_2-S_1+A=8,\qquad x_1+3x_2+S_2=10. \]
Am Start sind \(x_1=x_2=S_1=0\). Dann ist \(A=8\) und \(S_2=10\). Alle Variablen sind nichtnegativ, das System hat also eine zulässige Basislösung, nämlich \(A\) und \(S_2\). Es ist aber eine Lösung der erweiterten Aufgabe, nicht der ursprünglichen: Das Problem ist erst dann das ursprüngliche, wenn \(A=0\) ist. Darum muss die erste Phase die künstliche Variable auf \(0\) drücken.
Die erste Zeile hatte \(\ge\) und bekommt \(A\). Die zweite hatte \(\le\) und bekommt keine. Die Basis am Start ist \(\{A,S_2\}\) mit den Werten \(8\) und \(10\). Die Variablen \(x_1\), \(x_2\) und \(S_1\) sind Nichtbasisvariablen und gleich \(0\). Gäbe es eine Zeile mit \(=\), etwa \(x_1+x_2=4\), bekäme sie nur eine künstliche Variable und keinen Überschuss: \(x_1+x_2+A_2=4\).
Wann das Problem wirklich das ursprüngliche ist
Das System mit den künstlichen Variablen beschreibt dieselben Punkte wie das ursprüngliche Problem nur dort, wo alle künstlichen Variablen \(0\) sind. Eine künstliche Variable größer als \(0\) heißt: Die Zeile ist im Punkt noch verletzt, und zwar um genau diesen Betrag. Ihre Summe misst, wie weit der Punkt noch vom zulässigen Bereich entfernt ist.
Ein zweites Beispiel, drei Zeilen
Ein Problem hat \(x_1+x_2\le 9\), \(2x_1+x_2\ge 4\) und \(x_1-x_2=1\). Die erste Zeile bekommt nur den Schlupf: \(x_1+x_2+S_1=9\). Die zweite bekommt Überschuss und \(A_1\): \(2x_1+x_2-S_2+A_1=4\). Die dritte bekommt nur \(A_2\): \(x_1-x_2+A_2=1\). Am Start sind \(S_1=9\), \(A_1=4\) und \(A_2=1\), die Summe der künstlichen Variablen ist \(5\).