<<

. 58
( 63 .)



>>

+

x + B ty ∈ IRn , Bx = θ, B t y = θ.
>

Da At y = θ ist, folgt aufgrund von (b) ± < y, b > ≥ 0, also < y, b > = 0. Damit ist
xn+1 > 0 und o.E. konnen wir xn+1 = 1 annehmen. Also ist x = (x, 1) und wir haben
¨
Ax ’ b = Bx = θ.

Das obige Lemma geht zuruck auf eine Arbeit von J. Farkas zur “Theorie der einfachen Unglei-
¨
chungen“ (1902). Allerdings war es in Grundzuugen schon in einer Arbeit (1836) von J.B. Fourier
¨
(1768 “ 1830) vorhanden.

Kommen wir nun zu Aufgabenstellungen, wo lineare Ungleichungenen wesentlich Ein-
gang ¬nden. Es ist dies die lineare Optimierung. Hier haben wir es mit einer Optimie-
rungsaufgabe zu tun, in der eine lineare Funktion (Zielfunktion) uber einem Polyeder
¨
(zul¨ssiger Bereich) zu minimieren/maximieren ist. Es handelt sich hier um eine Auf-
a
gabe, bei der sowohl die Zielfunktion als auch der zul¨ssige Bereich konvex ist.
a

Da n¨mlich die Einrichtung der ganzen Welt die vorzuglichste ist und da sie von dem weisesten
a ¨
Sch¨pfer herstammt, wird nichts in der Welt angetro¬en, woraus nicht irgendeine Maximum“ oder
o
Minimumeigenschaft hervorleuchtet. Deshalb kann kein Zweifel bestehen, daß alle Wirkungen der
Welt ebenso durch die Methode der Maxima oder Minima wie aus den wirkenden Ursachen selbst
abgeleitet werden k¨nnen.
o
L. Euler (Frei ubersetzt aus “Commentationes Mechanicae“).
¨

Betrachten wir ein Problem der optimalen Produktionsplanung.
Ein Unternehmer produziert n Produkte A1 , . . . , An, zu deren Herstellung m verschiedene
Rohsto¬e B1 , . . . , Bm ben¨tigt werden. Das Produkt Ak enthalte alk Anteile des Rohstof-
o
fes Bl und m¨ge beim Verkauf pro Einheit einen Reingewinn von ck Zahlungseinheiten
o
Baumeister: Lineare Algebra II / Stand: August 1996 242


erbringen. Vom Rohsto¬ Bl sei die Menge bl verfugbar. Wir wollen vereinfachend anneh-
¨
men, daß der Markt fur die Produkte A1, . . . , An unbegrenzt aufnahmef¨hig ist und daß
a
¨
die H¨he des Angebots keine Ruckwirkung auf die Preise hat. Die Produktionsmenge xk
o ¨
der Ware Ak soll nun so festgelegt werden, daß der Gewinn maximal wird. Diese Aufgabe
l¨ßt sich mathematisch als Bestimmung eines Maximums der Zielfunktion
a
n
f(x1 , . . . , xn ) := ck xk
k=1

unter den Nebenbedingungen
n
alk xk ¤ bl , 1 ¤ l ¤ m , xk ≥ 0 , 1 ¤ k ¤ n,
k=1

formulieren. In Matrixschreibweise erhalten wir mit

A := (alk )1 ¤l¤m,1 ¤k ¤n , c := (c1, . . . , cn) , b := (b1, . . . , bm )

unter Verwendung des euklidischen Skalarprodukts < ·, · > die Optimierungsaufgabe
Minimiere < c, x >
unter den Nebenbedingungen Ax ¤ b , x ≥ θ .
Dabei verstehen wir die Symbole “¤ “ und “≥“ bei Vektoren komponentweise (siehe
Abschnitt 9.4). Die Aufgabe heißt linear, da sowohl die Zielfunktion als auch die Neben-
bedingungen durch lineare Abbildungen beschrieben werden. Klar, die zulassige Menge
¨

