Management Science: Vorbereitung für Simplexverfahren

Lineare Gleichungssysteme

Beispiel Bert

Der Student Bert kauft am Montag 2 Semmeln und 1 l Milch und zahlt 1,80 €. Am Dienstag kauft er 4 Semmeln und 3 l Milch und zahlt 4,60 €. Wieviel kosten eine Semmel und ein Liter Milch?

Wir bezeichnen als x1 den Preis für eine Semmel und als x2 den Preis für einen Liter Milch und erhalten das lineare Gleichungssystem

2x1+x2=1,80;

4x1+3x2=4,60.

Lösung linearer Gleichungssysteme Gaußscher Algorithmus

In der Matrizenrechnung wird aus praktischen Gründen häufig das Additionsverfahren verwendet.

Wie löst man ein LGS?

Beispiel: Betrachten wir das folgende lineare Gleichungssystem

{\begin{matrix}I:&5x1&-x2&+2x3&+3x4&=29\\II:&&3x2&-4x3&+x4&=-7\\III:&&&2x3&+2x4&=30\\IV:&&&&x4&=10.\\\end{matrix}}

Wie könnte man das lösen? Es bietet sich folgende Vorgehensweise an:

Aus IV ist gegeben:

x_{4}=10.

Eingesetzt in III ergibt das

2x3+2\cdot 10=30\Rightarrow x3=5

Eingesetzt in II ergibt das

3x2-4\cdot 5+10=-7\Rightarrow x2=1

Eingesetzt in I ergibt das

5x1-1+2\cdot 5+3\cdot 10=29\Rightarrow x2=-2.

Dieses System war einfach lösbar, aber betrachten wir nun

3x+2y-z=13;

2x-y+3z=-1;

5x-4y+4z=3.

Ideal wäre es, auch hier wieder das Gleichungssystem auf „Dreiecksgestalt“ wie oben zu bringen. Das kann man mit dem Additionsverfahren erreichen. Man wendet hier so genannte elementare Zeilenoperationen an.

Zulässige Zeilenoperationen sind

Multiplikation einer Zeile mit einer Konstanten,
Addition einer Zeile auf eine andere (bzw. Subtraktion),
Vertauschen zweier Zeilen.

Für die manuelle Durchführung der Zeilenoperationen fasst man alle Zeilen zweckmäßigerweise in einem so genannten Tableau zusammen.

Beispiel von oben:

Tableau:

x₁ x₂ x₃ | b
------------
3  2 -1 |13
2 -1  3 |-1
5 -4  4 | 3

In der ersten Zeile sind aus Übersichtlichkeitsgründen die zu den Koeffizienten gehörenden Variablennamen angegeben.

Die Spalten des Tableaus werden nun von links nach rechts abgearbeitet:

Die 1. Spalte soll sein: ${\begin{pmatrix}3\\0\\0\end{pmatrix}}$

Ein Vielfaches der 1. Zeile wird von einem Vielfachen der 2. Zeile subtrahiert:

___________________________________________________________

Ein Vielfaches der 1. Zeile wird von einem Vielfachen der 3. Zeile subtrahiert.:

___________________________________________________________

Neues Tableau als Zwischenergebnis:

Die 2. Spalte soll sein:

Ein Vielfaches der 2. Zeile wird von einem Vielfachen der 3. Zeile subtrahiert.

___________________________________________________________

Neues Tableau als Ergebnis:

Das entspricht dem Gleichungssystem

das nun rekursiv von unten nach oben gelöst werden kann.

Man nennt dieses Verfahren, nämlich das Gleichungssystem in Dreiecksgestalt umzuwandeln,

Gaußscher Algorithmus oder Gaußsches (teilweises) Eliminationsverfahren

Vollständiges Eliminationsverfahren

Das Gaußsche Eliminationsverfahren ermöglicht eine rekursive Berechnung der Variablen von unten nach oben. Das LGS kann aber weiter umgeformt werden, so dass z.B. ein Tableau der Form

entsteht. Hier kann die Lösung direkt abgelesen werden:

Man nennt dieses Verfahren vollständiges Gaußsches Eliminationsverfahren. Das Verfahren ist zwar aufwendiger, wird aber aus verschiedenen Gründen häufig angewendet, vor allem in der Datenverarbeitung.

Beispiel:

Gegeben ist das Tableau

2 0 1 2 1 2 2 1 0 1 1 3

das mit Hilfe der vollständigen Elimination umgeformt werden soll.

Man erhält als Ergebnis

1 0 0 7 0 1 0 15 0 0 1 -12

Wir erhalten die Lösungen x1 = 7; x2 = 15; x3 = -12.

Es ist eine gute Übung, die Transformation selber zu versuchen.

In diesem Beispiel waren 3 Gleichungen und 3 Variablen gegeben, wobei jede der Gleichungen eine eigenständige Information enthalten hat. Es gab eine eindeutige Lösung.

Beispiel:

Bert kauft wieder ein und wir haben heute.

