90. Jahresbericht des Bundes-Realgymnasiums Steyr 1972/73

Nehmen wir diesen Satz zur Kenntnis, so läßt sich jedes Minimierungsproblem auf ein solches der Maxim ierung zurückführen und damit nach dem Simplexal- gorithmus lösen. Dies soll an einem Beispiel gezeigt werden . Gegeben ist das Optimierungsproblem: 3x' + y' + z' ~ 40 2x' + y' + 4z ' ~ 30 240x' + 90y' + 2402' = Z' (min) Die Funktion Z' ("-' y' z') soll ein Minimum werden, wenn die angegebenen Nebenbedingungen gelten. Man kann dieses Problem als dua les Problem zu folgendem primalen betrachten : 3x + 2y ;;;; 240 x+ y ;;;; 90 X + 4y ;;;; 240 40x + 30y = Z (max) Diese Aufgabe stimmt mit der in Punkt b) formulierten überein. Aus dem Lö- sungstableau dieser Aufgabe kann nun auch die Lösung des zu diesem Maxi- mierungsproblem dualen Minimierungsproblems entnommen werden . LI V X 60 -2 y 30 -1 3 w 60 3 -10 ---------- - lz 1 3300 10 10 1 Das Minimum von Z' ist 3300 ; es entspricht also dem Maximum von Z, welches 3300 beträgt (Hauptsatz der linearen Optimierung) . Die Werte der Variablen x' und y' sind der letzten Zeile des Tableaus zu entnehmen: x' = 10, y' = 10. Die Variable z' besitzt in diesem Falle den Wert 0. (Die dritte Schlupfvariable des primalen Problems wurde nicht ausgetauscht.) Die Lösung des Minimierungsproblems kann also durch die Überführung in ein Maximierungsproblem simultan mit dessen Lösung ermittelt werden . h) Schlußbemerkungen Es wurde in dieser Arbeit der Versuch gemacht, vor allem die Simplex- methode darzustellen. Viele Einzelheiten, wie die Behandlung der Entartungs- fälle oder spezielle Optimierungsprobleme, konnten nicht berücksichtigt wer- den. Es wurden nur ganz einfache Beispiele ausgewählt. Neben der Simplex- methode gibt es noch eine Reihe anderer Verfahren zur Lösung von Optimie- rungsproblemen (z. 8 . die Basisvektormethode), doch ist bei diesen der Rechenaufwand meist wesentlich größer als beim Simplexverfahren. Diesem wird heute vor allem deswegen der Vorzug gegeben, weil dafür gute Pro- gramme vorliegen, die eine Berechnung mit Hilfe von Elektronenrechnern ermöglichen. i) Aufgaben 1. Stelle die Erfüllungsmenge folgender Ungleichungssysteme graphisch dar : a) x - y ;;;; 4 b) 2x + 3y < 6 X + y ~ 0 2x - 3y > 6 29