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

一、简答题

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

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

当存在两个以

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

2． 一个运输问题，如果其单位运价表的某一行元素分别加上一个常数，最优调运方案是否发生变化，试说明理由（用表或直接用公式）;

【答案】最优方案不会发生变化。因为在计算任意空格的检验数时，若其通过变化行的一个基格，则其必经过两个基格，

则

最优方案不发生变化。

二、计算题

3． 如下线性规划问题:

当t l =t2=0时用单纯形法求解得最终单纯形表如下表所示: 试分析说明如下问题: （l ）确定

（2）当t 2=0时，t 1在什么范围内变化上述最优解不变:; （3）当t l =0时，t 2在什么范围内变化上述最优基不变。

表

的值;

【答案】（1）

（2）当t 2=0，变化的只有x l 的系数，代入到最优单纯形表，如表所示

表

若最优解不变，则

（3）当t l =0，变化的只有b l ，b 2的系数，最优解若不变，则

4． 有4个工人，要指派他们分别完成4项工作，每个人做各项工作所消耗的时间如表所示。问指派哪个人去完成哪项工作，可使总的消耗时间为最小?

表

【答案】第一步:将系数矩阵进行变换为

第二步:进行试指派，得到

因为m=3

第三步：做最少的直线覆盖所有的0元素，并进行再指派

指派成功，此项工作有多种指派方案，minz=70，指派矩阵如下:

由解矩阵得最优指派方案为: （1）

甲→A ，乙→D ，丙→C ，丁→B ;