Normalform (kanonische Form)
Voraussetzung: Zielfunktion
Der Simplex-Algorithmus ist auf eine feste Gestalt des Problems zugeschnitten, die kanonische Form oder Normalform. Aufgaben aus der Praxis und aus Klausuren sehen oft anders aus: Es wird minimiert, oder eine Nebenbedingung hat \(\ge\). Bevor du rechnest, bringst du das Problem deshalb in diese Form. Voraussetzung ist die Zielfunktion und das Rechnen mit Ungleichungen.
Ein lineares Optimierungsproblem ist in kanonischer Form, wenn vier Dinge gelten:
- Die Zielfunktion \(Z\) wird maximiert.
- Jede Nebenbedingung hat die Gestalt \(a_{i1}x_1+\dots+a_{in}x_n\le b_i\).
- Jede rechte Seite ist nichtnegativ, \(b_i\ge 0\).
- Alle Variablen sind nichtnegativ, \(x_i\ge 0\).
Eigenschaft 3 hat einen Grund. Im Simplex-Starttableau sind alle Entscheidungsvariablen \(0\). Der Ursprung muss dann eine zulässige Lösung sein, und das ist er nur, wenn \(0\le b_i\) für jede Nebenbedingung gilt. Eigenschaft 4 gilt in Wirtschaftsaufgaben von selbst, weil Mengen nicht negativ sind.
Ist das Problem nicht in kanonischer Form, hilft eine von zwei Umformungen. Soll minimiert werden, maximierst du stattdessen \(\tilde Z=-Z\): Alle Koeffizienten wechseln das Vorzeichen. Hat eine Nebenbedingung die Gestalt \(a_{i1}x_1+\dots+a_{in}x_n\ge -b_i\) mit \(b_i>0\), multiplizierst du die ganze Ungleichung mit \(-1\). Das Zeichen dreht sich, und alle Zahlen wechseln das Vorzeichen, auch auf der rechten Seite.
Wenn die rechte Seite positiv bleibt
Eine Nebenbedingung wie \(x_1+x_2\ge 4\) hat \(\ge\) und eine positive rechte Seite. Mit \(-1\) multipliziert wird daraus \(-x_1-x_2\le -4\), und die rechte Seite ist negativ. Eine solche Aufgabe lässt sich nicht in kanonische Form bringen. Der Ursprung ist hier nicht zulässig, denn \(0+0\ge 4\) ist falsch. Für diesen Fall gibt es eine erweiterte Methode, die Zweiphasenmethode.
Ein zweites Beispiel, nur die Zielfunktion ist zu ändern
Maximiere \(Z=7x_1+2x_2\) unter \(x_1+x_2\le 10\), \(3x_1+x_2\le 18\), \(x_1,x_2\ge 0\). Es wird maximiert, jede Nebenbedingung hat \(\le\), die rechten Seiten \(10\) und \(18\) sind nichtnegativ und die Variablen sind nichtnegativ. Das Problem ist schon in kanonischer Form, es ist nichts umzuformen.