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

一、简答题

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

A ij 表示工作人员i 做工作j 时的工作效益

则得线性规划模型为:

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

，p （v i ）+lij ] 标号进行如下修改:T （v j ）=min[T（v i ）

（3）比较所有具有T 标号的点，把最小者改为P 标号，即: 当存在两个以上最小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。

二、计算题

3． 出从1节点到U 节点的最短路径

图

【答案】Dijkstra 算法，即标号法求解

（l ）对节点l 进行P 标号，即P （1）=0，其余点进行T 标号，即T （j ）=+∞ 因为

而

（2）修改节点3、5的T 标号

因为

（3）修改节点6，8的标号

因为

（4）修改节点9的标号

因为

（5）修改节点7的标号

因为

（6）修改节点9、11的标号

因为

（7）修改节点12的标号

因为故将点12进行P 标号，

故将节点2进行P 标号， 故将点5进行P 标号， 故将点6进行P 标号， 故将点4进行P 标号， 故将点8进行P 标号， 故将点9进行P 标号，

顶节点12已经进行了P 标号，且线为1→2→5→8→11→12

4． 用割平面法求解整数规划。

于是得到节点1到节点12的最短路程为18，最短路

【答案】松弛问题的单纯形最优表为:

从最优单纯形表中可知，X 2=7/4，有最大小数部分3/4，故从最优单纯形表的第二行产生割平面约束。 割平面约束为:

引入松弛变量x 5，得割平面方程

表

将上式代入最优单纯形表，然后用对偶单纯形法求解，得表：

续表