ij m - uni-due.de · Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003 2 - 3 mit der Koeffizientenmatrix () ij m n a × A = , dem Spaltenvektor x mit den Unbekannten

Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003

2 - 1

1.2 Matrizen, Determinanten, Lineare Gleichungssyst eme und Lineare Optimierung Determinanten sind in der linearen Algebra ein wichtiges Hilfsmittel. Man kann mit ihnen z.B. elementargeometrische Größen sehr elegant beschreiben und die Lösung eines linearen Gleichungssystem mit der Cramerschen Regel direkt angeben. Bevor wir uns mit den Determinanten beschäftigen, wenden wir uns zunächst den damit eng verbundenen Matrizen zu. Definition 1.2.1: Eine Matrix vom Typ (m×n) (oder eine (m×n)-Matrix) ist ein rechteckiges Zahlen-schema der Form

��

�

�

��

�

�

=

−

−

−

mnmnmm

nn

nn

aaaa

aaaa

aaaa

121

2122221

1111211

....

.

.

.

.

.

.

.....

...

...

A

Die Zahlen aij ∈ � heißen Komponenten (oder Elemente) der Matrix A. Wir schrei-

ben auch abkürzend

( )

nmija×

=A .

Bemerkung 1.2.1: Die (n×1)-Matrizen sind Spaltenvektoren der Länge n und die (1×n)-Matrizen sind Zeilenvektoren der Länge n. Beispiel 1.2.1:

Die Matrix ��

��

�=

402

531A ist vom Typ (2×3).

Definition 1.2.2: Eine (m×n)-Matrix ( )

nmija×

=A wird mit einem Spaltenvektor x�

der Länge n multipli-

ziert, indem man mit jedem Zeilenvektor der Matrix A und dem Spaltenvektor �x wie


2 - 2

beim Skalarprodukt die Produktsumme bildet. Das Ergebnis der Multiplikation ist der folgende Spaltenvektor

��

�

�

��

�

�

+++

++++++

=

��

�

�

��

�

�

��

�

�

��

�

�

=

−

−

−

nmnmm

nn

nn

nmnmnmm

nn

nn

xa...xaxa.

.

.xa...xaxa

xa...xaxa

x

.

.

.

x

aaaa

aaaa

aaaa

2211

2222121

12121111

121

2122221

1111211

....

.

.

.

.

.

.

.....

...

...

xA�

.

Mit Hilfe von Matrizen können lineare Gleichungssysteme sehr einfach dargestellt werden. Ein allgemeines lineares Gleichungssystem mit m linearen Gleichungen für n Unbekannte x1,...,xn hat die Form

(1.2.1)

��

�

��

=+++

=+++=+++

mnmnmm

nn

nn

bxa...xaxa.

.

.bxa...xaxa

bxa...xaxa

2211

22222121

11212111

mit den Koeffizienten aij ∈ � und den Absolutgliedern bi ∈ �. Kommt eine Unbe-kannte xi in der Gleichung nicht vor, dann hat sie dort den Koeffizienten 0. Für das Gleichungssystem (1.2.1) schreiben wir:

(1.2.2)

��

�

�

��

�

�

=

��

�

�

��

�

�

��

�

�

��

�

�

mnmnmm

n

n

b.

.

.b

b

x.

.

.x

x

a...aa.

.

.

.

.

.

.

.

.a...aa

a...aa

2

1

2

1

21

22221

11211

oder kurz (1.2.3) bxA

�� =


2 - 3

mit der Koeffizientenmatrix ( )

nmija×

=A , dem Spaltenvektor x�

mit den Unbekannten

xi , 1 ≤ i ≤ n, und dem Spaltenvektor b�

der rechten Seite mit den Absolutgliedern bi , 1 ≤ i ≤ m. Definition 1.2.3: Das lineare Gleichungssystem (1.2.2) bzw. (1.2.3) heißt homogen, falls b

� =

�0 , d.h.

alle bi sind gleich Null, sonst inhomogen. Beispiel 1.2.2: (i) Das Gleichungssystem

�

=+=+53

123

21

21

xx

xx

lautet in der Matrizenschreibweise

��

��

�=��

��

��

��

�

5

1

13

23

2

1

x

x.

(ii) Für das Gleichungssystem

��

�

=++−=+

=−+

3753

2

132

321

21

321

xxx

xx

xxx

erhalten wir:

��

�

�

��

�

�

=��

�

�

��

�

�

��

�

�

��

�

�

−

−

3

2

1

753

011

132

3

2

1

x

x

x

.

Kommen wir nun zu den Determinanten, die allerdings nur für Matrizen mit gleicher Anzahl von Zeilen und Spalten definiert sind; d.h. wir betrachten im folgenden (n×n)-Matrizen und lineare Gleichungssysteme mit n Gleichungen und n Unbekannten.


2 - 4

Definition 1.2.4:

Sei ��

��

�=

2221

1211

aa

aaA eine (2×2)-Matrix. Die Zahl

( ) 211222112221

1211 aaaaaa

aadet −== :A

heißt Determinante der (2×2)-Matrix A. Beispiel 1.2.3:

(i) 165235152

31−=−=⋅−⋅=��

�

��

�det

(ii) 101424278382

73=−=⋅−⋅=

Die Determinante einer (3×3)-Matrix wird über die Determinante einer (2×2)-Matrix wie folgt definiert. Definition 1.2.5:

Sei ��

�

�

��

�

�

=

333231

232221

131211

aaa

aaa

aaa

A eine (3×3)-Matrix, dann ist

( )2322

131231

3332

131221

3332

232211

333231

232221

131211

aa

aaa

aa

aaa

aa

aaa

aaa

aaa

aaa

det +−== :A .

Eine Rechenregel, die nur für dreireihige Determinanten gilt, ist die Regel von Sarrus (Französischer Mathematiker 1798 - 1861).


2 - 5

(1.2.4)

( )

.aaaaaaaaaaaaaaaaaa

