整数规划_分支定界法_MATLAB程序.doc

1、整数规划分支定界法MATLAB程序1.这种方法绝对能都解出答案，而且答案正确function x,val=fzdj(n,f,a,b,aeq,beq,lb,ub)x=zeros(n,1);x1=zeros(n,1);m1=2;m2=1;x1,val1=linprog(f,a,b,aeq,beq,lb,ub);if (x1=0)x=x1;val=val1;elseif (round(x1)=x1)x=x1;val=val1;elsee1=0,a,b,aeq,beq,lb,ub,x1,val1;e(1,1)=e1;zl=0;zu=-val1;while (zu=zl)for c=1:1:m2if (

2、m1=2)if (cell2mat(em1-1,c(1)=1)e1=1,0;e(m1,c*2-1)=e1;e(m1,c*2)=e1;continue;end;end;x1=cell2mat(em1-1,c(8);x2=zeros(n,1);s=0;s1=1;s2=1;lb1=cell2mat(em1-1,c(6);ub1=cell2mat(em1-1,c(7);lb2=cell2mat(em1-1,c(6);ub2=cell2mat(em1-1,c(7);for d=1:1:nif (abs(round(x1(d)-x1(d)0.0001)&(s=0)s=1;lb1(d)=fix(x1(d)+

3、1;if (a*lb1=b)s1=0;end;ub2(d)=fix(x1(d);if (a*lb2=b)s2=0;end;end;end;e1=s1,a,b,aeq,beq,lb1,ub1,0;e2=s2,a,b,aeq,beq,lb2,ub2,0;e(m1,c*2-1)=e1;e(m1,c*2)=e2;end;m1=m1+1;m2=m2*2;for c=1:1:m2if (cell2mat(em1-1,c(1)=0)x1,val1=linprog(f,cell2mat(em1-1,c( 2),cell2mat(em1-1,c(3),cell2mat(em1-1,c(4),cell2mat(e

4、m1-1,c(5),cell2mat(em1-1,c(6),cell2mat(em1-1,c(7);e1=cell2mat(em1-1,c(1),cell2mat(em1-1,c(2),cell2mat(em1-1,c(3),cell2mat(em1-1,c(4),cell2mat(em1-1,c(5),cell2mat(em1-1,c(6),cell2mat(em1-1,c(7),x1,val1;e(m1-1,c)=e1;end;z=val1;if (-z)(-zl)e1=1,0;e(m1-1,c)=e1;elseif (abs(round(x1)-x1)(-zu)zu=cell2mat(e

5、m1-1,c(9);end;end;end;for c=1:1:m2if (cell2mat(em1-1,c(1)=0)&(cell2mat(em1-1,c(9)=zu)x=cell2mat(em1-1,c(8);end;end;val=zu;end;2.这种方法是课本上的程序，但是不能解题，希望高手能将它改进function x,y=IntLp(f,G,h,Geq,heq,lb,ub,x,id,options)%整数线性规划分支定界法，可求解全整数线性或混合整数线性规划%y=min f*x subject to:G*x=h Geq*x=heq x为全整数%数或混合整数列向量%用法% x,y=

6、IntLp(f,G,h)% x,y=IntLp(f,G,h,Geq,heq)% x,y=IntLp(f,G,h,Geq,heq,lb,ub)% x,y=IntLp(f,G,h,Geq,heq,lb,ub,x)% x,y=IntLp(f,G,h,Geq,heq,lb,ub,x,id)% x,y=IntLp(f,G,h,Geq,heq,lb,ub,x,id,options)%参数说明% x:最优解列向量；y:目标函数最小值；f:目标函数系数列向量% G:约束不等式条件系数矩阵；h:约束不等式条件右端列向量% Gep：约束等式条件系数矩阵；heq:约束等式条件右端列向量% lb:解的下界列向量（De

7、fault:-inf）% ub:解得上界列向量（Default:inf）% x:迭代初值列向量；% id:整数变量指标列向量，1整数，0实数（default:1）% options的设置请参见 optimset或linprog%例 min z=x1+4x2%s.t. 2x1+x2=6% x1,x2=0且为整数%先将 x1+x2=6 化为 -x1-2x2=-6%x,y=IntLp(1;4,2 1;-1 -2,8;-6,0;0)global upper opt c x0 A b Aeq beq ID options;if nargin10,options=optimset();options.Di

8、splay=off; options.LargeScale=off;endif nargin9,id=ones(size(f);endif nargin8,x=;endif nargin7|isempty(ub),ub=inf*ones(size(f);endif nargin6|isempty(lb),lb=zeros(size(f);endif nargin5,heq=;endif nargin4,Geq=;endupper=inf;c=f;x0=x;A=G;b=h;Aeq=Geq;beq=heq;ID=id;ftemp=IntLp(lb(:),ub(:);x=opt;y=upper;%以

9、下为子函数function ftemp=IntLp(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 how0.00005%in order to avoid error return;end;if max(abs(x.*ID-round(x.*ID)0.00005%in order to avoid error opt=x;upper=ftemp; return; else opt=opt;x; return; end;en

10、d;notintx=find(abs(x-round(x)0.00005);%in order to avoid errorintx=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)= UB) FN(1)=; if isempty(FN)=1 flag=1; else k=FN(1); A=AA

11、k; b=BBk; end else for i=1:NL if abs(x(i)-round(x(i)1e-7 kk=FN(end); FN=FN,kk+1,kk+2; temp_A=zeros(1,NL); temp_A(i)=1; temp_A1=A;temp_A; AA(kk+1)=temp_A1; b1=b;fix(x(i); BB(kk+1)=b1; temp_A2=A;-temp_A; AA(kk+2)=temp_A2; b2=b;-(fix(x(i)+1); BB(kk+2)=b2; FN(1)=; k=FN(1); A=AAk; b=BBk; break; end end if (i=NL) & (abs(x(i)-round(x(i)=1e-7) UB=fval; y=x; FN(1)=; if isempty(FN)=1 flag=1; else k=FN(1); A=AAk; b=BBk; end end endendy=round(y);fval=c*y;以上程序都是我网上搜到的，还有自己从课本上自己敲的，第一个程序能成功解出答案，后两个不能，也许是程序有问题，也许是我不会调用，希望高手指点，帮助更多朋友们能够应用这三个程序！