2017年国防科学技术大学信息系统与管理学院853运筹学基础考研冲刺密押题
● 摘要
一、填空题
1． 最速下降法的搜索方向_____。
牛顿法的搜索方向为_____。 拟牛顿法的搜索方向为_____。 【答案】
【解析】最速下降法:
可以得出，
当
时，下降最快。
牛顿法：正定二次函
数
即搜索方向是
拟牛顿法
：
（单位阵）
2． 当极大化线性规划模型达到最优时。某非基变量x j 的检验数为马. 当价格系数为c j 的变化量为△c j 时，原 线性规划问题最优解保持不变的条件是_____。
【答案】
若
是最优点，
则
，极大化 【解析】x j 为非基变量，其价格系数变化△c j 后，其检验数变为
3． 在灵敏度分析时, 当LP 某系数发生变化使原最优单纯形表中的解为该LP 的一个正侧解，但不是可行解, 为求新的最优解, 处理办法是:_____。
【答案】对偶单纯形法
4． 对于线性规划问题:MaxZ=CX.AX≦b.X ≧0，若B=（P 1，P 2，…，P m ）为A 中m 个线性无关的列向量, 且为该LP 的一个可行基，则对应于基B 的基可行解为:_____，该基可行解为最优解的条件是:_____。
【答案】
，对于一切
有。
【解析】若B=（P 1，P 2，…，P m ）为A 中m 个线性无关的列向量，
此时令非基变量
， 这时变量的个数等于线性方程组的个数，用高斯消去法，可求得对应
于基B 的基可行解
为
。由最优解的判别定理，若对于一
切
, 则所求得的基可 行解为最优解。
二、选择题
5． 用单纯形法求解线性规划问题时，满足（ ）对应的非基变量xj 可以被选作为换入变量。
A. 检验数σ>0 B. 检验数σ<0
C. 检验数σ>0中的最大者 D. 检验数σ<0中的最小者 【答案】C
【解析】当某些σ>0时，xj 增加则目标函数值还可以增大，这时要将某个非基变量xj 换到基变量中去，为了使目标函数值增加得快，一般选择σ>0中的大者。
6．
是某个目标约束条件所对应的目标函数，该目标函数就从逻辑上来看所表达的含义是（ ）。
A. 恰好完成目标值 B. 不超过目标值 C. 完成和超额完成目标值 D. 不能表示任何意义 【答案】D
【解析】目标规划的目标函数是按各自目标约束的正、负偏差变量和赋予相应的优先因子及权系数而构造的。 当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值。因此目标规划的目标函数只能是。 本题对应的目标函数是求maxZ ，所以没有任何意义。
7． 关于最小费用最大流，求解时不会用到下面哪种方法（ ）。
A.Dijkstra 算法 B.Floyd 算法
C.Ford 一Fulkerson 算法 D. 奇偶点作业法 【答案】D
【解析】奇偶点作业法为中国邮递员问题中寻找欧拉圈时所用的方法，最小费用最大流问题并不涉及此法。
8． 求一个赋权图中包括指定边集的最小连接方案（最小树），下面（ ）方法是正确的。
A. 最小树的初始边集为图中最小权边，按其余各边的权从小到大，逐一检查选取 B. 最小树的初始边集为某一条指定边，按其余各边边的权从小到大，逐一检查选取 C. 最小树的初始边集为所有指定边的集合，按其余各边边的权从小到大，逐一检查选取 D. 最小树的初始边集为权最小的一条指定边，按其余各边边的权从小到大，逐一检查选取 【答案】C
【解析】该问题不是简单的最短路问题，它要求最小连接方案包括指定边集，所以，最小树的初始边集应为 所有指定边的集合。
三、计算题
9． 已知某运输问题的供需关系及单位运价如表所示，要求:
（l ）用表上作业的方法求出最优调运方案:
（2）分析从A 1到B l 的单位运价可变化范闺，使（l ）中求得的最优调运方案保持不变: （3）分析从A 1到B 1的单位运价可变化范围，使（1）中求得的最优调动方案保持不变:
表
【答案】（1）此问题为运输不平衡问题，故需要加一个虚拟销地，其销量为2，第一步，用沃格尔法确定初始方案为:
表
第二步，用位势法计算初始方案中非基变量的检验数为:
表