a

a

a

a

a

a

aaa

aaa

aaa

det

122133112332132231322113312312332211

32

22

12

31

21

11

333231

232221

131211

−−−++=

=A

Wie man dem Schema (1.2.4) entnimmt, werden die 1. und die 2. Spalte noch ein-mal neben die Determinante geschrieben. Dann werden in Richtung der Pfeile zum "+"-Zeichen die positiven Summanden als Produkt der Diagonalen gebildet und die negativen Summanden entsprechend als Produkt der Diagonalen in Richtung zum "-"-Zeichen. Beispiel 1.2.4:

Sie ��

�

�

��

�

�

−−−

=563

212

320

A , dann erhalten wir mit der Regel von Sarrus:

det(A) = 53200936120

6

1

2

3

2

0

563

212

320

−=−−−−+=−

−−−−

.

Für einen weiteren wichtigen Satz der Determinantenberechnung benötigen wir den Begriff der Unterdeterminante. Streichen wir in einer Determinante die Zeile und die Spalte, die zu einem bestimm-ten Element der Determinante gehören, so bilden die nicht durchgestrichenen Ele-mente die zu diesem Element gehörende Unterdeterminante. Die Unterdeterminante des Elementes aij heißt det(Aij), wobei Aij die nach dem obigen Prinzip gebildete Untermatrix ist. Beispiel 1.2.5:

Aus

333231

232221

131211

aaa

aaa

aaa

ergibt sich die zu a11 gehörende Unterdeterminante als

det(A11)= 3332

2322

aa

aa

+ + +

- - -


2 - 6

und mit

333231

232221

131211

aaa

aaa

aaa

ist die zu a23 gehörende Unterdeterminante

det(A23)= 3231

1211

aa

aa.

Stellt man z. B. eine dreireihige Determinante dar durch

2322

131231

3332

131221

3332

232211

333231

232221

131211

aa

aaa

aa

aaa

aa

aaa

aaa

aaa

aaa

+−= ,

so sprechen wir von der Entwicklung der Determinante nach der ersten Spalte . Wie Determinanten nach den Elementen einer anderen Zeile(Spalte) entwickelt wer-den, wird festgelegt in folgendem Satz 1.2.1: Eine Determinante wird nach den Elementen einer Zeile(Spalte) entwickelt, indem die Elemente der entsprechenden Zeile(Spalte) mit ihren zugeordneten Unterdeter-minanten multipliziert und die Produkte summiert werden. Dabei bekommt jedes Produkt aus Element und Unterdeterminante das Vorzeichen, das sich aus der Stel-lung des Elements in dem folgenden Schema ergibt (Schachbrettregel):

+ − +− + −+ − +

.

Diesen Satz nennt man auch den Entwicklungssatz von Laplace . Den Laplace-schen Entwicklungssatz können wir auch auf beliebige (n×n)-Matrizen anwenden. Als Verallgemeinerung für den Sonderfall n = 3 erhalten wir für beliebiges n ∈ � die folgende


2 - 7

Bemerkung 1.2.2: Für die Entwicklung einer Determinanten nach der i-ten Zeile erhalten wir analog: ( ) ( ) ( ) ( ) ( ) ( ) ( )inin

in2i2i

i21i1i

i1 Adeta1...Adeta1Adeta1Adet +++ −++−+−= . Der Vorzeichenfaktor der Elemente kann auch im allgemeinen Fall des Laplace-schen Entwicklungssatzes mit der Schachbrettregel bestimmt werden.

Beispiel 1.2.6:

Wir berechnen die Determinanten der Matrix

��

�

�

��

�

�

−−

=

1342

2360

0123

1021

A .

Mit dem Laplaceschen Entwicklungssatz erhalten wir für die Entwicklung nach der ersten Spalte:

Rekursive Definition der Determinante: Für n ≥ 3 ist die Entwicklung einer Determinante det(A) nach der k-ten Spalte gege-ben durch ( ) ( ) ( ) ( ) ( ) ( ) ( )nknk

knk2k2

k2k1k1

k1 Adeta1...Adeta1Adeta1Adet +++ −++−+−= , wobei Aik die (n-1)×(n-1)-Matrix bezeichnet, die aus A durch Entfernen (Streichen) der k-ten Spalte und der i-ten Zeile entsteht (1 ≤ i ≤ n).

Schachbrettregel:

+ − +− + −+ − +

. . .

. . .

. . ....

.

.

.

.

.

.

.

.

.


2 - 8

��

�

�

��

�

�

−−

=134

236

012

11A , ��

�

�

��

�

�

−=134

236

102

21A ,

��

�

�

��

�

�

−=134

012

102

31A , ��

�

�

��

�

�

−−=

236

012

102

41A

Somit gilt:

( ) ( ) ( ) ( ) ( )

( )

.

det2det0det3det1det

72

16224332

−=

−⋅−⋅−−=

⋅−⋅+⋅−⋅= 41312111 AAAAA

Bemerkung 1.2.3: Es ist natürlich günstig eine Determinante nach der Zeile oder Spalte zu entwickeln, in der möglichst viele Nullen vorkommen. Einige Rechenregeln für Determinanten gibt der folgende Satz 1.2.2: (i) Vertauscht man zwei Spalten oder Zeilen einer Determinante, so wechselt die Determinante das Vorzeichen. (ii) Eine Determinante wird mit einer Zahl r ∈ � multipiziert, indem man alle Ele-

mente einer Zeile oder einer Spalte mit dieser Zahl multipliziert; also:

��

�

�

��

�

�

⋅=

��

�

�

��

�

�

⋅

n

i

1

n

i

1

z

z

z

z

z

z

��

��

�

��

��

�

rr detdet bzw. ( ) ( )ni1ni1 s,,s,,ss,,s,,s

��

��

��

��

�⋅=⋅ rr detdet .


2 - 9

(iii) Man addiert zwei Determinanten, die sich nur in den Elementen einer Spalte

