2018年北京航空航天大学人文社会科学学院981管理科学基础之运筹学考研基础五套测试题
● 摘要
一、选择题
1． 运输问题中，m+n-l个变量构成基本可解的充要条件是它不含（ ）。
A. 松弛变量
B. 多余变量
C. 闭回路
D. 圈
【答案】C
【解析】位于闭回路上的一组变量，它们对应的运输问题约束条件的系数列向量线性相关，因而在运输问题基可行解的迭代过程中，不允许出现全部顶点由填有数字的格构成的闭回路。也就是说，在确定运输问题的基可行解时，除要求基变量的个数为（m+n-l）外，还要求运输表中填有数字的格不构成闭回路。
2． 求一个赋权图中包括指定边集的最小连接方案（最小树），下面（ ）方法是正确的。
A. 最小树的初始边集为图中最小权边，按其余各边的权从小到大，逐一检查选取
B. 最小树的初始边集为某一条指定边，按其余各边边的权从小到大，逐一检查选取
C. 最小树的初始边集为所有指定边的集合，按其余各边边的权从小到大，逐一检查选取
D. 最小树的初始边集为权最小的一条指定边，按其余各边边的权从小到大，逐一检查选取
【答案】C
【解析】该问题不是简单的最短路问题，它要求最小连接方案包括指定边集，所以，最小树的初始边集应为 所有指定边的集合。
3． 影子价格实际上是与原问题的各约束条件相联系的（ ）的数量表现。
A. 决策变量
B. 松弛变量
C. 人工变量
D. 对偶变量
【答案】D
【解析】影子价格是对偶问题的经济解释，实际上影子价格的大小即为对偶变量的大小。
4． 动态规划是解决（ ）的一种数学方法。
A. 单阶段决策过程最优化
B. 多目标决策过程最优化
C. 多阶段决策过程最优化
D. 位目标决策过程最优化
【答案】C
【解析】动态规则是运筹学的一个分支，它是解决多阶段决策过程最优化的一种数学方法
二、填空题
5． 图G=（V ，E ）有生成树的充分必要条件是_____。
【答案】G 是连通图
【解析】图G 是连通图，如果G 不含圈，那么G 本身是一个树，从而G 使它自身的一个支撑树。现设G 含圈，任取一个圈，从圈中任意地去掉一条边，得到G 的一个支撑子图Gl 。如果Gl 不含圈，那么Gl 是G 的 一个支撑树，如果Gl 仍含圈，那么从Gl 中再任取一个圈，如此重复，最终可以得到G 的一个支撑子图Gk ， 它不含圈，于是Gk 就是G 的一个支撑树。
6． 若P （k ）是f （x ）在x （K ）处的下降方向，则满足_____。
【答案】均有
【解析】若存在实数
，使对于任意的，就称方向）为均有下式成立:
点的一个下降方向。
7． 运输问题任一基可行解非零分量的个数的条件是_____。
【答案】小于等于行数+列数-1
【解析】任意运输问题的基可行解可变量个数为:行数+列数一l 。然而基变量也可能等于0，所以运输问题 任一基可行解非零分量的个数小于等于行数+列数一1。
8． 网络中如果树的节点个数为z ，则边的个数为_____。
【答案】z-l
【解析】由树的性质可知，树的边数=数的节点数-1
三、简答题
9． 什么是启发式方法? 说明用启发式方法解决实际问题的过程和步骤。
【答案】（1）对于结构不良问题，为得到近似可用的解，分析人员必须运用自己的感知和洞察力，从与其有关而 较基本的模型与算法中寻求其间的联系，从中得到启发，去发现适于解决该问题的思路和途径，这种方法称为启 发式方法。
（2）用启发式方法解决实际问题的过程和步骤:①系统观察和分析实际问题; ②抽象并明确提出问题; ③ 建立启发式数学模型; ④选择启发式策略，设计启发式方法，按照一定的搜索规则反复迭代逼近模型最优可行解，直到得到满意解; ⑤检验和修正模型及其满意解。
四、计算题
10．设有线性规划
在第一二约束电分别加入松弛变量x 3、x 4
所示。
表
，并用单纯形法求解，得到最优单纯形表如表
（1）求出原规划LP 。
（2）写出LP 的对偶规划LD 。
（3）求LD 的最优解和最优目标值。
【答案】（l ）
（2）
（3）L p 的最优解为（3，l ），最优目标值为4x3+5xl=17 T
由强对偶性