2017年哈尔滨工业大学经济与管理学院850运筹学考研强化模拟题
● 摘要
一、选择题
1． 若f 是G 的一个流，K 为G 的一个割，且f 的流量等于K 的容量，则K 一定是（ ）。
A. 最大流
B. 最大割
C. 最小流
D. 最小割
【答案】D
【解析】网络从发点到收点的各通路中，由容量决定其通过能力，最小割集则是这些路中的咽喉部分，或者叫瓶口, 其容量最小，它决定了整个网络的最大通过能力。
2． 对于动态规划，下列说法正确的有（ ）
A. 在动态规划模型中，问题的阶段数等于问题中的子问题的数目
B. 动态规划中，定义状态时应保证在各个阶段中所做决策的相互独立性
C. 对一个动态规划问题，应用顺推成逆推解法可能会得出不同的最优解
D. 假如一个线性规划问题含有8个变量和6个约束，则用动态规划方法求解时将划分为6个阶段，每个阶 段的状态将有一个8维的向量组成
【答案】AB
【解析】对于一个动态规划问题，不论是采用顺推法还是逆推法，只能得到一个唯一的解; 假如一个线性规 划问题含有8个变量和6个约束，则用动态规划方法求解时将按照变量的个数划分为8个阶段，每个阶段的状态 将有一个6维的向量组成。
3． 关于对偶问题，下列叙述错误的有（ ）
A. 根据对偶问题的性质, 当原问题为无解时, 其对偶问题无可行解; 反之当对偶问题无可行解, 其原问题具有无界解。
B. 若线性规划的原问题有多重最优解，则其对偶问题也一定具有多重最优解。
C. 己知y 飞为线性规划的对偶问题的最优解，若y*j>0，说明在最优生产计划中第j 种资源己完全耗尽
D. 若某种资源的影子价格等于k ，在其他条件不变的情况下，当种资源增加5个单位时，相应的目标函 数只讲增大sk
【答案】A
【解析】当原问题（对偶问题）无可行解时，对偶问题（原问题）或具有无界解或无可行解。
4． 根据对偶解的经济含义，若天然气资源是我国的一种稀缺能源资源，其影子价格必然是（ ）。
A. 不能确定
B.<0
C.=0
D.>0
【答案】D
【解析】影子价格是对系统内部资源稀缺程度的一种客观评价，某种资源的影子价格越高，说明该资源在系 统内越稀缺，增加该资源的供应量对系统目标函数值贡献也越大。天然气是资源是一种稀缺能源资源，其影子价 格必然大于0。
二、简答题
5． 试将Norback 和love 提出的几何法与C 一W 节约算法进行比较。
【答案】（1）几何法:首先找出凸包，然后考查以不在旅行线路上的点为角顶，以线路上的点的连线为对边的角的大小，选出最大者所对应的角顶，插入到旅行线路中，反复进行直至形成哈密尔顿回路。
（2）C 一W 节约算法:首先以某一点为基点，确定初始解，然后考查基点之外的其它点的连线所构成的弧的 节约值的大小，选出节约值最大者所对应的弧，插入到旅行线路中，直至旅行线路中包含所有的点。
6． 试说明C 一W 节约算法的基本思想，你认为还可用它解决哪些方面的问题? 举例加以说明。
【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧
这样在满足访问若干城市各一次且仅一次的条件下， 插入到旅行线路中，最大限度地缩短了路程。
（2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点i 与点j 维修时间总和的一半。优先考虑将节约值最大的长度加入工作线路中去进行迭代。
三、计算题
7． 用两阶段法求解以下线性规划问题
【答案】第一阶段:加入松弛变量x 4，x 5，人工变量x 6，数学模型为:
用单纯形法求解如表所示。
表
第一阶段的最优解为X=
第二阶段：除去人工变量x 6，目标函数为：
求解结果为
8． 用表上作业法求表1至表4中给出的运输问题的最优解（表中数字M 为任意大正数）。
表1 表
2
表3 表4