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.

$$\begin{array}{rll}\text{ Primal }& & \text{ Dual }\\ \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 }\end{array}$$

Primales Problem

$$\begin{array}{ll}{\min }_{x,y}& c^{\top }x+d^{\top }y\\ \text{ s.t. }& Ax+By\ge a\\ & Cx+Dy=b\\ & x\ge 0\end{array}$$

Duales Problem

$$\begin{array}{ll}{\max }_{u,v}& a^{\top }u+b^{\top }v\\ \text{ s.t. }& A^{\top }u+C^{\top }v\le c\\ & B^{\top }u+D^{\top }v=d\\ & u\ge 0\end{array}$$