Management Science: Lineare Gleichungssysteme

Einführungsbeispiel

Porzellanbeispiel

Eine kleine Porzellanmanufaktur, die hochwertige ausgesuchte Waren produziert, hat neben dem laufenden Angebot noch Kapazität frei. Der Verkaufsleiter vermutet, dass vor allem eine Nachfrage nach Bechern, Tellern und Teekannen besteht. Für die Herstellung müssen die Teile in eine Form gegossen werden. Wenn die Teile genügend angetrocknet sind, werden sie händisch nachbearbeitet. Sodann werden sie zweimal gebrannt. Sie werden von Hand bemalt und dann schließlich noch einmal bei hoher Hitze gebrannt.

Für die händische Nachbearbeitung benötigt man für einen Becher 4 Minuten, für einen Teller 2 Minuten und für eine Kanne 6 Minuten. Im Brennofen brauchen die Becher eine Einheit Platz und die Teller und Kannen je zwei Einheiten. Die Bemalung ist aufwendig und dauert bei Bechern je 20 Minuten, bei Tellern 10 und bei Kannen wieder 20 Minuten.

Es stehen noch insgesamt 10 Stunden Kapazität für die Nachbearbeitung, 240 Stellplatz-Einheiten im Brennofen und 45 freie Stunden des gestalterischen Personals für die Bemalung zur Verfügung.

Die Produktion muss also die Aufgabe lösen, wie viele Teile sie jeweils herstellen soll, damit die obigen Vorgaben erfüllt sind.

Man kann nun diese Vorgaben in ein Gleichungssystem packen. Nennen wir die unbekannte Zahl der zu produzierenden Becher B, die der Teller T und die der Kannen K.

Wir haben also 600 Minuten für die Nachbearbeitung und können nun angeben: 4 Minuten * Zahl der Becher + 2 Minuten * Zahl der Teller + 6 Minuten * Zahl der Kannen soll 600 Minuten ausmachen.

$4\cdot B+2\cdot T+6\cdot K=600$

Ebenso erhalten wir

$1\cdot B+2\cdot T+2\cdot K=240$

und

$20\cdot B+10\cdot T+20\cdot K=2700$.

Es sollen alle drei Gleichungen gleichzeitig erfüllt sein, so dass man strenggenommen schreiben müsste

$(4\cdot B+2\cdot T+6\cdot K=600)$ $\,\land \,$ $(1\cdot B+2\cdot T+2\cdot K=240)$ $\,\land \,$ $20\cdot B+10\cdot T+20\cdot K=2700)$.

Da aber jeder weiß, dass die Gleichungen alle zugleich gelten sollen, schreibt man die Gleichungen des Linearen Gleichungssystems (LGL) einfach untereinander:

${\begin{aligned}&I&&\,4\cdot B+2\cdot T+6\cdot K=600\\&II&&\,1\cdot B+2\cdot T+2\cdot K=240\\&III&&\,20\cdot B+10\cdot T+20\cdot K=2700\end{aligned}}$

Allgemein ausgedrückt betrachten wir ein Gleichungssystem

${\begin{matrix}a_{11}\cdot x_{1}&+\,a_{12}\cdot x_{2}&+\,\ldots &+\,a_{1j}\cdot x_{j}&+\,\ldots &+a_{1n}\cdot x_{n}&=b_{1}\\a_{21}\cdot x_{1}&+\,a_{22}\cdot x_{2}&+\,\ldots &+\,a_{2j}\cdot x_{j}&+\,\ldots &+\,a_{2n}\cdot x_{n}&=b_{2}\\\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\a_{i1}\cdot x_{1}&+\,a_{i2}\cdot x_{2}&+\,\ldots &+\,a_{ij}\cdot x_{j}&+\,\ldots &+\,a_{in}\cdot x_{n}&=b_{i}\\\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\a_{m1}\cdot x_{1}&+\,a_{m2}\cdot x_{2}&+\,\ldots &+\,a_{mj}\cdot x_{j}&+\,\ldots &+\,a_{mn}\cdot x_{n}&=b_{m}\end{matrix}}$

