当前位置：问答库＞考研试题

一、选择题

1． 设线性规划A. 基本可行解 B. 基本可行最优解 C. 最优解 D. 基本解 【答案】A

【解析】可行解包括基可行解与非基可行解。

2． 求一个赋权图中包括指定边集的最小连接方案（最小树），下面（ ）方法是正确的。 A. 最小树的初始边集为图中最小权边，按其余各边的权从小到大，逐一检查选取 B. 最小树的初始边集为某一条指定边，按其余各边边的权从小到大，逐一检查选取 C. 最小树的初始边集为所有指定边的集合，按其余各边边的权从小到大，逐一检查选取 D. 最小树的初始边集为权最小的一条指定边，按其余各边边的权从小到大，逐一检查选取 【答案】C

【解析】该问题不是简单的最短路问题，它要求最小连接方案包括指定边集，所以，最小树的初始边集应为 所有指定边的集合。

3． 关于最小费用最大流，求解时不会用到下面哪种方法（ ）。 A.Dijkstra 算法 B.Floyd 算法

C.Ford 一Fulkerson 算法 D. 奇偶点作业法 【答案】D

【解析】奇偶点作业法为中国邮递员问题中寻找欧拉圈时所用的方法，最小费用最大流问题并不涉及此法。

有可行解，则此线性规划一定有（ ）。

二、填空题

4． 若对偶问题为无界解，则原问题:_____。 【答案】无可行解

【解析】任一对偶问题的可行解都是原问题的上界，而原问题的任意可行解都是对偶问题的下界。若对偶问题为无界解，则原问题的目标函数有可行解。

第 2 页，共 24 页

无界，即无限小，则z 无解，即没

5． 图G=（V ，E ）有生成树的充分必要条件是___。 【答案】G 是连通图

【解析】图G 是连通图，如果G 不含圈，那么G 本身是一个树，从而G 使它自身的一个支撑树。现设G 含圈，任取一个圈，从圈中任意地去掉一条边，得到G 的一个支撑子图Gl 。如果Gl 不含圈，那么Gl 是G 的 一个支撑树，如果Gl 仍含圈，那么从Gl 中再任取一个圈，如此重复，最终可以得到G 的一个支撑子图Gk ， 它不含圈，于是Gk 就是G 的一个支撑树。

6． 对于线性规划问题:MaxZ=CX.AX≦b.X ≧0，若B=（P 1，P 2，…，P m ）为A 中m 个线性无关的列向量, 且为该LP 的一个可行基，则对应于基B 的基可行解为:_____，该基可行解为最优解的条件是:_____。 【答案】

，对于一切

有

。

【解析】若B=（P 1，P 2，…，P m ）为A 中m 个线性无关的列向量，此时令非基变

量

， 这时变量的个数等于线性方程组的个数，用高斯消去法，可求得对应

于基B 的基可行解

为

。由最优解的判别定理，若对于一

切

, 则所求得的基可 行解为最优解。

7． 若P （k ）是f （x ）在x （K ）处的下降方向，则满足_。

【答案】均有 【解析】若存在实数

，使对于任意的

，就称方向

）为

均有下式成立:

点的一个下降方向。

三、证明题

8． 证明:r （x ）二x12+x22是严格凸函数。 【答案】首先求导为（2x l ，2x 2:） 求海塞矩阵

为正定矩阵，所以f （x ）为严格凸函数 9． 证明:矩阵对策

的鞍点不存在的充要条件是有一条对角线的每一个元素均大于另一对角线上的每一个元素。 【答案】（l ）先证充分性，要使鞍点存在，

就必存在

①

可假设主对角线的每一个元素均大于次对角的每一个元素，即

使对一切

，

有

第 3 页，共 24 页

则充分性得证。

（2）证必要性。假设“有一条对角线的每一个元素均大于另一条对角线上的每一个元素”这种情形不存在，则可设

又可假设

其他情形同理可类推得出存在鞍点，由命题与逆否命题等价可知必要性成立. 10．对于单服务台情形，试证: （1）定长服务时间长服务时间【答案】对于

是负指数服务时间

排队系统，

当k=l时，则

变成M 分布，即上式指标变成M/M/1排队系统指标，即

当k →∞时，则

分布变成D 分布，即上式指标变成M/D/l排队系统指标，即

所以，定长服务时间

的一半。

，

是负指数服务时间

的一半; 定长服务时间

是负指数服务时间

的一半。

，是负指数服务时间

的一半; （2）定

第 4 页，共 24 页