Zad := {x ∈ IRn |Ax ¤ b, x ≥ θ}

ist ein (konvexes) Polyeder.
Die obige Optimierungsaufgabe l¨ßt sich geometrisch interpretieren. Betrachte dazu fol-
a
gendes konkrete


Beispiel 9.36
Sei m := 3, n := 2 und seien A, b, c gegeben durch
«  « 
10 5 50
¬
’1  , b :=  ’6 · , c :=
· ¬
A :=  ’2 ’10, ’20
 .
’200 ’400 ’1000

Das Polyeder der zul¨ssigen Menge wird im 1. Quadranten IR2 begrenzt durch die Gera-
a +
den
10x + 5y = 50, 2x + y = 6, 200x + 400y = 1000
Durch die Zielfunktion ist die Geradenschar

’10x ’ 20y = a

mit dem Scharparameter a de¬niert. Diejenige Gerade dieser Schar, die fur die Punkte
¨
(x, y) des zul¨ssigen Polyeders einen minimalen Parameter a besitzt, liefert die (eine)
a
Baumeister: Lineare Algebra II / Stand: August 1996 243


Losung des Optimierungsproblems. Im vorliegenden Beispiel ist die L¨sung eindeutig
o
¨
74
bestimmt. Sie liegt im “Eckpunkt“ ( 3 , 3 ) des Polyeders. Der entsprechende Wert der
Zielfunktion betr¨gt f( 7 , 4 ) = ’50. (Der negative Gewinn kann als Kosten interpretiert
a
2
33
werden.)

Die obige Form der Optimierungsaufgabe wollen wir zu einer Standardform abwandeln.
Wir behandeln

Minimiere < c, x >
unter den Nebenbedingungen Ax = b , x ≥ θ .

Dabei sind also
A ∈ IR m,n , b ∈ IRm , c ∈ IRn
gegeben und wir k¨nnen o.E. n > m annehmen. Anderenfalls hat n¨mlich das Glei-
o a
chungssystem Ax = b im allgemeinen genau eine oder keine L¨sung; in keinem Falle ist
o
die Aufgabe dann interessant.
Auf diese Standardform “ wir benennen sie mit (LOP) “ lassen sich ursprunglich an-
¨
ders formulierte Aufgaben, auch das eingangs formulierte lineare Optimierungsproblem,
umschreiben.


Beispiel 9.37
Durch Einfuhrung der “Hilfsvariablen“ y ∈ IRm wird aus der Aufgabe
¨
Minimiere < c, x >
unter den Nebenbedingungen Ax ¤ b , x ≥ θ

die Aufgabe

Minimiere < c , x >
unter den Nebenbedingungen A x = b , x ≥ θ ,

wobei
x
A := (A|E) , b := b , x := , c := (c|θ)
y
2
ist.

Die Besch¨ftigung mit Aufgaben vom Typ (LOP) wird unter dem Stichwort “Lineare
a
Optimierung“ zusammengefaßt; sie ist Kern des Fachgebiets “Operations Research“. Hier
sind typische Anwendungen der linearen Optimierung: Transportprobleme (Kosten-
minimierung beim Transport von Gutern zu den M¨rkten), Rundreiseprobleme (Ko-
a
¨
stenminimierung bei der Ausarbeitung einer Tour durch eine vorgegebene Anzahl von
St¨dten); letzteres Problem ist ein Problem der ganzzahligen Optimierung. Das im
a
n¨chsten Abschnitt zur Vorstellung kommende Simplexverfahren kann so abge¨ndert wer-
a a
den, daß es auch ganzahlige Probleme l¨st.
o

Fur das Problem (LOP) wollen wir das Simplexverfahren beschreiben. Davor haben wir
¨
noch einige Vorbereitungen zu tre¬en.
Baumeister: Lineare Algebra II / Stand: August 1996 244


