<<

. 60
( 63 .)



>>

Sei x ∈ Z, y ∈ Z — und es gelte < c, x > = < b, y > . Dann ist x eine L¨sung von
o
(LOP).
Beweis:
Sei u ∈ Z. O¬enbar gelten wegen x ≥ θ, u ≥ θ die folgenden Ungleichungen:
< c, u > ≥ < At y, u > = < y, Au > = < y, b > = < c, x > .
Baumeister: Lineare Algebra II / Stand: August 1996 250


Also ist
< c, x > = inf{< c, u > |u ∈ Z}.


Wir fuhren mit Indizes µ1 , . . . , µm ∈ {1, . . . , n} folgende Bezeichnungen ein:
¨

A(µ1 | · · · |µm ) := (aµ1 | · · · |aµm ) ∈ IRm,m ,
C(µ1 | · · · |µm )t := (cµ1 , . . . , cµm ) ∈ IR 1,m .


Ausgangspunkt fur das Simplexverfahren ist nun eine Ecke x ∈ Z mit Basisvariablen
¨
µ1 , . . . , µm . Setze β := {µ1 , . . . , µm }.

Schritt 1 Sei x ∈ IR m,1 de¬niert durch xi := xµi , 1 ¤ i ¤ m.
˜ ˜

Da x nach Voraussetzung Ecke ist, gilt

A(µ1 | · · · |µm )˜ = b , x ≥ θ.
x ˜ (9.4)



Schritt 2 Berechne die eindeutige Losung y von
¨

A(µ1| · · · |µm )t y = c(µ1 | · · · |µm ) (9.5)

und setze
∆ := At y ’ c.
(∆ heißt Schlupf.)


