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

一、简答题

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． 简述目标规划单纯形法求解的基本思想。

【答案】第一步，建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K 行，置k=l;

第二步，检查该行中是否存在负数，且对应的前k 一1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转第三步。若无负数。则转第五步;

第三步，按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别 的变量为换出变量;

第四步，按单纯形法进行基变换运算，建立新的计算表，返回第二步;

第五步，当k=K时，计算结束。表中的解即为满意解。否则置k=k+l，返回到第二步。

二、计算题

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

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

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

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

表

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

续表

最优解为

4． 用两阶段法求解以下线性规划问题

【答案】第一阶段:加入松弛变量x 4，x 5，人工变量x 6，数学模型为:

用单纯形法求解如表所示。

表

第一阶段的最优解为X=

第二阶段：除去人工变量x 6，目标函数为：

求解结果为

5． 为解决污水河流的污染问题，某城市拟修建污水处理站。备选的站址有A 、B 、C 三个，其投资等技术经 济参数如表所示:

表