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

一、计算题

1． 某建筑公司最近几年的发展重点是承接中东等地区的建筑项目。公司需要一种大型的建筑设备，该设备 今后4年的购买价格（预测值）分别为（5 .0，5.3，5.7，6.0）（万元）（产品购买价+运输到工地的费用）。如该设备连 续使用，其第i 年的使用费及维修费分别为（l ，1.7，2.5，3.3），（万元）由于路途遥远，淘汰后的设备就在当地折价 处理了，使用满i 年的设备处理价格为（3.3，2.5，1.5，0.8）（万元）. 公司在制定一个4年的设备购买计划，你有什 么建议? （限用图论理论，写出算法，计算过程，最终结论，最佳总费用）

【答案】可以把这个问题转化为最短路问题，根据题意绘制如下赋权有向图。

图

采用Dijksra 算法计算图1中的最短路为:

（l ）对起点1进行P 标号，即p （l ）=0; 对其余点进行T 标号，

即检查点1，进行T 标号：（2）点2获得P 标号，. （3）点3获得P 标号，（4）点4获得P 标号，（5）点5获得P 标号，）上图中的最短路为

检查点2，修改T 标号:检查点3，修改T 标号:检查点4，无需修改T 标号。 求解结束。

。即第一年初购进一台设备，第三年初淘汰掉并购置新设备，直至第

四年末淘汰 掉。最佳总费用11.1万元。

2． 有一运输问题，它有3个重载点和2个车场，其运输表如表所示。表中小方框内的数字为两点 间的车辆空驶距离，l 、2和3三项运输业务的重载里程（己将装卸车时间折算在内）分别为7，8和9，其他有关情况如表中所示。此外，要求车辆的每条行车路线总长度（包括重驶、空驶及装卸车所用时间的折算长度）L 在45~ 60之间。试用本章给出的车辆优化调度启发式算法，求出其满意的可接受可行解，并据此排出行车路线。

表

【答案】（l ）首先只考虑重载点的情况，利用伏格尔法进行求解，并且用位势法进行检验，得到只考虑重载点的最优解为

（2）解的扩展

按照由小到大顺序对

进行调整

（3）解的收缩 因为

，其非零分量为:

所以，不需要进行解的收缩过程。从而得到可行解X （）

,

（4）安排行车路线

以可行解X （）为依据可安排行车线路，并且考虑到行车路线总长度，安排线路如下。 ①通车数目为4，路线为4→1→3→1→5，线路总长为 6+10+12+10+（7×2+9）=60 ∈［45, 60］

②通车数目为3，路线为5→2→1→1→3→5，线路总长为 2+2+4+10+2+（7×2+8+9）=20+31=51 ∈［45, 60］ ③通车数目为3，路线为5→1→2→1→4，线路总长为 14+12+2+8+（7x2+8）=58 ∈［45, 60］

3． 利用库恩一塔克条件求解以下问题:

（l ）试写出库恩一塔克条件。

（2）a 满足什么条件以上问题有最优解? （3）分别求出相应的最优解和最优值。 【答案】（l ）所求问题变形为

l

l

故库恩一塔克条件为