管理数学实验—— MATLAB在管理运筹中的应用4_管理数学实验_图与网络的优化计算

1、Zxf.sme.bit第4章 图与网络的优化计算1、图与网络的概念、图与网络的概念2、最短路问题最短路问题3、统筹方法、统筹方法Zxf.sme.bit1、图与网络的基本概念、图与网络的基本概念1.1 1.1 图的基本构成图的基本构成1.2 1.2 图的图的基本术语基本术语1.3 1.3 图的代数图的代数表示表示Zxf.sme.bit1 1.1 .1 图的基本构成图的基本构成 图论中图是由图论中图是由点点与与边边构成，反映一些对象之间的关系。构成，反映一些对象之间的关系。 例例1，在一人群中，对相互认识的关系可以用图来表示，如下图，在一人群中，对相互认识的关系可以用图来表示，如下图e2e4e3e

2、1李(v4)赵(v1)周(v5)孙(v3)吴(v6)钱(v2)陈(v7)e5Zxf.sme.bit 图可以很好的描述、刻画反映对象之间的特定关系。图可以很好的描述、刻画反映对象之间的特定关系。 一般情况下，图中点的相对位置、联线长短，对于反映对象之一般情况下，图中点的相对位置、联线长短，对于反映对象之间的关系并不是很重要，如对上图七人相互认识的关系也可以间的关系并不是很重要，如对上图七人相互认识的关系也可以用下图来表示。可见图论的图与几何图、工程图是不一样的。用下图来表示。可见图论的图与几何图、工程图是不一样的。e3e4e1e2李李(v4)赵赵(v1)周周(v5)孙孙(v3)吴吴(v6)钱钱(

3、v2)陈陈(v7)e5Zxf.sme.bit 如果把上面例子中如果把上面例子中“相互认识相互认识”的关系改成的关系改成“认识认识”的关系，的关系，那么只用两点联线就很难刻画他们之间的关系了，这是引入一那么只用两点联线就很难刻画他们之间的关系了，这是引入一个带箭头的联线，称为个带箭头的联线，称为弧弧 在图论中，在图论中，弧弧通常记为通常记为ai,下图就是一个反映这下图就是一个反映这7人人“认识认识”关关系的图。系的图。a5 a6a3 a4李李(v4)赵赵(v1)周周(v5)孙孙(v3)吴吴(v6)钱钱(v2)陈陈(v7)a11a1a2a7 a8a9 a10a12a13a14Zxf.sme.bit

