C
D E F Nhomakorabea匈牙利算法
１
２ ３
A
B C
１
２ ３ ４ 5
A
B C D E F
１ ２
A B
３
４ 5
C
D E
４
5
D
E F
F
(1)找到某一匹配M (2)找出一条增广路径P，通过取反操作获得更大的匹配M’代替M (3)重复(2)操作直到找不出增广路径为止
分配问题及其数学模型
有甲、乙、丙、丁、戊五 位工人被指派去完成A、B 、 C 、 D 、 E五项任务，每 个人完成任务所需的工时 各不相同，见表。求应如 何指派人员才能使得所用 工时最少？

二分图


设G=(V,{R})是一个无向图。图的顶点集V可分割为两个互不 相交的子集X和Y（子集内部没有边） ，图任何一条边的两个 端点都分属不同的子集。则称图G为二分图。 用n个顶点X={1,2,3,4,5}表示n个工作，用m个顶点 Y={A,B,C,D,E,F}表示m个工人。
A
B
C
D
E
F
{A,B,C,D,E,F}
2 0 2 4 5
-0 -0 -0 -0 -0
第二步：进行试指派，以寻求最优解。 在 (bij) 中找尽可能多的独立 0 元素，若能找出 n 个 独立 0元素，就以这 n个独立 0元素对应解矩阵 (xij)中的 元素为1，其余为0，这就得到最优解。找独立0元素， 常用的步骤为：
B C A B
C D E F
A
D
E
F
1
A B
2
C
3 D
4 E
5
F A
1 B
2 C
3 D
4
5
E
F
1
2
3
4
5
1
2
3
4
5
匈牙利算法

１
A
B
增广路的定义(也称增广轨或交错轨)：若P是图 G中一条连通两个未匹配顶点的路径，并且属 ２ M的边和不属M的边(即已匹配和待匹配的边)在 P上交替出现，则称P为相对于M的一条增广路 径。 ３ 由增广路的定义可以推出下述三个结论： 1）P的路径长度必定为奇数，第一条边和最后 ４ 一条边都不属于M。 2）P经过取反操作可以得到一个更大的匹配M’。 3）M为G的最大匹配当且仅当不存在相对于M 5 的增广路径。
7 ◎ 2 Ø 2 4 3 Ø Ø ◎ Ø 8 3 5 ◎ 11 8 4 ◎ Ø ◎ 4 1 4 3
上面矩阵有5个独立0元素，这就得到相应的最优解。
0 0 0 0 1
1 0 0 0 0
0 1 0 0 0
0 0 0 1 0
1
2
3
4
5
{1,2,3,4,5}
二分图匹配


给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两 条边都不依附于同一个顶点，则称M是一个匹配。在工作分配的问 题中，我们给出一个可行的分配方案，就是一个匹配。 选择这样的边数最大的子集称为图的最大匹配问题如果这个匹配是 最优的（可以填补的工作岗位最多），就是最大匹配。
5 0 2 0 2 3 0 0 0 10 5 7 9 8 0 0 0 6 3 6
2 0 2 4 5
5 2 ◎ 0 9 0 Ø
0 ◎ 3 10 8 6
2 Ø 0 2 0 Ø 0 ◎ 0 Ø 5 7 2 ◎ 0 Ø 0 4 3 6 5
5 2 ◎ 0 9 0 Ø √
0 2 0 ◎ Ø 2 3 Ø 0 0 0 Ø ◎ 10 5 7 2 √ 8 ◎ 0 0 Ø 4 6 3 6 5 √
第四步；在没有被直线覆盖的部分中找出最小元素。 然后在行打√行每个元素减去这一最小元素，而在打√ 列的每个元素都加上这一最小元素，以保证原来0元 素不变。这样得到新系数矩阵。若得到n个独立的0 元素，则已得到最优解，否则回到第三步。
(1)从只有一个0元素的行(列)开始，给这个0元素加圈，记作◎ 。然后划 去◎ 所在列(行)的其它0元素，记作Ø ；这表示这列所代表的任务已指派完， 不必再考虑别人了。 (2)给只有一个0元素的列(行)中的0元素加圈，记作◎；然后划去◎ 所在 行的0元素，记作Ø ． (3)反复进行(1)，(2)两步，直到尽可能多的0元素都被圈出和划掉为止。
5 2 ◎ 9 Ø
◎
3 10 8 6
2 Ø 2 Ø Ø ◎ 5 7 2 ◎ Ø 4 3 6 5
第三步；作最少的直线覆盖所有0元素，以确 定该系数矩阵中能找到最多的独立元素数。
（1）对没有◎的行打√ （2）在已经打√的行中所含有的0 元素打√号 （3）在已经打√号的列中含◎元 素的行打√； √ （4）重复（2）（3）直到得不出 打√的行列为止 （5）对没有打√的行画一横线， 有打√的列画一纵线，这就覆盖所 有0元素的最少直线数。令这一直 线数为l。若l<n,说明必须再换当 前的系数矩阵，才能找到n个独立 的0元素，为此转到第四步；若 l=n，而m<n，应回到（2）（4） 另行试探。
12 8 (cij ) 7 15 4
-7 -6 -7 -6 -4
5 0 2 0 2 3 0 0 0 10 5 7 9 8 0 0 0 6 3 6
2 0 2 4 5
5 0 2 0 2 3 0 0 0 10 5 7 9 8 0 0 0 6 3 6
•
非标准型的指派问题：
匈牙利法的条件是：模型求最小值、效率cij≥0。 当遇到各种非标准形式的指派问题时，处理方法是先将 其转化为标准形式， 1、人数和事数不相等的指派问题：人少事情多，虚拟 “人”，做各事的费用系数为0；人多事情少，虚拟 “事”，各人做的费用系数为0。 2、对于求极大化的问题，只要系数矩阵变换为B＝（mcij）nn，仍可利用匈牙利算法进行求解。 3、一个人可以做几件事情的指派问题：可以将该人化 作相同的几个“人”来接受指派，费用一样。 4、某事一定不能由某人做的指派问题，费用系数为“ M” 然后用匈牙利法来求解。

