概念

对偶理论

每个线性规划都有对偶问题，强对偶定理保证最优值相等，互补松弛条件与影子价格揭示约束的边际价值。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

对偶理论运筹学

01定义

每个线性规划都有一个对偶问题：原问题最小化、对偶最大化，弱对偶给界、强对偶保证最优值相等。对偶变量的经济解释是影子价格——约束右端每增加一单位，最优目标改善多少。

对偶：min 与 max 从两侧逼近同一最优值

任意可行 $x,y$ ： $b^Ty\leq c^Tx$ （一行乘法可证）——对偶给原问题提供证书；原问题有有限最优解 $\Rightarrow$ 对偶也有且最优值相等。对偶的对偶回到原问题。

最优时 $x_j$ 与第 $j$ 条对偶约束的松弛互补为零：变量非零 $\Leftrightarrow$ 对应约束取等。影子价格 $y_i^*$ 是资源 $i$ 的边际价值——经济学与最优化的接口。

参数扰动下最优解如何变化：对偶变量直接给出右端项的边际效应，基不变区间内目标函数线性变化——生产计划「如果原料涨价怎么办」的答案。

b^Ty\leq c^Tx,\quad \max\ b^Ty=\min\ c^Tx\ (\text{强对偶})

冯·诺依曼 1947 年在与丹齐格交谈当天即写出对偶理论；盖尔-库恩-塔克 1951 年严格证明；库普曼斯的经济解释使其获 1975 年诺贝尔奖。

电力市场的节点电价、拍卖中的清算价格、资源定价与影子价格报告、列生成与拉格朗日松弛等大规模算法的收敛证书。

线性规划对偶：max cᵀx 与 min bᵀy拖动 c₁ 改变目标方向：原问题与对偶问题的最优值始终相等（强对偶）

c₁1.00