线性规划对偶：定理、互补松弛与影子价格

对偶不是另一套孤立公式，而是同一个线性规划从“生产方案”和“资源定价”两个角度看的结果。

一组标准对应

\begin{aligned} (P)\quad \min\quad &c^Tx\\ \text{s.t.}\quad &Ax\ge b,\ x\ge0 \end{aligned}

的对偶是

\begin{aligned} (D)\quad \max\quad &b^Ty\\ \text{s.t.}\quad &A^Ty\le c,\ y\ge0. \end{aligned}

每条原约束对应一个对偶变量；每个原变量对应一条对偶约束。等式约束对应自由对偶变量，自由原变量对应等式对偶约束。

最稳的做法不是背完整符号表，而是先把原问题化到标准形式，再逐列写对偶。

对任意原可行 $x$ 和对偶可行 $y$ ：

b^Ty\le y^TAx=x^TA^Ty\le c^Tx.

因此对偶值永远是原最小化问题的下界。若找到一对可行解满足 $b^Ty=c^Tx$ ，不用再跑算法，它们已经同时最优。

弱对偶还立即推出：若原问题目标可趋于 $-\infty$ ，对偶不可能可行；若对偶目标可趋于 $+\infty$ ，原问题不可能可行。

在线性规划中，只要一方存在有限最优解，另一方也存在最优解，且

c^Tx^*=b^Ty^*.

单纯形最优表中，检验数的符号条件本质上正是构造了一个对偶可行解。

把弱对偶中的两段不等式变成等式，需要

y_i(Ax-b)_i=0,\qquad x_j(c-A^Ty)_j=0.

使用口诀：

例：若某最优原解满足 $x_1>0,x_2=0$ ，且第一条资源约束有剩余，则相应有第一对偶变量 $y_1=0$ ，而 $x_1$ 对应的对偶约束必须取等号。通常几条线性方程就能求出 $y^*$ 。

在

v(b)=\min\{c^Tx:Ax\ge b,x\ge0\}

中，最优对偶变量 $y_i^*$ 描述右端 $b_i$ 小幅增加时最优值的边际变化。在最优基不变的范围内，

v(b+\Delta b)=v(b)+{y^*}^T\Delta b.

这就是影子价格。它只在局部、最优基保持不变时是精确线性的，不能无限外推。

计算

c^Tx-b^Ty\ge0.

若出现负数，至少有一边不可行或符号写错；若为零且双方可行，最优性已经证明。