- 1、本文档共26页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
关键路径(CPM)
AOE网(Activity On Edge network),即边表示活动的网络,与AOV网相对应的是。它通常表示一个工程的计划或进度。
AOE网是一个有向带权图,图1中的:
边:表示活动(子工程),
边上的权:表示该活动的持续时间,即完成该活动所需要的时间;
顶点:表示事件,每个事件是活动之间的转接点,即表示它的所有入边活动到此完成,所有出边活动从此开始。
其中有两个特殊的顶点(事件),一个称做源点,它表示整个工程的开始,亦即最早活动的起点,显然它只有出边,没有入边;另一个称做汇点,它表示整个工程的结束,亦即最后活动的终点,显然它只有入边,没有出边。除这两个顶点外,其余顶点都既有人边,也有出边,是入边活动和出边活动的转接点。
在一个AOE网中,若包含有n个事件,通常令源点为第0个事件,汇点为第n-1个事件,其余事件的编号(即顶点序号)分别为1~n-2。
一个AOE网如图,该网中包含有10项活动和7个事件。
例如,边1,2表示活动al,持续时间(即权值)为3,假定以天为单位,即a1需要3天完成,它以V1事件为起点,以V2事件为终点;边2,5和2,4分别表示活动a4和a5,它们的持续时间分别为4天和2天,它们均以V2事件为起点,以V5和V4事件为终点。该网中的源点和汇点分别为第1个事件V1和最后一个事件V7,它们分别表示整个工程的开始和结束。
对于一个AOE网,待研究的问题是:
(1)整个工程至少需要多长时间完成?
(2)哪些活动是影响工程进度的关键?
图1 AOE网
1.事件的最早发生时间与活动的最早开始时间的关系
在AOE网中,一个顶点事件的发生或出现必须在它的所有入边活动(或称前驱活动)都完成之后,即只要有一个入边活动没有完成,该事件就不可能发生。所以:
一个事件的最早发生时间是它的所有入边活动,或者说最后一个入边活动刚完成的时间。
一个活动的开始必须在它的起点事件发生之后,也就是说,一个顶点事件没有发生时,它的所有出边活动(或称后继活动)都不可能开始,所以:
一个活动的最早开始时间是它的起点事件的最早发生时间。若用Ve[j]表示顶点Vj事件的最早发生时间,用e[i]表示Vj一条出边活动ai的最早开始时间,则有e[i]=Ve[j]。
2.求事件的最早发生时间
对于源点事件来说,因为它没有入边,所以随时都可以发生,整个工程的开始时间就是它的发生时间,亦即最早发生时间,通常把此时间定义为0,从此开始推出其他事件的最早发生时间。
例如,如图所示的AOE网中,
V5事件的发生必须在a4和a8活动都完成之后,而a4和a8活动的开始又必须分别在V2和V4事件的发生之后,V2和V4事件的发生又必须分别在a1和a2活动的完成之后,因a1和a2的活动都起于源点,其最早开始时间均为0,所以a1和a2的完成时间分别为3和6,这也分别是V2和V4的最早发生时间,以及a4和a8的最早开始时间,故a4和a8的完成时间分别为7和7,由此可知V5事件的最早发生时间为7,即所有入边活动中最后一个完成的时间。
从以上分析可知,一个事件的发生有待于它的所有入边活动的完成,而每个入边活动的开始和完成又有待于前驱事件的发生,而每个前驱事件的发生又有待于它们的所有入边活动的完成,……总之,一个事件发生在从源点到该顶点的所有路径上的活动都完成之后,显然,其最早发生时间应等于从源点到该顶点的所有路径上的最长路径长度。这里所说的路径长度是指带权路径长度,即等于路径上所有活动的持续时间之和。
如从源点V1到顶点V4共有三条路径,长度分别为5、6和3,所以V4的最早发生时间为6。
从源点V1到汇点V7有多条路径,通过分析可知,其最长路径长度为10,所以汇点V7的最早发生时间为10。汇点事件的发生,表明整个工程中的所有活动都已完成,所以完成图所对应的工程至少需要10天。
如何从源点V1的最早发生时间1出发,求出其余各事件的最早发生时间。
求一个事件Vk的最早发生时间(即从源点V1~Vk的最长路径长度)的常用方法是:
由它的每个前驱事件Vi的最早发生时间(即从源点V1~Vi的最长路径长度)分别加上相应入边i,k上的权,其值最大者就是Vk的最早发生时间。由此可知,必须按照拓扑序列中的顶点次序(即拓扑有序)求出各个事件的最早发生时间,这样才能保证在求一个事件的最早发生时间时,它的所有前驱事件的最早发生时间都已求出。
设Ve[k]表示vk事件的最早发生时间,Ve[j]表示vk的一个前
您可能关注的文档
- 毕业设计室内灯具考察解剖.doc
- 毕业设计正文解剖.doc
- 避难硐室功能测试解剖.doc
- 新颖等离子体纳米颗粒的化学合成简析.doc
- 辩论整合解剖.doc
- 标幽赋白话解解剖.doc
- 某钢结构厂房标解答.doc
- 某计算所科研综合楼主体施工准备工程施工组织设计解答.doc
- 某框架结构办公楼楼梯设计解答.doc
- 宾馆供配电一层宴会大厅照明设计解剖.doc
- 人教版语文八年级上册19 蝉 练习-课件.ppt
- 幼儿园29.妈妈肚子里的我 课件.ppt
- 引导式教育-医学课件.ppt
- 部编版历史七年级上册第20课 魏晋南北朝的科技与文化-1-课件.ppt
- 部编版二年级语文《玲玲的画》课件1.ppt
- 幼儿园12施工现场请绕行 课件.ppt
- 人教版PEP英语五年级上册Part B Read and write&Let's check& Let's wrap it up &Part C Story time[3]-课件.ppt
- 北师大版数学三年级上册第2单元 观察物体 第2课时 看一看(二)-课件.ppt
- 部编版小学道德与法治1 我们班四岁了-课件.ppt
- 创意班 奇思妙想-水果-画室资料.ppt
文档评论(0)