2016年军事交通学院军事运筹学801运筹学考研强化班模拟试题及答案
● 摘要
一、简答题
1． 试说明C 一W 节约算法的基本思想，你认为还可用它解决哪些方面的问题? 举例加以说明。
【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧插入到旅行线路中， 这样在满足访问若干城市各一次且仅一次的条件下，最大限度地缩短了路程。 （2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点i 与点j 维修时间总和的一半。优先考虑将节约值最大的长度加入工作线路中去进行迭代。
2． 试写出求解最短径路的Dijkstra 算法的步骤。
【答案】Dijkstra 算法的步骤为:
（l ）给v s 以p 标号，P （v S ）二0，其余各点均给T 标号，T （v i ）=+∞。
（2）若v i 点为刚得到P 标号的点，考虑这样的点v i ，（v i ，vj ）属于E ，且v i 为T 标号。对v j 的T
，p （v i ）+lij ] 标号进行如下修改:T （v j ）=min[T（v i ）
（3）比较所有具有T 标号的点，把最小者改为P 标号，即:
3． 试简述求解整数规划模型的分枝定界法剪枝的几种情况。
【答案】（l ）某枝已经达到其范围内的最优解;
（2）某枝域内没有可行解时，即是不可行域;
（3）某枝所得数据不优于当前最优解时。
4． 简述求解整数规划分枝定界法的基本思想。
【答案】设有最大化的整数规划问题A ，与它对应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z*的上界，记作; 而A 的任意可行解的目标函数值将是z*的一个下界
域（称为分支）的方法，逐步减小和增大; 。分支定界法就是将B 的可行域分成子区:， 最终求到z*。 当存在两个以上最小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。
二、计算题
5． 银行要把总行与支行的计算机直接或间接地连接起来，保持连通，其中任意两银行之间的距离如表所示，而连接线费用为0.2万元/百米，求总费用最小的连接方案及最小总费用。
表
【答案】构建图论模型，如图所示。
图
采用破圈法，如图所示。求得最小支撑树，即为最优连接方案
图
6． 某科学试验可用1，2，3三套不同仪器中的任一套去完成。每做完一次试验后. 如果下次仍用原来的仪器，则需要对该仪器进行检查整修而中断试验:如果下次换用另外一套仪器，则需拆装仪器。也要中断试验。假定一次试验时间比任何一套仪器的整修时间都长，因此一套仪器换下来隔一次再重新使用时，不会由于整修而影响试验。设i 仪器换成j 仪器所需中断试验的时间为t ij ，如表所示。现要做4次试验，问应如何安排使用仪器的顺序，使总的中断试验的时间最小。
表 #####
【答案】设A. B. C 分别代表三套仪器1，2，3，A i 表示在第i 次实验中用仪器A ，依此类推B i . C i ，并设虚拟开始S 和结束点D 。则得网络图如图所示:
###
图
求总的中断试验的时间最小，即找最短路问题，利用Dijkstra 算法计算如下: （1） j=0, S 0={S}, P （S ）=0,
T （A i ） =T （B i ） =T （C i ） =0,
A 1, B 1, C 1到S 点距离相同，
则S 1= （S 、A 1、B 1、C 1）,
（2）
则S 2= （S 、A 1、B 1、C 1、A 2、B 2、C 2） 可同时标号
（3）
则S 3= （S 、A 1、B 1、C 1、A 2、B 2、C 2、A 3、B 3、C 3）
（4）
j=3