分支定界法_分支定界法的公式

分支定界法由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“分支定界法的公式”。

整数线性规划之分支定界法

摘要

最优化理论和方法是在上世纪 40 年代末发展成为一门独立的学科。1947年，Dantaig 首先提出求解一般线性规划问题的方法，即单纯形算法，随后随着工业革命、计算机技术的巨大发展，以及信息革命的不断深化，到现在的几十年时间里，它有了很快的发展。目前，求解各种最优化问题的理论研究发展迅速，例如线性规划、非线性规划以及随机规划、非光滑规划、多目标规划、几何规划、整数规划等，各种新的方法也不断涌现，并且在军事、经济、科学技术等方 面应用广泛，成为一门十分活跃的学科。

整数规划（integer programming）是一类要求要求部分或全部决策变量取整数值的数学规划，实际问题中有很多决策变量是必须取整数的。本文主要介绍求解整数线性规划问题的分支定界法及其算法的matlb实现。

关键词：整数线性规划；分支定界法；matlb程序；

1． 引言

1.1优化问题发展现状

最优化理论与算法是一个重要的数学分支，它所讨论的问题是怎样在众多的方案中找到一个最优的方案.例如，在工程设计中，选择怎样的设计参数，才能使设计方案既满足要求又能降低成本；在资源分配中，资源有限时怎样分配，才能使分配方案既可以满足各方面的要求，又可以获得最多的收益；在生产计划安排中，怎样设计生产方案才能提高产值和利润；在军事指挥中，确定怎样的最佳作战方案，才能使自己的损失最小，伤敌最多，取得战争的胜利；在我们的生活中，诸如此类问题，到处可见.最优化作为数学的一个分支，为这些问题的解决提供了一些理论基础和求解方法.最优化是个古老的课题.长期以来，人们一直对最优化问题进行着探讨和研究.在二十世纪四十年代末，Dantzig 提出了单纯形法，有效地解决了线性规划问题，从而最优化成为了一门独立的学科。目前，有关线性规划方面的理论和算法发展得相当完善,但是关于非线性规划问题的理论和算法还有待进一步的研究，实际应用中还有待进一步的完善。传统的非线性全局最优化方法只能求出问题的局部最优解，但由于许多问题的局部最优解不一定是全局最优解，使得传统的非线性最优化方法不能直接成功地应用于求解非线性全局最优化问题。另外，没有一个固定的评判标准来判断得到的局部最优解是否为全局最优解。随着科学技术的发展和计算机计算能力的提高，最优化理论在最近这几年来得到了迅速的发展，涌现出了许多新的算法, 如打洞函数法,填充函数法，lagrangian 乘子函数方法，信赖域方法，虑子方法等。

本文主要介绍求解整数线性规划问题的分支定界法及其算法的matlb实现。

1.2整数线性规划及其数学模型

整数规划主要有以下三大类：（1）全整数规划（all integer programming）：所有的决策变量都取整数值，也称为纯整数规划（pure integer programming）；（2）混合整数规划（mixed integer programming）：仅要求一部分决策变量取整数值；

（3）0-1规划（zero-one integer programming）：该类问题的决策变量只能取0或1.本文主要讨论的整数线性规划问题模型为：

minzcTxAxb s.t.xj0(j1,2,...,n)xj为整数，（c1,...,cn)其中c

T，x（x1,...,xn)T,A(aij)mn,b(b1,...,bm)T

2．求解整数线性规划的算法——分支定界法

2.1求整数最优解问题的提出

对于整数规划的一个数学问题,把它的整数约束条件改为非负约束,得到一个普通线性规划问题,这个过程叫做从原问题ILP得到它的一个松弛问题LP,说它是“松弛”的,是因为从整数变为实数,条件放宽了许多。

minzcTxAxbILP： s.t.xj0 (j1,2,...,n)xj为整数，minzcTxAxbLP： s.t.（j1,2,...,n）xj0,（c1,...,cn)其中cT，x（x1,...,xn)T,A(aij)mn,b(b1,...,bm)T

给定一个整数规划的数字题,一个直观的求解思路是先做出它的松弛问题。如果松弛问题的最优解中每一个整变量(即分量)的值都满足各自的整数约束,原问题得到解决。如果松弛问题的最优解中,某个变量的值不是整数,问题就很难解决。实践表明,求解整数规划是一个很困难的工作。随着计算机技术的迅猛发展,数学运算软件得到了广泛的使用,如:matlab,mathematica,maple等。计算机已经成为应用数学软件求解问题的主要运算工具。

2.2分支定界法

分支定界算法是20世纪60年代初由Land和Doig提出，并由Dakin修正，可用于求解纯整数或混合整数线性规划问题。对于一个纯整数规划ILP问题,求解它的一个基本思路是分支定界法,正如它的名字那样,主要由“分支”和“定界”组成。

首先讨论LP与ILP解的相关问题：“LP的解”。可能有以下3种情况:(1)LP没有可行解,这时ILP也没有可行解,则停止；

