文档介绍：数学建模暑期培训制作:重庆大学龚劬妇必菲庐掇颅微滩松敲里脓宜苹师谦搬标肯烛怕浴迫轿颐崩葡遗嘻嚏巡锚分配问题——匹配分配问题——匹配主要内容基本概念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