WORD格式
-------------
专业资料整理
WORD格式
------------- ∴最优方案为：
8 B1
12 B3
20 B2 A 1
A 2
A 3
2
8
10
B2
B4
B4
最小运费 Z=1×8+2×2+6×12+5×8+10×20+9×10=414
六、（8 分）有甲、乙、丙、丁四个人，要分别指派他们完成 A 、B、 C、D 四项不同的工作，每人做各项工作所消耗的时间如下表所示：
A B C D 甲 2 10 9 7 乙 15 4 14 8 丙
13 14 16 11 丁
4
15
13
9
问：应该如何指派，才能使总的消耗时间为最少？ 解：用 “匈牙利法”求解。 效率矩阵表示为：
2 10
9
7
0
8
7
5
列约简 行约简
15 4 14 8 11 0 10 4
13
14 16 11 2 3 5 0 标号
4
15 13
9
0
11
9
5
√
√
(0) 8 2 5 (0) 8 2 5
11 (0)
5 4 11 (0)
5 4 2
3 (0) 0*
2 3 (0) 0*
*
* √ 0
12
4
5
0
12
4
5
专业资料整理
WORD格式
-------------
专业资料整理
WORD格式
-------------
0 13 4 (0)
至此已得最优解：
*
6 (0) 3 10 0 0 0 1
( 0) 5 0 2 0 1 0 0
*
3 4 (0) 3
1 0 0 0
0 0 1 0
∴使总消耗时间为最少的分配任务方案为：
甲→ C，乙→ B，丙→ D，丁→ A
此时总消耗时间
W=9+4+11+4=28
七、（6 分）计算下图所示的网络从 A 点到 F 点的最短路线及其长度。
此题在“《运筹学参考综合习题》 （我站搜集信息自编） .doc”中已有。
3
5
A
4
7
B3
C3
2
B2
5 1
B1
5
4
3
C2
9
C1
5
8
4 6 4
4
D3
7
5
D2
9
E2
1
D1
4 2
E1
6
1
F 2
解：此为动态规划之“最短路问题” ，可用逆向追踪“图上标号法”解决如下：
专业资料整理
WORD格式
-------------
专业资料整理
(整理)《运筹学》期末考试试题及参考答案
