分支定界法

精品课程《运筹学》第三节分枝定界法§3.1分枝定界法的基本思想§3.2分枝定界法计算步骤精品课程《运筹学》§3.1分枝定界法的基本思想考虑纯整数线性规划问题)(P00xP的最优解不满足整数要求0ix][0iixx1][0iixx为整数向量xxbAxtsxcT0..min][,0..min0iiTxxxxbAxtsxc为整数向量1][,0..min0iiTxxxxbAxtsxc为整数向量精品课程《运筹学》)(P)(1P)(2P)(3P)(4P)(5P)(6P][0iixx1][0iixx][2kkxx1][2kkxx][3llxx1][3llxx分枝树分枝过程分枝过程在某个点上由下述两个原因之一而停止：⑴相应的松弛LP问题的解是满足整数要求的；⑵相应松弛LP问题是不可行的.精品课程《运筹学》定界过程假设在某一时刻，到当时为止所得到的最好的满足整数要求解的目标函数值是mz，而且我们正打算由某一点kx分枝，该点子域对应的ILP的下界为kTkxcz，若mkzz，这意味着点kx的所有后代得到的各个解x的目标函数值均有mkTzzxc因此无须由kx继续分枝.死点被剪枝精品课程《运筹学》§3.2分枝定界法计算步骤例3.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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xTxz)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活点集合，从活点集合中去掉点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步若当前最好的整数解：，U，则原ILP问题无解，否则，当前最好的整数解就是原ILP问题的最优解，U就是最优值.计算停止.