分支定界法PPT演示课件

1、精品课程运筹学精品课程运筹学3.1 分枝定界法的基本思想分枝定界法的基本思想 考虑纯整数线性规划问题考虑纯整数线性规划问题 )(p00 xp的的最最优优解解不不满满足足整整数数要要求求0ix0iixx 10 iixx为为整整数数向向量量xxbaxtsxct0.min , 0.min0iitxxxxbaxtsxc 为为整整数数向向量量1, 0.min0 iitxxxxbaxtsxc为为整整数数向向量量精品课程运筹学)(p)(1p)(2p)(3p)(4p)(5p)(6p0iixx 10 iixx2kkxx 12 kkxx3llxx 13 llxx分分 枝枝 树树分分 枝枝 过过 程程分枝过程在某个

2、点上由下述两个原因之一而停止：分枝过程在某个点上由下述两个原因之一而停止： 相应的松弛相应的松弛lp问题的解是满足整数要求的；问题的解是满足整数要求的； 相应松弛相应松弛lp问题是不可行的问题是不可行的 .精品课程运筹学定界过程定界过程假假设设在在某某一一时时刻刻，到到当当时时为为止止所所得得到到的的最最好好的的满满足足整整数数要要求求解解的的目目标标函函数数值值是是mz，而而且且我我们们正正打打算算由由某某一一点点kx分分枝枝， 该该点点子子域域对对应应的的 ilp 的的下下界界为为ktkxcz ，若若mkzz ，这这意意味味着着点点kx的的所所有有后后代代得得到到的的各各个个解解x的的目目

3、标标函函数数值值均均有有 mktzzxc 因因此此无无须须由由kx继继续续分分枝枝. 死点死点被剪枝被剪枝精品课程运筹学3.2 分枝定界法计算步骤分枝定界法计算步骤 例例3.3.13.3.1 用分枝定界法求解整数线性规划用分枝定界法求解整数线性规划 ，整整数数0,121124124.)(min212212121xxxxxxxtsxx精品课程运筹学 01x2x )(min21xx )(p)(1p)(2p11 x21 x4,)25,23(00 zxt精品课程运筹学)(p)(1p)(2p11 x21 x4,)25,23(00 zxt 01x2x )(1p问问题题)(2p问问题题1x2x12 x22

4、xtxz)23, 1(,2511 27,)23, 2(22 zxt)(3p)(4p精品课程运筹学)(p)(1p)(2p11 x21 x4,)25,23(00 zxt)(3p)(4p12 x22 xtxz)23, 1(,2511 27,)23, 2(22 zxt 01x2x)(3p问问题题22 x)(4p问问题题)(5p)(6p21 x31 x无解无解txz)1 ,25. 2(,25. 333 精品课程运筹学无解无解txz)1 , 2(, 355 01x2x)(5p问问题题31 x)(6p问问题题)(p)(1p)(2p11 x21 x4,)25,23(00 zxt)(3p)(4p12 x22 x

5、txz)23, 1(,2511 27,)23, 2(22 zxt)(5p)(6p21 x31 x无解无解txz)1 ,25. 2(,25. 333 最优解最优解精品课程运筹学第第1步步 第第2步步 解整数线性规划问题的分枝定界法步骤：解整数线性规划问题的分枝定界法步骤： 令令活活点点集集合合： o （注注： “o”代代表表原原问问题题，下下面面的的正正整整数数“k”代代表表子子问问题题)(kp） ，上上界界 ：u，当当前前最最好好的的整整数数解解： ； 若活点集合若活点集合 ，则转向第，则转向第 7 步，否则，选择步，否则，选择一个分枝点一个分枝点 k活点集合，从活点集合中去掉点活点集合，从活

6、点集合中去掉点 k； 第第3步步 解解点点k对对应应的的松松弛弛 lp 问问题题，若若此此问问题题无无解解，转转回回第第 2 步步； 精品课程运筹学第第4步步 第第5步步 第第6步步 若点若点k对应的松弛对应的松弛 lp 问题的最优值问题的最优值uzk ，则点则点k被剪枝，转回第被剪枝，转回第 2 步；步； 若若点点k对对应应的的松松弛弛 lp 问问题题的的最最优优解解kx满满足足整整数数要要求求（此此时时一一定定有有uzk ） ，则则上上界界kzu ：，当当前前最最好好的的整整数数解解：kx ，转转回回第第 2 步步； 若若点点k对对应应的的松松弛弛 lp 问问题题的的最最优优解解kx不不满满足足整整数数要要求求，按按kx某某个个非非整整数数分分量量生生成成点点 k的的两两个个后后代代点点， 令令这这两两个个后后代代点点为为活活点点， 并并加加入入到到活活点点集集合合中中， 转回第转回第2步；步； 精品课程运筹学第第7步步若当前最好的整数解：