√ √
√
第 20页
1 2 4 3 0 ◎
◎
0 6 2 0 Ø
3 0 Ø 3 0 ◎ 3 3 Ø 0 5 3 0 ◎ 0 Ø 2 1 3 1 4
√
l =m=4 < n=5
√ √ √ √
√
√
2016/4/5
第 21页
1 2 4 3 ◎ 0
√
√
√
2016/4/5
第 18页
2 2 4 4 ◎ 0
2016/4/5
◎
0 5 1 Ø 0
4 ◎ 0 3 1 Ø 5 2 3 0 4 Ø 0 ◎ 0 3 2 3 1 5
1 2 4 3 0
0 6 2 0
3 0 3 0 3 3 0 5 3 0 0 2 1 3 1 4
5 1 0 7
9 5 9 6
0 4 3 0
4 0 2 3
5 1 0 7
4 0 4 1
0 4 3 0
－5
第二步，试指派：
4 ◎ 2 3
2016/4/5
5 4 ◎ 1 Ø 4 ◎ 4 3 7 1 Ø
找到 3 个独立零元素 但m=3<n=4
第 19页
1 2 4 3 0
2016/4/5
0 6 2 0
3 0 3 0 3 3 0 5 3 0 0 2 1 3 1 4
1 2 4 3 ◎ 0
◎
0 6 2 Ø 0
3 √ Ø 0 √ 3 √ √ ◎ 0 3 3 Ø 0 5 3 ◎ 0 Ø 0 2 1 3 1 4
分配问题与匈牙利法
2016/4/5
第 1页
1. 分配问题
在实际中经常会遇到这样的问题，有n 项不同的任务，需要n 个人分别完成其中的一项，但由于任务的性质和各人的专长
不同，因此各人去完成不同的任务的效率（或花费的时间或
费用）也就不同。于是产生了一个问题，应指派哪个人去完 成哪项任务，使完成 n 项任务的总效率最高（或所需时间最 少），这类问题称为分配问题或指派问题。
◎
0 5 1 Ø 0
4 ◎ 0 3 1 Ø 5 2 3 0 4 Ø 0 ◎ 0 3 2 3 1 5
第 17页
2 2 4 4 ◎ 0
◎
0 5 1 Ø 0
4 ◎ 0 3 1 Ø 5 2 3 0 4 Ø 0 ◎ 0 3 2 3 1 5
l =m=4 < n=5
2016/4/5
第 4页
例1
任务 人员 甲 乙 丙 丁
A 2 10 9 7
B 15 4 14 8
C 13 14 16 11
D 4 15 13 9
求解过程如下：
第一步，变换系数矩阵：
2 10 9 7
2016/4/5
15 4 14 8
13 14 16 11
4 -2 15 -4 13 -9 -7 9
任务 人员 甲 乙 丙 丁 英语 日语 德语 俄语
6 4 3 5
7 5 1 9
11 9 10 8
2 8 4 2
求解过程如下： 第一步，变换系数矩阵：
6 4 (cij ) 3 5
7 11 2 2 5 9 8 4 1 10 4 1 9 8 2 2
4 0 2 3
0 13 11 2 6 0 10 11 0 5 7 4 0 1 4 2
第 6页
0 13 11 2 6 0 10 11 0 5 7 4 0 1 4 2
-0
2016/4/5
0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0
例1
任务 人员 甲 乙 丙 丁
A 2 10 9 7
B 15 4 14 8
C 13 14 16 11
D 4 15 13 9
2. 匈牙利法
第一步：变换指派问题的系数矩阵（cij）为(bij)，使在(bij) 的各行各列中都出现0元素
第二步：进行试分配，以寻求最优解。如果得到最优解，
运算结束，否则转到第三步。 第三步：作最少的直线覆盖所有0元素。 第四步：变换矩阵(bij)以增加0元素，转到第二步。
-0
-4
-2
第 7页
第二步，试分配：
Ø 13 7 ◎ 0 0 6 0 ◎ 6 9 ◎ 0 5 3 2 ◎ Ø Ø 1 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
1 0 0 0
2016/4/5
第 8页
任务 人员 甲
A 2
B 15
2016/4/5
第 12页
4 ◎ 2 3
5 4 ◎ √ Ø 1 4 ◎ 4 3 7 1 Ø√ √
3 ◎ 2 2
4 3 ◎ 1 Ø 5 ◎ 4 4 6 0 Ø
3 4 3 0 0 1 0 5 2 0 4 4 2 6 0 0
2016/4/5
Ø 0
3
Ø 0 ◎ 0 2
◎
0 2 0 Ø 3
Ø 0
6 2 ◎ 0 4
4
3 ◎ 0 3 Ø 0 6
总时间为28
第 25页
6 2 5 3 2 3 1 7 4 0 0 3 3 4 2 6
-1 -2
第 16页
2 2 4 4 0
2016/4/5
0 5 1 0
4 0 3 1 2 3 0 5 4 0 0 3 2 3 1 5
2 2 4 4 ◎ 0
◎
0 6 2 Ø 0
3 Ø 0 3 ◎ 0 3 3 Ø 0 5 3 ◎ 0 Ø 0 2 1 3 1 4
√ √
√ √ √ √
0 1 3 2 0
3 0 3 0 4 4 0 6 0 6 2 0 3 0 0 2 0 2 0 3
√
2016/4/5
德语
11 9 10 8
俄语
2 8 4 2
0 1 0 0
0 0 1 0
0 0 0 1
1 0 0 0
此分配问题的最优时间：2+4+1+8=15
2016/4/5
第 14页
例3 费 用 人员 甲 工作 A 7 B 5 C 9 D 8 E 11
乙 丙
丁 戊
9 8
7 4
12 5
C 13
D 4
乙
丙 丁
10
9 7
4
14 8
14
16 11
15
13 9
0 0 1 0
0 1 0 0
0 0 0 1
1 0 0 0
此分配问题的最优时间：4+4+9+11=28
例 2 有一份中文说明书，需译成英、日、德、俄四种文字。现有甲、乙、丙、丁四人，他们 将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分配任务，使总时间最少？
第 22页
0 1 3 2 0
3 0 3 0 4 4 0 6 0 6 2 0 3 0 0 2 0 2 0 3
Ø 0 1 3 2 ◎ 0
◎
0 6 2 Ø 0
3 Ø 0 3 ◎ 0 Ø 6 4 4 0 3 ◎ 0 0 Ø 2 0 Ø 2 0 ◎ 3
3 6
7 4
6 7
11 6
9 5
9
9 6 11
7 9 8 7 4
2016/4/5
5 9 8 11 5 12 7 11 9 7 5 4 6 94 3 6 9 63 6 7 5 11 4
2 2 4 4 0
0 5 1 0
总时间为28
此问题有多个最优解
2016/4/5
第 23页
◎ 0 1 3 2 Ø 0
Ø 0
3
Ø 0 ◎ 0 2
Ø 0
6 2 ◎ 0 42 0 Ø 3Fra bibliotek◎ 0
4
3 ◎ 0 3 Ø 0 6
总时间为28
第 24页
2016/4/5
0 Ø 1 3 2 ◎ 0
第 11页
第三步，作最少的直线覆盖所有0元素：
4 ◎ 2 3
5 4 ◎ √ 1 Ø 4 ◎ 4 3 √ Ø 7 1 √
独立零元素的个数m等于最少直线数l，即l＝m=3<n=4； 第四步，变换矩阵(bij)以增加0元素：没有被直线覆盖的所有元素中的最小元素为1，然后 打√各行都减去1；打√各列都加上1，得如下矩阵，并转第二步进行试指派：
0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0
第 13页
3 ◎ 2 2
2016/4/5
4 3 1 Ø ◎ 4 6 ◎
◎
5 4 Ø
得到4个独立零元素， 所以 最优解矩阵为：
任务
人员 甲 乙 丙 丁
英语
6 4 3 5
日语
7 5 1 9