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

一、简答题

1． 试写出标准指派问题的线性规划问题。

【答案】

A ij 表示工作人员i 做工作j 时的工作效益 则得线性规划模型为:

2． 简述常用的不确定型决策准则。

【答案】不确定性决策是指决策者对将发生结果的概率一无所知，只能凭决策者的主观倾向进行决策，适用于对 概率判断缺乏信心，对事情做出简单的估计。。不确定性决策由决策者的主 观态度不同基本可分为四种准则:悲 观主义准则、乐观主义准则、等可能性准则、最小机会准则。

（l ）悲观主义决策准则:行中取min ，再取max 。 （2）乐观主义决策准则:行中取max ，再取max 。

（3）等可能性准则:先求各策略的收益期望值，再从中取max 。 （4）最小机会损失准则:

机会损失矩阵:每一列的值为列中最大的数分别减去其他的数（自己则变为0，其他的值全大，即

于等于0）

（5）折衷主义决策准则

其中a （最小收益值。

然后选择

3． 试写出求解最短径路的Dijkstra 算法的步骤。

【答案】Dijkstra 算法的步骤为:

第 2 页，共 24 页

。

）为乐观系数，，。分别表示第i 个策略可能得到的最大收益值与

（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 标号进行如下修改:T （v j ）=min[T（v i ），p （v i ）+lij ]

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

当存在两个以

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

4． 在解决实际问题时应如何运用启发式策略? 除本书上列出的几个启发式策略之外，你认为还有什么样的策略可以使用?

【答案】在解决实际问题时，可根据实际问题的性质和要求来选用某一启发式策略; 为得到理想效果，也可将几个策略联合起来使用。除本书上列出的几个启发式策略之外，还有计算机仿真、模拟策略、类比策略、近似策略等可以使用。

二、证明题

5． 现有一个线性规划问题（P 1）:

, 其对偶问题的最优解为Y*=（y1, y2, y3, …ym ）

另有一线性规划（P 2）:

【答案】问题（P 2）的对偶问题为:

问题（P 2）的对偶问题为:

T

其中，d=（d 1, d 2, ...d 3） 。 求证:

易见，问题（P 1）的对偶问题与问题（P 2）的对偶问题具有相同的约束条件，从而，问题（P 1）的对偶问 题的最优解

令问题（P 2）的对偶问题的最优解为

6． 证明:矩阵对策

的鞍点不存在的充要条件是有一条对角线的每一个元素均大于另一对角线上的每一个元素。

第 3 页，共 24 页

一定是问题（P 2）的对偶问题的可行解。 ，则:

。

因为原问题与对偶问题的最优值相等，所以

【答案】（l ）先证充分性，要使鞍点存在，就必存在有

①

使对一切，

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

则充分性得证。

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

又可假设

其他情形同理可类推得出存在鞍点，由命题与逆否命题等价可知必要性成立. 7． 设

是正定二次函数

。试证:若

关于Q 共扼

分别

在两条平行

于方向P 的直线上的极小点，则方向p 与方向

【答案】因为则有从而又由于则有

分别是f （x ）在两条平行于方向P 的直线上的极小点， ，

8． 车间内有m 台机器，有c 个修理工（m>c），每台机器发生故障率为兄，符合M/M/c/m/m模型， 试证:

【答案】由题设知

并说明上式左右两端的概率意义。

第 4 页，共 24 页