4、1.2 图的基本术语无向图：无向图： 由由点点和和边边构成的图叫构成的图叫无向图无向图，简称图，记作，简称图，记作G=(V,E)，其中，其中，V是图是图G的点集合，的点集合，E是图是图G的边集合；的边集合；有向图：有向图： 由由点点和和弧弧构成的图叫构成的图叫有向图有向图。记为。记为D=（V,A），其中），其中V为图为图D的点的点集合，集合，A为图为图D的弧集合。的弧集合。无向图是一种特殊的有向图，无向图的边实际就是等价于两条反无向图是一种特殊的有向图，无向图的边实际就是等价于两条反向的弧。向的弧。Zxf.sme.bit821521,),(eeeEvvvVEVG端点，关联边，相邻端点，关联边，

5、相邻 若有边若有边e可表示为可表示为e=vi,vj,称称vi和和vj是边是边e的的端点端点，反之称边，反之称边e为点为点vi或或vj的的关联边关联边。若。若点点vi、vj与同一边关联，称点与同一边关联，称点vi和和vj相邻；若相邻；若边边ei和和ej具有公共的端点，称边具有公共的端点，称边ei和和ej相邻相邻。,212vve e2可记作：v3e7e4e8e5e6e1e2e3v1v2v4v5G =（V，E）Zxf.sme.bit环，多重边，简单图环，多重边，简单图 如果边如果边e的两个端点相重，称该边为的两个端点相重，称该边为环环。如果两个点之间多于一条边，称为如果两个点之间多于一条边，称为多重

6、边多重边，对无环、无多重边的图称作对无环、无多重边的图称作简单图简单图。 次，奇点，偶点，孤立点次，奇点，偶点，孤立点 与某一个点与某一个点vi相关联的边的数目称为相关联的边的数目称为点点vi的的次次（也叫做度），记作（也叫做度），记作d(vi)。 d(v1), d(v3)=5, d(v5)=1。次为奇数的点称作次为奇数的点称作奇点奇点，次为偶数的点称作次为偶数的点称作偶点偶点，次为次为0的点称作的点称作孤立点孤立点。图的次图的次 一个图的次等于各点的次之和。一个图的次等于各点的次之和。v3e7e4e8e5e6e1e2e3v1v2v4v5Zxf.sme.bit 链、路、回路（圈）链、路、回路（

7、圈） 图中有些点和边的交替序列图中有些点和边的交替序列对任意对任意vt1 和和vt(2tk)均相邻，称均相邻，称从从v0到到vk的的链链。如果链中各边。如果链中各边e1,e2,ek互不相同称为互不相同称为简单链简单链。如果链中所有的顶点。如果链中所有的顶点v0，v1，vk也不相同，这样的链称也不相同，这样的链称初等链（路）初等链（路）。当。当v0与与vk重合时称为重合时称为回路回路（圈圈），如果边不重），如果边不重复称为简单回路（复称为简单回路（圈圈）kkvevev,110图中，图中，1=v5,e8,v3,e3,v1,e2,v2,e4,v3,e7,v4是一条链，是一条链，1中因顶中因顶点点v3

8、重复出现，不能称作路，但重复出现，不能称作路，但称为称为简单链简单链。v3e7e4e8e5e6e1e2e3v1v2v4v5Zxf.sme.bit是一条链也是一条路。是一条链也是一条路。473852,vevevv3e7e4e8e5e6e1e2e3v1v2v4v5连通图连通图若在一个图中，如果每一对顶点之间至少存在一条链，若在一个图中，如果每一对顶点之间至少存在一条链，称这样的图为称这样的图为连通图连通图，否则称该图是不连通的。，否则称该图是不连通的。3=v4,e7,v3,e3,v1,e2,v2,e6,v4是一条回路并且是简单回路。是一条回路并且是简单回路。Zxf.sme.bit子图、支撑子图子图

9、、支撑子图 图图G1=V1、E1和图和图G2=V2，E2如果如果 称称G1是是G2的一个的一个子图子图。 若有若有 则称则称 G1是是G2的一的一个个支撑子图支撑子图（部分图）。（部分图）。 注意支撑子图也注意支撑子图也是子图是子图,子图不一定是支撑子图。子图不一定是支撑子图。2121EEVV和2121EEVV，v3e7e4e8e5e6e1e2e3v1v2v4v5v3e7e6e1e2e3v1v2v4v5支撑子图支撑子图e4v3e8e5e6v2v4v5子图子图Zxf.sme.bit赋权图赋权图 赋权图 G=V,E 是指研究对象点之间关系的某种属性用权数表示，如距离、费用等，这个权数与边eiE相关

10、联，表示为边的权数C(ei) 0。赋权图的权数根据研究问题的需要而定。 下图所示为赋权图。Zxf.sme.bit关关联联矩矩阵阵注：设图为简单图不关联与若相关联与若01jijiijevevm)(ijm对无向图，其关联矩阵，其中：不关联与若的终点是若的起点是若jijijiijevevevm011)(ijm对有向图，其关联矩阵，其中：1.3 图的代数表示Zxf.sme.bit邻邻接接矩矩阵阵注：设图为简单图不相邻与若相邻与若01jijiijvvvva)(ijaA对无向图，其邻接矩阵，其中：)(ijaA对有向图=(V, E)，其邻接矩阵，其中：EvvEvvajijiij),(),(01Zxf.sme

11、.bit邻邻接接矩矩阵阵对赋权图，其邻接矩阵，其中： VVijaAEvvjiwEvvwaiijiijij),(0,),(jj当当为权值当 Zxf.sme.bit2 2 最短路问题最短路问题 2.1 最短路算法及程序最短路算法及程序 2.2 最短路示例最短路示例Zxf.sme.bit2.12.1 最短路算法及程序最短路算法及程序 最短路问题是对一个赋权的有向图最短路问题是对一个赋权的有向图D（其赋权根据具体问题的要（其赋权根据具体问题的要求可以是路程的长度，成本的花费等等）中指定的两点求可以是路程的长度，成本的花费等等）中指定的两点vs和和vt，找到，找到一条从一条从vs到到vt的最短路，使得这

12、条路上所有弧的权数的总和最小，这的最短路，使得这条路上所有弧的权数的总和最小，这条路被称之为从条路被称之为从vs到到vt的的最短路最短路，这条路上所有弧的权数的总和被称，这条路上所有弧的权数的总和被称之为从之为从vs到到vt的的距离距离。 最短路问题求解的最常用方法有：最短路问题求解的最常用方法有： 固定起点固定起点的最短路的最短路Dijkstra算法算法 和和 任意两顶点之间的任意两顶点之间的最短路最短路Floyd算法算法Zxf.sme.bit例例2、用用Dijkstra算法求下图v1到v7的最短路长及最短路线86252353421057(0,s)862(2,1)54(4,4)11147(5

13、,4)10(7,6)12(11,6)v7已标号，计算结束。从v1到v7的最短路长是 11最短路线是：v1 v4 v6 v7Zxf.sme.bit Floyd算法 Floyd算法是一种用于寻找给定的加权图中任意两顶点之间的最短路径的算法。它是通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的赋权邻接矩阵A=a(i,j)nn开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样的公式由D(1)构造出D(2)；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时引入

14、一个路径矩阵R来记录两点间的中间点，据此可推得任意两点间的最短路径。Zxf.sme.bit Floyd算法步骤： 算法步骤求任意两点间的最短路Floyd算法描述：求任意两顶点间的最短路。如前所示，符号d(i,j)代表i到j的距离，r(i,j)代表i到j之间的插入点。算法的输入为赋权邻接矩阵初始化：令k =1，对i,jV，设置d(i,j)= w(i,j)，r(i,j)= j；更新d(i,j)，r(i,j)当k = |V|，则计算结束；否则令k=k+1，转。VVjiwW), (否则当),(),(),(),(),(),(),(,jkdkidjkdkidjidjidjidji否则当kjkdkidjid

15、jirjirji),(),(),(),(),(,Zxf.sme.bit Floyd算法程序function D,R=my_floydDR(A) %Floyd算法，求最短距离矩阵和路径矩阵% 输出参数： D为最短距离矩阵， R最短路径矩阵% 输入参数： A赋权邻接矩阵 n=size(A,1); D=A; %赋初值 DR=zeros(n,n);for i=1:n for j=1:n if D(i,j)=inf R(i,j)=j; %赋初值 R end endendfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j) 0 disp(min_path=); di