Wir haben es also mit n vielen Unbekannten x_j (j=1, ... n) und m vielen Gleichungen i zu tun. Die Werte a_ij werden als Koeffizienten des Gleichungssystems bezeichnet.

Lösung eines LGS per Hand

Wie löst man nun ein lineares Gleichungssystem? Die meisten der Leser werden so etwas schon einmal gemacht haben. Wir betrachten nun ein Gleichungssystem, hier mal ausnahmsweise ohne konkreten Realitätsbezug.

${\begin{matrix}I&\quad 1\cdot x_{1}&+\,2\cdot x_{2}&+\,3\cdot x_{3}&+\,4\cdot x_{4}&=40\\II&&\quad 5\cdot x_{2}&+\,6\cdot x_{3}&+\,3\cdot x_{4}&=30\\III&&&\quad 4\cdot x_{3}&+\,2\cdot x_{4}&=20\\IV&&&&\quad 5\cdot x_{4}&=10\end{matrix}}$.

Wir können das LGS nun rekursiv von unten nach oben lösen:

$IV\quad 5\cdot x_{4}=10\quad \Rightarrow \quad x_{4}=2$

$III\quad 4\cdot x_{3}+2\cdot 2=20\quad \Rightarrow \quad 4\cdot x_{3}=20-2\cdot 2\quad \Rightarrow \quad x_{3}=4$

$II\quad 5\cdot x_{2}+6\cdot 4+2\cdot 2=30\quad \Rightarrow \quad 5\cdot x_{3}=30-6\cdot 4-2\cdot 2\quad \Rightarrow \quad x_{2}=0$

$I\quad 1\cdot x_{1}+2\cdot 0+3\cdot 4+4\cdot 2=40\quad \Rightarrow \quad x_{1}=40-3\cdot 0-2\cdot 4-3\cdot 2\quad \Rightarrow \quad x_{1}=20$

Dieses System war einfach lösbar. Aber was ist mit unserem Porzellanbeispiel? Ideal wäre es, auch hier wieder die obige Dreiecksgestalt des Gleichungssystems zu erreichen. Mit Hilfe des gaußschen Eliminationsverfahrens gelingt uns das. Dafür verwenden wir elementare Zeilenoperationen, das sind Operationen, die für das LGS äquivalent sind, die also den Inhalt des Gleichungssystem nicht verändern. Es sind dies

• Eine Zeile des Gleichungssystems kann mit einer reellen Zahl a (a ungleich 0) multipliziert werden.
• Ein Zeile des Gleichungssystems kann auf eine andere addiert werden.

Durch gezielte Zeilenoperationen eliminiert man in den Zeilen die Variablen dergestalt, dass man das Gleichungssystem rekursiv lösen kann.

Wir wollen das anhand des Beispiels durchführen:

Um das Gleichungssystem klein zu halten, teilen wir zuerst gegebenenfalls Zeilen so durch eine Konstante, dass gerade noch ganze Zahlen übrig bleiben:

${\begin{aligned}&I&&\,2\cdot B+1\cdot T+3\cdot K=300\\&II&&\,1\cdot B+2\cdot T+2\cdot K=240\\&III&&\,2\cdot B+1\cdot T+2\cdot K=270\end{aligned}}$

Für das bessere Verständnis von Ungeübten machen wir momentan mit der Bezeichnungsweise des Beispiels weiter. Es soll das obige Gleichungssystem in folgende Form überführt werden, wobei das Kästchen für einen beliebigen Wert steht:

${\begin{aligned}&I&&\,2\cdot B+1\cdot T+3\cdot K=300\\&II&&\,0\cdot B+\Box \cdot T+\Box \cdot K=\Box \\&III&&\,0\cdot B+0\cdot T+\Box \cdot K=\Box \end{aligned}}$

