H . p. KuNzi : Lineare Programmierung

3

Ausdruck (1) : Ç = p^ % + ^2 ^2 liefert eine Schar paralleler Hyperebenen (Geraden). Das Optimum für Q wird erreicht, wenn eine der parallelen Geraden die «äusserste Ecke» trifft (in unserem Falle P3).

b ) Das Minimumproblem:

Neben der oben formulierten Maximumaufgabe ist es sinnvoll, auch von einer Minimumaufgabe zu sprechen, indem man zum Beispiel verlangt, dass der lineare Ausdruck -_ /.4

K - HJl - ^ - ЧУ2^ '" -^ ^тУт (4)

zum Minimum wird, unter den Restriktionen

«11 У1 + Ч1 Уч + •

" ■^ ^тхУт ^Pl

«12 ) ^l + ^22>'2+-

'■^ ( ^т2Ут'^р2

Ч^Ух - ^ Ч^Уъ^ •

• ' + 4^g У m ^ Pg

( 5 )

und

II

yj^O j=l,2,...,m. (6)

Man könnte für das so formulierte Minimumproblem II entsprechende analytische und geometrische Überlegungen anstellen wie beim Maximum problem.

Mit voller Absicht habe ich das Problem II in einer gewissen Symmetrie zum Problem I geschrieben. Die beiden so aufgestellten Probleme I und II heissen dual zueinander, und für sie gilt das zentrale

Dualitätstheorem : Am Optimalpunkt stimmen die Werte Q und К der beiden aufgaben I und II über ein.

Für diesen Beweis,der nicht mehr ganz elementar verläuft, muss ich Sie auf die entsprechende Fachliteratur verweisen [7J.

c ) Die Überführung der Ungleicliungen in Gleichungen:

Im folgenden beschränken wir uns wieder auf das Maximumproblem, für das wir nun nach expHziten Lösungen suchen wollen. Die entsprechenden Überlegungen für die Minimumaufgabe sind analog zu denjenigen der Maximumaufgabe.

Der erste Schritt im Lösungsverfahren besteht darin, dass die Ungleichungen des Systems (2) in Gleichungen überführt werden, denn es ist im allgemeinen angenehmer, mit Gleichungen als mit Ungleichungen zu rechnen.

Um dies auszuführen, addieren wir zu jeder Ungleichung auf der linken Seite der Reihe nach die nicht-negativen Schlupfvariablen

^g + V ^g^2> • • • > ^g-\-m~ ^n (')

hinzu und schreiben das Problem I nochmals in etwas modifizierter Form : Man maximiere den Ausdruck

Q = Pi^i + "'-^Pg^g + Pg+i^g+i-^ '" -^P unter den linearen Restriktionen

^21 ^1 ~i~ ' * ' "b ^2g -^g ~^ ^g + 2 ^^ ^2 >

( 8 )

^mi% +

und

+ ^mg^g~^ ^g + m-~ ^m

4 , H . ' - '>^g + m ^0

( 9 )

( 10 )

III