2017年哈尔滨工业大学威海校区850运筹学考研强化模拟题
● 摘要
一、选择题
1． 动态规划是解决（ ）的一种数学方法。
A. 单阶段决策过程最优化 B. 多目标决策过程最优化 C. 多阶段决策过程最优化 D. 位目标决策过程最优化 【答案】C
【解析】动态规则是运筹学的一个分支，它是解决多阶段决策过程最优化的一种数学方法
2． 设线性规划
A. 基本可行解 B. 基本可行最优解 C. 最优解 D. 基本解 【答案】A
【解析】可行解包括基可行解与非基可行解。
3． 一般卖报童模型的假设条件，不包括以下（ ）。
A. 买入一件物品的成本是固定并已知的 B. 卖出一件物品的收入是固定并己知的
C. 若物品在一个周期中卖不出去，折价收入是固定并己知的 D. 物品的销售数量是己知的 【答案】D
【解析】报童问题为需求是随机离散的存储问题，所以其假设中不可能包括物品的销售数量是己知的。
4． 在产销平衡运输问题中，设产地有m 个，销地有n 个。如果用最小元素法求最优解，那么基变量的个数 为（ ）。
A. 不能大于（m+n-1） B. 不能小于（m+n-l） C. 等于（m+n-l）
第 2 页，共 59 页
有可行解，则此线性规划一定有（ ）。
D. 不确定 【答案】A
【解析】在运输问题中，其自变量的个数是m ×n ，约束方程有m+n个，但是对于产销平衡问题，有以下关系式存在:
。故，模型最多只有m+n﹣1个独立方程，
由此得运输问题最多有m+n﹣1个基变量。当出现退化解时，基变量小于m+n﹣1个。
二、简答题
5． 什么是可行流?
【答案】满足下列条件的网络流f 称为可行流 （l ）容量限制条件:对每一弧（v i ，v j
）对于起点Vs ，记对于终点V t ，记
6． 什么是关于可行流f 的增广链?
【答案】设f 是一个可行流，v s 是网络的起点，v t 是网络的终点，若
满足下列条件: （l ）在弧（2）在弧称
是关于可行流f 的一条增广链。
即即
中每一前向弧是非饱和弧。 中每一后向弧是非零流弧。
是从v s 到v t ，的一条链，
（2）平衡条件 对于中间点，流出量=流入量，即对每个
式中，V （f ）称为这个可行流f 的流量，即发点的净输出量（或收点的净输入量）。
三、计算题
7． 某一印刷厂有六项加工任务，对印刷车间和装订车间所需时间（单位:天）如表所示，试求最优的加工顺序和总加工天数。
表
【答案】加工天数矩阵为
根据最优排序规则，其最优加工顺序为J 4→J 1→J 3→J 2→J 5→J 6，总加工时间为44天。
第 3 页，共 59 页
8． 对下列整数规划问题，问用先解相应的线性规划然后凑整的办法能否得到最优整数解?
（1）
（2）
【答案】 （1）在该线性规划问题的约束条件中分别加入松弛变量
，化为标准型
先不考虑上述模型中的整数约束，利用单纯形法进行求解，如表所示。
表
此时的最优解为
用分支定界法进一步求解此整数规划.
记
，因为
，最优目标值。
时，为可行解，z=13; 当凑整
为
对该最优解进行凑整，当凑整
为
时均为非可行解。
为可行解，所以
第 4 页，共 59 页
。将原问题分解为两个子问