《ERP高级计划》书的解读―APS算法分析之三分枝界定法（B&B）（一）（蔡颖）

分枝和界定法（Branch and Bound）：

它主要是对混合整数线性规划MILP的解决方法 ，分枝定界可以在一个决策树里描述，使用确定性搜索方法可以避免整个枚举 ，使得原始问题可以被分为较小的子问题

分枝: 选择那些所有原先已被分析的子问题

界定: 对目标函数的上下限的界定指明后续的子问题是否可以导致一个较好的可行方案。 

重要注明:一个较好的界定决策=> 分枝也许被尽早的折断 。

分枝和界定法B&B 是一个特殊列举算法. 和这个列举的不同是只有有限的子问题的数量必需解决。 分枝和界定法 B&B 的算法工作就像一个分配和战胜策略。首先，整数问题的线性松弛被解决。如果方案是整数的，那么它也是优化的方案。否则，两个新的子问题在一分数变量上分枝所创立。此过程是重复的，直到没有进一步的子问题被创立或所有方案是整数的或不可行的。

Dakin‘s 分枝和界定法B&B 算法:

1.      整数问题的线性松弛

2.      分枝

3.      定界

4.      优化测试

第一步: 线性松弛 (如, 用单一法)

－没有可行方案 => MILP 没有可行方案 => 结束

－最佳整数方案 => 结束

－最佳, 非整数方案 => 到第二步
线性规划LP松散的目标函数是上界分枝，是对MILP的目标函数值来说，较低界定是 “－00”

第二步: 分枝

?         非整数变量 X的分枝, 用 g < X < g+1 和 g 作为整数.所有方案集被分为两个子集:

*         (a) 方案 X ≤ g

*         (b) 方案 X≥ g+1

?         剩余的其它约束没有改变.

第三步: 界定

?         第二步的两个子问题已被解决. 两个问题的目标函数值是子集的上界。如果仍然还有必需整数化的非整数变量 ，那么分枝必须 继续。但是，如果子集的界定是低于整数方案可行的目标值或子集问题是步可行的，就不必分析子集问题，

?         如果所有变量是整数的，如果有超过一可行方案的一子集问题，那么，最佳方案比较目标函数值就可以找到。

第四步 : 优化测试

?         如果所有分枝被隐含或明确指明分析算法就中断。那么，要么优化方案已经找到，要么问题不可行。

案例：

Z = X + 4 × Y => 最大!

 约束:

1:       5 ×X + 8 × Y ≤   40

2:       -2 ×X + 3 ×Y ≤   9

3:       X, Y ≥ 0 和整数 

LP 松弛 的方案 (没有整数约束)

X = 1 17/31, Y = 4 1/31

加上 Z = 17 21/31 (定界上限)

子问题5的结束：整数方案; 新界定: Z = 15
子问题6的结束: 方案的目标函数值 Z = 14 落入界定以下 Z = 15

注意: 如果有（至少一个子集）变量，没有整数，那么，一条件就需要决定那一个子问题必须分枝。在 Dakin-算法最新的界定规则通常被分配。这就意味着没有完整分析的最后一代子集就是分枝。如果子集是同步产生，那么，较高上界的界定的子集被选择。
　

(待续)

微信扫一扫实时了解行业动态

微信扫一扫分享本文给好友