由网友(易生峰狂只为李)分享简介：1种求解失散最劣化答题的计较阐发要领，又称分枝定界法。即求解子答题，裁减较好的解，直到任何暂慢思量的部门前提全数拔出为止。这时候求患上的最劣解便是答题A的最劣解。外文名branch and bound method范畴私路接通观点简介branch and bound method分支边界法1种求解失散最劣化答题的计较阐发方...

一种求解离散最优化问题的计算分析方法，又称分枝定界法。即求解子问题，淘汰较差的解，直到所有暂缓考虑的部分条件全部插入为止。这时求得的最优解就是问题A的最优解。

外文名

branch and bound method

领域

公路交通

概念简介

branch and bound method

分支界限法

一种求解离散最优化问题的计算分析方法，又称分枝定界法。它是由R.J.达金和兰德－多伊格在20世纪60年代初提出的。这种方法通常仅需计算和分析部分允许解，即可求得最优解。因此在求解分派问题和整数规划问题时常用此法。

基本方法

求解一个约束条件较多的问题A,可以暂缓考虑部分条件，变换成问题B,先求B的最优解。B的最优解一定比A的好（或相当）。再将原来暂缓考虑的部分条件逐步插入问题B中，得到B的若干子问题，称为分枝。求解这些子问题，淘汰较差的解，直到所有暂缓考虑的部分条件全部插入为止。这时求得的最优解就是问题A的最优解。

最常见的两种方式

1).队列式（FIFO）分支限界法：将活结点表组织成一个队列，并按队列的先进先出原则选取下一个结点作为当前扩展结点。

2).优先队列式分支限界法：将活结点表组织成一个优先队列，并按优先队列给结点规定的优先级选取优先级最高的下一个结点作为当前扩展结点。队列式分支限界法的搜索解空间树的方式类似于解空间树的宽 度优先搜索，不同的是队列式分支限界法不搜索以不可行结点（已经 被判定不能导致可行解或不能导致最优解的结点）为根的子树。这是因为，按照规则，这样的结点未被列入活结点表。优先队列式分支限界法的搜索方式是根据活结点的优先级确定 下一个扩展结点。结点的优先级常用一个与该结点有关的数值p 来表示。最大优先队列规定p 值较大的结点点的优先级较高。在算法实现时通常用一个最大堆来实现最大优先队列，用最大堆的Deletemax 运算抽取堆中的下一个结点作为当前扩展结点，体现最大效益优先的原则。类似地，最小优先队列规定p 值较小的结点的优先级较高。在算法实现时，常用一个最小堆来实现，用最小堆的Deletemin 运算抽取堆中下一个结点作为当前扩展结点，体现最小优先的原则。采用优先队列式分支定界算法解决具体问题时，应根据问题的特点选用最大优先或最小优先队列，确定各个结点点的p 值。

分派问题

分枝限界法

设生产任务Ⅰ、Ⅱ、Ⅲ和Ⅳ,皆可在4台不同设备A、B、C和D上去完成。由于设备性能和技术要求等不同，在不同设备上完成各项任务所需的费用（或时间）均不相同，下表列出某一具体问题的任务、设备和费用的数量关系。规定每台设备只能安排一项生产任务。要求分派这4项生产任务，使总费用为最少。

首先分析在所有分派方案中，以何种分派方案的费用为最低。由表可知，当分派方案是

（即任务I交由D设备去完成时，下同）,

时，即得总费用

为最小。它称为下界。但这样的分派方案要由D设备去完成Ⅰ、Ⅳ两项任务，不符合题意要求。所以称这个解为非允许解。为此必须加以改进。接着，规定任务Ⅰ交由A去完成，其他任务则选择费用最小的设备去完成，则由表可知，其总费用为

该方案恰好满足一台设备完成一项任务的规定，因此总费用193的解称为允许解。依次计算

各分派方案的解，如图1所示。

分析1～4的分派方案后可知，要求的最优解一定在164和148之间，即上界是164，下界是148。这时，只要在方案4这个分枝上继续进行组合即可。

用同样计算方法得图2所示的分派方案。由分派方案5～7可知，方案5的总费用为156，但是非允许解，方案6的总费用是157，是允许解。

所以方案6是最优解。其具体分派组合是:

。上述计算过程可归纳如图3所示。

分枝限界法

分枝限界法

分枝限界法

参考书目

李德等编：《运筹学》，清华大学出版社，北京,1982。