Duale Transformationsregeln

Mit diesen Regeln lässt sich ein primales Problem in ein duales Problem umwandeln. Das kann dann zum Beispiel mit dem dualen Simplex gelöst werden.

 Primal  Dual  Ungleichung ↔ nicht-negative Variable  Gleichung ↔ freie Variable  nicht-negative Variable ↔ Ungleichung  freie Variable ↔ Gleichung \begin{array}{rll} \hline \text { Primal } & & \text { Dual } \\ \hline \text { Ungleichung } & \leftrightarrow & \text { nicht-negative Variable } \\ \text { Gleichung } & \leftrightarrow & \text { freie Variable } \\ \text { nicht-negative Variable } & \leftrightarrow & \text { Ungleichung } \\ \text { freie Variable } & \leftrightarrow & \text { Gleichung } \\ \hline \end{array}

Primales Problem

min⁡x,yc⊤x+d⊤y s.t. Ax+By≥aCx+Dy=bx≥0\begin{array}{ll} \min _{x, y} & c^{\top} x+d^{\top} y \\ \text { s.t. } & A x+B y \geq a \\ & C x+D y=b \\ & x \geq 0 \end{array}

Duales Problem

max⁡u,va⊤u+b⊤v s.t. A⊤u+C⊤v≤cB⊤u+D⊤v=du≥0\begin{array}{ll} \max _{u, v} & a^{\top} u+b^{\top} v \\ \text { s.t. } & A^{\top} u+C^{\top} v \leq c \\ & B^{\top} u+D^{\top} v=d \\ & u \geq 0 \end{array}