专题五-图与网络分析.ppt

1专题五专题五 图论与网络计划模型图论与网络计划模型最小生成树模型最小生成树模型最短路最短路模型模型最大流最大流模型模型最小费用流最小费用流模型模型网络计划与优化网络计划与优化模型模型数据、模型与决策数据、模型与决策2第一节第一节 图与网络基础概念图与网络基础概念图子图和生成子图网络图链、路、圈和回路连通图简单图数据、模型与决策数据、模型与决策3一、图一、图n 由有限个代表事物的点和表示事物间由有限个代表事物的点和表示事物间联系线联系线构成，这些点构成，这些点称为称为顶点顶点。n为了反映为了反映7家企业的业务来往联系，用家企业的业务来往联系，用7个点表示个点表示7家企业，家企业，若某两家企业之间存在业务来往，则两点间联线。若某两家企业之间存在业务来往，则两点间联线。n数学表达：顶点用数学表达：顶点用V=v1,v2,vn表示；顶点间的连线称表示；顶点间的连线称为边，用为边，用E=e1,e2,表示，则图的表示方法为：表示，则图的表示方法为：G=V,E数据、模型与决策数据、模型与决策4无向图：对象之间具有对称性，（甲对乙，乙对甲）。无向图：对象之间具有对称性，（甲对乙，乙对甲）。有向图：不具有对称性的事物。有向图：不具有对称性的事物。A A认识认识B B，B B一定认识一定认识A?AA?A到到B B的距离，一定等于的距离，一定等于B B到到A A的距的距离？离？为了反映球队之间比赛胜负关系，则球队之间单纯用一为了反映球队之间比赛胜负关系，则球队之间单纯用一条联线就难以表达。条联线就难以表达。对策：对策：带箭头的线，有向线有向图。带箭头的线，有向线有向图。数据、模型与决策数据、模型与决策5边：两点间不带箭头联线称为边，若两点为边：两点间不带箭头联线称为边，若两点为vi,vj,则边记为：则边记为：vi,vj；弧：两点间带箭头联线称弧弧：两点间带箭头联线称弧,若有若有vi指向指向vj的弧，的弧，则弧记为：（则弧记为：（vi,vj）。无向图定义：由点和边组成，表示无向图定义：由点和边组成，表示G=V,E；有向图定义：由点和弧组成，表示有向图定义：由点和弧组成，表示D=V,A。数据、模型与决策数据、模型与决策6二、子图与生成子图二、子图与生成子图子图：图子图：图G1中的点是图中的点是图G2中点的一部中点的一部分，图分，图G1中的边是图中的边是图G2中的一部分。中的一部分。生成图：图生成图：图G1的的点点与图与图G2相同，边是相同，边是其中的一部分。其中的一部分。数据、模型与决策数据、模型与决策7三、网络图三、网络图各边赋予一定的物理量，例如距离，则叫各边赋予一定的物理量，例如距离，则叫做网络图。做网络图。所赋予的物理量叫做权。所赋予的物理量叫做权。权可以是：距离、时间、成本、容量等。权可以是：距离、时间、成本、容量等。e11表示上海到北京的铁路长度。或，旅客从上海到北京的车票费用数据、模型与决策数据、模型与决策8四、链、路、圈、回路四、链、路、圈、回路链：点和边的交错序列（链：点和边的交错序列（vi1,ei1,vi2,eik-1,vik）,若有若有eit=vit,vit+1。初等链：顶点和边相互交替出现的初等链：顶点和边相互交替出现的点不重复序列点不重复序列。路：在有向图中，链中每条边的方向和链的走向一致的链。路：在有向图中，链中每条边的方向和链的走向一致的链。圈：起点和终点相同的链叫做圈。圈：起点和终点相同的链叫做圈。回路：起点和终点相同的路叫做回路。回路：起点和终点相同的路叫做回路。v4v1v2v5v3e1e2e3e4e5e6任意举出一条链，初等链，路，圈和回路。数据、模型与决策数据、模型与决策9五、连通图和简单图五、连通图和简单图连通图：连通图：在图中，任意两点之间都有一条链相连，在图中，任意两点之间都有一条链相连，叫做连通图。否则是非连通图。非连通图可以由叫做连通图。否则是非连通图。非连通图可以由几个连通图构成。几个连通图构成。环：环：某边的两个顶点相同；某边的两个顶点相同；多重边：多重边：两个顶点之间多于一条边。两个顶点之间多于一条边。简单图：简单图：没有环和多重边的图是简单图。没有环和多重边的图是简单图。数据、模型与决策数据、模型与决策10第二节第二节 树及最小生成树算法树及最小生成树算法什么是树？什么是树？构造生成树的方法构造生成树的方法最小生成树最小生成树寻找最小生成树的方法寻找最小生成树的方法数据、模型与决策数据、模型与决策11树：不含圈的连通图树：不含圈的连通图五个城市连通电话线问题n什么是连通图：任意两点之间都有一条链相连。n什么是圈：起点和终点相同的链叫做圈。已知有五个城市，要在它们之间架设电话线，要求任何两个城市都可以互相通话（允许通过其它城市），并且电话线的根数最少。一、树的基本概念一、树的基本概念数据、模型与决策数据、模型与决策12树的基本性质树的基本性质任意两点之间有且只有一条链；任意两点之间有且只有一条链；图是树的充要条件：任意两个顶点之间只有一图是树的充要条件：任意两个顶点之间只有一条链；条链；若树有若树有p个顶点，则共有个顶点，则共有q=p-1条边；条边；图是树的充要条件：连通图，边数图是树的充要条件：连通图，边数=顶点数顶点数1。五个城市连通电话线问题数据、模型与决策数据、模型与决策13生成树的概念生成树的概念生成图：图生成图：图G1的点与图的点与图G2相同，边是其中相同，边是其中的一部分。的一部分。如果如果G1是树，则称为生成树。是树，则称为生成树。五个城市连通电话线问题数据、模型与决策数据、模型与决策14二、构造生成树的方法二、构造生成树的方法法1：破圈法：无圈的连通图，图中无圈。起点和终点相同的链叫做圈。起点和终点相同的链叫做圈。从图中取圈，从图中取圈，从圈中去掉一从圈中去掉一边，重复直到边，重复直到无圈。无圈。数据、模型与决策数据、模型与决策15避圈法：从图中某一点开始生长边，从图中某一点开始生长边，选取与入树边不构成圈的边。选取与入树边不构成圈的边。数据、模型与决策数据、模型与决策16三、最小生成树三、最小生成树生成树不唯一架设电话线铺设水管连接边长度最短？数据、模型与决策数据、模型与决策17设有一个连通图，每一边都有一个非负权，设有一个连通图，每一边都有一个非负权，w(e)=wij.树的权：树中所有边的权之和。树的权：树中所有边的权之和。最小生成树：图中，权最小的生成树。最小生成树：图中，权最小的生成树。数据、模型与决策数据、模型与决策18将图中求最小生成树的问题归结为整数规将图中求最小生成树的问题归结为整数规划问题，列出数学模型。划问题，列出数学模型。3568a12a13a24a34a36a67a47a45a78a581247数据、模型与决策数据、模型与决策19数据、模型与决策数据、模型与决策20四、寻找最小生成树的方法四、寻找最小生成树的方法（1）避圈法：开始选一条最小权的边，）避圈法：开始选一条最小权的边，以后总从与已选边不构成圈的那些未选以后总从与已选边不构成圈的那些未选边中，选一条权最小的（相同最小权的边中，选一条权最小的（相同最小权的边，任选一条）。边，任选一条）。（2）破圈法：任取一圈，从圈中去掉）破圈法：任取一圈，从圈中去掉一条权最大的边（相同权的边，任去一一条权最大的边（相同权的边，任去一条），在余下图中，重复此步骤，直到条），在余下图中，重复此步骤，直到得到一个不含圈的图，即得最小树。得到一个不含圈的图，即得最小树。数据、模型与决策数据、模型与决策21分别用破圈法和避圈法求图中的最小生成树39263314473926331447数据、模型与决策数据、模型与决策22(3)矩阵求解算法 步骤1：构造一个矩阵，651572344v1v2v3v4v5v6数据、模型与决策数据、模型与决策23T651572344v1v2v3v4v5v6数据、模型与决策数据、模型与决策24步骤步骤2：从矩阵中任一行开始，用：从矩阵中任一行开始，用T表明节点入树，划表明节点入树，划去该节点所在的列。去该节点所在的列。T数据、模型与决策数据、模型与决策25步骤步骤3：在标：在标T的行中选取最小元素，用方框表示，将的行中选取最小元素，用方框表示，将对应的边入树，将新得到节点标对应的边入树，将新得到节点标T，划去所在列。，划去所在列。TT数据、模型与决策数据、模型与决策26步骤步骤4：重复步骤：重复步骤3。TTT数据、模型与决策数据、模型与决策27矩阵计算方法矩阵计算方法TTTT数据、模型与决策数据、模型与决策28矩阵计算方法矩阵计算方法TTTTT数据、模型与决策数据、模型与决策29矩阵计算方法矩阵计算方法TTTTTT数据、模型与决策数据、模型与决策30矩阵计算结果矩阵计算结果数据、模型与决策数据、模型与决策31683572348数据、模型与决策数据、模型与决策32第三节第三节 最短路问题及算法最短路问题及算法什么是最短路问题？什么是最短路问题？求解最短路问题的基本思路求解最短路问题的基本思路Dijstra 算法：标号法算法：标号法数据、模型与决策数据、模型与决策33一、什么是最短路问题？91344372858始点终点v1v2v3v42v5v6v7数据、模型与决策数据、模型与决策34二、求解最短路问题的基本思路 对于在始点到终点的总体最短路径上的任意一点，从始点到该点的最短路在总体最短路径上。动态规划动态规划的思路的思路数据、模型与决策数据、模型与决策35三、Dijkstra算法对每个节点，用两种标号：对每个节点，用两种标号：T和和P，表示从，表示从始点到该节点的距离，始点到该节点的距离，P是最短距离，是最短距离，T是是目前路径的距离。目前路径的距离。通过不断改进通过不断改进T值，当其最小时，将其改为值，当其最小时，将其改为P标号。标号。开始时，令开始时，令始点始点有有P=0，P标号，其它节点标号，其它节点T=M（无穷大）。（无穷大）。数据、模型与决策数据、模型与决策36P(V1)=0,T(V2)=M,第一步：T(V2)=min(T(V2),P(V1)+W12)=0+8=8T(V3)=min(T(V3),P(V1)+W13)=0+6=6 T(V4)=min(T(V4),P(V1)+W14)=0+2=2Min(T(V2),T(V3),T(V4)=2断言：V1到V4的最短距离为2?P(V4)=2数据、模型与决策数据、模型与决策37第二步：T(V3)=min(T(V3),P(V4)+W43)=min(6,2+3)=5T(V6)=min(T(V6),P(V4)+W46)=min(M,2+2)=4T(V2)=min(T(V2),P(V1)+W12)=0+8=8T(V3)=min(T(V3),P(V1)+W13)=0+6=6Min(T(V2),T(V3),T(V6)=4断言：V1到V6的距离最短：4。P(V6)=4数据、模型与决策数据、模型与决策38第一步：假定vi是新产生的P标号点，考查以考查以vi为开始点的所有弧段为开始点的所有弧段vivj。如果vj是P标号点，则对vj点不再进行标号；如果vj是T标号点，则计算第二步：产生新的P标号点，在现有所有的T标号中将值最小的T标号改为P标号。重复上述步骤,直到没有点可标号。数据、模型与决策数据、模型与决策39第三步：第三步：T(V5)=min(T(V5),P(V6)+W65)=min(M,4+3)=7T(V7)=min(T(V7),P(V6)+W67)=min(M,4+9)=13T(V2)=min(T(V2),P(V1)+W12)=0+8=8T(V3)=min(T(V3),P(V4)+W43)=min(6,2+3)=5Min(T(V2),T(V3),T(V5),T(V7)=5断言：断言：V1到到V3的距离最短：的距离最短：5。P(V3)=5数据、模型与决策数据、模型与决策40数据、模型与决策数据、模型与决策41数据、模型与决策数据、模型与决策42问：从V1到V6的最短距离为多少？从V1到V3的距离为多少？从V3到V5的最短距离为多少？数据、模型与决策数据、模型与决策43练习：求V1到V9点的最短距离。v1v2v3v4v5v6v7v8v923491351156512463数据、模型与决策数据、模型与决策44无向图（取消箭头）计算方法无向图（取消箭头）计算方法?86234151921234567数据、模型与决策数据、模型与决策45v1v2v3v4v5v6v7v8v923491351156512463数据、模型与决策数据、模型与决策46四、四、Ford算法算法Dijkstra算法不适用于负权网络具有负权的网络，应当用Ford算法（修正标号法）修正标号法特点是：不但最小T标号应改为P标号，P标号也可修改，修改后P标号再次改为T标号。25-464数据、模型与决策数据、模型与决策472v1v3v4v98-588545St7数据、模型与决策数据、模型与决策48五、寻找最短路径的方法使用双标号数据、模型与决策数据、模型与决策49已知有6个村庄，相互间道路距离如下图，拟建一所小学。A处有学生50人，B处有40人，C处有60人，D处有20人，E处有70人，F处有90人。问小学应建在哪个村庄，使学生上学走的路程最短？ABDCFE2664183137数据、模型与决策数据、模型与决策50第四节第四节 最大流问题最大流问题网络流的基本概念网络流的基本概念求解网络最大流的基本原理求解网络最大流的基本原理寻找网络最大流的标号法寻找网络最大流的标号法确定网络中最大流的方法确定网络中最大流的方法数据、模型与决策数据、模型与决策51 如图是联接某石油销地和产地的交通网（管道），如图是联接某石油销地和产地的交通网（管道），弧旁数字表示此运输管道的最大通过能力。产品弧旁数字表示此运输管道的最大通过能力。产品从从V1送到送到V7现在要求制定一个运输方案，使从现在要求制定一个运输方案，使从V1到到V7的产品运输最多。的产品运输最多。91344372858始点终点v1v2v3v42v5v6v7数据、模型与决策数据、模型与决策52一、网络流的基本概念一、网络流的基本概念流量：某时间内通过弧(vivj)的物质数量fij。容量：弧的最大允许流通量。始点（发点），终点（收点），中间点91344372858始点终点v1v2v3v42v5v6v7数据、模型与决策数据、模型与决策53可行流f：节点和边的限制条件（1）容量限制条件：通过每条弧的流量不超过弧的容量。（2）平衡条件：网络中的总流量等于始点净输出量；网络中的总流量等于终点净输入量；流进中间点的流量等于流出该点的流量。41341231223始点终点v1v2v3v41v5v6v7网络中的总流量数据、模型与决策数据、模型与决策54如何判断流分配是否可行？41341231223始点终点v1v2v3v41v5v6v791344372858始点终点v1v2v3v42v5v6v7数据、模型与决策数据、模型与决策55饱和弧：网络中流量等于容量的弧；非饱和弧：流量小于容量的弧；正向弧：定义从始点到终点的一条链，与链方向一致的弧，为正向弧，反之为反向弧。12345691344372858始点终点v1v2v3v42v5v6v7零流弧：流量=0的弧数据、模型与决策数据、模型与决策56增广链：对于一可行流 ，网络一条链满足BDCFE10，55，211，64，15，13，26，33，317，28，3非饱和弧非零流弧数据、模型与决策数据、模型与决策57二、求解网络最大流的基本原理二、求解网络最大流的基本原理数学模型数据、模型与决策数据、模型与决策58列出下述问题的数学模型：从三口油井1，2，3经管道将油输送到脱水处理厂7，8，中间经4，5，6三个泵站。图中弧旁数字为各管道通过的最大能力，求从油井每小时输送到处理厂的最大流量。20101010502030152050201234567830数据、模型与决策数据、模型与决策59定理：定理：可行流可行流f为最大流的充分必要条为最大流的充分必要条件是当且仅当网络不存在增广链。件是当且仅当网络不存在增广链。若若f是最大流，则不存在增广链；是最大流，则不存在增广链；若不存在增广链，则若不存在增广链，则f是最大流。是最大流。数据、模型与决策数据、模型与决策60给出一初始可行流，寻找增广链，若存在，则通过该增广链调整、增加网络流。若不存在增广链，则网络流不可再增加。求得最大流。流量调整多少？数据、模型与决策数据、模型与决策61三、寻找网络最大流的标号法三、寻找网络最大流的标号法Ford-Fulkson标号算法：寻增广链。给每个节点以一对标号，第一个标号表示箭尾节点，第二个标号表示可调整量，若终点有了标号，则找到一条增广链，否则不存在增广链。增广链判定：vivjvivj数据、模型与决策数据、模型与决策62调整过程：在增广链上，正向弧正向弧加上调整量，反向弧反向弧减去调整量。经过调整网络流v(f)增加一个调整量：4，43，05，33，36，4n按上述调整，得网络流是否可行？n流量是否增加了？4，43，15，23，36，3数据、模型与决策数据、模型与决策63数据、模型与决策数据、模型与决策64数据、模型与决策数据、模型与决策65数据、模型与决策数据、模型与决策66从三口油井1，2，3经管道将油输送到脱水处理厂7，8，中间经4，5，6三个泵站。图中弧旁数字为各管道通过的最大能力，求从油井每小时输送到处理厂的最大流量。20101010502030152050201234567830数据、模型与决策数据、模型与决策67第五节 最小费用最大流问题什么是最小费用流问题？求解最小费用流的赋权图法数据、模型与决策数据、模型与决策68一、什么是最小费用流354123152最大流分配是否唯一？最大流分配是否唯一？引入每条流的成本！数据、模型与决策数据、模型与决策69给定网络N=(V,A,c,b)和经过网络的流量v，求流在网络上的最佳分布，使总费用最小。数据、模型与决策数据、模型与决策70二、求解最小费用流的赋权图法二、求解最小费用流的赋权图法增广链费用，最小费用增广链。当沿着一条关于可行流f的增广链，以 调整f，得到的可行流f，流量增加，费用变化：称之为增广链的费用。多条增广链,费用不同.数据、模型与决策数据、模型与决策71对于可行流，沿最小费用增广链调整流，对于可行流，沿最小费用增广链调整流，可使流增加，并保持流费用最小。可使流增加，并保持流费用最小。给定初始可行流（若该流量下费用最小），给定初始可行流（若该流量下费用最小），求最小费用增广链，若存在，则沿该增广求最小费用增广链，若存在，则沿该增广链调整网络流；再寻求最小费用增广链，链调整网络流；再寻求最小费用增广链，直到给定的网络流不存在增广链为止，即直到给定的网络流不存在增广链为止，即为最小费用最大流。为最小费用最大流。数据、模型与决策数据、模型与决策72如何求最小费用增广链？增广链的条件增广链的条件数据、模型与决策数据、模型与决策73赋权网络：赋权网络：将饱和弧反向将饱和弧反向将非饱和、非零流弧加一反向弧将非饱和、非零流弧加一反向弧零流弧不变零流弧不变所有正向弧的权为该弧的费用，反向弧的所有正向弧的权为该弧的费用，反向弧的权为该弧费用的相反数权为该弧费用的相反数如此变化后，有何特点？如此变化后，有何特点？n赋权图中，从始点到终点每条通路都是当前赋权图中，从始点到终点每条通路都是当前可行流的增广链。可行流的增广链。n最小费用增广链对应赋权网络的最短路。最小费用增广链对应赋权网络的最短路。数据、模型与决策数据、模型与决策74最小费用流的实例数据、模型与决策数据、模型与决策75数据、模型与决策数据、模型与决策76数据、模型与决策数据、模型与决策77数据、模型与决策数据、模型与决策78数据、模型与决策数据、模型与决策79-2数据、模型与决策数据、模型与决策80数据、模型与决策数据、模型与决策81赋权赋权网络已不存在最短路（增广链）网络已不存在最短路（增广链）数据、模型与决策数据、模型与决策82第六节网络计划技术第六节网络计划技术网络图的绘制与识别网络图的时间参数计算网络优化的基本方法数据、模型与决策数据、模型与决策83甘特图不易表现工程全貌不易表现工程全貌不便于对各项工作的安排进行筹划和推敲不便于对各项工作的安排进行筹划和推敲不能识别影响进度的关键工作不能识别影响进度的关键工作不能反映一项工作不能按进度完成时对工不能反映一项工作不能按进度完成时对工程进度影响程进度影响项目有几项工作项目有几项工作?能否体现工作之间先后关系能否体现工作之间先后关系?能否反映工作开工和完工的能否反映工作开工和完工的时间时间?数据、模型与决策数据、模型与决策84一、网络图一、网络图网络图的构成作业作业（工作、工序、活动），箭头箭头表示，箭头之上表示工作名称，之下表示工作时间。需要消耗一定的人力、物力，经过一定的时间完成。事项事项，节点表示，表示某个工作的结束和另一工作的开始。虚工作虚工作数据、模型与决策数据、模型与决策85一个基建项目网络图一个基建项目网络图特点：工作数；先后时间。有了工作和事项，可按照特点：工作数；先后时间。有了工作和事项，可按照作业的先后次序绘制网络图。作业的先后次序绘制网络图。数据、模型与决策数据、模型与决策86路线：路线：从开始节点开始节点到结束节点结束节点的一条路经，一个网络图有多条路线，每条路线有一个总时间。关键路线：关键路线：总时间最长的路线。工期：工期：关键路线的总时间数据、模型与决策数据、模型与决策87网络图的路线网络图的路线路线有几条？路线有几条？关键路线是哪条？关键路线是哪条？工期有多长？工期有多长？数据、模型与决策数据、模型与决策88以上网络图共有8条路线可以计算出这8条路线的总时间，最长的是16天。关键路线是当某些工作的时间调整后，可能引起关键路线的变化和工期的变化。例如将工作E的时间缩短为4天，则工期缩短为13天，关键路线将变为1346BEG5651356BFH553数据、模型与决策数据、模型与决策89二、二、网络图的画法作业的串联：先行作业；紧前作业；紧前作业；紧后作业作业的并联两事项间只能有一项作业两事项间只能有一项作业数据、模型与决策数据、模型与决策90网络图应从左向右延伸，编号应从小到大，且不重复。箭头事项编号大于箭尾事项编号。网络图只能一个开始节点，一个终止节点。不能出现循环路线。尽量少交叉，采用暗桥；有层次性。始工作和结束工作绘制网络图的基本原则绘制网络图的基本原则数据、模型与决策数据、模型与决策91数据、模型与决策数据、模型与决策92一项工作有两个紧后工作一项工作有两个紧前工作数据、模型与决策数据、模型与决策93数据、模型与决策数据、模型与决策94修改修改数据、模型与决策数据、模型与决策95三、网络图时间参数计算三、网络图时间参数计算事项时间参数的计算作业时间参数的计算关键路线的寻找方法数据、模型与决策数据、模型与决策96作业时间的确定作业时间的确定对具有标准的作业，采用单一时间估计法对一般性作业，采用三点时间估计法最乐观时间：a最可能时间：m最悲观时间：b计算时间期望值和方差数据、模型与决策数据、模型与决策97作业时间计算方法作业时间计算方法数学期望；方差数据、模型与决策数据、模型与决策98事项参数计算事项参数计算事项最早时间：以节点j为开始的各项作业最早可开工的时间。事项最迟时间：以此节点为结束的各项作业最迟必须完成时间。ijiiijj数据、模型与决策数据、模型与决策99图上计算法1）从始节点开始（始节点最早为零），用方括号表示某节）从始节点开始（始节点最早为零），用方括号表示某节点的最早时间。点的最早时间。2）从终节点开始（终节点最迟为工期），用三角表示某节）从终节点开始（终节点最迟为工期），用三角表示某节点最迟时间。点最迟时间。12345ABCDEHFG67841078127540411141426313501441414263135数据、模型与决策数据、模型与决策100作业时间参数的计算作业时间参数的计算作业最早开始时间作业最早结束时间作业最迟开始时间作业最迟结束时间总时差单时差数据、模型与决策数据、模型与决策101作业最早时间作业最早时间ijii最早开始最早开始最早结束最早结束数据、模型与决策数据、模型与决策102作业最迟时间作业最迟时间ijj最迟开始最迟开始最迟结束最迟结束数据、模型与决策数据、模型与决策103作业时间参数计算作业时间参数计算12345ABCDEHFG67841078127540411141426313501441414263135作业作业D的时间参数的时间参数作业作业G的时间参数的时间参数数据、模型与决策数据、模型与决策104总时差：在不影响总工程完工工期情况下，作业完工期可推迟的时间。单时差：不影响下一作业最早开工的情况下，一项作业完工期可推迟的时间。最早开始，最早结束最早开始，最早结束最迟开始，最迟结束最迟开始，最迟结束ijEF数据、模型与决策数据、模型与决策105时差12345ABCDEHFG67841078127540411141426313501441414263135数据、模型与决策数据、模型与决策106最早时间：最早时间：由上到下；先定开始作业由上到下；先定开始作业A的最早开始时间的最早开始时间（0），加上作业时间得到作业的最早结束时间。凡是先行），加上作业时间得到作业的最早结束时间。凡是先行作业（作业（B，C）只有一个为）只有一个为A，则，作业，则，作业A的最早结束时间为的最早结束时间为该作业（该作业（B，C）的最早开始时间。若有多项先行作业，则）的最早开始时间。若有多项先行作业，则为先行作业最早结束时间最长的为该作业的最早开始时间。为先行作业最早结束时间最长的为该作业的最早开始时间。数据、模型与决策数据、模型与决策107最迟时间：最迟时间：由下到上；最后一个作业的最早结束时间为最迟由下到上；最后一个作业的最早结束时间为最迟结束时间，减去作业时间为最迟开始时间；查看该作业的先结束时间，减去作业时间为最迟开始时间；查看该作业的先行作业，先行作业的最迟结束时间为该作业的最迟开始时间。行作业，先行作业的最迟结束时间为该作业的最迟开始时间。若某作业是两个以上作业的先行作业，取小的为该作业的最若某作业是两个以上作业的先行作业，取小的为该作业的最迟开始时间。迟开始时间。数据、模型与决策数据、模型与决策108关键路线的确定方法总时差为零的作业即是关键作业；关键作业构成关键路线。数据、模型与决策数据、模型与决策109已知下表所列资料：要求(1)绘制网络图；(2)计算各工序的最早开工、最早完工，最迟开工，最迟完工时间，总时差，并指出关键工序；(3)若要求工程完工时间缩短2天，缩短哪些工序的时间为好。工序 紧前工序工序时间工序 紧前工序工序时间工序 紧前工序工序时间ag,m3ec5ia,l2bh4fa,e5kf,i1c-7gb,c2lb,c7dl3h-5mc3数据、模型与决策数据、模型与决策110四、网络优化四、网络优化工程进度计划编制：工期，费用，工程进度计划编制：工期，费用，资源资源从工程进度角度编制，考虑工工作时间作时间关系；考虑资源条件限制，包括人员和物质条件，如设备工时，器材，工具，厂房，运输工具，原材料，动力，燃料。数据、模型与决策数据、模型与决策111工期限定，资源需要平衡工期限定，资源需要平衡问题：问题：多项工作同时展开，可能导致资源使用不均衡，延误关键工作，不能保证工期。解决措施：解决措施：工期不变，就是关键工作时间不能调整。调整非关键路线上工作的开始时间，使资源实现平衡。数据、模型与决策数据、模型与决策112箭线下面的数字是作业时间；箭线下面的数字是作业时间；括号内是该作业所需的人力。括号内是该作业所需的人力。数据、模型与决策数据、模型与决策113各工作都按最早开各工作都按最早开始时间开始始时间开始12345678910 11123564H(1)G(2)A(9)E(8)B(3)F(7)D(4)C(6)数据、模型与决策数据、模型与决策114数据、模型与决策数据、模型与决策115调整非关键工作的开始时间调整非关键工作的开始时间数据、模型与决策数据、模型与决策116资源有限，要求工期最短资源有限，要求工期最短下图表示的项目只有10人工作数据、模型与决策数据、模型与决策117第一次调整第一次调整数据、模型与决策数据、模型与决策118第二次调整第二次调整数据、模型与决策数据、模型与决策119费用优化费用优化一般情况下，若采取措施缩短工期，则间接费用将减少，直接费用将增加。间接费用：管理费间接费用：管理费用，工期越短，间用，工期越短，间接费用越少。接费用越少。直接费用：与项目直接费用：与项目规模有关的费用，规模有关的费用，包括材料费用，直包括材料费用，直接生产工人工资。接生产工人工资。数据、模型与决策数据、模型与决策120计算工作费用率：缩短工作每一单位时间，所需计算工作费用率：缩短工作每一单位时间，所需要增加的费用。要增加的费用。在网络图中找出费用率最低的关键工作作为缩短在网络图中找出费用率最低的关键工作作为缩短时间的对象。时间的对象。计算费用变化。计算费用变化。数据、模型与决策数据、模型与决策121作业的费用率为极限时间正常时间数据、模型与决策数据、模型与决策122一个例子ij问题：正常工期多少天？问题：正常工期多少天？缩短工期，费用变化情况？缩短工期，费用变化情况？数据、模型与决策数据、模型与决策123解题思路以正常时间进行网络分析，求得关键路线。在关键路线上，寻找最小费率的工作，缩短其时间，使工期最多到次长路线次长路线的长度。缩短工期必须对所有关键路线进行，此时应选择费率总和最小的组合方案。数据、模型与决策数据、模型与决策124第一步求关键路线第一步求关键路线工期=11天缩短工期受到缩短工期受到两个限制：极两个限制：极限时间；新关限时间；新关键路线。键路线。数据、模型与决策数据、模型与决策125第二步选择第二步选择(2,3)缩短工期缩短工期工期=10天增加费用1数据、模型与决策数据、模型与决策126第三步按第第三步按第I I方案缩短工期方案缩短工期工期=9天增加费用1+2=3数据、模型与决策数据、模型与决策127再按方案再按方案III缩短周期缩短周期工期=8天增加费用3+3=6数据、模型与决策数据、模型与决策128第四步按第第四步按第I、II方案缩短方案缩短4天天工期=4天增加费用6+16=22数据、模型与决策数据、模型与决策129一般数学模型一般数学模型设工作j（j=1，J）的完成需要第k种资源量为rjk，工作执行时间为dj。第k种资源总量为常量Rk，工作j的开始时间为Sj，At为在t-1，t时间段内正在进行的工作集合。则工期最短的数学模型为：数据、模型与决策数据、模型与决策130本章要求结合企业的某项活动，按照资源条件进行计划排定。数据、模型与决策数据、模型与决策此课件下载可自行编辑修改，供参考！此课件下载可自行编辑修改，供参考！感谢您的支持，我们努力做得更好！感谢您的支持，我们努力做得更好！