(Zeile) unterscheiden, indem die Elemente dieser Spalten (Zeilen) addiert und die übrigen beibehalten werden; also:

��

�

�

��

�

�

+=

��

�

�

��

�

�

+

��

�

�

��

�

�

n

1

n

1

n

1

z

ba

z

z

b

z

z

a

z

��

��

�

��

��

�

��

��

�

detdetdet bzw.

( ) ( ) ( )n1n1n1 s,,ba,,ss,,b,,ss,,a,,s

��

��

��

��

��

��

� +=+ detdetdet (iv) Wenn zwei Spalten (Zeilen) einer Determinante einander proportional sind; d.h. jir ≠⋅= ,ji ss

�� bzw. jir ≠⋅= ,ji zz

��, für ein r ∈ �,

dann hat die Determinante den Wert Null. (v) Addiert man zu den Elementen einer Spalte (Zeile) ein beliebiges Vielfaches der

Elemente einer anderen Spalte (Zeile), so ändert sich der Wert der Determinante nicht; also:

��

�

�

��

�

�

=

��

�

�

��

�

�

⋅+

n

j

i

1

n

j

ji

1

z

z

z

z

z

z

zz

z

��

��

��

�

��

��

��

�

detdet

r

bzw.

( ) ( )nji1njji1 s,,s,,s,,ss,,s,,ss,,s

��

��

��

��

��

��

�detdet =⋅+ r

Bemerkung 1.2.4: Ein Vorteil des Laplace'schen Entwicklungssatzes liegt darin, dass man nach Satz 1.2.1 die Zeilen bzw. Spalten einer Determinante so lange umformen kann, bis eine Spalte (Zeile) aus möglichst vielen Nullen besteht. Entwickeln wir die Determinante dann nach dieser Spalte (Zeile), so wird der Rechenaufwand erheblich reduziert.


2 - 10

Beispiel 1.2.7:

Wir berechnen die Determinante

439

2515

462370

. Durch elementare Umformungen er-

halten wir:

1443

25103

430

250

46231

433

255

462323

3

43033

25053

46231233

439

2515

462370

=+=+=+++

= ..

.

.

.

.

Kommen wir nun zur so genannten Cramer-Regel . Satz 1.2.3 (Cramer-Regel): Sei ( ) nnIR ×∈= n1 a,...,aA

�� mit det(A) ≠ 0 und nIR∈b

�. Dann hat das Gleichungs-

system

��

�

�

��

�

�

=

��

�

�

��

�

�

��

�

�

��

�

�

nnnnnn

n

n

b

b

b

x

x

x

a...aa

a...aa

a...aa

��

2

1

2

1

21

22221

11211

die Lösung:

Um xi zu ermitteln, wird also die i-te Spalte der Matrix A durch den Spaltenvektor b

�

ersetzt. Das Verfahren wird im folgen Beispiel verdeutlicht. Beispiel 1.2.8: (i) Gesucht ist die Lösung des Gleichungssystems

�

−=−=+

175

332

21

21

xx

xx.

( ) n1,...,i,detdet

