分支定界法（Branch and Bound Method
一、分支定界法概述
1. 定义与定位
分支定界法是求解 整数规划问题（纯整数、混合整数、0-1规划）的 核心全局优化算法，由 Land 和 Doig 于1960年提出。
其核心思想是通过“分支”（将可行域分解为子区域）和“定界”（确定最优解的上下边界），逐步排除非最优子区域（剪枝），最终找到整数最优解，避免穷举法的低效性。
2. 适用范围
- 纯整数规划：所有决策变量均需为整数；
- 混合整数规划：部分决策变量为整数，其余为连续变量；
- 0-1规划：决策变量仅取 $0$ 或 $1$（可视为纯整数规划的特例，分支定界法可处理，但匈牙利法更高效）。
二、核心原理：分支、定界与剪枝
1. 三大核心逻辑
| 逻辑模块 | 核心目标 | 具体操作 |
|---|---|---|
| 分支（Branch） | 缩小可行域 | 选取非整数解的变量，添加“上界/下界”约束，将原问题分解为两个互斥的子问题（子问题可行域无交集，且并集为原问题可行域的子集） |
| 定界（Bound） | 确定最优解范围 | - 上界（UB）：所有未剪枝子问题的松弛解目标值的最大值（初始上界为原问题松弛解的目标值）； - 下界（LB）：已找到的整数解目标值的最大值（初始下界为 $-\infty$，找到第一个整数解后更新） |
| 剪枝（Prune） | 排除非最优子区域 | 若某子问题的松弛解目标值 $\leq$ 当前下界（或子问题无解），则该子问题无可能包含最优解，直接舍弃（剪枝），无需进一步分支 |
三、完整求解步骤（含剪枝逻辑）
分支定界法的求解过程是 迭代循环，直至所有子问题被“剪枝”或找到整数最优解。
-
步骤1：求解松弛问题
去掉整数约束，求解对应的线性规划（松弛问题），得到松弛解 $x^$ 和目标值 $z^$。 -
步骤2：判断松弛解性质
- 若松弛问题 无解：原整数规划无解，终止计算；
- 若松弛解 $x^$ 满足整数约束：该解即为整数最优解（因松弛解是整数规划的上界，此时 $UB=LB=z^$），终止计算；
- 若松弛解 $x^$ 不满足整数约束：进入“分支”步骤，同时将 $z^$ 设为初始上界（UB）。
-
步骤3：分支操作
选取一个 非整数变量 $x_i$，添加两个互斥约束：- 子问题1：
\(x_i \leq \lfloor x_i^* \rfloor\) - 子问题2：
\(x_i \geq \lceil x_i^* \rceil\)
- 子问题1：
-
步骤4：定界与剪枝
分别求解两个子问题的松弛解，判断：-
若子问题 无解：剪枝；
-
若子问题松弛解目标值 $\leq LB$：剪枝；
-
若子问题松弛解目标值 $> LB$：
- 若松弛解满足整数约束：更新 $LB=\max(LB, z)$，剪枝；
- 若松弛解不满足整数约束：保留，继续分支。
-
-
步骤5：重复迭代
对未剪枝的子问题，继续执行步骤3–4，直至所有子问题被剪枝。最终 $LB$ 对应的整数解即为最优解。
四、经典案例演示
1. 问题条件
目标函数：
\(\max z = 3x_1 + x_2\)
约束条件：
\(2x_1 + 3x_2 \leq 14\)
\(2x_1 + x_2 \leq 24\)
\(x_1, x_2 \geq 0,\quad x_1,x_2 \in \mathbb{Z}\)
2. 求解过程
（1）初始松弛问题
最优解 $(x_1=3.25, x_2=2.5)$，$z^*=14.75$（非整数）。
边界：$UB=14.75, \ LB=-\infty$。
（2）第一次分支（以 $x_1=3.25$ 分支）
- 子问题1（$x_1 \leq 3$）：解 $(3,2.67)$，$z=10.3$（非整数，保留）；
- 子问题2（$x_1 \geq 4$）：解 $(4,1)$，$z=14$（整数，更新 $LB=14$）。
此时：$UB=10.3,\ LB=14$。
（3）第二次分支（对子问题1分支，$x_2=2.67$）
- 子问题1-1（$x_2 \leq 2$）：$z=13 < LB$，剪枝；
- 子问题1-2（$x_2 \geq 3$）：$z=13.5 < LB$，剪枝。
（4）终止
所有子问题均剪枝，最优解为 $(x_1=4, x_2=1)$，最优值 $z=14$。
五、Matlab编程实现
1. 编程前提
linprog只支持最小化问题。若目标为最大化，需转化为最小化：
\(\max z \ \Leftrightarrow\ \min (-z)\)- 自定义
branchbound.m（递归分支定界）和intprog.m（入口函数）。
五、Matlab编程实现（完整代码）
1. 编程核心前提
- Matlab的
linprog函数仅支持最小值问题，若目标函数为最大值（如\(\max z\)），需转化为\(\min (-z)\)，求解后还原符号； - 需自定义
branchbound.m（分支定界逻辑）和intprog.m（整数规划入口函数），协同实现迭代与剪枝。
2. 关键函数与参数
| 函数/参数 | 作用说明 |
|---|---|
linprog(f,A,B,Aeq,Beq,lb,ub,options) |
求解线性规划松弛问题，f为目标函数向量，A,B为不等式约束（\(Ax \leq B\)） |
optimset() |
设置优化参数，如'Display','off'（不显示迭代过程）、'MaxIter',1000（最大迭代步数） |
| 误差阈值（如\(1e-5\)） | 判断变量是否为整数：若$ |
整数约束向量I |
标记整数变量（如I=[1,2]表示\(x_1,x_2\)为整数） |
3. 完整代码示例（求解\(\max z=20x_1+10x_2\)）
（1）问题转化
- 目标函数转化：\(\min z' = -20x_1 -10x_2\)（对应
f=[-20,-10]）； - 约束：\(5x_1+4x_2 \leq24\)、\(2x_1+5x_2 \leq13\)（对应
A=[5 4;2 5]，B=[24;13]）； - 变量边界：\(x_1,x_2 \geq0\)（
lb=[0;0]，ub=[inf;inf]）。
（2）intprog.m（入口函数）
function [x, fval, status] = intprog(f, A, B, I, Aeq, Beq, lb, ub, e)% 输入参数：% f: 目标函数向量（最小值），A,B: 不等式约束Ax<=B，I: 整数变量索引% Aeq,Beq: 等式约束Aeqx=Beq，lb,ub: 变量上下界，e: 整数判断误差阈值% 输出参数：x: 最优整数解，fval: 最优目标值，status: 求解状态% 参数默认值设置if nargin < 4, I = [1:length(f)]; end % 默认所有变量为整数if nargin < 5, Aeq = []; Beq = []; end % 默认无等式约束if nargin < 6, Beq = []; endif nargin < 7, lb = zeros(length(f), 1); end % 默认下界为0if nargin < 8, ub = inf(length(f), 1); end % 默认上界为infif nargin < 9, e = 1e-5; end % 默认误差阈值1e-5% 求解初始松弛问题options = optimset('Display', 'off'); % 不显示迭代过程[x0, fval0, exitflag] = linprog(f, A, B, Aeq, Beq, lb, ub, [], options);% 判断松弛问题是否有解if exitflag < 0disp('整数规划无可行解');x = x0;fval = fval0;status = exitflag;return;end% 调用分支定界函数求解bound = inf; % 初始上界（最小值问题，上界为inf）[x, fval, status] = branchbound(f, A, B, I, x0, fval0, bound, Aeq, Beq, lb, ub, e);% 若为最大值问题，还原目标值符号（此处f已转化为最小值，故无需额外处理）
end
（3）branchbound.m（分支定界逻辑）
function [x, fval, status] = branchbound(f, A, B, I, x0, fval0, bound, Aeq, Beq, lb, ub, e)% 递归实现分支定界逻辑x = [];fval = bound;status = 0;% 1. 判断当前松弛解是否为整数解is_integer = true;for i = Iif abs(x0(i) - round(x0(i))) > e % 非整数变量is_integer = false;break;endend% 2. 若为整数解，更新最优解if is_integerx = x0;fval = fval0;status = 1;return;end% 3. 若松弛解目标值≥当前上界，剪枝（最小值问题，更大的目标值无意义）if fval0 >= bound - estatus = -1;return;end% 4. 选择分支变量（此处选第一个非整数变量，可优化为“目标系数最大”策略）branch_var = -1;for i = Iif abs(x0(i) - round(x0(i))) > ebranch_var = i;break;endend% 5. 构造两个子问题的约束（添加分支变量的上下界）xi = x0(branch_var);floor_xi = floor(xi); % 向下取整ceil_xi = ceil(xi); % 向上取整% 子问题1：x(branch_var) ≤ floor_xiA1 = [A; zeros(1, length(f))];A1(end, branch_var) = 1;B1 = [B; floor_xi];[x1, fval1, status1] = linprog(f, A1, B1, Aeq, Beq, lb, ub, [], optimset('Display','off'));% 子问题2：x(branch_var) ≥ ceil_xiA2 = [A; zeros(1, length(f))];A2(end, branch_var) = -1; % 转化为 -x ≤ -ceil_xi → x ≥ ceil_xiB2 = [B; -ceil_xi];[x2, fval2, status2] = linprog(f, A2, B2, Aeq, Beq, lb, ub, [], optimset('Display','off'));% 6. 递归求解子问题1if status1 >= 0[x1_int, fval1_int, status1_int] = branchbound(f, A1, B1, I, x1, fval1, min(bound, fval), Aeq, Beq, lb, ub, e);if status1_int == 1 && fval1_int < fvalfval = fval1_int;x = x1_int;status = 1;endend% 7. 递归求解子问题2if status2 >= 0[x2_int, fval2_int, status2_int] = branchbound(f, A2, B2, I, x2, fval2, min(bound, fval), Aeq, Beq, lb, ub, e);if status2_int == 1 && fval2_int < fvalfval = fval2_int;x = x2_int;status = 1;endend
end
（4）测试脚本（test.m）
% 测试：max z=20x1+10x2，约束5x1+4x2≤24，2x1+5x2≤13，x1,x2≥0且为整数
f = [-20, -10]; % 转化为min(-z)
A = [5 4; 2 5];
B = [24; 13];
I = [1, 2]; % x1,x2为整数
lb = [0; 0];
ub = [inf; inf];[x, fval, status] = intprog(f, A, B, I, [], [], lb, ub);% 输出结果（还原最大值目标值）
disp('最优整数解：');
disp(x);
disp('最优目标值（max z）：');
disp(-fval); % 因f为-min(z)，故还原为-z
（5）运行结果
最优整数解：41
最优目标值（max z）：90
六、关键补充知识点
1. 分支变量选择策略
| 策略名称 | 逻辑 | 适用场景 | ||
|---|---|---|---|---|
| 目标系数优先策略 | 选择目标函数系数绝对值最大的非整数变量 | 收敛快 | ||
| 离整数最远策略 | 选择 $ | x_i^* - \lfloor x_i^* \rfloor | $ 最大者 | 快速缩小可行域 | ||
| 字典序策略 | 选择下标最小的非整数变量 | 简单易实现 |
2. 算法优缺点
- 优点：全局最优；比穷举高效；适用范围广。
- 缺点：大规模问题效率低；依赖松弛解质量；剪枝不一定高效。
3. 与其他算法对比
| 算法 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| 分支定界法 | 全局最优；适用面广 | 大规模耗时 | 通用整数规划 |
| 割平面法 | 不需分支 | 约束增多 | 中小规模纯整数 |
| 匈牙利法 | 多项式时间 | 仅限0-1指派 | 任务分配 |
| 穷举法 | 简单直观 | 指数复杂度 | 变量极少 |
4. 应用场景
- 生产计划（产品数量）
- 物流调度（车辆数）
- 资源分配（整数金额）
- 选址问题（0-1决策）
七、常见问题与注意事项
- 浮点误差：需设阈值（如 $10^{-5}$）判断整数性。
- 无限循环：设置
MaxIter、MaxFunEvals防止卡死。 - 混合整数规划：仅对整数变量分支。
- 等式约束：分支不改变等式约束。
八、总结
分支定界法是整数规划的 通用全局优化算法，通过
- 分支（划分可行域）、
- 定界（上下界控制）、
- 剪枝（排除劣解），
保证全局最优解。实际应用中，合理的 分支变量选择 与 剪枝策略 能显著提升求解效率。