[拼音]：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所示。

严正声明：本文由历史百科网注册或游客用户泽雨自行上传发布关于» 分枝限界法的内容，本站只提供存储，展示，不对用户发布信息内容的原创度和真实性等负责。请读者自行斟酌。同时如内容侵犯您的版权或其他权益，请留言并加以说明。站长审查之后若情况属实会及时为您删除。同时遵循 CC 4.0 BY-SA 版权协议，尊重和保护作者的劳动成果，转载请标明出处链接和本声明内容：作者：泽雨；本文链接：https://www.freedefine.cn/wenzhan/33693.html