分配问题——匹配.ppt

《分配问题——匹配.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学建模暑期培训分配问题——匹配主要内容基本概念Kuhn-munkras算法的MATLAB程序自编函数maxmatch的用法应用：引例的求解引例：车辆调度问题设某车队有8辆车，存放在不同的地点，队长要派出其中5辆到5个工地去运货。各车从存放处调到装货地点所需费用列于下页表，问应选哪5辆车调到何处去运货，才能使各车从车所在地点调到装货地点所需的总费用最少？引例：车辆调度问题123456781302518322719222622931191821203019328293019192223264293019242519182152120181716141618车

2、地点引例：车辆调度问题123456781302518322719222622931191821203019328293019192223264293019242519182152120181716141618车地点x5y1y2y3y4y5x1x2x3x4y6y7y8基本概念匹配：图G=(V,E)中一些互不相邻的边构成的集合M，称为G的一个匹配；M中边的端点称为M渗透点；V中的其余顶点称为M非渗透点。理想匹配：若匹配M渗透了图G的所有顶点，则称M为G的理想匹配。最大匹配：若匹配M是G中边数最多的匹配，则称M为G的最大匹配。M可增长路径：设M是图G=(

3、V,E)的一个匹配，P是G中的一条路径。若P的边在M与E-M中交替出现，则称P是一条M交错路径；若一条M交错路径的起点和终点都是M非渗透点，则称其为M可增长路径。基本概念最大权匹配：在加权二部图G中，边权和最大的匹配M称为G的最大权匹配。二部图的边矩阵A：A=（aij)mxn二部图的边权矩阵A：A=（aij)mxn,aij为边（xi，yj)的权，若xi与yj之间无边，则aij取0.MATLAB程序——Kuhn-munkras算法functionsumw=kuhngong(A)n=size(A,1);w=A;l=zeros(n,2);fori=1:nf

4、orj=1:nifl(i,1)

5、2)=i;endendendFLAG3=1;whileFLAG3FLAG3=0;u=0;fori=1:nif~M(i,1)u=i;break;endendendMATLAB程序——Kuhn-munkras算法（续）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;endendendfprintf(1,'}');fprint

6、f(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;whileFLAG4fori=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,endF

7、LAG4=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,endfori=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

8、)=i;end,end,end,endforx=1:nfory=1