2016年华东交通大学经济管理学院812运筹学考研内部复习题及答案
● 摘要
一、选择题
1． 己知Y i 为线性规划的对偶问题的最优解，若Y i >0，说明（ ）。 A. 原问题的最优解x i =0
B. 在最优生产计划中第i 种资源己完全耗尽 C. 在最优生产计划中第i 种资源有剩余 D. 无法判断 【答案】B
【解析】当影子价格为0时，表示某种资源未得到充分利用; 而当资源的影子价格不为零时，表明该种资源在生产中己耗费完毕。
2． 求一个赋权图中包括指定边集的最小连接方案（最小树），下面（ ）方法是正确的。 A. 最小树的初始边集为图中最小权边，按其余各边的权从小到大，逐一检查选取 B. 最小树的初始边集为某一条指定边，按其余各边边的权从小到大，逐一检查选取 C. 最小树的初始边集为所有指定边的集合，按其余各边边的权从小到大，逐一检查选取 D. 最小树的初始边集为权最小的一条指定边，按其余各边边的权从小到大，逐一检查选取 【答案】C
【解析】该问题不是简单的最短路问题，它要求最小连接方案包括指定边集，所以，最小树的初始边集应为 所有指定边的集合。
3． 如果要使目标规划实际实现值不超过目标值，则相应的偏离变量应满足（ ）。 A.d 十>0; B.d 十=0; C.d 一=0; D.d 十>0且d 一>0 【答案】B
【解析】实际实现值不超过目标值，即.
，根据
，可知
4． 单纯形法中，关于松弛变量和人工变量，以下说法正确的是（ ）。 A. 在最后的解中，松弛变量必须为0，人工变量不必为0 B. 在最后的解中，松弛变量不必为0，人工变量必须为0 C. 在最后的解中，松弛变量和人工变量都必须为0 D. 在最后的解中，松弛变量和人工变量都不必为0 【答案】B
【解析】松弛变量是在约束不等式号的左端加入的，在最后的解中，其值可以不必为0; 人工变量是在原约束条件为等式的情况下加入的，只有基变量中不再含有非零的人工变量时，原问题才有
解，所有最后的解中人工变量必须为0。
二、填空题
5． 某极小化线性规划问题的对偶问题的最优解的第1个分量为y l =-12，则该问题的第1个约束条件的右端常数项的对偶价格为:_____。 【答案】-12
【解析】由对偶问题的经济解释可知，原问题约束条件的右端常数项的对偶价格等于对偶问题的最优解中相 应的分量的值。 6． 若P （ 【答案】
【解析】若存在实数
【答案】G 是连通图
【解析】图G 是连通图，如果G 不含圈，那么G 本身是一个树，从而G 使它自身的一个支撑树。现设G 含圈，任取一个圈，从圈中任意地去掉一条边，得到G 的一个支撑子图Gl 。如果Gl 不含圈，那么Gl 是G 的 一个支撑树，如果Gl 仍含圈，那么从Gl 中再任取一个圈，如此重复，最终可以得到G 的一个支撑子图Gk ， 它不含圈，于是Gk 就是G 的一个支撑树。
8． 若x 为某极大化线性规划问题的一个基可行解，用非基变量表达其目标函数的形式为
则X 为该LP 最优解的条件是:_____。 【答案】
。
【解析】求极大化问题，则当所有非基变量的检验数均为非正时，即得最优解。线性规划最优时要求非基变 量检验数小于等于0，所以
k ）
是
f （x ）在x （
K ）
处的下降方向，则满足_。
均有下式成立:
）为
点的一个下降方向。
，就称方向
均有
，使对于任意的
7． 图G=（V ，E ）有生成树的充分必要条件是___。
三、证明题
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中至少有两个点与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．车间内有m 台机器，有c 个修理工（m>c），每台机器发生故障率为兄，符合M/M/c/m/m模型， 试证:
【答案】由题设知
一个周期T c 等于发生故障的机器在系统中的逗留时间W s
加上机连续正常工作时间
为 服务台繁忙的概率。服务台繁忙的概率也为
11．对于M/M/1/m/m模型，试证【答案】因为
，所以
。
，
则
并说明上式左右两端的概率意义。
，并给与直观解释。
。
若L s 表示系统中平均出故障的机器数，则系统外的机器平均数应为m 一L s 。于是，系统的有效到达率，即 m 台机器单位时间内实际发生故障的平均数为因此，有
12．现有一个线性规划问题（P 1）:
，即
。
, 其对偶问题的最优解为Y*=（y1, y2, y3, …ym ）
。
另有一线性规划（P 2）:
【答案】问题（P 2）的对偶问题为:
问题（P 2）的对偶问题为:
其中，d=（d 1, d 2, ...d 3） 。 求证:
T
易见，问题（P 1）的对偶问题与问题（P 2）的对偶问题具有相同的约束条件，从而，问题（P 1）的对偶问 题的最优解
令问题（P 2）的对偶问题的最优解为13．证明下列定理: （1）设有两个矩阵对策，
一定是问题（P 2）的对偶问题的可行解。 ，则:
。
，其中
因为原问题与对偶问题的最优值相等，所以