《分支定界法》ppt课件

《《分支定界法》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章　整数规划运筹帷幄，决胜千里史记《张良传》Linearprogramming5.2分支定界解法检查可行的整数组合的一部分，就能定出最优的整数解。可用于解纯整数或混合的整数规划问题由于灵活且便于用计算机求解，所以此法已成为求解整数规划的重要方法。设有最大化的整数规划问题A，相应的线性规划为问题B。步骤：求解问题B，得到最优解，如果不是A的解，则求得的解作为最优目标函数z*的上界取A的任意可行解的目标函数值作为z*的下界逐步减小和增大，最终求得z*例2求解Amaxz=40x1+90x2s.t

2、.9x1+7x2567x1+20x270x10，x20x1，x2都是整数解：不考虑整数要求，求解B,得到最优解：x1=4.81x2=1.82z0=3560z*356开始分支：在B中得到x1=4.81，分区域：x14x15分成两个区域，得到两个问题B1和B2：maxz=40x1+90x2s.t.9x1+7x2567x1+20x270x10，x20x14maxz=40x1+90x2s.t.9x1+7x2567x1+20x270x10，x20x15B1：B2：得到解

3、：问题B1问题B2Z1=349Z2=341x1=4.00x1=5.00x2=2.10x2=1.57因为z1>z2,所以改为349，0z*349开始分解B1(按照x2)，得到B3,B4:maxz=40x1+90x2s.t.9x1+7x2567x1+20x270x10，x20x14x22maxz=40x1+90x2s.t.9x1+7x2567x1+20x270x10，x20x14x23B3：B4：问题B3问题B4Z1=340Z2=327x1=4.00x1=1.42x2=2

4、.00x2=3.00分析得到：340z*341。对B2分解为B5，B6，得到z5=308,B6无可行解。所以问题的解：x1=4.00x2=2.00z0=340总结步骤（A,B）:(1)解问题B,得到以下情况之一就停止：B没有可行解，这是A也没有可行解B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解。B有最优解，但不符合问题A的整数条件，（2）用观察法找到A的一个整数可行解，一般可取xj=0,j=1,…,n,试探求得其目标函数值，并记作，得到z*进行迭代分枝，在B的最优解中任选

5、一个不符合整数条件的变量xj，其值为bj,以[bj]构成两个约束条件：xj[bj]和xj[bj]+1定界，以每个后继问题为一分支表明求解的结果，比较得到新的上界。从已符合条件的分支中，得到最大的作为下界比较与剪枝，对于<，则剪掉这支。若>，且不符合整数条件的，则重复第一步骤。12