Mo 2 Se 1l Mi 1,80 € Di 4 Se 2l Mi 3,60 €

Gleichungssystem:

2x1 + x2 = 1,8 4x1 + 2x2 = 3,6 2 Gleichungen, 2 Unbekannte

Hier ist II eigentlich nur 2I, also steckt in II keine neue Information mehr. Es ist faktisch nur eine Gleichung gegeben. Das Tableau zur Lösung

2 1 1,80 4 2 3,6

ergibt nach Umformung

1 0,5 0,9 0 0 0

Es bleibt nur eine Gleichung übrig: x1 + 0,5x2 = 0,9.

Also ist x2 = 1,8 -2x1.

Weitere Informationen kann man aus der Gleichung nicht gewinnen. Man kann aber x1 einen Wert zuweisen und das resultierende x2 bestimmen, z.B. x1=0,5 → x2= 0,8 oder . x1=0,1 → x2= 0,1,6. Es gibt daher unendlich viele Lösungen. Eine sogenannte spezielle Basislösung ist x1=0→ x2= 1,8.

Es soll unter Verzicht auf Matrizentheorie auf Basislösungen eingegangen werden.

Gegeben ist das Gleichungssystem

1x1 + 2x2 + 3x3 + 4x4 + 5x5 + 6x6 = 50 1x1 + 1x3 + 1x5 =10 1x1 + 1x4 = 10 1x1 + 1x2 + 2x3 + 2x4 + 3x5 + 3x6 = 30.

Es soll wieder vollständige Elimination angestrebt werden, was aber nicht vollständig möglich sein wird, da es 6 Variablen, aber nur 4 Gleichungen gibt.

Wir stellen das LGS als Tableau dar:

x1 x2 x3 x4 x5 x6 b 1 2 3 4 5 6 50 1 0 1 0 1 0 10 1 0 0 1 0 0 10 1 1 2 2 3 3 30

Bringt man das Tableau auf „Dreiecksgestalt“, erhält man

x1 x2 x3 x4 x5 x6 b 1 2 3 4 5 6 xxx 0 2 2 4 4 6 xxx 0 0 1 -1 1 0 xxx 0 0 0 0 0 0 0

wobei die rechte Spalte im Moment nicht kümmert. Man sieht aber, dass die letzte Zeile Null wird. Es sind also nur noch drei Gleichungen mit eigenständiger Information übrig. Die vierte Zeile ist von den anderen Zeilen linear abhängig.

Nun soll das Tableau durch vollständige Elimination wieder so weit wie möglich auf „Diagonalgestalt“ gebracht werden. Wir erhalten dann

x1 x2 x3 x4 x5 x6 b 1 0 0 1 0 0 10 0 1 0 3 1 3 20 0 0 1 -1 1 0 0 0 0 0 0 0 0 0

Als Gleichungssystem bedeutet das

1x1 + x4 = 10 1x2 + 3x4 + 1x5 + 3x6 =10 1x3 - 1x4 + 1x5 = 20

Auch hier sind mehr Variablen als Gleichungen vorhanden. Und man kann lediglich eine Variable durch andere Variablen ausdrücken, etwa die Basislösung

x1 = 10 - x4 x2 =20 - 3x4 - x5 - 3x6 x3 = x4 - x5.

Auch hier können x4, x5 und x6 beliebig festgelegt werden. x1, x2 und x3 können dann damit bestimmt werden. Eine spezielle Basislösung ergibt sich, wenn x4, x5 und x6 gleich Null gesetzt werden. Dann erhält man die Basislösung x1 = 10, x2 = 20 und x3 = 0.

Interessiert man sich aber für x5 statt x3 in der Basislösung, muss man das Gleichungssystem mit Hilfe der elementaren Zeilentransformationen so umformen, dass sich nun bei Variable x5 die Spalte 0, 0, 1 ergibt. Dazu sortieren wir zunächst die Spalten so um, dass x5 den Platz von x3 annimmt, was kein Problem ist, wenn man nicht vergisst, mit welcher Variablen man es zu tun hat.

x1 x2 x5 x4 x3 x6 b 1 0 0 1 0 0 10 0 1 1 3 0 3 20 0 0 1 -1 1 0 0 0 0 0 0 0 0 0

Nun wird das LGS wieder so umgeformt, dass links wieder die Basislösung steht. Es ergibt sich

x1 x2 x5 x4 x3 x6 b 1 0 0 1 0 0 10 0 1 0 4 -1 3 20 0 0 1 -1 1 0 0 0 0 0 0 0 0 0

Dass die Spalte b gleich geblieben ist, ist Zufall. Die Basislösung ist nun

x1 = 10 - x4 x2 = 20 - 4x4 + x3 - 3x6 x5 = x4 – x3.

Die spezielle Basislösung ergibt sich, wenn x3, x4 und x6 gleich Null gesetzt werden. Dann erhält man die Basislösung x1 = 10, x2 = 20 und x5 = 0.