主程序:clear;time=cputime;[fab]=matrix_gen(K,T,n,M,LT,Sij,wi);m=length(f);e=-ones(1,n+K*T);e(1:n)=zeros(1,n);e=sparse(e);u=ones(1,m);extx=sparse(zeros(m,T));blpx=sparse(zeros(m,10000));var2_br=-ones(1,n);[rmpobj,x]=rmp_solve(n,K,T.extx,f,a,b,e,var2_br);s=1;if(round(x)==x)optx=x;optobj=rmpobj;returnelseupb=rmpobj;lowb=greedy(f,a,b,m,n,K,T);indbou=find(min(abs(x(end-n+1:end)-0.5))==abs(x(end-n+1:end)-0.5),1,first');var_br=sparse(zeros(1,n));var_br(1,indbou)=1;var2_br=sparse(-ones(2,n));var2_br(1,indbou)=1var2=find(var2_br(s,:)==1);blpf=f;blpa=a;blpa(indbou,m-n+indbou)=0;blpe=e;blpu=u;extx=sparse(zeros(m,2*T));extx(:,1:T)=iexl(n,K,T,m,M,a,var2);ifextx(:,1:T)==-ones(m,T)blpobj(s)=-1;blpx(:,s)=zeros(m,1);pool(s)=0;elsepool(s)=s;ends=s+1;var2_br(2,indbou)=0;pool(s)=s;s=s+1;while(nnz(pool)>0)bpool=max(pool);spool=bpool-1;fori=spool:bpoolifi==spoolj=1;elsej=2;end[blpobj(i),blpx(:,i)]=rmp_solve(n,K,T,extx(:,(j-1)*T+1:j*T),blpf,blpa,blpb(j:),blpe,var2_br(i,:));ifblpx(:,i)~=zeros(m,1)blpx(m-n+indbou,i)=1;endpool(i)=0;endifround(blpx(end-n+1:end,spool))==blpx(:,spool)ifblpobj(spool)>lowblowb=blpobj(spool);endendifmax(blpobj)>lowbbranch=find(max(blpobj)==blpobj,1,'first');upb=blpobj(branch);blpobj(branch)=-blpobj(branch);indbou=find(min(abs(blpx(end-n+1;branch)-0.5))==abs(blpx(end-n+1:end,branch)-0.5),1,'first');var_br((s+1)/2,:)=var_br(ceil(branch/2),:);var_br((s+1)/2,indbou)=1;var=find(var_br((s+1)/2)==1);blpa=a;blpa(var,m-n+var)=0;blpa=sparse(blpa);var2_br(s,:)=var2_br(branch,:);var2_br(s,indbou)=1;var2=find(var2_br(s,:)==1);blpb(1,:)=b;blpb(1,var2)=nonzeross(-a(var2,m-n+var2));extx(:,1:T)=iexl(n,K,T,m,M,a,var2);ifextx(:,1:T)=-ones(m,T)blpobj(s)=-1;blpx(:,s)=zeros(m,1);pool(s)=0;elsepool(s)=s;ends=s+1;var2_br(s,:)=var2_br(branch,:);var2_br(s,indbou)=0;var2=find(varx_br(s,:)==1);blpb(2,:)=b;blpb(2,var2)=nonzeros(-a(var2,m-n+var2));extx(:,T+1:2*T)=iexl(n,K,T,m,M,a,var2);pool(s)=s;s=s+1;endendendr=cputime-timematrix_gen子程序：function[f,a,b]=matrix_gen(K,T,n,M,LT,Sij,wi)m=sum(LT(:,2)-LT(:,1))+2*n;f=sparse(zeros(1,m));a=sparse(zeros(n+K*T,m));b=sparse(zeros(1,n+K*T));fori=1:Tb(1,n+(i-1)*K:n+i*K)=M;endwj=Sij*wj;vf=0;fori=1:nv_n(i)=LT(i,2)-LT(i,1)+1;f(vf+1:vf+v_n(i))=wj(i);vf=vf+v_n(i);enda1=a(1:n,:);a2=a(n+1:n_K*T,:);vf=0;fori=1:na1(i,vf+1:vf+v_n(i))=1;a1(i,m-n+i)=-v_n(i);vf=vf+v_n(i);endfori=1:Tforj=1:nifLT(j,1)<=i&i0v_1=columnl(find(rowl==i));v_1=v_1';forj=1:length(v_1)v_1(1,j)=find(nz_col==v_1(1,j));endsplow(v_1)=1;endifnnz(i=row0)>0v_0=column0(find(row0==i));v_0=v_0';forj=1:length(v_0)v_0(1,j)=find(nz_col==v_0(1,j));endspu(v_0)=0;endlp(i)=lp_maker(spf,spa,spb,spe,splow,[],1);mxlpsolve('solve',sp(i));spobj(i)=mxlpsolve('get_objective',lp(i)-rmpdual(n+i));endincre=1;whilemax(spobj)>le-1ind=find((max(spobj)==spobj),1,'first'inx=mxlpsolve('get_variables',lp(ind));fori=1:Tmxlpsolve('delete_lp',lp(i));endl=sparse(zeros(m,T+incre));l(:,1:end-1)=extx;extx=1;extx(find(A(ind,:)))=inx;nrmpf=zeros(1,T+incre+n);nrmpf(1,1:T+incre)=f*extx;nrmpa1=[a(1:n,:)*extx,a(1:n,m-n+1:m)];nrmpa2=[rmpa2(:,1:end-n),zeros(T,1),rmpa2(:,end-n+1:end)];rmpa2(ind,end-n)=1;nrmpa=[nrmpa1;nrmpa2];rmpu=ones(1,T+n+incre);[rmpobj,rmpx,rmpdual]=lp_solve(nrmpf,nrmpa,rmpb,rmpe,[],rmpu,[],1);ifisempty(rmpobj)==1x=zeros(m,1);return;endlp=zeros(1,T);spobj=zeros(1,T);fori=1:TA(i,:)=sum(a(n+(i-1)*K+1:n+i*K,:));nz_col=find(A(i,:));[row,column]=find(a(1:n,nz_col));spf=f(nz_col)-rmpdual(row)';spa=a((n+(i-1)*K+1:n+i*K),nz_col);spb=b(n+(i-1)*K+1:n+i*K);spe=e(n+(i-1)*K+1:n+i*K);splow=zeros(1,length(spf));spu=ones(1,length(spf));ifnnz(i=rowl)>0v_1=columnl(find(rowl==i));v_1=v_1';forj=1:length(v_1)v_1(1,j)=find(nz_col==v_1(1,j));endsplow(v_1)=1;endifnnz(i=row0)>0v_0=column0(find(row0==i));v_0=v_0';forj=1:length(v_0)v_0(1,j)=find(nz_col==v_0(1,j));endspu(v_0)=0;,lp(i)-rmpdual(n+i));endlp(i)=lp_maker(spf,spa,spb,spe,splow,[],1);mxlpsolve('solve',sp(i));spobj(i)=mxlpsolve('get_objective'endincre=incre+1;endx1=extx*rmpx(1:end-n);ifisempty(v1)==1x=[x1(1:m-n);rmpx(end-n+1:end)];elsejob=rmpx(end-n+1:end)=1;x=[x1(1:m-n);job];endx=sparse(x);greedy子程序：function[lowb,lowbx]=greedy(f,a,b,m,n,K,T)v=zeros(1,n);lowbx=zeros(1,m);fori=1:nv(i)=sum(f.*a(i,:));end[R,I]=sort(v,'descend');lowb=0;fori=1:nnz_col=find(a(I(i),:));lowbx(1,nz_col)=1;ifnnz(a*lowbx'<=b')
本文档为【列生成算法程序】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483