2017年上海工程技术大学航空运输学院821运筹学[专业硕士]考研导师圈点必考题汇编
● 摘要
一、选择题
1． 影子价格实际上是与原问题的各约束条件相联系的（ ）的数量表现。
A. 决策变量
B. 松弛变量
C. 人工变量
D. 对偶变量
【答案】D
【解析】影子价格是对偶问题的经济解释，实际上影子价格的大小即为对偶变量的大小。
2． 设线性规划
A. 基本可行解
B. 基本可行最优解
C. 最优解
D. 基本解
【答案】A
【解析】可行解包括基可行解与非基可行解。
3． 单纯形法求解最大化线性规划问题，如果存在“左端≥右端常数”的约束条件，对此约束条件应引入（ ）。
A. 可控变量
B. 环境变量
C. 人工变量
D. 松弛变量
【答案】D
【解析】约束方程为“≥”不等式，则可在“≥”不等式左端减去一个非负剩余变量（也可称松弛变量）。
4． 在网络中，设通过弧（v i ，v j ）的流量和容量分别为f ij 和c ij ，若弧（v i ，v j ）是非饱和弧则有（ ）
第 2 页，共 80 页 有可行解，则此线性规划一定有（ ）。
【答案】C
二、填空题
5． 两阶段法中，若第一阶段目标函数最优值不为0，则原问题_____。
【答案】无可行解
【解析】第一阶段目标函数值不是0，则说明最优解的基变量中含有非零的人工变量，表明原先性规划问题五可行解。
6． 现有m 个约束条件，若某模型要求在这m 个条件中取”个条件作为约束，用，1变量来实现 该问题的约束条件组为:_____。
【答案】
【解析】0一l 变量取1时取该约束条件，否则不取，又一共取S 个约束条件。则可得到约束条件组为:
。
k K 7． 若P （）是f （x ）在x （）处的下降方向，则满足_____。
【答案】均有
【解析】若存在实数，使对于任意的均有下式成立:
，就称方向）为点的一个下降方向。
8． 对于同一风险决策问题，与用期望收益最大准则得到相同结果的决策准则是:_____。
【答案】期望损失最小准则
【解析】对于同一风险决策问题，用期望收益最大准则和期望损失最小准则获得的决策方案相同。
三、证明题
9． 己知九个人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中至少有
第 3 页，共 80 页
两个点与v 9之间 存在连线，设该两点为v 4和v 5。假设与v 4和与v 9相连的其他五点之间无边，
则
，与已知的 d （v 4）=5相矛盾，故假设不成立。即v 4与上述五点间必存在至少
两条边，设其中一点为v k ，则v k ，v 4，v 9两两相连，即存在三人之间互相握过手。
10．设线性规划问题1是
（）是其对偶问题的最优解。
又设线性规划问题2是
其中k i 是给定的常数，求证
【答案】问题1的矩阵表示为
其中
问题2的矩阵表示为
。 设X 1 为它的一个可行解，其对偶问题的最优解为
其中
问题1的对偶问题为
问题2的对偶问题为
= 。 设X 2 为它的一个可行解，其对偶问题的最优解为Y 2
第 4 页，共 80 页