Warum addiert man die künstliche Variable in der Zielfunktion?

Question

Wenn in einer lineare Nebenbedingung die linke Seite größer gleich der linken Seite entspricht, muss eine Schlupfvariable mit Koeffizient -1 hinzugefügt werden, um eine Gleichung aus dieser zu machen. Jedoch kann die Schlupfvariable keine Basisvariable darstellen, denn sonst würde die Schlupfvariable einen negativen Wert haben (Linke Seite >= 0), was die Bedingung nicht zulassen. Deshalb muss als Basisvariable eine künstliche Variable hinzugefügt werden mit Koeffizient 1. Die künstliche Variable wird auch in der Zielfunktion addiert. Warum addiert man die künstliche Variable in der Zielfunktion?

Answer 1

Wenn in einer lineare Nebenbedingung die rechte Seite größer gleich der linken Seite entspricht, muss eine Schlupfvariable mit Koeffizient -1 hinzugefügt werden, um eine Gleichung aus dieser zu machen.

Das ist falsch. Aus einer Ungleichung der Form

$x+y\leq 100$ macht man die Gleichung $x+y+s_1=100$ mit $s_1\geq 0$.

Der Koeffizient ist also nicht -1.

Richtig wäre

$x+y\geq 100$ wird zu $x+y-s_1=100$ mit $s_1\geq 0$.

Ich sehe hier jetzt so erstmal keine Verletzung der Nichtnegativitäts-Bedingung.

Wie sieht das konkrete Optimierungsproblem aus? Es ist manchmal schwierig, wenn man nur Prosa schreibt.

Comments

Du hast komplett recht, genau auf x+y >= 100 wollte ich mich drauf beziehen. Wenn die Entscheidungsvariablen x=y=0 sind, steht in der Gleichung -s1 = 100 <=> s1 = -100, deshalb schreibt man x+y-s1 + k1 = 100, sodass x=y=0 gilt. Da eine Größer-Gleich-Beschränkung vorliegt, muss für Anwendung des Simplex-Algorithmus demnach die Wahl der Pivotspalte sich ändern. Dies erreicht man, indem man die künstliche Variable bestraft mit einem sehr kleinen bzw. betraglich großen Wert -M.

---

Ah, du beziehst dich gezielt auf den Simplex-Algorithmus.

Damit die Nebenbedingungen erfüllt sind, gilt natürlich das von dir Gesagte. Hat man nun ein Minimierungsproblem und nimmt die künstliche Variable mit in die Zielfunktion auf, dann kann man damit den Algorithmus durchführen. Der Wert dieser neuen Variable wird dann sehr einem sehr großen Wert bestraft, damit der Algorithmus versucht, diese Größe möglichst auf 0 zu reduzieren, da diese Variable ja nur künstlich ist und wir sie an sich gar haben wollen. Bei einem Maximierungsproblem wird der Wert dann entsprechend klein bestraft.