什么是分枝限界法?

[拼音]：fenzhi xianjiefa

[外文]：branch and bound method

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

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

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

首先分析在所有分派方案中，以何种分派方案的费用为最低。由表可知，当分派方案是(I-D)（即任务I交由D设备去完成时，下同）,(Ⅱ-A)，(Ⅲ-C)，(Ⅳ-D)时，即得总费用

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

该方案恰好满足一台设备完成一项任务的规定，因此总费用193的解称为允许解。依次计算(I-B),(I-C),(I-D)各分派方案的解,如图1所示。分析1～4的分派方案后可知,要求的最优解一定在164和148之间，即上界是164，下界是148。这时,只要在方案4这个分枝上继续进行组合即可。用同样计算方法得图2所示的分派方案。由分派方案5～7可知，方案5的总费用为156，但是非允许解，方案6的总费用是157，是允许解。所以方案6是最优解。其具体分派组合是:(I-D),(Ⅱ-B),(Ⅲ-C)，(Ⅳ-A)。上述计算过程可归纳如图3所示。

参考书目

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