(2)LP有最优解,并且解变量都是整数,因而它也是ILP的最优解,则停止;(3)LP有最优解,但不符合ILP中的整数条件,此时记它的目标函数值为z0,这时若记z为ILP的最优目标函数值,则必有zz0

其次,给出算法的步骤: 第一步——分支:在LP的最优解中任选一个不符合整数条件的变量xj,设其值为lj,[lj]是不超过lj的最大整数。构造两个约束条件:xj[lj]和xj[lj]+1,将两个条件分别加入其松弛问题LP,将LP分成两个后继问题LP1和LP2。不考虑整数条件要求,求解LP1和LP2。根据需要各后继问题可用类似的方法进行分支,如此不断继续,直到获得整数规划的最优解,这就是所谓的“分支”。

第二步——定界:以每个后继子问题为一分支并标明求解的结果,与其他问题的解的结果一道,找出最优目标函数值最小者作为新的下界,替换z0,从已符合整数条件的各分支中,找出目标函数值为最小者作为新的上界z*,即有z*zz0。

第三步——比较与剪支:各分支的最优目标函数中若有大于z*者,则剪掉这一支;若小于z*,且不符合整数条件,则重复第一步骤,一直到最后得到最优目标函数值zz*为止,从而得最优整数解xj,j1,2,...,n.“分支”为整数规划最优解的出现创造了条件,而“定界”则可以提高搜索的效率。经验表明:在可能的情况下根据对实际问题的了解,实现选择一个合理的“界限”,可以提高分支定界法的搜索效率

*2.3实例

例1求解下列整数规划

minz7x13x24x3x12x23x38 3x1x2x35s.t.x0jx为整数，(j1,2,3)j解：设原整数规划问题为ILP, 其松弛问题为

minz7x13x24x3LP：

x12x23x38 s..t3x1x2x35x0,j1,2,3j求解线性规划问题LP得:x(0)(0.4,3.8,0);z014.2

(1)按条件和将问题LP分解成子问题LP1和LP2并赋它们下界为14.2

x①求线性规划子问题LP1得：

(0.5,3,0.5);z114.5；求线性规划子问题LP得：

中x1143)2(x(2)(,4,0);z2；minz1,z2z2；因x33②求线性规划子问题LP3得：x(3)1，因此以条件x10和x113将LP2分成两个子问题LP3和LP4并赋它们下界为14.33

(0,5,0);z315；求线性规划子问题LP4得：x(4)(1,4,0);z419；因x(3)和x(4)是原整数规划问题的可行解且minz3,z4z3，所以令z315为上界。再将LP1分支，因x(1)中x10.5，因此以条件x10和x11将LP1分成两个子问题LP5和LP6并赋它们下界为14.33 ③求线性规划子问题LP5得：x(5)(0,3,2);z517；求线性规划子问题LP6得：749x(6)(1,0,);z6；由于z5，z6>z315,所以LP5和LP6都没有继续分支求解的必33要,至此求得最优解为x*x3(0,5,0)，,最优目标函数值为z*z315。

3．matlab程序实现

下面给出整数线性规划分支定界法的matlab程序ILp1.m.function [x,y]=ILp1(f,G,h,Geq,heq,lb,ub,x,id,options)global upper opt c x0 A b Aeqbeq ID options;

ifnargin

ifnargin

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)

global upper opt c x0 A b Aeqbeq ID options;

[x,ftemp,how]=linprog(c,A,b,Aeq,beq,vlb,vub,x0,options);if how

ifftemp-upper>0.00005 %in order to avoid error return;end;

if max(abs(x*ID-round(x*ID)))

if upper-ftemp>0.00005 %in order to avoid error opt=x';upper=ftemp;return;else

opt=[opt;x'];return;end;end;

notintx=find(abs(x-round(x))>=0.00005);%in order to avoid er-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)

对例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 0 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

勘测定界心得

勘测定界心得骆金超尊敬的各位领导、各位同事大家好！首先给大家拜个晚年，祝大家新年愉快！回顾2008年，这一年是丰收的一年。在领导和全体同志的关怀、帮助、支持下，紧紧围绕测量工......

勘测定界验收报告

土地勘测定界成果检查验收办法日期： 2009-8-27 一、土地勘测定界的范围包括土地征用、划拨、出让、农用地转用、土地利用规划及土地开发整理复垦等。二、土地勘测定界检查验......

勘测定界技术总结

勘测定界技术总结报告土地勘测定界是实地确定土地使用界线范围，测定界桩位置，调绘土地利用现状，计算用地面积，为国土资源行政主管部门用地审批和地籍管理等提供科学、准确的基础......

预分支电缆安装工艺工法及成本核算

预分支电缆安装工艺工法及成本核算摘要：详细介绍了传统电缆配电干线方式缺陷及预分支电缆的优点及发展前景，对预分支电缆的安装工艺工法进行了详尽的叙述，并以中关村金和国际大......

无分支证明

无分支机构声明现有财务、业务、人员等由我公司进行统一管理，我公司未设立分支机构。特此声明 ******************* ****年****月****日 无分包声明现有业务由我公司进行统一......