數(shù)學建模暑期培訓分配問題——匹配主要內(nèi)容基本概念Kuhn-munkras算法的MATLAB程序自編函數(shù)maxmatch的用法應用：引例的求解引例：車輛調(diào)度問題

設某車隊有8輛車，存放在不同的地點，隊長要派出其中5輛到5個工地去運貨。各車從存放處調(diào)到裝貨地點所需費用列于下頁表，問應選哪5輛車調(diào)到何處去運貨，才能使各車從車所在地點調(diào)到裝貨地點所需的總費用最少？引例：車輛調(diào)度問題123456781302518322719222622931191821203019328293019192223264293019242519182152120181716141618車地點引例：車輛調(diào)度問題123456781302518322719222622931191821203019328293019192223264293019242519182152120181716141618車地點x5y1y2y3y4y5x1x2x3x4y6y7y8基本概念

匹配：圖G=(V,E)中一些互不相鄰的邊構(gòu)成的集合M，稱為G的一個匹配；M中邊的端點稱為M滲透點；V中的其余頂點稱為M非滲透點。

理想匹配：若匹配M滲透了圖G的所有頂點，則稱M為G的理想匹配。

最大匹配：若匹配M是G中邊數(shù)最多的匹配，則稱M為G的最大匹配。

M可增長路徑：設M是圖G=(V,E)的一個匹配，P是G中的一條路徑。若P的邊在M與E-M中交替出現(xiàn)，則稱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: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;endendendMATLAB程序——Kuhn-munkras算法（續(xù)）if~ufprintf(1,‘二部圖最大權匹配運行結(jié)果\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(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,endFLAG4=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)=i;end,end,end,endforx=1:nfory=1:nif(FLAG_S(x))&(~FLAG_T(y))&(FLAG_AGL(x,y)==x)f(y,2)=x;

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~stopfori=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,endMATLAB程序——Kuhn-munkras算法（續(xù)）MATLAB程序——Kuhn-munkras算法（續(xù)）FLAG3=1;break;end%%2endifFLAG4break;endendendifFLAG4break;endifFLAG3break;endend%FLAG_S,FLAG_T,MifFLAG3break;endend,endKuhn-munkras算法的MATLAB程序程序名maxmacth.m用途：①求二部圖的最大匹配②求加權二部圖的最大權匹配3.調(diào)用格式：maxmatch(a)，其中a為二部圖的邊矩陣或加權二部圖的邊權矩陣，要求a是方陣，即二部圖的X部的頂點數(shù)與Y部的頂點數(shù)相等。程序使用說明1.求二部圖的最大匹配例1：求下圖的最大匹配自編函數(shù)maxmatch的用法a=[0,1,1,0,0;1,0,0,1,1;0,1,1,0,0;0,1,1,0,0;0,0,0,0,1];maxmatch(a)輸出：最大權匹配M={x2y1,x3y3,x4y2,x5y5}

最大權W(M)=4x5y1y2y3y4y5x1x2x3x4該圖的最大匹配為{x2y1,x3y3,x4y2,x5y5},其權為4例2：求下圖的最大匹配自編函數(shù)maxmatch的用法x1x2x3x4y1y2y3y4y5a=[1,1,0,0,0;0,1,1,0,0;0,1,0,0,1;0,0,1,1,0];maxmatch(a)輸出：最大權匹配M={x1y1,x2y2,x3y5,x4y3}最大權W(M)=4該圖的最大匹配為{x1y1,x2y2,x3y5,x4y3}2.求加權二部圖的最大權匹配例3：求下圖的最大權匹配a=[4,0,0,5,0;0,0,2,4,0;0,6,5,0,6;2,0,0,3,3];maxmatch(a)輸出：求得最大權匹配M={x1y1,x2y4,x3y2,x4y5,}最大權W(M)=17該圖的最大權匹配為{x1y1,x2y4,x3y2,x4y5}，其權為17。y1y2y3y4y5x1x2x3x44542665332自編函數(shù)maxmatch的用法

設某車隊有8輛車，存放在不同的地點，隊長要派出其中5輛到5個工地去運貨。各車從存放處調(diào)到裝貨地點所需費用列于下頁表，問應選哪5輛車調(diào)到何處去運貨，才能使各車從車所在地點調(diào)到裝貨地點所需的總費用最少？引例的求解：車輛調(diào)度問題123456781302518322719222622931191821203019328293019192223264293019242519182152120