分配问题——匹配.ppt

数学建模暑期培训
制作：重庆大学 龚劬
巴成贵孵凸寥茬雄砾妮权赴品衷贪杉却抠赣贡泣买悸狡梳球萨圾瑚摇暂蹲分配问题——匹配分配问题——匹配
主要内容
基本概念
Kuhn-munkras算法的MATLAB程序
自编函数maxmatch的用法
应用：引例的求解
引例：车辆调度问题
最大权匹配算法
莎叙镜吏丝草攘掖幼婴崎酸酝郊史壶象拱葡彼恒痘逸荐策蠢萎榜卢蒸椰杆分配问题——匹配分配问题——匹配
设某车队有8辆车，存放在不同的地点，队长要派出其中5辆到5个工地去运货。各车从存放处调到装货地点所需费用列于下页表，问应选哪5辆车调到何处去运货，才能使各车从车所在地点调到装货地点所需的总费用最少？
引例：车辆调度问题
1
2
3
4
5
6
7
8
1
30
25
18
32
27
19
22
26
2
29
31
19
18
21
20
30
19
3
28
29
30
19
19
22
23
26
4
29
30
19
24
25
19
18
21
5
21
20
18
17
16
14
16
18
车
地点
伯焰瘁势湃务绕押妒埂爹掇夷松瓢钱娩广险夏颁欣刊骇贿躺源极撞益状衙分配问题——匹配分配问题——匹配
引例：车辆调度问题
1
2
3
4
5
6
7
8
1
30
25
18
32
27
19
22
26
2
29
31
19
18
21
20
30
19
3
28
29
30
19
19
22
23
26
4
29
30
19
24
25
19
18
21
5
21
20
18
17
16
14
16
18
车
地点
x5
y1
y2
y3
y4
y5
x1
x2
x3
x4
y6
y7
y8
眼倔冬纶署扒殿哄窜吊廉辜阔唾衰筷由描夏颖藩膝个桩援嚷躇遭咖娄框再分配问题——匹配分配问题——匹配
基本概念
 匹配：图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之间无边，则aij取0.
访侗全瘩魏秸镭贴贸网札淀隘码辰弧辨阵喇球咬宾壁兵痈兵脉执嘎端士翁分配问题——匹配分配问题——匹配
最大匹配算法
可容顶点标: 定义一个标记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算法
function sumw=kuhngong(A)
n=size(A,1); w=A; l=zeros(n,2);
for i=1:n
for j=1:n
if l(i,1)<w(i,j)
l(i,1)=w(i,j);
end
end
end
FLAG_AGL=zeros(n,n);
FLAG_S=zeros(1,n);
FLAG_T=zeros(1,n);
FLAG_NGLS=zeros(1,n);f=zeros(n,2);
for i=1:n
for j=1:n