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

一、编程利用Matlab的线性规划指令：[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub)编写计算整数规划函数，输入与输出与上述指令相同分枝定界法（递归实现）function[x,fval,status]=intprog(f,A,B,I,Aeq,Beq,lb,ub,e)%整数规划求解函数intprog()%其中f为目标函数向量%A和B为不等式约束Aeq与Beq为等式约束%I为整数约束%lb与ub分别为变量下界与上界%x为最优解，fval为最优值%例子:%maximize20x1+10x2%S.T.%5x1+4x2=24%2x1+5x2=13%x1,x2=0%x1,x2是整数%f=[-20,-10];%A=[54;25];%B=[24;13];%lb=[00];%ub=[infinf];%I=[1,2];%e=0.000001;%[xvs]=IP(f,A,B,I,[],[],lb,ub,,e)%x=41v=-90.0000s=1%控制输入参数ifnargin9,e=0.00001;ifnargin8,ub=[];ifnargin7,lb=[];ifnargin6,Beq=[];ifnargin5,Aeq=[];ifnargin4,I=[1:length(f)];end,end,end,end,end,end%求解整数规划对应的线性规划,判断是否有解options=optimset('display','off');[x0,fval0,exitflag]=linprog(f,A,B,Aeq,Beq,lb,ub,[],options);ifexitflag0disp('没有合适整数解');x=x0;fval=fval0;status=exitflag;return;else%采用分支定界法求解bound=inf;[x,fval,status]=branchbound(f,A,B,I,x0,fval0,bound,Aeq,Beq,lb,ub,e);end子函数function[newx,newfval,status,newbound]=branchbound(f,A,B,I,x,fval,bound,Aeq,Beq,lb,ub,e)%分支定界法求解整数规划%f,A,B,Aeq,Beq,lb,ub与线性规划相同%I为整数限制变量的向量%x为初始解，fval为初始值options=optimset('display','off');[x0,fval0,status0]=linprog(f,A,B,Aeq,Beq,lb,ub,[],options);%递归中的最终退出条件%无解或者解比现有上界大则返回原解ifstatus0=0||fval0=boundnewx=x;newfval=fval;newbound=bound;status=status0;return;end%是否为整数解,如果是整数解则返回intindex=find(abs(x0(I)-round(x0(I)))e);ifisempty(intindex)newx(I)=round(x0(I));newfval=fval0;newbound=fval0;status=1;return;end%当有非整可行解时，则进行分支求解%此时必定会有整数解或空解%找到第一个不满足整数要求的变量n=I(intindex(1));addA=zeros(1,length(f));addA(n)=1;%构造第一个分支x=floor(x(n))A=[A;addA];B=[B,floor(x(n))];[x1,fval1,status1,bound1]=branchbound(f,A,B,I,x0,fval0,bound,Aeq,Beq,lb,ub,e);A(end,:)=[];B(:,end)=[];%解得第一个分支，若为更优解则替换，若不是则保持原状status=status1;ifstatus10&&bound1boundnewx=x1;newfval=fval1;bound=fval1;newbound=bound1;elsenewx=x0;newfval=fval0;newbound=bound;end%构造第二分支A=[A;-addA];B=[B,-ceil(x(n))];[x2,fval2,status2,bound2]=branchbound(f,A,B,I,x0,fval0,bound,Aeq,Beq,lb,ub,e);A(end,:)=[];B(:,end)=[];%解得第二分支，并与第一分支做比较，如果更优则替换ifstatus20&&bound2boundstatus=status2;newx=x2;newfval=fval2;newbound=bound2;end二、求解利用上述指令求解下列问题：汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量小型中型大型现有量钢材（吨）1251000劳动时间（小时）250125150120000利润（万元）35121、若每月生产的汽车必须为整车，试制订月生产计划，使工厂的利润最大2、如果生产某一类型汽车，则至少要生产50辆，那么最优的生产计划应作何改变？解：1f=[-3-5-12];A=[125;250125150];B=[1000120000];I=[1:length(f)];lb=[000];[x,fval,status]=intprog(f,A,B,I,[],[],lb)答案为x=3073441fval=-2653status=12lb=[505050]答案为x=35020050fval=-2.6500e+003status=1用分枝定界法求解整数线性规划问题&l&N;H%A+j6o._%%问题的标准形式：%%minc'*x%%s.t.A*x=b%%Aeq*x=beq!q%n+4FK^%%!Y要求是整数%%function[y,fval]=BranchBound(c,A,b,Aeq,beq)%NL=length(c);UB=inf;LB=-inf;-F*^&U(K4Y$OFN=[0];AA(1)={A};BB(1)={b};k=0;flag=0;whileflag==0;[x,fval,exitFlag]=linprog(c,A,b,Aeq,beq);if(exitFlag==-2)|(fval=UB)E#v7K:i1?&G-e.^.rFN(1)=[];(x/G8{:o8S7t/n#Hifisempty(FN)==13Q+Y1c4\)~%Sflag=1;else!@3T'`\lG'c&A3P'[k=FN(1);A=AA{k};(B2i6E8e8J9Q0O8w)ob=BB{k};endelsefori=1:NLZ!IM8Q5h2^2|1l;R3]!^ifabs(x(i)-round(x(i)))1e-7.M8G1m8{;t:J!D:gkk=FN(end);FN=[FN,kk+1,kk+2];'g9i4^-A:q#M)b7ctemp_A=zeros(1,NL);temp_A(i)=1;#y9O:E3Y#jxtemp_A1=[A;temp_A];AA(kk+1)={temp_A1};b1=[b;fix(x(i))];BB(kk+1)={b1};!P&q5C*LJ2]0xwtemp_A2=[A;-temp_A];,n-HM({.BAA(kk+2)={temp_A2};-z2p5v,z4s;O0J8Hu0Kb2=[b;-(fix(x(i))+1)];'N8R7R7M4wBB(kk+2)={b2};FN(1)=[];a3T8m.a,v2c8A)V)@7?/ek=FN(1);3D&F'C*u2kA=AA{k};b=BB{k};break;end,b,U9gR%H4U,Z+l5Q:uend&s7z1|1T6H%c)vX9zif(i==NL)&(abs(x(i)-round(x(i)))=1e-7)8j'x-U4C!V6W1RUB=fval;ezZ:H:E5j;O$qy=x;!h@!v!n0P2XFN(1)=[];ifisempty(FN)==1-sP,u5Mi}2l;cflag=1;elseF0O%k.t9v/|k=FN(1);;n'Q!B,E7R0[1O;`(Q-OA=AA{k};b=BB{k};end7I;V1P:V%?#Y!o$N3c/uendendend0P/y9F1h'l3?/y,qy=round(y);/s0r'y7j9@fval=c*y;3?&G,P#Y.|;