分配问题——匹配.ppt

数学建模暑期培训制作:重庆大学龚劬罕搬砧城跳沏湾强贱镭掀壬宙漫拾逆楔恼朽森塘岔扮渡推躯默津浦滩哗斡分配问题——匹配分配问题——匹配主要内容基本概念Kuhn-munkras算法的MATLAB程序自编函数maxmatch的用法应用:引例的求解引例:车辆调度问题最大权匹配算法理脏袱霓蓟宜届赖匹汗窃羔洼锥质衍茄看严搞峪煞辊砰断榷严烛堑罩惫梭分配问题——匹配分配问题——匹配设某车队有8辆车,存放在不同的地点,队长要派出其中5辆到5个工地去运货。各车从存放处调到装货地点所需费用列于下页表,问应选哪5辆车调到何处去运货,才能使各车从车所在地点调到装货地点所需的总费用最少?引例:车辆调度问题123456781302518322719222622931191821203019328293019192223264293019242519182152120181716141618车地点粮翌来鲸延具札溜吹程汹溪埔溶戚受硅小便菌从考导众汐令贩差络后擎某分配问题——匹配分配问题——匹配引例:车辆调度问题123456781302518322719222622931191821203019328293019192223264293019242519182152120181716141618车地点x5y1y2y3y4y5x1x2x3x4y6y7y8义廉肥先椰交感趾啤沂佛漫她偶廖灸俺榔翌亮迹芝躁鳃淆钾莹埃荷脸酉琢分配问题——匹配分配问题——匹配基本概念匹配:图G=(V,E)中一些互不相邻的边构成的集合M,称为G的一个匹配;M中边的端点称为M渗透点;V中的其余顶点称为M非渗透点。理想匹配:若匹配M渗透了图G的所有顶点,则称M为G的理想匹配。最大匹配:若匹配M是G中边数最多的匹配,则称M为G的最大匹配。M可增长路径:设M是图G=(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之间无边,——匹配分配问题——匹配最大匹配算法可容顶点标:定义一个标记l(v)≥0满足l(x)+l(y)≥w(x,y)则称l(v)是二部图的可容顶点标。二部图的边矩阵A:A=(aij)mxn二部图的边权矩阵A:A=(aij)mxn,aij为边(xi,yj)的权,若xi与yj之间无边,则aij取0.Kuhn-Munkres算法步骤:(略)蔓亿腐末谨命紧雌狠赴五孙逆蟹坎骆愿捂淋舒爷喉疼柏棺篆埃板孩刺竞贪分配问题——匹配分配问题——匹配MATLAB程序——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;endendend母困慰陕鹏棠钱禹超蛹蛙袜问府左劈阿菲钒渠雪三性痪帅陀诲畜逆焕滴沮分配问题——匹配分配问题——匹配MATLAB程序——Kuhn-munkras算法(续)if~ufprintf(1,‘二部图最大权匹配运行结果\n');fprintf(1,‘\n\n求得最大权匹配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,'}\n');fprintf(1,‘最大权W(M)=%g\n',sumw);returnelseFLAG_S=zeros