线性规划

如何将标准主问题转化为对偶问题？

定理：主问题(P)

$$ \begin{align*} &\max && c^\top x \\ &s.t. && Ax=b \\ & && x\geq0 \end{align*} $$

的对偶问题(D)为

$$ \begin{align*} &\min && b^\top y \\ &s.t. && A^\top y\geq c \end{align*} $$

任何线性规划问题都可以写成标准形式，如下例：
非标准形式(P1)

$$ \begin{align*} &\max && d^\top x \\ &s.t. && Fx=0 \\ & && Ix\leq c \\ & && x\geq0 \end{align*} $$

引入松弛变量$x^\prime$，则有标准形式(P)

$$ \begin{align*} &\max && \begin{bmatrix}d\\0\end{bmatrix} ^\top \begin{bmatrix}x\\x^\prime\end{bmatrix} \\ &s.t. && \begin{bmatrix}I & 1\\F & 0\end{bmatrix}\begin{bmatrix}x\\x^\prime\end{bmatrix}= \begin{bmatrix}c\\0\end{bmatrix} \\ & && \begin{bmatrix}x\\x^\prime\end{bmatrix}\geq0 \end{align*} $$

使用以上定理可以很容易得到对偶问题

对于最小化问题，可以先转为最大化问题再使用以上定理，也可以直接使用以下定理
定理：主问题(P)

$$ \begin{align*} &\min && c^\top x \\ &s.t. && Ax=b \\ & && x\geq0 \end{align*} $$

则有对偶问题(D)

$$ \begin{align*} &\max && b^\top y \\ &s.t. && A^\top y\leq c \end{align*} $$