分支定界法的Matlab实现

一个调用例子:ifint=[O1];f=

[109];a=[l0;01;-5-3];b=[810-45];[x,fval,exitflag]=linprogdisifinLf,a,b」],function r=checkintx%算法如果xi是整数，则返回ri=l；否则返回r i=0function r=ifrowinmatarow amatA%输入参数%arow向量，%amat矩阵%%设计如果arow与矩阵amat中的某一行相等，则返回1,如果找不到现等的一行，则返回0可以使用ismemberairow,amatjrows，替换if rowinmat的调用，2005-10-28标注使用时，将下面的代码存入文件linprogdis.m function[xAfval,exitflag output,lambda]=...rlinprogdisifint,f,A,b,Aeq,beq,lb,ub,xO,options%Title:%分支定届法求解混合整数线性规划模型%渐修订:2004-03-06%】%初步完成2002年12月%最新注释2004-11-20%数据处理[tl,t2]=sizeb;b=b1;%将匕转置为列向量end%调用线性规划求解[x,fval,exitflag,output,lambda]=linprogfAeq,beq lbub x0,options;z zzif exitflagV=0,%如果线性规戈U失败，则本求解也失败returnend%得到有整数约束的决策变量的序号vl=findifint==l;%整数变量的indextmp=xvl;%【整数约束之决策变量】的当前值if isemptytmp,%无整数约束，则是一般的线性规划，直接返回即可return endv2=findcheckinttmp==0;%寻找不是整数的index ifisemptyv2,%如果整数约束决策变量确实均为整数，则调用结束returnend%第卜个决策变量还不是整数解%注意先处理第1个不满足整数约束的决策变量k=vlv21;%分支1:左分支tmpl=zeros1,length f;%线性约束之系数向量tmplk=1;low=floorxk;%thisA分支后实际调用线性规划的不等式约束的系数矩阵A%thisb分支后实际调用线性规划的不等式约束向量bif ifrowinmat[tmpl,low][A,b]==1r%如果分支的约束已经存在旧的A,b中，则不改变约束thisA=A;thisb=b;elsethisA=[A;tmpl];thisb=b;thisbend+1=low;end%dispfenzhil1,thisA,thisb%递归调用[xl,fvall,exitflagl,outputl,lambda1]•••linprogdisifint,f,thisA,thisb,Aeq,beq,lb,ub,xO,o ptions;%分支2右分支tmp2=zeros1,lengthf;%tmpl;tmp2k=-l;high=-ceilxk;if ifrowinmat[tmp2high],[A,b]==1AthisA=A;thisb=b;elsethisA=[A;tmp2];thisb=b;thisbend+1=high;end%disp1fenzhi2,thisA,thisb[x2,fval2,exitflag2,output2,lainbda2]linprogdisifint fthisA,thisb,Aeq,beq lb,ub xO,o ptions;f zf fifisemptyv2exitflagl0exitflag2=0fval=fvall|exitflag20exitflagl=0fval=fval

2...|exitflagl0exitflag20fval=fvall fval=fval2,disp，error callfreturn%isempty v2表示都是整数2002-12-7非常重要end%下面分别根据返回标志exitf lag确定最终的最优解%case1if exitflagl0exitflag2=0%【左分支有】最优解，右分支无最优解X=xl;fval=fvall;exitflag=exitflagl;output=outputl;lambda=lambdal;elseif exitflag20exitflagl=0%【右分支%case2有】最优解，左分支无最优解fval=fval2;exitflag=exitflag2;output=output2;lambda=lambda2;%case3elseif exitflagl0exitflag20%【左、右分支均有】最优解，则比较选优if fvallfval2,%【左】分支最优minX=xl;fval=fvall;exitflag=exitflagl;output=outputl;lambda=lambdal;else x=*2;,%【右】分支最优min fval=fval2;exitflag=exitflag2;output=output2;lambda=lambda2;end%fvallfval2end functionr=checkintx%算法如果xi是整数,则返回ri=l；否则返回r i=0%输入参数X向量%输出参数r向量for i=l:lengthxrifminabsxi-floorxi,absxi-ceilxi1e-03%这里用于判定是否为0的参数可以调整，如改为le-6r i=l;elser i=0;endend functionr=ifrowinmatarow,amat%输入参数%arow向量，%amat矩阵%%设计:如果arow与矩阵amat中的某一行相等,则返回1,如果找不到现等的一行，则返回0r=0;rows=sizeamat1;Afor i=l:rows,temp=amat i:==arow;%利用Matlabftl==A操作，如果相等，则为1向量；if lengthfind temp==0==0,%没有为的，BP temp元素全部是1r=l;return end%end%for。