2018年重庆交通大学交通运输学院812运筹学考研核心题库
● 摘要
一、选择题
1． 对于动态规划，下列说法正确的有（ ）
A. 在动态规划模型中，问题的阶段数等于问题中的子问题的数目
B. 动态规划中，定义状态时应保证在各个阶段中所做决策的相互独立性
C. 对一个动态规划问题，应用顺推成逆推解法可能会得出不同的最优解
D. 假如一个线性规划问题含有8个变量和6个约束，则用动态规划方法求解时将划分为6个阶段，每个阶 段的状态将有一个8维的向量组成
【答案】AB
【解析】对于一个动态规划问题，不论是采用顺推法还是逆推法，只能得到一个唯一的解; 假如一个线性规 划问题含有8个变量和6个约束，则用动态规划方法求解时将按照变量的个数划分为8个阶段，每个阶段的状态 将有一个6维的向量组成。
2． 无约束最优化问题
）问题的（ ）。
A. 全局最优解
B. 局部最优解
C. 极点
D .K-T点
【答案】B
【解析】局部最优解即在X*的某邻域，满足
3． 在求解整数规划问题时，不可能出现的是（ ）。
A. 唯一最优解
B. 无可行解
C. 多重最优解
D. 无穷多最优解
【答案】D
【解析】整数规划的可行解的个数是有限的，所以整数规划中不可能出现无穷多最优解。 ，则称X*是函数的局部最优解。中，如果在X*的某个领域内满足，则X ’是
4． 关于最小费用最大流，求解时不会用到下面哪种方法（ ）。
A.Dijkstra 算法
B.Floyd 算法
C.Ford 一Fulkerson 算法
D. 奇偶点作业法
【答案】D
【解析】奇偶点作业法为中国邮递员问题中寻找欧拉圈时所用的方法，最小费用最大流问题并不涉及此法。
二、填空题
5． 若对偶问题为无界解，则原问题:_____。
【答案】无可行解
【解析】任一对偶问题的可行解都是原问题的上界，而原问题的任意可行解都是对偶问题的下界。若对偶问题为无界解，则原问题的目标函数
即没有可行解。
6． 如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k ，最优调运方案是否会发生变化: _____。
【答案】不发生变化
【解析】如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k ，最优调运方案中各变量的 检验数均不发生变化，所以最优调运方案不发生变化。
7． 运输问题任一基可行解非零分量的个数的条件是_____。
【答案】小于等于行数+列数-1
【解析】任意运输问题的基可行解可变量个数为:行数+列数一l 。然而基变量也可能等于0，所以运输问题 任一基可行解非零分量的个数小于等于行数+列数一1。
8． 对于同一风险决策问题，与用期望收益最大准则得到相同结果的决策准则是:_____。
【答案】期望损失最小准则
【解析】对于同一风险决策问题，用期望收益最大准则和期望损失最小准则获得的决策方案相同。 无界，即无限小，则z 无解，
三、判断题
9． 目标规划问题的日标函数都是求最大化问题的。（ ）
【答案】×
【解析】当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值，因此目标规划的目
标函数只能是最小化的。
10．线性规划问题的每一个基解对应可行域的一个顶点。（ ）
【答案】×
【解析】基解不一定是可行解，基可行解对应着可行域的顶点。
11．如果线性规划问题无最优解，则它也一定没有基可行解。（ ）
【答案】×
【解析】当问题的解为为无界时，此时该规划问题无最优解，但存在基可行解。
12．如果图T 是树，则T 中一定存在两个顶点，它们之间存在两条不同的链。（ ）
【答案】×
【解析】连通且不含圈的无向图称为树。因此任意两点间必定只有一条链。
13．指派问题效率矩阵的每个元素乘以同一大于0的常数k ，将不影响最优指派方案。（ ）
【答案】√
【解析】效率矩阵每个元素乘以同一大于0的常数k ，即目标函数的系数同时增大k 倍，不会影响最优基的变化，故不影响最优指派方案。
四、证明题
14．称顾客为等待所费时间与服务时间之比为顾客损失率，用R 表示。
（l ）试证:对于M/M/1模型，
（2）在上题中，设 不变而。 是可控制的，试定使顾客损失率小于4。
证毕。
时，顾客损失率小于4。【答案】（l ）对于M/M/1模型, （2）由
15．假设线性规划问题为:
，得。由定义，有，所以当
其中，秩
运用单纯形算法求得的最优基可行解时，所有的非基变量检验数全都<0，试证明这时所得到的最优解必定 是线性规划问题（l ）的准最优解。
【答案】一般情况下，经过迭代后解变为
相关内容
相关标签