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

一、简答题

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

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

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

2． 试将Norback 和love 提出的几何法与C 一W 节约算法进行比较。

【答案】（1）几何法:首先找出凸包，然后考查以不在旅行线路上的点为角顶，以线路上的点的连线为对边的角的大小，选出最大者所对应的角顶，插入到旅行线路中，反复进行直至形成哈密尔顿回路。

（2）C 一W 节约算法:首先以某一点为基点，确定初始解，然后考查基点之外的其它点的连线所构成的弧的 节约值的大小，选出节约值最大者所对应的弧，插入到旅行线路中，直至旅行线路中包含所有的点。

二、计算题

3． 在图中，分别求v 1至v 6，v 1至V 4，v 6至v Z 和v Z 至vs 的最短路和最短距离。

图

【答案】用Floyd 方法求解

令网络的权矩阵为

其中，为到的距离

由表示从v i 到v j 点的或

直接有边或借v 1点为中间点是的最短路长，括弧中元素为更新元素，得

表示从vi 到vj 点最多经v l ，v 2的最短路长，得

以此类推，

所以v l 至v 6的最短路是v 1一v 3一v 5一v 6，最短距离是-1;

v l 至v 4的最短路是v 1一v 3一v 5一v 4，最短距离是3;

v 6至v 2的最短路是v 6一v 4一v 2，最短距离是3:

v 2至v 5的最短路是v 2一v3一v 5，最短距离1;

4． 某造船厂根据合同要从当年起连续三年末各提供三艘规格型号相同的大型客货轮，已知该厂在三年内 生产大型客货轮的能力及每艘客货轮的成本如表1所示。

表

1

已知加班生产时，每艘客货轮成本比正常生产时高出70万元。又知造出来的客货轮如当年不交货，每艘每 积压一年造成积压损失为40万元。在签订合同时，该厂已储存了两艘客货轮，而该厂希望在第三年末完成合同 后还能储存一艘备用。问该厂应如何安排每年客货轮的生产量，使在满足上述各项要求的情况下，总的生产费用 加积压损失为最少?

【答案】设人为第A i 年的正常生产能力，A i ‘为第i 年的加班生产能力; B j 为第j 年的需求订货，S 为因积压而产生的供货能力。因为产大于销，所以虚拟一个销地B 4，于是可构造如表2的运价表。问题变为求解表1 的最优调运方案。

表2 单位：千万元

第一步:用伏格尔法求初始可行解，求得的初始解，如表3所示。

表3