论文部分内容阅读
摘要 叙述使用网络技术中的最短路径法求解教育装备全寿命周期最低费用的方法，为使实用性和可操作性更强，专门介绍求最短路径的Dijkstra算法。
关键词 全寿命周期费用；最短路径；Dijkstra算法
中图分类号 G48 文献标识码 A 文章编号 1671-489X（2008）12-0001-03
在教育装备的研究领域里，人们已经熟知了装备的全寿命周期费用（LCC，Life Cycle Cost）管理理论。全寿命周期一般是指设备的设计阶段、生产阶段、使用阶段和退役阶段，其费用涉及公司成本、用户成本和社会成本[1]。作为教育装备使用与管理者，更关心的是设备在使用阶段和退役阶段的费用问题；并希望找到一个方法，能够在保证设备性能的基础上产生最低费用。网络技术中的最短路径法可以解决这一问题。
1 网络技术与最短路径
对研究对象（事物）特征的描述，可以通过对事物的状态以及与其他事物之间的关系来表示。用结点表示事物的状态，而用结点间的连线（称为“边”）表示事物之间的关系就形成了一个网络（图1）。如果用结点（A、B、…F）代表装备的寿命周期时间分界点，而在边上标注出费用情况，就可以用网络技术来解决装备的寿命周期最小费用问题。
在步骤0时，v=A，结点A的相邻结点有B、C、D。这3个结点与结点A之间形成边的费用分别为2、5、1；而且3个结点的前一结点的标号都是A。结点E和F与结点A不相邻，所以D(E) = D(F) = ∞。在与结点A相邻的3个结点中，只有边AD的费用最低，即D(D) = 1，所以选择边AD为当前的最短路径，将D结点纳入集合N中。在步骤1，v = D，当前结点D的相邻结点有B、C、E。这3个结点到结点A的总费用分别为3、4、2，所以选择费用低的结点E为下一结点，并将结点E纳入集合N中。同时注意到，从A结点直接到B结点的费用为2，比经过D结点再到B结点的费用低，所以到B结点的最低费用已经求得。但是由于每一步骤只能将一个求得的结点放入集合N，这里选择先将结点E纳入集合N。在步骤2，v = E，当前结点E的相邻结点有C和F，从源结点A到这两个结点的费用分别为3和4。但是与结点A到结点B的费用2相比还不是最低的，所以将结点B纳入集合N。在步骤3，比较到C、F结点的费用，选择将C纳入集合N。最后将结点F纳入集合N。此时，集合N中包含了全部结点，从中得到从源结点A到达所有其他结点的最低费用路径（如图2中的粗实线所示）。
在表中可见，若选择结点F为目的结点，则最短路径的前一结点为结点E，总费用为4；而结点E的前一结点为结点D，结点D的前一结点为结点A，其顺序为F-E-D-A。将该顺序倒过来就是最短路径顺序A-D-E-F。
3 求解装备寿命周期最小费用问题
为使问题简化，我们只考虑装备在使用阶段的情况。而费用则仅考虑购置费用和设备的维修费用。设某学校需要在每年的年初时计划更新购置并常年维护使用一批教学设备。从当年开始将该设备的平均购置费用逐年变化情况列于表3，而该设备平均维修费用逐年变化情况列于表4。
图3是将表5反映的情况转换成的网络图。每个结点表示年初，每条边上的数字为周期费用。设A结点为源结点，F结点为目的结点，则上述需要解决的问题就转化成在该网络图中求最短路径的问题。
在这个求解过程中应注意几个问题：1）因为每个结点都不存在“不相邻”结点，所以没有出现∞值；2）这个网络图中的边为有向边，在计算路径费用时要沿着边的指向进行，不可逆向计算；3）计算出的最低费用路径有两条，一条是A-B-F，另一条是A-D-F，两条路径的费用都为3.8。这一结果说明，如果在第1年初购置了该设备，则在第2年初或第4年初更新该设备，使得到第5年末（或第6年初）时总费用最低。但是，如果考虑到一台设备的实际使用寿命应大于1年，同时第5年后还要长期使用这种设备，就应选择路径A-D-F，即在第4年初更新设备较为合理。
参考文献
[1]陈晓川,方明伦.制造业中产品全生命周期成本的研究概况综述[J].机械工程学报:中文版,2002,38(11):17-25
[2]Kurose J,Ross K.Computer Networking：A Top-Down Approach Featuring the Internet[M].3rd Edition.2004,7
关键词 全寿命周期费用；最短路径；Dijkstra算法
中图分类号 G48 文献标识码 A 文章编号 1671-489X（2008）12-0001-03
在教育装备的研究领域里，人们已经熟知了装备的全寿命周期费用（LCC，Life Cycle Cost）管理理论。全寿命周期一般是指设备的设计阶段、生产阶段、使用阶段和退役阶段，其费用涉及公司成本、用户成本和社会成本[1]。作为教育装备使用与管理者，更关心的是设备在使用阶段和退役阶段的费用问题；并希望找到一个方法，能够在保证设备性能的基础上产生最低费用。网络技术中的最短路径法可以解决这一问题。
1 网络技术与最短路径
对研究对象（事物）特征的描述，可以通过对事物的状态以及与其他事物之间的关系来表示。用结点表示事物的状态，而用结点间的连线（称为“边”）表示事物之间的关系就形成了一个网络（图1）。如果用结点（A、B、…F）代表装备的寿命周期时间分界点，而在边上标注出费用情况，就可以用网络技术来解决装备的寿命周期最小费用问题。
在步骤0时，v=A，结点A的相邻结点有B、C、D。这3个结点与结点A之间形成边的费用分别为2、5、1；而且3个结点的前一结点的标号都是A。结点E和F与结点A不相邻，所以D(E) = D(F) = ∞。在与结点A相邻的3个结点中，只有边AD的费用最低，即D(D) = 1，所以选择边AD为当前的最短路径，将D结点纳入集合N中。在步骤1，v = D，当前结点D的相邻结点有B、C、E。这3个结点到结点A的总费用分别为3、4、2，所以选择费用低的结点E为下一结点，并将结点E纳入集合N中。同时注意到，从A结点直接到B结点的费用为2，比经过D结点再到B结点的费用低，所以到B结点的最低费用已经求得。但是由于每一步骤只能将一个求得的结点放入集合N，这里选择先将结点E纳入集合N。在步骤2，v = E，当前结点E的相邻结点有C和F，从源结点A到这两个结点的费用分别为3和4。但是与结点A到结点B的费用2相比还不是最低的，所以将结点B纳入集合N。在步骤3，比较到C、F结点的费用，选择将C纳入集合N。最后将结点F纳入集合N。此时，集合N中包含了全部结点，从中得到从源结点A到达所有其他结点的最低费用路径（如图2中的粗实线所示）。
在表中可见，若选择结点F为目的结点，则最短路径的前一结点为结点E，总费用为4；而结点E的前一结点为结点D，结点D的前一结点为结点A，其顺序为F-E-D-A。将该顺序倒过来就是最短路径顺序A-D-E-F。
3 求解装备寿命周期最小费用问题
为使问题简化，我们只考虑装备在使用阶段的情况。而费用则仅考虑购置费用和设备的维修费用。设某学校需要在每年的年初时计划更新购置并常年维护使用一批教学设备。从当年开始将该设备的平均购置费用逐年变化情况列于表3，而该设备平均维修费用逐年变化情况列于表4。
图3是将表5反映的情况转换成的网络图。每个结点表示年初，每条边上的数字为周期费用。设A结点为源结点，F结点为目的结点，则上述需要解决的问题就转化成在该网络图中求最短路径的问题。
在这个求解过程中应注意几个问题：1）因为每个结点都不存在“不相邻”结点，所以没有出现∞值；2）这个网络图中的边为有向边，在计算路径费用时要沿着边的指向进行，不可逆向计算；3）计算出的最低费用路径有两条，一条是A-B-F，另一条是A-D-F，两条路径的费用都为3.8。这一结果说明，如果在第1年初购置了该设备，则在第2年初或第4年初更新该设备，使得到第5年末（或第6年初）时总费用最低。但是，如果考虑到一台设备的实际使用寿命应大于1年，同时第5年后还要长期使用这种设备，就应选择路径A-D-F，即在第4年初更新设备较为合理。
参考文献
[1]陈晓川,方明伦.制造业中产品全生命周期成本的研究概况综述[J].机械工程学报:中文版,2002,38(11):17-25
[2]Kurose J,Ross K.Computer Networking：A Top-Down Approach Featuring the Internet[M].3rd Edition.2004,7