存在即有理---线性规划中的对偶-白红宇

在求解一个规划问题（不限于线性规划）的时候，我们常常需要知道这个问题有没有可行解（有时候约束条件很复杂，不要说最优解，找到可行解都很难），或者是估计一下目前的解离最优解还有多远（大型问题多用迭代解法，如果能大致估计当前的解的质量，就对算法什么时候运行结束有一个大致的把握，如果得到了可接受的近似解也可以提前停止），以及判断原问题的最优解是否无界（万一出现这种情况迭代就停不下来了）。

我们从对偶理论开始理解

对偶问题就是回答这些问题的利器：弱对偶定理给原问题的最优解定了一个界，强对偶定理给出了原问题最优解的一个判定条件。同时，还有很多别的优良性质：例如可以化难为易（把难以求解的约束条件扔到目标函数的位置上去），如果问题的形式合适(变量少，约束多)还可以通过把约束变量和对偶变量互换来把大规模问题转换成小规模问题。实际上，很多凸优化问题都是通过解对偶问题来求解的，线性规划只是其中一个特例而已。

对于一个带有不等式条件约束的优化问题：

min \quad z=c^Tx \qquad s.t. \quad Ax \geq b(x \geq 0)

其对偶问题是

max \quad w =b^Ty \qquad s.t. \quad A^Ty \leq c(y \geq 0)

那么问题来了，看起来规律满满，实际上一点儿也摸不着头脑。为啥是这样？我给大家举个栗子来说明一下。

某家电厂生产家电，现有资源生产两种产品，有关数据如下表：

\begin{array}{c} % inner horizontal array of arrays 内层水平表格 \begin{array}{c|cccc} \Delta&产品1&产品2&总限时\\ \hline 设备A & 0 & 5 & 15hour \\ 设备B & 6 & 2 & 24hour \\ 调试工序 & 1 & 1 & 5hour \\ \hline 利润 & 2 & 1 & \end{array} \end{array}

这表的意思就是我们工厂总共给设备A划分15个小时的工作时间，给设备B24小时的工作时间，并且给调试工序分配5小时，设备A和设备B生产产品1和2的耗时如表所示(0代表生产不了)，最后一个产品1 获得利润为2，产品2获得利润为1。工厂嘛，求利润最大时如何分配。

那么很容易我们将其写成一个带有若干条件约束的优化问题。

\begin{matrix} & max \quad z=2x_1+x_2 \\ s.t. & 6x_1+2x_2 \leq 24 \\ & x_1+x_2 \leq 5 \\ & x_1,x_2 \geq 0 \\ \end{matrix}

厂家的思维是我有这么多资源，我要尽可能的把它变成钱。那这时候来了个收购此厂家的人，他呢，当然不希望这厂家利润高，因为厂家利润高，他就得花更多的钱来收购厂家。但是厂家利润也不是无止境的低，毕竟生产出来的东西就是有那么多利润嘛。我们设设备A的利润是 $y_1$ 元/hour，设备B的利润是 $y_2$ 元/hour，调试工序的利润是 $y_3$ 元/hour。

收购的时候，由于厂家希望自己利润高，厂子能够卖更多钱，所以能接受的利润也是有底线的。底线为：

在这个底线基础上，收购方需要总利润尽可能低：

于是，我们这个问题就成了：

\begin{matrix} & min \quad w=15y_1+24y_2+5y_3 \\ s.t. & 6y_2+y \geq 2 \\ & 5y_1 +2y_2+y_3 \geq 1 \\ & y_1,y_2,y_3 \geq 0 \\ \end{matrix}

这便是原问题的对偶问题。对偶问题常有其明显的经济含义。

一般规则

根据原问题写出其对偶问题时要注意约束条件和变量的符号变化情况，其变换规则如下

max 问题第 i 个约束取“≥”，则min问题第 i 个变量 ≤ 0

min 问题第 i 个约束取“≤”，则max问题第 i 个变量 ≤ 0

原问题第 i 个约束取等式，对偶问题第 i 个变量无约束

max 问题第 j 个变量 ≤ 0 ,则min问题第j个约束取“≤”

min 问题第 j 个变量 ≤ 0 ，则max问题第j个约束取“≥”

原问题第j个变量无约束，对偶问题第j个约束取等式

以上规则是具体的变换规则，实际上其变换规律就是假如原问题不符合以上的给出的(1)或(2)的标准形状，那么原问题的第 i 个不符合要求的约束，对应的对偶问题的第i个变量要 ≤ 0 ；同样假如原问题的第 i 个变量不符合要求(就是 xi≤ 0)，对应的对偶问题的第i个约束要改变符号。

对偶定理包含了一系列的定理，其中主要有弱对偶定理，强对偶定理，最优性定理，互补松弛定理。通过这些定理可以将原来难以解决的原问题通过引入对偶理论从而得以解决，各定理的具体内容如下:

弱对偶定理

max 问题任一可行解的目标值为min问题目标值的一个下界； min 问题任一可行解的目标值为max问题目标值的一个上界

强对偶定理

若原问题有最优解，那么对偶问题也有最优解，且两个问题最优解的目标函数值相等。

无界性

若原问题(对偶问题)为无界解，则对偶问题(原问题)为无可行解。

需要注意的是，无界性的逆不存在。若原(对偶)问题为无可行解，对偶(原问题)问题或为无界解，或为无可行解。

最优性

若 $\overline{x}$ 和 $\overline{y}$ 分别为原问题和对偶问题的可行解，那么原问题和对偶问题都有最优解，且当 $c^T\overline{x}=b^T \overline{y}$ 时， $\overline{x}$ 和 $\overline{y}$ 分别为原问题和对偶问题的最优解。

互补松弛定理

若 $\overline{x}$ 和 $\overline{y}$ 分别为原问题和对偶问题的可行解，则它们分别是原问题和对偶问题的最优解的充要条件是 $\overline{x}^T(A^T\overline{y}−c)=0$ 和 $\overline{y}^T(A\overline{x}−b)=0$ 通过互补松弛定理，给出原问题(对偶问题)的最优解，便可求得其对偶问题(原问题)的最优解。