关于MATLAB整数规划分支定界法

《关于MATLAB整数规划分支定界法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、—＞编程利用Matlab的线性规划指令:[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub)编写计算整数规划函数，输入与输出■上述指令相同分枝定界法(递归实现)function[x,fval,status]=intprog(ffAfB,1,Aeq,Beq,lbzub,e)牛整数规划求解函数intprog()%其中f为目标函数向量%A和B为不等式约束Aeq与Beq为等式约束%I为整数约束%lb与ub分别为变量下界与上界%X为戢优解，fva1为最优值$例子：%maximize20xl+10x2%S・T.%5xl+4x2<=24%2xl+

2、5x2<=13%xlrx2>=0%xl,x2是整数%f=[-20z-10];%A=[54;25];%B=[24;13];%lb=[00];%ub=[infinf];%I=[l,2];%e=0.000001;%[xvs]=IP(f,AzBzl,[],[],lb,ub,,e)%x=41v=-90.0000s=1%控制输入参数ifnargin<9,e=0.00001;ifnargin<8,ub=[];ifnargin<7,lb=[];ifnargin<6,Beq=[];ifnargin<5,Aeq=[];ifnargin<4zI=[1:length(f)];e

3、nd,end,end,end,endzend咎求解整数规划对应的线性规划，判断是否有解options=optimset(1display1r1offf);[x0rfvalO,exitflag]=linprog(f,A,B,Aeq,Beq,lb,ub,[],options);ifexitflag<0disp(<没有合适整数解冷;x=xO;fval=fvalO;status=exitflag;return;else%采用分支定界法求解bound=inf;[x,fval,status]=branchbound(f,A,BzIzxOzfvalO,bound,Ae

4、q,Beqzlbzub,e);end了函数function[newx,newfval,status,newbound]branchbound(f,A,BzI,xzfval,boimd,Aeq,Beq,lb,ub,e)%分支定界法求解整数规划%f,A,B,Aeq,Beq,lb,ub与线性规划相同%I为整数限制变量的向量%X为初始解，fval为初始值options=optimset「display；off;[xOzfvalO,statusO]=linprog(fzA,B,Aeq,Beq,lb,ub,[],options);坯递归小的最终退出条件带无解或者解比

5、现冇上界人则返回原解ifstatusO<=0

6、

7、fvalO>=boundnewx=x;newfval=fval;newbound=bound;status=statusO;return;end曾是否为整数解，如果是整数解则返I叫intindex=find(abs(xO(I)-round(xO(I)))>e);ifisempty(intindex)newx(I)=round(xO(I));newfval=fvalO;newbound=fvalO;status=1;return;end%当有非整可行解时,则进行分支求解务此时必怎会冇整数解或空解坯找到第一个不

8、满足整数要求的变量n=I(intindex(1));addA=zeros(1,length(f));addA(n)=1;号构造笫1个分支x<=floor(x(n))A=[A;addA];B=[B,floor(x(n))];[xlrfvall,statusl,boundl]branchbound(f,A,B,IzxO,fvalO,bound,AeqfBeq,lb,ubfe);A(end,:)=[];B(:,end)=[];咎解得第一个分支，若为更优解则替换，若不是则保持原状status=statusl;ifstatusl>0&&boundl

9、wx=xl;newfval=fvail;bound=fvall;newbound=boundl;elsenewx=xO;newfval=fvalO;newbound=boimd;end号构造笫二分支A=[A;-addA];B=[B,-ceil(x(n))];[x2zfval2,status2,bound2]branchbound(f,A,B,IzxO,fvalO,bound,AeqfBeq,lb,ubfe);A(end,:)=[];B(:zend)=[];曾解得第二分支，并与第一分支做比较，如果更优则替换ifstatus2>0&&bound2

10、status=status2;newx=x2;newfval=fval2;new