9.5 Extremalpunkte
Im Beispiel der Produktionsplanung hatten wir gesehen, daß die L¨sung ein “Eckpunkt“
o
des zul¨ssigen Polyeders ist. Dieser Sachverhalt stellt die Basis des im n¨chsten Abschnit
a a
zu besprechenden Simplexverfahrens dar. Hier bereiten wir die Schritte dieses Verfahrens
vor. Dazu studieren wir einige Eigenschaften von Polyedern genauer.


De¬nition 9.38
Sei X IR “ Vektorraum und sei M ‚ X konvex.
Ein Punkt x ∈ M heißt Extremalpunkt von M genau dann, wenn aus der Bezie-
hung
x = ay + (1 ’ a)z, x, y ∈ M, 0 < a < 1,
stets x = y = z folgt.
Die Menge der Extremalpunkte von M bezeichnen wir mit ext(M).
2

Beispiel 9.39
Sei M := {x ∈ IRn | x 2 ¤ 1}. Dann ist ext(M) = {x ∈ IR n | x 2 = 1}.
Sei M := {x ∈ IRn | x 1 ¤ 1}. Dann ist ext(M) = {ei|1 ¤ i ¤ n}.
Sei M := Zad mit Zad aus Beispiel 9.36. Dann ist

ext(M) = {(0, 6), (0, 10), (5, 0), ( 7 , 4 )} .
33

In jedem Falle stellen wir fest, daß die Ausgangsmenge M als konvexe Hulle der Extremal-
¨
punkte dargestellt werden kann. Dies wollen wir sp¨ter fur Polyeder allgemein beweisen.
a ¨
(In der Funktionalanalysis stellt der Satz von Krein“Milman das entsprechende Resultat
2
dar.)

Liegt ein Polyeder vor, so bezeichnen wir der Anschauung gem¨ß Extremalpunkte auch
a
als Ecken.

Sei nun stets
Z := {x ∈ IRn |Ax = b, x ≥ θ}.
Zu z ∈ Z bezeichnen wir mit

I(z) := {j ∈ {1, . . . , n}|zj > 0}

die Menge der aktiven Indizes von z.
Die Matrix A in Spaltenschreibweise sei A = (a1| . . . |an ).

Im folgenden Satz stellen wir eine algebraische Charakterisierung von Ecken bereit.
Baumeister: Lineare Algebra II / Stand: August 1996 245


Satz 9.40
Es sind f¨r x ∈ Z folgende Aussagen ¨quivalent:
u a

(a) x ist Ecke von Z.

(b) Die Vektoren aj , j ∈ I(x), sind linear unabhangig.
¨
Zusatz: Ist rg(A) = m, dann ist (b) auch zur Aussage

(c) Es gibt µ1 , . . . , µm ∈ {1, . . . , n} mit rg(aµ1 | · · · |aµm ) = m und xj = 0 f¨r
u
j ∈ {µ1 , . . . , µm }
/

¨quivalent.
a
Beweis:
(a) =’ (b)
O.E. k¨nnen wir annehmen I(x) = {1, . . . , r} mit r ≥ 1. Wegen x ∈ Z gilt die Beziehung
o
r
aij xj = bi , 1 ¤ i ¤ m.
j=1

Annahme: a1 , . . . , ar sind linear abhangig. Dann gibt es also ±1 , . . . , ±r ∈ IR mit
¨
r r
j
±2 = 0.
±j a = θ , j
j=1 j=1

Da fur j ∈ {1, . . . , r} ja xj > 0 gilt, gibt es > 0 mit
¨
xj ± ±j > 0 , 1 ¤ j ¤ r.

Setze
y + := (x1 + ±1, . . . xr + ±r , 0, . . . , 0),
y ’ := (x1 ’ ±1, . . . , xr ’ ±r , 0, . . . , 0).

<<

. 58
( 63 .)



>>