Benutzerin:Gabriele Hornsteiner/LGS

Lineare Optimierung Lineare Optimierung oder auch lineare Programmierung bedeutet, dass eine Zielfunktion optimiert wird, die von einem System linearer Gleichungen bzw. Ungleichungen abhängt.

Lineare Gleichungssysteme

Dieser Abschnitt ist als Hinführung zum Simplexverfahren eine kurze Einführung bzw. Wiederholung der linearen Gleichungssysteme.

Lösung linearer Gleichungssysteme

Ein Gleichungssystem ist eine Folge von Gleichungen, die zugleich erfüllt sein müssen. Beispiel:

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikibooks.org/v1/“:): {\displaystyle 5x+√y-e^x=xy} x^2+y^2=1000

Solche Gleichungssysteme sind i.a. schwer zu lösen. Häufig können nur Näherungsverfahren angewendet werden. Einfacher sind lineare Systeme.

Allgemeines Beispiel:

a_1 x+ b_1 y+c_1 z= d_1; a_2 x + b_2 y +c_2 z = d_2; a_3 x + b_3 y +c_3 z = d_3.

Auch hier müssen die Gleichungen zusammen erfüllt sein. Gaußscher Algorithmus

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

Wie löst man ein LGS?

3x + 2y – z = 13; 2x – y + 3z = -1; 5x – 4y + 4 z = 3.

Man bringt die linke Seite „auf Dreiecksgestalt“ und löst dann rekursiv. 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:

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

Die 1. Spalte soll sein:

2. Zeile:

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

___________________________________________________________

3. Zeile:

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

___________________________________________________________

 

Neues Tableau als Zwischenergebnis:

Die 2. Spalte soll sein:

3. Zeile:

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 erhält die Lösungen

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:

Lösbarkeit von Gleichungssystemen

Eindeutige Lösbarkeit:

Porzellan-Beispiel I:

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 ⋅ B+2 ⋅ T+6 ⋅ K = 600 

Ebenso erhalten wir

1 ⋅ B+2 ⋅ T+2 ⋅ K = 240 

und

20 ⋅B+10 ⋅T+20 ⋅K = 2700 .

Als Lineares Gleichungssystem (LGL) ergibt sich also

4 ⋅B+2 ⋅T+6 ⋅K = 600

1 ⋅B+2 ⋅T+2 ⋅K = 240   

20 ⋅B+10 ⋅T+20 ⋅K = 2700

Wir haben drei Gleichungen und drei Unbekannte.

Um das Gleichungssystem klein zu halten, kürzen wir:

2 ⋅B+1 ⋅T+3 ⋅K = 300 

1 ⋅B+2 ⋅T+2 ⋅K = 240

2 ⋅B+1 ⋅T+2 ⋅K = 270

 

Wir erhalten das unten folgende Tableau und lösen es mit Hilfe der vollständigen Elimination:

B T K b

1. Spalte soll sein:

1. Zeile: 

Zeile:

___________________________________________________________

3. Zeile:

___________________________________________________________

  Neues Tableau als Zwischenergebnis:

Die 2. Spalte soll sein:

2. Zeile:

Zeile:

___________________________________________________________

3. Zeile:

___________________________________________________________

Neues Tableau als Zwischenergebnis:

  Die 3. Spalte soll sein:

3. Zeile:

Zeile:

___________________________________________________________

2. Zeile:

___________________________________________________________

Neues Tableau als Endergebnis:

Das entspricht dem ausführlichen Gleichungssystem

  mit den Lösungen

Wir haben hier eine eindeutige Lösbarkeit des Gleichungssystems.

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

Wir haben hier eine eindeutige Lösbarkeit des Gleichungssystems.

Mehrdeutige Lösbarkeit – zu wenig aussagefähige Gleichungen

Beispiel:

Ein Betrieb stellt Teemischungen her. Es sind noch Kapazitäten frei. Man überlegt, die Tees Winterfeuer, Herbstglut und Balance herzustellen. Nachfolgend sind die knappen Zutaten pro Packung Tee angegeben (Einheit 100 g).

Produkt Winterfeuer Herbstglut Balance Vorrätige Zutaten Menge W H B Hibiskus 1 1 1 30 Johannisbeerblätter 1 2 1 40 Früchte 2 3 2 70

Wir erhalten das Gleichungssystem

das nun gelöst werden soll.   Tableau:

W H B b

1. Spalte soll sein:

Zeile:

Zeile:

___________________________________________________________

3. Zeile:

___________________________________________________________

  Neues Tableau als Zwischenergebnis:

Die 2. Spalte soll sein:

2. Zeile:

Zeile:

___________________________________________________________

3. Zeile:

___________________________________________________________

 

Neues Tableau:

Das entspricht dem ausführlichen Gleichungssystem

W kann beliebig festgelegt werden, B errechnet sich damit, z.B.

Spezielle Basislösung: W = 0:

 

Betrachten wir nun ein weiteres lineares Gleichungssystem:

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

Wir fassen die Daten in einem Tableau zusammen:

x1 x2 x3 x4 x5 x6 b

Nun versuchen wir wieder, mit dem vollständigen Eliminationsverfahren eine direkte Lösung für die Variablen zu erhalten. Es ergibt sich die kanonische Form

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

Wir nennen eine Variable, die in ihrer Spalte bis auf eine Eins lauter Nullen enthält, eine Basisvariable. (In der Matrizentheorie wird diese Spalte iter Einheitsvektor genannt, wobei i die Zeile mit der Eins ist.)  

Wir wollen nun, analog zu oben, mit Hilfe des Tableaus die Lösungen der Basisvariablen direkt ablesen:

Man sieht, dass die Variablen x4, x5 und x6 frei variierbar sind. Je nachdem, welche Werte sie annehmen, errechnen sich die Werte von x1 bis x3. Eine spezielle Basislösung ergibt sich, wenn man die Variablen x4, x5 und x6 Null setzt. Dann erhalten wir die Lösungen

Wir könnten nun andere Variablen zu Basisvariablen erklären und dann wieder die neue kanonische Form ermitteln. Wir ersetzen beispielsweise die Basisvariable x3 durch eine neue Basisvariable x5. Dazu sortieren wir zunächst die Variablen um, was kein Problem ist, wenn man nicht vergisst, was sie bedeuten.

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

Wir formen nun das Tableau so um, dass links wieder die Basisvariablen stehen.

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 hier unverändert ist, ist nur Zufall. Wir wollen nun wieder die Lösungen direkt ablesen:

Eine spezielle Basislösung ergibt sich, wenn man die Variablen x4, x3 und x6 Null setzt. Dann erhalten wir die Lösungen