<<

. 59
( 63 .)



>>

Dann haben wir
y + ≥ θ, y ’ ≥ θ
und n r r r
± ±
a xj ±
a j yj a j yj j
±j aj = b.
= =
j=1 j=1 j=1 j=1

Also sind y ± ∈ Z und 1 (y + + y ’) = x.
2
Da y ± = x, ist dies ein Widerspruch zur Tatsache, daß x Extremalpunkt von Z ist.
(b) =’ (a)
Sei o.E. I(x) = {1, . . . , r}. Betrachte eine Darstellung

x = ay + (1 ’ a)z, y, z ∈ Z, a ∈ (0, 1),

von x. O¬ensichtlich gilt dann I(x) = I(y) ∪ I(z). Wegen Az = b = Ay folgt daraus
n r
a (yj ’ zj ) = aj (yj ’ zj )
j
θ=
j=1 j=1
Baumeister: Lineare Algebra II / Stand: August 1996 246


und wegen der linearen Unabh¨ngigkeit von a1, . . . , ar weiterhin yj = zj , 1 ¤ j ¤ r, und
a
yj = zj = 0, r + 1 ¤ j ¤ n, wegen I(x) = I(y) ∪ I(z). Damit ist x Ecke von Z.
Zum Zusatz. (c) =’ (b) ist klar. (b) =’ (c) folgt so:
O.E. k¨nnen wir I(x) = {1, . . . , r} annehmen. Da o¬enbar r ¤ m gilt, hat man im Fall
o
r < m a1, . . . , ar nur mit Spalten der Matrix A zu einer Basis von IR m zu erg¨nzen. Dies
a
ist m¨glich, da rg(A) = m gilt.
o


Satz 9.41

