分支定界法完整可编辑版

一个调用例子：ifint=[0 1];f=[10 9];a=[1 0;0 1;-5 -3];b=[8 10 -45];[x,fval,exitflag] = linprogdis(ifint,f,a,b,[],[],[],[],[],[])function r=checkint(x)%算法：如果x(i)是整数，则返回r(i)=1；否则返回r(i)=0function r=ifrowinmat(arow,amat)%输入参数：% arow 向量，% amat 矩阵%%设计：如果 arow与矩阵amat中的某一行相等，则返回1，如果找不到现等的一行，则返回0可以使用ismember(arrow,amat,’rows’)替换ifrowinmat的调用，2005-10-28标注使用时，将下面的代码存入文件：linprogdis.mfunction [x,fval,exitflag,output,lambda]=... linprogdis(ifint,f,A,b,Aeq,beq,lb,ub,x0,options)%Title:% 分支定届法求解混合整数线性规划模型%%初步完成：2002年12月%最新修订: 2004-03-06%最新注释：2004-11-20%数据处理[t1,t2] = size(b);if t2~=1,b=b';%将b转置为列向量end%调用线性规划求解[x,fval,exitflag,output,lambda] =linprog(f,A,b,Aeq,beq,lb,ub,x0,options);if exitflag<=0,%如果线性规划失败，则本求解也失败returnend%得到有整数约束的决策变量的序号v1=find(ifint==1);%整数变量的indextmp=x(v1);%【整数约束之决策变量】的当前值if isempty(tmp),%无整数约束，则是一般的线性规划，直接返回即可returnendv2=find(checkint(tmp)==0);%寻找不是整数的index if isempty(v2),%如果整数约束决策变量确实均为整数，则调用结束returnend%第k个决策变量还不是整数解%注意先处理第1个不满足整数约束的决策变量k=v1(v2(1));%分支1：左分支tmp1=zeros(1,length(f));%线性约束之系数向量tmp1(k)=1;low=floor(x(k));%thisA 分支后实际调用线性规划的不等式约束的系数矩阵A%thisb 分支后实际调用线性规划的不等式约束向量b if ifrowinmat([tmp1,low],[A,b])==1%如果分支的约束已经存在旧的A，b中，则不改变约束thisA= A;thisb= b;elsethisA=[A;tmp1];thisb=b;thisb(end+1)=low;end%disp('fenzhi1'),thisA,thisb%递归调用[x1,fval1,exitflag1,output1,lambda1]= ...linprogdis(ifint,f,thisA,thisb,Aeq,beq,lb,ub,x0,o ptions);%分支2：右分支tmp2=zeros(1,length(f));%tmp1;tmp2(k)=-1;high= - ceil(x(k));if ifrowinmat([tmp2,high],[A,b])==1thisA= A;thisb= b;elsethisA=[A;tmp2];thisb=b;thisb(end+1)=high;end%disp('fenzhi2'),thisA,thisb[x2,fval2,exitflag2,output2,lambda2]= ...linprogdis(ifint,f,thisA,thisb,Aeq,beq,lb,ub,x0,o ptions);if isempty(v2) & ((exitflag1>0 & exitflag2<=0 & fval<=fval1 ) ...| (exitflag2>0 & exitflag1<=0 &fval<=fval2 )...| (exitflag1>0 & exitflag2>0 &fval<=fval1 & fval<=fval2 )),disp('error call')return %isempty(v2) 表示都是整数 2002-12-7非常重要end%下面分别根据返回标志exitflag确定最终的最优解%case 1if exitflag1>0 & exitflag2<=0 %【左分支有】最优解，右分支无最优解x = x1;fval = fval1;exitflag = exitflag1;output = output1;lambda = lambda1;%case 2elseif exitflag2>0 & exitflag1<=0 %【右分支有】最优解，左分支无最优解x = x2;fval = fval2;exitflag = exitflag2;output = output2;lambda = lambda2;%case 3elseif exitflag1>0 & exitflag2>0 %【左、右分支均有】最优解，则比较选优if fval1<fval2,%【左】分支最优（min）x = x1;fval = fval1;exitflag = exitflag1;output = output1;lambda = lambda1;else x = x2;,%【右】分支最优（min）fval = fval2;exitflag = exitflag2;output = output2;lambda = lambda2;end%fval1<fval2endfunction r=checkint(x)%算法：如果x(i)是整数，则返回r(i)=1；否则返回r(i)=0%输入参数：x 向量%输出参数：r 向量for i=1:length(x),ifmin(abs(x(i)-floor(x(i))),abs(x(i)-ceil(x(i))))<1 e-03%这里用于判定是否为0的参数可以调整，如改为1e-6r(i)=1;elser(i)=0;endendfunction r=ifrowinmat(arow,amat)%输入参数：% arow 向量，% amat 矩阵%%设计：如果 arow与矩阵amat中的某一行相等，则返回1，如果找不到现等的一行，则返回0r = 0;rows = size(amat,1);for i=1:rows,temp = (amat(i,:)==arow);%利用 Matlab的==操作，如果相等，则为1向量；if length(find(temp==0))==0,%没有为0的，即temp元素全部是1r=1;return end%end %for。

分支定界法第一篇：分支定界法整数线性规划之分支定界法摘要最优化理论和方法是在上世纪 40 年代末发展成为一门独立的学科。

1947年，Dantaig 首先提出求解一般线性规划问题的方法，即单纯形算法，随后随着工业革命、计算机技术的巨大发展，以及信息革命的不断深化，到现在的几十年时间里，它有了很快的发展。

目前，求解各种最优化问题的理论研究发展迅速，例如线性规划、非线性规划以及随机规划、非光滑规划、多目标规划、几何规划、整数规划等，各种新的方法也不断涌现，并且在军事、经济、科学技术等方面应用广泛，成为一门十分活跃的学科。

整数规划（integer programming）是一类要求要求部分或全部决策变量取整数值的数学规划，实际问题中有很多决策变量是必须取整数的。

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

关键词：整数线性规划；分支定界法；matlb程序；1．引言1.1优化问题发展现状最优化理论与算法是一个重要的数学分支，它所讨论的问题是怎样在众多的方案中找到一个最优的方案.例如，在工程设计中，选择怎样的设计参数，才能使设计方案既满足要求又能降低成本；在资源分配中，资源有限时怎样分配，才能使分配方案既可以满足各方面的要求，又可以获得最多的收益；在生产计划安排中，怎样设计生产方案才能提高产值和利润；在军事指挥中，确定怎样的最佳作战方案，才能使自己的损失最小，伤敌最多，取得战争的胜利；在我们的生活中，诸如此类问题，到处可见.最优化作为数学的一个分支，为这些问题的解决提供了一些理论基础和求解方法.最优化是个古老的课题.长期以来，人们一直对最优化问题进行着探讨和研究.在二十世纪四十年代末，Dantzig 提出了单纯形法，有效地解决了线性规划问题，从而最优化成为了一门独立的学科。

目前，有关线性规划方面的理论和算法发展得相当完善,但是关于非线性规划问题的理论和算法还有待进一步的研究，实际应用中还有待进一步的完善。