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所示。