16、sp(min_path); disp(min_distance=); disp( min_distance); end end endendZxf.sme.bit计算结果：min_path= 1 4 6 2min_distance= 7min_path= 1 4 3min_distance= 5min_path= 1 4min_distance= 2min_path= 1 4 6 2 5min_distance= 12min_path= 1 4 6min_distance= 4min_path= 1 4 6 7min_distance= 11min_path= 2 5min_distance=

17、 5min_path= 2 5 7min_distance= 10min_path= 3 2min_distance= 5min_path= 3 4min_distance= 2min_path= 3 2 5min_distance= 10min_path= 3 6min_distance= 4min_path= 3 6 7min_distance= 11min_path= 4 6 2min_distance= 5min_path= 4 3min_distance= 3min_path= 4 6 2 5min_distance= 10min_path= 4 6min_distance= 2mi

18、n_path= 4 6 7min_distance= 9min_path= 5 7min_distance= 5min_path= 6 2min_distance= 3min_path= 6 2 5min_distance= 8min_path= 6 7min_distance= 7Zxf.sme.bit最短路问题的应用 例例4.设备更新问题设备更新问题。某公司使用一台设备，在每年年初，公司就。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费就低。如

19、果继续使用旧设备，支付一定的购置费，当然新设备的维修费就低。如果继续使用旧设备，这样可以省去了购置费，但维修费就高了。现在需要制定一个五年之这样可以省去了购置费，但维修费就高了。现在需要制定一个五年之内的更新设备的计划，使得五年内购置费和维修费总的支付费用最小。内的更新设备的计划，使得五年内购置费和维修费总的支付费用最小。这种设备每年年初的价格及设备所需要的维修费如表所示。这种设备每年年初的价格及设备所需要的维修费如表所示。Zxf.sme.bit设备每年年初的价格表设备每年年初的价格表已知使用不同时间（年）的设备所需要的维修费如表所示已知使用不同时间（年）的设备所需要的维修费如表所示设备所需要

20、的维修费设备所需要的维修费表表使用年数使用年数0-11-22-33-44-5每年维修费用每年维修费用5681118年份年份12345年初价格年初价格1111121213Zxf.sme.bit161617171822304159223041233123(0,s)(16,1)(22,1)(30,1)(41,1)(53,3,4)设备更新设备更新问题图示计算问题图示计算：Zxf.sme.bit建立主程序脚本文件，调用Dijkstra算法程序求解：得到结果：W = 0 16 22 30 41 59 Inf 0 16 22 30 41 Inf Inf 0 17 23 31 Inf Inf Inf 0 17

21、 23 Inf Inf Inf Inf 0 18 Inf Inf Inf Inf Inf 0 ; min_distance, min_Path = zxf_multiPath_Dijkstra(W, 1, 6)min_distance = 53min_Path = 1 3 6 1 4 6Zxf.sme.bit从从v1到到 v6的距离为的距离为53，其最短路径有两条：，其最短路径有两条： 一条为一条为v1 v3 v6，另一条为，另一条为 v1 v4 v6。第第一个方案为第一个方案为第1年初的购置新设备使用到第年初的购置新设备使用到第2年底（第年底（第3年初），年初），第第3年初再购置新设备使用到

22、第年初再购置新设备使用到第5年底（第年底（第6年初）。年初）。第二个方案为第第二个方案为第1年初的购置新设备使用到第年初的购置新设备使用到第3年底（第年底（第4年初），年初），第第4年初再购置新设备使用到第年初再购置新设备使用到第5年底（第年底（第6年初）。年初）。这两个方案使得总的支付为最小，均为这两个方案使得总的支付为最小，均为53。Zxf.sme.bit 作为一个管理者，常常面临着一些复杂、大型的工程项目，这些作为一个管理者，常常面临着一些复杂、大型的工程项目，这些工程项目涉及到众多部门和单位的大量的独立的工作或活动，如何来工程项目涉及到众多部门和单位的大量的独立的工作或活动，如何来编制

