说明:双击或选中下面任意单词,将显示该词的音标、读音、翻译等;选中中文或多个词,将显示翻译。
您的位置:首页 -> 词典 -> 分枝限界算法
1)  Branch Limitation algorithm
分枝限界算法
2)  multi-branch-and-bound algorithm
分枝-限界算法
3)  parallel Branch_and_Bound algorithm
并行分枝限界算法
4)  branch-bound method
分枝限界法
1.
On the basis of the branch-bound method, a computing program is developed.
以平面桁架为例将结构连续变更定理用于结构的可靠性分析,以分枝限界法为基础编制了电算程序。
2.
On the basis of the branch-bound method,the computing programm is composed.
本文以桁架为例首次将结构连续变更原理用于结构的可靠性分析,并以分枝限界法为基础编制了电算程序,从而有效地筛选出结构可能失效模式的集合。
5)  delimited divarication algorithm
限界分枝法
6)  ch-and-bound technique
分枝和限界法
补充资料:分枝限界法
      一种求解离散最优化问题的计算分析方法,又称分枝定界法。它是由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。
  

说明:补充资料仅用于学习参考,请勿用于其它任何用途。
参考词条