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

一、简答题

1． 什么是可行流?

【答案】满足下列条件的网络流f 称为可行流 （l ）容量限制条件:对每一弧（v i ，v j ）对于起点Vs ，记对于终点V t ，记

（2）平衡条件 对于中间点，流出量=流入量，即对每个

式中，V （f ）称为这个可行流f 的流量，即发点的净输出量（或收点的净输入量）。

2． 试写出求解最短径路的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 标号进行如下修改:T （v j ）=min[T（v i ），p （v i ）+lij ]

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

当存在两个以

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

二、计算题

3． 工件按泊松流到达服务台，平均间隔时间为10分钟，假设对每一工件的服务（加工）所需时间服从负指 数分布，平均服务时间为8分钟。求:

（l ）工件在系统内等待平均数和工件在系统内平均逗留时间。

（2）若要求有90%的把握使工件在系统内的逗留时间不超过30分钟，则工件的平均服务时间最多是多少?

（3）若每一工件的服务分二段，每段所需时间都服从负指数分布，平均都为4分钟。在这种情况下，工件 在系统内的平均瘦身是多少?

【答案】（l ）

该模型为

（2）工作系统内逗留时间服从参数为刀

平均服务时间最多为5.656min （3）

的负指数分布。

4． 在某单人理发店顾客到达为泊松流，平均到达间隔为20 min，理发时间服从负指数分布，平均时间为 15 min。求:

（l ）顾客来理发不必等待的概率; （2）理发店内顾客平均数; （3）顾客在理发店内平均逗留时间;

（4）若顾客在店内平均逗留时间超过1.25h ，则店主将考虑增加设备及理发员，问平均到达率提高多少时，店主才做这样的考虑?

【答案】该系统为M/M/1模型，

5． 已知世界六大城市:P e ，N ，P a ，L ，T ，M 。试在表所示交通网络的数据中确定最小树。

表

【答案】将表用图形的形式表示出来，如图所示。

图

（1）采用避圈法。从图中选取权数最小的边[L，P a ]; 从未选的边中，选取权最小的边[Pe ，T]:依次进行，并使得它们相互不构成圈，直到再也不能选取出边为止。经过五次选边，得到边集合 {[L，P a ]，[Pe ，T]，[M，N]，[L，N]，[Pe ，L]}构成了唯一的最小支撑树，如图所示，此最小支撑树的总权为119。

图

（2）采用破圈法。应用破圈法的原理，依次进行破圈，直到所有边构成的图中不含有圈为止。所得到的结 果与上述避圈法的相同。