资源描述：
《马尔可夫骨架过程在PERT网络中的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、孔祥星合作者：张玄、侯振挺中南大学2012年5月27日马尔可夫骨架过程在PERT网络中的应用2012年“随机图与复杂网络”学术研讨会统筹方法想泡壶茶喝。当时的情况是：没有开水，开水壶要洗，茶壶茶杯要洗，茶叶没有拿，怎么办？bstcd12345活动1（洗茶壶）需要1分钟，活动2（烧开水）需要15分钟，活动3（洗茶壶）需要1分钟，活动4（洗茶杯）需要1分钟，活动5（拿茶叶）需要2分钟。在华罗庚先生所提的统筹方法中，项目中每个活动的持续时间是固定的，只要安排好工序就可以求出项目的完工时间。后来有人假设项目中每个活动的持续时间是相互独立服从负指数分布的随机变量，
2、可用马氏链来研究项目的完工时间分布。我们进一步把每个活动的持续时间推广为相互独立服从一般分布的随机变量，把每个活动已实施的时间作为补充变量，从而构建一个带有吸收态的马尔可夫骨架过程，通过其向后方程得到了PERT网络完工时间分布的解析表达式。PERT网络用表示一个具有一个源点s和一个汇点t的有向非循环网络，其中，表示节点（事件）集，表示弧（活动）的集合，对于任意个一个活动，其持续时间是服从一般分布的随机变量。令表示弧的起点，表示弧的终点，一条有向路径是一个弧序列且弧序列满足如下的条件，且。PERT网络定义1令和分别表示以节点为起点和终点的弧的全体，分别可以
3、表示如下：定义2设，，则割集定义为如果一个割集是空集，则称为一致有向割集。PERT网络定义3在项目的实施过程中，在时刻每个活动都会处于活动、休眠的或空闲的三种状态之一：（1）活动：如果某个活动在时刻t正在施工则称该活动处于活动的状态。（2）休眠：如果某个活动已经完工，但是中的活动没有都完工，此时中的活动不能开始施工，称处于休眠的状态。（3）空闲：如果某个活动既不是活动的也不是不活动的，则称为空闲的。PERT网络设是PERT网络的一条路径，路径的完工时间很明显不一定等于各个活动的完工时间之和。为了计算路径的完工时间分布，可采用如下的方法，令从而包含所有活动
4、的子图的完工时间等于路径的完工时间。PERT网络如图（a）所示，设路径，则，从而。则子图如图（b）所示，路径的完工时间与子图的完工时间相等。PERT网络在图(b)中所有的UDC为(1,2),(2,3),(1,4),(3,4),(5)。所有UDC的容许二划分如下表所示，其中，*表示该活动处于休眠状态。表1如上令和表示所有UDC中活动的和休眠的活动。对，令表示活动已实施的时间，令表示活动的持续时间分布。则剩余马氏骨架过程时间的分布可表示为以活动的已实施的时间作为补充变量则表1的状态变为表2马氏骨架过程令则是一个状态空间为的马尔科夫骨架过程。令表示的不连续时间
5、点（在时刻有一个活动完工），则是马氏骨架过程的骨架时序列。为了表述的方便，把表2中10个状态分别用1,2，……，10来表示，马尔科夫骨架过程在完成状态1后转移到状态2或4或6，完成某项活动马氏骨架过程后继续向后转移，最终到达状态10，从而整个项目完成。马尔科夫骨架过程的状态转移示意图如下所示：马氏骨架过程令表示PERT网络的完工时间，则可以通过马尔科夫骨架过程的向后方程计算项目工期的分布。令表示从状态9转移到状态10的完工时间分布，其中活动5已实施的时间长度为，则马氏骨架过程令表示从状态8转移到状态10的完工时间分布，其中活动3已实施的时间长度为，则马氏
6、骨架过程令表示从状态1转移到状态10的完工时间分布，其中活动1和2已实施的时间长度分别为和则马氏骨架过程路径的完工时间等于子图的完工时间，即马尔科夫骨架过程从状态1转移到状态10的时间。马氏骨架过程为了说明本章所得解析结果的有效性，给出一个具体的例子，设活动5的持续时间服从参数的-分布，则其密度函数和剩余时间分布为设活动1,2,3,4,6的持续时间分布分别服从参数为1,2,3,4,6的负指数分布。例子路径的完工时间等于子图的完工时间，即马氏骨架过程从初始状态1到达吸收态10的时间。完工时间的分布、期望与方差如下：例子[1]KulkarniV.,Adlak
7、haV.MarkovandMarkov-RegenerativePERTnetworks.OperationsResearch,1986,34:769~781[2]AzaronA.,KatagiriH.,SakawaM.,etal.Multi-objectiveresourceallocationprobleminPERTnetworks.EuropeanJournalofOperationalResearch,2006,172:838~854[3]AzaronA.,Tavakkoli-MoghaddamR..Amulti-objectiveresour
8、ceallocationproblemindynamicPERTnetworks
