线性规划原问题与对偶问题的转换

	原问题	对偶问题
变量	$x_1,\cdots,x_n$	$y_1,\cdots,y_m$
矩阵	$A$	$A^T$
不等式右方常数	$b$	$c$
目标函数	$\max c^Tx$	$\min b^T y$
约束	第$i$条约束是$\le$	$y_i\ge0$
	$\ge$	$y_i\le0$
	$=$	$y_i\in\F$
	$x_j\ge0$	第$j$条约束是$\ge$
	$x_j\le0$	$\le$
	$x_j\in\F$	$=$

首先解释表格中反直觉的约束符号对应变量取值符号的问题。例如，原问题$\le$的约束对应对偶变量$\ge0$的取值，而对偶问题$\ge$的约束同样对应原变量$\ge0$的取值。

假设我们有一个求最大值的线性规划原问题
\begin{align*}
\max&~c^T x\\
Ax&\le b\\
x&\ge0
\end{align*}
对偶问题需要通过对约束条件进行线性组合，以找到一个原问题的上界。即，在$Ax\le b$两边同乘变量$y$，且保持$\le$方向。因此$y\ge0$。

于是，原问题的$\le$约束对应对偶变量的$\ge0$。

同理，若对偶问题是求最小值，对应的约束是$A^T y\ge c$，则原问题需要找一个对偶问题的下界。即，在$A^T y\ge c$两边同乘变量$x$，且保持$\ge$方向，因此$x\ge0$。

我们考虑对于求最大值的线性规划来说，什么是“正常”的。即，约束为$\le$以防止变量无限制增大，且取值$\ge0$。对于求最小值的线性规划，约束为$\ge$以防止变量无限制减小，变量同样取值$\ge0$。

在转换对偶问题时，“正常”的原问题约束，对应“正常”的对偶问题变量，“反常”的原问题约束，对应”反常“的对偶问题变量，严格的原问题约束（取等），对应对偶问题的自由变量（$\in\F$）：

原问题性质	对偶问题性质
$\max$原问题正常约束	$\min$对偶问题正常变量
$\max$原问题反常约束	$\min$对偶问题反常变量
$\max$原问题严格约束	$\min$对偶问题自由变量
$\max$原问题正常变量	$\min$对偶问题正常约束
$\max$原问题反常变量	$\min$对偶问题反常约束
$\max$原问题自由变量	$\min$对偶问题严格约束

用网络最大流问题的按路径建模的线性规划举例。设$G=(V,E)$是一个有向图，边容量$u:E\to \F_{+}$，$s$和$t$分别是源点和汇点。设

\[ \mathcal{P}:=\{P\subseteq E\mid P\text{是一条$s-t-$路径}\} \]

则最大流问题的线性规划模型为：

\begin{array}{rl} \max & \displaystyle \sum_{P\in\mathcal P} y_P\\ \text{s.t.} & \displaystyle \sum_{P\in\mathcal P:\, e\in P} y_P \le u(e) \qquad \forall e\in E,\\ & y_P\ge 0 \qquad \forall P\in\mathcal P. \end{array}

运用转换法则：每条路径有一个“正常”变量$y_P$代表路径上的流量，每条边有一条正常“约束”保证经过这条边的流量不超过容量。对每条约束（边）引入“正常”对偶变量$x_e$，约束符号为$\ge$，取值$\ge0$。对偶问题有原问题变量数量条约束，右边常数是原目标函数内对应原变量的系数$1$，左边$e$的约束的对偶变量$x_e$的系数是原变量在$e$的约束中的系数$1$。于是得到其对偶问题的线性规划模型：

\begin{array}{rl}
\min & \displaystyle \sum_{e\in E} u(e)x_e\\
\text{s.t.}
& \displaystyle \sum_{e\in P}x_e\ge 1
\qquad \forall P\in\mathcal P,\\
& x_e\ge 0
\qquad \forall e\in E.
\end{array}

$x_e=1$代表割掉这条边（$x_e$可以取分数并不影响，因为线性规划的最优解出现在解多胞形的一个极小面上）。显然这就是最大流问题的对偶问题──最小割问题。

注：实际上这个基于路径的模型是极差的，因为路径数量可以达到指数级别。一般最大流问题的线性规划模型基于节点的流平衡。