2016年东华大学旭日工商管理学院802运筹学考研导师圈定必考题汇编及答案
● 摘要
一、选择题
1． 影子价格实际上是与原问题的各约束条件相联系的（ ）的数量表现。 A. 决策变量 B. 松弛变量 C. 人工变量 D. 对偶变量 【答案】D
【解析】影子价格是对偶问题的经济解释，实际上影子价格的大小即为对偶变量的大小。 2． 线性规划的最优解有以下几种可能（ ）。 A. 唯一最优解 B. 多个最优解
C. 没有最优解，因为目标函数无界 D. 没有最优解，因为没有可行解 【答案】ABCD
【解析】线性规划问题的每个基可行解对应可行域的一个顶点，若现行规划问题有最优解，必在某个顶点上 得到，当该顶点唯一时，有唯一最优解; 当目标函数在多个顶点上达到最大值时，则该问题有无限多个最优解; 目标函数无界，称线性规划问题具有无界解，此时无最优解; 使目标函数达到最大的可行解称为最优解，故没有可行解就没有最优解。
3． 若f 是G 的一个流，K 为G 的一个割，且f 的流量等于K 的容量，则K 一定是（ ）。 A. 最大流 B. 最大割 C. 最小流 D. 最小割 【答案】D
【解析】网络从发点到收点的各通路中，由容量决定其通过能力，最小割集则是这些路中的咽喉部分，或者叫瓶口, 其容量最小，它决定了整个网络的最大通过能力。
4． 单纯形法求解最大化线性规划问题，如果存在“左端≥右端常数”的约束条件，对此约束条件应引入（ ）。 A. 可控变量 B. 环境变量 C. 人工变量 D. 松弛变量
【答案】D
【解析】约束方程为“≥”不等式，则可在“≥”不等式左端减去一个非负剩余变量（也可称松弛变量）。
二、填空题
5． 现有m 个约束条件
，若某模型要求在这m 个条件中取”个条件作为约束，用，1
变量来实现 该问题的约束条件组为:_。 【答案】
【解析】0一l 变量取1时取该约束条件，否则不取，又一共取S 个约束条件。则可得到约束条件组为:
。
6． 在用对偶单纯形法求解某线性规划问题时, 当进基变量x i 确定后，出基变量的选取原则是:_____。 【答案】
否会发生变化: _____。 【答案】不发生变化
【解析】如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k ，最优调运方案中各变量的 检验数均不发生变化，所以最优调运方案不发生变化。
8． 在灵敏度分析时, 当LP 某系数发生变化使原最优单纯形表中的解为该LP 的一个正侧解，但不是可行解, 为求新的最优解, 处理办法是:____。 【答案】对偶单纯形法
7． 如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k ，最优调运方案是
三、证明题
9． 设G=（V ，E ）是一个简单圈，令证明:（l ）若（2）若
，则G 必有圈； ，则G 必有包含至少
条边的圈。
，假设
（称
为G 的最小次）。
（3）设G 是一个连通图，不含奇点。证明:从G 中丢失任一条边后，得到的图仍是连通图。 【答案】（l ）因为G （V ，E ）是一个简单圈，故该图中无环，也无重复边。若G 中无圈，则G 可能是树或非连通图，这两种情况均存在悬挂点，即
相矛盾。故假设不成立， 所以，G 必有圈。
（2）若的次至少为
，设与，也至少与
对应的点为v k ，则v k
必与个端点相连。如果v k 与v i
这
个端点相连。由（l ）的结论知，G
个端点不构成圈，那么在端
v k 至少与这中必有圈（由于对圈中的连通图而言，点处必向外延伸（因为最小次为
个端点构成圈）。
， 不与其中某点相连，必与其外某点相连）经连通链而到
另一端点，对该圈而言，边数大于条，故G 必定 是包含不少于占 条边的圈。
（3）证明:因为G 连通且不含奇点，故d （v ）=2n，且该图中无悬挂点。由题（l ）的结论知，G 必有圈。又因为G 是连通的，所以从G 中去掉任一条边，都必在某一圈中。而从圈中去掉任一条边，所得图仍是连通图。
10．证明:矩阵对策G={S1，S 2; A}在混合策略意义下有解的充要条件是:存在
为函数以
的一个鞍点，即对一切
【答案】（l ）先证明充分性 对任意X , Y 均有
，故得出
又所以，
另一方便，对任何X ，Y 有
②
由不等式①、②
，
（2）再证必要性。设有X*，Y*，使得
则由
，有
所以对任意X ，Y ，有
综上得证。 11．证明下列定理: （1）设有两个矩阵对策，
，L 为任一常数，则有
（2）设有两个矩阵对策
，
，
（3）设则
，
（定理8） 为矩阵对策，且 ，其中
）和
了为斜对称矩阵（亦称这种对策为对称对策）。分别为局中人I 和
的最优策略集。（定理9）
，其中
，
。（定理7）
，其中a>0
为任一常数。则
① ，所以得
，有
，
使
相关内容
相关标签