23、计划、安排进度并进行有力的控制，这是管理的重要内容。编制计划、安排进度并进行有力的控制，这是管理的重要内容。 统筹方法是解决这些问题的强有力的工具。这种技术是在统筹方法是解决这些问题的强有力的工具。这种技术是在 20 世世纪纪 50 年代末发展起来的，年代末发展起来的，1956 年美国杜邦公司为了协调企业不同业年美国杜邦公司为了协调企业不同业务部门的系统规划，应用网络方法制定了第一套网络计划，提出了务部门的系统规划，应用网络方法制定了第一套网络计划，提出了3 统筹方法统筹方法Zxf.sme.bit关键路线方法关键路线方法 ( Critical Path Method， 缩写为缩写为 CPM )

24、。 1958 年美国海军武装部在研制年美国海军武装部在研制“北极星北极星”导弹计划时，针对导弹计划时，针对”北北极星极星”导弹项目中很多工作或活动都是第一次尝试。因其完成工作导弹项目中很多工作或活动都是第一次尝试。因其完成工作或活动的时间无经验数据可循的特点提出了或活动的时间无经验数据可循的特点提出了计划计划 (图解图解) 评审法评审法 (Program Evaluation and Review Technique，缩写为缩写为 PERT ) 。由于由于 CPM 与与 PERT 既有相同的目标与应用，又有很多相同的术语，这两既有相同的目标与应用，又有很多相同的术语，这两个方法合并为一种方法，

25、在国外称之为个方法合并为一种方法，在国外称之为 PERT / CPM，60 年代我国开年代我国开始应用这种方法，根据它统筹安排的特点，称之为始应用这种方法，根据它统筹安排的特点，称之为统筹方法统筹方法。Zxf.sme.bit 统筹方法可以应用在各种不同的项目计划上，特别适用于生统筹方法可以应用在各种不同的项目计划上，特别适用于生产技术复杂、工作项目繁多且联系紧密的一些跨部门的工作计划，产技术复杂、工作项目繁多且联系紧密的一些跨部门的工作计划，例如新产品的研制开发，工厂、大楼、高速公路等大型工程项目例如新产品的研制开发，工厂、大楼、高速公路等大型工程项目的建设，大型复杂设备的维修以及新系统的设计

26、与安装等计划。的建设，大型复杂设备的维修以及新系统的设计与安装等计划。 统筹方法包括统筹方法包括绘制计划网络图、进度安排、网络优化绘制计划网络图、进度安排、网络优化等环节，等环节，下面分别讨论这些内容。下面分别讨论这些内容。Zxf.sme.bit 网络方法网络方法(也叫统筹方法或计划协调技术也叫统筹方法或计划协调技术)是一种科学的组织管是一种科学的组织管理方法，在实际工作中取得了良好效果，被广泛地应用到各个理方法，在实际工作中取得了良好效果，被广泛地应用到各个部门。部门。 网络方法的网络方法的主要特点主要特点： 系统性；系统性； 协调性；协调性； 动态性；动态性； 可计算性。可计算性。Zxf.

27、sme.bit 网络方法的网络方法的主要步骤主要步骤： 绘制工序流程网络图；绘制工序流程网络图； 计算时间参数；计算时间参数； 确定关键路线；确定关键路线； 制定工程进度表。制定工程进度表。3.1 3.1 基本概念基本概念(1) (1) 工序流程网络图：工序流程网络图：描述一项工程各工序、事项及线路的描述一项工程各工序、事项及线路的关系和组成的有向图。关系和组成的有向图。 一项工程总是由一些工序一项工程总是由一些工序(或作业或作业)所组成。所组成。 工程：一项复杂的工作任务；工程：一项复杂的工作任务； 工序：在完成某项工程的过程中，相对独立的活动工序：在完成某项工程的过程中，相对独立的活动 事

28、项：工序的开工或完工事项：工序的开工或完工(相邻工序的交接处相邻工序的交接处)Zxf.sme.bit(2) (2) 工序流程网络图符号工序流程网络图符号 工序：用一支箭工序：用一支箭“”表示一道工序；表示一道工序； 事项：用一个圈事项：用一个圈“”表示一个事项；表示一个事项；(下图为一网络图下图为一网络图)u箭尾事项箭尾事项、箭头事项箭头事项u相关事项相关事项u紧前工序紧前工序u紧后工序紧后工序u始点事项始点事项、终点事项终点事项1298574635A4D6H2I3L4F7 B32K3J2E1GC图图3Zxf.sme.bit(3) (3) 绘制网络图的规则绘制网络图的规则必须正确表达各工序之间

