整数规划分支定界法.doc

《整数规划分支定界法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Matlab课后作业2年级：2008级专业：经济数学学号：姓名：吴德华一、编程利用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为最优解

2、，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.;%[xvs]=IP(f,A,B,I,[],[],lb,ub,,e)%x=41v=-90.0000s=1%控制输入参数ifnargin<9,e=0.00001;ifnargin<8,ub=[];ifnargin<7,lb=[]

3、;ifnargin<6,Beq=[];ifnargin<5,Aeq=[];ifnargin<4,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);ifexitflag<0disp('没有合适整数解');x=x0;fval=fval0;status=exitflag;

4、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为初始值opt

5、ions=optimset('display','off');[x0,fval0,status0]=linprog(f,A,B,Aeq,Beq,lb,ub,[],options);%递归中的最终退出条件%无解或者解比现有上界大则返回原解ifstatus0<=0

6、

7、fval0>=boundnewx=x;newfval=fval;newbound=bound;status=status0;return;end%是否为整数解,如果是整数解则返回intindex=find(abs(x0(I)-round(x0(I)))>e);

8、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]=

9、branchbound(f,A,B,I,x0,fval0,bound,Aeq,Beq,lb,ub,e);A(end,:)=[];B(:,end)=[];%解得第一个分支，若为更优解则替换，若不是则保持原状status=status1;ifstatus1>0&&bound1

10、eil(x(n))];[x2,fval2,status2,bound2]=branchbound(f,A,B,I,x0,fval0,bound,Aeq,Beq,lb,ub,e);A(end,:)=[];B(:,end)=[];%解得第二分支，并与第一分支做比较，如果更优则替换ifstatus2>0&&bound2