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

一、简答题

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

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

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

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． 某企业，用量最大的某种材料A ，需求基本稳定。原本是每月订一次货，一次订货的购货款是120万元， 订货提前期是5天，单价60元/公斤。目前流动资金比较紧张，获得货款又比较困难，企业领导考虑能否降低原 料库存量以减少基金占用。经过与供货厂家协商，对方在单价不变5天后即 可到货，的条件下，收到订单后可准备货源，该企业的年库存费率为平均存货额的20%。平均每次订货的费用为1200元。能否制定一个有效的库存 策略，使得库存占用资金降低50%，同时花在库存管理方面的费用尽可能低。（每月按30天计算）

【答案】

对于现行的订货策略： 订货批量

库存平均占用资金为:

第 2 页，共 38 页

一年的库存管理费用为如果采用经济订货批量 订货批量

库存平均占用资金为：一年的库存管理费用为

可见，要使库存占用资金降低50%，必须增加库存管理费用。 令

则订货周期

解得

一年的库存管理费用为24×1200=28800（元）

所以每隔15天订一次货，每次订货10000公斤，订货提前期为5天，即库存量降到3333公斤时订货。

4． 某公司有五台新设备，将有选择地分配给三个工厂，所得的收益如表所示

表

表中---表示不存在这样的方案。请用动态规划求出收益最大的分配方案。 【答案】将问题按工厂的个数分为3个阶段，

设s k 表示为分配给第k 个工厂到第n 个工厂的新设备数目， x k 表示为分配给第k 个工厂的新设备数目， 则

为分配给第k+l个工厂至第n 个工厂的设备数目，

表示为x k 个新设备分配给第k 个工厂所得的收益，

表示为s k 个设备分配给第k 个工厂到第n 个工厂时所得到的最大收益。 因而可写出逆推关系式为

第 3 页，共 38 页

下面从最后一阶段开始向前逆推计算: 第三阶段:

表

第二阶段：

表

第一阶段：

表

得到最优分配方案为:分配给工厂1两台新设备; 工厂3三台新设备，可得最大收益为16。

5． 用单纯形法求解如下LP 问题:

【答案】将原问题标准化:

第 4 页，共 38 页