1、分支定界法分支定界法LT本文主要讨论的整数线性规划问题模型为：其中2求解整数线性规划的算法分支定界法2.1求整数最优解问题的提出对于整数规划的一个数学问题,把它的整数约束条件改为非负约束,得到一个普通线性规划问题,这个过程叫做从原问题ILP得到它的一个松弛问题LP,说它是“松弛”的,是因为从整数变为实数,条件放宽了许多。ILP： LP： 其中给定一个整数规划的数字题,一个直观的求解思路是先做出它的松弛问题。如果松弛问题的最优解中每一个整变量(即分量)的值都满足各自的整数约束,原问题得到解决。如果松弛问题的最优解中,某个变量的值不是整数,问题就很难解决。实践表明,求解整数规划是一个很困难的工作。
2、随着计算机技术的迅猛发展,数学运算软件得到了广泛的使用,如:matlab,mathematica,maple等。计算机已经成为应用数学软件求解问题的主要运算工具。2.2分支定界法分支定界算法是20世纪60年代初由Land和Doig提出，并由Dakin修正，可用于求解纯整数或混合整数线性规划问题。对于一个纯整数规划ILP问题,求解它的一个基本思路是分支定界法,正如它的名字那样,主要由“分支”和“定界”组成。首先讨论LP与ILP解的相关问题：“LP的解”。可能有以下3种情况:(1)LP没有可行解,这时ILP也没有可行解,则停止；(2)LP有最优解,并且解变量都是整数,因而它也是ILP的最优解,则停
3、止;(3)LP有最优解,但不符合ILP中的整数条件,此时记它的目标函数值为,这时若记为ILP的最优目标函数值,则必有其次,给出算法的步骤:第一步分支:在LP的最优解中任选一个不符合整数条件的变量,设其值为,是不超过的最大整数。构造两个约束条件:和+1,将两个条件分别加入其松弛问题LP,将LP分成两个后继问题LP1和LP2。不考虑整数条件要求,求解LP1和LP2。根据需要各后继问题可用类似的方法进行分支,如此不断继续,直到获得整数规划的最优解,这就是所谓的“分支”。第二步定界:以每个后继子问题为一分支并标明求解的结果,与其他问题的解的结果一道,找出最优目标函数值最小者作为新的下界,替换,从已符合
4、整数条件的各分支中,找出目标函数值为最小者作为新的上界,即有。第三步比较与剪支:各分支的最优目标函数中若有大于者,则剪掉这一支;若小于,且不符合整数条件,则重复第一步骤,一直到最后得到最优目标函数值为止,从而得最优整数解“分支”为整数规划最优解的出现创造了条件,而“定界”则可以提高搜索的效率。经验表明:在可能的情况下根据对实际问题的了解,实现选择一个合理的“界限”,可以提高分支定界法的搜索效率2.3实例例1 求解下列整数规划解：设原整数规划问题为 ILP, 其松弛问题为LP： 求解线性规划问题LP得:按条件和将问题LP分解成子问题LP1和LP2并赋它们下界为14.2求线性规划子问题LP1得：；
5、求线性规划子问题LP得：；因中，因此以条件和将LP2分成两个子问题LP3和LP4并赋它们下界为14.33求线性规划子问题LP3得：；求线性规划子问题LP4得：；因和是原整数规划问题的可行解且，所以令为上界。再将LP1分支，因中，因此以条件和将LP1分成两个子问题LP5和LP6并赋它们下界为14.33求线性规划子问题LP5得：；求线性规划子问题LP6得：；由于，,所以LP5和LP6都没有继续分支求解的必要,至此求得最优解为，,最优目标函数值为。3matlab 程序实现下面给出整数线性规划分支定界法的matlab程序 ILp1.m.function x,y=ILp1(f,G,h,Geq,heq,l
6、b,ub,x,id,options)global upper opt c x0 A b Aeq beq ID options;if nargin10,options=optimset();options.Display=off;options.LargeScale=off;endif nargin9,id=ones(size(f);endif nargin8,x=;endif nargin7 lisempty(ub),ub=inf*ones(size(f);endif nargin6 lisempty(lb),lb=zeros(size(f);endif nargin5,heq=;endif
7、nargin4,Geq=;endupper=inf;c=f;x0=x;A=G;b=h;Aeq=Geq;beq=heq;ID=id;ftemp=ILP(lb(:),ub(:);x=opt;y=upper;%下面是子函数function ftemp=ILP(vlb,vub)global upper opt c x0 A b Aeq beq ID options;x,ftemp,how=linprog(c,A,b,Aeq,beq,vlb,vub,x0,options);if how0.00005 %in order to avoid errorreturn;end;if max(abs(x*ID-r
8、ound(x*ID)0.00005 %in order to avoid error opt=x;upper=ftemp; return;elseopt=opt;x;return;end;end;notintx=find(abs(x- round(x)=0.00005); %in order to avoid er-rorintx=fix(x);tempvlb=vlb;tempvub=vub;if vub(notintx(1,1),1)=intx(notintx(1,1),1)+1;tempvlb(notintx(1,1),1)=intx(notintx(1,1),1)+1;ftemp=ILP
9、(tempvlb,vub);end;if vlb(notintx(1,1),1)=intx(notintx(1,1),1)tempvub(notintx(1,1),1)=intx(notintx(1,1),1);ftemp=ILP(vlb,tempvub);end;对例1的matlab实现c=7,3,4;a=-1,-2,-3;-3,-1,-1;b=-8;-5;x,z=ILp1(c,a,b,0;0;0,inf;inf;inf)输出结果x = 0 5.0000 0z = 15.0000这与之前讨论的结果一致，说明该算法的正确性。4总结虽然对于用分支定界法解决整数规则等问题在运筹学里有一套完整的理论,但将它用计算机来实现还是有一定的难度。本文正是在这个方面作了一些探讨,主要介绍了求解整数线性规划问题的分支定界法及其算法的matlb实现，并以实例验证了该算法的正确性。参考文献1王开荣.最优化方法M.北京:科学版社,2012.219-2222李胜华.分支与定界算法的实现研究J.内江师范学院学报,2003,18(2):21-23 3潘君.整数规划的分支定界法及其 MATLAB 实现J.科技信息,2008（07）:167-1684施光燕,董加礼.最优化方法.北京: 高等教育出版社,1999-09 5郭志军，分支定界算法的 MATLAB 实现J.职业圈，2007（20）:139-140