Es wird die zweite Zeile mit 2 multipliziert. Dann wird davon die erste Zeile abgezogen:

${\begin{aligned}&II\cdot 2:&&\,2\cdot B+4\cdot T+4\cdot K=480\\&I:&&\,2\cdot B+1\cdot T+3\cdot K=300\\&---------&&\,-----------\\&II_{neu}=II\cdot 2-I:&&\,0\cdot B+3\cdot T+1\cdot K=180\end{aligned}}$

Es wird von der dritten Zeile die erste Zeile subtrahiert:

${\begin{aligned}&III:&&\,2\cdot B+1\cdot T+2\cdot K=270\\&I:&&\,2\cdot B+1\cdot T+3\cdot K=300\\&---------&&\,-----------\\&III_{neu}=III-I:&&\,0\cdot B+0\cdot T-1\cdot K=-30\end{aligned}}$

Jetzt sind die speziellen Koeffizienten des Gleichungssystems gleich Null, wie gewüscht. Wir erhalten das neue Gleichungssystem

${\begin{aligned}&I&&\,2\cdot B+1\cdot T+3\cdot K=300\\&II&&\,0\cdot B+3\cdot T+1\cdot K=180\\&III&&\,0\cdot B+0\cdot T-1\cdot K=-30\end{aligned}}$

und können nun die Variablen von unten nach oben rekursiv ermitteln:

${\begin{aligned}&III:&&\,K=30\\&II:&&\,3\cdot T+1\cdot 30=180\Rightarrow T=50\\&I:&&\,2\cdot B+1\cdot 50+3\cdot 30=300\Rightarrow B=80\end{aligned}}$

Die Vorgaben der Produktion können alle erfüllt werden und es werden nun 80 Becher, 50 Teller und 30 Kannen gefertigt.

Lösung durch Matrizenrechnung

Wir wollen nun das LGS mit Hilfe des Matrizenkalküls etwas näher beleuchten. Die Interpretation als Matrix-Problem hat den Vorteil, dass die Darstellung knapp und aufgeräumt wirkt und dass auch Erkenntnisse der Matrizentheorie die Gesetzmäßigkeit bei LGSs verdeutlichen.

${\begin{aligned}&I&&\,2\cdot B+1\cdot T+3\cdot K=300\\&II&&\,1\cdot B+2\cdot T+2\cdot K=240\\&III&&\,2\cdot B+1\cdot T+2\cdot K=270\end{aligned}}$

Wir definieren die Koeffizientenmatrix

${\underline {A}}={\begin{pmatrix}2&1&3\\1&2&2\\2&1&2\end{pmatrix}}$,

den Vektor der unbekannten Variablen ${\underline {x}}={\begin{pmatrix}B\\T\\K\end{pmatrix}}$ und den Vektor der Beschränkungen ${\underline {b}}={\begin{pmatrix}300\\240\\270\end{pmatrix}}$.

Wir können dann das Gleichungssystem schreiben als

${\underline {A}}\cdot {\underline {x}}={\underline {b}}\,.$

Allgemein können wir die Matrizen so angeben:

Die Koeffizientenmatrix ${\underline {A}}={\begin{pmatrix}a_{11}&a_{12}&\ldots &a_{1j}&\ldots &a_{1n}\\a_{21}&a_{22}&\ldots &a_{2j}&\ldots &a_{2n}\\\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\a_{i1}&a_{i2}&\ldots &a_{ij}&\ldots &a_{in}\\\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\a_{m1}&a_{m2}&\ldots &a_{mj}&\ldots &a_{mn}\\\end{pmatrix}}\,,$

