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 der Produktionsplanung, Kostenrechnung oder in Stoffstromanalysen. Häufig werden lineare Gleichungssysteme mithilfe von Matrizen dargestellt und algorithmisch gelöst.

Definition

Ein lineares Gleichungssystem mit [math]\displaystyle{ m }[/math] Gleichungen und [math]\displaystyle{ n }[/math] Unbekannten hat die allgemeine 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 den Koeffizienten [math]\displaystyle{ a_{ij} \in \mathbb{R} }[/math] und den Werten der rechten Seite [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 (rechte Seite) ist.

Koppelt man die Matrix [math]\displaystyle{ A }[/math] mit dem Vektor [math]\displaystyle{ b }[/math], erhält man die erweiterte Koeffizientenmatrix [math]\displaystyle{ (A|b) }[/math]. Diese wird in der Regel mit dem Gaußschen Eliminationsverfahren umgeformt, um die Lösung des Systems zu ermitteln.

Homogene und inhomogene lineare Gleichungssysteme

• Ein homogenes lineares Gleichungssystem liegt vor, wenn [math]\displaystyle{ b = 0 }[/math] gilt (der Vektor der rechten Seite besteht nur aus Nullen), also [math]\displaystyle{ A \cdot x = 0 }[/math]. Es besitzt immer mindestens die triviale Lösung [math]\displaystyle{ x = 0 }[/math] (alle Unbekannten sind Null).
• Ein inhomogenes lineares Gleichungssystem liegt vor, wenn [math]\displaystyle{ b \neq 0 }[/math] gilt (mindestens ein Wert auf der rechten Seite ist ungleich Null). Es kann keine, genau eine oder unendlich viele Lösungen besitzen.

Lösungskriterien (Satz von Kronecker-Capelli)

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] ab:

• Das System ist generell lösbar, wenn gilt: [math]\displaystyle{ \operatorname{rang}(A) = \operatorname{rang}(A|b) }[/math].
• Die Lösung ist eindeutig, wenn zusätzlich gilt: [math]\displaystyle{ \operatorname{rang}(A) = n }[/math] (wobei [math]\displaystyle{ n }[/math] die Anzahl der Unbekannten ist).
• Es gibt unendlich viele Lösungen, wenn gilt: [math]\displaystyle{ \operatorname{rang}(A) = \operatorname{rang}(A|b) < n }[/math]. In diesem Fall werden die Lösungen häufig in Abhängigkeit von einem oder mehreren Parametern angegeben.
• Es gibt keine Lösung, wenn gilt: [math]\displaystyle{ \operatorname{rang}(A) \neq \operatorname{rang}(A|b) }[/math] (meist bedeutet dies [math]\displaystyle{ \operatorname{rang}(A) < \operatorname{rang}(A|b) }[/math]).

Zeilenstufenform

In der Zeilenstufenform verringert sich in jeder Zeile der Matrix die Anzahl der Unbekannten um mindestens eine (Stufenbildung). Unterhalb der Stufen (führende Koeffizienten bzw. Pivotelemente) stehen ausschließlich Nullen. Die erweiterte Koeffizientenmatrix kann mithilfe des Gaußschen Eliminationsverfahrens in diese Form gebracht werden.

Sind darüber hinaus alle Pivotelemente auf den Wert 1 normiert und stellen sie in ihrer jeweiligen Spalte den einzigen von Null verschiedenen Eintrag dar, spricht man von der reduzierten Zeilenstufenform. Hierfür verwendet man den erweiterten Gauß-Jordan-Algorithmus.

Betriebswirtschaftliche Anwendungen

In der Betriebswirtschaft werden lineare Gleichungssysteme unter anderem verwendet zur:

• Produktions- und Kapazitätsplanung (z. B. optimale Ressourcenauslastung),
• innerbetrieblichen Kosten- und Erlösrechnung (z. B. Verteilung von Gemeinkosten),
• Analyse von Stoff- und Warenströmen (Gozintograph),
• Modellierung von Stücklisten und mehrstufigen 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 zweite Gleichung lediglich ein Vielfaches (das 2-fache) der ersten Gleichung ist. Die Gleichungen sind linear abhängig.

Inhomogenes lineares Gleichungssystem

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

Die eindeutige Lösung dieses Systems lautet [math]\displaystyle{ x_1 = 2 }[/math] und [math]\displaystyle{ x_2 = 1 }[/math]. Geometrisch entspricht dies dem Schnittpunkt zweier Geraden im zweidimensionalen Raum.

Betriebswirtschaftliches Beispiel (Kapazitätsplanung)

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 exakt 50 Einheiten gefertigt werden (unabhängig davon, wie sie sich auf Produkt 1 und 2 aufteilen).

Das entsprechende LGS lautet:

[math]\displaystyle{ \begin{aligned} 1x_1 + 1x_2 &= 50 \quad \text{(Mengenrestriktion)} \\ 2x_1 + 3x_2 &= 120 \quad \text{(Kapazitätsrestriktion)} \end{aligned} }[/math]

Das Lösen dieses Systems liefert das Ergebnis [math]\displaystyle{ x_1 = 30 }[/math] und [math]\displaystyle{ x_2 = 20 }[/math]. Antwort: Es können exakt 30 Einheiten von Produkt 1 und 20 Einheiten von Produkt 2 gefertigt werden, um die Maschinenkapazität vollständig auszulasten.