分配问题——匹配.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