资源描述：
《分支界定-branches-bounds》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、分支定界法的Matlab程序杨昔阳(泉州师范学院数学系,福建泉州,362000)最近想收集一下与数学建模有关的常用算法，发现网上竟然没有一个差不多的基于Matlab的整数规划程序。特编写一个Matlab程序，供大家参考。例如MinZ=¡15x1¡20x28><6x1+4x2<=25s:t:x1+3x2<=10>:x2是整数只需在命令行输入（其中w=[2]表示x2是整数,若x1;x2都是整数,w=[1,2]）>>A=[64;13];b=[25;10];f=[-15,-20];w=[2];>>[x,fval]=i
2、ntlinprog(f,A,b,[2])Optimizationterminated.Optimizationterminated.Optimizationterminated.x=2.83332.0000fval=-82.5000程序如下：function[myx,myfval]=intlinprog(f,A,B,w,Aeq,Beq,lb,ub,x0,options)%INTLINPROG:IntegerLinearProgramming整数规划%一切变量的用法与linprog相同，除了w,用来标记那些变量
3、是整数变量%Example:MinZ=-15x1-20x2，%s.t.6x1+4x2<=25%x1+3x2<=10%x2是整数%程序：A=[64;13];b=[25;10];f=[-15,-20];w=[2];%[x,fval]=intlinprog(f,A,b,w)%%byDamutou(杨昔阳,泉州师范学院数学系)%damutou@263.net1minfval=10000000;dimx=length(f);minx=zeros(2,1);%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
4、%%%%ifnargin<10,options=[];ifnargin<9,x0=[];ifnargin<8,ub=[];ifnargin<7,lb=[];ifnargin<6,Beq=[];ifnargin<5,Aeq=[];ifnargin<4,w=1:dimx;end,end,end,end,end,end,end%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%[minx,minfval]=damutou(f,A,B,Aeq,Beq,lb,ub,x0,options,w,dim
5、x,minfval,minx);myx=minx;myfval=minfval;function[minx,minfval]=damutou(f,A,B,Aeq,Beq,lb,ub,x0,options,w,dimx,minfval,minx)[x,fval,exitflag,output,lambda]=linprog(f,A,B,Aeq,Beq,lb,ub,x0,options);ifexitflag~=1return;elseiffval>minfvalreturnelsefori=wifabs(x(i
6、)-round(x(i)))>0.00001%ifx(i)isnotanintegerww=zeros(1,dimx);ww(i)=1;A=[A;ww];B=[B;floor(x(i))];[minx,minfval]=damutou(f,A,B,Aeq,Beq,lb,ub,x0,options,w,dimx,minfval,minx);A(end,:)=[];B(end,:)=[];ww=zeros(1,dimx);ww(i)=-1;A=[A;ww];B=[B;-ceil(x(i))];[minx,minf
7、val]=damutou(f,A,B,Aeq,Beq,lb,ub,x0,options,w,dimx,minfval,minx);A(end,:)=[];B(end,:)=[];endendifmax(abs(x(w)-round(x(w))))<0.000012iffval
