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