ZU DEN KURSEN!

Operations Research 1 - Umformung in die Normalform (Maximierungsproblem)

Kursangebot | Operations Research 1 | Umformung in die Normalform (Maximierungsproblem)

Operations Research 1

Umformung in die Normalform (Maximierungsproblem)

In den folgenden Abschnitten soll gezeigt werden, wie man mittels des Simplex-Verfahrens ein lineares Optimierungsproblem löst. Zunächst aber muss das lineare Optimierungsproblem in Normalform gegeben sein. Die Normalform lässt sich ganz einfach aus der Standardform (siehe vorherige Kapitel) ableiten.

Die Normalform ist wie folgt definiert:

Methode

Hier klicken zum Ausklappen

             maximiere    $f(x_1, x_2, ... , x_n) = c x_1 + c x_2 + ... c x_n = \sum_{j = 1}^n c_j x_j$ 

u.d.N (unter den Nebenbedingungen)

$a_{ij} x_j + ... + a_{in} x_n = b_i$        $i = 1, ..., m$  und   $j = 1, ..., n$

$x_i \ge 0$                                       $j = 1, ..., n$


Mittels Matrixschreibweise lässt sich die Normalform kompakter schreiben zu:

Methode

Hier klicken zum Ausklappen

            maximiere $f(x) = c^Tx$

u.d.N.


$Ax = b$

$x \ge 0$

Der Unterschied zur Standardform ist die Gleichheitsbedingung $=$ statt der Ungleichheitsbedingung $\le$. 

Vorgehensweise

Um also das Simplex-Verfahren anwenden zu können, muss die Normalform vorliegen. Diese erhält man aus der Standardform. Man geht wie folgt vor:

  1. Lineares Optimierungsproblem in Standardform überführen (siehe vorherige Kapitel).

  2. Standardform in Normalform überführen:
    Hierfür muss die Ungleichheitsbedingung $\le$ der Standardform in eine Gleichheitsbedingung $=$ umgeformt werden. Hierzu werden die Schlupfvariablen $x_{n+1}, ..., x_{N}$ eingeführt. Diese werden innerhalb der Zielfunktion mit $0$ bewertet. Es müssen soviele Schlupfvariablen hinzugefügt werden, wie Ungleichungen in Gleichungen überführt werden müssen.

Wie man die Standardform in die Normalform überführt soll im folgenden Beispiel gezeigt werden.

Beispiel: Standardform in Normalform umwandeln

Beispiel

Hier klicken zum Ausklappen

Gegeben sei das folgende lineare Optimierungsproblem in Standardform:

$f(x_1, x_2) = 5x_1  - 10 x_2 + 10x_3 $    $\rightarrow$  max!

u.d.N

$x_1 +  x_2 - x_3 \le 8$

$-x_1 -  x_2 + x_3 \le -8$

$x_1 - 2 x_2 + 2x_3 \le 4$


$x_1, x_2, x_3 \ge 0$

Geben Sie die Normalform an!

Das obige lineare Optimierungsproblem, welches in Standardform gegeben ist, kann nun durch Einführung von Schlupfvariablen, welche in der Zielfunktion den Wert null erhalten (also nicht berücksichtigt werden) in die Normalform überführt werden. Es werden nun 3 Schlupfvariablen für die drei Ungleichungen eingeführt:

$f(x_1, x_2) = 5x_1  - 10 x_2 + 10x_3 + 0x_4 + 0x_5 + 0x_6$    $\rightarrow$  max!

u.d.N

$x_1 +  x_2 - x_3 + x_4                           = 8$

$-x_1 -  x_2 + x_3         + x_5              = -8$

$x_1 - 2 x_2 + 2x_3                + x_6      = 4$


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

Da die Schlupfvariablen in der Zielfunktion mit dem Wert Null eingehen, können diese auch vernachlässigt werden:

$f(x_1, x_2) = 5x_1  - 10 x_2 + 10x_3$    $\rightarrow$  max!

u.d.N

$x_1 +  x_2 - x_3 + x_4                           = 8$

$-x_1 -  x_2 + x_3         + x_5              = -8$

$x_1 - 2 x_2 + 2x_3                + x_6      = 4$


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

Zur Lösung dieses linearen Optimierungsproblems kann ein Simplex-Verfahren (Big-M-Methode, duales Simplexverfahren) herangezogen werden. Wie diese Verfahren funktionieren wird in den nachfolgenden Abschnitten ausführlich erläutert.