Beachte, daß rg(A(µ1 | · · · |µm )t = m gilt, da aµ1 , . . . , aµm linear unabh¨ngig sind. Wir
a
sehen nun, daß mit Lemma 9.48 auf die Optimalit¨t von x geschlossen werden kann, falls
a
∆ ≥ θ ist. Wir halten dies fest in

Schritt 3 Ist ∆ ≥ θ, so ist x eine Losung von (LOP). STOP
¨


Ist der Optimalit¨tstest in Schritt 3 negativ, so versuchen wir eine neue Ecke zu konstru-
a
¨
ieren. Deren Basisvariablen sollen sich nur in einem Element unterscheiden (Ubergang zu
einer benachbarten“ Ecke/Einzelaustausch).


Schritt 4 Bestimme ein r ∈ {1, . . . , n} mit ∆r < 0.

Wegen (9.5) gilt r ∈ {µ1 , . . . , µm } = β.
/
Baumeister: Lineare Algebra II / Stand: August 1996 251


Schritt 5 Berechne die eindeutige Losung d von
¨
A(µ1| · · · |µm )d = ar (9.6)


Der Vektor d enth¨lt die Koordinaten der Darstellung von ar durch die Basis aµ1 , . . . , aµm .
a
Wir diskutieren die Bedeutung von d fur das weitere Vorgehen. De¬niere dazu fur ∈ IR
¨ ¨
den Vektor x( ) ∈ IR durch
n,1

±
 xi ’ di
˜ , falls j = µi
x( )j := , falls j = r .


0 , sonst
Damit gilt also fur ∈ IR :
¨
m m
(˜i ’ di )a + a =
µi r
xiaµi = b
Ax( ) = x ˜
i=1 i=1

und
m
(˜i ’ di )cµi + cr
< c, x( ) > = x
i=1
= < c(µ1 | · · · |µm ), x > ’ (< c(µ1 | · · · |µm ), d > ’cr )
˜
= < c(µ1 | · · · |µm ), x > ’ (< y, A(µ1| · · · |µm )d > ’cr )
˜
= < c, x > ’ ∆r


Lemma 9.49
Ist d gemaß (9.6) berechnet und gilt d ¤ θ, dann ist das Problem (LOP ) unl¨sbar.
o
¨
Beweis:
Es gilt o¬enbar x( ) ∈ Z fur alle ≥ 0. Dies zeigt
¨
inf < c, x( ) > = ’∞.
≥0




Schritt 6 Ist d ¤ θ, so ist das Problem (LOP ) nicht l¨sbar.
o STOP

Schritt 6 nennen wir den Losbarkeitstest. Fallt er negativ aus, d.h. tritt d ¤ θ nicht
¨ ¨
ein, fahren wir so fort:

:= min{xi d’1 |di > 0, 1 ¤ i ¤ m}.
˜i

Damit gilt
x( ) ∈ Z, x( )l = 0 fur ein l ∈ {µ1 , . . . , µm }.
¨
ist das großtm¨gliche ≥ 0, fur das x( ) zul¨ssig bleibt.)
(Beachte: o a
¨ ¨
Baumeister: Lineare Algebra II / Stand: August 1996 252


Schritt 7 Wahle s ∈ {1, . . . , m} mit
¨

= xµs d’1 , ds > 0,
s

und setze
β := β\{µs } ∪ {r} , x := x( ).



Lemma 9.50

Wird β und x gem¨ß Schritt 7 bestimmt, so ist x Ecke mit Basisvariablen β .
a
Beweis:
O.E. s = 1, d.h. β = {r, µ2 , . . . , µm }. O¬ensichtlich gilt I(x ) ‚ β . Wir uberprufen die
¨ ¨
r µ2 µm
lineare Unabh¨ngigkeit von a , a , . . . , a . Sei dazu
a
m
r
±i aµi = θ.
±a +
i=2

Ist ± = 0, so folgt aus der Tatsache, daß am1 , . . . , aµm linear unabh¨ngig sind, ±2 = · · · =
a
±m = 0. Ist ± = 0, so k¨nnen wir o.E. ± = ’1 annehmen. Dann gilt
o
m
±i aµi = ar
i=2

und ein Vergleich mit (9.6) zeigt

d1 = 0, di = ±i , 2 ¤ i ¤ m.

Nach Wahl von r gilt aber d1 > 0. Widerspruch !

Nach Lemma 9.50 k¨nnen wir nun, vorausgesetzt wir sind nicht in Schritt 3 oder Schritt 6
o
ausgestiegen, mit x := x , β := β bei Schritt 1 fortsetzen. Einige mit Schritt 4 und Schritt
7 zusammenh¨ngende Fragen kl¨ren wir sp¨ter.
a a a

Wir wollen nun die Schritte 1 bis 7 in einem Rechenschema zusammenfuhren, dem soge-
¨
nannten Simplextableau.

In Schritt 1 und Schritt 5 werden Darstellungen von b und ar durch die Basis aµ1 , . . . , aµm
erforderlich. Wir formulieren allgemein:
m m
±k,j a , 1 ¤ j ¤ n, b =
j µk
±k,0 aµk .
a=
k=1 k=1

O¬enbar gilt
±k,µl = δkl , 1 ¤ k, l ¤ m.
Die Koe¬zienten ±k,l sind zu interpretieren als Losungskomponenten einer Gleichung
¨

A(µ1 | · · · |µm )ˆ = ˆ (ˆ = aj oder ˆ = b).
x bb b
Baumeister: Lineare Algebra II / Stand: August 1996 253


Diese kann man auch ablesen, nachdem die ger¨nderte Matrix (A(µ1 | · · · |µm )|ˆ durch
a b)
elementare Umformungen auf eine Form gebracht wurde, in der in den Spalten µ1 , . . . , µm
eine Einheitsmatrix steht.

Wir fassen zusammen (1. Form des Tableaus):

···
1 n
···
µ1 ±1,1 ±1,n ±1,0
. . . .
. . . .
. . . .
···
µm ±m,1 ±m,n ±m,0



Beispiel 9.51

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

wobei
4
2020
c = (1, 3, 0, 0) , A = ,b =
1101 3

ist.
Eine Ecke liegt fur die Basisvariablen µ1 = 1, µ2 = 2 vor. Wir erhalten so aus der ger¨nder-
a
¨
ten Matrix
2020 4
1101 3
durch Umformung schließlich als 1. Form des Tableaus


12 3 4
110 1 02
2 0 1 ’1 1 1

Daraus lesen wir nun in der letzten Spalte auch die Koordinaten der Ecke ab:

x = (2, 1, 0, 0) mit I(x) = {1, 2}

2
Es liegt eine nichtentartete Ecke vor

Der Wert der Zielfunktion in der Ecke x stellt sich folgendermaßen dar:
m m
±k,0 cµk ’ 0.
∆0 :=< c, x > = ±k,0 cµk = (9.7)
k=1 k=1
Baumeister: Lineare Algebra II / Stand: August 1996 254


In Schritt 2 werden die Großen ∆j ben¨tigt.

<<

. 60
( 63 .)



>>