8
匈牙利算法的基本原理是基于以下两个定理. 定理1 设C=(Cij)n×n是指派问题的效益矩阵， 若将C中的任一行（或任一列）减去该行 （或该列）中的最小元素，得到新的效率矩 阵C’，则C’对应的新的指派问题与原指派问 题有相同的最优解. 定理2 效率矩阵C中独立的0元素的最多个数 等于覆盖所有0元素的最少直线数. 当独立零 元素的个数等于矩阵的阶数时就得到最优解.

9
匈牙利法的解题步骤：


第一步：变换指派问题的系数矩阵（cij）为 (bij)，使在(bij)的各行各列中都出现0元素，即 (1) 从（cij）的每行元素都减去该行的最小 元素； (2) 再从所得新系数矩阵的每列元素中减去 该列的最小元素。
7 9 7 9 9 6 6 6 17 12 14 9 14 6 6 10 10 7 10 9
匈牙利算法
经典问题——工作分配
一个公司有n个工作岗位空缺，每个岗位空 缺需要有一定资格的人来填补。现在有m个 人申请这n个工作。由于每个人工作能力不 同，所以不同的人能胜任不同的工作。 现在已知每个人所能胜任的若干工作，求 这m个人最多可以填补几个工作岗位。 每个人只能做一份工作，每个工作岗位也 只需要一个人
0 0 1 0 0
或
0 0 0 0 1
1 0 0 0 0
0 0 0 1 0
0 1 0 0 0
0 0 1 0 0
解矩阵得到2个最优指派方案；（1）甲-B，乙-C， 丙--E，丁-D,戊-A；（2）甲-B，乙-D，丙-E,丁-C， 戊-A。所需时间为minz=7+6+9+6+4=32
xi1 xi 2 xij xin 1 i=1,2, …,n s.t x1 j x2 j xij xnj 1 j=1,2, …,n xij 0,1 i 1,2,, n; j 1,2,, n
j i
min Z cij xij
5 2 ◎ 0 9 0 Ø
+2
√ ×
0 Ø 2 0 0 Ø ◎ 10 5 7 2 √ -2 8 ◎ 0 0 4 Ø 6 3 6 5 √ -2 0 2 ◎ 3 Ø 0
7 4 Ø 11 ◎
◎ 2 Ø 2 3 ◎ Ø Ø 8 3 5 ◎ 8 Ø ◎ 4 4 1 4 3
时 任 间 务 人员
A 12 8 7 15 4
B 7 9 17 14 10
C 9 6 12 6 7
D 7 6 14 6 10
E 9 6 9 10 9
甲 乙 丙 丁 戊
设有n个工作，要由 n个人 来承担，每个工作只能由一 个人承担，且每个人只能承 担一个工作。cij表示第i个人 做第j件事的费用,求总费用 最低的指派方案。
15
请各位老师和同学批评指导！