线性规划的强对偶定理

命题陈述

考虑原始线性规划 $\min\ c^\top x$，约束为 $Ax \ge b,\ x \ge 0$，及其对偶问题 $\max\ b^\top y$，约束为 $A^\top y \le c,\ y \ge 0$。若其中一个问题有最优解，则另一个也有，且它们的最优值相等：$c^\top x^* = b^\top y^*$。

为什么成立?

弱对偶性总是成立：对偶问题的任意可行值都是原始问题任意可行值的下界，就像买家出价永远不会超过资源的真实价值。强对偶定理指出这个差距在最优点恰好消失——对偶变量就像每种受限资源的公平『影子价格』,按影子价格给所有资源定价,恰好重现原始问题的最优成本,不多不少。

用到此定理的主题

相关定理

分步证明

该定理暂无分步证明。