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

一、简答题

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

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

（2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点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 标号进行如下修改:T （v j ）=min[T（v i ），p （v i ）+lij ]

（3）比较所有具有T 标号的点，把最小者改为P 标号，即:

当存在两个以

上最小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。

二、计算题

3． 一辆货车的有效载重量是20吨，载货有效空间是7×2.5×2m 。现有六件货物可供选择运输，每件货物 的重量、体积及收入如表所示。

表

另外，在货物4和5中优先运货物4，货物2和3不能混装，怎样安排货物运输使收入最大，建立数学模型， 说明是什么模型，可用什么方法求解（注:不要求求解）。

【答案】由题意建立数字模型如下:

该模型为0一1规划模型，可采用隐枚举法求解。

4． 试用SUMT 外点法求解

【答案】原非线性规划问题可改写为:

构造惩罚函数

令

，得

的解为

，为最优解。

5． 某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、巧00毫升和2000毫升，根据 需要列出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、 190、（单位毫升）。尚有10件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的 价格（单位美元）。这些物品的容量及价格分别见表，试建立数学模型给出一个合理的安排方案把物品放在 三个旅行包里。（不必求解）

表

【答案】设10件可带可不带的物品分别标号为1，……，10.

将必带物品中的400+150+760+190=1500的都放在1500的旅行包中，而300+250+450=1000正好放在1000的旅行包中，最后将2000的旅行包用来装可带可不带的物品，使的放入的物品越多越好，节约的费用越多越好，

设

6． 用运输问题的表上作业法求解线性规划问题:

【答案】由题意，得到运价表为:

由此可得，该问题是个运输平衡问题。 第一步，用沃格尔法得到初始方案为

第二步，用位势法得到初始方案中非基变量的检验数为

即x ll =10，从上述计算可得，所有非基变量的检验数均大于0，所以该初始方案就是最优方案。

x 13=20，x 22=15，x 23=5