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

一、简答题

1． 试写出M/M/1排队系统的Little 公式。 【答案】M/M/1排队系统的Little 公式为

2． 试将Norback 和love 提出的几何法与C 一W 节约算法进行比较。

【答案】（1）几何法:首先找出凸包，然后考查以不在旅行线路上的点为角顶，以线路上的点的连线为对边的角的大小，选出最大者所对应的角顶，插入到旅行线路中，反复进行直至形成哈密尔顿回路。

（2）C 一W 节约算法:首先以某一点为基点，确定初始解，然后考查基点之外的其它点的连线所构成的弧的 节约值的大小，选出节约值最大者所对应的弧，插入到旅行线路中，直至旅行线路中包含所有的点。

3． 在线性规划的灵敏度分析中，当基变量的价值系数变化后，最优表中哪些数据会发生变化，怎样变化。

【答案】基变量的价值系数变化后，可能会引起伏表中基变量检验数的变化。 设Cr 是基变量Xr 的系数。因

，当Cr 变化△Cr ，时，就引起C B 的变化，这时有:

可见，当Cr 变化成△Cr 后，最终表中的检验数是:

二、证明题

4． 证明:（1）若（2）若

和

和

是对策G 的两个解，则

和

。

也是对策G 的解。

是对策G 的两个解，则是G 的解，所以

①

【答案】（1）因为

同理，因为是G 的解，所以

②

由不等式①可知

③

由不等式②可知

④

由不等式③与不等式④可知

（2）由（1）证明过程中不等式③和不等式④可知即解。

5． 对于单服务台情形，试证: （1）定长服务时间长服务时间【答案】对于

是负指数服务时间

排队系统，

的一半。

，即可知，

故

。

也是

，是负指数服务时间的一半; （2）定

当k=l时，则

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

当k →∞时，则

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

所以，

定长服务时间

的一半。

6． 设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 中去掉任一条边，都必在某一圈中。而从圈中去掉任一条边，所得图仍是连通图。