分支定界解析

《分支定界解析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、MATLAB解整数规划问题__分支定界法柯伟敏G012012348一、问题分析在线性规划问题屮，有些最优解可能是分数或小数，事实上，线性规划是连续变量的线性优化问题。但在实际问题中，常冇要求解答必须是整数的情形。例如，所求解是机器人的台数，完成工作的人数或者装货的车数等，分数或者小数的解答就不符合要求。为了满足整数解的要求，初看起来，似乎只要把己得到的带有分数的或小数的解经过‘舍入化整’就可以了。但这常常是不行的，因为化整之后不见得就是可行解，或虽是可行解，但不一定是最优解。因此，对求最优整数解问题，有必要另行研究。我们称这样的问题为

2、整数规划问题。学习运筹学过后，我们学习了笔算这类问题，但是当对于一个问题的约束条件有很多个吋，手算必然耗费很大个工作量。但是用MATLAB解题却可以达到事半功倍的效果，省去了很多繁琐的运算过程。二、:学原理下面我主要介绍分支定界解法。分支定界法的基本思想是不断将可行域分割成小的集合，然后再小的集合上找整数最优解，在分割可行域时，整数解并不会丢失。其算法过程如下：*1、置矩阵NF_lb为原整数的的lb，NF_ub为原整数规划的ub，置最优解二0，目标函数的最优上界F=+°°。2、设NF_lb的第一列为lbQ,NF_ub第一列为ub(),

3、求解线性规划minf(x)=cx,AxQ3、若/=+<-，则将NF_lb的第一列和NF_ub的第一列去掉，转7，否则，转44、若则将NF_lb的第一列去掉，和NF_ub的第一列去棹，转7,否则，转5._氺_5、若^

4、第一列分量&对应的下界改为［及］+1;第二个问题的lb等于1b()，而ub是将NF_ub中的第一列,对应的上界改为［%；］,再将NF_lb的第一列和NF_ub的第一列去掉，把Ql,Q2对应的1b，ub作为新列分别添加到NFlb和NFub的后面，转2*木7、若NF_lb不为空，则转2,若为空，且*不为空，则*为原整数规划的最优解，^最优值，如果X为空，则原整数规划不存在最优解。三、解题过程根据上述算法，编写对应的MATLAB程序function[x,fm]=IntProgFZ(f,A,b,Acq,bcq,lb,ub)x=NaN;fm=N

5、aN;NFlb=zeros(size(lb));NFub=zeros(size(ub));NF_lb(:,1)=lb;NFub(:,1)=ub;F=inf;while1sz=size(NFlb);k=sz⑵；opt=optimset(’TolX’，le-9);%解线性规划[xm,fv,exitflag]=1inprog(f,A,b,Acq,bcq,NF_lb(:,1),NF_ub(:,1),[],opt);%求原问题的松弛问题的最优ifexitflag==~2%不存在最优解xm=NaN;fv=NaN;endifxm=二NaNfv=in

6、f;%无穷大，对应第3步endiffv"=inf%不为不穷大iffv

7、解!’)；x=NaN;fm=NaN;return;endendelselbl=NF_lb(:，1);%分解为两个问题ubl=NFub(:,1);tmpNF_lb=NF_lb(:,2:k);%去掉第一列tmpNF_ub=NF_ub(:，2:k);%去掉第一列NF_lb=tmpNF_lb;NF_ub=tmpNF_ub;[bArr,index]=find(abs((xm-round(xm)))〉=1.0e-7);%任找一个非整数变量，算法第6步，分成两个问题p=bArr(1);new_lb=lbl;newub=ubl;new_lb(p)=m

8、ax(floor(xm(p))+1,lbl(p));%更新求解表new_ub(p)=min(floor(xm(p)),ubl(p));%更新求解表NF_lb=[NF_lbnew_lblbl];NFub=[NFububln