当前位置:问答库>考研试题

2016年上海对外经贸大学运筹学(同等学力加试)复试笔试最后押题五套卷

  摘要

一、计算题

1. 求图中,从任意一点到另外任一点的最短路。

【答案】用Dijtstra 算法寻求最短路,计算结果如表所示。

从表可以得出任意一点到另外任一点的最短路。 (l )从v 1开始到各点的最短路。

(2)从v 2开始到v j 的最短路。

V 2不能到达v l ,故对v 2而言,v 1为不可达点。 (3)从v 3出发到各点的最短路。

v 3不能到达v l 和v 2,故v 1,v 2为v 3的不可达点。

,且d (v 4,v 6)=3。 (4)从v 4出发,只有一条路(v 4,v 6)

,且d (v 5,v 6)=6。 (5)从v 5出发,只有一条路(v 5,v 6)

(6)从v 6出发,则无路。

2. 用表上作业法求表1至表4中给出的运输问题的最优解(表中数字M 为任意大正数)。

表1 表

2

表3 表

4

【答案】(l ) 解表1

,求得的初始解如表5所示。 第一步:用伏格尔法求初始可行解(过程类似于上一题,不再赘述)

表5

第二步:用位势法进行最优解的判断。在对应于表5的数字格处填入单位运价,并增加一行一列,在行中填入v j ,在列中填入

,。令v 1=0,并按照

表6 表

7

求出所有的

和v j ,如

表6所示。对于表16中的空格,依据

计算其检验数,如表7所示。

由表7可知,所有空格处的检验数均为非负。所以,表5中的运输方案,即为此问题的最优调运方案, 最小运价为32。由于非基变量的检验数中(2)解表2

第一步:用伏格尔法求初始可行解,求得的初始解,如表8所示。

8

,所以该运输问题有无穷多最优解。

第二步:用位势法进行最优解的判断。在对应于表8的数字格处填入单位运价,并增加一行一列,在行 中填入v j ,

在列中填入

。令u 1=0,

按照

表9

求出所有的

和v j ,

并依据

计算所 有空格处的检验数,计算结果如表9所示。