3.3匈牙利算法

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

3
Ø
6
Ø
6
5
对没有打行画横线

5 2

3
2
Ø Ø
7
2
Ø
5

2 4
10
9 8

第38页

3
Ø
6
Ø
6
5
有打列画纵线
5 2

3
2
Ø Ø
7
2
Ø
5

2 4
10
9 8

第39页

3
Ø
6
Ø
6
5
第四步：在没有被直线覆盖的部 分中找出最小元素，然后在打 行各元素都减去这最小元素，而 在打列中各元素都加上这最小 元素，以保证原来0元素不变， 这样得到新的系数矩阵（它的最 优解和原问题相同）。若得到n 个独立的0元素，则已经得到最 优解。否则回到第三步重复进行。
10
9 8
Ø
6
3
6
5
第30页
从只有一个0元素的列开始， 给这个0元素加圈，记
5 2

3
2
Ø Ø
7 0
2
Ø
5

2 4
10
9 8

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

3
2
Ø Ø
7
2
Ø
5

2 4
10
9 8

3
Ø
6
Ø
6
5
第32页
的个数m=4,而n=5, m<n，转下 一步。
第4页
引入0-1变量xij=1分配第i人去完 成第j 项任务，xij=0不分配第i人去完 成第j 项任务。
分配问题的数学模型：
Min Z= cijxij
s.t. xij =1 (j=1,2……n) xij =1 (i=1,2……n) xij 0或1 (i=1,2…..n; j=1,2……n)
J 19 24 16 20
G 20 27 15 24
R 28 20 18 19
（1）问应该如何分配工作，使所需总时间 最少？ （2）如果把上表中的数据看成创造效益的 数据，应如何指派，可使得总的效益最大？
第63页
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
E 2 10
J 15 4
G 13 14
R 4 15
丙
丁
9
7
14
8
16
11
13
9
第3页
类似有：有n项加工任务，怎样 分配到n台机床上分别完成；有n 条航线，怎样指定n艘船分别去 航行….. 等。 表中数据称为效益矩阵或系数矩 阵，其元素大于零，表示分配第 i人去完成第j 项任务时的效益 （或时间、成本等）。
第11页
2 15 13
(cij)= 10 4 14
4
15 13
2
4 9 7 0 13 11 6 0 0 5 1 10 7 4 4 2 11 4 2 2
9 14 16
7
8 11
9
0 13 6 0 0 5
7 6 3
0 9 2
0
0
1
0
0
第12页
第二步：进行试分配，以寻找最优解。 从只有一个0元素的行（或列）开 始，给这个0元素加圈，记，然后 划去所在的列（或行）的其他0元 素，记作Ø。 给只有一个0元素的列（或行）的0 元素加圈，记，然后划去所在的 行（或列）的其他0元素，记作Ø。 反复进行上述两步，直到所有的0 元素都被圈出和划掉为止。
第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元素， 记作Ø。
第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
第5页
xij =1 (j=1,2……n)表示
第j 项任务只能由一人去完成。
xij =1 (i=1,2……n)
第i人只能完成一项任务。 满足约束条件的解称为可行解可写成 矩阵形式：
0 1 0 0
X= 0 0 1 1 0 0 1
0 0 0
0 0
称为解矩阵其 各行各列元素 之和为1。
第6页
匈牙利算法依据： 对同一工作i来说，所有机床的效 率都提高或降低同一常数，不会 影响最优分配；同样，对同一机 床j来说,做所有工作的效率都提高 或降低同一常数，也不会影响最 优分配。
任务 人员 甲 乙
丙
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
第55页
下面有二种分配方案：第二种
7 4

3 8 8
2
Ø Ø
5
2

3
Ø
4
Ø
11
Ø
1

4

4
3
第56页
最优解如下：Z=32
0 0
1
0 0 0
0
0 0
0
0
1
0
0 1
0
0
0
0
0
1
0
1
பைடு நூலகம்
0
0
第57页
分配问题结果如下：Z=32
2
0 0
5
2
0
3
0
0 4
0
11
0
1
0
4

4
3
第46页
然后划去所在的列的其他0元素，记 作 Ø。
7 4
0
3 8 8
2
0 0
5
2
0
3
0
0 4
Ø
11
0
1
0
4

