In der linearen Optimierung geht es um die optimale Aufteilung knapper Ressourcen auf unterschiedliche Verwendungszwecke. Bei den knappen Ressourcen könnte es sich beispielsweise um Maschinenkapazitäten oder Raumbedarf von Gütern handeln. Das Optimum wird dabei mathematisch, häufig mit Hilfe des Simplexverfahrens, bestimmt.

Modellierung linearer Programme

Bei der Modellierung von linearen Programmen müssen zunächst verschiedene Parameter, wie z. B. Bearbeitungszeiten von Werkstücken oder Maschinenkapazitäten, bestimmt werden. Danach wird eine Zielfunktion definiert, die unter bestimmten Nebenbedingungen maximiert werden soll. Bei der Zielfunktion handelt es sich häufig um die Gewinnfunktion, da die Maximierung des Nettogewinns für Unternehmen ein zentrales Ziel darstellt. Die Nebenbedingungen werden durch die Knappheit von Ressourcen beschrieben (z. B. Kapazität, Zeit, Raum). Danach können Sie die Problemstellung mithilfe des Simplexverfahrens lösen.

Besonders einfach erlernen Sie die Vorgehensweise zur Erstellung linearer Modelle, wenn Sie sich ein einfaches Beispiel machen: Angenommen Sie haben drei Maschinen M1, M2 und M3 auf denen die zwei Produkte P1 und P2 hergestellt werden sollen. Die Maschinen haben unterschiedliche Kapazitäten, außerdem dauert die Bearbeitung eines bestimmten Produktes auf den Maschinen unterschiedlich lang und die fertigen Endprodukte werfen einen unterschiedlich hohen Gewinn ab.
Gesucht ist nun das gewinnmaximale Produktionsprogramm, also das Produktionsprogramm, bei dem der größte Gewinn erzielt wird.

Beispiel mit Zahlenwerten und Hinführung zum Simplexverfahren

Im nächsten Schritt benötigen Sie für die Modellierung Ihres Problems konkrete Zahlenwerte. Nehmen Sie an, dass für die Bearbeitung von P1 auf M1 2 Stunden anfallen, auf M2 3 Stunden und auf M3 4 Stunden. Für P2 fallen auf M1 4 Stunden an, auf M2 5 Stunden und auf M3 3 Stunden. Die Maschinenkapazitäten betragen für M1 500 Stunden, für M2 300 Stunden und für M3 600 Stunden. Die Gewinne für die fertigen Endprodukte P1 betragen 3 Euro/Stück, für die fertigen Endprodukte P2 4 Euro/Stück.

1. Am besten legen Sie sich eine Tabelle mit drei Zeilen und drei Spalten an, wobei Sie zusätzlich Platz für die Überschriften der Zeilen bzw. Spalten lassen sollten. Im Feld "Spalte 1 und Zeile 1" steht beispielsweise die Bearbeitungszeit von P1 auf M1, im Feld "Spalte 2 und Zeile 3" die Bearbeitungszeit von P2 auf M3. In Spalte 3 stehen die Maschinenkapazitäten der drei Maschinen.
2. Nun müssen Sie zwei Variablen x1, x2 definieren, die den Fertigungsmengen von P1 und P2 entsprechen.
3. Sie erhalten also die Nebenbedingungen 2x1+4x2 ? 500 (Maschine 1), 3x1+5x2 ? 300 (Maschine 2) und 4x1+3x2 ? 600 (Maschine 3). Es handelt sich jeweils um Ungleichungen, da die Kapazitäten nicht voll ausgeschöpft werden müssen.
4. Die zu maximierende Zielfunktion (Gewinn) lautet G(x1, x2) = 3x1+4x2 -> max.
5. Außerdem gelten für die Produktionsmenge die Nichtnegativitätsbedingungen von x1, x2 ? 0. Sie sehen, alle Gleichungen sind lineare Gleichungen. Betrachten Sie diese zusammen, so erhalten Sie ein lineares Optimierungsproblem.

Lineare Optimierung und Anwendung des Simplexverfahrens

Die Idee zur Lösung eines linearen Programms besteht darin, dass die Ungleichungen durch Einführung von "Schlupfvariablen" in Gleichungen umgewandelt werden und das modifizierte Optimierungsproblem als LGS gelöst wird. Das Simplexverfahren ist also dem Gauß-Algorithmus zum Lösen von LGS sehr ähnlich.

