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

一、简答题

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

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

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

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

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

3． 试写出求解最短径路的Dijkstra 算法的步骤。 【答案】Dijkstra 算法的步骤为:

（l ）给v s 以p 标号，P （v S ）二0，其余各点均给T 标号，T （v i ）=+∞。

（2）若v i 点为刚得到P 标号的点，考虑这样的点v i ，（v i ，vj ）属于E ，且v i 为T 标号。对v j 的T ，p （v i ）+lij ] 标号进行如下修改:T （v j ）=min[T（v i ）

（3）比较所有具有T 标号的点，把最小者改为P 标号，即:

当存在两个以上最

小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。

二、证明题

4． 己知九个人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两两相连，即存在三人之间互相握过手。 5． . 令试证

【答案

】

为一组

使得

用

左乘上式，并且由共轭关系可知：

令由

知BA=E，所以故得证。

6． 设G 为2*2对策，且不存在鞍点。证明若

。

【答案】可利用反证法求证。 假设条件不成立，可设

。

又

。

当

时，对

，存在鞍点，最优纯策略为

; 当a 12=a11=a21时

，，所以

和

是G 的解，

则

。

A

共轭向量，它们必线性无关。

则

。

，A 为为一组A 共轭向量（假定为列向量）

对称正定矩阵，

， 存在鞍点，最优纯策略为

，这与G 不存在鞍点矛盾，故结论成立。