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

一、简答题

1． 试说明C 一W 节约算法的基本思想，你认为还可用它解决哪些方面的问题? 举例加以说明。

【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧插入到旅行线路中， 这样在满足访问若干城市各一次且仅一次的条件下，最大限度地缩短了路程。

（2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点i 与点j 维修时间总和的一半。优先考虑将节约值最大的长度加入工作线路中去进行迭代。

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

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

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

二、计算题

3． 某公司要将一批货从二个产地运到四个销地，有关数据如表所示。

表

现要求制定调运计划，且依次满足:

（l ）B3的供应量不低于需要量;

（2）其余销地的供应量不低于85%;

（3）A 3给B 3的供应量不低于200;

（4）A 2尽可能少给B 1;

（5）销地B 2、B 3的供应量尽可能保持平衡。

（6）使总运费最小。

试建立该问题的目标规划数学模型。

【答案】设x if 为A i 到B i 的运量，数学模型为

B 3保证供应

B 1需求的85%

B 2需求的85%

B 3需求的85%

A 3对B 3

A 2对B 1

B 2与B 3的平衡

运费最小

4． 已知运输问题的产销平衡表、单位运价表及最优调运方案分别见表1和表2，试回答下列问题。

表1 表

2

（l ）从

（2）从的单位运价c 22在什么范围变化时，上述最优调运方案不变?

的单位运价c 24变为何值时，有无穷多最优调运方案? 除表30中方案外，至少

再写出其他两种。

【答案】（l ）因为，当以单位运价表计算的基变量检验数为0，且非基变量检验数为非负时，调运方案不变。所以，假设c 22未知，对表1中的最优调运方案，利用位势法计算非基变量的检验数，如表3所示。

表

3

要使所有非基变量的检验数非负，则应满足条件

计算得，当时，表30给出的最优方案不变。

（2）当存在某非基变量的检验数为0时，有无穷多最优解。假设c 24未知，利用位势法计算所有非基变量的检验数，如表4所示。

表

4

由所示。 可得，所以当c 24变为17时，此问题有无穷多最优调运方案。以（A 2，B 4）为调入格，作一闭回路，取不同的调入量对其进行调整可得到其它两个最优调运方案，如表5，6

表5 表6