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

一、计算题

1． 给一个连通的赋权图G ，类似于求G 的最小支撑树的Kruskal 方法，给出一个求G 的最大支撑树的方法。

【答案】类似于避圈法。

第一步选一条最大权边，之后每步均从未被选取的边中选最大权边，加入到树的边的集合中，并要求不能与 已选取的边构成圈（若在某步中存在两条及以上的边都是最大权边，则从中任选一条）。

2． 表表示某运输问题的运价表和供需关系表。用最小元素法确定初始调运方案，并判断是否最优:

表

【答案】用最小元素法确定初始方案为表

表

用位势法对上述的初始方案进行检验，

表

由上可看出，所有非基变量的检验数均不为负数，故该方案是最优方案。

3． 线性规划问题

当t l =t2=0时，该问题的最优单纯型表如表所示。

表

（l ）确定所有参数，并写出该线性规划问题; （2）当t 2=0时，分析使最优解不变的t 1的变化范围; （3）当t 1=0时，分析使最优基不变的t 2的变化范围。

【答案】（l ）由最优单纯型表得出，x l 和x 3为基变量x B ，则对应初始单纯形表中为:

由最优单纯型表得到由由由由

，得, 得

, 得, 得

（2）x 1是基本量，它的系数变化会影响到检验数的变化。若使最优解不变，应有:

, 解得

, 所以, 求得, 解得, 解得

，即

,

综上，当t l =t2=0时，线性规划为

（3）

将其反映到最终单纯形表中，其b 列数字为:

当b ≥0时问题的最优解不变，解得

4． 某航空公司售票处开展电话订票业务。据统计分析，电话到达过程服从泊松分布，平均到达率为每小时 20个，平均每个业务员每小时可以处理10个电话订票业务。请问该公司应该安装多少台电话，才能使因电话占 线而损失的概率小于10%。 【答案】

假设公司应该安装c 台电话，故

所有电话都占线的概率为:

解得c=5

5． 田忌和齐王赛马，他们各有上、中、下三匹不同等级的马，但是齐王的马比田忌同等级的马稍高一筹，即齐王同等级的马要胜过田忌同等级的马，但是不同级别的马则相差很远。每匹马只能出场一次，采取三局两胜 的记分方法。请给出比赛结果田忌的赢得矩阵。 【答案】设齐王和田忌的策略集分别为

田忌的赢得可用表表示。

表

，

所以，田忌的赢得矩阵是