L2 Lösen von Linearen Optimierungsproblemen
Herstellen der Normalform
Nachdem Lineare Optimierungsprobleme eingeführt wurden sowie ein sehr eingeschränkt einsetzbares Vorgehen zum grafischen Auffinden einer Lösung gezeigt wurde, wird in diesem Kapitel ein numerisches Verfahren vorgestellt, der Simplexalgorithmus.
Schlupfvariable
Entscheidungsvariablen
Strukturvariablen
Herstellen der Normalform
Bevor der Simplexalgorithmus zum Einsatz kommen kann, muss das Problem in ein Tableau eingetragen werden. Dazu wiederum muss das Problem in die sogenannte Normalform gebracht werden.
Die Normalform wird dadurch hergestellt, dass die Ungleichungen durch das Hinzufügen einer sogenannten Schlupfvariable in Gleichungen überführt werden.
Zu jeder Nebenbedingung des Problems wird eine nichtnegative Schlupfvariable ergänzt und das Kleiner-gleich-Zeichen durch ein Gleichzeichen ersetzt. Die Variable gibt an, wie groß die Differenz zwischen der rechten und der linken Seite der ursprünglichen Ungleichung ist.
| a11·x1 | + a12·x2 | + a13·x3 | +… | + a1n·xn | + xn+1 | = | b1 | |||
| a21·x1 | + a22·x2 | + a23·x3 | +… | + a2n·xn | +xn+2 | = | b2 | |||
| ... | ||||||||||
| am1·x1 | + am2·x2 | + am2·x3 | +… | + amn·xn | + xn+m | = | bm |
Bisher gab es n Variablen, die, um den Unterschied zu den Schlupfvariablen deutlich zu machen, auch Struktur- oder Entscheidungsvariablen genannt werden. Nun kommen nochmal m Schlupfvariablen hinzu, sie werden in dieser Darstellung mit n+1 bis n+m indiziert.
An vielen Stellen sind Strukturvariablen und Schlupfvariablen gleich zu behandeln, dann kann auch auf die ausdrückliche Unterscheidung verzichtet werden und es können einfach alle Variablen mit 1 bis n indiziert werden.
Beispiel:
Aus dem Problem
| max z= | 6·x1 | + 8·x2 | ||
| 0,8·x1 | + 0,8·x2 | ≤ | 80 | |
| 0,1·x1 | + 0,2·x2 | ≤ | 16 | |
| 0,1·x1 | ≤ | 7 |
x1≥0; x2≥0;
wird das Problem
| max z= | 6·x1 | + 8·x2 | ||||||
| 0,8·x1 | + 0,8·x2 | +x3 | = | 80 | ||||
| 0,1·x1 | + 0,2·x2 | + x4 | = | 16 | ||||
| 0,1·x1 | + x5 | = | 7 |
x1≥0; x2≥0; x3≥0; x4≥0; x5≥0;
Bezogen auf das Müslibeispiel gibt die Schlupfvariable an, wieviel einer Zutat noch übrig ist.
Nun bilden die Nebenbedingungen ein unterbestimmtes Gleichungssystem. Schon direkt nach dem Aufstellen liegt eine Basislösung vor. Die Strukturvariablen sind allesamt Nichtbasisvariablen und damit auf null gesetzt. Die Schlupfvariablen sind Basisvariablen.
Beispiel:
Zu Beginn der Überlegungen rund um die Müsliproduktion wird noch kein Müsli hergestellt, d.h. x1=0 und x2=0. Die Vorräte sind noch vollständig vorhanden, d.h. x3=80; x4=16 und x5=7
Eintragen ins Tableau
Nun kann das Lineare Optimierungsproblem in das Tableau eingetragen werden. Dabei ist noch eine Umformung an der Zielfunktion vorzunehmen.
max z= c1·x1+ c2·x2+ c3·x3+…+ cn·xn
Es ist zu beachten, dass z eine Variable ist. Bisher stehen auf beiden Seiten des Gleichzeichens Variablen. Durch Umsortieren können wie bei den Nebenbedingungen auch alle Variablen auf die linke Seite gebracht werden.
z - c·x1- c2·x2- c3·x3-…- cn·xn = 0
Das Tableau hat dann folgende Form:
Es fällt auf, dass aufgrund der vorangegangenen Umformung die Koeffizienten in der Zielzeile ihr Vorzeichen geändert haben. Ein Umstand, der im Weiteren immer wieder sorgfältiger Beachtung bedarf.
Beispiel:
Das bekannte Müsliproblem
| max z= | 6·x1 | + 8·x2 | ||||||
| 0,8·x1 | + 0,8·x2 | +x3 | = | 80 | ||||
| 0,1·x1 | + 0,2·x2 | + x4 | = | 16 | ||||
| 0,1·x1 | + x5 | = | 7 |
lässt sich wie folgt in ein Tableau eintragen:
