资源描述：
《分支定界算法的MATLAB实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2007年第20期职业圈NO.20,2007(总第72期)ZHIYEQUAN(CumulativetyNO.72)分支定界算法的MATLAB实现郭志军(辽宁对外经贸学院,辽宁大连116052)【摘要】分支定界法可求纯整数或混合整数线性规划问题,(2)LP有最优解,并且解变量都是整数,因而它也是ILP的求解方法由分支和定界组成。“分支”为整数规划最优解的出现最优解,则停止;创造了条件,而“定界”则可以提高搜索的效率。用MATLAB编(3)LP有最优解,但不符合ILP中的整数条件,此时记它的写程序,通过计算机来完成这一复杂的过程。目标函数值为,这时若记为ILP的最优目标函数
2、值,则必【关键词】整数规划;分支定界法;编写程序有【中图分类号】TH164【文献标识码】A其次,给出算法的步骤:【文章编号】1671-5969(2007)20-0139-03第一步——分支:在LP的最优解中任选一个不符合整数条件的变量,设其值为,是不超过的最大整数。构造两一、求整数最优解问题的提出个约束条件:和,将两个条件分别加入其松把线性规划中的某些变量的非负约束条件改为非负整变弛问题LP,将LP分成两个后继问题LP1和LP2。不考虑整数条量,所得到的模型叫做整数线性规划(integerlinearprogramming,件要求,求解LP1和LP2。根据需要各后继问题
3、可用类似的方法简记作ILP),还简称为整数规划。如果所有变量都是整变量,叫进行分支,如此不断继续,直到获得整数规划的最优解,这就是做纯整数规划,全是{0,1}变量的,叫做{0,1}规划。否则是混合整所谓的“分支”。数规划。第二步——定界:以每个后继子问题为一分支并标明求解对于整数规划的一个数字题,把它的整数约束条件改为非的结果,与其他问题的解的结果一道,找出最优目标函数值最小负约束,得到一个普通线性规划的题目,这个过程叫做从原问题者作为新的下界,替换,从已符合整数条件的各分支中,找出ILP得到它的一个松弛问题LP,说它是“松弛”的,是因为从整数目标函数值为最小者作为新的
4、上界,即有。变为实数,条件放宽了许多。第三步——比较与剪支:各分支的最优目标函数中若有大于者,则剪掉这一支;若小于,且不符合整数条件,则重复第一步骤,一直到最后得到最优目标函数值为止,从而得最ILP:优整数解,“分支”为整数规划最优解的出现创造了条件,而“定界”则可以提高搜索的效率。经验表明:在可能的情况下根据对实际问LP:题的了解,实现选择一个合理的“界限”,可以提高分支定界法的搜索效率。下面用一个例子来说明上述过程:其中例1求解下列整数规划。给定一个整数规划的数字题,一个直观的求解思路是先做出它的松弛问题。如果松弛问题的最优解中每一个整变量(即分量)的值都满足各自的
5、整数约束,原问题得到解决。如果松弛问题的最优解中,某个变量的值不是整数,问题就很难解决。实践表明,求解整数规划是一个很困难的工作。随着计算机技术的迅猛发展,数学运算软件得到了广泛的解设原整数规划问题为ILP,其松弛问题为使用,如:matlab,mathematica,maple等。计算机已经成为应用数学软件求解问题的主要运算工具。二、求解整数规划的算法——分支定界法LP:分支定界算法是上个世纪60年代初由Land,Doig和Dakin等人提出的可用于求解纯整数或混合整数线性规划问题的算求解线性规划问题LP得:法。对于一个纯整数规划ILP问题,求解它的一个分支定界法的,的
6、基本思路,正如它的名字那样,主要由“分支”和“定界”组成。按条件和将问题LP分解成子问题LP1和首先讨论LP与ILP解的相关问题:LP2并赋它们下界为14.2.LP的解,可能有以下情况之一:(1)LP没有可行解,这时ILP也没有可行解,则停止;·求线性规划子问题LP1得:,;-139-·求线性规划子问题LP2得:,;ifnargin<6
7、isempty(lb),lb=zeros(size(f));endmin{}=;ifnargin<5,heq=[];end中1/3,因此以条件和将LP2分成两ifnargin<4,Geq=[];end个子问题LP3和LP4并赋它们下界为
8、了14.33.upper=inf;c=f;x0=x;A=G;b=h;Aeq=Geq;beq=heq;ID=id;·求线性规划子问题LP3得:,;ftemp=ILP(lb(:),ub(:));·求线性规划子问题LP4得:,;x=opt;y=upper;由于和是原整数规划问题的可行解且min{,}=%下面是子函数=15,所以置这上界。functionftemp=ILP(vlb,vub)以下再将LP1分支,因所以可按条件globalupperoptcx0AbAeqbeqIDoptions;将LP1分成两个问题LP5和LP6,并赋予它们下界14.
