L2 Lösen von Linearen Optimierungsproblemen
Bezug zu unterbestimmten Gleichungssystemen
Oben wurde bereits erwähnt, dass Lineare Optimierungsprobleme, abgesehen von den Nichtnegativitätsbedingungen, unterbestimmte lineare Gleichungssysteme 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 Nichtnegativitätsbedingungen 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 Nichtnegativitätsbedingungen 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:
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 Nichtnegativitätsbedingungen sind teilweise verletzt und die Basislösung ist keine zulässige Lösung des Linearen Optimierungsproblems.
