词条 | 分枝限界法 |
释义 | fenzhi xianjiefa 分枝限界法(卷名:自动控制与系统工程) branch and bound method 一种求解离散最优化问题的计算分析方法,又称分枝定界法。它是由R.J.达金和兰德-多伊格在20世纪60年代初提出的。这种方法通常仅需计算和分析部分允许解,即可求得最优解。因此在求解分派问题和整数规划问题时常用此法。 基本方法 求解一个约束条件较多的问题A,可以暂缓考虑部分条件,变换成问题B,先求B的最优解。B的最优解一定比 A的好(或相当)。再将原来暂缓考虑的部分条件逐步插入问题B中,得到B的若干子问题,称为分枝。求解这些子问题,淘汰较差的解,直到所有暂缓考虑的部分条件全部插入为止。这时求得的最优解就是问题A的最优解。 分派问题 ![]() 首先分析在所有分派方案中,以何种分派方案的费用为最低。由表可知,当分派方案是(I-D)(即任务I交由D设备去完成时,下同),(Ⅱ-A),(Ⅲ-C),(Ⅳ-D)时,即得总费用 ![]() ![]() ![]() ![]() ![]() 参考书目 李德等编:《运筹学》,清华大学出版社,北京,1982。 |
随便看 |
百科全书收录78206条中英文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。