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

	原问题	对偶问题
变量	$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^T$得到 \begin{align*} y^TAx&\le y^Tb\\ &\Longleftrightarrow\\ (A^Ty)^T x&\le b^Ty \end{align*}

需保持$\le$方向，因此$y\ge0$。若选取$y$使得$c\le A^T y$，我们就得到$c^T x$的上界$b^T y$。因此对偶问题就是在$y\ge0$以及$A^T y\ge c$的约束下，最小化$c^Tx$的上界$b^Ty$。

同理，若对偶问题是 \begin{align*} \min&~b^T y\\A^T y&\ge c\\y&\ge0 \end{align*} 原问题需要通过对约束条件进行线性组合，以找到一个对偶问题的下界。即，在$A^Ty\ge c$两边同乘变量$x^T$得到 \begin{align*} x^TA^Ty&\ge x^Tc\\ &\Longleftrightarrow\\ (Ax)^T y&\ge c^T x \end{align*}

需保持$\ge$方向，因此$x\ge0$。若选取$x$使得$b\ge A x$，我们就得到$b^T y$的下界$c^T x$。因此原问题就是在$x\ge0$以及$A x\le b$的约束下，最大化$b^T y$的下界$c^T x$。

我们考虑对于求最大值的线性规划来说，什么是“正常”的。即，约束为$\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$代表割掉这条边。显然这就是最大流问题的对偶问题──最小割问题。

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