Hilfszielfunktion
Voraussetzung: Künstliche Variable
Die künstlichen Variablen sollen am Ende \(0\) sein, denn nur dann gehört die Lösung zum ursprünglichen Problem. Dafür brauchst du ein Maß, wie weit du davon noch entfernt bist: die Summe der künstlichen Variablen. Diese Summe wird zu einer eigenen Zielfunktion, der Hilfszielfunktion. Das ist Schritt 8 bis 10 der Zweiphasenmethode. Voraussetzung ist die künstliche Variable.
Du gehst in drei Schritten vor.
- Bilde die Hilfszielfunktion \(T=A_1+A_2+\dots\), die Summe aller künstlichen Variablen. Sie soll minimiert werden, und \(T=0\) ist das Beste, was sie erreichen kann.
- Der Simplex maximiert, also maximierst du \(-T\).
- Löse jede Zeile, die eine künstliche Variable hat, nach dieser Variablen auf und setze das in \(-T\) ein. Danach steht in \(-T\) keine künstliche Variable mehr.
Warum Schritt 3: Am Start sind die künstlichen Variablen Basisvariablen, und in der Zielzeile eines Tableaus stehen nur Nichtbasisvariablen. Darum drückst du \(-T\) durch \(x_1\), \(x_2\) und die Überschussvariablen aus. Die Zeile \(-T\) zeigt dann, wie sich \(T\) verändert, wenn eine Nichtbasisvariable wächst. Aus dem Auflösen folgt auch der Startwert: Mit \(x_1=x_2=S=0\) ist \(-T=-\) (Summe der rechten Seiten).
Nach \(A\) aufgelöst ist \(A=8-x_1+2x_2+S_1\). Dann ist \(-A=-8+x_1-2x_2-S_1\), alle Vorzeichen wechseln. Am Start, bei \(x_1=x_2=S_1=0\), ist \(-A=-8\). Die erste Phase will diesen Wert auf \(0\) anheben. Dass vor \(x_1\) eine \(+1\) steht, zeigt: Wächst \(x_1\), steigt \(-A\), und die künstliche Variable sinkt.
Mehrere künstliche Variablen
Hat das Problem zwei Zeilen mit künstlichen Variablen, ist \(T=A_1+A_2\) und \(-T=-A_1-A_2\). Du löst beide Zeilen auf und addierst die Ergebnisse. Beispiel: \(x_1+x_2-S_1+A_1=4\) und \(x_1-x_2+A_2=1\). Aus ihnen folgt \(A_1=4-x_1-x_2+S_1\) und \(A_2=1-x_1+x_2\). Dann ist \(-T=-(4-x_1-x_2+S_1)-(1-x_1+x_2)=-5+2x_1+0\cdot x_2-S_1\). Der Beitrag von \(x_2\) hebt sich auf, \(x_1\) bekommt die Summe der beiden Zahlen.
Wozu \(-T=0\) gut ist
Erreicht die erste Phase \(-T=0\), sind alle künstlichen Variablen \(0\), und die zugehörige Basislösung ist ein zulässiger Punkt der ursprünglichen Aufgabe. Das ist der Startpunkt der zweiten Phase. Bleibt \(-T\) kleiner als \(0\), obwohl der Simplex nicht weiterkommt, gibt es keinen zulässigen Punkt. Das ist der Inhalt des nächsten Schritts.