negative Spalten im Simplex-Algorithmus?

Darf man eine Spalte, die eine negative Zahl hat, als Pivot-Spalte verwenden?

Answer 1

[Mathmaninoff, UserMod Light]

Nur das Pivotelement selber muss positiv sein, da durch dieses dividiert wird und bei einem negativen Divisor dann auch die rechte Seite negativ werden würde, was aber der Voraussetzung, dass die Basisvariable nicht negativ sein soll, widerspricht.

Beispielaufgabe:

Maximiere x.

Normalerweise schreibt man nur eine Koeffizientenmatri, aber so finde ich es anschaulicher:

x - y + s      = 1
    y     +  t = 1
------------------
x              = 0 = -z

Zu Beginn sind x = y = 0 und die Schlupfvariablen s = t = 1.

Hier ist die erste Spalte die Pivotspalte, weil nur der Zielfunktionskoeffizient von x positiv ist und da nur in der ersten Zeile das x einen positiven Koeffizienten hat, ist das die Pivotzeile.

x - y + s     = 1
    y     + t = 1
------------------
    y - s     =-1 = -z

Hier hat das y unten noch einen positiven Koeffizienten. Und hier muss man eben diese Spalte neben, obwohl oben das y einen negativen Koeffizienten hat.

x     + s + t = 2
    y     + t = 1
------------------
      - s - t =-2 = -z

Das entspricht der Lösung x =2, y = 1, s = 0, t = 0.

Es ist also kein Problem, dass in der Spalte ein negativer Koeffizient war.