线性规划与单纯形法
- 线性规划与单纯形法
- 线性规划的概念
- 对偶原理
- 内容
- 证明（此部分由 AI 辅助编写）
- A. 弱对偶性 (Weak Duality)
- B. 强对偶性 (Strong Duality)
- 快速求对偶问题：矩阵转置大法
- 单纯形法
线性规划的概念
对偶原理
内容
对于原问题：
它的对偶问题是：
以上两个问题互为对偶问题。对偶问题的对偶问题是原问题。
证明（此部分由 AI 辅助编写）
对偶理论中最基础且重要的两个证明是弱对偶性和强对偶性。
A. 弱对偶性 (Weak Duality)
内容：若 \(\mathbf{x}\) 是原问题的可行解，\(\mathbf{y}\) 是对偶问题的可行解，则恒有 \(\mathbf{c}^T \mathbf{x} \le \mathbf{b}^T \mathbf{y}\)。
证明：
-
由对偶问题的约束条件可知：\(\mathbf{A}^T \mathbf{y} \ge \mathbf{c}\)。
-
由于 \(\mathbf{x} \ge \mathbf{0}\)，我们在等式两边左乘 \(\mathbf{x}^T\)（或右乘 \(\mathbf{x}\)），不等号方向不变：
\[\mathbf{x}^T (\mathbf{A}^T \mathbf{y}) \ge \mathbf{x}^T \mathbf{c} \implies (\mathbf{A}\mathbf{x})^T \mathbf{y} \ge \mathbf{c}^T \mathbf{x} \] -
再看原问题的约束：\(\mathbf{A}\mathbf{x} \le \mathbf{b}\)。
-
由于 \(\mathbf{y} \ge \mathbf{0}\)，我们在等式两边右乘 \(\mathbf{y}\)：
\[\mathbf{y}^T (\mathbf{A}\mathbf{x}) \le \mathbf{y}^T \mathbf{b} \implies (\mathbf{A}\mathbf{x})^T \mathbf{y} \le \mathbf{b}^T \mathbf{y} \] -
结合 (2) 和 (4) 的结果：
\[\mathbf{c}^T \mathbf{x} \le (\mathbf{A}\mathbf{x})^T \mathbf{y} \le \mathbf{b}^T \mathbf{y} \]证毕。
直观意义：对偶问题的任何一个可行解，都为原问题的最大值提供了一个“天花板”。
B. 强对偶性 (Strong Duality)
内容：若原问题有最优解 \(\mathbf{x}^*\)，则对偶问题也有最优解 \(\mathbf{y}^*\)，且 \(\mathbf{c}^T \mathbf{x}^* = \mathbf{b}^T \mathbf{y}^*\)。
证明简述（基于单纯形法）：
利用单纯形法的最优表结构可以给出构造性证明：
- 当单纯形法达到最优时，检验数 \(\sigma_j = c_j - \mathbf{c}_B^T \mathbf{B}^{-1} \mathbf{A}_j \le 0\)（对于所有 \(j\)）。
- 令 \(\mathbf{y}^T = \mathbf{c}_B^T \mathbf{B}^{-1}\)。
- 由检验数 \(\le 0\) 可得：\(\mathbf{c}_B^T \mathbf{B}^{-1} \mathbf{A} \ge \mathbf{c}^T\)，即 \(\mathbf{y}^T \mathbf{A} \ge \mathbf{c}^T\)，这满足对偶问题的约束。
- 此时原问题的最优值 \(Z^* = \mathbf{c}_B^T \mathbf{B}^{-1} \mathbf{b} = \mathbf{y}^T \mathbf{b} = W\)。
- 根据弱对偶性，既然找到了一个使得 \(Z=W\) 的可行解，那么它必然是各自的最优解。
快速求对偶问题：矩阵转置大法
一个例子：
求以下问题的对偶问题：
\[\begin{aligned} \max \quad& z=4x_1+3x_2 \\ \text{s.t.} \quad & 2x_1+x_2\le 10 \\ & x_1+x_2\le 8 \\ & x_2\le 7 \\ & x_1,x_2\ge 0 \end{aligned} \]
我们可以根据系数写出矩阵：
其中第一行表示最值函数中的系数，第一个位置是补位的 \(0\)。第一列是不等号右边的常数。其他位置代表不等号左边的系数。
我们将它转置得到：
它就代表以下对偶问题：