数据模型决策：问题求解

对于关键路径问题,本节将结合一个实例来探讨其求解方法。

例19.9 某购物中心的所有者正在计划对现有的32个商业购物中心进行现代化改革并扩张规模,该项目预计能为7～10个新的商业购物中心提供空间。通过私人投资,资金已安排到位,所有者要做的只是计划、安排和完成这个扩张项目。活动安排如表19.2所示,该项目中最关键的步骤是哪几个?

表19.2　活动安排

解 根据上述内容,可画出该项目的网络计划图,如图19.19所示。

为了简化计划评审法和关键路径法的估算,我们对项目网络图做了一些改动,如图19.20所示。注意,在每个结点左上方单元格中都给出了该活动的字母代码,在左下方单元格中则列出了完成活动需要的时间。

图19.19　项目计划图

图19.20　关键路径法简化图

首先找出网络中具有最早开始时间和最晚开始时间的活动,设ES表示活动的最早开始时间,EF表示活动的最早完成时间,t表示活动时间。对于任何活动,最早完成时间为EF=ES+t。

因为活动A 可与项目一同开始,所以设活动A 的最早开始时间为0,而完成活动A 需要5周时间,所以活动A 的最早完成时间为EF=ES+t=0+5=5。同时可以看出,D 活动紧随在A 活动之后,因此D 活动的最早开始时间ES=5,D 活动的最早完成时间EF=ES+t=5+3=8。

将每项活动的最早开始时间和最早完成时间写到结点处的右上方单元格中。以活动A,C,B,H 为例,其中B 和C 都是H 的紧前活动,因此,活动H 的最早开始时间为活动B 和活动C 的最早完成时间中较晚的一个。于是得到图19.21,活动H 的最早开始时间为6和9中较晚的那个,即为9。

继续在项目网络图中向前推进线路,为图中所有的活动建立最早开始时间和最早完成时间,图19.22显示了整个项目中所有活动的最早开始时间和最早完成时间。

现在通过在项目网络图中向后逆推(也叫反推法)找出关键路径。由于项目的总完成时间为26周,因此应从具有最晚完成时间(26周)的活动I 开始向后逆推。一旦知道了某项活动的最晚完成时间,就可以通过下述公式计算其最晚开始时间。设LS表示每项活动的最晚开始时间,LF表示每项活动的最晚完成时间,得LS=LF-t。

图19.21　关键路径法演示简化图

图19.22　最早开始时间和最早完成时间

根据分析可以得出,一项活动的最晚完成时间等于其所有紧后活动最晚开始时间中的最小值,由此得到该项目每个活动的最晚开始时间和最晚完成时间,如图19.23所示。(www.xing528.com)

图19.23　最晚开始时间和最晚完成时间

在向前推进和向后逆推的工作之后,就可以确定每项活动相关松弛的量。松弛是指延误某项活动的活动时间而又不会影响项目整体完工时间的时间长度。每项活动松弛的量可用如下公式计算:

松弛=LS-ES=LF-EF。

例如,活动C 的松弛为LS-ES=8-5=3周,因此,活动C 最多可延误3周完成,而又不会影响整个项目的计划完成时间。就这个意义来说,活动C 对于项目能否按期完成并不重要。下面考虑活动E,根据图19.23提供的信息,可以很容易得到活动E 的松弛为LS-ES=5-5=0,因此活动E 没有松弛。为了不增加整个项目的完工时间,活动E 是不能被延误的。换句话说,按计划完成活动E 对于按预定计划完成整个项目是重要的。一般来说,重要活动就是指没有松弛的活动。

我们可以为所有活动的开始时间和完成时间制定具体的安排,将有关活动安排的所有信息以表格的形式列出,如表19.3所示。从松弛栏可以看出,活动A,E,F,G,I没有松弛,因此这些活动是项目中的重要活动,而由这些结点构成的路径A→E→F→G→I 就是该购物中心项目网络的关键路径。

表19.3　关键路径法

由此可以看出,活动A,E,F,G,I 决定整个项目工期,如果这些活动被延误,则整个项目的工期必然被延误,这些活动是决策者在安排计划时需要重点考虑的活动。

图论有着非常丰富的内容,详细内容可参考相关文献。