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

一、简答题

1． 试写出求解最短径路的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）。 2． 对在多台设备上加工多个工件的工件排序问题来说，应如何衡量不同排序方案的优劣? 你认为应有哪 些准则? 这些准则的适用条件是什么? 请举出两个实例加以详细说明。

【答案】（l ）应根据工期最短、成本最低、质量最优等优劣标准来衡量不同排序方案的优劣。 （2）设备充分利用、总加工时间最短等某一或某几种目标函数最优。

（3）每个工件在m 台设备加工都有一定的先后顺序，工件在不同设备的加工顺序不同的情况不作考虑以及 信息掌握情况和资源约束等适用条件。

（4）举例。建筑施工流水作业问题:在不同的施工段上按一定的施工工艺进行施工，而施工工艺又由不同 的施工工序组成，每道施工工序都要消耗一定的人工费用，机械台班和材料费用，并且某些施工工序之间有一定的先后约束关系，如支起模板后才能浇注混凝土，而此问题关注不同施

使整个施工按照最短施工时间保持一定施工节拍进行流工工序如何搭接排序组成一定施工工艺，

水作业，同时消耗人、机、材等资源也合理。

二、计算题

3． 随机型网络计划假设某项工程的关键路线为（1，3，5，7，9），共有4项关键活动，各项活动的a ，m ，b 值由下表给出（单位:天）。试求总工期T E 的期望值和方差以及在17天内完工的概率。（其中: a 为最乐观的时间; b 为最保守的时间; m 为最可能的时

间

表 各项活动的a ，m ，b 值

【答案】由题意可知，根据己知条件，可以求解总工期的期望和方差为:

易知总工期T 服从均值为T ，方差为v ’的正态分布，即总工期服从N （Tz ，v ’）的正态分布在17天内完工的概 率为

即在17天内完工的概率为0.87.

4． 某公司为了扩大市场，要举行一个展销会，会址打算选择在甲、乙、丙三地。获利情况除了与会址有关系外，还与天气有关。天气可区分为晴、普通、多雨三种（分别以N 1，N 2，N3表示）. 通过天气预报，估计三种天气情况可能发生的概率为0.25，0.50，0.25。其收益情况见表，（1）用期望值准则进行决策。（2）用矩阵法进行决策。（3）用决策树法进行决策。

表

，E （乙），E （丙），则

【答案】（1）设选择甲、乙、丙三地的期望收益分别为E （甲）

选择甲地的期望收益最大。所以，最优方案为选择甲地。

（2）令收益矩阵为R ，概率矩阵为P ，期望值矩阵为E ，由表可知

于是

（3）构造决策树，并将有关数据标在决策树上，如图所示

可见甲地的期望收益最大，所以按矩阵法决策的最优方案为选择甲地。

图

，则

令选址方案为甲、乙和丙，三地的期望收益分别为E （甲）、E （乙）和E （丙）

因为E （甲）最大，所以采用决策树法进行决策的最优选址方案为甲地。 5． 判断表1和表2中给出的调运方案能否作为用表上作业法求解时的初始解? 为什么?

表1 表

2