对偶与资源价值

同一份资源分配问题，可以从“怎样选择活动”来问，也可以从“每单位资源至少应该值多少钱”来问。后一个问题就是对偶。它不是把原题抄一遍，而是在寻找一个能证明原题最优值不能更低的价格系统。

从下界构造对偶

考虑原问题

$$\min c^Tx\quad\text{s.t. }Ax\ge b,\ x\ge0.$$

给每条资源约束一个非负价格 $y_i\ge0$。若价格向量满足

$$A^Ty\le c,$$

那么每种活动的“资源价格”都不超过它的直接成本。对任意原问题可行 $x$，有

$$b^Ty\le x^TA^Ty\le c^Tx.$$

于是 $b^Ty$ 是原问题最优值的下界。我们希望这个下界尽量大，于是得到对偶最大化问题

$$\max b^Ty\quad\text{s.t. }A^Ty\le c,\ y\ge0.$$

这就是弱对偶：任何原可行解都不低于任何对偶可行解。它不需要强对偶定理，单靠矩阵乘法和符号条件即可证明，因此非常适合当作独立的最优性检查。

相等就是证书

若找到原可行 $x$ 和对偶可行 $y$，并且

$$c^Tx=b^Ty,$$

两边都夹在同一个数上：原问题不可能有更小值，对偶也不可能有更大值，所以两者同时最优。这个证书比“算法运行了若干轮”更直接，别人可以独立检查可行性和两个目标值。

互补松弛告诉我们哪里在起作用

定义原约束的松弛量 $s=Ax-b\ge0$，对偶约束的松弛量 $r=c-A^Ty\ge0$。由

$$c^Tx-b^Ty=x^T(c-A^Ty)+y^T(Ax-b)=x^Tr+y^Ts,$$

可见目标间隙是两个非负项的和。间隙为零当且仅当

$$x_jr_j=0\quad\text{对每个 }j,\qquad y_is_i=0\quad\text{对每个 }i.$$

这意味着：若一个活动在原解中用了正量 $x_j>0$，它的对偶约束必须紧；若一种资源还有剩余 $s_i>0$，它的价格必须是零。互补松弛能把数值答案翻译成一句业务解释。

敏感性不是永久承诺

若右端项 $b_i$ 增加一点，最优值常近似变化 $y_i\Delta b_i$。例如资源影子价格为 7，增加 3 单位资源时，在当前基仍保持最优的范围内，最优成本约改变 21。它是局部导数，不是任意大改动后的保证。

当某个非基变量变成正数、某个基变量降到零，当前基可能改变；此时原来的影子价格、目标斜率和可行方案结构都要重新计算。报告中要写出“有效区间”或至少说明这是小扰动解释。

练习

1. 原问题是 $\min 3x_1+2x_2$ s.t. $x_1+x_2\ge4$、、。写出对偶。

查看解答

约束矩阵的两列分别是 $(1,2)^T$ 与 $(1,1)^T$，所以对偶为 $\max 4y_1+5y_2$，约束 、，并且 。

2. 已知原可行 $x$ 的第一种活动用量为正，但对应对偶约束有严格松弛。能否两者同时最优？

查看解答

不能。若 $x_j>0$ 且 $r_j=c_j-a_j^Ty>0$，则目标间隙中有 ，两目标值不可能相等，因此至少有一个解不是最优配对。

3. 为什么影子价格不能用于解释资源量大幅变化后的新最优值？

查看解答

影子价格来自当前基下的局部边际变化。扰动太大可能使基变量符号改变或另一约束变紧，最优基随之改变，原价格不再是新的斜率。

1

若原、对偶解都可行且目标值相等，可以得到哪些结论？

A.原解最优B.对偶解最优C.原问题一定有唯一解D.所有约束都必须紧

提交