对偶理论

1. 基本概念
   对偶理论是线性规划的核心内容之一，它指出每一个线性规划问题（称为原问题）都对应一个与之密切相关的另一个线性规划问题（称为对偶问题）。原问题与对偶问题在数学模型、解的性质和经济解释上存在紧密联系。例如，若原问题是最大化目标函数，则对偶问题通常是最小化目标函数，且约束条件与原问题的变量方向相反。

2. 数学模型的对偶关系
   考虑标准形式的原问题：

\[ \begin{align*} \text{最大化} \quad & z = \mathbf{c}^T \mathbf{x} \\ \text{约束条件} \quad & A\mathbf{x} \leq \mathbf{b}, \\ & \mathbf{x} \geq \mathbf{0}. \end{align*} \]

其对偶问题为：

\[ \begin{align*} \text{最小化} \quad & w = \mathbf{b}^T \mathbf{y} \\ \text{约束条件} \quad & A^T \mathbf{y} \geq \mathbf{c}, \\ & \mathbf{y} \geq \mathbf{0}. \end{align*} \]

其中，\(\mathbf{x}\) 是原问题的决策变量，\(\mathbf{y}\) 是对偶变量（也称为影子价格）。每个原约束对应一个对偶变量，原问题的资源限制 \(\mathbf{b}\) 成为对偶问题的目标函数系数。

3. 对偶定理与解的性质

   • 弱对偶定理：若 \(\mathbf{x}\) 和 \(\mathbf{y}\) 分别是原问题和对偶问题的可行解，则 \(\mathbf{c}^T \mathbf{x} \leq \mathbf{b}^T \mathbf{y}\)。这意味着最大化问题的目标值不会超过最小化问题的目标值。
   • 强对偶定理：若原问题有最优解，则对偶问题也有最优解，且两者目标函数值相等（即 \(z^* = w^*\)）。
   • 互补松弛条件：最优解满足 \(\mathbf{x}^T (A^T \mathbf{y} - \mathbf{c}) = 0\) 和 \(\mathbf{y}^T (A\mathbf{x} - \mathbf{b}) = 0\)，即资源有剩余时对应影子价格为0，资源稀缺时影子价格为正。

4. 经济解释：影子价格
   对偶变量 \(\mathbf{y}\) 具有重要的经济含义，表示对应资源每增加一单位时目标函数值的改进量。例如，在原问题中，若第 \(i\) 种资源的影子价格 \(y_i = 5\)，则增加一单位该资源可使目标函数值增加5。这为资源分配提供了边际价值参考。

5. 应用与扩展
   对偶理论不仅用于灵敏度分析（分析参数变化对解的影响），还启发了算法设计（如对偶单纯形法）。在整数规划中，对偶性常用于构造拉格朗日松弛或分支定界法的下界。此外，对偶思想可推广到非线性规划和网络优化等问题中。