对偶与资源价值

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

原问题与对偶问题的资源—价格两侧关系

从下界构造对偶

考虑原问题

\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,

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

primal/dual 可行性与目标相等组成最优证书

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

定义原约束的松弛量 $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。它是局部导数，不是任意大改动后的保证。

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

练习

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

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

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

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