x i == +− )a,...,a,b,a,...,a(A n1i1i1

��1.


2 - 11

Da 02975

32≠−=��

�

��

�

−det , erhalten wir mit der Cramer-Regel:

29

18

71

33

29

1 =��

��

�

−−−= detx1 und

29

17

15

32

29

1 =��

��

�

−−= detx2 .

(ii) Ein Goldschmied hat drei Stangen Legierung. Diese enthalten die Stoffe Gold,

Silber und Kupfer wie folgt

Gold Silber Kupfer 1. Stange 1 g 8 g 12 g 2. Stange 8 g 10 g 2 g 3. Stange 10 g 6 g 14 g

Aus diesen Stangen will er eine Stange herstellen, die 10 g Gold, 10 g Silber und 11 g Kupfer enthält. Wie viel Gramm muss er von jeder Stange nehmen?

Gesucht ist also die Lösung des Gleichungssystems

��

�

=++=++=++

1114212

106108

10108

321

321

321

xxx

xxx

xxx

.

Da 1232

14212

6108

1081

−=��

�

�

��

�

�

det , gilt:

��

�

�

��

�

�

−=

14211

61010

10810

1232

1detx1 ,

��

�

�

��

�

�

−=

141112

6108

10101

1232

1detx2 und

��

�

�

��

�

�

−=

11212

10108

1081

1232

1detx3 .


2 - 12

Also: 0,1720x1 ≈ , 0,5244x2 ≈ und 0,5633x3 ≈ .

Von der ersten Stange muss man daher 21⋅x1 g, von der zweiten 20⋅x2 g und von der dritten 30⋅x3 g nehmen.

Wichtiger Hinweis: Die Cramersche Regel kann nur für (n x n)-Gleichungssysteme benutzt werden; also für Gleichungssysteme, die aus n Gleichungen mit jeweils n Unbekannten bestehen. Ferner ist die Cramer-Regel für größere Gleichungssysteme sehr rechenintensiv und wegen der rekursiven Struktur der Determinante nicht leicht zu programmieren. Ein Verfahren, das die Lösbarkeit von linearen (nxm)-Gleichungssystemen überprüft und auch alle Lösungen bestimmen kann, ist der Gauß-Algorithmus, der zunächst an zwei ausführlichen Beispielen erklärt werden soll. Anschließend soll der Gauß-Algorithmus für allgemeine Fälle beschrieben werden. Die grundlegende Idee dieses Algorithmus ist, ein Gleichungssystem in eine geeig-nete Form zu bringen (die sogenannte Zeilenstufenform); und zwar durch Anwen-dung der folgenden Rechenregel: Das k-fache einer Gleichung des Systems wird zu einer anderen addiert mit dem Ziel, die Koeffizientenmatrix A des Gleichungssystems bxA

�� = so umzuformen, dass eine Matrix B entsteht, die unterhalb der Hauptdiagonalen nur Nullen hat. Dabei wird natürlich die rechte Seite das Systems ebenfalls umgeformt und wir erhalten das neue Gleichungssystem cxB

�� = . Bei dieser Umformung bleiben die Lösungsmengen der beiden Gleichungssysteme gleich. Notationen: Die folgenden Notationen sind in der Matrizenrechnung sehr hilfreich: (i) Rij bezeichnet das Vertauschen der i-ten und j-ten Zeile einer Matrix (ii) rRi bezeichnet die Multiplikation der i-ten Zeile einer Matrix mit einem

Skalar r ≠ 0. (iii) Ri ± rRj bezeichnet die Addition (Subtraktion) des r-fachen der Elemente

der j-ten Zeile zu (von) den entsprechenden Elementen in der i-ten Zeile. Beispiel 1.2.9: Wir betrachten zunächst noch einmal das Gleichungssystem

(1.2.5) ��

�

=++=++=++

1114212

106108

10108

321

321

321

xxx

xxx

xxx

,


2 - 13

das wir bereits mit der Cramer-Regel gelöst haben und lösen es sehr ausführlich mit Hilfe der oben beschriebenen Umformungen: 1. Schritt:

Wir multiplizieren die erste Zeile des obigen Systems (1.2.5) mit 811

21 =aa

und

subtrahieren dann diese Zeile von der zweiten. Somit erhalten wir folgendes äquivalentes System:

��

�

=++−=−−

=++

1114212

707454

10108

321

32

321

xxx

xx

xxx

In der oben festgelegten Notation können wir auch schreiben:

��

�

=++=++=++

1114212

106108

10108

321

321

321

xxx

xxx

xxx

⇔ ��

�

=++−=−−

=++

1114212

707454

10108

321

32

321

xxx

xx

xxx

R2 − 8R1

Diese Schreibweise bedeutet, dass das zweite Gleichungssystem durch die angege-benen Zeilenoperationen aus dem vorhergehenden entstanden ist. Wir werden gleich eine sehr übersichtliche und kurze Schreibweise kennen lernen, die die so genannte erweiterte Koeffizientenmatrix benutzt. 2. Schritt:

Wir multiplizieren die erste Zeile des obigen Systems (1.2.5) mit 1211

31 =aa

und sub-

trahieren dann diese Zeile von der dritten. Wir erhalten das System:

��

�

−=−−−=−−

=++

10910694

707454

10108

32

32

321

xx

xx

xxx


2 - 14

3. Schritt:

Wir multiplizieren die zweite Zeile des Systems in Schritt 2 mit 27

47

54

94

21

32 ==aa

und

subtrahieren dann diese Zeile von der dritten. Wir erhalten das System:

��

�

��

=

−=−−=++

27

347

27

616707454

10108

3

32

321

x

xx

xxx

Die Lösung lässt sich jetzt sehr einfach bestimmen. Aus der dritten Gleichung erhal-

ten wir sofort 0,5633117x3 ≈=616

347. Setzen wir das in der zweiten Gleichung ein, so

erhalten wir 0,5244x2 ≈ und schließlich aus der ersten Gleichung 0,1720x1 ≈ . Beispiel 1.2.10: Gegeben sei das (3 x 5)-Gleichungssystem mit

��

�

�

��

�

�

−−−=

42724

20302

11111

A , ��

�

�

��

�

�

=2

0

1

b�

.

Also:

(1.2.6) ��

�

=−+−+−=++=++++

242724

0232

1

54321

531

54321

xxxxx

xxx

xxxxx

1. Schritt:

Wir multiplizieren die erste Zeile des Systems (1.2.6) mit 211

21 =aa

und subtrahieren

dann diese Zeile von der zweiten. Somit erhalten wir folgendes äquivalentes System:

��

�

=−+−+−−=−+−

=++++

242724

222

1

54321

432

54321

xxxxx

xxx

xxxxx


2 - 15

2. Schritt:

Wir multiplizieren die erste Zeile des Systems (1.2.6) mit 411

31 −=aa

und subtrahieren

dann diese Zeile von der dritten. Das äquivalentes System ist dann:

(1.2.7) ��

�

=+−+−=−+−

=++++

6636

222

1

432

432

54321

xxx

xxx

xxxxx

3. Schritt:

Wir multiplizieren die zweite Zeile des Systems (1.2.7) mit 322

32 −=aa

und subtrahieren

dann diese Zeile von der dritten. Das äquivalentes System lautet:

��

�

=⋅+⋅−=−+−

=++++

000

222

1

43

432

54321

xx

xxx

xxxxx

Die letzte Gleichung ist immer erfüllt, egal welche Werte wir für 3x und 4x einsetzen. Wir haben also aus dem Ausgangssystem folgendes Gleichungssystem abgeleitet:

(1.2.8) ��

�

=⋅+⋅+⋅+⋅+⋅−=⋅+−+−⋅

=++++

000000

20220

1

54321

54321

54321

xxxxx

xxxxx

xxxxx

Die zugeordnete Koeffizientenmatrix lautet:

��

�

�

��

�

�

−−=00000

02120

11111

B und ��

�

�

��

�

�

−=0

2

1

c�

.

Die Gleichungssysteme bxA

�� = und cxB�� = sind äquivalent. Wir können jetzt das

umgeformte System lösen, wobei alle Lösungen des ersten Systems gefunden wer-den. Stellen wir die zweite Gleichung im System (1.2.8) nach 2x um, so erhalten wir:

432 xx21

1x +−= .

Setzen wir diesen Ausdruck für 2x in der ersten Gleichung von (1.2.7) ein, so folgt:


2 - 16

5431 xx2x21

1x −−−−= .

Die Unbekannten 3x , 4x und 5x können beliebig vorgegeben werden, die Unbe-

kannten 1x und 2x sind danach bestimmt. Das Gleichungssystem hat also unendlich viele Lösungen. Die Umformungen, die in den beiden oberen Beispielen gezeigt wurden, werden übersichtlicher, wenn sie an der erweiterten Koeffizientenmatrix durchgeführt wer-den. In dieser Matrix wird die rechte Seite der Gleichung als neue Spalte aufgenom-men. Erweiterte Koeffizientenmatrix:

(1.2.9) ( )��

�

�

��

�

�

=

mmnmm

n

n

ba...aa

ba...aa

ba...aa

b,AK

21

222221

111211

��

�.

Die elementaren Umformungen dieser erweiterten Koeffizientenmatrix, so dass unter der Hauptdiagonalen der Matrix A nur noch Nullen stehen, sind: (i) Vertauschen zweier Zeilen (ii) Multiplikation einer Zeile mit einer reellen Zahl 0≠r (iii) Addition des r-fachen einer Zeile zu einer anderen. Im folgenden Beispiel wird gezeigt, wie die Gleichungssysteme aus den Beispielen Beispiel 1.2.9 und 1.2.10 mit Hilfe der erweiterten Koeffizientenmatrix sehr übersicht-lich gelöst werden können. Beispiel 1.2.10: (i) Wir betrachten wieder das Gleichungssystem

��

�

=++=++=++

1114212

106108

10108

321

321

321

xxx

xxx

xxx

,


2 - 17

Die erweiterte Koeffizientenmatrix, auf die wir im Folgenden unsere Zeilenumfor-mungen anwenden, lautet:

��

�

�

��

�

�

11

10

10

14212

6108

1081

⇔ ��

�

�

��

�

�

−−−11

70

10

14212

74540

1081

R2 − 8R1

⇔ ��

�

�

��

�

�

−−

−−−−

109

70

10

106940

74540

1081

R3 − 12R1

⇔

��

�

�

��

�

�

−−−

27

34770

10

27

61600

74540

1081

R3 − (47/27)R2

Mittels Rückwärtssubstitution (diese wird in folgenden Beispielen noch ausführlich beschrieben) erhalten wir somit mit Hilfe der dritten Zeile der erweiterten Koeffizien-tenmatrix:

0,5633117x3 ≈=616

347.

Aus der zweiten Zeile erhalten wir nach Einsetzen des Wertes für 3x den Wert für

2x ; und zwar: 0,5244x2 ≈ . Aus der ersten Zeile folgt schließlich 0,1720x1 ≈ . (ii) Die erweiterte Koeffizientenmatrix für das Gleichungssystem (1.2.6) lautet:

��

�

�

��

�

�

−− 2

0

1

42724

20302

11111


2 - 18

⇔ ��

�

�

��

�

�

−−−

−−2

2

1

42724

02120

11111

R2 − 2R1

⇔ ��

�

�

��

�

�

−−

−−6

2

1

06360

02120

11111

R3 − (-4)R1

⇔ ��

�

�

��

�

�

−−−0

2

1

00000

02120

11111

R3 − (-3)R2

In der zweiten Zeile können wir zwei Variablen frei wählen z. B. 3x und 4x . Stellen

wir die zweite Zeile nach 2x um, so erhalten wir:

432 xx21

1x +−= .

Setzen wir diesen Ausdruck für 2x in der ersten Gleichung ein, so folgt:

5431 xx2x21

1x −−−−= .

Die Unbekannten 3x , 4x und 5x können wieder beliebig vorgegeben werden und

die Unbekannten 1x und 2x sind danach bestimmt. Allgemeine Form des Gauß-Algorithmus: Falls 11a = 0 ist, vertausche die Zeilen, bis 011 ≠a ist. Multipliziere die erste Zeile mit

11

21

a

a− und addiere diese zur zweiten. Multipliziere die erste Zeile mit

11

31

a

a− und addie-

re sie zur dritten usw. Durch diese Umformungen entsteht aus der Ausgangsmatrix (1.2.6) eine Matrix der Form


2 - 19

��

�

�

��

�

�

mmnm

n

n

cdd

cdd

baaa

...0

...0

...

2

2222

111211

��.

Für die neu entstandene Untermatrix

��

�

�

��

�

�

mmnmm

n

n

cddd

cddd

cddd

...

...

...

32

333332

222322

��

führen wir im 2. Eliminationsschritt die oben beschriebenen Umformungen wieder durch. Also, falls 22d = 0 ist, vertausche die Zeilen, bis 022 ≠d . Gibt es so eine Zahl

nicht, ist der 2. Schritt beendet. Falls doch, multipliziere die erste Zeile mit 22

32

d

d− und

addiere sie zur zweiten usw. Die Ausgangsmatrix hat nach diesem Schritt die Form

��

�

�

��

�

�

mmnm

n

n

cee

ceee

baaaa

~...

...

~...

...

3

222322

11131211

00

0

��

Nach höchstens (m –1)-Eliminationsschritten erhalten wir dann eine umgeformte Ko-effizientenmatrix M, die folgendes Aussehen besitzt:

(1.2.10)

rm

rM

−

��

��

��

�

��

�

��

�

�

��

�

�

=

0...00...000

...

0...00...000

*...*0...000

****00

******0

*...******

��

��

Dabei sind die mit * markierten Stellen irgendwelche Zahlen, die durch Umformung berechnet wurden. Die Anzahl der von Null verschiedenen Zeilen der aus A mittels Gauß-Algorithmus entstandenen Matrix M nennt man den Rang von A; also r = Rang A.


2 - 20

Man kann zeigen, dass der Rang einer Matrix A nicht von den speziellen Eliminati-onsschritten abhängt. Falls r = n = m ist, also alle Zeilen von Null verschieden sind, so hat M die Form

(1.2.11)

��

�

�

��

�

�

•••••••••••••••••

=

0...000

...0

...000

...00

...0

...

��

M

Satz 1.2.4: (i) Das homogene Gleichungssystem 0xA

�� = hat genau dann nur die Lösung 0...21 ==== nxxx wenn gilt: Rang A = n.

(ii) Die allgemeine Lösung des linearen Gleichungssystems 0�� =xA hat

(n – Rang A) frei wählbare Variable.

(iii) Ist die Anzahl der Gleichungen kleiner als die Anzahl der Unbekannten; also m < n, dann besitzt das homogene System 0xA

�� = von Null verschiedene Lösungen.

(iv) Das inhomogene System bxA

�� = ist genau dann lösbar, wenn gilt: ( ) )Rang(Rang AbA/ =

�.

(v) Ist das System bxA

�� = lösbar, dann lässt sich die allgemeine Lösung darstellen als uxx 0

�� += . Dabei ist 0x

�eine spezielle Lösung des Systems bxA

�� = und u�

die allgemeine Lösung des zugehörigen homogenen Problems.


2 - 21

Hat man die erweiterte Koeffizientenmatrix ( )bA,�

K mittels Gauß-Algorithmus in die

Form ( )dA/�

M gebracht, wobei

(1.2.12)

rm

r

d

d

d

d

d

dAM

m

r

r

−

��

��

��

�

��

�

��

�

�

��

�

�

=

+

��

��

1

2

1

0...00...000

...

0...00...000

*...*0...000

****00

******0

*...******

)/( ,

kann folgende Lösbarkeitsentscheidung getroffen werden: Ist eine der Zahlen m1r d,...,d + in (1.2.9) von Null verschieden, so hat das Glei-

chungssystem bxA�� = keine Lösung. Ist z. B. 0d 1r ≠+ , so erhalten wir den Wider-

spruch 0dx0...x0x0 1rn21 ≠=⋅++⋅+⋅ + . Ist dagegen 0d....d m1r ===+ , so können wir aus ( )dA/

�M mittels Rückwärtssubsti-

tution die Lösung(en) berechnen. Sind in der r-ten Gleichung k Koeffizient von Null verschieden, so können wir (k –1) Variable frei wählen. Nachdem wir diese gewählt haben, können wir die k-te Variable berechnen. Genauso verfahren wir mit der (r-1)-ten Gleichung bis hin zur 1-ten Gleichung. Die Rückwärtssubstitution soll noch einmal an einem Beispiel verdeutlicht werden. Beispiel 1.2.11: Mit dem Gauß-Algorithmus sei folgende erweiterte Koeffizientenmatrix bereits be-rechnet worden:

( )��

�

�

��

�

�

−−

−

=

000000

031000

041200

024321

M dA/�

.

Es ist m = 4 und r = 3. Aus der dritten Gleichung folgt: 0x3x 54 =+− . In dieser Gleichung können wir 5x (oder auch 4x ) frei wählen. Setzen wir 25 �x = , so

erhalten wir 24 �3x = . Mit der zweiten Gleichung folgt:


2 - 22

( ) ( ) 0�4�31x2 223 =−⋅+

Also: 23 �21

x = .

Mit der ersten Gleichung ist:

( ) ( ) ( )

2231

21

2231

21

22221

21

�x2x

0�x2x

0�2�34�3x2x

−=⇔=+−⇔

=+++−.

Hier ist 2x frei wählbar. Wir setzen 12 �x = und erhalten als allgemeine parameter-abhängige Lösung ( ) ( ) IR�,�;�;�;3�;�;��2x;x;x;x;x 212222

1122

31154321 ∈−= .

Für jede Wahl der Parameter 21 �,� erhalten wir eine spezielle Lösung. Für 1�1 = und 0�2 = lautet diese spezielle Lösung 0xxx1,x2,x 54321 ===== . Hinweis: Auch der Gauß-Algorithmus ist für das Lösen sehr großer linearer Glei-chungssystem nicht besonders gut geeignet. In der Numerischen Mathematik wer-den wir später andere Lösungsverfahren kennen lernen. Am Schluss dieses Kapitels wollen wir auf Probleme aus dem Gebiet der Linearen Optimierung eingehen und betrachten dazu folgendes Beispiel: Ein Betrieb wird mit der Herstellung der beiden Produkte P1 und P2 beauftragt. Der Reingewinn beträgt für P1 → 20,-- € pro Einheit, P2 → 10,-- € pro Einheit. Zur Fertigung jedes Einzelproduktes werden je 3 Maschinen benötigt. Die Maschi-nenzeiten dürfen für einen bestimmten Zeitraum nicht überschritten werden. Wir erhalten somit folgende Tabelle: Maschine Durchlaufzeiten (h) Maschinenzeitfonds (h) P1 P2 M1 30 10 3000 M2 40 30 6000 M3 10 20 2000


2 - 23

Für Modelle der Linearen Optimierungsrechnung muss ein Optimierungskriterium festgelegt werden. In unserem Beispiel ist das Optimierungskriterium der maximale Reingewinn. Dieser Reingewinn lässt sich mathematisch beschreiben durch (1.2.13) maxzx10x20 21 →=+ . Die Werte für x1 und x2 sollen also so bestimmt werden, dass z einen maximalen Wert annimmt und die obige Produktionstabelle eingehalten wird. Da die Funktion

( ) 2121 x10x20x,xfz +== das Ziel der Optimierung beschreibt, wird sie auch Ziel-funktion genannt. Die Variablen, die in der Zielfunktion vorkommen (hier x1 und x2), entscheiden über den Wert von z. Diese Variablen werden daher als Entschei-dungsvariablen bezeichnet. Da ferner nur positive Mengenzahlen für praktische Probleme sinnvoll sind, führen wir noch die Nichtnegativitätsbedingungen ein: 0xund0x 21 ≥≥ . Insgesamt können wir nun unsere Problem mathematisch wie folgt beschreiben: Zielfunktion: maxzx10x20 21 →=+

Restriktionen:

2000x20x10(3)

6000x30x40(2)

3000x10x30(1)

21

21

21

≤+≤+≤+

Nichtnegativität : 0xund0x 21 ≥≥ Dieses Problem wollen wir mit Hilfe des Simplexverfahrens lösen. Zunächst ver-wandeln wir aber das System von Ungleichungen durch Hinzufügen so genannter Schlupfvariablen iw in ein Gleichungssystem

2000wx20x10(3)

6000wx30x40(2)

3000wx10x30(1)

321

221

121

=++=++=++

.

Diese Schlupfvariablen stellen einen Ausgleich zwischen der rechten und der linken Seite der Ungleichungen im System der Restriktionen dar. Zu diesen drei Gleichun-gen fügen wir noch die Zielfunktion hinzu und erhalten somit eine Gleichungssystem mit vier Gleichungen; nämlich:

0zx10x20(4)

2000wx20x10(3)

6000wx30x40(2)

3000wx10x30(1)

21

321

221

121

=−+=++=++=++

,


2 - 24

mit 0z,,w,w,wx,x 32121 ≥ . Die Schlupfvariablen unterliegen natürlich auch der Nichtnegativitätsbedingung, da sie ja den Ausgleich zwischen der linken und der rechten Seite des Systems bilden. Wir haben somit ein lineares inhomogenes Gleichungssystem mit (m+1) Gleichun-gen und n+(m+1) Variablen. Im Beispiel ist n = 2 und m = 3, also haben wir 4 Glei-chungen mit 6 Variablen. Ein solches unterbestimmtes Gleichungssystem hat im all-gemeinen unendlich viele Lösungen, die dadurch ermittelt werden, dass n beliebige Variablen als freie Variablen gewählt und die übrigen, die so genannten gebunde-nen Variablen , in Abhängigkeit dieser freien Variablen berechnet. Bemerkung 1.2.5: (i) Eine Lösung eines Optimierungsproblems heißt zulässig, wenn für alle Variablen

die Nichtnegativitätsbedingung erfüllt ist.

(ii) Haben in einer zulässigen Lösung die n freien Variablen den Wert Null und sind die anderen (m+1)Variablen alle größer oder gleich Null, so liegt eine zulässige Basislösung vor.

(iii) Die im Allgemeinen von Null verschiedenen Variablen heißen Basisvariablen , die übrigen werden als Nichtbasisvariablen bezeichnet.

Das Simplexverfahren geht bei der Berechnung von einer ersten Basislösung aus (Anfangslösung) und ermittelt aus dieser Anfangslösung sukzessive die Optimallö-sung. Damit gehört es zu den Iterationsverfahren . Lösen wir das obige System nach den Basisvariablen auf, so erhalten wir als Basis-darstellung der Anfangslösung

(1.2.14)

21

213

212

211

x10x200z(4)

x20x102000w(3)

x30x406000w(2)

x10x303000w(1)

−−=−−−=−−=−−=

.

Setzen wir hier die Nichtbasisvariablen 0xx 21 == , so erhalten wir für die Basisvari-ablen 2000w6000,w3000,w 321 === und z = 0. Das Ziel besteht nun darin, durch Variablenaustausch diese Anfangslösung zu verbessern. Um zu ermitteln, gegen welches iw die Variable jx ausgetauscht werden kann, benötigen wir das Quotien-

tenverfahren. Dazu bilden wir die Quotienten iq aus dem Absolutglied iA der Glei-chungen (1) ... (3) in (1.2.14) und aus dem negativen Wert der entsprechenden Ko-effizienten der neuen Basisvariable z. B. 1x . Der kleinste nichtnegative Quotient minq gibt an, gegen welche Basisvariable ausgetauscht wird. Mit Hilfe dieses Quotienten wird also die Zeile ermittelt, in der die neue Basisvariable steht. Eine solche Zeile wird Pivotzeile (PZ) genannt. Somit erhalten wir als Quotienten für:


2 - 25

20010))((:2000q(3)

15040))((:6000q(2)

q10030))((:3000q(1)

3

2

min1

=−−==−−=

==−−=

Für (4) entfällt die Quotientenbildung, da die Zielvariable z nie aus der Basis entfernt wird. Die Umrechnungen erfolgen beim Simplexverfahren in der Simplextabelle, die folgendes Aussehen hat: Tabelle 1

BV 1x 2x iA iq

1w -30 -10 3000 100 �PZ

2w -40 -30 6000 150

3w -10 -20 2000 200

-z -20�PS -10 0 Die Spalte, auf die das Quotientenverfahren angewendet wird, heißt Pivotspalte (PS) und wird durch den betragsmäßig größten Koeffizient der Zielfunktion bestimmt (hier -20). Somit haben wir festgelegt, dass 1x durch 1w ausgetauscht wird. Im Kreuzpunkt von PZ und PS steht das Pivotelement (PE) γ . Umrechnen Tabelle k �� Tabelle (k+1): Pivotzeile (PZ) Pivotspalte (PS) Alle übrigen Elemente

γ

γγ

−=′

=′

jj

zz :.2

1:.1

γ

γγ

ii

ss =′

=′

:.2

1:.1

jiijij zsaa ′⋅+=′ :

Mit diesen Vorschriften erhalten wir Tabelle 2

BV 1w 2x iA iq

1x -1/30 -1/3 100 300

2w 4/3 -50/3 2000 120

3w 1/3 -50/3 1000 60 �PZ

-z 2/3 -10/3�PS -2000 Aus der Tabelle 2 ist die verbesserte Lösung ersichtlich:

2000z1000,2000,w100,wx0x0,w 32121 ====�== . Die Zielfunktion ist nach dem ersten Austauschschritt:


2 - 26

2000x3

10w

32

z 21 ++−= .

Wie wir aus Tabelle 2 nach Festlegung von PZ und PS entnehmen können, tau-schen wir 2x gegen 3w . Tabelle 3

BV 1w 3w iA iq

1x -2/50 1/50 80

2w 1 1 1000

2x 1/50 -3/50 60

-z 3/5 1/5 -2000 Aus Tabelle 3 folgt:

2200z1000,60,wx80,x00,ww 22131 ====�== .

Die Zielfunktion lautet jetzt: 2200w51

w53

z 21 +−−= .

Klar ist, dass z nun nicht mehr verbessert werden kann, da die Zielfunktion zwei Nichtbasisvariablen enthält mit dem Wert Null und negativen Koeffizienten. Wir ha-ben also mit der zweiten verbesserten Lösung die Optimallösung erreicht, die da lau-tet:

2200z60,x80,x max21 === mit einem freien Maschinenfonds von 1000w2 = h für Maschine M2. Ablauf des Simplexalgorithmus für den Normalfall de r Maximierung: (1) Mathematisches Modell aufstellen mit Zielfunktion, Restriktionen und Nichtnega-tivitätsbedingungen. In unserem Beispiel: Zielfunktion: maxzx10x20 21 →=+

Restriktionen:

2000x20x10(3)

6000x30x40(2)

3000x10x30(1)

21

21

21

≤+≤+≤+

Nichtnegativität : 0xund0x 21 ≥≥ (2) Gleichungssystem mit iw als Schlupfvariable und z als Zielvariable. Basisdarstel-lung für die Anfangslösung. In unserem Beispiel:


2 - 27

21

213

212

211

x10x200z(4)

x20x102000w(3)

x30x406000w(2)

x10x303000w(1)

−−=−−−=−−=−−=

.

(3) 1.Simplextabelle mit iw als Basisvariablen (Anfangslösung). In unserem Beispiel: Tabelle 1

BV 1x 2x iA iq

1w -30 -10 3000 100 �PZ

2w -40 -30 6000 150

3w -10 -20 2000 200

-z -20�PS -10 0 (4) Iteration durchführen; und zwar nach folgendem Schema: Enthält die z-Zeile noch ein Element g < 0? Wenn Ja: Auswahl von PS, PZ und PE als Vorbereitung für die nächste Tabelle: 1. PS: Spalte mit kleinstem g < 0 2. PZ: Zeile mit minq 3. PE: Kreuzungspunkt von PS und PZ Austauschverfahren zur Berechnung der Tabelle (k + 1). Gehe zu (4). Wenn Nein: Optimallösung und maxz aus der Tabelle ablesen. Fertig! Der Simplexalgorithmus lässt sich ziemlich einfach programmieren. Im folgenden sehen wir die Eingabe und die Berechnungslauf zu folgendem Optimierungsproblem: Zielfunktion: maxzxx2x4 321 →=++

Restriktionen:

100x1x2x0(4)

50x0x1x1(3)

100x4x0x1(2)

200x0x2x2(1)

321

321

321

321

≤++≤++≤++≤++

Nichtnegativität : 0xund0x0,x 321 ≥≥≥ .


2 - 28

Eingabedatei für das Programm Simplex, das an der Universität Duisburg-Essen im Institut für Angeandte Materialtechnik (IAM) programmiert wurde: * Erste Zeile: Zielfunktion minimieren oder maximieren * Die Zielfunktion wird als zweite Zeile eingelesen max 4 2 1 = z 2 2 0 < 200 1 0 4 < 100 1 1 0 < 50 0 2 1 < 100 Ausgabedatei des Simplex-Programms: Lösungsalgorithmus -> Lineare Optimierung gerechnet am 12.11.01 15:36:31 --------------------------------------------------------------------------------------------------------------------------- Maximiere die Zielfunktion Die 1. Simplextabelle: Pivot-Spalte: 1 Pivot-Zeile: 2 x1 x2 x3 ai qi w1 -2,000 -2,000 0,000 200,000 100,000 w2 -1,000 0,000 -4,000 100,000 100,000 w3 -1,000 -1,000 0,000 50,000 50,000 w4 0,000 -2,000 -1,000 100,000 -1,000 z -4,000 -2,000 -1,000 0,000 0,000 Die 2. Simplextabelle: Pivot-Spalte: 3 Pivot-Zeile: 2 w3 x2 x3 ai qi w1 2,000 0,000 0,000 100,000 -1,000 w2 1,000 1,000 -4,000 50,000 12,500 x1 -1,000 -1,000 0,000 50,000 -1,000 w4 0,000 -2,000 -1,000 100,000 100,000 z 4,000 2,000 -1,000 -200,000 0,000 Die 3. Simplextabelle -> Ergebnistabelle: w3 x2 w2 ai qi w1 2,000 0,000 0,000 100,000 -50,000 x3 0,250 0,250 -0,250 12,500 -50,000 x1 -1,000 -1,000 0,000 50,000 50,000 w4 -0,250 -2,250 0,250 87,500 350,000 z 3,750 1,750 0,250 -212,500 0,000 SAL Ergebnis:


2 - 29

Zielfunktion und Basisvariablen -> w1 = 100,000 x3 = 12,500 x1 = 50,000 w4 = 87,500 z = 212,500 Nichtbasisvariablen -> w3 = 0 x2 = 0 w2 = 0

Weichen wir vom Normalfall der Maximierung ab und lassen im System von Un-gleichungen neben dem kleiner-gleich-Zeichen auch das Gleichheitszeichen oder das größer-gleich-Zeichen zu und betrachten darüber hinaus auch Minimierungs-probleme, so wird der Simplexalgorithmus ein wenig komplizierter. Es kann dann auch vorkommen, dass eine zweite Zielfunktion betrachtet werden muss. Mit dem oben erwähnten Simplex-Programm können aber auch solche Probleme gelöst wer-den. Eine sehr schöne Einführung in die Lineare Optimierung findet man in dem Lehr- und Übungsbuch Mathematik IV , das im Fachbuchverlag Leipzig-Köln er-schienen ist.

Documents

ij m - uni-due.de · Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003 2 - 3 mit der Koeffizientenmatrix () ij m n a × A = , dem Spaltenvektor x mit den Unbekannten