2017年太原科技大学经济与管理学院836运筹学考研导师圈点必考题汇编
● 摘要
一、填空题
1． 网络中如果树的节点个数为z ，则边的个数为_____。
【答案】z-l
【解析】由树的性质可知，树的边数=数的节点数-1
2． 若P （k ）是f （x ）在x （K ）处的下降方向，则满足_____。
【答案】均有
【解析】若存在实数
，使对于任意的
，就称方向
）为
均有下式成立:
点的一个下降方向。
3． 某整数规划模型，解其松弛问题得到最优解。若其中某分量x j 二场为非整数，用分支定界法求解时，针对 该分量构造的两个约束条件应为:_____。
【答案】
【解析】由分支定界法的原理可以，良容易得至“结果，其中〔b j 〕为不大于bj 的最大整数。
4． Fibonacoi 法在[2，6]区间上取的初始点是_____。
【答案】
，
【解析】由Fibonacci 的计算方法可知。
二、选择题
5． 求一个赋权图中包括指定边集的最小连接方案（最小树），下面（ ）方法是正确的。
A. 最小树的初始边集为图中最小权边，按其余各边的权从小到大，逐一检查选取 B. 最小树的初始边集为某一条指定边，按其余各边边的权从小到大，逐一检查选取 C. 最小树的初始边集为所有指定边的集合，按其余各边边的权从小到大，逐一检查选取 D. 最小树的初始边集为权最小的一条指定边，按其余各边边的权从小到大，逐一检查选取 【答案】C
【解析】该问题不是简单的最短路问题，它要求最小连接方案包括指定边集，所以，最小树的初始边集应为 所有指定边的集合。
6． 在产销平衡运输问题中，设产地有m 个，销地有n 个。如果用最小元素法求最优解，那么基变量的个数 为（ ）。
A. 不能大于（m+n-1） B. 不能小于（m+n-l） C. 等于（m+n-l） D. 不确定 【答案】A
【解析】在运输问题中，其自变量的个数是m ×n ，约束方程有m+n个，但是对于产销平衡问题，有以下关系式存在:
。故，模型最多只有m+n﹣1个独立方程，
由此得运输问题最多有m+n﹣1个基变量。当出现退化解时，基变量小于m+n﹣1个。
7． 己知Y i 为线性规划的对偶问题的最优解，若Y i >0，说明（ ）。
A. 原问题的最优解x i =0
B. 在最优生产计划中第i 种资源己完全耗尽 C. 在最优生产计划中第i 种资源有剩余 D. 无法判断 【答案】B
【解析】当影子价格为0时，表示某种资源未得到充分利用; 而当资源的影子价格不为零时，表明该种资源在生产中己耗费完毕。
8． 用匈牙利法求解指派问题时，不可以进行的操作是（ ）。
A. 效益矩阵的每行同时乘以一个常数 B. 效益矩阵的每行同时加上一个常数 C. 效益矩阵的每行同时减去一个常数 D. 效益矩阵乘以一个常数 【答案】D
【解析】效益矩阵乘以一个常数相当于系数矩阵的某行或某列乘以一个常数，这相当于目标函数中的部分系 数乘以一个常数，而目标函数整体乘以一个系数，显然会影响求解结果。
三、证明题
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．假设线性规划问题为:
其中
，秩
运用单纯形算法求得的最优基可行解时，所有的非基变量检验数全都<0，试证明这时所得到的最优解必定 是线性规划问题（l ）的准最优解。
【答案】一般情况下，经过迭代后解变为
再将上式代入目标函数式，整理后得到
令于是
再令则
时，此时的解就为最优解。
这样当所有非基变量的检验数即
11．车间内有m 台机器，有c 个修理工（m>c），每台机器发生故障率为兄，符合M/M/c/m/m模型， 试证:
【答案】由题设知
一个周期T c 等于发生故障的机器在系统中的逗留时间W s 加上机连续正常工作时间
为 服务台繁忙的概率。服务台繁忙的概率也为
，所以
。
，
则
并说明上式左右两端的概率意义。