90. Jahresbericht des Bundes-Realgymnasiums Steyr 1972/73

Tableau 4 u w V Der Austausch der Variablen ergibt also : X 2 -21 8 X + 2u + Bv - 21w = z 3 0 -2 1 z + 0u + V- 2w 3 y -2 -1 13 -5 y - 1u - 5v + 13w = -2 Die Lösung des Gleichungssystems folgt, wenn u = v = w = 0: x = 1, y = -2, z = 3. Die Lösungsmenge erscheint in der 1. Spalte. Natürlich wird diese Methode im allgemeinen nicht zur Lösung linearer Gleichungssysteme angewendet. Dazu benützt man den Gauß'schen Algo- rithmus oder die Regel von Cramer, sie ist jedoch zum Verständnis des Simplex-Algorithmus dienlich. e) Simplexmethode Im folgenden soll der Simplex-Algorithmus al lgemein , jedoch nur für 2 Va- riable dargestellt werden. Es kommen dabei alle wesentlichen Punkte der Methode heraus. Das vorgelegte Optimierungsproblem lautet: Eine lineare Funktion (Zielfunktion) in 2 Variablen Z = dx + ey ist gegeben, wobei der Definitionsbereich der Funktion durch 5 Ungleichungen bestimmt ist : a1X + b,y ;;;;; a,x + b2y ;;;;; a3X + b3y ;;;;; X ~ 0 y ~ ~: l C3 0 Durch Einführung von Hilfsvariablen (genannt Sc h I u p f v a r i ab I e) werden die Ungleichungen in Gleichungen übergeführt. Das entsprechende Glei- chungssystem hat daher die Form: u + a,x + b,y = c, } (1) V + a,x + b,y = C2 w + a3X + b3y C3 2- dx - ey = 0 Die Schlupfvariablen dürfen nicht negativ werden , da sonst die ursprüng- lichen Variablen nicht mehr den gegebenen Beschränkungen genügen würden . Das Wesen der Simplexmethode besteht darin, daß die Zielfunktion einen mögl ichst großen Wert annimmt, wobei gewisse Schlupfvariable möglichst klein werden sollen. 24