得到4个独立零元素， 所以 最优解矩阵为：
0 1 0 0
0 0 1 0
0 0 0 1
1 0 0 0
第 13页
第4章 整数规划与分配问题
运筹学
任务
人员 甲 乙 丙 丁
英语
6 4 3 5
日语
7 5 1 9
德语
11 9 10 8
俄语
2 8 4 2
0 1 0 0
第4章 整数规划与分配问题
运筹学
例1
任务 人员 甲 乙 丙 丁 A 2 10 9 7 B 15 4 14 8 C 13 14 16 11 D 4 15 13 9
第4章 整数规划与分配问题
运筹学
2. 匈牙利法
第一步：变换指派问题的系数矩阵（cij）为(bij)，使在(bij)的各行各列中都出现0元素
√
√ √ √ √
0 1 3 2 0
0 6 2 0 4
3 0 0 2 4
0 2 0 3 0
3 0 3 0 6
2012-8-31
第 22页
第4章 整数规划与分配问题
运筹学
0 1 3 2 0
0 6 2 0 4
3 0 0 2 4
0 2 0 3 0
6 4 ( c ij ) 3 5
7 5 1 9
11 9 10 8
2 8 4 2
2 4 1 2
4 0 2 3
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
3 0 0 2 3
1 3 1 4 0
3 0 3 0 5
2012-8-31
第 19页
第4章 整数规划与分配问题
运筹学
1 2 4 3 0
0 6 2 0 3
3 0 0 2 3
1 3 1 4 0
3 0 3 0 5
1 2 4 3 ◎ 0
◎ 0
3
◎ 0
1 3 1 4
Ø 0
6 2
Ø 0
Ø 0
2 3
√
3
√
3 Ø 0 3 ◎ 0 5
√
√ √ √ √
2012-8-31
第 20页
第4章 整数规划与分配问题
运筹学
1 2 4 3 ◎ 0
◎ 0
3 0 ◎ 0 Ø 2 3
√
1 3 1 4 0 Ø
6 2 0 Ø最少直线数l，即l＝m=3<n=4； 第四步，变换矩阵(bij)以增加0元素：没有被直线覆盖的所有元素中的最小元素为1，然后 打√各行都减去1；打√各列都加上1，得如下矩阵，并转第二步进行试指派：
2012-8-31
第 12页
第4章 整数规划与分配问题
运筹学
4 5 4 ◎ ◎ 1 Ø 4 2 ◎ 4 3 Ø 3 7 1
第 7页
第4章 整数规划与分配问题
运筹学
第二步，试分配：
Ø 0 13 ◎ 6 0 ◎ 0 5 Ø 0 1
7 6 3
◎ 0
◎ 0
9 2 Ø 0
0 0 1 0
0 1 0 0
0 0 0 1
1 0 0 0
2012-8-31
第 8页
－5
第二步，试指派：
4 5 4 ◎ ◎ 1 Ø 4 2 ◎ 4 3 3 7 1 Ø
2012-8-31
找到 3 个独立零元素 但m=3<n=4
第 11页
第4章 整数规划与分配问题
运筹学
第三步，作最少的直线覆盖所有0元素：
4 5 4 ◎ ◎ 1 Ø 4 2 ◎ 4 3 Ø 3 7 1
例 2 有一份中文说明书，需译成英、日、德、俄四种文字。现有甲、乙、丙、丁四人，他们 将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分配任务，使总时间最少？
任务 人员 甲 乙 丙 丁 英语 日语 德语 俄语
6
7
11
2
4
5
9
8
3
1
10
4
5
9
8
2
第4章 整数规划与分配问题
运筹学
求解过程如下： 第一步，变换系数矩阵：
第4章 整数规划与分配问题
运筹学
求解过程如下： 第一步，变换系数矩阵：
2 10 9 7
15 4 14 8
13 14 16 11
4 15 13 9
-2 -4
-9
-7
0 6 0 0
13 0 5 1
11 10 7 4
2 11 4 2
运筹学
◎ 0 1 3 2 0 Ø
Ø 0
3
Ø 0
◎ 0
Ø 0
6 2
◎ 0
2
Ø 0
2 4
3
◎ 0
4
3 ◎ 0 3 Ø 0 6
总时间为28
2012-8-31
第 24页
第4章 整数规划与分配问题
运筹学
0 Ø 1 3 2 ◎ 0
Ø 0
第4章 整数规划与分配问题
运筹学
任务 人员 甲
A 2
B 15
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
第4章 整数规划与分配问题
运筹学
0 0 1 0
0 0 0 1
1 0 0 0
此分配问题的最优时间：2+4+1+8=15
2012-8-31
第 14页
第4章 整数规划与分配问题
运筹学
例3 费 用 人员 甲 工作 A 7 B 5 C 9 D 8 E 11
乙 丙
丁 戊
9 8
7 4
12 5
3 6
7 4
6 7
11 6
9 5
9
3
Ø 0
◎ 0
◎ 0
6 2
◎ 0
2
Ø 0
2 4
3
Ø 0
4
3 ◎ 0 3 Ø 0 6
总时间为28
2012-8-31
第 25页
9 6 11
第4章 整数规划与分配问题
运筹学
7 5 9 12 8 5 7 3 4 6
11 5 7 11 9 7 4 6 94 6 9 63 7 5 11 4 9 8
2 2 4 4 0
0 5 1 0 2
4 0 0 3 3
◎ 0
4
Ø 0
◎ 0
5 1
Ø 0
3 3
2
4 3 ◎ 0 1 3 5 1 Ø 0 5 2
2012-8-31
第 17页
第4章 整数规划与分配问题
运筹学
2 2 4 4 ◎ 0
◎ 0
4
Ø 0
◎ 0
5 1
Ø 0
3 3
2
√
4 √ 3 ◎ 0 1 3 5 1 √ Ø 0 5 2
√
√
√
3 4 3 ◎ ◎ 1 Ø 5 2 ◎ 4 4 Ø 2 6 0
3 0 2 2
4 1
3
0
4
0
6
0
0 5 4 0
3 4 3 ◎ ◎ 1 Ø 5 2 ◎ 4 4 ◎ Ø 2 6
2012-8-31
3 4 2 6 1
6 2 5 3 7
-1 -2
2012-8-31 第 16页
第4章 整数规划与分配问题
运筹学
2 2 4 4 0
0 5 1 0 2
4 0 0 3 3
2 3 1 5 0
4 0 3 1 5
2 2 4 4 ◎ 0
第二步：进行试分配，以寻求最优解。如果得到最优解，运算结束，否则转到第三步。 第三步：作最少的直线覆盖所有0元素。 第四步：变换矩阵(bij)以增加0元素，转到第二步。
2012-8-31
第 4页
第4章 整数规划与分配问题
运筹学
例1
任务 人员 甲 乙 丙 丁 A 2 10 9 7 B 15 4 14 8 C 13 14 16 11 D 4 15 13 9
l =m=4 < n=5
2012-8-31 第 18页
第4章 整数规划与分配问题
运筹学
2 2 4 4 ◎ 0
◎ 0
4
Ø 0
◎ 0
5 1
Ø 0
3 3
2
4 3 ◎ 0 1 3 5 1 Ø 0 5 2
1 2 4 3 0
0 6 2 0 3
2012-8-31
第 6页
第4章 整数规划与分配问题
运筹学
0 13 6 0 0 5 0 1 -0 -0
2012-8-31
11 10 7 4 -4
2 11 4 2 -2
0 6 0 0
13 0 5 1
7 6 3 0
0 9 2 0
第4章 整数规划与分配问题
运筹学
分配问题与匈牙利法
2012-8-31