Lineares Gleichungssystem

Ein lineares Gleichungssystem (LGS) ist eine Menge von linearen Gleichungen mit mehreren Unbekannten. Lineare Gleichungssysteme treten in vielen mathematischen und insbesondere betriebswirtschaftlichen Fragestellungen auf, z.B. bei Produktionsplanung, Kostenrechnung oder Stoffstromanalysen. Häufig werden lineare Gleichungssysteme mithilfe von Matrizen dargestellt und gelöst.

Definition

Ein lineares Gleichungssystem mit [math]\displaystyle{ m }[/math] Gleichungen und [math]\displaystyle{ n }[/math] Unbekannten hat die Form

[math]\displaystyle{ \begin{aligned} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n &= b_1 \\ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n &= b_2 \\ \vdots \qquad & \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n &= b_m \end{aligned} }[/math]

mit Koeffizienten [math]\displaystyle{ a_{ij} \in \mathbb{R} }[/math] und rechten Seiten [math]\displaystyle{ b_i \in \mathbb{R} }[/math].

Die Matrizengleichung des Systems lautet

[math]\displaystyle{ A \cdot x = b }[/math],

wobei [math]\displaystyle{ A }[/math] die Koeffizientenmatrix, [math]\displaystyle{ x }[/math] der Unbekanntenvektor und [math]\displaystyle{ b }[/math] der Ergebnisvektor ist. Die erweiterte Koeffizientenmatrix lautet [math]\displaystyle{ (A|b) }[/math] und wird in der Regel mit dem Gauß'schen Eliminationsverfahren in Zeilenstufenform gebracht, zum die Lösung zu ermitteln.

Homogene und inhomogene lineare Gleichungssysteme

• Ein homogenes lineares Gleichungssystem liegt vor, wenn [math]\displaystyle{ b = 0 }[/math] gilt, also [math]\displaystyle{ A \cdot x = 0 }[/math]. Es besitzt immer mindestens die triviale Lösung [math]\displaystyle{ x = 0 }[/math].
• Ein inhomogenes lineares Gleichungssystem liegt vor, wenn [math]\displaystyle{ b \neq 0 }[/math] gilt. Es kann keine, genau eine oder unendlich viele Lösungen besitzen.

Lösungskriterien

Die Lösbarkeit eines linearen Gleichungssystems hängt vom Rang der Koeffizientenmatrix [math]\displaystyle{ A \in \mathbb{R}^{m \times n} }[/math] und der erweiterten Koeffizientenmatrix [math]\displaystyle{ (A|b) }[/math] mit [math]\displaystyle{ b \in \mathbb{R}^{m} }[/math] ab:

• Das System ist lösbar, wenn [math]\displaystyle{ \operatorname{rang}(A) = \operatorname{rang}(A|b) }[/math].
• Die Lösung ist eindeutig, wenn zusätzlich [math]\displaystyle{ \operatorname{rang}(A) = n }[/math] gilt.
• Es gibt unendlich viele Lösungen, wenn [math]\displaystyle{ \operatorname{rang}(A) = \operatorname{rang}(A|b) \lt n }[/math].
• Es gibt keine Lösung, wenn [math]\displaystyle{ \operatorname{rang}(A) \neq \operatorname{rang}(A|b) }[/math].

Bei unendlich vielen Lösungen werden diese häufig mithilfe von Parametern dargestellt.

Zeilenstufenform

In der Zeilenstufenform verringert sich in jeder Zeile die Anzahl der Unbekannten um mindestens eine, die dann auch in den darauffolgenden Zeilen nicht mehr vorkommt. Die erweiterte Koeffizientenmatrix kann mit Hilfe des Gauß'schen Eliminationsverfahrens in Zeilenstufenform gebracht werden. Enthält jede Zeile genau eine Unbekannte, so spricht man von reduzierter Zeilenstufenform. Hierfür verwendet man den Gauß-Jordan-Algorithmus.

Betriebswirtschaftliche Anwendungen

In der Betriebswirtschaft werden lineare Gleichungssysteme unter anderem verwendet zur

• Produktions- und Kapazitätsplanung,
• Kosten- und Erlösrechnung,
• Analyse von Stoff- und Warenströmen,
• Modellierung von Stücklisten und Produktionsprozessen.

Beispiele

Homogenes lineares Gleichungssystem

[math]\displaystyle{ \begin{aligned} x_1 + 2x_2 - x_3 &= 0 \\ 2x_1 + 4x_2 - 2x_3 &= 0 \end{aligned} }[/math]

Dieses System besitzt unendlich viele Lösungen, da die Gleichungen linear abhängig sind.

Inhomogenes lineares Gleichungssystem

[math]\displaystyle{ \begin{aligned} 2x_1 + x_2 &= 5 \\ x_1 - x_2 &= 1 \end{aligned} }[/math]

Die eindeutige Lösung lautet [math]\displaystyle{ x_1 = 2 }[/math], [math]\displaystyle{ x_2 = 1 }[/math].

Betriebswirtschaftliches Beispiel

Ein Unternehmen produziert zwei Produkte. Für Produkt 1 werden 2 Maschinenstunden, für Produkt 2 werden 3 Maschinenstunden benötigt. Insgesamt stehen 120 Maschinenstunden zur Verfügung. Zusätzlich sollen insgesamt 50 Produkte hergestellt werden.

[math]\displaystyle{ \begin{aligned} x_1 + x_2 &= 50 \\ 2x_1 + 3x_2 &= 120 \end{aligned} }[/math]

Die Lösung gibt an, wie viele Einheiten der beiden Produkte gefertigt werden können.