车辆调度问题讲课稿.doc

《车辆调度问题讲课稿.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、精品好文档，推荐学习交流车辆调度问题设某车队有8辆车，存放在不同的地点，队长要派出其中5辆到5个工地去运货。各车从存放处调到装货地点所需费用列于下页表，问应选哪5辆车调到何处去运货，才能使各车从车所在地点调到装货地点所需的总费用最少？车地点123456781302518322719222622931191821203019328293019192223264293019242519182152120181716141618x5y1y2y3y4y5x1x2x3x4y6y7y8MATLAB程序——Kuhn-munkras算法functionsumw=kuhngong(A)n=size(A

2、,1);w=A;l=zeros(n,2);fori=1:nforj=1:nifl(i,1)

3、(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=i

4、nf;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,end仅供学习与交流，如有侵权请联系网站删除谢谢10精品好文档，推荐学习交流if~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;enden

5、dendfprintf(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

6、(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;仅供学习与交流，如有侵权请联系网站删除谢谢10精品好文档，推荐学习交流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~s

7、topfori=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,FL