割平面法 我来为您详细讲解运筹学中一个重要的数学规划方法——割平面法。 1. 基本概念 割平面法是一种求解整数规划问题的精确算法。它的核心思想是：先求解原整数规划问题对应的线性规划松弛问题（即去掉整数约束），如果得到的最优解不满足整数性要求，就添加一个线性不等式约束（称为割平面）来割掉部分非整数解区域，但不割掉任何整数可行解，然后重新求解新的线性规划问题，如此迭代直到找到整数最优解。 2. 方法原理 考虑整数规划问题：min{cᵀx: Ax ≤ b, x ∈ Z₊ⁿ} 首先求解线性规划松弛：min{cᵀx: Ax ≤ b, x ≥ 0} 设得到最优解x* 如果x* 的所有分量都是整数，则已找到最优解 如果x 有非整数值，则构造割平面（有效不等式），将x 割掉但保留所有整数可行解 3. Gomory割平面构造 对于纯整数规划，最经典的是Gomory割平面： 从单纯形表的最终表中选择一个分数解的基本变量xᵢ 写出该行约束：xᵢ + ∑ⱼaᵢⱼxⱼ = bᵢ 将系数分解为整数部分和小数部分：aᵢⱼ = ⌊aᵢⱼ⌋ + fᵢⱼ, bᵢ = ⌊bᵢ⌋ + fᵢ 构造割平面：∑ⱼfᵢⱼxⱼ ≥ fᵢ 4. 算法步骤 求解当前线性规划松弛问题 检查最优解是否为整数解 如果是，输出最优解；算法结束 如果不是，选择一个分数变量构造割平面 将割平面添加到约束集中 返回步骤1 5. 收敛性保证 在合理假设下，Gomory割平面法具有有限收敛性。经过有限次迭代后，算法要么找到整数最优解，要么证明问题无可行解。这是因为每次添加割平面后，可行域都被严格缩小，而整数点的数量是有限的。 6. 实际应用考虑 割平面的选择策略影响算法效率 可能需要添加多个割平面才能得到整数解 常与分支定界法结合形成分支割平面法 现代整数规划求解器都集成了割平面技术 这种方法将困难的整数规划问题转化为一系列相对容易求解的线性规划问题，是整数规划理论的重要基石。