L2 Lösen von Linearen Optimierungsproblemen

Bezug zu unterbestimmten Gleichungssystemen

unzulässige Lösung
zulässige Lösung

Oben wurde bereits erwähnt, dass Lineare Optimierungsprobleme, abgesehen von den Nicht­negativitäts­bedingungen, unterbestimmte lineare Gleichungs­systeme sind, bei denen sogar schon automatisch eine Basislösung vorliegt. Dementsprechend kann auch ein Basistausch vorgenommen werden. Grundsätzlich kann für jede Auswahl von m Basisvariablen eine Basislösung angegeben werden. Allerdings kann es dabei vorkommen, dass die Variablen negative Werte annehmen, was eine Verletzung der Nichtnegativitätsbedingung ist.

Von daher sind manche Basislösungen unzulässig in Bezug auf die Nicht­negativitäts­bedingungen und damit das Gesamtproblem. Es hat sich die vom Wortsinn her etwas merkwürdige klingende Bezeichnung unzulässige Lösung etabliert.

Eine Basislösung, die auch die Nicht­negativitäts­bedingungen erfüllt, wird hingegen als zulässige Lösung bezeichnet.

Beispiel:

Das obige Tableau enthält eine zulässige Lösung, da alle Werte auf der rechten Seite positiv sind. Nun wird ein Basistausch vorgenommen. Die Variable x4 soll die Basis verlassen und dafür x1 aufgenommen werden. Es ergibt sich folgendes Tableau:

LP_und_Basistausch

Das Ergebnis lautet:

z=960; x1=160; x2=0; x3=-48; x4=0; x5=-9

Hinweis zum Ablesen der Lösung

Es fällt auf, manche Variablen haben negative Werte, die Nicht­negativitäts­bedingungen sind teilweise verletzt und die Basislösung ist keine zulässige Lösung des Linearen Optimierungsproblems.

zurueck
weiter