分支定界法 第一步：基本概念与问题背景 分支定界法是一种用于求解整数规划问题的精确算法。许多实际问题要求决策变量取整数值（如生产数量、人员分配），但线性规划的松弛解可能得到非整数解。分支定界法通过“分支”和“定界”两个核心操作，系统性地枚举可行解的子集，避免完全枚举，从而高效找到最优整数解。 第二步：核心思想与流程框架 松弛问题 ：先求解整数规划的线性松弛问题（忽略整数约束）。若松弛解满足整数要求，则该解即为原问题最优解；否则，记录其目标值作为当前下界（最小化问题）或上界（最大化问题）。 分支 ：选择一个非整数变量 \(x_ j\)，生成两个子问题： 子问题1：添加约束 \(x_ j \leq \lfloor x_ j^* \rfloor\) 子问题2：添加约束 \(x_ j \geq \lceil x_ j^* \rceil\) 其中 \(x_ j^* \) 是当前非整数解。分支将可行域划分为更小部分，且不丢失任何整数可行解。 定界 ：对每个子问题求解松弛问题，更新全局界： 最小化问题：松弛解值作为子问题的下界，全局上界为当前最好整数解的目标值。 最大化问题：松弛解值作为子问题的上界，全局下界为当前最好整数解的目标值。 剪枝 ：若子问题满足以下条件之一，则停止进一步分支： 松弛问题无可行解； 松弛解值劣于当前全局界（不可能得到更优整数解）； 松弛解为整数解，更新当前最好解及全局界。 第三步：关键技术与细节 变量选择策略 ：分支变量可优先选择： 分数部分最接近0.5的变量（如 \(x_ j^ =3.2\) 的分数部分为0.2，\(x_ k^ =4.7\) 的分数部分为0.7，后者更可能产生明显变化）； 对目标函数影响最大的变量（基于减少成本或灵敏度分析）。 节点选择策略 ： 深度优先：快速找到整数解，便于早期剪枝； 最佳界优先：优先处理有最乐观界的节点，可能减少总节点数。 预处理 ：添加约束收紧可行域（如系数约化、逻辑不等式），提升松弛问题的质量。 第四步：算法收敛性与复杂度 分支定界法理论上必在有限步内找到最优解（整数解数量有限），但最坏情况下仍需枚举所有节点，是指数级复杂度。 实际效率高度依赖问题结构：松弛问题提供的界越紧，剪枝越早，计算量越小。 第五步：应用场景与扩展 典型应用：旅行商问题、资源分配、调度问题等组合优化场景。 扩展方法：结合割平面法（如分支切割法）、启发式规则（初始解生成）加速求解。现代求解器（如CPLEX、Gurobi）均内置高度优化的分支定界框架。