xi1 xi2 j ixij xin 1
担一个工作。cij表示第i个人 做第j件事的费用,求总费用
s.tx 1 j x 2 j x ii= j1 ,2, …x n ,n j1
最低的指派方案。
j=1,2, …,n
匈牙利算法示例专题宣讲x i j0 ,1i 1 ,2 , ,n ;j 1 ,2 , ,n 7
径。
３
C
由增广路的定义可以推出下述三个结论：
1）P的路径长度必定为奇数，第一条边和最后 一条边都不属于M。
４
D
2）P经过取反操作可以得到一个更大的匹配M’。
3）M为G的最大匹配当且仅当不存在相对于M 5
E
的增广路径。
F
匈牙利算法示例专题宣讲
5
匈牙利算法
１
A
１
A
１
A
２
B
２
B
２
B
３
C
４
D
３
C
３
C
元素打√号 （3）在已经打√号的列中含◎元素 的行打√； √ （4）重复（2）（3）直到得不出 打√的行列为止 （5）对没有打√的行画一横线， 有打√的列画一纵线，这就覆盖所 有0元素的最少直线数。令这一直 线数为l。若l<n,说明必须再换当
5 ◎0
2
3
◎0 1 0
9
8
Ø0 6
√
前的系数矩阵，才能找到n个独立
9
C 、 D 、 E五项任务，每
个人完成任务所需的工时
乙8
9
6
6
6
各不相同，见表。求应如 何指派人员才能使得所用
丙 7 17 12 14 9
工时最少？
丁 15 14 6
6 10
设有n个工作，要由 n个人 戊 4 10 7 10 9
来承担，每个工作只能由一
miZ n
cijxij
个人承担，且每个人只能承
6
-6
(cij )
7
1
5
17 14
12 6
14 6
9 -7
1
0
-6
4 1 0 7 1 0 9 -4
5 0 2 0 2
2
3
0
0
0
0 10 5 7 2
9
8
0
0
4
0 6 3 6 5
-0 -0 -0 -0 -0
5 0 2 0 2
2
3
0
0
0
0 10 5 7 2
9
8
0
0
4
0 6 3 6 5
A
BC D
E
F {A,B,C,D,E,F}
1
2
3
4
5
{1,2,3,4,5}
匈牙利算法示例专题宣讲
3
二分图匹配
给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两 条边都不依附于同一个顶点，则称M是一个匹配。在工作分配的问 题中，我们给出一个可行的分配方案，就是一个匹配。
选择这样的边数最大的子集称为图的最大匹配问题如果这个匹配是 最优的（可以填补的工作岗位最多），就是最大匹配。
5 ◎0 2 0Ø 2
的0元素，为此转到第四步；若
l=n，而m<n，应回到（2）（4）
另行试探。
匈牙利算法示例专题宣讲
2 0Ø 2
Ø0 0Ø ◎0
5 7 2 √
◎0
0Ø
4
3 6 5 √
12
第四步；在没有被直线覆盖的部分中找出最小元素。 然后在行打√行每个元素减去这一最小元素，而在打√ 列的每个元素都加上这一最小元素，以保证原来0元 素不变。这样得到新系数矩阵。若得到n个独立的0元 素，则已得到最优解，否则回到第三步。
４
D
４
D
5
E
5
E
5
E
F
F
F
(1)找到某一匹配M
(2)找出一条增广路径P，通过取反操作获得更大的匹配M’代替M
(3)重复(2)操作直到找不出增广路径匈为牙利止算法示例专题宣讲
6
分配问题及其数学模型
时任
有甲、乙、丙、丁、戊五 人间员 务 A B C D E
位工人被指派去完成A、B 、 甲 12 7
9
7
8
匈牙利算法示例专题宣讲
匈牙利算法的基本原理是基于以下两个定理.
定理1 设C=(Cij)n×n是指派问题的效益矩阵 ，若将C中的任一行（或任一列）减去该行 （或该列）中的最小元素，得到新的效率矩 阵C’，则C’对应的新的指派问题与原指派问 题有相同的最优解.
定理2 效率矩阵C中独立的0元素的最多个数 等于覆盖所有0元素的最少直线数. 当独立零 元素的个数等于矩阵的阶数时就得到最优解.
(2)给只有一个0元素的列(行)中的0元素加圈，记作◎；然后划去◎ 所在 行的0元素，记作Ø ．
(3)反复进行(1)，(2)两步，直到尽可能多的0元素都被圈出和划掉为止。
5 0 2 0 2
2
3
0
0
0
0 10 5 7 2
9
8
0
0
4
0 6 3 6 5
5 ◎0 2 Ø0 2
2
3
Ø0 Ø0 ◎0
◎0 1 0 5 7 2
9
8
◎0
Ø0
4
Ø0 6 3 6 5 匈牙利算法示例专题宣讲
5 ◎ 2 Ø 2
2
3
Ø Ø ◎
◎ 10 5 7 2
9
8
◎
Ø
4
Ø 6 3 6 5 11
第三步；作最少的直线覆盖所有0元素，以确 定该系数矩阵中能找到最多的独立元素数。
（1）对没有◎的行打√
（2）在已经打√的行中所含有的0
匈牙利算法示例专题宣讲
10
第二步：进行试指派，以寻求最优解。
在(bij)中找尽可能多的独立0元素，若能找出n个 独立0元素，就以这n个独立0元素对应解矩阵(xij)中的 元素为1，其余为0，这就得到最优解。找独立0元素，
常用的步骤为：
(1)从只有一个0元素的行(列)开始，给这个0元素加圈，记作◎ 。然后划 去◎ 所在列(行)的其它0元素，记作Ø ；这表示这列所代表的任务已指派完， 不必再考虑别人了。
匈牙利算法示例专题宣讲
二分图
设G=(V,{R})是一个无向图。图的顶点集V可分割为两个互不 相交的子集X和Y（子集内部没有边） ，图任何一条边的两个 端点都分属不同的子集。则称图G为二分图。
用n个顶点X={1,2,3,4,5}表示n个工作，用m个顶点 Y={A,B,C,D,E,F}表示m个工人。
9
匈牙利算法示例专题宣讲
匈牙利法的解题步骤：
(b第ij)一，步使：在变(bi换j)的指各派行问各题列的中系都数出矩现阵0（元c素ij），为即 元素(1)；从（cij）的每行元素都减去该行的最小 (2) 再从所得新系数矩阵的每列元素中减去
该列的最小元素。
1 2 7 9 7 9 -7
8
9
6
6
A
BC D
E
F
A
B
C
D
E
F
1
2
3
4
5
A
B
C
D
EF12345A
B
C
D
E
F
1
2
3
4
匈牙5利算法示例专题宣1讲
2
3
4
5
4
匈牙利算法
１
A
增广路的定义(也称增广轨或交错轨)：若P是图
G中一条连通两个未匹配顶点的路径，并且属 ２
B
M的边和不属M的边(即已匹配和待匹配的边)在
P上交替出现，则称P为相对于M的一条增广路