2016年上海财经大学信息管理与工程学院运筹学复试笔试仿真模拟题
● 摘要
一、计算题
1． 在图中，（l ）用Dijkstra 方法求从v l 到各点的最短路; （2）指出对v l 来说，哪些顶点是不可到达的。
图
【答案】（1）
①v1已经获得P 标号，
计算从v l 到各点的最短路的步骤如下:
，修改v2，v5，v7的T 标号
因为
②v5已经获得P 标号
，
，改写v6的T
标号为
，所以有
。
于是，有v 1到各点v 2，v 5，v 7，v 6，v 8的最短路为
（2）v 1不能到达v 3及v 4。
2． 商品A 的需求量等已知数据如表所示。
表
每出售一件A 可盈利5元，售不出则损失3元/件。求【答案】
表
第 2 页，共 58 页
，
因为
3． 有四项工作A 、B 、C 、D 分别由甲、乙、丙、丁四个人来完成，各人完成各项任务所花费的时间（单位: 天）如下。试求解每人都承担一项工作的最优分配方案
表
【答案】该问题是指派问题，且是求目标最小。因此用匈牙利方法计算如下:
初次分配，矩阵中。个数小于4，因此对矩阵找出最少覆盖O 元素直线
进行计算后得到另一矩阵
重新分配如下:
一A ，丙一D ，丁一B 。
，的个数为4，因此指派成功，即最优的支配方案是:甲一C ，乙
第 3 页，共 58 页
4． 某科学试验可用l#、2#，3#三套不同仪器中的任一套去完成。每做完一次试验后，如果下次仍用原来的 仪器，则需要对该仪器进行检查整修而中断试验:如果下次换用另外一套仪器，则需拆装仪器，也要中断试验。 假定一次试验时间比任何一套仪器的整修时间都长，因此一套仪器换下来隔一次再重新使用时，不会由于整修而 影响试验。设i#仪器换成j#仪器所需中断试验的时间为t ij ，如表所示。现要做4次试验，问应如何安排使用 仪器的顺序，使总的中断试验的时间最小?
表
【答案】设A 、B 、c 分别代表三套仪器l#、2#，3#，A i 表示在第i 次实验中用仪器A ，依此类推B i 、C i ，并设虚拟开始S 和结束点D 。则得如图所示网络图:
图
求总的中断试验的时间最小，即找最短路问题，利用Dijkstra 算法计算如下:
到S 点距离相同，
则
可同时标号
（4）
第 4 页，共 58 页
相关内容
相关标签