Ist Z = …, so besitzt Z Ecken.
Beweis:
Da die Menge {#I(z)|z ∈ Z} eine Teilmenge von IN 0 ist, gibt es ein x ∈ Z mit

#I(x) = min{#I(z)|z ∈ Z}.

Wir wollen zeigen, daß x eine Ecke ist. Dabei ist dies schon klar, falls #I(x) = 0 ist. Wir
nehmen also nun #I(x) ≥ 1 an. O.E. also I(x) = {1, . . . , r} , r ≥ 1.
Annahme: a1 , . . . , ar sind linear abh¨ngig. Dann gibt es ±1 , . . . , ±r ∈ IR mit
a
r r
j
±2 = 0.
±j a = θ, j
j=1 j=1

Setze
:= min{xj |±j |’1 |±j = 0, 1 ¤ j ¤ r}
und sei l ∈ {1, . . . , r} mit
= xl |±l |’1 , ±l = 0.
Sei u := (x1 ’ ±1, . . . , xr ’ ±r , 0, . . . , 0). Dann gilt
r
Au = Ax ’ ±j aj = Ax = b,
j=1

also u ∈ Z, da o¬enbar u ≥ θ ist. Nun gilt

#I(u) ≥ r ’ 1,

was ein Widerspruch zur Konstruktion von r ist.

Kennt man die Ecken eines Polyeders, so kann man damit das Polyeder einfach beschrei-
ben. Dies ist die Aussage des folgenden Satzes.


Satz 9.42
Ist Z ein Polyeder, so gilt
Z = co(ext(Z)).
Beweis:
Sei x ∈ Z und r := #I(x). Ist r = 0, so ist x selbst Ecke. Wir beweisen die Aussage nun
Baumeister: Lineare Algebra II / Stand: August 1996 247


induktiv nach r.
Wiederum k¨nnen wir also o.E. annehmen: I(x) = {1, . . . , r}. Sind a1 , . . . , ar linear un-
o
abh¨ngig, so ist x Ecke und wir haben nichts mehr zu zeigen. Seien also a1, . . . , ar linear
a
abh¨ngig. Dann gibt es ±1 , . . . , ±r ∈ IR mit
a
r r
j
±2 = 0.
±j a = θ , j
j=1 j=1

Setze fur ∈ IR
¨
x( ) := (x1 + ±1 , . . . , xr + ±r , 0, . . . , 0).
Da Z konvex abgeschlossen und beschrankt ist, gibt es < 0, > 0 mit:
¨ 1 2

x( ) ∈ Z fur ∈ [ 1, 2], x( ) ∈ Z fur ∈ [ 1, 2], x( 1)j = x( 2 )j = 0, r + 1 ¤ j ¤ n.
/ /
¨ ¨

Dazu gibt es auch l, k ∈ {1, . . . , r} mit

x( 1)l = x( 2)k = 0 .

Also gilt #I(x( 1)) < r, #I(x( 2)) < r.
Nach Induktionsvoraussetzung sind x( 1) , x( 2) ∈ co(ext(Z)). Da
2 2
x( 1) + (1 ’
x= )x( 2)
’ ’
2 1 2 1

gilt, ist x selbst in co(ext(Z)).

Das obige Ergebnis ist im wesentlichen der Satz von H. Minkowski (1909 “ 1964): Jedes Polyeder
ist die konvexe Hulle seiner Extremalpunkte. Die erste systematische Abhandlung uber konvexe
¨ ¨
Mengen wurde im Nachlaß von Minkowski gefunden.

Nun kommen wir zum Hauptergebnis.
Satz 9.43
Sei Z = … und sei Z beschr¨nkt. Dann gibt es eine Ecke x von Z mit
a

< c, x > = min{< c, z > |z ∈ Z}.
Beweis:
Da Z abgeschlossen und beschr¨nkt ist, ist Z sogar kompakt. Da die Zielfunktion stetig
a
ist, gibt es u ∈ Z mit
< c, u > = min{< c, z > |z ∈ Z}.
Nach Satz 9.42 gibt es ±1 , . . . , ±l ∈ [0, 1] und Ecken x1, . . . , xl von Z mit
l l
k
u= ±k x , ±k = 1.
k=1 k=1

Wegen
l
min{< c, z > |z ∈ Z} = < c, u > = ±k < c, xk > ≥ min{< c, xk > |1 ¤ k ¤ l}
k=1
Baumeister: Lineare Algebra II / Stand: August 1996 248


muß es k0 ∈ {1, . . . , l} geben mit
< c, u > = < c, xk0 > .
Also leistet x := xk0 das Gewunschte.
¨

Nun k¨nnen wir das Prinzip des im n¨chsten Abschnitt zu beschreibenden Simplexver-
o a
fahren schon skizzieren: Da das Minimum in einer Ecke angenommen wird, sucht man das
Minimum in einer Ecke. Satz 9.40 liefert uns nun eine obere Schranke fur die Anzahl der
¨
n n
Ecken x von Z, da es h¨chstens nur m Ecken geben kann. Da m sehr schnell groß
o
wird, wenn etwa realistischerweise n ∼ 2m gilt, ist das Verfahren, die Zielfunktion in den
Ecken auszuwerten und ihre Werte zu vergleichen, kein e¬zientes Vorgehen. Es ist der
Vorteil der im n¨chsten Abschnitt zu besprechenden Methode, daß im allgemeinen sehr
a
n
viel weniger als m Ecken berechnet werden mussen, ehe eine L¨sung gefunden ist.
o
¨


9.6 Simplexverfahren
Satz 9.40 entnimmt man, daß eine Ecke x von Z h¨chstens m positive Eintr¨ge xj haben
o a
kann, wenn rg(A) = m gilt.
Generelle Annahme: rg(A) = m

De¬nition 9.44
Ein z ∈ Z heißt Basispunkt mit Basisvariablen µ1 , . . . , µm , falls gilt:
aµ1 , . . . , aµm sind linear unabhangig, zj = 0, falls j ∈ {µ1 , . . . , µm }.
/
¨
Die Variablen {j|j ∈ {µ1 , . . . , µm } heißen Nichtbasisvariablen.
/
2

Lemma 9.45
Es sind ¨quivalent f¨r z ∈ Z :
a u

(a) z ist Ecke.

(b) z ist Basispunkt.
Beweis:
Siehe Satz 9.40.

Bei der De¬nition von Basisvariablen f¨llt auf, daß nicht behauptet wird, daß Komponen-
a
ten zj , die zu Basisvariablen geh¨ren, positiv sind. Dies kann man im allgemeinen auch
o
nicht erwarten.


De¬nition 9.46
Eine Ecke z ∈ Z heißt entartet , wenn es eine Basisvariable j gibt mit zj = 0.
2
Baumeister: Lineare Algebra II / Stand: August 1996 249


Beispiel 9.47
Betrachte das Minimierungsproblem
Minimiere < c, x >
unter den Nebenbedingungen Ax = b , x ≥ θ
fur m := 3, n := 5 und
¨
«  « 
11100 2
A :=  2 1 0 0 1  , b :=  3 · , c :=
¬ · ¬
’3, ’1
 .
10010 1
Dann ist x = (1, 1, 0, 0, 0) eine entartete Ecke mit Basisvariablen 1, 2, 3 bzw. 1, 2, 4 bzw.
2
1, 1, 5. Die Ecke bestimmt also die Basisvariablen nicht in eindeutiger Weise.

Kommen wir nun zur Beschreibung des Simplexverfahrens; entartete Ecken erfordern
dabei eine Sonderbehandlung. In seiner Durchfuhrung unterscheidet man zwei Schritte:
¨
Phase I Bestimmung einer Startecke von Z.
¨
Phase II Ubergang von einer nichtoptimalen Ecke zu einer benachbarten“ Ecke, in

der der Wert der Zielfunktion zumindest nicht anw¨chst (Eckenaustausch) und
a
Entscheidung, ob ein weiterer Eckenaustausch die Zielfunktion verkleinert oder
nicht (Optimalit¨tstest).
a
Da der Eckenaustausch mit benachbarten“ Ecken erfolgt, kann man diesen Schritt als

Schritt von einer Ecke entlang einer Kante“ zu einer anderen Ecke verstehen. Man

berucksichtigt also sehr wesentlich, daß der zul¨ssige Bereich die Form“ eines Simplex
a
¨

hat; daher die Bezeichnungsweise.

Das Simplexverfahren wurde 1947/48 von G.B. Danzig eingefuhrt. Es war lange Zeit konkurrenzlos
¨
was E¬ektivit¨t und Praktikabilit¨t betri¬t. Erst 1980 und 1985 wurden andersartige Verfahren
a a
(Ellipsoid-Verfahren, Innere-Punkte-Verfahren) vorgeschlagen, die im Vergleich zum Simplexver-
fahren etwas mehr beweisbare E¬ektivitat besitzen. In der Praxis ist das Simplexverfahren aber
¨
wohl immer noch konkurrenzlos.

Kommen wir nun zur schrittweisen Darstellung des Verfahrens. Dazu stellen wir zun¨chst
a
ein Ergebnis zum Optimalit¨tstest bereit. Sei
a
Z — := {y ∈ IRm,1 | At y ¤ c} .
Im n¨chsten Abschnitt wird klar werden, daß Z — als zul¨ssige Menge eines zu (LOP)
a a

“dualen“ Problems (LOP) auftritt.

Lemma 9.48

<<

. 59
( 63 .)



>>