Lineares Gleichungssystem: Unterschied zwischen den Versionen

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 [[Matrix|Matrizen]] dargestellt und algorithmisch gelöst.

Ein '''lineares Gleichungssystem''' mit <math>m</math> Gleichungen und <math>n</math> Unbekannten hat die allgemeine Form:

mit den Koeffizienten <math>a_{ij} \in \mathbb{R}</math> und den Werten der rechten Seite <math>b_i \in \mathbb{R}</math>.

Die '''Matrizengleichung''' des Systems lautet:

</math>

wobei <math>A</math> die Koeffizientenmatrix, <math>x</math> der Unbekanntenvektor und <math>b</math> der Ergebnisvektor (rechte Seite) ist.  

 

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

* Ein '''homogenes''' lineares Gleichungssystem liegt vor, wenn <math>b = 0</math> gilt (der Vektor der rechten Seite besteht nur aus Nullen), also <math>A \cdot x = 0</math>. Es besitzt immer mindestens die triviale Lösung <math>x = 0</math> (alle Unbekannten sind Null).

* Ein '''inhomogenes''' lineares Gleichungssystem liegt vor, wenn <math>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 [[Matrix#Rang|Rang]] der Koeffizientenmatrix <math>A \in \mathbb{R}^{m \times n}</math> und der erweiterten Koeffizientenmatrix <math>(A|b)</math> ab:

* Das System ist generell '''lösbar''', wenn gilt: <math>\operatorname{rang}(A) = \operatorname{rang}(A|b)</math>.

* Die Lösung ist '''eindeutig''', wenn zusätzlich gilt: <math>\operatorname{rang}(A) = n</math> (wobei <math>n</math> die Anzahl der Unbekannten ist).

* Es gibt '''unendlich viele Lösungen''', wenn gilt: <math>\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>\operatorname{rang}(A) \neq \operatorname{rang}(A|b)</math> (meist bedeutet dies <math>\operatorname{rang}(A) < \operatorname{rang}(A|b)</math>).

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ßsches_Eliminationsverfahren|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ßsches_Eliminationsverfahren|Gauß-Jordan-Algorithmus]].

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.

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.

Die eindeutige Lösung dieses Systems lautet <math>x_1 = 2</math> und <math>x_2 = 1</math>. Geometrisch entspricht dies dem Schnittpunkt zweier Geraden im zweidimensionalen Raum.

 

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).

1x_1 + 1x_2 &= 50 \quad \text{(Mengenrestriktion)} \\

2x_1 + 3x_2 &= 120 \quad \text{(Kapazitätsrestriktion)}

 

'''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.