关键路径

6.5关键路径问题一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机,都要包括许多工序.这些工序相互约束,只有在某些工序完成之后,一个工序才能开始.即它们之间存在完成的先后次序关系,一般认为这些关系是预知的,而且也能够预计完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进度的要害工序是哪几个？PT(Potentialtaskgraph)图在PT(Potentialtaskgraph)图中,用结点表示工序,如果工序i完成之后工序j才能启动,则图中有一条有向边(i,j),其长度wi表示工序i所需的时间.这种图必定不存在有向回路,否则某些工序将在自身完成之后才能开始,这显然不符合实际情况.在PT图中增加两个虚拟结点v0和vn,使所有仅为始点的结点都直接与v0联结,v0为新增边的始点,这些新增边的权都设为0;使所有仅为终点的结点都直接与vn联结,vn为新增边的终点.这样得到的图G仍然不存在有向回路.例一项工程由13道工序组成,所需时间(单位：天)及先行工序如下表所示(P172).工序序号ABCDEFGHI所需时间263243842先行工序—AABC,DDDDG,H工序序号JKLM所需时间3856先行工序GH,EJK试问这项工程至少需要多少天才能完成?那些工程不能延误?那些工程可以延误?最多可延误多少天?先作出该工程的PT图.由于除了工序A外，均有先行工序,因此不必虚设虚拟结点v0.AB22C6D3E2F2G2H2K4N3I8J8442L3M856在PT图中,容易看出各工序先后完成的顺序及时间.虚拟结点AB22C6D3E2F2G2H2K4N3I8J8442L3M856这项工程至少需要多少天才能完成?就是要求A到N的最长路,此路径称为关键路径.那些工程不能延误?那些工程可以延误?最多可延误多少天?关键路径上的那些工程不能延误.关键路径(最长路径)算法定理若有向图G中不存在有向回路,则可以将G的结点重新编号为u1,u2,…,un,使得对任意的边uiuj∈E(G),都有i＜j.各工序最早启动时间算法步骤：①根据定理对结点重新编号为u1,u2,…,un.②赋初值(u1)=0.③依次更新(uj),j=2,3,…,n.(uj)=max{(ui)+(ui,uj)|uiuj∈E(G)}.④结束.其中(uj)表示工序uj最早启动时间,而(un)即(vn)是整个工程完工所需的最短时间.AB22C6D3E2F2G2H2K4N3I8J8442L3M856此例不必重新编号，只要按字母顺序即可.(A)=0,(B)=(C)=2,(D)=8,(E)=max{2+3,8+2}=10,(F)=(G)=(H)=(D)+2=10,(I)=max{(G)+8,(H)+4}=18,(J)=(G)+8=18,(K)=max{(E)+4,(H)+4}=14,(L)=(J)+3=21,(M)=(K)+8=22,(N)=max{(F)+3,(I)+2,(L)+5,(M)+6}=28.关键路径?通过以上计算表明：这项工程至少需要28天才能完成.关键路径(最长路径):A→B→D→E→K→M→NA→B→D→H→K→M→N工序A,B,D,E,H,K,M不能延误,否则将影响工程的完成.但是对于不在关键路径上的工序,是否允许延误？如果允许,最多能够延误多长时间呢？各工序允许延误时间t(uj)等于各工序最晚启动时间(uj)减去各工序最早启动时间(uj).即t(uj)=(uj)-(uj).最晚启动时间算法步骤(已知结点重新编号)：①赋初值(un)=(un).②更新(uj),j=n-1,n-2,…,1.(uj)=min{(ui)-(ui,uj)|uiuj∈E(G)}.③结束.顺便提一句,根据工序uj允许延误时间t(uj)是否为0,可判断该工序是否在关键路径上.AB22C6D3E2F2G2H2K4N3I8J8442L3M856(N)=28,(M)=28-6=22,(L)=28-5=23,(K)=(M)-8=14,(J)=(L)-3=20,(I)=28-2=26,(H)=min{(K)-4,(I)-4}=10,(G)=min{(J)-8,(I)-8}=12,(F)=28-3=25,(E)=(K)-4=10,(D)=min{(E)-2,(F)-2,(G)-2,(H)-2}=8,(C)=(E)-3=7,(B)=(D)-6=2,(A)=0.各工序允许延误时间如下：t(A)=t(B)=t(D)=t(E)=t(H)=t(K)=t(M)=0,t(C)=5,t(F)=15,t(G)=2,t(I)=8,t(J)=2,t(L)=2.PERT图在PERT(Programmeevaluationandreviewtechnique)图中,采用有向边表示工序,其权值表示该工序所需时间.如果工序ei完成后ej才能开始,则令vk是ei的终点,ej的始点.根据这种约定,前例的PERT图如下：ABCEFDDGGHHIJKLM对于PERT图,一些算法与PT图类似.PT图要比PERT图好一些.PT图的结点数基本上是固定的,这是最重要的一点,容易编程计算.另外PT图比PERT图更加灵活,它能适应一些额外的约束.例如下图中(i)/2vivj⑴(i)+tvivj⑵bjv0vj⑶⑴表示工序vi完成一半之后vj就可以开始.⑵表示工序vi完成后经过t时刻vj才开始.⑶表示在时间bj之后工序vj才能开始,其中v0表示虚拟结点.PERT图(计划评审技术图)设有向图G=V,E,vVv的后继元集+(v)={x|xVv,xE}v的先驱元集-(v)={x|xVx,vE}PERT图:满足下述条件的n阶有向带权图D=V,E,w,(1)D是简单图,(2)D中无回路,(3)有一个入度为0的顶点,称作始点;有一个出度为0的顶点,称作终点.通常边的权表示时间,始点记作v1,终点记作vn关键路径关键路径:PETR图中从始点到终点的最长路径vi的最早完成时间TE(vi):从始点v1沿最长路径到vi所需的时间TE(v1)=0TE(vi)=max{TE(vj)+wji|vj-(vi)},i=2,3,,nvi的最晚完成时间TL(vi):在保证终点vn的最早完成时间不增加的条件下,从始点v1最迟到达vi的时间TL(vn)=TE(vn)TL(vi)=min{TL(vj)-wij|vj+(vi)},i=n-1,n-2,,1关键路径(续)vi的缓冲时间TS(vi)=TL(vi)-TE(vi),i=1,2,,nvi在关键路径上TS(vi)=0例2求PERT图中各顶点的最早完成时间,最晚完成时间,缓冲时间及关键路径.解最早完成时间TE(v1)=0TE(v2)=max{0+1}=1TE(v3)=max{0+2,1+0}=2TE(v4)=max{0+3,2+2}=4TE(v5)=max{1+3,4+4}=8TE(v6)=max{2+4,8+1}=9TE(v7)=max{1+4,2+4}=6TE(v8)=max{9+1,6+6}=12例2(续)缓冲时间TS(v1)=0-0=0TS(v2)=2-1=1TS(v3)=2-2=0TS(v4)=6-4=2TS(v5=10-8=2TS(v6)=11-9=2TS(v7)=6-6=0TS(v8)=12-12=0关键路径:v1v3v7v8例2(续)最晚完成时间TL(v8)=12TL(v7)=min{12-6}=6TL(v6)=min{12-1}=11TL(v5)=min{11-1}=10TL(v4)=min{10-4}=6TL(v3)=min{6-2,11-4,6-4}=2TL(v2)=min{2-0,10-3,6-4}=2TL(v1)=min{2-1,2-2,6-3}=06.6网络最优化模型转化为线性规划模型本节将某些网络最优化问题转化为线性规划问题来求解,但这并不意味着线性规划的方法是解决这些网络最优化问题的最有效算法.事实上,这些网络最优化问题均各自存在更有效的算法.我们之所以将它们转化为线性规划问题,主要基于以下两个方面的考虑：⑴我们有现成的功能很强的软件,它可以方便地求解线性规划问题.⑵将某些网络最优化模型,转化为线性规划模型,本身就是一种非常好的建模训练,具体的转化技巧具有重要的启发意义.6.7系统监控模型定义1设图G=(V,E),KV如果图G的每条边都至少有一个顶点在K中,则称K是G的一个点覆盖.若G的一个点覆盖中任意去掉一个点后不再是点覆盖,则称此点覆盖是G的一个极小点覆盖.顶点数最少的点覆盖,称为G的最小点覆盖.例如,右图中,{v0,v2,v3,v5,v6}等都是极小点覆盖.{v0,v1,v3,v5},{v0,v2,v4,v6}都是最小点覆盖.系统监控问题之一假设v1,v2,…,v7是7个哨所,监视着11条路段(如下图所示),为节省人力,问至少需要在几个哨所派人站岗,就可以监视全部路段?这就是要求最小点覆盖问题.v2v1v3v7v6v5v4{v1,v3,v5,v6}和{v1,v3,v5,v7}都是最小点覆盖,所以至少需要在4个哨所派人站岗来监视全部路段.到目前为止,还没有找到求最小点覆盖的有效算法,即多项式时间算法(算法步数不超过nc,n为G的顶点数,c为常数).一种启发式近似算法见P169.最大独立点集定义2设图G=(V,E),IV如果I中任意两个顶点在G中都不相邻,则称I是G的一个独立点集.若G的一个独立点集中,任意添加一个点后不再是独立点集,则称此独立点集是G的一个极大独立点集.顶点数最多的独立点集,称为G的最大独立点集.例如,右图中,{v1,v4}等都是极大独立点集.{v1,v3,v5},{v2,v2,v6}是最大独立点集.最小控制集定义3设图G=(V,E),DV如果v∈V,要么v∈D,要么v与D的某个点相邻,则称D是G的一个控制集.若G的一个控制集中任意去掉一个点后不再是控制集,则称此控制集是G的一个极小控制集.顶点数最少的控制集,称为G的最小控制集.例如,右图中,{v1,v3,v5}是极小控制集,{v0}是最小控制集.系统监控问题之二假设下图代表一指挥系统,顶点v1,v2,…,v7表示被指挥的单位,边表示可以直接下达命令的通信线路.欲在某些单位建立指挥站,以便可以通过指挥站直接给各单位下达命令,问至少需要建立几个指挥站?这就是要求最小控制集问题.v2v1v3v7v6v5v4{v1,v3},{v3,v5}等都是最小控制集,所以至少需要在2个单位建立指挥站.到目前为止,还没有找到求最小控制集的有效算法.一种启发式近似算法见P169.最小点覆盖、最大独立点集和最小控制集的关系定理1设无向图G=(V,E)中无孤立点(不与任何边关联的点),若D是G中极大独立点集,则D是G中极小控制集.定理2设无向图G=(V,E)中无孤立点,KV,则K是G的点覆盖当且仅当Kc=V\K是G的独立点集.推论设无向图G=(V,E)中无孤立点,KV,则K是G的最小(极小)点覆盖当且仅当Kc=V\K是G的最大(极大)独立点集.6.8着色模型已知图G=(V,E),对图G的所有顶点进行着色时,要求相邻的两顶点的颜色不一样,问至少需要几种颜色?这就是所谓的顶点着色问题.若对图G的所有边进行着色时,要求相邻的两条边的颜色不一样,问至少需要几种颜色?这就是所谓的边着色问题.这些问题的提出是有实际背景的.值得注意的是,着色模型中的图是无向图.对于顶点着色问题,若是有限图,也可按第一节所述的方法转化为有限简单图.而边着色问题可以转化为顶点着色问题.对偶图将原图中的点化为边,边化为点即可.这样得到的图称为原图的对偶图.下面图中,右图是左图的对偶图.v2v1v3v7v6v5v4e3e2e1e4e5e6e7e8e9e10e1e2e4e3e5e7e8e10e9e6不过还原比较困难,右图中黄色的边对应左图中