<<

. 61
( 63 .)



>>

o
¨
∆j = (Aty)j ’ cj (9.8)
= < aj , x > ’cj (9.9)
m
±k,j aµk , x > ’cj
=< (9.10)
k=1
m
±k,j < aµk , x > ’cj
= (9.11)
k=1
m
±k,j cµk ’ cj
= (9.12)
k=1

(9.7) und (9.8) lassen sich folgendermaßen lesen:
Man erh¨lt (∆|∆0) aus (’c|0) durch elementare Zeilenumformungen unter
a
Zuhilfenahme der Zeilen des Tableaus mit dem Ziel
∆µ1 = · · · = ∆µm = 0.


Wir fugen der bisherigen Form des Tableaus die Zeile (’c|0) an und fuhren die elementaren
¨ ¨
Zeilenumformungen durch.
Beispiel 9.52
Aus dem Tableau
1 2 3 4
1 1 010 2
2 0 1 -1 1 1
-1 -3 0 0 0
erhalten wir

1 2 3 4
110 10 2
201 -1 1 1
00 -2 3 5
Der Wert der Zielfunktion in der aktuellen Ecke ist also ∆0 = 5, der Schlupf ∆3 ist ’2,
2
der Schlupf ∆4 = 3.

Das nun so entwickelte Tableau
···
1 n
···
µ1 ±1,1 ±1,n ±1,0
. . . .
. . . .
. . . .
···
µm ±m,1 ±m,n ±m,0
···
∆1 ∆n ∆0
Baumeister: Lineare Algebra II / Stand: August 1996 255


enthalt alle Gr¨ßen, die in Schritt 1 bis 7 ben¨tigt werden; Schritt 2 ist als Zwischenschritt
o o
¨
fur Schritt 3 nicht n¨tig, da der Schlupf durch elementare Umformungen berechnet werden
o
¨
kann (siehe oben).

Beispiel 9.53
Als Starttableau (β = {1, 2}) haben wir nun
1 2 3 4
110 1 0 2
2 0 1 ’1 1 1
0 0 ’2 3 5
Schritt 1: x = (2, 1) , x = (2, 1, 0, 0).
˜
Schritt 3: Keine Optimalitat, da ∆4 > 0 .
¨
Schritt 4: r = 4 .
Schritt 5: d = (0, 1) .
Schritt 6: Losbarkeit kann nicht ausgeschlossen werden.
¨
Schritt 7: d2 > 0; also s = 2 , da x2 = 1 .
˜
1
d2
2
Gehe mit β := {1, 4} zu Schritt 1.

Um Schritt 7 einfacher auswerten zu konnen, ist es sinnvoll dem Tableau eine weitere
¨
Spalte anzuhangen. Sie wird in Schritt 7 ausgefullt und enthalt die Großen
¨ ¨ ¨ ¨
±i,0
, 1 ¤ i ¤ m,
ui =
±i,r
wobei wir ui = ∞ fur ±i,r ¤ 0 vereinbaren. Damit k¨nnen wir dann ein s leicht ermitteln.
o
¨

Wir haben nun noch zu uberlegen, wie wir aus dem Simplextableau zur Basis β das
¨
Simplextableau zur Basis β erhalten. Dies entspricht einem Basiswechsel, der allerdings
nur in einem Vektor vollzogen wird.
Wir wissen aus Schritt 7:

±s,r > 0 , aµ1 , . . . , aµs , . . . , aµn ist Basis von IRm .

Es gilt
ar = ±k,r aµk + ±s,r aµs ,
k=s

1
aµs = ’ ( ±k,r aµk + ar ).
±s,r k=s
Damit erhalten wir fur 1 ¤ j ¤ n
¨
aj = ±k,j aµk + ±s,j aµs ,
k=s

d.h.
±s,j ±s,j r
(±k,j ’
aj = ±k,r )aµk + a.
±s,r ±s,r
k=s
Baumeister: Lineare Algebra II / Stand: August 1996 256


Ferner
±s,0 ±s,0 r
(±k,0 ’ ±k,0 )aµk +
b= a.
±s,r ±s,r
k=s

Dies bedeutet: Zu β gehort das Tableau mit den Gr¨ßen (0 ¤ j ¤ n, 1 ¤ k ¤ m)
o
¨
± ±
 ±k,j ’ s,j ±k,r , k = s
±s,r
±k,j := ±s,j
 ,k = s
±s,r
Man erh¨lt also das neue Tableau durch elementare Zeilenumformungen mit dem Ziel, daß
a
in der r-ten Spalte der s-te Einheitsvektor entsteht. Die Berechnung von (∆|∆0) erfolgt
dann wie oben beschrieben: Elementare Zeilenumformungen mit dem Ziel ∆r = 0.
Beispiel 9.54
Wir starten mit β = {1, 2} und erreichen in Schritt 7 das Tableau
1 2 3 4
110 1 02
201 -1 1 1
00 -2 3 5
Es wird die Variable µ2 = 2 gegen r = 4 ausgetauscht. Also ergibt sich als n¨chstes
a
Tableau
1 2 3 4
110 10 22
1∞
401 -1 1
0 -3 10 2
Es liegt noch keine Optimalit¨t vor und es wird die Variable µ1 = 1 gegen r = 3 ausge-
a
tauscht. Als Tableau ergibt sich
1 2 3 4
3 1 010 2
4 1 101 3
-1 -3 0 0 0
Da ∆1 ¤ 0, ∆2 ¤ 0 ist, liegt Optimalit¨t vor. Die optimale Ecke ist
a
x = (0, 0, 2, 3)
2
und der zugehorige Wert der Zielfunktion ist 0.
¨

