Aufstellen eines linearen Programms - Überführung in Standard- oder Schlupfform (Uni Köln)

Um lineare Programme mit einem Algorithmus lösen zu können, müssen diese in eine Form gebracht werden, die von einem Programm verarbeitet werden kann.

Hier eine kleine Zusammenfassung der "Umwandlungstricks"

Umwandlung in die Standardform

Alle Nebenbedingungen der Standardform haben die Form $Ax \le b$ und in der Regel gilt für alle x die Nichtnegativitätsbedingung $x_i \ge 0, i=\{1..n\}$

Die Zielform ist also immer
$\text{max } c^t x$
$Ax \le b$
$x \ge 0$

(1) Umwandlung von Gleichheit in Ungleichheit

$\text{max } c^t x$
Ax = b
$x \ge 0$

Umwandlung:

$\text{max } c^t x$
$\begin{pmatrix} A \\ -A \end{pmatrix} x \le \begin{pmatrix} b \\ -b \end{pmatrix}$
$x \ge 0$

(2) Hinzufügen der Nichtnegativitätsbedingung

$\text{max } c^t x$
Ax = b

Umwandlung (die positiven und die negativen Komponenten von x werden quasi gesondert abgefangen):

$\text{max } c^t x$
$A(x^+ - x^-) \le b \gdw \begin{pmatrix} A & -A \end{pmatrix} \begin{pmatrix} x^+ \\ x^- \end{pmatrix} \le b$
$x \ge 0$

Umwandlung in die Schlupfform

Die Schlupfform beeinhaltet ebenfalls die Nichtnegativitätsbedingung. Alle anderen Bedingungen werden durch Gleichheit ausgedrückt.
Die Zielform ist also immer
$\text{max } c^t x$
Ax = b
$x \ge 0$

(3) Ungleichheit in Gleichheit umwandeln

Dazu wird die Schlupfvariable s eingesetzt

$\text{max } c^t x$
$Ax \le b$
$x \ge 0$

Umwandlung mit der Schlupfvariable $s = b - Ax \gdw Ax + s = b$
$\text{max } c^t x$
$\begin{pmatrix} A & I \end{pmatrix} \begin{pmatrix} x \\ s \end{pmatrix} = b$
$x \ge 0$

« Zurück zur Liste

Kursinformation

Hochschule:: Universität zu Köln
Veranstaltung:: Effiziente Algorithmen
Leitung:: Prof. Dr. R. Schrader
Download:: PDF-Dokument

Leite dieses Dokument an Freunde weiter.