2018年上海海事大学科学研究院809运筹学考研基础五套测试题
● 摘要
一、简答题
1． 试说明C 一W 节约算法的基本思想，你认为还可用它解决哪些方面的问题? 举例加以说明。
【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧插入到旅行线路中， 这样在满足访问若干城市各一次且仅一次的条件下，最大限度地缩短了路程。
（2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点i 与点j 维修时间总和的一半。优先考虑将节约值最大的长度加入工作线路中去进行迭代。
2． 用表上作业法解运输问题时，在什么情况下会出现退化解? 当出现退化解时如何处理?
【答案】当运输问题某部分产地的产量和，与某一部分销地的销量和相等时，在迭代过程中间有可能在某个格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。
当出现退化时，为了使表上作业法的迭代工作能顺利进行下去，退化时应在同时划去的一行或一列中的某个 格中填入数字0，表示这个格中的变量是取值为0的基变量，使迭代过程中基变量个数恰好为（m+n-l）个。
3． 试简述求解整数规划模型的分枝定界法剪枝的几种情况。
【答案】（l ）某枝已经达到其范围内的最优解;
（2）某枝域内没有可行解时，即是不可行域;
（3）某枝所得数据不优于当前最优解时。
二、综合题
4． 某运输问题，两个产地，三个销地，两个中转站，有关数据如图所示，中转站3的容量限制为800。
（l ）建立使总运输成本之和最小的调运数学模型。
（2）试将问题转化成可用表上作业法计算的调运表。
【答案】（l ）设x ij 表示从i 地运往j 地的运量，i=1，2，3，4; j=3，4，5，6，7;
则可得数学模型如下:
（2）因为产销不平衡，故虚拟一销量为400的销地8。则得下列产销平衡表和运价表。
表
5． 某工厂生产某种零件，每年需要量为18000个，该厂每月可生产3000个，每次生产后的装配费为5000元，每个零件的存储费为1.5元，求每次生产的最佳批量。
【答案】由题意知，该题模型为“不允许缺货，生产需一定时间”，已知C 3=500，C l =1.5，P= 3000, R=18000/12=1500。
最佳批量是
所以，每次生产的最佳批量为科72个。
6． 某建筑公司最近几年的发展重点是承接中东等地区的建筑项目。公司需要一种大型的建筑设备，该设备 今后4年的购买价格（预测值）分别为（5 .0，5.3，5.7，6.0）（万元）（产品购买价+运输到工地的费用）。如该设备连 续使用，其第i 年的使用费及维修费分别为（l ，1.7，2.5，
3.3）（万元），由于路途遥远，淘汰后的设备就在当地折价 处理了，使用满i 年的设备处理价格为（3.3，2.5，1.5，0.8）（万元）. 公司在制定一个4年的设备购买计划，你有什 么建议? （限用图论理论，写出算法，计算过程，最终结论，最佳总费用）
【答案】可以把这个问题转化为最短路问题，根据题意绘制如下赋权有向图。
图
采用Dijksra 算法计算图1中的最短路为:
=0; 对其余点进行T 标号，
（l ）对起点1进行P 标号，即p （l ）即
检查点1，进行T 标号：
（2）点2获得P 标号，.
（3）点3获得P 标号，
（4）点4获得P 标号，
（5）点5获得P 标号，）
上图中的最短路为检查点2，修改T 标号:检查点3，修改T 标号:检查点4，无需修改T 标号。 求解结束。 。即第一年初购进一台设备，第三年初淘汰掉并购置新设备，直 至第四年末淘汰 掉。最佳总费用11.1万元。
7． 某工厂一年要进行A ，B ，C 三种新产品试制，由于资金不足，估计在年内这三种新产品研制不成功 的概率分别为0.4，0.6，0.8，因而都研制不成功的概率为0.4xo.6x0.8=0.192。为了促进三种新产品的研制，决定增拨2万元的研制费，并要求资金集中使用，以万元为单位进行分配。其增拨研制费与新产品不成功的概率如表所示。试问如何分配费用，使三种新产品都研制不成功的概率为最小。
表
【答案】按产品种类将问题分三个阶段，阶段变量k=1，2，3；设状态变量s k 为从第k 种产品至第3种产品增拨的研制费用; x k 为第k 种产品增拨的研制费用。状态转移方程为:
，p k （x k ）表示给k 种产品补加研制费x k 后的不成功概率，由题意知，动态规划
的逆推关系式为:
边界条件f 4（s 4）=1