2017年哈尔滨工业大学威海校区850运筹学考研题库
● 摘要
一、选择题
1． 用线性规划制定某一企业的生产计划问题，两种资源的影子价格分别为y 甲=5，y 乙=8，说明这两种资源在该企业中的稀缺程度为:（ ）。
A. 甲比乙更稀缺 B. 甲和乙同样稀缺 C. 乙比甲更稀缺 D. 甲和乙都不稀缺 【答案】C
【解析】影子价格是对系统内部资源稀缺程度的一种客观评价，某种资源的影子价格越高，说明该资源在系统内越稀缺，增加该资源的供应量对系统目标函数值的贡献也越大。
2． 线性规划可行域为封闭的有界区域，最优解可能是（ ）。
A. 唯一的最优解 B. 一个以上的最优解 C. 目标函数无界 D. 没有可行解 【答案】AB
【解析】可行域非空，故有可行解; 可行域封闭，故目标函数有界，有一个或多个最优解。
3． 对于动态规划，下列说法正确的有（ ）
A. 在动态规划模型中，问题的阶段数等于问题中的子问题的数目 B. 动态规划中，定义状态时应保证在各个阶段中所做决策的相互独立性 C. 对一个动态规划问题，应用顺推成逆推解法可能会得出不同的最优解
D. 假如一个线性规划问题含有8个变量和6个约束，则用动态规划方法求解时将划分为6个阶段，每个阶 段的状态将有一个8维的向量组成
【答案】AB
【解析】对于一个动态规划问题，不论是采用顺推法还是逆推法，只能得到一个唯一的解; 假如一个线性规 划问题含有8个变量和6个约束，则用动态规划方法求解时将按照变量的个数划分为8个阶段，每个阶段的状态 将有一个6维的向量组成。
4． 线性规划灵敏度分析应在（ ）的基础上，分析系数的变化对最优解产生的影响。
A. 初始单纯形表 B. 最优单纯形表
C. 对偶问题初始单纯形表 D. 对偶问题最优单纯形表 【答案】BD
【解析】灵敏度分析的是当系数的一个或几个发生变化时, 已求得的线性规划问题的最优解会有什么变化，所以进行灵敏度分析是在最优单纯形表或对偶问题的最优单纯形表的基础上分析的, 最优单纯形表反映的就是系数变化前己求得的最优解。
二、简答题
5． 试说明C 一W 节约算法的基本思想，你认为还可用它解决哪些方面的问题? 举例加以说明。
【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧 这样在满足访问若干城市各一次且仅一次的条件下， 插入到旅行线路中，最大限度地缩短了路程。
（2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点i 与点j 维修时间总和的一半。优先考虑将节约值最大的长度加入工作线路中去进行迭代。
6． 简述求解最小费用最大流的赋权网络设置方法。
，有可行流f ，保持原网络各点， 【答案】解:对网络G=（ V ，E ，C ，d ）每条边用两条方向相反的有向边代替，各边的权
②当边（vj 名）为原来G 中边（vi ，vj ）的反向边，令
按如下规则:
三、计算题
7． 某公司需要对某产品决定未来半年内每个月的最佳存储量，以使总费用极小化。已知半年里对该产品 的需求量和单位订货费用、单位存储费用的数据，如表所示。
表
【答案】按月份将问题划分为6个阶段，阶段变量k=1，2，3，…，6。状态变量s k 为第k 阶
段开始时的产品存储量，决策变量u k 为第k 阶段的订货量，d k 为第k 阶段的需求量。状态转移方程:
允许决策集合为:
最优值函数
为第k 阶段开始存储量为
时，从第1阶段至第k 阶段的最小存储费用。
;
c （j , i）（j≤ i）为从阶段j 到阶段i 的总成本，利用再生产点性质求解:
（1）由
，计算c （j , i）:
=175425
=213425
=243125
（2）按照递推关系式，有
=124125
所以，最优决策方案为:第l 月初的订货量为50; 第2月初的订货量为150; 第5月朝的订货量为70。其余月份不订货。
相关内容
相关标签