L3 Verallgemeinerung von Linearen Optimierungsproblemen und Lösung
Restriktionstypen
Größer-gleich-Bedingungen
Größer-gleich-Bedingungen haben folgende Form:
ai1·x1+ ai2·x2+ …+ ain·xn ≥ bi
Dem Vorgehen bei Kleiner-gleich-Bedingungen entsprechend lässt sich nun eine nichtnegative Variable einführen, die den Überschuss angibt.
ai1·x1+ ai2·x2+ …+ ain·xn – xn+i =bi
Trägt man diese Gleichung zusammen mit den anderen in ein Tableau ein, steht in der xn+i Spalte leider kein Einheitsvektor und somit gibt es auch noch keine Basislösung.
Ansatz Überschussvariable und künstliche Variable einführen
Eine Idee wäre, sich mit dem Zustand, dass anfänglich keine Basislösung vorliegt, anzufreunden und später eine herzustellen. Da das Ganze aber automatisierbar sein soll, wird ein auf den ersten Blick etwas umständlicher wirkender Weg beschritten.
ai1·x1+ ai2·x2+ …+ ain·xn – xn+i + x’n+i =bi
Es wird mit der Überschussvariablen gearbeitet und zusätzlich eine künstliche Variable eingeführt. So ist eine Basislösung vorhanden, die sogar zulässig ist. Gravierendes Problem ist, dass die Nebenbedingung nicht richtig abgebildet ist. Wegen der künstlichen Variable kann die ursprüngliche linke Seite auch kleiner-gleich der rechten Seite sein.Deswegen zielt die 1. Phase des Simplexalgorithmus darauf ab, die künstlichen Variablen aus der Basis zu entfernen und zu streichen.
Beispiel:
4·x1 ≥120
Ansatz 2: Negative rechte Seite in Kauf nehmen
Eine andere Möglichkeit ist, die Gleichung
ai1·x1+ ai2·x2+ …+ ain·xn – xn+i =bi
mit -1 zu multiplizieren.
-ai1·x1- ai2·x2- …- ain·xn + xn+i =-bi
Auf diese Weise erhält man im Tableau Einheitsvektoren und es ist auch eine Basislösung vorhanden. Allerdings nimmt die Variable xn+i =-bi einen negativen Wert an, was dazu führt, dass die vorhandene Basislösung unzulässig in Bezug auf die Nichtnegativitätsbedingung ist.
Wird dieser Ansatz gewählt, muss die 1. Phase des Simplexalgorithmus darauf verwendet werden, diese Unzulässigkeiten durch geeignete Basistäusche zu beseitigen.
Gleichungen
Gleichungen haben folgende Form:
ai1·x1+ ai2·x2+ …+ ain·xn = bi
Auch hier ist das Problem, dass beim Eintragen in das Simplextableau eine Basislösung fehlt. An dieser Stelle hilft nur, eine künstliche Variable einzuführen.
ai1·x1+ ai2·x2+ …+ ain·xn + x’n+i =bi
Solange diese Variable größer als null ist, ist die Gleichung nicht erfüllt, sondern eine Kleiner-gleich-Nebenbedingung. Von daher müssen auch diese künstlichen Variablen in der 1. Phase des Simplexalgorithmuses entfernt werden.
Freie Variablen
Die Lineare Optimierung ist darauf ausgerichtet, dass Variablen nicht negativ sein dürfen. Es kann aber in realen Problemen Variablen geben, die auch negative Werte annehmen dürfen. Sie werden Freie Variablen genannt.
Freie Variablen können in einen positiven und einen negativen Teil gespaltet werden.
Beispiel (kein Zusammenhang mit begleitendem Beispiel):
