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
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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
�� =
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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.
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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).
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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
+ + +
- - -
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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:
+ − +− + −+ − +
. . .
. . .
. . ....
.
.
.
.
.
.
.
.
.
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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 .
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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.
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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.
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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 .
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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
,
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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:
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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
,
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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.
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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.
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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:
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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
=−+=++=++=++
,
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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:
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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:
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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:
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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 ≥≥≥ .
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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:
Mathematik I und II für Ingenieure (IAM) Version2.4/30.11.2003
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.