1. Beispiel: Ein Flugzeug ist durch drei Güter G1, G2, G3 mit einem möglichst hohen Gesamtfrachtwert zu beladen. Diese haben einen Platzbedarf von 1, 0,2 bzw. 6 dm3, haben ein Gewicht von 1, 0, 4 bzw. 8 Kg und einen Wert von 10, 3 bzw. 50 Euro. Wie ist das Flugzeug ideal zu beladen, wenn der Frachtraum 2000dm3 beträgt und es maximal 3000 Kg Fracht befördern kann?
2. Sie definieren x1, x2, x3 als Mengen der Güter G1, G2, G3.
3. Nun können Sie die Nebenbedingungen mit Schlupfvariablen wie folgt aufstellen: x1+0,4x2+8x3+x4 = 3000 und x1+0,2x2+6x3+x5 = 2000. Die Zielfunktion (Gesamtfrachtwert) lautet G(x1, x2, x3) = 10x1+3x2+50x3 -> max. Diese stellen Sie noch um, indem Sie alle Variablen auf eine Seite bringen (G-10x1-3x2-50x3 = 0).
4. Anschließend stellen Sie das Simplex-Tableau auf. Es hat 3 Zeilen und 7 Spalten. Auf der linken Seite tragen Sie in den Spalten x1, x2, x3, x4, x5 und G als Überschriften ab. Auf der rechten Seite ist b die einzige Spalte. Hier stehen nachher die optimalen Mengen der Güter und der höchstmögliche Gesamtfrachtwert. Die dritte Zeile ist die Zielzeile. (Kontrolle: in den drei Zeilen mit den oben genannten Überschriften stehen also die Zahlen: Zeile 1: 1, 0.4, 8, 1, 0, 0, 3000, Zeile 2: 1, 0.2 6, 0, 1, 0, 2000 und Zeile 3: -10, -3, -50, 0, 0, 1, 0).
5. Nun gehen Sie wie bei der Anwendung des Gauß-Verfahrens zur Lösung eines LGS vor. Durch Zeilenumformungen ändern Sie im ersten Schritt Zeile 1 bzw. Zeile 2 geschickt so um und addieren diese zur anderen Zeile, dass nur noch eine 1 in "Zeile 1 + Spalte 1" und eine 0 in "Zeile 2 + Spalte 1" auftritt. Dadurch ändern sich auch die Werte in der Zielzeile automatisch.
6. In diesem Fall könnten Sie beispielsweise Zeile 2 mit -1 multiplizieren und zu Zeile 1 hinzuaddieren und Zeile 2 mit 10 multiplizieren und zu Zeile 3 hinzuaddieren (Kontrolle: Zeile 1: 0, 0.2, 2, 1, -1, 0, 1000, Zeile 2: bleibt gleich, Zeile 3: 0, -1, 10, 0, 10, 1, 20.000).
7. Im zweiten Schritt nehmen Sie sich Spalte 2 vor und erschaffen durch Umformung in "Zeile 2 + Spalte 2" eine 0 und anschließend in "Zeile 1 und Spalte 2" eine 1. Dabei ist wiederum zu beachten wie sich die Zielzeile ändert.
8. Die Umformungsschritte wären beispielsweise Zeile 1 mit -1 zu multiplizieren und zu Zeile 2 zu addieren und Zeile 1 mit 5 zu multiplizieren und zu Zeile 3 zu addieren (Kontrolle: nach Durchführung beider Schritte ergeben sich: Zeile 1: 0, 1, 10, 5, -5, 0, 5000, Zeile 2: 1, 0, 4, -1, 2, 0, 1000 und Zeile 3: 0, 0, 20, 5, 5, 1, 25.000).
9. Auf der rechten Seite des Tableaus können Sie nun die Lösungen ablesen. Es ergibt sich ein Gesamtfrachtwert von 25.000 Euro, es werden 5000 Einheiten von Gut 1 transportiert, 1000 Einheiten von Gut 2 und keine Einheit von Gut 3.

Beachten Sie, dass sich bei der Lösung des Simplex-Tableaus nur eine optimale Lösung ergibt, wenn in der Zielzeile auf der linken Seite nach dem letzten Umformungsschritt ausschließlich positive Zahlen stehen. Das System haben Sie nach 2-3 weiteren Beispielen verinnerlicht und können solche Aufgabenstellungen auch in Zukunft spielerisch lösen.

Gruß raffisworld