2017年湖北工业大学机械工程学院910运筹学考研题库
● 摘要
一、简答题
1． 试说明C 一W 节约算法的基本思想，你认为还可用它解决哪些方面的问题? 举例加以说明。
【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧 这样在满足访问若干城市各一次且仅一次的条件下， 插入到旅行线路中，最大限度地缩短了路程。
（2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点i 与点j 维修时间总和的一半。优先考虑将节约值最大的长度加入工作线路中去进行迭代。
2． 试将Norback 和love 提出的几何法与C 一W 节约算法进行比较。
【答案】（1）几何法:首先找出凸包，然后考查以不在旅行线路上的点为角顶，以线路上的点的连线为对边的角的大小，选出最大者所对应的角顶，插入到旅行线路中，反复进行直至形成哈密尔顿回路。
（2）C 一W 节约算法:首先以某一点为基点，确定初始解，然后考查基点之外的其它点的连线所构成的弧的 节约值的大小，选出节约值最大者所对应的弧，插入到旅行线路中，直至旅行线路中包含所有的点。
3． 什么是启发式方法? 说明用启发式方法解决实际问题的过程和步骤。
【答案】（1）对于结构不良问题，为得到近似可用的解，分析人员必须运用自己的感知和洞察力，从与其有关而 较基本的模型与算法中寻求其间的联系，从中得到启发，去发现适于解决该问题的思路和途径，这种方法称为启 发式方法。
（2）用启发式方法解决实际问题的过程和步骤:①系统观察和分析实际问题; ②抽象并明确提出问题; ③ 建立启发式数学模型; ④选择启发式策略，设计启发式方法，按照一定的搜索规则反复迭代逼近模型最优可行解，直到得到满意解; ⑤检验和修正模型及其满意解。
4． 试简述求解整数规划模型的分枝定界法剪枝的几种情况。
【答案】（l ）某枝已经达到其范围内的最优解; （2）某枝域内没有可行解时，即是不可行域; （3）某枝所得数据不优于当前最优解时。
二、计算题
5． 某投资者，若投资项目A ，一年后肯定获得收益C ; 若投资项目B ，一年后收益不确定，收益为C 1的概率为P ，收益为C 2的概率为1一P 。在c 1 【答案】投资项目A 的期望收益为C 投资项目B 的收益为若选择投资项目A , 则所以 。 , 即 。 , 变形得 , 又由于 , 同理，若选择项目B ，则所以, 当当当 6． 试用变尺法解 小点处梯度的模不大于0.5。 【答案】取初始点 时选择项目B 时选择项目A 或项目B 之一均可以。 时选择项目A 。 ，取初始点 ，要求近似极 显然，，故 令，可得，于是 又因为，所以为近似极小点。 7． 某罐头制造公司需要在近五周内必须采购一批原料，估计在未来五周内价格有波动，其浮动价格和概 率如表所示。试求各周以什么价格购入，使采购价格的数学期望值最小。 表 【答案】按采购期限将该问题分为5个阶段，将每周的价格看作该阶段的状态。 --状态变量，表示第k 周的实际价格。 --决策变量， =1，表示第k 周决定采购; =0，表示第k 周决定等待。 --第k 周决定等待，而在以后采取最优决策时采购价格的期望值。 第k 周实际价格为 可写出逆序递推关系式为: 其中：由 和 的定义可知： 并且得出最优决策为： 从最后一周开始，逆序递推计算，具体过程如下: 当k=5时，当k=4时，由 于是 可知 即在第5周时，若所需的原料尚未买入，则无论市场价格如何，都必须采购，不能再等。 时，从第k 周至第5周采取最优决策时的最小期望值。 因而 所以，第4周的最优决策为同理求得 所以