分支定界法:什么意思、基本思想、求解步骤、例子例题

2020年11月1日13:29:23分支定界法:什么意思、基本思想、求解步骤、例子例题已关闭评论

分支定界法:什么意思、基本思想、求解步骤、例子例题

分支定界法是在20世纪60年代初由Land Doig和Dakin等人提出的,由于该方法灵活,便于计算机求解,所以它是现在求解整数规划的重要方法。

它的基本思想是,先不考虑原整数规划问题中的整数性约束,去解其相应的松弛问题。对于最大化问题,松弛问题的最优值就是原问题最优值的上界。如果松弛问题的最优解满足整数性约束,则它就是原问题的最优解。

否则,就在不满足整数约束的变量中,任意选择 i,设[ ]是不超过 的最大整数,将新的约束条件 ≤[ ]和 ≥[ ]+1分别加入原问题中,把原问题分支为两个子问题,并分别求解子问题的松弛问题。

若子问题的松弛问题的最优解满足整数约束,则不再分支,其相应的目标函数值就是原问题目标函数值的一个下界。对不满足整数约束的子问题,如果需要,继续按上述方法进行新的分支,并分别求解其对应的松弛问题,直至求得原问题的最优解为止。

因此,我们总结 分支定界法的求解步骤 如下。

(1)先不考虑整数约束,求解整数规划的松弛问题,可能得到以下情况之一:

① 若松弛问题没有可行解,则整数规划也没有可行解,停止计算;

② 若松弛问题有最优解,并符合整数规划的整数条件,则线性规划的最优解即为整数规划的最优解,停止计算;

③ 若松弛问题有最优解,但不符合整数规划的整数条件,转入下一步。

(2) 分支 :从不满足整数条件的基变量中任选一个 进行分支,它必须满足 x≤[ ]或 ≥[ ]+1中的一个,把这两个约束条件加进原问题中,形成两个互不相容的子问题。

(3) 定界 :把满足整数条件各分支的最优目标函数值作为上(下)界,用它来判断分支是保留还是剪支。

(4) 剪支 :把那些子问题的最优值与界值比较,凡不优或不能更优的分支全剪掉,直到每个分支都查清为止。

例3-2-1 用分支定界法求解。

分支定界法:什么意思、基本思想、求解步骤、例子例题

(1)用单纯形法可解得相应的松弛问题的最优解(1.2,2.1), =11.1,很明显,这个最优解不符合整数条件,我们需要继续分支,并把这个最优值定为各分支的上界。

(2)选择 =1.2来进行分支,加入条件 ≤1和 ≥2,得到两个子问题。

分支定界法:什么意思、基本思想、求解步骤、例子例题

(3)用单纯形法求得 的最优解(1,2.25), =10.75, 的最优解(2,0.5), =9.5。没有得到整数解,继续分支。对 进行分支,加入条件 2≤2和 ≥3,生出两个子问题。

分支定界法:什么意思、基本思想、求解步骤、例子例题

(4)用单纯形法可解得相应的 的最优解(1,2), =10, 的最优解(0,3), =9。 和 的解都是整数,比较它们对应的目标函数值,显然 3的目标函数值大于 ,剪去 一支,把 中 =10作为目标函数的下界。

(5)我们回头看 ,在这一支中,可以继续分支以求得整数解。但这一支现在的最优值 =9.5,也就是说,不管再怎么分,在这一支中求得的目标函数值不可能超过9.5,因此,也不可能超过 中求得的 =10,因此将此支剪去。至此,我们得到了该整数规划的最优解 =1, =2, =10。

用树形图(见图3-2-1)表示求解这个问题的全过程。

分支定界法:什么意思、基本思想、求解步骤、例子例题

 

  • 版权声明:本篇文章(包括图片)来自网络,由程序自动采集,著作权(版权)归原作者所有,如有侵权联系我们删除,联系方式(QQ:452038415)。