2017年重庆交通大学经济与管理学院812运筹学考研导师圈点必考题汇编
● 摘要
一、选择题
1． 单纯形法求解最大化线性规划问题，如果存在“左端≥右端常数”的约束条件，对此约束条件应引入（ ）。
A. 可控变量
B. 环境变量
C. 人工变量
D. 松弛变量
【答案】D
【解析】约束方程为“≥”不等式，则可在“≥”不等式左端减去一个非负剩余变量（也可称松弛变量）。
2． 己知Y i 为线性规划的对偶问题的最优解，若Y i >0，说明（ ）。
A. 原问题的最优解x i =0
B. 在最优生产计划中第i 种资源己完全耗尽
C. 在最优生产计划中第i 种资源有剩余
D. 无法判断
【答案】B
【解析】当影子价格为0时，表示某种资源未得到充分利用; 而当资源的影子价格不为零时，表明该种资源在生产中己耗费完毕。
3． 关于最小费用最大流，求解时不会用到下面哪种方法（ ）。
A.Dijkstra 算法
B.Floyd 算法
C.Ford 一Fulkerson 算法
D. 奇偶点作业法
【答案】D
【解析】奇偶点作业法为中国邮递员问题中寻找欧拉圈时所用的方法，最小费用最大流问题并不涉及此法。
4． 线性规划可行域为封闭的有界区域，最优解可能是（ ）。
A. 唯一的最优解
B. 一个以上的最优解
C. 目标函数无界
D. 没有可行解
【答案】AB
【解析】可行域非空，故有可行解; 可行域封闭，故目标函数有界，有一个或多个最优解。
二、填空题
5． 运输问题任一基可行解非零分量的个数的条件是_____。
【答案】小于等于行数+列数-1
【解析】任意运输问题的基可行解可变量个数为:行数+列数一l 。然而基变量也可能等于0，所以运输问题 任一基可行解非零分量的个数小于等于行数+列数一1。
6． 若x 为某极大化线性规划问题的一个基可行解，
用非基变量表达其目标函数的形式为
则X 为该LP 最优解的条件是:_____。 【答案】
。 【解析】求极大化问题，则当所有非基变量的检验数均为非正时，即得最优解。线性规划最优时要求非基变 量检验数小于等于0，所以
7． 无向连通图G 是欧拉图的充要条件是_____。
【答案】G 中无奇点
8． 当极大化线性规划模型达到最优时。某非基变量x j 的检验数为马. 当价格系数为c j 的变化量为△c j 时，原 线性规划问题最优解保持不变的条件是_____。 【答案】
，极大化 【解析】x j 为非基变量，其价格系数变化△c j 后，其检验数变为
三、判断题
9． 用动态规划方法求最优解时，都是在行进方向规定后，均要顺着这个规定的行进方向，逐段找出最优途 径。（ ）
【答案】√
【解析】用递推法求解动态规划问题，首先将过程分成几个相互联系的阶段，选取状态变量和决策变量并定 义最优值函数，然后写出基本的递推关系式和基本方程。其行进方向的规定，即选择用逆推法还是顺推法。因 为动态规划的状态具有无后效性，所以必须按规定的行进方向逐段找出最优途径。
10．如果线性规划问题有最优解，则它对偶问题也一定有最优解。（ ）
【答案】√
【解析】由对偶定理知，原命题为真，且线性规划问题与它的对偶问题的最优值相等。
11．利用破圈法求赋权图的最小支撑树时，每次都是任取一个圈并去掉其中权最小的边，直到该赋权图不再 含圈时，便得到最小支撑树。（ ）
【答案】×
【解析】利用破圈法求最小支撑树时，每次任取一个圈，去掉圈中权最大的边。
12．若线性规划问题的可行解为最优解，则该可行解必定是基可行解。（ ）
【答案】×
【解析】基解且可行才有可能是最优解。
13．在任一图G 中，当点集v 确定后，树图是G 中边数最少的连通图。， （ ）
【答案】×
【解析】连通且不含圈的无向图称为树。
四、证明题
14．己知九个人v 1，v 2，…，v 9中v 1和两个人握过手，v 2和v 3各和四个人握过手，v 4，v 5，v 6，v 7各和五个人握过手，v 8，v 9各和六个人握过手，证明这九个人一定可以找出三人互相握过手。
【答案】该问题可表述为一个包含9个点（每个人代表一个点）的图的问题。依题意知 d （v l ）=2，d （v 2）=d（v 3）=4，d （v 4）=d（v 5）=d（v 6）=d（v 7）=5，d （v 8）=d（v 9）=6 其中，边v i ，v j 代表v i 和v j 握过手。对于v 9，因为d （v 9）=6，所以v 4，v 5，v 6，v 7中至少有两个点与v 9之间 存在连线，设该两点为v 4和v 5。假设与v 4和与v 9相连的其他五点之间无边，
则
，与已知的 d （v 4）=5相矛盾，故假设不成立。即v 4与上述五点间必存在至少
两条边，设其中一点为v k ，则v k ，v 4，v 9两两相连，即存在三人之间互相握过手。
15．某决策问题有m 个方案A （i=1，…，m ），n 个状态sj （j=l，…，n ），各状态出现的概率为P （Sj ）; 决策问题的收益矩阵为
）
【答案】用EMV i 从表示方案i 的期望收益，用EOL i 共表示方案i 的期望损失。
方案i 的期望损失:
所以当EMV 为最大时，EOL 便为最小。所以在决策时用这两个决策准则所得到的结果是相同的。
。试证明用期望收益最大准则和期望损失最小准则获 得的决策方案相同。（提示:Aj 方案在Sj 状态下的损
失值为
相关内容
相关标签