分支定界法Matlab程序实现与验证

1分支定界法Matlab程序实现与验证为了更深入理解分支定界法计算流程，从而决定花费几天时间仔细学习该算法，并编写出该算法的Matlab计算程序。同时为了后面个人的借鉴学习，编写本文档。在进行分支定界法计算程序编写过程中，通过网络搜索，发现了Matlab2014版之后嵌入了混合整数线性规划求解函数intlinprog，从而也将该函数的使用方法撰写下来。1 整数规划问题简介 在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常有要求解答必须是整数的情形(称为整数解)。例如：所求解是机器的台数、完成工作的人数或装货的车数等，分数或小数的解答就不合要求。为了满足整数解的要求，初看起来，似乎只要把已得到的带有分数或小数的解经过“舍入化整”就可以了。但这常常是不行的，因为化整后不见得是可行解；或虽是可行解，但不一定是最优解。因此，对求最优整数解的问题，有必要另行研究。人们称这样的问题为整数规划(IntegerProgramming，IP)，整数规划是最近几十年发展起来的规划论中的一个分支。整数规划中如果所有的变数都限制为(非负)整数，就称为纯整数规划(PureIntegerProgramming，PIP)或称为全整数规划(AllIntegerProgramming，AIP)；如果仅一部分变数限制为整数，则称为混合整数计划(MixedIntegerProgramming，MIP)。整数规划的一种特殊情形是0-1规划，该规划中变量的取值仅限于0或1，指派问题就是一类典型的0-1规划问题。现举例说明用前述单纯形法求得的解不能保证是整数最优解。例1：某厂拟用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运所受限制如表1所示。问两种货物各托运多少箱,可使获得利润为最大?表1货物托运示例数据货物体积（m³/箱）重量（百公斤/箱）利润（百元/箱）甲5220乙4510托运限制24（m³）13百公斤设1x、2x分别为甲、乙两种货物的托运箱数（为非负整数），列该问题的纯整数规划模型如下：12max2010zxx21212121254242513,0,intxxxxxxxx当不考虑两个变量整数约束时，将上述模型作为一个LP问题在Matlab中可以求得最优解。Matlab中的求解程序如下：f=[-20-10];A=[54;25];B=[2413];lb=[00];[x,fit,exitF]=linprog(f,A,B,[],[],lb,[])运行该程序后得到的结果如下：x=4.80000.0000fit=-96.0000exitF=1可以看出，当1x取值4.8、2x取值0时可以获得最大的盈利96个单位，但是由于1x的取值不是整数，不符合实际装箱要求。如果将解｛4.80｝转化为｛50｝，则不满足第一条约束，转化后的解不是可行解；如果将解｛4.80｝转化为｛40｝，得到盈利为80单位，虽然是可行解，但是并不是最优解。如果将如果将解｛4.80｝转化为｛41｝，则可以获得盈利90个单位，且该解是可行解，也是该问题的最优解。从这个例子可以看出，将整数规划问题对应的线性规划问题的解直接整数化虽然很简单，但是最后得到的解可能同最优解之间相距深远，因此需要采取特定的方法来获取证书规划的最优解。2 分支定界法基本运算逻辑 在求解整数规划时，如果可行域是有界的，首先容易想到的方法就是穷举变量的所有可行的整数组合，然后比较它们的目标函数值以定出最优解。对于小型的问题，变量数很少，可行的整数组合数也是很小时，这个方法是可行的，也是有效的。对于大型的问题，可行的整数组合数是很大的。例如将n项任务指派n个人去完成，不同的指派方案共有n!种，当n=10，这个数就超过300万；当n=20，这个数就超过2×1018，如果一一计算，就是用每秒百万次的计算机，也要几万年的功夫，很明显，解这样的题，穷举法是不可取的。所以我们的方法一般应是仅检查可行的整数组合的一部分，就能定出最优的整数解。分支定界解法(branchandboundmethod)就是其中的一个。分支定界法可用于解纯整数或混合的整数规划问题。在20世纪60年代初3由LandDoig和Dakin等人提出。由于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法。设有最大化的整数规划问题A，与它相应的线性规划为问题B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z*的上界，记作z，而A的任意可行解的目标函数值将是z*的一个下界z。分支定界法就是将B的可行域分成子区域(称为分支)的方法，逐步减小z和增大z，最终求到z*。现用下例来说明，例2：12max4090zxx12121212975672070,0,intxxxxxxxx图1分支定界法求解示例的过程《运筹学》教材编写组《运筹学》第三版p117，清华大学出版社为了更好的理解分支定界法的计算流程，下面计算另外两个示例。4例3：整数规划模型如下，判断使用线性规划求解后采用凑整的办法能够求得最优整数解？12max32zxx121212122314.5416.5,0,intxxxxxxxx解：（1）首先将该模型转化为linprog理解的LP标准型如下：12min32zxx1212122314.5416.5,0xxxxxx（2）通过如下Matlab程序进行求解f=[-3-2];A=[23;41];B=[14.516.5];lb=[00];ub=[inf,inf];[x,fit,exitF]=linprog(f,A,B,[],[],lb,ub)求解结果为：z=15.5，x=[3.5,2.5]（3）采用将两个变量取整来获取可行解，可以将解转化为如下四种组合：[32][33][42][43]其中[33]，[43]不满足第一个约束条件，[42]不满足第二个约束条件，为非可行解。[32]对应的目标函数值为：13。那么这个解是不是最优解呢？下面通过分支定界获得最优解来对比。（4）分支定界5图2例3分支定界计算过程图根据上图的分支定界求解可知，最优解为[3,2]，目标函数最大值为13，所以通过简单的取整得到了本模型的最优解。当一个分支中下界和上界相等时，或者找到了下界，其他分支无可行解则表示找到了最优解；剪枝规则：当找到了函数的整数可行解下界后，其他分支LP解值不能大于下界时，剪枝；或者无可行解时，剪枝。例4：整数规划模型如下，判断使用线性规划求解后采用凑整的办法能够求得最优整数解？12max32zxx12121212231429,0,intxxxxxxxx解：（1）首先将该模型转化为linprog理解的LP标准型如下：23x22x12x1=3x14x13x123.52.515.5xxz1232.8314.67xxz122.75414.25xxz无可行解1223.513xxz1240.513xxz123213xxz0,15.5zz0,14.67zz13,14.25zz13,13zz612min32zxx121212231429,0xxxxxx（2）通过如下Matlab程序进行求解f=[-3-2];A=[23;21];B=[149];lb=[00];ub=[inf,inf];[x,fit,exitF]=linprog(f,A,B,[],[],lb,ub)求解结果为：z=14.75，x=[3.25,2.5]（3）采用将两个变量取整来获取可行解，可以将解转化为如下四种组合：[32][33][42][43]其中[33]，[43]不满足第一个约束条件，[42]不满足第二个约束条件，为非可行解。[32]对应的目标函数值为：13。那么这个解是不是最优解呢？下面通过分支定界获得最优解来对比。（4）分支定界7图3例4分支定界计算过程图根据上图的分支定界求解可知，最优解为[4,1]，目标函数最大值为14，所以通过简单的取整不能得到了本模型的最优解。3 分支定界法程序设计逻辑框图 根据上述示例的计算过程，总结分支定界计算机处理流程如下：（1）将原整数规划模型A整理成线性规划标准形式B；该模型的参数有：f,A,b,Aeq,beq,lb,ub,X0,F0，其中X0和F0分别设定为模型A的初始可行解和目标函数值，可由人工简要计算后获得；（2）求解线性规划问题B，根据问题B的解进行后续的分支和定界，处理准则如下：（a）如果无可行解，剪枝（如果不是处于递归过程中，则执行至此处，问题结束，该整数规划没有可行解）；（b）如果有非整数可行解，且函数值高于上界F0，剪枝；（c）如果有非整数可行解，但低于上界，则继续分支，执行步骤（3）；（d）如果有整数可行解，且函数值高于上界，剪枝；（e）如果有整数可行解，且函数值低于上界，更新上界数值F0和可行解23x22x12x1=3x14x13x123.252.514.75xxz1232.6714.33xxz122.75313.5xxz无可行解1223.3312.67xxz124114xxz123213xxz0,14.75zz0,14.33zz13,13.5zz4,14.33zz8X0，停止分支。（3）任意选择一个取值不满足整数的变量i进行分支，分成~iixx和~1iixx，用这两个条件分别形成线性规划模型B1和B2，其中B1模型中ub（i）=~ix，模型B2中lb(i)=~1ix；（4）采用递归函数的形式，令B=B1，重新执行步骤（2）；（5）采用递归函数的形式，令B=B2，重新执行步骤（2）；（6）获得最优解，解的数值分别为数值更新之后的X0和F0。4 分支定界法Matlab函数jBranchBound程序源代码 根据上述程序设计逻辑结构，设计分支定界法的Matlab函数源代码如下：function[xOut,fitOut,flagOut]=jBranchBound(c,A,B,Aeq,beq,vlb,vub,optXin,optF)globaloptXoptValoptFlag;optX=optXin;optVal=optF;options=optimoptions('linprog','Algorithm','interior-point-legacy','display','none');[x,fit,status]=linprog(c,A,B,Aeq,beq,vlb,vub,[],options);ifstatus~=1%nooptimalsolution,endtheprogram%dothesewhenthefirstLPcann'tgetafeasiblesolution%inthenextloop,thesevaluedon'treturnback.xOut=x;fitOut=fit;flagOut=status;return;end%thefollowingprogramsarebasedontheconditionofstatus=1ifmax(abs(x-round(x)))0.005%therehaverealsolutioniffitoptVal%cann'tfindanyrealfeasiblesolutionbetterthanoptValxOut=x;fitOut=fit;flagOut=-100;return;else%continuetobranchendelse%therehaveintegersolutioniffitoptVal%cann'tfindanyintegerfeasiblesolutionbetterthanoptValxOut=x;fitOut=fit;flagOut=-101;return;elseoptVal=fit;