2016年浙江海洋学院工程硕士运筹学复试笔试最后押题五套卷
● 摘要
一、计算题
1． 某工厂的100台机器，拟分四个周期使用，在每一周期有两种生产任务。据经验，把x 1台机器投入第一种生产任务，则在一个生产周期中将有x 1/3台机器报废; 余下的机器全部投入第二种生产任务，则有1/10机器报废，如果于第一种生产任务每台机器可收益10，于第二种生产任务每台机器可收益7，问怎样分配机器，使总收入最大?
【答案】按周期将该问题划分为四个阶段，第k 阶段为第k 周期分配机器; 状态变量周期初的完好机器数:决策变量周期用于第二种任务的机器台数; 状态转移方程为:
;
阶段指标务的总收益，
大值。于是有递推关系：
其中k=3, 2, 1；f 5（s 5）=0。
，最优解为
，最优解为
，最优解为
表示第k 个周期
台机器用于第一种任务，
台机器用于第二种任
表示第k 个周期用于第一种任务的机器台数，
表示第k 表示第k
最优值函数f k （s k ）表示第k 周期初完好机器台数为s k 时，从第k 周期至第4个周期的总收益最
因为s 1=100，所以最大总收益
第 2 页，共 51 页
，最优解为
反推出最优策略为:第1周期100台机器全部用于第二种生产任务; 第2周期90台机器全部用于第二种生 产任务; 第3周期81台机器全部用于第一种生产任务; 第4周期54台机器全部用于第一种生产任务。
2． 用位势法检验下列运输问题的可行解是否为最优解;
注:括号中数字为相应位置上的运输量。
【答案】由于基变量的个数应为m+n-1=3+4-1=6个，而表格所给最优解中基变量的个数为4，应在空格（1，l ） 和空格（2，2）中补充运量0。
（l ）用位势法检验，在表中增加一位势列u i 和位势行v j ，计算位势:
（2）计算检验数:
由于存在检验数
，故这个解不是最优解。
第 3 页，共 51 页
3． 某科学试验可用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）
第 4 页，共 51 页