车辆调度问题.pdf

车辆调度问题设某车队有8辆车，存放在不同的地点，队长要派出其中5辆到5个工地去运货。各车从存放处调到装货地点所需费用列于下页表，问应选哪5辆车调到何处去运货，才能使各车从车所在地点调到装货地点所需的总费用最少？车地点123456781302518322719222622931191821203019328293019192223264293019242519182152120181716141618x1x2x3x4x5y1y2y3y4y5y6y7y8MATLAB程序——Kuhn-munkras算法functionsumw=kuhngong(A)n=size(A,1);w=A;l=zeros(n,2);fori=1:nforj=1:nifl(i,1)<w(i,j)l(i,1)=w(i,j);endendendFLAG_AGL=zeros(n,n);FLAG_S=zeros(1,n);FLAG_T=zeros(1,n);FLAG_NGLS=zeros(1,n);f=zeros(n,2);fori=1:nforj=1:nifl(i,1)+l(j,2)==w(i,j)FLAG_AGL(i,j)=i;endendendM=zeros(n,2);fori=1:nforj=1:nif(FLAG_AGL(i,j)==i)&(~M(j,2))&(~M(i,1))M(i,1)=i;M(j,2)=i;endendendFLAG3=1;whileFLAG3FLAG3=0;u=0;fori=1:nif~M(i,1)u=i;break;endendendwhileFLAG4fori=1:nifFLAG_S(i)forj=1:nifFLAG_AGL(i,j)==iFLAG_NGLS(j)=1;end,end,end,endFLAG_EQU=1;fori=1:nifFLAG_NGLS(i)~=FLAGT(i)FLAG_EQU=0;break;end,endFLAG4=0;al=inf;ifFLAG_EQUfori=1:nforj=1:nif(FLAG_S(i))&(~FLAG_T(j))temp=l(i,1)+l(j,2)-w(i,j);ifal>tempal=temp;end,end,end,endif~ufprintf(1,‘二部图最大权匹配运行结果');fprintf(1,‘求得最大权匹配M={');sumw=0;fori=1:nforj=1:nifM(j,2)==ifprintf(1,'x%dy%d,',i,j);sumw=sumw+w(i,j);break;endendendfprintf(1,'}');fprintf(1,‘最大权W(M)=%g',sumw);returnelseFLAG_S=zeros(1,n);FLAG_T=zeros(1,n);FLAG_S(u)=1;f=zeros(n,2);FLAG_NGLS=zeros(1,n);endFLAG4=1;fori=1:nifFLAG_S(i)l(i,1)=l(i,1)-al;end,endforj=1:nifFLAG_T(j)l(j,2)=l(j,2)+al;end,endFLAG_AGL=zeros(n,n);fori=1:nforj=1:nifl(i,1)+l(j,2)==w(i,j)FLAG_AGL(i,j)=i;end,end,end,endforx=1:nfory=1:nif(FLAG_S(x))&(~FLAG_T(y))&(FLAG_AGL(x,y)==x)f(y,2)=x;ifM(y,2)%%1startforz=1:nif(FLAG_AGL(z,y)==z)&(M(y,2)==z)FLAG_S(z)=1;FLAG_T(y)=1;f(z,1)=y;FLAG4=1;break;end,endelse%%1endstop=0;searched=zeros(n,2);while~stopfori=1:nif(f(y,2)==i)M(y,2)=i;M(i,1)=i;ifi==ustop=1;break;endfork=1:nif(f(i,1)==k)M(k,2)=0;y=k;break;end,endifstop==0breakend,end,end,endFLAG3=1;break;end%%2endifFLAG4break;endendendifFLAG4break;endifFLAG3break;endend%FLAG_S,FLAG_T,MifFLAG3break;endend,end引例的求解：车辆调度问题该问题是求一个最小权最大匹配的问题，可以用一个大数（大于所有费用）减每一个费用，把问题转化为了新的费用矩阵下求最大权匹配问题。求解步骤：1）求新的费用矩阵：用一个大数（大于