Kanonische Form, Standardform, Normalform

In diesem Abschnitt soll nochmals zusammenfassend erläutert werden, welchen Unterschied die

• Kanonische Form,
• Standardform und
• Normalform.

aufweisen.

Kanonische Form

Es handelt sich um die kanonische Form, wenn ein Maximierungsproblem gegeben ist. Hierbei müssen für alle Nebenbedingungen die Kleiner/Gleich-Bedingung ($\le$) gelten und es muss für alle Variablen die Nichtnegativitätsbedingung gegeben sein. Zudem müssen die Werte der rechten Seite alle einen positiven Wert aufweisen.

Anwendung: Primales Simplexverfahren

Beispiel:

$f(x_1, x_2) = 15 x_1 + 25 x_2$      $\rightarrow$ max!

u.d.N.

$x_1 + x_2 \le 150$

$5 x_1 + 8 x_2 \le 80$

              $x_2 \le 70$

$x_1, x_2 \ge 0$

Standardform

Es handelt sich um die Standardform, wenn ein Maximierungsproblem gegeben ist. Hierbei müssen für alle Nebenbedingungen die Kleiner/Gleich-Bedingung ($\le$) gelten und es muss für alle Variablen die Nichtnegativitätsbedingung gegeben sein. Die Werte der rechten Seite müssen aber nicht unbedingt positiv sein.

Anwendung: Bei Vorliegen von negativen Werten auf der rechten Seite (liegen diese nicht vor handelt es sich um die kanonische Form), wird das Verfahren mittels dualen Simplexalgorithmus oder der Big-M-Methode gelöst. Alternativ wird das Problem dualisiert und dann mittels primalen Simplex gelöst (siehe folgende Abschnitte).

Beispiel:

$f(x_1, x_2) = 15 x_1 + 25 x_2$      $\rightarrow$ max!

u.d.N.

$x_1 + x_2 \le -150$

$5 x_1 + 8 x_2 \le 80$

              $x_2 \le 70$

$x_1, x_2 \ge 0$

Normalform

Die Normalform muss letztlich für die Anwendung der ausgewählten Simplexalgorithmen vorliegen. Dabei werden die Nebenbedingungen der kanonische Form bzw. der Standardform in Gleichheitsbedingungen umgeformt, indem Schlupfvariablen eingefügt werden. Diese gehen mit den Wert Null in die Zielfunktion ein und werden innerhalb diese damit nicht berücksichtigt.

Beispiel:

$f(x_1, x_2) = 15 x_1 + 25 x_2$      $\rightarrow$ max!

u.d.N.

$x_1 + x_2        + x_3                     =  -150$

$5 x_1 + 8 x_2            + x_4            = 80$

              $x_2                     + x_5   =  70$

$x_1, x_2, x_3, x_4, x_5 \ge 0$