L2 Lösen von Linearen Optimierungsproblemen
Die erste Iteration
Die erste Iteration
Tableau 1
Tableau 2
Die Umrechnung aller Zeilen einschließlich der Zielzeile läuft wie bei einem Basistausch üblich.
Umrechnen der Pivotzeile
Zunächst wird die Pivotzeile so normiert, dass das Pivotelement 1 ist. Dazu werden die Elemente in der Pivotzeile r in allen Spalten durch das Pivotelement ars geteilt. Auch die rechte Seite wird durch das Pivotelement geteilt.
Mathematisch ausgedrückt:
umgerechnete Element
Hinweise zur Notation:
|
Die geschwungene Linie, genannt Tilde, über dem Buchstaben kennzeichnet, dass es sich um das umgerechnete Element handelt. Das heißt das Element gehört in das neue Tableau. |
|
Das Zeichen ist eine Abkürzung, es bedeutet „für alle“. Vor dem Zeichen steht eine Rechenanweisung, die „für alle“ Elemente der nachfolgend angegebenen Menge durchzuführen ist. In vorliegendem Beispiel handelt es sich um die Menge aller Spalten. |
Umrechnen aller übrigen Elemente
Anschließen wird ein Vielfaches der Pivotzeile so zu den anderen Zeilen addiert, dass in der Pivotspalte ein Einheitsvektor entsteht. Das Vorgehen ist dem beim Gaußalgorithmus sehr ähnlich. Das bedeutet, alle Elemente in der Pivotspalte außer dem Pivotelement müssen null werden.
Mathematisch ausgedrückt liest sich das Ganze wie folgt:
| \ | Bedeutet „ohne“. Vorstehende Rechenanweisung ist also nicht auf die Zeile r anzuwenden, schließlich wurde diese ja zuvor schon nach einer anderen Rechenanweisung umgerechet. |
| zo | Damit ist die rechte Seite der Zielzeile gemeint. |
Praktische Tipps zur Umrechnung
Die mathematische vollständige Darstellung der Rechenregel mag etwas kompliziert wirken. Aber keine Sorge! Wie auch beim Gaußalgorithmus (vgl. Hinweise) ist es ein beliebter Trick, sich die Lage der an der Umrechnung beteiligten Elemente im Tableau zu verdeutlichen. Diese haben die Form eines „Z“. So kann Element für Element umgerechnet werden.
Da in der Pivotspalte außer dem Pivotelement alle Eintragungen null sein müssen, kann diese Spalte sehr schnell ausgefüllt werden. Das Ausrechnen nach obiger Regel ist auch möglich, wenn kein Rechenfehler vorliegt ist das Ergebnis aber immer null.
Die Spalten deren Elemente in der Pivotzeile null sind, ändern sich nicht und können ebenfalls schnell übertragen werden.
Inhaltliche Interpretation:
Das Produktionsprogramm nach der 1. Iteration sieht die Herstellung von 80 kg Superfruchtmüsli vor. Das Trockenobst ist in diesem Fall aufgebraucht. Es sind noch 16 kg Haferflocken und 7 kg Nüsse übrig. Aber, bitte an dieser Stelle noch nicht anfangen zu mischen, sondern erst den Algorithmus zu Ende bringen!
Denn durch die Herstellung von Standardmüsli können noch 2 € pro kg verdient werden. Der Wert ist geringer, da das Trockenobst gedanklich aufgebraucht ist. Soll auch Standardmüsli hergestellt werden, kann nur weniger Superfruchtmüsli hergestellt werden. Damit Trockenobst für 1 kg Standardmüsli zur Verfügung steht, muss die Menge Superfruchtmüsli um 1/2 kg gesenkt werden. Um 6 € mit Standardmüsli zu verdienen, muss auf 8 €/2=4 € Erlös aus Superfruchtmüsli verzichtet werden. Unter dem Strich können also 2 € zusätzlich verdient werden.
