基于最短路算法在生产最优化中的应用.docVIP

基于最短路算法在生产最优化中的应用 问题 最短路问题是图论中的一个重要问题。人们已经熟知最短路算法在电信、交通、电子设计及计算机等领域有广泛的应用[1～3 ] 。迪克斯特拉算法(Di2jkstra) 是典型最短路算法,可计算图的一个结点到其他结点的最短路径。本文给出基于迪克斯特拉算法的一种简捷有效的最短路算法实现,然后利用这一算法实现求解设备更新问题和原料选配问题,揭示最短路算法在生产优化领域的意义。 算法实现 有限权图可以是生产实践中各种图的抽象,如图1 所示。 若图中的点代表城市,边代表公路线或航线,边的权代表相应的路程或航程,也可以是某种费用,则两点间的最短路和距离即意味着两城市之间的最短行程或最低费用。 现就图1 给出一种迪克斯特拉最短路算法[4～6 ]的实现,该算法实现能一次求出权图中任一点到图中其余各点的最短路及距离。求图1 中点V3 到图中其余各点的最短路及距 离,运算格式如图2 所示。 图2 点V3 到其余各点的最短路及距离 此运算格式显示了点V3 到其余各点的最短路及距离。( V3 ) (0) 表示点V3 到本身的距离为0 ,(V3 ,V2 ) (1) 表示点V3 到点V2 的最短路及距离。此运算格式严格清晰显示了求解顺序及过程。下面给出上述运算格式的运算过程:①在一行中按任意顺序列出除V3 以外的其余各点,另起一行写出( V3 ) (0) ,然后从图1 中查出V3到各点的权,分别标在对应点的下面,从其中选出最小者1 ,则把1 及其所对应的点以条框圈起,同时另起一行写出( V3 , V2 ) (1) 即为点V3 到点V2 的最短路及距离,如图3 所示。 V3 到V2 点的最短路及距离 ②在①基础上,从图1 中查出V2 到除去V3 ,V2的其余各点的权并加上1 ( V3 到V2 的距离) ,分别标在各点的对应位置(1 + ∞= ∞) 。在第一步和现在所标出的权及权和中,条框圈起的除外,选取最小者为2 ,则把2 所对应的点及权和一列用条框圈起,同时另起一行写出( V3 , V5 ) (2) 即为V3 点到点V5 的最短路及距离,如图4 所示。 图4 　V3 点到V5 点的最短路及距离 继续第①②步的作法,运算过程中,若选取最小者时,同时有两个或两个以上相等,则任选一个即可。如此下去,直到除V3 以外的所有的点被条框所圈起,就得到上面所给出的运算结果格式。这里指出这一算法对于有向权图仍然适用。 3 　设备更新问题 某公司需要使用一种设备,第一年购进一新设备,若一台设备使用5 年,预期5 年之内维修费用依次为4 ,6 ,10 ,16 ,18 (万元) 。采购费用逐年增加,预期今后5 年之内一台新设备的采购费用依次为18 ,19 ,20 ,20 ,21 (万元) 为了保证在5 年之内都有该设备使用,如何安排维修采购,使费用最小? 此问题可化为求图的最短路径问题。以点Vi ( i = 1 ,2 ,3 ,4 ,5)表示“第i 年年初购进一台新设备”, V6 表示第5 年年底。弧( Vi , Vj ) 表示在第i 年年初购进的设备一直使用到第j 年年初所需费用,如图5 所示。 w ( V1 ,V3 ) = 18 + 4 + 6 = 28 ,其他各弧的权值可按已知数据算出。与上述的运算过程相同,得到的结果格式,如图6 所示。 运算结果显示费用最省的采购方案是在只在第2 年或只在第4 年采购新设备,这两个方案的费用均是68 ,为最小费用值。结果同时还给出了计划期为2 ,3 ,4 ,5 年的最优策略为不采购新设备。 4 　原料选用问题 某淀粉厂生产淀粉的原料可以为玉米、稻米和甘薯。在淀粉每月产量一定的情况下,三种不同原料前半年的采购费用随月份变化。玉米1～6 月的原料费用依次为:2 ,3 ,4 ,4 ,3 ,3 (万元) ,稻米1～6 月的原料费用依次为:4 ,3 ,2 ,2 ,2 ,2 (万元) ,甘薯1～6月的原料费用为:4 ,4 ,5 ,5 ,1 ,1 (万元) 。每月初做计划,确定本月采用何种原料。由于原料的改变,须更换生产设备,每次更换生产设备所需费用为1(万元) 。假设各种原料货源有保证,问前半年如何选用原料才能使生产总费用最少? 该问题可以化为求权图的最短路问题,如图7所示。 图中( V0 ,V1 ,1 ) , ( V1 ,1 ,V1 ,2 ) 和( V1 ,5 V6 ) 分别表示采用玉米为原料1 月,2 月和6 月的费用,其他单向弧的意义类似,双向弧表示设备转换费用。由最短路算法得不同月份的选料策略,如图8 所示。 　运算结果显示了从1 月份开始到其后各不同月份的原料选用策略。V0 V1 ,1 V1 ,2 V2 ,2 V2 ,3 V2 ,4 V3 ,4 V3 ,5V6 (13) 表示若从1 月份开始生产期为半年,