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

一、简答题

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 标号，即:

2． 什么是启发式方法? 说明用启发式方法解决实际问题的过程和步骤。

【答案】（1）对于结构不良问题，为得到近似可用的解，分析人员必须运用自己的感知和洞察力，从与其有关而 较基本的模型与算法中寻求其间的联系，从中得到启发，去发现适于解决该问题的思路和途径，这种方法称为启 发式方法。

（2）用启发式方法解决实际问题的过程和步骤:①系统观察和分析实际问题; ②抽象并明确提出问题; ③ 建立启发式数学模型; ④选择启发式策略，设计启发式方法，按照一定的搜索规则反复迭代逼近模型最优可行解，直到得到满意解; ⑤检验和修正模型及其满意解。

3． 简述对偶问题的“互补松弛性”。

【答案】互补松弛性:若仅当为最优解。 分别是原问题和对偶问题的可行解。那么，当且 当存在两个以上最小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。

4． 考虑两个企业的资源整合问题。如果每个单位单独组织生产，各自的效益和，往往小于把两个单位的生 产要素进行重组，然后再统筹生产带来的收益高。因此，资产重组，往往能够带来“双赢”的格局，企业自身也 希望通过合并，做大做强。问题是，每个企业可能会故意夸大其利润水平，从而希冀分得更多的合作收益。请谈谈你的设想，用以协调 其中可能出现的问题（不超过300字，可用符号表述你的想法）?

【答案】让两个企业单独汇报独立生产能获得的利润，分别记为z 1、z 2。如果z 1+z2≦z 成之，则将

，按照z 1、z 2的比例进行分配。这样的分配方式，两个企业说真话，合作后的额外收益z-（z 1+z2）

是一个均衡策略。

二、计算题

5． 己知运价表如表所示:

表

求解总运费最小的最优解（注:求解方法不限，要求写出必要的计算过程）。

【答案】此问题是一个产销不平衡的运输问题，首先增加一个假想的产地戊，其产量为30，运价为0，化为产销平衡问题如表所示:

表

采用伏格尔法，求得初始解如下:

表

采用位势法检验，得下表:

表

表中还有负检验数，说明未得最优解，用闭回路法进行改进，如表所示:

表

确定调入量θ=min（50，20，30）=20。按闭回路上的正负号，加入和减去20，得到调整方案，如表所示:

表

对上表结果在采用位势法求各空格的检验数，如表所示:

表

此时所有检验数都非负，即达到最优，最小运费为:

40×2+30×2+20×4+60×3+30×5=580

6． 证明如下序列不可能是某个简单图的次的序列:

（l ）7，6，5，4，3，2;

（2）6，6，5，4，3，2，l ;

（3）6，5，5，4，3，2，l 。

【答案】（1）由定理知，

能是图的次序列。

（2）此序列中，奇点为5，3，1，个数是奇数，所以此序列不可能为图的次的序列。

（3）对于七个顶点的图，若依次假定d （v 1）=6，d （v 2）=5，…，d （v 7）=l。

； v 2与v 1之间存在边e 12:，而①假定G 中无重复边，则v 1与其他六个顶点皆有连线（包括与v 7）

为偶数，而在此序列中，为奇数，所以此序列不可