第25页
然后划去所在的列的其他0元素， 记作Ø。
5 2 0 3 2 0 5 0 0 0 7 0 2 0 2 4
10
9 8
Ø
6
3
6
5
第26页
从只有一个0元素的列开始， 给这个0元素加圈，记
5 2

3
2 0 5 0
0 0 7 0
2 0 2 4
10
9 8
Ø
6
3
6
5
第27页
然后划去所在的行的其他0元素， 记作Ø。
第13页
若还有没有划圈的0元素，且同行 （或列）的0元素至少有二个，从剩有 0元素最少的行（或列）开始，比较这 行各0元素所在列中0元素的数目，选 择0元素少的那列的0元素加圈，然后 划掉同行同列的其他0元素，可反复进 行，直到所有的0元素都被圈出和划掉 为止。 若元素的数目m等于矩阵阶数n， 那么这分配问题的最优解已得到。若 m<n，则转下一步。
5 2

3
2
Ø Ø
7
2
Ø
5

2 4
10
9 8

3
Ø
6
Ø
6
5
第33页
第三步：作最少的直线覆盖所有的0元素， 以确定该系数矩阵中能找到最多的独立 元素数。
对没有的行，打；
对已打行中所有含0元素的列打；
再对打列中含0元素的行打；
重复上述两步，直到得不出新的打行 列为止。 对没有打行画横线，有打列画纵线， 就得到覆盖所有0元素的最少直线数。
3
第51页
下面有二种分配方案：
7 4

3 8 8
2
Ø 0
5
2
0
3
Ø
4
Ø
11
0
1
0
4

4
3
第52页
下面有二种分配方案：第一种
7 4

3 8 8
2
Ø
5
2
Ø
3
Ø
4
Ø
11

1
Ø
4

4
3
第53页
最优解如下：Z=32
0 0
1
0 0 0
0
0 1
0
0
0
0
0 1
0
0
0
1
0
0
0
1
0
0
第54页
分配问题结果如下：Z=32
J 19 24 16 20
G 20 27 15 24
R 28 20 18 19
（1）问应该如何分配工作，使所需总时间 最少？ （2）如果把上表中的数据看成创造效益的 数据，应如何指派，可使得总的效益最大？
第63页

5 1

Ø
第17页
给只有一个0元素的列的0 元素加圈，记。
Ø
6
13
7
6
0
9

5
1

Ø
3
2
0

第18页
然后划去所在的行的其他0元 素，记作Ø
Ø
6 13 7 6 3 0 9 2

5 1

Ø
Ø
第19页
给最后一个0元素加圈， 记 。 Ø
6 13 7 6 3

9 2

5 1

Ø
Ø
第20页
7 4
0
3 8 8
2
0 0
5
2
0
3
Ø
4
Ø
11
0
1
0
4

4
3
第49页
从只有一个0元素的列开始，给这个0 元素加圈，记
7 4

3 8 8
2
0 0
5
2
0
3
Ø
4
Ø
11
0
1
0
4

4
3
第50页
然后划去所在的行的其他0元素，记 作 Ø。
7 4

3 8 8
2
Ø 0
5
2
0
3
Ø
4
Ø
11
0
1
0
4

4
12
7
9
7
9
7 6 7 6 4
8
7
9
6
6
14
6
9
17 12
15
4
14
10
6
7
6
10
10
9
第23页
5
0
2
0
2
2
0
3
10
0
5
0
7
0
2
9
0
8
6
0
3
0
6
4
5
第24页
从只有一个0元素的行开始，给 这个0元素加圈，记
5 2 0 3 2 0 5 0 0 0 7 0 2 0 2 4
10
9 8
0
6
3
6
5
0
1
0
4
-2
4
3
在打列中各元素都加上这最小元素2。
7 4
0
3 8 8
2
0 0
5
2
0
3
0
0 4
0
11

第44页
0
1
0
4
0
4
3
重复第二步，寻找独立0元素。
7 4
0
3 8 8
2
0 0
5
2
0
3
0
0 4
0
11
0
1
0
4
0
4
3
第45页
从只有一个0元素的行开始，给这个0 元素加圈，记
7 4
0
3 8 8
5 2

3
2 0 5 0
Ø
0 7 0
2 0 2 4
10
9 8
Ø
6
3
6
5
第28页
从只有一个0元素的列开始， 给这个0元素加圈，记
5 2

3
2 0 5 0
Ø
0 7 0
2

2 4
10
9 8
Ø
6
3
6
5
第29页
然后划去所在的行的其他0元素， 记作Ø。
5 2

3
2
Ø Ø
7 0
2
Ø
5 0

2 4
第1页
指派问题（分配问题） (Assignment Problem) 例5 有一份中文说明书，需翻译 成英、日、德、俄四种文字，分 别记作E、J、G、R，现有甲、 乙、丙、丁四人，他们将中文说 明书翻译成英、日、德、俄四种 文字所需时间如下，问应该如何 分配工作，使所需总时间最少？
第2页
任务 人员 甲 乙
第14页
从只有一个0元素的行（或列）开 始，给这个0元素加圈，记。
0 13 6
7 6
0 9

5
1
0
0
3
0
2
0
第15页
从只有一个0元素的行（或列） 开始，给这个0元素加圈，记，
0 13 7 0
6

5
6
3
9
2

0
1
0
0
第16页
然后划去所在的列的其他0 元素，记作Ø。 Ø
6 13 7 6 3 0 0 9 2 0
第9页
任务 人员 甲 乙
E 2 10
J 15 4
G 13 14
R 4 15
丙
丁
9
7
14
8
16
11
13
9
第10页
匈牙利算法的步骤：
第一步：使分配问题的系数矩阵经 变换，在各行各列中都出现0元素： 从系数矩阵的每行元素减去该行的 最小元素。 再从所得系数矩阵的每列元素减去 该列的最小元素。 若某行已经有0元素，就不必再减了。
第59页
如何安排讲座的日程，使不能出席的学生总数最少？
解：这是一个不平衡的的分配问题，需虚设一个 讲座，且Ci,5=0 , i=1,2,..,5 生态学 能源 一 二 三 四 五 50 40 60 30 10 40 30 20 30 20 运输 60 40 30 20 10 生物 工程 20 30 20 30 30
虚设 讲座
0 0 0 0 0
第60页
最优安排为：
星期 讲座 一 生物工程 三 能源 四 运输 五 生态学
第61页
指派问题（分配问题） (Assignment Problem) 练习： 安排4个人完成4项不同 的任务，每个人完成各项工作所 消耗的时间如下表，
第62页
任务 人员 甲 乙 丙 丁
E 20 18 26 17
任务 人员 甲 乙
丙
A
12
B
7
C
9
D
7
E
9
8
7
9
17
6
12
6
14
6
9
丁
戊
15
4
14
10
6
7
6
10
10
9
第58页
例7：某学校为提高学生的学习兴趣和加强学术讨论的 气氛，决定举办生态学.能源.运输和生物工程四个学术 讲座。每个讲座每周下午举行一次，经调查，周一至 五不能出席某一讲座的学生人数如下： 生态学 一 二 三 四 五 50 40 60 30 10 能源 40 30 20 30 20 运输 60 40 30 20 10 生物工程 20 30 20 30 30