L3 Verallgemeinerung von Linearen Optimierungsproblemen und Lösung
Simplexalgorithmus 1. Phase: Herstellen zulässiger Lösung mit M-Methode
Um auf eine zulässige Lösung zu kommen, gibt es zwei Ansätze. Im Folgenden wird die M-Methode beschrieben. Alternativ dazu kann die hier nicht näher erläuterte Duale Simplexmethode verwendet werden. Beide führen zum Ziel.
Eintragung in das Tableau
Das begleitende Beispiel komplett in das Tableau eingetragen sieht wie folgt aus:
Das Ziel der 1. Phase ist, die künstlichen Variablen x‘3 und x‘4 die derzeit Basisvariablen sind auf null zu setzen und zu eliminieren. Ein algorithmisch gradliniger Weg ist, daraus ein neues Optimierungsproblem zu machen.
Aufgabe: Minimiere die Summe der künstlichen Variablen! Wenn alle künstlichen Variablen null sind, ist auch die Summe null und das Ziel erreicht.
Dazu wird für die 1. Phase eine zweite Zielfunktion aufgestellt, die lautet
min z= x‘3+x‘4
bzw.
max -z= -x‘3-x‘4
Ganz naiv in das Tableau eingetragen, würde sich Folgendes ergeben:
Versuchstableau
Das Tableau enthält keine Basislösung mehr! In den Spalten der künstlichen Variablen, in denen eigentlich nur Einheitsvektoren stehen dürfen, steht nun in der Zielfunktion eine weitere Eins. Das Problem lässt sich beheben.
Zu diesem Zweck werden die betroffenen Zeilen von der zweiten Zielfunktion subtrahiert.
Tableau 1
Nun ist das Tableau in einer Form, mit der gerechnet werden kann. Gelegentlich wird hinter die Werte in der 2. Zielfunktion auch noch ein M geschrieben. Dabei steht M für eine große Zahl und soll verdeutlichen, dass der 2. Zielfunktion in der 1.Phase eine überragende Bedeutung zukommt. Daraus leitet sich der Name M-Methode ab.
Besonderheit in der nachfolgenden Rechnung ist, dass die ursprüngliche Zielfunktion mit umgerechnet wird, aber ansonsten keinen Einfluss hat. Ihre Koeffizienten spielen keine Rolle und sie kann auch nicht Pivotzeile werden.
Durchführen der 1. Phase
Tableau 2
Der Zielwert der 2. Zielfunktion ist gestiegen. Allerdings hat sich der Zielwert der ursprünglichen Zielfunktion leider verschlechtert. Aber das spielt keine Rolle, da es in der 1. Phase einzig und allein darum geht, die Zulässigkeit herzustellen.
Die Variable x‘3 hat die Basis verlassen. Sie wird sofort gestrichen, um Arbeit zu sparen, und vor allem um sicherzustellen, dass sie nicht wieder in die Basis gelangt.
Da in der 2. Zielfunktion weiterhin negative Koeffizienten zu finden sind, geht die Rechnung weiter.
Tableau 3
Im 3. Tableau ist der Zielwert der 2. Zielfunktion null. Es gibt keine negativen Koeffizienten mehr in der 2. Zielzeile und alle künstlichen Variablen wurden aus der Basis entfernt.
Die Zulässigkeit ist hergestellt und die 1. Phase erfolgreich abgeschlossen. Die 2. Zielzeile sowie die Spalte der Variable x‘4 werden noch gelöscht und die 2. Phase beginnt.
Im 3. Tableau ist der Zielwert der 2. Zielfunktion null. Es gibt keine negativen Koeffizienten mehr in der 2. Zielzeile und alle künstlichen Variablen wurden aus der Basis entfernt.
Die Zulässigkeit ist hergestellt und die 1. Phase erfolgreich abgeschlossen. Die 2. Zielzeile sowie die Spalte der Variable x‘4 werden noch gelöscht und die 2. Phase beginnt.
Anschließendes Durchführen der 2. Phase
Tableau 4
Tableau 4
Nach einer Iteration ist das Optimum erreicht.
Lösung:
Das Minimum ist z=460 (Vorsicht, im Tableau ist –z eingetragen!)
x1=55, x2=15, x3=100, x5=0
