L3 Verallgemeinerung von Linearen Optimierungsproblemen und Lösung
Bisher wurde ein vereinfachter Fall mit Kleiner-gleich-Nebenbedingungen betrachtet, bei dem automatisch eine zulässige Lösung vorliegt. Im allgemeinen Fall ist das nicht gewährleistet, dann muss zunächst eine zulässige Lösung gefunden werden. Das geschieht in der 1. Phase des Simplexalgorithmus. In diesem Kapitel werden verschiedene Verallgemeinerungen besprochen. Begleitend dazu wird folgendes Beispiel verwendet:
| min | z= 4·x1 | +16·x2 | |
| u.d.N. | 4·x1 | ≥120 | |
| 2·x1 | +2·x2 | =140 | |
| 12·x1 | +4·x2 | ≤720 |
Optimierungsrichtung: Minimierung
Bisher wurde der Simplexalgorithmus am Beispiel der Maximierung vorgestellt. Schließlich sind in der Betriebswirtschaftslehre Fragestellungen bei denen es um Gewinn-, Deckungsbeitrags- oder Erlösmaximierung geht sehr weit verbreitet und beliebt.
Mathematisch ist mit demselben Handwerkszeug auch die Minimierung möglich. Inhaltlich wichtig sind Minimierungsprobleme ebenfalls, nur vielleicht sind sie nicht so populär.
Ein typisches Minimierungsproblem ist zum Beispiel, wenn aufgrund von angenommenen Aufträgen schon feststeht, welche Mengen produziert werden müssen und es nur noch darum geht, das Bestellte möglichst kostenminimal zu produzieren.
Die Zielfunktion von Minimierungsproblemen lautet:
min z= c1·x1+ c2·x2+ c3·x3+…+ cn·xn
Ansatz Zielfunktion mit -1 multiplizieren und maximieren
Nun kann man die vorstehende Funktion mit -1 multiplizieren.
max -z= -c1·x1- c2·x2- c3·x3-…- cn·xn
Die Koeffizienten und der Zielwert ändern ihr Vorzeichen. Aus dem min wird max und schon liegt wieder das bekannte Maximierungsproblem vor. Ist das Ergebnis ermittelt, ist lediglich darauf zu achten, dass das Vorzeichen von z wieder zurückgewechselt wird.
Falls das zu schnell ging:
Man stelle sich vor, über mehre Schritte wird z ausgehend von 5 minimiert. Je kleiner der Wert wird, desto besser. Eine Folge über mehrere Schritte könnte lauten: 5;3;2.
Durch Multiplikation mit -1 ändert sich das Vorzeichen von z. Die gleiche Optimierung würde dann wie folgt lauten: -5;-3;-2
D.h. in jedem Schritt wird -z größer.
Die Aufgabe z zu minimieren ist deswegen identisch mit der Aufgabe –z zu maximieren.
Beispiel:
Aus
min z= 4·x1+16·x2
wird
max - z= - 4·x1- 16·x2
Im Tableau eingetragen:
Etwas Konzentration erfordert der doppelte Vorzeichenwechsel. Bei Eintragung in das Tableau wechseln die Koeffizienten erneut das Vorzeichen.
Ansatz Auswahlregel ändern
Alternativ kann man die Zielfunktion unverändert lassen und einfach die Auswahlregeln für die Pivotspalte ändern. Dann muss immer der größte Koeffizient in der Zielzeile gewählt werden und nicht der kleinste. Beendet ist die Rechnung, wenn alle Zielzeilenkoeffizienten negativ oder null sind. Bei einer Handrechnung nachteilig ist an diesem Ansatz, dass während der gesamten Rechnung die geänderte Auswahlregel beachtet werden muss und nicht nur bei Aufstellen des Tableaus und beim Ablesen des Zielwerts.
