(整理)《运筹学》期末考试试题及参考答案

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格式

-------------

专业资料整理