4
3
第47页
从只有一个0元素的行开始，给这个0 元素加圈，记
7 4
0
3 8 8
2
0 0
5
2
0
3
0
4
Ø
11
0
1
0
4

4
3
第48页
然后划去所在的列的其他0元素，记 作 Ø。
任务 人员 甲 乙
丙
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
第7页
•匈牙利法基本思想：通过变换修改系数矩阵 的行和列的元素，使在每一行或每一列中至少 有一个0元素，直到在不同行、不同列中至少有 一个0元素，从而得到与这些0元素相对应的一 个完全分配方案。 •关键：寻找n个独立0元素。
第8页
例5 有一份中文说明书，需翻译 成英、日、德、俄四种文字，分 别记作E、J、G、R，现有甲、 乙、丙、丁四人，他们将中文说 明书翻译成英、日、德、俄四种 文字所需时间如下，问应该如何 分配工作，使所需总时间最少？
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

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页
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
第1页
指派问题（分配问题） (Assignment Problem) 例5 有一份中文说明书，需翻译 成英、日、德、俄四种文字，分 别记作E、J、G、R，现有甲、 乙、丙、丁四人，他们将中文说 明书翻译成英、日、德、俄四种 文字所需时间如下，问应该如何 分配工作，使所需总时间最少？
第2页
任务 人员 甲 乙
5 2

3
2
Ø Ø
7
2
Ø
5

2 4
10
9 8

3
Ø
6
Ø
6
5
第33页
第三步：作最少的直线覆盖所有的0元素， 以确定该系数矩阵中能找到最多的独立 元素数。
对没有的行，打；
对已打行中所有含0元素的列打；
再对打列中含0元素的行打；
重复上述两步，直到得不出新的打行 列为止。 对没有打行画横线，有打列画纵线， 就得到覆盖所有0元素的最少直线数。
可见m=n=4,得到最优解。
0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0
即甲译俄文、乙译日文、丙 译英文、丁译德文所需时间 最少。Z=28小时
第21页
例6 分配问题效率矩阵
任务 人员 甲 乙
丙
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
第22页
第13页
若还有没有划圈的0元素，且同行 （或列）的0元素至少有二个，从剩有 0元素最少的行（或列）开始，比较这 行各0元素所在列中0元素的数目，选 择0元素少的那列的0元素加圈，然后 划掉同行同列的其他0元素，可反复进 行，直到所有的0元素都被圈出和划掉 为止。 若元素的数目m等于矩阵阶数n， 那么这分配问题的最优解已得到。若 m<n，则转下一步。
第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
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
第40页
没有被直线覆盖的最小元素为2
5 2

3
2
Ø Ø
7
2
Ø
5

2 4
10
9 8

第41页

3
Ø
6
Ø
6
5

5 2
0
3 10 8
2
0 0
7
2
0
5
0
2 4
0
9

第42页
0
3
0
6
0
6
5
在打行各元素都减去这最小元素2。
5 2
0
3 8 8
2
0 0
5
2
0
3
0
0 4
-2
9

第43页
虚设 讲座
0 0 0 0 0
第60页
最优安排为：
星期 讲座 一 生物工程 三 能源 四 运输 五 生态学
第61页
指派问题（分配问题） (Assignment Problem) 练习： 安排4个人完成4项不同 的任务，每个人完成各项工作所 消耗的时间如下表，
第62页
任务 人员 甲 乙 丙 丁
E 20 18 26 17
第9页
任务 人员 甲 乙
E 2 10
J 15 4
G 13 14
R 4 15
丙
丁
9
7
14
8
16
11
13
9
第10页
匈牙利算法的步骤：
第一步：使分配问题的系数矩阵经 变换，在各行各列中都出现0元素： 从系数矩阵的每行元素减去该行的 最小元素。 再从所得系数矩阵的每列元素减去 该列的最小元素。 若某行已经有0元素，就不必再减了。
第34页
对没有的行，打
5 2

3
2
Ø Ø
7
2
Ø
5

2 4
10
9 8

3
Ø
6
Ø
6
5

第35页
对已打行中所有含0元素的列打

5 2

3
2
Ø Ø
7
2
Ø
5

2 4
10
9 8

3
Ø
6
Ø
6
5

第36页
再对打列中含0元素的行打
5 2

3
2
Ø Ø
7
2
Ø
5

2 4
10
9 8

第37页