29、的相互制约和相互依赖关系必须正确表达各工序之间的相互制约和相互依赖关系必须按工序的先后顺序从左向右画图，不应有必须按工序的先后顺序从左向右画图，不应有“缺口缺口”和和“回路回路”每一道工序与其相关的箭头箭尾事项必须一一对应每一道工序与其相关的箭头箭尾事项必须一一对应相关事项只能为一个工序所有，应用虚工序解决平行工序相关事项只能为一个工序所有，应用虚工序解决平行工序只允许出现一个开始事项和一个结束事项只允许出现一个开始事项和一个结束事项较长时间工序的分段平行作业处理较长时间工序的分段平行作业处理较大或较复杂网络图的简化与合并。较大或较复杂网络图的简化与合并。Zxf.sme.bit 绘制网络图的例

30、子：绘制网络图的例子：(4) 路与关键路线路与关键路线 路：从始点到达终点的一条通路路：从始点到达终点的一条通路 关键路线：所需时间最长的路关键路线：所需时间最长的路201011432A I61578A IIA III BI BIIBIII B乙乙甲甲AC图图5Zxf.sme.bit3.2 计划网络图计划网络图 统筹方法的第一步工作就是绘制计划网络图，也就是将统筹方法的第一步工作就是绘制计划网络图，也就是将工序工序（或称为活动、作业，指任何消耗时间或资源的行动或称为活动、作业，指任何消耗时间或资源的行动）进度表转进度表转换为统筹方法的网络图。换为统筹方法的网络图。 下面用一个例题来说明计划网络

31、图的绘制方法。下面用一个例题来说明计划网络图的绘制方法。例例5. 某公司研制新产品的部分工序与所需时间以及它们之间的某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其相互关系都显示在其 工序进度表工序进度表 如下表所示，请画出其统筹方如下表所示，请画出其统筹方法网络图。法网络图。Zxf.sme.bit工序代号工序代号工序内容工序内容所需时间所需时间(天天)紧前工序紧前工序a产品设计与工艺设计产品设计与工艺设计60b外购配套零件外购配套零件15ac外购生产原料外购生产原料13ad自制主件自制主件38ce主配件可靠性试验主配件可靠性试验8b，d解：解：用网络图来表示上述的工序进度

32、表。用网络图来表示上述的工序进度表。13245a60b15e8c13d38图图 6Zxf.sme.bit例例 6 . 把例把例 5 的工序进度表作一些扩充，如下表所示，请画的工序进度表作一些扩充，如下表所示，请画出其统筹方法的网络图。出其统筹方法的网络图。工序代号工序代号所需时间所需时间(天天)紧前工序紧前工序a60b15ac13ad38ce8b，df10dg16dh5e， f，gZxf.sme.bit解：解：在图在图 6 加入加入 f 工序得图工序得图 7 。13245a60b15e8c13d386f10图图 7Zxf.sme.bit在网络图上添加在网络图上添加 g、h 工序得网络图如下工序

33、得网络图如下 图图 8 中工序中工序 f 和工序和工序 g 有相同的开始点有相同的开始点 4 和结束点和结束点 6。由于。由于在统筹方法的网络中计算机程序计算时，相邻两个点之间不管在统筹方法的网络中计算机程序计算时，相邻两个点之间不管有多少弧（工序），计算机都有多少弧（工序），计算机都13245a60b15e8c13d386f107h5g16图图8Zxf.sme.bit认为它们是同一条弧认为它们是同一条弧（同一个工序同一个工序），因此，因此在统筹方法的网络在统筹方法的网络图中不允许两个点之间有多于一条弧的情况发生图中不允许两个点之间有多于一条弧的情况发生。为此增加一。为此增加一个点和虚工序，同

34、时调整一些点的编号，得图个点和虚工序，同时调整一些点的编号，得图 9，这就是例，这就是例 4 的统筹方法网络图。的统筹方法网络图。ab132456015e8c13d387f108h5g16图图 960Zxf.sme.bit3.3 网络时间与关键网络时间与关键路线（路线（CPM） 在绘制出网络图之后，可以用网络图求出：在绘制出网络图之后，可以用网络图求出： 1）完成此工程项目所需的最少时间。）完成此工程项目所需的最少时间。 2）每个工序的开始时间与结束时间。）每个工序的开始时间与结束时间。 3）关键路线及其相应的关键工序。）关键路线及其相应的关键工序。 4）非关键工序在不影响工程的完成时间的前提

35、下，其开始）非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时间可以推迟多久。时间与结束时间可以推迟多久。Zxf.sme.bit(1) (1) 时间参数的计算时间参数的计算 工序时间工序时间t(i,j) 事项的最早时间事项的最早时间te(j)t te e(j)=max(j)=maxt te e( (i i) + t() + t(i,ji,j),j=2,3,),j=2,3,n,ni it te e( (i i) )为为( (i,ji,j) )工序箭尾事项的最早时间，工序箭尾事项的最早时间，始点始点t te e(1)=0(1)=0，n n表示终点事项编号。表示终点事项编号。 工程最早完工

