物流运筹学复习题及答案

?11?7?(0?4)?0;?12?8?(0?2)?0?14?2?(0?1)?0;?21?7?(4?2)?0 ?33?9?(3?0)?0;?34?6?(?1?0)?0 故这时的方案为最优，这时的运输方案为 销地 产地 B1 20 B2 10 20 B3 10 30 B4 50 A1 A2 A3 总运费为390百元。

2、某公司生产糖果，它有三个加工厂A1,A2,A3，每月产量分别为7吨，4吨，9吨。

该公司把这些产品分别运往四个销售店B1,B2,B3,B4，每月的销售量分别为3吨，6吨，5吨，6吨，已知从第i个加工厂到第j个销售店的每吨糖果的运价如表所示，请确定在满足各销售店需求量的前提下，各加工厂到各销售店的每月调运方案，使该公司所花的总运费最小。

收点发点 A1 A2 B1 B2 B3 B4 3 7 1 11 4 9 3 10 2 10 5 8 A3 解：用伏格尔法得到初始方案如下

收点发点 A1 B1 B2 B3 B4 产量 行位势 3 7 1 4 2 11 5 4 3 0 10 10 7 0 A2 5 4 -7 A3 9 2 8 9 -2 5

3 6 销量 3 6 5 6 列位势 3 11 3 10 用位势法进行检验令u1?0由u1?v2?11得v2?11；

由u2?v2?4得u2??7；由u1?v3?3得v3?3 由u1?v4?10得v4?10；由u3?v4?8得u3??2 由u3?v1?1得u3?3 计算各空格的检验数

?11＝3?(3?0)＝0;?21＝7-(-7+3)?0?23?10?(?7?3)?0;?24?5?(?7?10)?0 ?32?9?(11?2)?0;?33?2?(3?2)?0故得到的方案为最优。这时的最优方案为

收点发点 B1 B2 B3 B4 A 2 5 0 1 A 4 2 A3 6 3 总运费为104。

四、用匈牙利法求解最小指派问题

??482103?297?1、?97其损益矩阵如下??74275?? ?94235????10106910????482103?6081??7???97297??2??5075???4?64?解：??7427???75?2053?????53?3??42???94235?2013????5?7???5???2???10106910????44034????22?23??进行增零变换得到

6

??4??31?3???5?????从而得到最优指派方案为

????42??42?

???2???1???73????2???? 4??3???10???

2、 有A、B、C、D四项任务需分派给甲、丙、丁四个人去做，这四个人都能承担上述

四项任务，但完成任务所需要的时间如表所示，问应如何分派任务，可使完成四项任务的总工时最小？ 任务 A 人 甲 乙 丙 丁 8 13 9 7 17 8 17 9 14 15 16 11 17 17 7 9 B C D ?8171417??096???1381517507????解：

?917167??2109???79119???024从而得到最优指派方案为

9???92??9??5?3?0??2105??2???2?9??9? ???2??8???8?? ?7???11??五、用Dijkstra算法求解最短路问题

1、求①到⑦的最短路长与最短路径

7

解：令P(1)?0,T(i)??,i?2,3,?,7 以①为起点，进行第一步迭代

T(2)?min{?,P(1)?T12}?min{?,0?4}?4T(3)?min{?,P(1)?T13}?min{?,0?3}?3 T(5)?min{?,P(1)?T15}?min{?,0?5}?5比较后，给③永久性编号P(3)?3 以③为起点，进行第二步迭代

T(6)?min{?,P(3)?T36}?min{?,3?2}?5

比较后，给②永久性编号P(2)?4 以②为起点，进行第三步迭代

T(5)?min{5,P(2)?T25}?min{5,4?1}?5

比较后，给⑤永久性编号P(5)?5 以⑤为起点，进行第四步迭代

T(4)?min{?,P(5)?T54}?min{?,5?3}?8 T(6)?min{5,P(5)?T56}?min{5,5?1}?5

比较后，给⑥永久性编号P(6)?5 以⑥为起点，进行第五步迭代

T(4)?min{8,P(6)?T64}?min{8,5?2}?7T(7)?min{?,P(6)?T67}?min{?,5?4}?9

比较后，给④永久性编号P(4)?7 以④为起点，进行第六步迭代

8