基于线性规划的分解算法求解示例
题目描述
考虑一个大型线性规划问题：
\[\min \quad c^T x \]
\[\text{s.t.} \quad A_1 x \le b_1 \quad (\text{约束组1}), \]
\[\quad \quad \quad A_2 x \le b_2 \quad (\text{约束组2}), \]
\[\quad \quad \quad x \ge 0, \]
其中约束组1的规模远小于约束组2（例如组1有几十个约束，组2有数千个约束），且约束组2具有可分解的结构（如多个互不关联的块约束）。直接求解整个问题计算成本高，需用分解算法将问题拆分为主问题和子问题迭代求解。
解题过程
1. 问题分解
将约束分为两部分：
- 主问题（Master Problem）：包含约束组1和部分活跃约束（初始可能为空）。
- 子问题（Subproblem）：包含约束组2，可进一步按结构分解为独立子问题（如按资源或时间段划分）。
原问题重写为：
\[\min \quad c^T x \]
\[\text{s.t.} \quad A_1 x \le b_1 \quad (\text{主问题约束}), \]
\[\quad \quad \quad A_2 x \le b_2 \quad (\text{子问题约束}), \]
\[\quad \quad \quad x \ge 0. \]
2. 初始主问题构建
忽略约束组2，得到初始松弛主问题：
\[\min \quad c^T x \]
\[\text{s.t.} \quad A_1 x \le b_1, \quad x \ge 0. \]
求解该问题得到初始解 \(x^*\)。
3. 子问题检验可行性
将 \(x^*\) 代入约束组2：
- 若 \(A_2 x^* \le b_2\) 成立，则 \(x^*\) 是原问题最优解，算法终止。
- 若存在违反的约束（如 \(a_i^T x > b_i\)），则生成一个割平面（Cut）添加到主问题。割平面形式为：
\[a_i^T x \le b_i \quad (\text{违反的约束})。 \]
4. 迭代过程
重复以下步骤直至收敛：
- 求解主问题：使用当前所有割平面，得到解 \(x^*\)。
- 调用子问题：检验 \(x^*\) 是否满足 \(A_2 x \le b_2\)。
- 若满足，算法终止。
- 若不满足，从违反约束中选择一个或多个生成割平面，加入主问题。
5. 收敛性说明
- 由于约束组2有限，最多生成所有可能约束后必收敛。
- 实际中通过优先级选择“最违反”的约束（如最大化 \(a_i^T x^* - b_i\)）加速收敛。
示例演示
假设原问题为：
\[\min \quad 2x_1 + 3x_2 \]
\[\text{s.t.} \quad x_1 + x_2 \le 5 \quad (\text{主约束}), \]
\[\quad \quad \quad 2x_1 + x_2 \le 8, \quad x_1 + 2x_2 \le 7 \quad (\text{子问题约束}), \]
\[\quad \quad \quad x_1, x_2 \ge 0. \]
步骤1：初始主问题仅包含 \(x_1 + x_2 \le 5\)，求解得 \(x^* = (5, 0)\)，目标值10。
步骤2：检验子问题约束：
- \(2(5) + 0 = 10 > 8\)（违反），添加割平面 \(2x_1 + x_2 \le 8\)。
步骤3：主问题更新为：
\[\min \quad 2x_1 + 3x_2 \]
\[\text{s.t.} \quad x_1 + x_2 \le 5, \quad 2x_1 + x_2 \le 8, \quad x \ge 0. \]
求解得 \(x^* = (3, 2)\)，目标值12。
步骤4：检验子问题约束：
- \(2(3) + 2 = 8 \le 8\)（满足），
- \(3 + 2(2) = 7 \le 7\)（满足），故最优解为 \((3, 2)\)。
关键点总结
- 分解算法通过割平面逐步逼近可行域，避免直接处理大规模约束。
- 适用于具有可分离结构的线性规划问题（如网络流、多阶段规划）。
- 效率取决于割平面生成策略（如贪心选择最紧约束）。