MATLAB 分支定界法求解例题 题目:min (4*x1+4*x2); 约束条件:2*x1+5*x2<=15,2*x1-2*x2<=5,x1,x2>=0,且都为整数. 把以下程序存为 ILP.m， %============================ function [x,y]=ILp(f,G,h,Geq,heq,lb,ub,x,id,options) s.t. G*x<=h Geq*x=heq x 为全整数或混合整数列向量 %整数线性规划分支定界法，可求解纯整数规划和混合整数规划。 %y=minf’*x %用法 %[x,y]=ILp(f,G,h,Geq,heq,lb,ub,x,id,options) %参数说明 %lb:解的下界列向量（Default:-int） %ub:解的上界列向量（Default:int） %x:迭代初值列向量 %id：整数变量指标列向量，1-整数，0-实数（Default:1） global upper opt c x0 A b Aeq beq ID options; if nargin<10,options=optimset({});options.Display='off'; options.LargeScale='off';end if nargin<9,id=ones(size(f));end if nargin<8,x=[];end if nargin<7 |isempty(ub),ub=inf*ones(size(f));end if nargin<6 |isempty(lb),lb=zeros(size(f));end if nargin<5,heq=[];end if nargin<4,Geq=[];end upper=inf;c=f;x0=x;A=G;b=h;Aeq=Geq;beq=heq;ID=id; ftemp=ILP(lb(:),ub(:)); x=opt;y=upper; %下面是子函数 function ftemp=ILP(vlb,vub) global upper opt c x0 A b Aeq beq ID options; [x,ftemp,how]=linprog(c,A,b,Aeq,beq,vlb,vub,x0,options); if how <=0 return; end; if ftemp-upper>0.00005 %in order to avoid error 

return; end; if max(abs(x.*ID-round(x.*ID)))<0.00005 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 error intx=fix(x);tempvlb=vlb;tempvub=vub; if vub(notintx(1,1),1)>=intx(notintx(1,1),1)+1; tempvlb(notintx(1,1),1)=intx(notintx(1,1),1)+1; ftemp=IntLP(tempvlb,vub); end; if vlb(notintx(1,1),1)<=intx(notintx(1,1),1) tempvub(notintx(1,1),1)=intx(notintx(1,1),1); ftemp=IntLP(vlb,tempvub); end; %==================================== 然后： clc;clear f=[4 4] A=[2 5;2 -2] b=[15;5] Aeq=[];beq=[]; LB=[0 0];UB=[]; [xn,yn]=ILp(f,A,b,Aeq,beq,LB,UB,[1 1],1,[]) [x,fval,exitflag]=linprog(f,A,b,Aeq,beq,LB,UB) 结果： xn = 0 0 yn = 

0 Optimization terminated. x = 1.0e-013 * 0.299004078674759 0.503948216933779 fval = 3.211809182434153e-013 exitflag = 1