36、时间工程最早完工时间Tf T Tf f= =t te e(n)(n) 事项的最迟时间事项的最迟时间tl(i)t tl l( (i i)=min)=mint tl l(j)-t(j)-t(i,ji,j),),i i=n-1,n-2,=n-1,n-2,1,1tl(n)= te(n) =Tf，或，或tl(n)=SD(计划完成时间计划完成时间)。Zxf.sme.bit 工序的最早可能开工时间工序的最早可能开工时间tes(i,j) t tes( (i,ji,j)=)=t te( (i i) ) 工序的最迟必须开工时间工序的最迟必须开工时间tls(i,j)t tls( (i,ji,j)=)=t tl(j)

37、-t(j)-t(i,ji,j) ) 工序的最早可能完工时间工序的最早可能完工时间tef(i,j)t tef( (i,ji,j)=)=t tes( (i,ji,j)+t()+t(i,ji,j)=)=t te( (i i)+t()+t(i,ji,j) ) 工序的最迟必须完工时间工序的最迟必须完工时间tlf(i,j)t tlf( (i,ji,j)=)=t tls( (i,ji,j)+t()+t(i,ji,j)=)=t tl(j)(j) 事项松弛时间事项松弛时间SE(i)SE(SE(i i)=)=t tl( (i i)-)-t te( (i i) )Zxf.sme.bit 工序总时差工序总时差 R(i

38、,j)R(i,j)=tls(i,j)-tes(i,j)=tlf(i,j)-tef(i,j) 工序单时差工序单时差 r(i,j)r(i,j)=te(j)-tef(i,j)=(te(j)-te(i)-t(i,j)(2) 关键路线关键路线 网络图中的最长路线称为关键路线。关键路线上各事网络图中的最长路线称为关键路线。关键路线上各事项的松弛时间和各工序总时差都等于终点事项的松弛项的松弛时间和各工序总时差都等于终点事项的松弛时间。时间。(一般为零一般为零)Zxf.sme.bit（3）网络网络时间与关键路线的时间与关键路线的MATLAB程序程序 T_Event, T_Activity, KeyRoute,

39、 ProjectTime = ProcessNetworkDiagram_CPM(AMatrix) 函数的输入参数：有向网络图的赋权邻接矩阵AMatrix； 输出参数： 事项矩阵T_Event（包括事项的编号、最早最迟时间、松弛时间及是否关键事项等时间结果）、 工序矩阵T_Activity（工序编号、工序起止事项、最早开始和结束时间、最迟开始和结束时间、总时差及工序标识等）、 按照事项代号给出的关键线路的事项向量KeyRoute、 项目完工时间ProjectTime。Zxf.sme.bit例例6的网络时间计算的网络时间计算准备邻接矩阵A，调用函数ProcessNetworkDiagram_CP

40、M(A)A=0 60 Inf Inf Inf Inf Inf Inf; Inf 0 13 Inf 15 Inf Inf Inf; Inf Inf 0 38 Inf Inf Inf Inf; . Inf Inf Inf 0 0 16 10 Inf; Inf Inf Inf Inf 0 Inf 8 Inf; Inf Inf Inf Inf Inf 0 0 Inf; . Inf Inf Inf Inf Inf Inf 0 5; Inf Inf Inf Inf Inf Inf Inf 0;T_Event,T_Activity,KeyRoute,ProjectTime = ProcessNetworkD

41、iagram_CPM(A)Zxf.sme.bitT_Event = 1 0 0 0 1 2 60 60 0 1 3 73 73 0 1 4 111 111 0 1 5 111 119 8 0 6 127 127 0 1 7 127 127 0 1 8 132 132 0 1 No te tl SE Key （注：事项编号、最早时间、最迟时间、松弛时间、关键事项）T_Activity = 1 1 2 0 60 0 60 0 1 2 2 3 60 73 60 73 0 1 3 2 5 60 75 104 119 44 0 4 3 4 73 111 73 111 0 1 5 4 5 111 111

42、119 119 8 -1 6 4 6 111 127 111 127 0 1 7 4 7 111 121 117 127 6 0 8 5 7 111 119 119 127 8 0 9 6 7 127 127 127 127 0 -1 10 7 8 127 132 127 132 0 1 No i j tes tef tls tlf R flag 注：工序编号、工序事项、最早开始时间、最早结束时间、最迟开始时间、最迟结束时间、工序总时差、标识（1为关键工序，0为非关键工序，-1为虚工序）KeyRoute = 1 2 3 4 6 7 8ProjectTime = 132Zxf.sme.bit 例

43、例 7. 某公司装配一条新的生产线，其装配过程中的各个工某公司装配一条新的生产线，其装配过程中的各个工序与其所需时间以及它们之间的相互衔接关系如表所示，求：序与其所需时间以及它们之间的相互衔接关系如表所示，求：完成此工程所需最少时间，关键路线及相应关键工序，各工序完成此工程所需最少时间，关键路线及相应关键工序，各工序的最早开始时间和结束时间和非关键工序在不影响工程完成时的最早开始时间和结束时间和非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以推迟多久。间的前提下，其开始时间与结束时间可以推迟多久。Zxf.sme.bit工序代号工序代号工序内容工序内容所需时间所需时间(天天)紧前

44、工序紧前工序a生产线设计生产线设计60b外购零配件外购零配件45ac下料、锻件下料、锻件10ad工装制造工装制造 120ae木模、铸件木模、铸件40af机械加工机械加工 118cg工装制造工装制造 230dh机械加工机械加工 215d，ei机械加工机械加工 325gj装配调试装配调试35b, i, f, hZxf.sme.bit解：解：根据上表绘制网络图根据上表绘制网络图ab132456045e18c10d207f258h15g30图图 10635ij40Zxf.sme.bit准备邻接矩阵A，调用函数ProcessNetworkDiagram_CPM(A)A=0 60 Inf Inf Inf

45、Inf Inf Inf; Inf 0 10 20 40 Inf 45 Inf; Inf Inf 0 Inf Inf Inf 18 Inf; . Inf Inf Inf 0 0 30 Inf Inf; Inf Inf Inf Inf 0 Inf 15 Inf; Inf Inf Inf Inf Inf 0 25 Inf; . Inf Inf Inf Inf Inf Inf 0 35; Inf Inf Inf Inf Inf Inf Inf 0;T_Event,T_Activity,KeyRoute,ProjectTime = ProcessNetworkDiagram_CPM(A)Zxf.sme.

46、bitT_Event = 1 0 0 0 1 2 60 60 0 1 3 70 117 47 0 4 80 80 0 1 5 100 120 20 0 6 110 110 0 1 7 135 135 0 1 8 170 170 0 1T_Activity = 1 1 2 0 60 0 60 0 1 2 2 3 60 70 107 117 47 0 3 2 4 60 80 60 80 0 1 4 2 5 60 100 80 120 20 0 5 2 7 60 105 90 135 30 0 6 3 7 70 88 117 135 47 0 7 4 5 80 80 120 120 40 -1 8

47、4 6 80 110 80 110 0 1 9 5 7 100 115 120 135 20 0 10 6 7 110 135 110 135 0 1 11 7 8 135 170 135 170 0 1KeyRoute = 1 2 4 6 7 8ProjectTime = 170Zxf.sme.bit将各工序的时差，以及其他信息构成工序时间表。将各工序的时差，以及其他信息构成工序时间表。关键工关键工序的时差都为零序的时差都为零。工序工序tEStLStEFtLF时差时差是否关键工序是否关键工序a0060600是是b609010513530否否c601077011747否否d606080800是

48、是e608010012020否否f701178813547否否g80801101100是是h10012011513520否否i1101101351350是是j1351351701700是是Zxf.sme.bit3.4 工序时间不确定时的网络时间与关键工序时间不确定时的网络时间与关键路线路线（PERT）例例8. 某公司研制新产品项目的工序与所需时间以及它们之间的某公司研制新产品项目的工序与所需时间以及它们之间的相互关系如相互关系如表所表所示，画出其统筹方法的网络图示，画出其统筹方法的网络图，并，并进行各工序进行各工序时间及项目完工概率的计算时间及项目完工概率的计算。Zxf.sme.bit表表 新

49、产品研制项目各项工作清单（时间单位：天）新产品研制项目各项工作清单（时间单位：天） 工作代号紧前工作工作时间（a m b）工作代号紧前工作工作时间（a m b）A13 15 23FD、E22 25 34B14 16 24GE27 31 41C20 24 34HD15 18 27DA18 21 30IG30 34 44EA、B15 18 27JC、E17 21 31Zxf.sme.bit1）乐观时间乐观时间。是指在顺利情况下，完成活动所需最少时间，常用符号。是指在顺利情况下，完成活动所需最少时间，常用符号 a 表表示；示；2）最可能时间最可能时间。是指在正常情况下，完成活动所需时间，常用符号。是

50、指在正常情况下，完成活动所需时间，常用符号 m 表示；表示；3）悲观时间悲观时间。是指在不顺利的情况下，完成工序所需最多时间，常用符号。是指在不顺利的情况下，完成工序所需最多时间，常用符号 b 表示表示。 三三种完成活动所需时间都具有一定概率，根据经验，可以假定这些时间种完成活动所需时间都具有一定概率，根据经验，可以假定这些时间的概率分布的概率分布近似近似服从服从 分布。分布。解解：表中对每个活动有三种时间估计表中对每个活动有三种时间估计Zxf.sme.bit64bmaT226abZxf.sme.bit活动活动 g 的完成时间的概率分布如图的完成时间的概率分布如图 15。 27 31 41乐观

51、时间乐观时间最有可能时间最有可能时间平均时间平均时间悲观时间悲观时间0图图 11Zxf.sme.bit调用程序 Mu_Sigma，计算各工序的平均时间及标准差。 工序的平均时间为： 16 17 25 22 19 26 32 19 35 22 工序时间标准差为：1.67 1.67 2.33 2.0 2.0 2.0 2.33 2.0 2.33 2.33Zxf.sme.bit（1）先按平均工序时间进行关键路线的计算；（2）再考虑随机因素的影响。根据表中根据表中的工序关系及工序平均时间，可以绘制出统筹方法的网络图的工序关系及工序平均时间，可以绘制出统筹方法的网络图H19A 16B17D22I35E19

52、G32J 22C25 F26图图 12Zxf.sme.bit（1）基于基于平均工序时间的关键路线的处理平均工序时间的关键路线的处理准备邻接矩阵A，调用函数ProcessNetworkDiagram_CPM(A)A=0 16 17 25 Inf Inf Inf Inf Inf; Inf 0 0 Inf Inf 22 Inf Inf Inf; Inf Inf 0 19 Inf Inf Inf Inf Inf; . Inf Inf Inf 0 0 Inf 0 32 Inf; Inf Inf Inf Inf 0 Inf Inf Inf 22; Inf Inf Inf Inf Inf 0 0 Inf 1

53、9; . Inf Inf Inf Inf Inf Inf 0 Inf 26; Inf Inf Inf Inf Inf Inf Inf 0 35; Inf Inf Inf Inf Inf Inf Inf Inf 0;T_Event,T_Activity,KeyRoute,ProjectTime = ProcessNetworkDiagram_CPM(A)Zxf.sme.bit输出结果：T_Event = 1 0 0 0 1 2 16 17 1 0 3 17 17 0 1 4 36 36 0 1 5 36 81 45 0 6 38 77 39 0 7 38 77 39 0 8 68 68 0 1

54、9 103 103 0 1 No te tl SE Key （注：事项编号、最早时间、最迟时间、松弛时间、关键事项） Zxf.sme.bitT_Activity = 1 1 2 0 16 1 17 1 0 2 1 3 0 17 0 17 0 1 3 1 4 0 25 11 36 11 0 4 2 3 16 16 17 17 1 -1 5 2 6 16 38 55 77 39 0 6 3 4 17 36 17 36 0 1 7 4 5 36 36 81 81 45 -1 8 4 7 36 36 77 77 41 -1 9 4 8 36 68 36 68 0 1 10 5 9 36 58 81 1

55、03 45 0 11 6 7 38 38 77 77 39 -1 12 6 9 38 57 84 103 46 0 13 7 9 38 64 77 103 39 0 14 8 9 68 103 68 103 0 1 No i j tes tef tls tlf R flag 注：工序编号、工序事项、最早开始时间、最早结束时间、最迟开始时间、最迟结束时间、工序总时差、标识（1为关键工序，0为非关键工序，-1为虚工序） KeyRoute = 1 3 4 8 9ProjectTime = 103Zxf.sme.bitZxf.sme.bit计算在不同完工时间SD的概率： P(T SD) = normc

56、df(SD,)例如，P(T 103) = normcdf(103,103,4.2) = 0.5， P(T 108) = normcdf(108,103,4.2) = 0.68。103 10817.65E(T)103图图 18Zxf.sme.bit（3）计算计算项目规定完成概率下的完工时间项目规定完成概率下的完工时间利用正态分布函数的反函数，就可以计算项目在规定完成概率P下的完工时间T： T = norminv(P,)例如，T(P=0.6) = norminv(0.6,103,4.2) = 104， T(P = 0.95) = norminv(0.95,103,4.2) = 110。Zxf.sm

57、e.bit3.5 网络优化网络优化 绘制网络图、计算网络时间和确定关键路线，得到了一个初始的计划绘制网络图、计算网络时间和确定关键路线，得到了一个初始的计划方案，但通常要对初始方案进行调整与完善。根据计划目标，综合地考虑方案，但通常要对初始方案进行调整与完善。根据计划目标，综合地考虑进度、资源和降低成本等目标，进行网络优化，确定最优的计划方案。进度、资源和降低成本等目标，进行网络优化，确定最优的计划方案。1）时间资源优化时间资源优化 在编制网络计划安排工程进度时，要合理地利用现有资源，并缩短工在编制网络计划安排工程进度时，要合理地利用现有资源，并缩短工程周期。为了使工程进度与资源程周期。为了使工程进度与资源Zxf.sme.bit利用都得到比较合理安排，采用以下做法：利用都得到比较合理安排，采用以下做