den Vektor der Variablen ${\underline {x}}={\begin{pmatrix}x_{1}\\x_{2}\\\vdots \\x_{j}\\\vdots \\x_{n}\\\end{pmatrix}}$ und der Beschränkungen ${\underline {b}}={\begin{pmatrix}b_{1}\\b_{2}\\\vdots \\b_{i}\\\vdots \\b_{m}\\\end{pmatrix}}\,.$

Nach den Regeln des Matrizenkalküls erhalten wir für den Vektor x die Lösung

${\underline {x}}={\underline {A}}^{-1}\cdot {\underline {b}}\,,$

die allerdings nur existiert, wenn ${\underline {A}}$ invertierbar ist.

Professionell lässt man LGS durch den Computer berechnen. Es gibt hier verschiedene gängige Verfahren. Verwendet man die Gaußsche Elimination, kann man Koeffizientenmatrix und den Restriktionsvektor zu einer Matrix M zusammenfassen. Dann werden die Zeilen dieser Matrix wieder so lange umgeformt, bis die Dreiecksbildung abgeschlossen ist. Formt man das Gleichungssystem weiter um, bis die Lösungen direkt ablesbar sind, was eigentlich beim Computereinsatz effizienter erscheint, spricht man von einem vollständigen Gaußschen Eliminationsverfahren oder dem Verfahren nach Gauß-Jordan. Häufig verwendet wird die LR-Zerlegung, bei der die Matrix A in zwei Dreiecksmatrizen zerlegt wird, was die weitere Bearbeitung dann erheblich vereinfacht.

Wenn kein Computer eingesetzt wird, etwa weil keine geeignete Software zur Verfügung steht oder weil im Unterricht die Verfahrensweise demonstriert werden soll, stellt man die Matrix M zweckmäßigerweise als so genanntes Tableau dar, auf dem man dann die Transformationen der gaußschen Elimination durchführt. Den Restriktionsvektor b kann man zur besseren Übersicht mit einem vertikalen Strich abtrennen.

Für unser Beispiel ergibt sich dann

I   2 1 3 | 300       I       2 1  3 | 300 
II  1 2 2 | 240   →   II-2*I  0 3  1 | 180  
III 2 1 2 | 270       III-I   0 0 -1 | -30

Wir wollen das LGS jetzt mit dem vollständigen Eliminationsverfahren ganz lösen. Dazu formen wir das System so lang um, bis A eine Diagonalmatrix mit lauter Einsen geworden ist. Es werden zuerst in der ersten Zeile die Elemente a₁₂ und a₁₃ auf Null gebracht.

Zwischenrechnungen:

3*I    6 3 9 900    I         6 0  8  720
-II  -(0 3 1 180)   +8*III    0 0 -8 -240
-----------------   ---------------------
Ineu   6 0 8 720    Ineu      6 0  0  480

Neues Tableau:

I   6 0  0 | 480      
II  0 3  1 | 180   
III 0 0 -1 | -30    

Es wird noch a₂₃ auf Null gesetzt:

 II   0 3  1 180     
+III  0 0 -1 -30    
-----------------  
IIneu 0 3  0 150    

Neues Tableau:

I   6 0  0 | 480      
II  0 3  0 | 150   
III 0 0 -1 | -30    
 

Nun werden noch die Kehrwerte der Diagonalelemente von A gebildet und man kann dann die Lösung ablesen.

I   6 0  0 | 480  |:6      I   1 0  0 | 80  
II  0 3  0 | 150  |:3  →   II  0 1  0 | 50
III 0 0 -1 | -30  |:-1     III 0 0  1 | 30  
 

Wandeln wir das Tableau wieder in ein Gleichungssystem um, erhalten wir

${\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}}\cdot {\begin{pmatrix}B\\T\\K\end{pmatrix}}={\begin{pmatrix}80\\50\\30\end{pmatrix}}$,

also

$B=80,\,T=50,\,K=30.$

Navigation

↓ Simplexverfahren

↑ Rang einer Matrix

↑↑ Inhaltsverzeichnis Management Science