分支定界法PPT学习教案

1、会计学1分支定界法分支定界法精品课程运筹学考虑纯整数线性规划问题 )(P00 xP的的最最优优解解不不满满足足整整数数要要求求0ix0iixx 10 iixx为为整整数数向向量量xxbAxtsxcT0.min , 0.min0iiTxxxxbAxtsxc 为整数向量为整数向量1, 0.min0 iiTxxxxbAxtsxc为整数向量为整数向量第1页/共12页精品课程运筹学)(P)(1P)(2P)(3P)(4P)(5P)(6P0iixx 10 iixx2kkxx 12 kkxx3llxx 13 llxx分 枝 树分 枝 过 程分枝过程在某个点上由下述两个原因之一而停止： 相应的松弛LP问题的解是

2、满足整数要求的； 相应松弛LP问题是不可行的 .第2页/共12页精品课程运筹学定界过程假设在某一时刻，到当时为止所得到的最好的满假设在某一时刻，到当时为止所得到的最好的满足整数要求解的目标函数值是足整数要求解的目标函数值是mz，而且我们正打，而且我们正打算由某一点算由某一点kx分枝， 该点子域对应的分枝， 该点子域对应的 ILP 的下界的下界为为kTkxcz ，若，若mkzz ，这意味着点，这意味着点kx的所有后的所有后代得到的各个解代得到的各个解x的目标函数值均有的目标函数值均有 mkTzzxc 因此无须由因此无须由kx继续分枝继续分枝. 死点被剪枝第3页/共12页精品课程运筹学例3.3.1

3、 用分枝定界法求解整数线性规划 ，整数，整数0,121124124.)(min212212121xxxxxxxtsxx第4页/共12页精品课程运筹学 01x2x )(min21xx )(P)(1P)(2P11 x21 x4,)25,23(00 zxT第5页/共12页精品课程运筹学)(P)(1P)(2P11 x21 x4,)25,23(00 zxT 01x2x )(1P问问题题)(2P问问题题1x2x12 x22 xTxz)23, 1(,2511 27,)23, 2(22 zxT)(3P)(4P第6页/共12页精品课程运筹学)(P)(1P)(2P11 x21 x4,)25,23(00 zxT)(

4、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 第7页/共12页精品课程运筹学无解Txz)1 , 2(, 355 01x2x)(5P问问题题31 x)(6P问问题题)(P)(1P)(2P11 x21 x4,)25,23(00 zxT)(3P)(4P12 x22 xTxz)23, 1(,2511 27,)23, 2(22 zxT)(5P)(6P21 x31 x无解Txz)1 ,25. 2(,25. 333 最优解第8页/共

5、12页精品课程运筹学第1步 第2步 解整数线性规划问题的分枝定界法步骤： 令令活活点点集集合合： O （注注： “O”代代表表原原问问题题，下下面面的的正正整整数数“k”代代表表子子问问题题)(kP） ，上上界界 ：U，当当前前最最好好的的整整数数解解： ； 若若活活点点集集合合 ，则则转转向向第第 7 步步，否否则则，选选择择一一个个分分枝枝点点 k活活点点集集合合，从从活活点点集集合合中中去去掉掉点点 k； 第3步 解解点点k对对应应的的松松弛弛 LP 问问题题，若若此此问问题题无无解解，转转回回第第 2 步步； 第9页/共12页精品课程运筹学第4步 第5步 第6步 若点若点k对应的松弛对

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