分支定界法资料

整数线性规划之分支定界法摘要最优化理论和方法是在上世纪40年代末发展成为一门独立的学科。1947年，Dantaig首先提出求解一般线性规划问题的方法，即单纯形算法，随后随着工业革命、计算机技术的巨大发展，以及信息革命的不断深化，到现在的几十年时间里，它有了很快的发展。目前，求解各种最优化问题的理论研究发展迅速，例如线性规划、非线性规划以及随机规划、非光滑规划、多目标规划、几何规划、整数规划等，各种新的方法也不断涌现，并且在军事、经济、科学技术等方面应用广泛，成为一门十分活跃的学科。整数规划（integerprogramming）是一类要求要求部分或全部决策变量取整数值的数学规划，实际问题中有很多决策变量是必须取整数的。本文主要介绍求解整数线性规划问题的分支定界法及其算法的matlb实现。关键词：整数线性规划；分支定界法；matlb程序；引言1.1优化问题发展现状最优化理论与算法是一个重要的数学分支，它所讨论的问题是怎样在众多的方案中找到一个最优的方案.例如，在工程设计中，选择怎样的设计参数，才能使设计方案既满足要求又能降低成本；在资源分配中，资源有限时怎样分配，才能使分配方案既可以满足各方面的要求，又可以获得最多的收益；在生产计划安排中，怎样设计生产方案才能提高产值和利润；在军事指挥中，确定怎样的最佳作战方案，才能使自己的损失最小，伤敌最多，取得战争的胜利；在我们的生活中，诸如此类问题，到处可见.最优化作为数学的一个分支，为这些问题的解决提供了一些理论基础和求解方法.最优化是个古老的课题.长期以来，人们一直对最优化问题进行着探讨和研究.在二十世纪四十年代末，Dantzig提出了单纯形法，有效地解决了线性规划问题，从而最优化成为了一门独立的学科。目前，有关线性规划方面的理论和算法发展得相当完善,但是关于非线性规划问题的理论和算法还有待进一步的研究，实际应用中还有待进一步的完善。传统的非线性全局最优化方法只能求出问题的局部最优解，但由于许多问题的局部最优解不一定是全局最优解，使得传统的非线性最优化方法不能直接成功地应用于求解非线性全局最优化问题。另外，没有一个固定的评判标准来判断得到的局部最优解是否为全局最优解。随着科学技术的发展和计算机计算能力的提高，最优化理论在最近这几年来得到了迅速的发展，涌现出了许多新的算法,如打洞函数法,填充函数法，lagrangian乘子函数方法，信赖域方法，虑子方法等。本文主要介绍求解整数线性规划问题的分支定界法及其算法的matlb实现。1.2整数线性规划及其数学模型整数规划主要有以下三大类：（1）全整数规划（allintegerprogramming）：所有的决策变量都取整数值，也称为纯整数规划（pureintegerprogramming）；（2）混合整数规划（mixedintegerprogramming）：仅要求一部分决策变量取整数值；（3）0-1规划（zero-oneintegerprogramming）：该类问题的决策变量只能取0或1.本文主要讨论的整数线性规划问题模型为：求解线性规划问题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';endifnargin<9,id=ones(size(f));endifnargin<8,x=[];endifnargin<7lisempty(ub),ub=inf*ones(size(f));endifnargin<6lisempty(lb),lb=zeros(size(f));endifnargin<5,heq=[];endifnargin<4,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;%下面是子函数functionftemp=ILP(vlb,vub)globalupperoptcx0AbAeqbeqIDoptions;[x,ftemp,how]=linprog(c,A,b,Aeq,beq,vlb,vub,x0,options);ifhow<=0return;end;ifftemp-upper>0.00005%inordertoavoiderrorreturn;end;ifmax(abs(x*ID-round(x*ID)))<0.00005ifupper-ftemp>0.00005%inordertoavoiderroropt=x';upper=ftemp;return;elseopt=[opt;x'];return;end;end;notintx=find(abs(x-round(x))>=0.00005);%inordertoavoider-rorintx=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.00000z=15.0000这与之前讨论的结果一致，说明该算法的正确性。4．总结虽然对于用分支定界法解决整数规则等问题在运筹学里有一套完整的理论,但将它用计算机来实现还是有一定的难度。本文正是在这个方面作了一些探讨,主要介绍了求解整数线性规划问题的分支定界法及其算法的matlb实现，并以实例验证了该算法的正确性。参考文献[1]王开荣.最优化方法[M].北京:科学版社,2012.219-222[2]李胜华.分支与定界算法的实现研究[J]