Der obigen Darstellung entnimmt man, daß die Zielfunktion von Tableau zu Tableau strikt
abnimmt, wenn die Ecken nicht entartet sind. Dies bedeutet, daß wir mit endlich vielen
Austauschritten zum Ziel kommen. Besitzt das Problem (LOP) jedoch auch entartete
Ecken, so kann nicht ausgeschlossen werden, daß man zu einer entarteten Ecke gelangt.
Da dann die Zielfunktion eventuell beim Austausch nicht abnimmt, kann nicht gesichert
werden, daß man zu einer schon betrachteten Ecke nicht wieder zuruckkehrt: Das Sim-
¨
plexverfahren kann zyklisch werden. Beein¬‚ußt wird dies durch die Wahl von r und s,
die ja im allgemeinen nicht eindeutig bestimmt ist. Naheliegend sind folgende Regeln:
Baumeister: Lineare Algebra II / Stand: August 1996 257


In Schritt 4 : Wahle kleinstes r mit ∆r = min{∆r |∆r > 0}
¨

In Schritt 7 : Wahle kleinstes s mit xs = min{ xi |di > 0, 1 ¤ i ¤ m}.
˜ ˜
¨ ds di

Zyklen werden durch eine solche Festlegung im allgemeinen immer noch nicht vermie-
den. Man kann diesem Problem aber beikommen durch eine Ordnung der Ecken (siehe
Spezialliteratur).

Das Simplexverfahren ben¨tigt beim Start eine Ecke (Phase I). Enth¨lt die Matrix eine
o a
Einheitsmatrix, so ist eine Startecke sofort ablesbar, wenn b ≥ θ gilt. Bei großen Proble-
men ist dies meist, selbst wenn dies der Fall sein sollte, nicht so einfach zu sehen. Hier
gibt es einen Trick“ : Betrachte das Hilfsproblem

Minimiere < e, w >
unter den Nebenbedingungen Ax + w = b, x ≥ θ, w ≥ θ,

wobei e = (1, . . . , 1) ist. Eine L¨sung dieses Hilfsproblems kann man mit dem Simplexver-
o
fahren berechnen, denn hier ist nun eine Startecke bekannt, n¨mlich (θ, b)(o.E. kann b ≥ θ
a
angenommen werden.) Ist nun (x , w ) eine L¨sung dieses Hilfsproblem und ist w— = θ,
— —
o
dann enth¨lt das Ausgangsproblem (LOP) keinen zul¨ssigen Vektor, also Z = …; ist da-
a a
— —
gegen w = θ, dann kann man aus x leicht eine Startecke von (LOP) ableiten.

Es existieren Zeit und Speicher sparende Versionen des Simplexverfahrens. Allerdings ist
auch ein Beispiel bekannt, bei dem alle Ecken durchlaufen werden. In diesem Fall ist die
Anzahl der Rechenschritte exponentiell in der Anzahl der Variablen. Aus der Praxis hat
man die Beobachtung, daß das Verfahren im allgemeinen mit einer Zahl von Rechen-
schritten auskommt, die polynomial in der Anzahl der Variablen/Gleichungen ist. Diese
Beobachtung wird gestutzt durch die Tatsache, daß unter Annahme an die Verteilung der
¨
Daten, im Mittel die Anzahl der Rechenschritte polynomial beschr¨nkt ist. Diese E¬zienz
a
konnte fur zwei Verfahren, die lineare Polygramme l¨sen, erst neulich bewiesen werden:
o
¨
1980 fur die Ellipsoid-Methode von Kachian und 1984 fur den Karmarkov-Algorithmus.
¨ ¨
Sie arbeiten auch mit dem Inneren der zul¨ssigen Menge.
a


9.7 Dualit¨t *
a
Ein wesentlicher Zug der linearen Programmierung ist, daß einem linearen Programm
stets ein duales lineares Programm zugeordnet werden kann, das eine sehr tiefe Einsicht
uber das Ausgangsprogramm liefert. In unserem Fall ist das duale Programm (LOP)* zu
¨
(LOP) gegeben durch

Maximiere < b, y >
unter den Nebenbedingungen At y ¤ c .

Die zul¨ssige Menge
a
Z — := {y ∈ IR m |Aty ¤ c}
Baumeister: Lineare Algebra II / Stand: August 1996 258


hatten wir bereits benutzt (siehe Lemma 9.48).
Setze

± := inf{< c, x > |z ∈ Z},
±— := sup{< b, y > |y ∈ Z — },

wobei wir ± = ∞ und ±— = ’∞ vereinbaren, falls Z = … bzw. Z — = … gilt.


Lemma 9.55

Seien x ∈ Z, y ∈ Z — . Dann gilt < c, x > ≥ < b, y > .
Beweis:
Mit Hilfe von At y ¤ c, x ≥ θ folgt

<<

. 61
( 63 .)



>>