第5章图与网络模型.ppt

管管 理理 运运 筹筹 学学1 第五章　图与网络模型第五章　图与网络模型§§1 1　图与网络的基本概念　图与网络的基本概念§§2 2　最短路问题　最短路问题§§3 3　最小生成树问题　最小生成树问题§§4 4　最大流问题　最大流问题§§5 5　车间作业计划　车间作业计划§§6 6　统筹法（网络规划）　统筹法（网络规划）管管 理理 运运 筹筹 学学 图图论论是是专专门门研研究究图图的的理理论论的的一一门门数数学学分分支支，，属属于于离离散散数数学学范范畴畴，，与与运运筹筹学学有有交交叉叉，，它它有有200多多年年历历史史，，大大体体可可划划分分为为三三个个阶阶段段：：第第一一阶阶段段是是从从十十八八世世纪纪中中叶叶到到十十九九世世纪纪中中叶叶，，处处于于萌萌芽芽阶阶段段，，多多数数问问题题为为游游戏戏而而产产生生，，最最有有代代表表性性的的工工作作是是所所谓谓的的Euler七七桥桥问问题题(1736年年)，，即即一一笔笔画画问题管管 理理 运运 筹筹 学学第第二二阶阶段段是是从从十十九九世世纪纪中中叶叶到到二二十十世世纪纪中中叶叶，，这这时时，，图图论论问问题题大大量量出出现现，，如如Hamilton问问题题，，地地图图染染色色的的四四色色问问题题以以及及可可平平面面性性问问题题等等，，这这时时，，也也出出现现用用图图解解决决实实际际问问题题，，如如Cayley把把树树应应用用于于化化学学领领域域，，Kirchhoff用用树树去去研研究究电电网络等网络等.管管 理理 运运 筹筹 学学第第三三阶阶段段是是二二十十世世纪纪中中叶叶以以后后，，由由生生产产管管理理、、军军事事、、交交通通、、运运输输、、计计算算机机网网络络等等方方面面提提出出实实际际问问题题，，以以及及大大型型计计算算机机使使大大规规模模问问题题的的求求解解成成 为为 可可 能能 ，， 特特 别别 是是 以以 Ford和和Fulkerson建建立立的的网网络络流流理理论论，，与与线线性性规规划划、、动动态态规规划划等等优优化化理理论论和和方方法法相相互互渗渗透透，，促促进进了了图图论论对对实实际际问题的应用。

问题的应用管管 理理 运运 筹筹 学学例例10-1：：哥尼斯堡七桥问题哥尼斯堡七桥问题 哥哥尼尼斯斯堡堡（（现现名名加加里里宁宁格格勒勒））是是欧欧洲洲一一个个城城市市，，Pregei河河把把该该城城分分成成两两部部分分，，河河中中有有两两个个小小岛岛，，十十八八世世纪纪时时，，河河两两边边及及小小岛岛之之间间共共有有七七座座桥桥，，当当时时人人们们提提出出这这样样的的问问题题：：有有没没有有办办法法从从某某处处（（如如A））出出发发，，经经过过各各桥桥一一次次且且仅仅一一次次最最后后回回到到原原地呢？地呢？管管 理理 运运 筹筹 学学ABCD管管 理理 运运 筹筹 学学 最最后后，，数数学学家家Euler在在1736年年巧巧妙妙地地给给出出了了这这个个问问题题的的答答案案，，并并因因此此奠奠定定了了图图论论的的基基础础，，Euler把把A、、B、、C、、D四四块块陆陆地地分分别别收收缩缩成成四四个个顶顶点点，，把把桥桥表表示示成成连连接接对对应应顶顶点点之之间间的的边边，，问问题题转转化化为为从从任任意意一一点点出出发发，，能能不不能能经经过过各各边边一一次次且且仅仅一一次次，，最最后后返返回回该该点点。

这这就就是是著著名名的的Euler问题管管 理理 运运 筹筹 学学ACBD管管 理理 运运 筹筹 学学有有7个个人人围围桌桌而而坐坐，，如如果果要要求求每每次次相相邻邻的的人人都都与与以以前前完完全全不不同同，，试试问不同的就座方案共有多少种？问不同的就座方案共有多少种？ 用用顶顶点点表表示示人人，，用用边边表表示示两两者者相相邻邻，，因因为为最最初初任任何何两两个个人人都都允允许许相相邻邻，，所所以以任任何何两两点点都都可可以以有边相连有边相连管管 理理 运运 筹筹 学学1 12 23 37 76 64 45 5管管 理理 运运 筹筹 学学假定第一次就座方案是假定第一次就座方案是（（1，，2，，3，，4，，5，，6，，7，，1）），，那那么么第第二二次次就就座座方方案案就就不不允允许许这这些些顶顶点点之之间间继继续续相相邻邻，，只只能能从从图图中删去这些边中删去这些边管管 理理 运运 筹筹 学学1 12 23 37 76 64 45 5管管 理理 运运 筹筹 学学1 12 23 37 76 64 45 5管管 理理 运运 筹筹 学学假定第二次就座方案是假定第二次就座方案是（（1，，3，，5，，7，，2，，4，，6，，1）），，那那么么第第三三次次就就座座方方案案就就不不允允许许这这些些顶顶点点之之间间继继续续相相邻邻，，只只能能从图中删去这些边。

从图中删去这些边管管 理理 运运 筹筹 学学1 12 23 37 76 64 45 5管管 理理 运运 筹筹 学学1 12 23 37 76 64 45 5管管 理理 运运 筹筹 学学假定第三次就座方案是假定第三次就座方案是（（1，，4，，7，，3，，6，，2，，5，，1）），，那那么么第第四四次次就就座座方方案案就就不不允允许许这这些些顶顶点点之之间间继继续续相相邻邻，，只只能能从从图图中中删删去去这这些些边边，，只只留留下下7点点孤孤立立点点，，所所以以该该问问题题只只有有三三个个就就座座方方案管管 理理 运运 筹筹 学学1 12 23 37 76 64 45 5管管 理理 运运 筹筹 学学1 12 23 37 76 64 45 5管管 理理 运运 筹筹 学学哈哈密密顿顿（（Hamilton））回回路路是是十十九九世世纪纪英英国国数数学学家家哈哈密密顿顿提提出出，，给给出出一一个个正正12面面体体图图形形，，共共有有20个个顶顶点点表表示示20个个城城市市，，要要求求从从某某个个城城市市出出发发沿沿着着棱棱线线寻寻找找一一条条经经过过每每个个城城市市一一次次而而且且仅仅一一次次，，最最后后回回到到原原处处的的周周游游世世界界线线路路（（并并不不要求经过每条边）。

要求经过每条边）管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学22§§1 1　图与网络的基本概念　图与网络的基本概念 图论中图是由点和边构成，可以反映一些对象之间的关系图论中图是由点和边构成，可以反映一些对象之间的关系 例如：在一个人群中，对相互认识这个关系我们可以用图来例如：在一个人群中，对相互认识这个关系我们可以用图来表示，下图就是一个表示这种关系的图表示，下图就是一个表示这种关系的图v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈e2e1e3e4e5管管 理理 运运 筹筹 学学23 §§1 1　图与网络的基本概念　图与网络的基本概念 当然图论不仅仅是要描述对象之间关系，还要研究特定关当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以表示如下，可见的，如对赵等七人的相互认识关系我们也可以表示如下，可见图论中的图与几何图、工程图是不一样的。

图论中的图与几何图、工程图是不一样的v1)赵赵(v2)钱钱孙孙(v3) 李李(v4)周周(v5)吴吴(v6)陈陈(v7)e2e1e3e4e5管管 理理 运运 筹筹 学学24§§1 1　图与网络的基本概念　图与网络的基本概念a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈 如果我们把上面例子中的如果我们把上面例子中的“相互认识相互认识”关系改为关系改为“认识认识” 的关系，那么只用两点之间的联线就很难刻画他们之间的的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这时我们引入一个带箭头的联线，称为弧下图就关系了，这时我们引入一个带箭头的联线，称为弧下图就是一个反映这七人是一个反映这七人“认识认识”关系的图相互认识用两条反向关系的图相互认识用两条反向的弧表示的弧表示管管 理理 运运 筹筹 学学25 §§1 1　图与网络的基本概念　图与网络的基本概念§无向图：无向图： 由点和边构成的图，记作由点和边构成的图，记作G=（（V，，E）。

•有向图：有向图： 由点和弧构成的图，记作由点和弧构成的图，记作D=（（V，，A）•连通图连通图：： 对无向图对无向图G，若任何两个不同的点之间，至少存在一条链，则，若任何两个不同的点之间，至少存在一条链，则G为为连通图•回路：回路： 若路的第一个点和最后一个点相同，则该路为回路若路的第一个点和最后一个点相同，则该路为回路•赋权图：赋权图： 对一个无向图对一个无向图G的每一条边的每一条边(vi,vj)，相应地有一个数，相应地有一个数wij，则称图，则称图G为赋权图，为赋权图，wij称为边称为边(vi,vj)上的权•网络：网络： 在赋权的有向图在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，中的每一条弧的赋权数称为弧的容量，D就就称为网络称为网络管管 理理 运运 筹筹 学学26§§2 2　最短路问题　最短路问题•最短路问题：对一个赋权的有向图最短路问题：对一个赋权的有向图D中的指定的两个点中的指定的两个点Vs和和Vt找到一条找到一条从从 Vs 到到 Vt 的路，使得这条路上所有弧的权数的总和最小，这条路被称的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从之为从Vs到到Vt的最短路。

这条路上所有弧的权数的总和被称为从的最短路这条路上所有弧的权数的总和被称为从Vs到到Vt的距离解最短路的解最短路的Dijkstra算法算法(双标号法）双标号法）步骤：步骤：1.给出点给出点V1以标号以标号(0,s)2.找出已标号的点的集合找出已标号的点的集合I，没标号的点的集合，没标号的点的集合J以及弧的集合以及弧的集合3. 如果上述弧的集合是空集，则计算结束如果如果上述弧的集合是空集，则计算结束如果vt已标号（已标号（lt,kt），则），则 vs到到vt的距离为的距离为lt，而从，而从 vs到到vt的最短路径，则可以从的最短路径，则可以从kt 反向追踪到起点反向追踪到起点vs 而得到如果而得到如果vt 未标号，则可以断言不存在从未标号，则可以断言不存在从 vs到到vt的有向路如果上的有向路如果上述的弧的集合不是空集，则转下一步述的弧的集合不是空集，则转下一步4. 对上述弧的集合中的每一条弧，计算对上述弧的集合中的每一条弧，计算 sij=li+cij 在所有的在所有的 sij中，找到其中，找到其值为最小的弧不妨设此弧为（值为最小的弧不妨设此弧为（Vc,Vd），则给此弧的终点以双标号），则给此弧的终点以双标号（（scd,c））,返回步骤返回步骤2。

管管 理理 运运 筹筹 学学 最短路问题是网络分析中的一个基本问题，它不仅可以直接应用最短路问题是网络分析中的一个基本问题，它不仅可以直接应用于于解决生产实际的许多问题，若管道铺设、线路安排、厂区布局于于解决生产实际的许多问题，若管道铺设、线路安排、厂区布局等，而且经常被作为一个基本工具，用于解决其它的优化问题等，而且经常被作为一个基本工具，用于解决其它的优化问题.定义 给定一个赋权有向图D = (V,A)，记D中每一条弧 上的权为为 给定D中一个起点 和 终点，设P是D中从 到 的一条路.则定义路P的权是P中所有弧的权之和.记为 ，即 又若P*是D图中 到 的一条路，且满足 则称P*为从 到 的最短路管管 理理 运运 筹筹 学学28最短路问题最短路问题 网络：网络：规定起点、中间点和终点的赋权图；有向网络：有向网络：网络中每个边都是有向边；无向网络：无向网络：网络中每个边都是无向边；混合网络：混合网络：网络中既有有向边，又有无向边；网络最短路线问题：网络最短路线问题：寻找网络中从起点 v1 到终点 vn 的最短路线。

Min L() =  lij 为从 v1 到 vn 的通路； lij 其中， lij为从 vi 到 vj 的一步距离管管 理理 运运 筹筹 学学29•结合例题学习、掌握求最短路的狄克斯拉、海斯和福德三个方法： 1、狄克斯拉方法：适用于满足所有权系数大于等于0（lij≥0）的网络最短路问题，能求出起点 v1 到所有其它点 vj 的最短距离； 2、海斯方法：基本思想是在最短路线上任意两点间路线也是最短路线利用 vi 到 vj 的一步距离求出 vi 到 vj 的两步距离再求出 vi 到 vj 的四步距离……经有限次迭代可求出 vi 到 vj 的最短距离； 3、福德方法：适用于有负权系数，但无负回路的有向或无向网络的最短路问题，能求出起点 v1 到所有其它点 vj 的最短距离 管管 理理 运运 筹筹 学学30§§2 2　最短路问题　最短路问题 例例1 求下图中求下图中v1到到v6的最短路的最短路解：采用解：采用Dijkstra算法，可解得最短路径为算法，可解得最短路径为v1 v3 v4 v6 各点的标号图如下：各点的标号图如下：v23527531512v1v6v5v3v4(3,1)v23527531512 V1（（0,s)v5(8,4)v6(2,1)v3(3,3)v4管管 理理 运运 筹筹 学学31 网络最短路线问题：网络最短路线问题：寻找网络中从起点 v1 到终点 vn 的最短路线。

标注 vk(lk，k-1) 定义：k=1时，l1=0，k-1=s，v1(0，s） min( lij )Min L() =  lij 为从 v1 到 vn 的通路； lij 其中， lij为从 vi 到 vj 的一步距离最短路问题最短路问题管管 理理 运运 筹筹 学学32§§2 2　最短路问题　最短路问题 例例2 电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图权数表示两地使其光缆线路最短？下图给出了甲乙两地间的交通图权数表示两地间公路的长度（单位：公里）间公路的长度（单位：公里） 解：这是一个求无向图的最短路的问题可以把无向图的每一边解：这是一个求无向图的最短路的问题可以把无向图的每一边（（vi,vj）都用方向相反的两条弧（）都用方向相反的两条弧（vi,vj）和（）和（vj,vi）代替，就化为有向）代替，就化为有向图，即可用图，即可用Dijkstra算法来求解。

也可直接在无向图中用算法来求解也可直接在无向图中用Dijkstra算法算法来求解只要在算法中把从已标号的点到未标号的点的弧的集合改成来求解只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可已标号的点到未标号的点的边的集合即可 V1 （甲地）（甲地）1517624431065v2V7 （乙地）（乙地）v3v4v5v6管管 理理 运运 筹筹 学学33§§2 2　最短路问题　最短路问题例例2最终解得：最终解得：最短路径最短路径v1 v3 v5 v6 v7，每点的标号见下图，每点的标号见下图（（0,s）） V1 （甲地）（甲地）1517624431065(13,3) v2 (22,6)V7 （乙地）（乙地）V5(14,3)V6(16,5) V3(10,1) V4(18,5)管管 理理 运运 筹筹 学学例设备更新问题设备更新问题某工厂使用一台设备，每年年初工厂要作出决定：继续使用，购某工厂使用一台设备，每年年初工厂要作出决定：继续使用，购买新的？如果继续使用旧的，要负维修费；若要购买一套新的，要买新的？如果继续使用旧的，要负维修费；若要购买一套新的，要负购买费。

试确定一个负购买费试确定一个5年计划，使总支出最小若已知设备在各年计划，使总支出最小若已知设备在各年的购买费，及不同机器役龄时的残值与维修费年的购买费，及不同机器役龄时的残值与维修费项目第1年第2年第3年第4年第5年购买费1111121213机器役龄0-11-22-33-44-5维修费5681118残值43210解：解：把把这个个问题化化为最短路最短路问题 设设bi 表示设备在第表示设备在第i 年年初的购买费年年初的购买费, ,ci 表示设备使用表示设备使用i 年后的维修费年后的维修费, , V={ {v1, v2, … , v6},},点点vi表示第表示第i 年年初购进一台新设备年年初购进一台新设备, ,虚设一个点虚设一个点v6表示第表示第5 5年年年底年底. . E ={ {vivj | 1≤i＜＜j≤6}.}. §§2 2　最短路问题　最短路问题管管 理理 运运 筹筹 学学35§§2 2　最短路问题　最短路问题例的解：例的解： 将问题转化为最短路问题，如下图：将问题转化为最短路问题，如下图： 用用vi表示表示“第第i年年初购进一台新设备年年初购进一台新设备”,弧弧 （（vi,vj）表示第）表示第i年年初购年年初购进的设备一直使用到第进的设备一直使用到第j年年初。

年年初把所有弧的权数计算如下表：把所有弧的权数计算如下表：v1v2v3v4v5v6123456116223041592162230413172331417235186管管 理理 运运 筹筹 学学 若每年购置一台新设备，则购置费为：若每年购置一台新设备，则购置费为：11+11+12+12+13=5911+11+12+12+13=59，每年的维修费为，每年的维修费为5 5元，元，共共59+5*5=84.59+5*5=84. 若在若在1，，2，，3年购置一台新设备，则购置费为：年购置一台新设备，则购置费为：11+12+13=36，每年的维修费为（，每年的维修费为（5+6））+（（5+6））+5=27，共，共36+27=63. 设备使用一年后就更新则不划算设备使用一年后就更新则不划算由表知，设备使用三年后应当更新由表知，设备使用三年后应当更新管管 理理 运运 筹筹 学学 这样上述设备更新问题就变为：在有向赋权图这样上述设备更新问题就变为：在有向赋权图G = (V, E, F )(图解如下图解如下) )中求中求v1到到v6的最短路问题的最短路问题. 管管 理理 运运 筹筹 学学 由实际问题可知由实际问题可知, ,设备使用三年后应当更新设备使用三年后应当更新, ,因此删除该图中因此删除该图中v1到到v5 , ,v1到到v6 , ,v2到到v6的连线；又的连线；又设备使用一年后就更新则不划算设备使用一年后就更新则不划算, ,因此再删除该因此再删除该图中图中v1v2 , ,v2v3 , ,v3v4 , ,v4v5 , ,v5v6 五条连线后得到五条连线后得到从上图中容易得到从上图中容易得到v1到到v6只有两条路：只有两条路：v1v3v6（费用（费用22+3122+31））和和v1v4v6 （费用（费用22+31））. . 而这两条路都是而这两条路都是v1到到v6的最短路的最短路. .管管 理理 运运 筹筹 学学39§§3 3　最小生成树问题　最小生成树问题•树是图论中的重要概念，所谓树就是一个无圈的连通图。

树是图论中的重要概念，所谓树就是一个无圈的连通图 图中，图中，(a)就是一个树，而就是一个树，而(b)因为图中有圈所以就不是树，因为图中有圈所以就不是树， (c)因为不连通所以也不是树因为不连通所以也不是树v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)管管 理理 运运 筹筹 学学40§§3 3　最小生成树问题　最小生成树问题 给了一个无向图给了一个无向图G=(V,E)G=(V,E)，我们保留，我们保留G G的所有点，而删掉部分的所有点，而删掉部分G G的边或的边或者说保留一部分者说保留一部分G G的边，所获得的图的边，所获得的图G G，称之为，称之为G G的生成子图在图中，的生成子图在图中，(b)(b)和和(c)(c)都是都是(a)(a)的生成子图的生成子图 如果图如果图G G的一个生成子图还是一个树，则称这个生成子图为生成树，的一个生成子图还是一个树，则称这个生成子图为生成树，在图中，在图中，(c)(c)就是就是(a)(a)的生成树的生成树。

最小生成树问题就是指在一个赋权的连通的无向图最小生成树问题就是指在一个赋权的连通的无向图G G中找出一个生成中找出一个生成树，并使得这个生成树的所有边的权数之和为最小树，并使得这个生成树的所有边的权数之和为最小a)(b)(c)管管 理理 运运 筹筹 学学41§§3 3　最小生成树问题　最小生成树问题求解最小生成树的破圈算法求解最小生成树的破圈算法算法的步骤：算法的步骤：1、在给定的赋权的连通图上任找一个圈在给定的赋权的连通图上任找一个圈2、在所找的圈中去掉一个权数最大的边（如果有两条或两条、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）以上的边都是权数最大的边，则任意去掉其中一条）3、如果所余下的图已不包含圈，则计算结束，所余下的图即、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第为最小生成树，否则返回第1步管管 理理 运运 筹筹 学学42§§3 3　最小生成树问题　最小生成树问题例例 用破圈算法求图（用破圈算法求图（a）中的一个最小生成树）中的一个最小生成树v1331728541034v7v6v5v4v2v13317285434v7v6v5v4v2v133725434v7v6v5v4v2v3v3v31v13372434v7v6v5v4v2v31v1337234v7v6v5v4v2v31v133723v7v6v5v4v2v31(a)(b)(c)(d)(e)(f)管管 理理 运运 筹筹 学学43§§3 3　最小生成树问题　最小生成树问题 例、某大学准备对其所属的例、某大学准备对其所属的7个学院办公室计算机联网，这个网络的可个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中能联通的途径如下图，图中v1,…,v7 表示表示7个学院办公室，请设计一个个学院办公室，请设计一个网络能联通网络能联通7个学院办公室，并使总的线路长度为最短。

个学院办公室，并使总的线路长度为最短 解：此问题实际上是求最小生成树，这在例中已经求得，也即按照解：此问题实际上是求最小生成树，这在例中已经求得，也即按照图的图的(f)(f)设计，可使此网络的总的线路长度为最短，为设计，可使此网络的总的线路长度为最短，为1919百米 ““管理运筹学软件管理运筹学软件””有专门的子程序可以解决最小生成树问题有专门的子程序可以解决最小生成树问题v1331728541034v7v6v5v4v2v3管管 理理 运运 筹筹 学学44§§4 4　最大流问题　最大流问题•最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量在不超过每条弧的容量的前提下，求出从发点到收点的最大流量最大流的数学模型最大流的数学模型 例例6 某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示由于管道的直径的送到一些销售点，这个网络的一部分如下图所示。

由于管道的直径的变化，它的各段管道（变化，它的各段管道（vi,vj）的流量）的流量cij（容量）也是不一样的容量）也是不一样的cij的单的单位为万加仑位为万加仑/小时如果使用这个网络系统从采地小时如果使用这个网络系统从采地 v1向销地向销地 v7运送石油，运送石油，问每小时能运送多少加仑石油？问每小时能运送多少加仑石油？v563522241263v1v2v7v4v3v6管管 理理 运运 筹筹 学学45§§4 4　最大流问题　最大流问题 我们可以为此例题建立线性规划数学模型：我们可以为此例题建立线性规划数学模型： 设弧设弧(vi,vj)上流量为上流量为fij，网络上的总的流量为，网络上的总的流量为F，则有：，则有：管管 理理 运运 筹筹 学学46§§4 4　最大流问题　最大流问题 在这个线性规划模型中，其约束条件中的前在这个线性规划模型中，其约束条件中的前6 6个方程表示个方程表示了网络中的流量必须满足守恒条件，发点的流出量必须等于了网络中的流量必须满足守恒条件，发点的流出量必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必收点的总流入量；其余的点称之为中间点，它的总流入量必须等于总流出量。

其后面几个约束条件表示对每一条弧须等于总流出量其后面几个约束条件表示对每一条弧(v(vi i,v,vj j) )的流量的流量fij要满足流量的可行条件，应小于等于弧要满足流量的可行条件，应小于等于弧(v(vi i,v,vj j) )的容量的容量c cijij，并大于等于零，即，并大于等于零，即0 0≤≤f fijij≤ ≤ c cijij我们把满我们把满足守恒条件及流量可行条件的一组网络流足守恒条件及流量可行条件的一组网络流 {f{fijij} }称之为可行流，称之为可行流，（即线性规划的可行解），可行流中一组流量最大（也即发（即线性规划的可行解），可行流中一组流量最大（也即发出点总流出量最大）的称之为最大流（即线性规划的最优解）出点总流出量最大）的称之为最大流（即线性规划的最优解） 我们把例我们把例6 6的数据代入以上线性规划模型，用的数据代入以上线性规划模型，用““管理运筹管理运筹学软件学软件””，马上得到以下的结果：，马上得到以下的结果：f f1212=5=5，，f f1414=5=5，，f f2323=2=2，，f f2525=3=3，，f f4343=2=2，，f f4646=1=1，，f f4747=2=2，，f f3535=2=2，，f f3636=2=2，，f f5757=5=5，，f f6767=3=3。

最优值最优值（最大流量）（最大流量）=10=10管管 理理 运运 筹筹 学学47 §§5 5　车间作业计划模型　车间作业计划模型一、一台机器、一、一台机器、n n个零件的排序问题个零件的排序问题 例例1.某车间只有一台高精度的磨床，常常出现很多零件同时要求这台某车间只有一台高精度的磨床，常常出现很多零件同时要求这台磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需时间磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需时间如下表所示如下表所示 应该按照什么样的加工顺序来加工这六个零件，才能使得这六个零应该按照什么样的加工顺序来加工这六个零件，才能使得这六个零件在车间里停留的平均时间为最少？件在车间里停留的平均时间为最少？零件零件加工时间加工时间（小时）（小时）零件零件加工时间加工时间（小时）（小时）1231.82.00.54560.91.31.5管管 理理 运运 筹筹 学学48 §§5 5　车间作业计划模型　车间作业计划模型 例例1解：如果我们用解：如果我们用Pi表示安排在第表示安排在第i位加工的零件所需的时间，用位加工的零件所需的时间，用Tj表示安排表示安排在第在第j位加工的零件在车间里总的停留时间，则有位加工的零件在车间里总的停留时间，则有 Tj = P1 + P2 +…+ Pj-1 + Pj = 不同的加工顺序得到不同的各零件的平均停留时间，如何得到一个使得各零件不同的加工顺序得到不同的各零件的平均停留时间，如何得到一个使得各零件的平均停留时间最少的排序呢？这就是我们最后要解决的优化问题，而且我们要设的平均停留时间最少的排序呢？这就是我们最后要解决的优化问题，而且我们要设法找到一种简便的算法。

法找到一种简便的算法 对于某种加工顺序，我们知道安排在第对于某种加工顺序，我们知道安排在第j位加工的零件在车间里总的停留时间为位加工的零件在车间里总的停留时间为Tj ，， Tj = 可知这六个零件的停留时间为：可知这六个零件的停留时间为： T1 + T2 + T3 + T4 + T5 + T6 ＝＝ P1 + ( P1 + P2 ) + (P1 + P2 + P3 ) + (P1 + P2 + P3 + P4 ) + (P1 + P2 + P3 + P4 + P5) + (P1 + P2 + P3 + P4 + P5 + P6 ) ＝＝ 6 P1 + 5 P2 + 4P3 + 3P4 + 2P5 + P6. 那么各个零件平均停留时间为那么各个零件平均停留时间为 从上式可知，对于一台机器从上式可知，对于一台机器n个零件的排序问题，只要系数越大，配上加工时个零件的排序问题，只要系数越大，配上加工时间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，加工间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，加工时间越多的零件排在越后面，可使各个零件的平均停留时间为最少。

时间越多的零件排在越后面，可使各个零件的平均停留时间为最少管管 理理 运运 筹筹 学学49 §§5 5　车间作业计划模型　车间作业计划模型二、两台机器、二、两台机器、n n个零件个零件 例例2.某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在磨床上加工，每台机器上各零件加工时间如表磨床上加工，每台机器上各零件加工时间如表12-5所示表表-1 应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间为应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间为最少？最少？ 解：由于每个零件必须先进行车床加工，再进行磨床加工，所以在车床上加解：由于每个零件必须先进行车床加工，再进行磨床加工，所以在车床上加工零件的顺序与在磨床上加工零件的顺序是一样的工零件的顺序与在磨床上加工零件的顺序是一样的 如果这些零件在车床上和磨床上加工顺序都为如果这些零件在车床上和磨床上加工顺序都为1，，2，，3，，4，，5我们用图我们用图12-1中的线条图来表示各零件加工的开始时间与完成时间，这种图是由一根时间轴和中的线条图来表示各零件加工的开始时间与完成时间，这种图是由一根时间轴和车床、磨床在每个时间段的状况的图形所构成。

车床、磨床在每个时间段的状况的图形所构成零件零件车床车床磨床磨床零件零件车床车床磨床磨床1231.52.01.00.50.251.75451.250.752.51.25管管 理理 运运 筹筹 学学50 §§5 5　车间作业计划模型　车间作业计划模型 图图 1 从上图中我们可以看出，加工时间的延长主要是由于磨床的停工待料从上图中我们可以看出，加工时间的延长主要是由于磨床的停工待料造成的，只要减少磨床的停工待料的时间就能减少整个加工任务的总时间造成的，只要减少磨床的停工待料的时间就能减少整个加工任务的总时间为了减少磨床的停工待料，我们应该一方面把在车床上加工时间越短的零为了减少磨床的停工待料，我们应该一方面把在车床上加工时间越短的零件越早加工，减少磨床等待的时间；另一方面把在磨床上加工时间越长的件越早加工，减少磨床等待的时间；另一方面把在磨床上加工时间越长的零件越晚加工，以便充分利用前面的时间，这样我们就得到了使完成全部零件越晚加工，以便充分利用前面的时间，这样我们就得到了使完成全部零件加工任务所需总时间最少的零件排序方法零件加工任务所需总时间最少的零件排序方法。

123451车床车床磨床磨床2345010管管 理理 运运 筹筹 学学51§§5 5　车间作业计划模型　车间作业计划模型 寻找例寻找例2的最优解：我们在表的最优解：我们在表12-5中找到所列出的最短加工时间是中找到所列出的最短加工时间是0.25,它是第二道工序磨床它是第二道工序磨床加工零件加工零件2的所需时间，由于这个时间与磨床有关，故我们把零件的所需时间，由于这个时间与磨床有关，故我们把零件2放在加工顺序的末尾，即第五放在加工顺序的末尾，即第五位，并在表中划去零件位，并在表中划去零件2 所在行如表所在行如表12-6中红色线条所示中红色线条所示 接着，我们又找到最短加工时间为接着，我们又找到最短加工时间为0.5，这一时间与磨床（第二工序）有关，我们把，这一时间与磨床（第二工序）有关，我们把 磨床加磨床加工时间为工时间为0.5的零件的零件1放到除第五外的加工顺序的末尾，即第四位加工，同时把放到除第五外的加工顺序的末尾，即第四位加工，同时把 表中的零件表中的零件1所在所在的行划去如表的行划去如表12-6中黄色线条所示中黄色线条所示。

下一个最短加工时间为下一个最短加工时间为0.75，这个加工时间是车床（第一工序）加工零件，这个加工时间是车床（第一工序）加工零件5的所需时间，故的所需时间，故把零件把零件5排在加工顺序的第一位上，同时把表中的零件排在加工顺序的第一位上，同时把表中的零件5所在的行划去如表所在的行划去如表12-6中蓝色线条所中蓝色线条所示零件零件车床车床（第一工序）（第一工序）磨床磨床（第二工序）（第二工序）零件零件车床车床（第一工序）（第一工序）磨床磨床（第二工序）（第二工序）1231.52.01.00.50.251.75451.250.752.51.25表表-2管管 理理 运运 筹筹 学学52 同样，下一个最短加工时间为同样，下一个最短加工时间为1，这是车床加工零件，这是车床加工零件3的所需时间，故的所需时间，故把零件把零件3排在第二位上，同时把零件排在第二位上，同时把零件3所在的行划去如表所在的行划去如表12-6中黑色线条中黑色线条所示 这样就得到了最优加工顺序：这样就得到了最优加工顺序：5，，3，，4，，1，，2一共只需一共只需7个小时就能个小时就能完成全部加工。

完成全部加工 从例从例2中我们可以归纳出关于两台机器中我们可以归纳出关于两台机器n个零件的排序问题，使得全部个零件的排序问题，使得全部任务总的时间任务总的时间 最短的排序算法最短的排序算法 在加工所需时间表上选出最短加工时间在加工所需时间表上选出最短加工时间tij，这是第，这是第i工序加工工序加工j零件所需零件所需时间，当时间，当i=1时，将零件时，将零件j的顺序尽量靠前，若的顺序尽量靠前，若i=2时，将零件时，将零件j的顺序的顺序尽量尽量靠后在表上划去零件靠后在表上划去零件j的所在行，回到步骤的所在行，回到步骤1 §§5 5　车间作业计划模型　车间作业计划模型管管 理理 运运 筹筹 学学基本基本概念概念•杜邦公司杜邦公司—关键路线法关键路线法CPM 确定型确定型•美国海军武器局美国海军武器局—计划评审技术计划评审技术PERT•网络图（有向赋权图）的构成网络图（有向赋权图）的构成•结点，也称事项，一道工序的开始或结束结点，也称事项，一道工序的开始或结束•工序（弧），相对独立的活动，消耗资源工序（弧），相对独立的活动，消耗资源•虚工序，只表示衔接关系，不消耗资源虚工序，只表示衔接关系，不消耗资源•工序时间（权），完成工序的时间消耗工序时间（权），完成工序的时间消耗§§6 6　统筹方法　统筹方法管管 理理 运运 筹筹 学学 网络规则•1 1、避免循环、不留缺口、避免循环、不留缺口、避免循环、不留缺口、避免循环、不留缺口•2 2、一一对应：一道工序用两个事项表示、一一对应：一道工序用两个事项表示、一一对应：一道工序用两个事项表示、一一对应：一道工序用两个事项表示•3 3 、从左向右依次展开、从左向右依次展开、从左向右依次展开、从左向右依次展开例：例：例：例：工 序ABCDEFGHI紧前工序----ABBC、DC、D E、FG工序时间466759748A,4B,6D,7E,5F,9H,4I,8C,6G,7管管 理理 运运 筹筹 学学关键路线法－－ CPM时间参数运算时间参数运算 什么是关键路线？什么是关键路线？1、作业时间、作业时间t（（i，，j），经验数据、统计数据），经验数据、统计数据2、事项最早时间、事项最早时间TE(j)＝＝max{TE(i)+ t（（i，，j））} 到到齐上上课，最后到者决定最早开，最后到者决定最早开课时间3、事、事项最最迟时间TL(i)＝＝min{TL(j)- t（（i，，j））} 保保证12点吃点吃饭，路最，路最远者决定最者决定最迟下下课时间4、工序最早可能开工、工序最早可能开工时间 TES(i,j)＝＝ TE(i) = max{TES(h,i)+ t（（h,i ））}5、工序最早可能完工、工序最早可能完工时间 TEF(i,j)＝＝TES(i,j)+ t（（i，，j））管管 理理 运运 筹筹 学学6 6 6 6、工序最迟必须开工时间、工序最迟必须开工时间、工序最迟必须开工时间、工序最迟必须开工时间 T T T TLSLSLSLS（（（（i,ji,ji,ji,j) ) ) )＝＝＝＝ T T T TL L L L(j)(j)(j)(j)－－－－ t t t t（（（（i,j)i,j)i,j)i,j)＝＝＝＝ min{Tmin{Tmin{Tmin{TLsLsLsLs(j,k)- t(j,k)- t(j,k)- t(j,k)- t（（（（i i i i，，，，j j j j））））} } } }7 7 7 7、工序最迟必须完工时间、工序最迟必须完工时间、工序最迟必须完工时间、工序最迟必须完工时间 T T T TLFLFLFLF（（（（i,j)i,j)i,j)i,j)＝＝＝＝ T T T TL L L L(j)(j)(j)(j)＝＝＝＝ T T T TLSLSLSLS（（（（i,j)+ ti,j)+ ti,j)+ ti,j)+ t（（（（i,j)i,j)i,j)i,j)8 8 8 8、工序总时差：在不影响其紧后工序、工序总时差：在不影响其紧后工序、工序总时差：在不影响其紧后工序、工序总时差：在不影响其紧后工序最迟必须最迟必须最迟必须最迟必须开工时开工时开工时开工时间的前提下，本工序可以推迟的时间间的前提下，本工序可以推迟的时间间的前提下，本工序可以推迟的时间间的前提下，本工序可以推迟的时间 R R R R（（（（i,ji,ji,ji,j）＝）＝）＝）＝ T T T TLSLSLSLS(i,j)(i,j)(i,j)(i,j)－－－－ T T T TESESESES(i,j) (i,j) (i,j) (i,j) ＝＝＝＝ T T T TLFLFLFLF(i,j)(i,j)(i,j)(i,j)－－－－ T T T TEFEFEFEF(i,j(i,j(i,j(i,j) ) ) ) ＝＝＝＝ min{Tmin{Tmin{Tmin{TLSLSLSLS(j,k) } (j,k) } (j,k) } (j,k) } – – T T T TEFEFEFEF（（（（i,ji,ji,ji,j））））9 9 9 9、工序单时差：在不影响其紧后工序、工序单时差：在不影响其紧后工序、工序单时差：在不影响其紧后工序、工序单时差：在不影响其紧后工序最早可能最早可能最早可能最早可能开工时开工时开工时开工时间的前提下，本工序可以推迟的时间间的前提下，本工序可以推迟的时间间的前提下，本工序可以推迟的时间间的前提下，本工序可以推迟的时间 r r r r （（（（i,ji,ji,ji,j）＝）＝）＝）＝ min{Tmin{Tmin{Tmin{TESESESES(j,k) } (j,k) } (j,k) } (j,k) } – – T T T TEFEFEFEF（（（（i,ji,ji,ji,j）））） 管管 理理 运运 筹筹 学学计算关系式•这些时间参数的关系可以用下图表示工作的关系状态。

管管 理理 运运 筹筹 学学时间参数图解.解上例：计算事项   时间参数     .解上例：计算事项   时间参数     TESTLSTEFTLFTESTLSTEFTLSr(i,j)R（i,j）A4B6C6G7D7E5F9H4I 80047613222028282024136关键路线：由总时差为零的工序构成 B D G It（i,j)t（j,k)管管 理理 运运 筹筹 学学• 解上例 计算工序时间参数 工序ijt(i,j) ESEFLSLFRrA4043730B6060600C641071333D761361300E561119241311F91322152420G71320132000H42226242822I82028202800管管 理理 运运 筹筹 学学60§§6 6　统筹方法　统筹方法 统筹方法包括绘制计划网络图、进度安排、网络优化等环节，下面进统筹方法包括绘制计划网络图、进度安排、网络优化等环节，下面进行分别讨论：行分别讨论：一、计划网络图一、计划网络图 统筹方法的第一步工作就是绘制计划网络图，也就是将工序（或称为统筹方法的第一步工作就是绘制计划网络图，也就是将工序（或称为活动）进度表转换为统筹方法的网络图。

活动）进度表转换为统筹方法的网络图 例例3、某公司研制新产品的部分工序与所需时间以及它们之间的相互、某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其工序进度表如表关系都显示在其工序进度表如表-3所示，请画出其统筹方法网络图所示，请画出其统筹方法网络图 表表-3工序代号工序代号工序内容工序内容所需时间（天所需时间（天)紧前工序紧前工序abcde产品设计与工艺设计产品设计与工艺设计外购配套零件外购配套零件外购生产原料外购生产原料自制主件自制主件主配可靠性试验主配可靠性试验601513388-aacb,d管管 理理 运运 筹筹 学学61§§6 6　统筹方法　统筹方法解解:用网络图表示上述的工序进度表用网络图表示上述的工序进度表 网络图中的点表示一个事件网络图中的点表示一个事件,是一个或若干个工序的开始或结束是一个或若干个工序的开始或结束,是相是相邻工序在时间上的分界点邻工序在时间上的分界点,点用圆圈表示点用圆圈表示,圆圈里的数字表示点的编号。

弧圆圈里的数字表示点的编号弧表示一个工序（或活动），弧的方向是从工序开始指向工序的结束，弧上表示一个工序（或活动），弧的方向是从工序开始指向工序的结束，弧上是各工序的代号，下面标以完成此工序所需的时间（或资源）等数据，即是各工序的代号，下面标以完成此工序所需的时间（或资源）等数据，即为对此弧所赋的权数．为对此弧所赋的权数． １２４５３abcde601383815图图-4管管 理理 运运 筹筹 学学62§§6 6　统筹方法　统筹方法 例４、把例３的工序进度表做一些扩充，如表例４、把例３的工序进度表做一些扩充，如表1-5，请画出其统筹方法，请画出其统筹方法的网络图的网络图 表表-5工序代号工序代号所需时间（天）所需时间（天）紧前工序紧前工序工序代号工序代号所需时间（天）所需时间（天）紧前工序紧前工序abcd60151338－－aacefgh810165b，ｄ，ｄdde，ｆ，ｇ，ｆ，ｇ管管 理理 运运 筹筹 学学63§§6 6　统筹方法　统筹方法 解：我们把工序解：我们把工序 e 扩充到图扩充到图5发生了问题，由于ｄ是发生了问题，由于ｄ是 e 的紧前工序，的紧前工序，故ｄ的结束应该是故ｄ的结束应该是 e 的开始，所以代表的开始，所以代表 e 的弧的起点应该是的弧的起点应该是④④，由于工，由于工序ｂ的结束也是序ｂ的结束也是④④，所以工序ｂ也成了工序，所以工序ｂ也成了工序 e 的紧前工序，与题意不的紧前工序，与题意不符。

符　　　　　　 为此我们设立虚工序虚工序是实际上并不存在而虚设的工序，用为此我们设立虚工序虚工序是实际上并不存在而虚设的工序，用来表示相邻工序的衔接关系，不需要人力、物力等资源与时间　来表示相邻工序的衔接关系，不需要人力、物力等资源与时间　　　　　 152643a60b158e1013dc38f图图-5管管 理理 运运 筹筹 学学64§§6 6　统筹方法　统筹方法 在网络图上添加ｇ、ｈ工序得网络图在网络图上添加ｇ、ｈ工序得网络图-6 　　　　　　在统筹方法的网络图中不允许两个点之间多于一条弧，因此增加在统筹方法的网络图中不允许两个点之间多于一条弧，因此增加了一个点和虚工序如图了一个点和虚工序如图-71256734a6015bec13d388h510fg16图图-6管管 理理 运运 筹筹 学学65§§6 6　统筹方法　统筹方法 在绘制统筹方法的网络图时，要注意图中不能有缺口和回路在绘制统筹方法的网络图时，要注意图中不能有缺口和回路。

1257834a6015bec13d388h510f616g图图12-7管管 理理 运运 筹筹 学学66§§6 6　统筹方法　统筹方法二、网络时间与关键路线二、网络时间与关键路线 在绘制出网络图之后，我们可以由网络图求出：在绘制出网络图之后，我们可以由网络图求出：1、完成此工程项目所需的最少时间完成此工程项目所需的最少时间2、每个工序的开始时间与结束时间每个工序的开始时间与结束时间3、关键路线及其应用的关键工序关键路线及其应用的关键工序4、非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时、非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时间可以推迟多久间可以推迟多久 例例5、某公司装配一条新的生产线，具体过程如表、某公司装配一条新的生产线，具体过程如表-10,求：完成此求：完成此工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间和工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间和非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以推迟多久。

推迟多久管管 理理 运运 筹筹 学学67§§6 6　统筹方法　统筹方法表表-10工序代号工序代号工序内容工序内容所需时间（天）所需时间（天）紧前工序紧前工序abcdefghij生产线设计生产线设计外购零配件外购零配件下料、锻件下料、锻件工装制造工装制造1木模、铸件木模、铸件机械加工机械加工1工装制造工装制造2机械加工机械加工2机械加工机械加工3装配调试装配调试60451020401830152535/aaaacdd,egb,i,f,h管管 理理 运运 筹筹 学学68§§6 6　统筹方法　统筹方法解：据表解：据表-10,绘制网络图如图绘制网络图如图-8 图图-8 如图如图-8 ,①①-②②-③③-⑦⑦-⑧⑧就是一条关键路线，我们要干完所有的工序就是一条关键路线，我们要干完所有的工序就必须走完所有这样的路线，由于很多工序可以同时进行，所以网络中最就必须走完所有这样的路线，由于很多工序可以同时进行，所以网络中最长的路线就决定了完成整个工程所需的最少时间，这条路线称为关键路长的路线就决定了完成整个工程所需的最少时间，这条路线称为关键路线。

线12346785a60b45echj35ig1030d204025f1815管管 理理 运运 筹筹 学学69§§6 6　统筹方法　统筹方法•下面我们给出找关键路线的办法下面我们给出找关键路线的办法 首先，从网络的发点开始，按顺序计算出每个工序的最早开始时间首先，从网络的发点开始，按顺序计算出每个工序的最早开始时间（（ES )和最早结束时间（和最早结束时间（EF) ，设一个工序所需的时间为，设一个工序所需的时间为t，这对于同一，这对于同一个工序来说，有个工序来说，有 EF=ES+t 工序工序a的最早的最早开始时间开始时间工序工序a的最早的最早完成时间完成时间11a[0，，60]60图图9管管 理理 运运 筹筹 学学70§§6 6　统筹方法　统筹方法 图图10 其次其次,从网络的收点开始计算出在不影响整个工程最早结束时间的情从网络的收点开始计算出在不影响整个工程最早结束时间的情况下各个工序的最晚开始时间况下各个工序的最晚开始时间(缩写为缩写为LS)和最晚结束时间（缩写为和最晚结束时间（缩写为LF),显然对同一工序有显然对同一工序有 LS=LF-t1236785a[0,60]60b[60,105]45e[60.100]c[60,70]h[100,115]j[135,170]35i[110.135]g[80,110]30d[60.80]204025f[70,88]1841015管管 理理 运运 筹筹 学学71§§6 6　统筹方法　统筹方法 运用此法则，可以从首点开始计算出每个工序的运用此法则，可以从首点开始计算出每个工序的LF与与LS，如图，如图12-11所示。

所示 接着，可以计算出每一个工序的时差，把在不影响工程最早结束时间接着，可以计算出每一个工序的时差，把在不影响工程最早结束时间的条件下，工序最早开始（或结束）的时间可以推迟的时间，成为该工序的条件下，工序最早开始（或结束）的时间可以推迟的时间，成为该工序的时差，对每个工序来说其时差记为的时差，对每个工序来说其时差记为Ts有有 Ts=LS-ES=LF-EF1236785a[0,60]60[0,60]b[60,105]45[90,135]e[60.100]c[60,70]h[100,115]j[135,170]35[135,170]i[110.135]g[80,110]30[80,110]d[60.80]20[60,80]40[80,120]25[110,135]f[70,88]18[117,135]410[107,117]15[120,135管管 理理 运运 筹筹 学学72§§6 6　统筹方法　统筹方法 最后将各工序的时差，以及其他信息构成工序时间表如表所示。

最后将各工序的时差，以及其他信息构成工序时间表如表所示 这样就找到了一条由关键工序这样就找到了一条由关键工序a,d,g,i和和j依次连接成的从发点到收点的依次连接成的从发点到收点的关键路线关键路线管管 理理 运运 筹筹 学学73三、完成工序所需时间与关键路线三、完成工序所需时间与关键路线 当完成工序所需时间不确定的情况下如何求网络时间和关键路线？当完成工序所需时间不确定的情况下如何求网络时间和关键路线？ 例例6. 长征研究院培训中心负责明年春天的各干部的工商管理培训，培长征研究院培训中心负责明年春天的各干部的工商管理培训，培训中心列出有关培训组织的各项活动的信息，要求绘制出统筹方法的网络训中心列出有关培训组织的各项活动的信息，要求绘制出统筹方法的网络图，设法求出网络时间和关键路线，并确定开始这个组织工作的时间以保图，设法求出网络时间和关键路线，并确定开始这个组织工作的时间以保证培训工作如期举行证培训工作如期举行 解：由表，绘出统筹方法的网络图如图解：由表，绘出统筹方法的网络图如图-12所示12356487abecdfghi 图图-12§§6 6　统筹方法　统筹方法管管 理理 运运 筹筹 学学74§§6 6　统筹方法　统筹方法 活动（工序）活动（工序）活动（工序）内容活动（工序）内容紧前活动紧前活动（工序）（工序） a b c d e f g h i 制定培训计划制定培训计划选聘培训教师选聘培训教师列出一些可供选择的培训地点列出一些可供选择的培训地点确定培训地点确定培训地点确定培训的日程安排确定培训的日程安排落实教学设备，器材，资料落实教学设备，器材，资料发培训通知并确定学员名单发培训通知并确定学员名单订旅馆房间订旅馆房间处理最后的一些事务处理最后的一些事务 - a - c b,d e b,d g f,g管管 理理 运运 筹筹 学学75§§6 6　统筹方法　统筹方法 由于是第一次搞培训，缺乏统计来确定完成每个活动所需时间，由于是第一次搞培训，缺乏统计来确定完成每个活动所需时间，但对所需时间做了三种估计：但对所需时间做了三种估计：1.乐观时间。

指所需最少时间，用乐观时间指所需最少时间，用a表示2.最可能时间指正常时间，用最可能时间指正常时间，用m表示3.悲观时间指不顺利情况下，最多时间，用悲观时间指不顺利情况下，最多时间，用b表示如表表示如表-13所示：所示： 表表-13 单位：周单位：周 活动活动 乐观时间乐观时间最可能时间最可能时间悲观时间悲观时间 abcdefghi1.52.01.01.50.51.03.03.01.52.02.52.02.01.02.03.54.02.02.56.03.02.51.53.07.05.02.5管管 理理 运运 筹筹 学学计划评审技术－－PERT•PERTPERT的产生的产生的产生的产生 关键路线法中，工序时间是确定值，而对研究关键路线法中，工序时间是确定值，而对研究关键路线法中，工序时间是确定值，而对研究关键路线法中，工序时间是确定值，而对研究性的工序来说，性的工序来说，性的工序来说，性的工序来说， t t（（（（i i，，，，j j）是随机的。

是随机的是随机的是随机的19581958年美年美年美年美国海军武器局研制北极星导弹时提出，重点在国海军武器局研制北极星导弹时提出，重点在国海军武器局研制北极星导弹时提出，重点在国海军武器局研制北极星导弹时提出，重点在于计划的评审于计划的评审于计划的评审于计划的评审•PERTPERT的时间估计的时间估计的时间估计的时间估计 采用三种时间估计法采用三种时间估计法采用三种时间估计法采用三种时间估计法a a－最－最－最－最乐观时间，乐观时间，乐观时间，乐观时间，b b－最悲观时间，－最悲观时间，－最悲观时间，－最悲观时间，mm－最可能时间，－最可能时间，－最可能时间，－最可能时间，则则则则 工序期望时间工序期望时间工序期望时间工序期望时间 t te e＝＝＝＝ 方差方差方差方差 δ δe e2 2＝（＝（＝（＝（ ））））2 2a+4m+b 6b－a6管管 理理 运运 筹筹 学学77§§6 6　统筹方法　统筹方法 显然这三种完成活动所需时间都具有一定概率，由经验，我们可以显然这三种完成活动所需时间都具有一定概率，由经验，我们可以可以假定这些时间的概率分布近似服从可以假定这些时间的概率分布近似服从 分布。

我们可以用如下公式计分布我们可以用如下公式计算出完成活动所需的平均时间：算出完成活动所需的平均时间： 以及方差以及方差 例如：完成工作例如：完成工作g g所需平均时间：所需平均时间： 同时求出方差为同时求出方差为管管 理理 运运 筹筹 学学78§§6 6　统筹方法　统筹方法 同样可以求出每个活动的完成所需平均时间及方差，如表同样可以求出每个活动的完成所需平均时间及方差，如表12-14：： 表表12-14活动活动T（平均时（平均时间）间）方差方差活动活动T方差方差a 20.028f20.111b30.445g40.445c20.111h40.111d20.028i20.028e10.028管管 理理 运运 筹筹 学学79§§6 6　统筹方法　统筹方法 下面就用平均时间代替完成活动所需时间，并在网络图上标上每个活下面就用平均时间代替完成活动所需时间，并在网络图上标上每个活动最早开始时间和最早结束时间，如图动最早开始时间和最早结束时间，如图12-14所示。

所示12345876同样也可以标上最晚开始时间和最晚完成时间等同样也可以标上最晚开始时间和最晚完成时间等a[0,2]g[5,9]b[2,5]e[5,6]d[2,4]f[6,8]c[0,2]i[13,15]h[9,13]32221424212345876a[0,2]g[5,9]b[2,5]e[5,6]d[2,4]f[6,8]c[0,2]i[13,15]h[9,13]2[1,3]1[10,11]4[5,9]4[9,13]2[3,5]2[0,2]3[2,5]2[13,15]2[11,13]图12-14图12-15管管 理理 运运 筹筹 学学80§§6 6　统筹方法　统筹方法 从表从表12-15上我们找到了一条从发点到收点由关键工序上我们找到了一条从发点到收点由关键工序a,b,g,h,i组成的组成的关键路线，用双线标出来则完成培训工作所需的平均时间为各关键路线关键路线，用双线标出来则完成培训工作所需的平均时间为各关键路线的时间之和：的时间之和： =2+3+4+4+2=15（周）（周） 同时完成时间近似服从一定的概率分布正态分布，则均值为关键路线同时完成时间近似服从一定的概率分布正态分布，则均值为关键路线上各关键活动之均值之和上各关键活动之均值之和15，方差也为关键路线上各关键活动方差之和，方差也为关键路线上各关键活动方差之和1.05。

由此我们可以计算出此项培训组织工作不同完工时间的概率，如由此我们可以计算出此项培训组织工作不同完工时间的概率，如16周周内完工的概率内完工的概率 为求此概率，可以先求为求此概率，可以先求u值 式中的式中的T为预定完工时间为预定完工时间16，，E（（T））=15，， 算得算得u=0.976查正态分布函数表可知概率为查正态分布函数表可知概率为0.8355即16周内完工周内完工的概率为的概率为83.55%.管管 理理 运运 筹筹 学学81§§6 6　统筹方法　统筹方法其正态分布图如图其正态分布图如图12-16所示：所示：16图图12-16管管 理理 运运 筹筹 学学82§§6 6　统筹方法　统筹方法四、网络优化四、网络优化 得到初始的计划方案，但通常要对初始方案进行调整与完善根据计得到初始的计划方案，但通常要对初始方案进行调整与完善根据计划目标，综合考虑资源和降低成本等目标，进行网络优化，确定最优的计划目标，综合考虑资源和降低成本等目标，进行网络优化，确定最优的计划方案。

划方案 1.时间时间-资源优化资源优化 做法：做法： 1）优先安排关键工序所需的资源优先安排关键工序所需的资源 2）利用非关键工序的时差，错开各工序的开始时间利用非关键工序的时差，错开各工序的开始时间 3）统筹兼顾工程进度的要求和现有资源的限制，多次综合平衡统筹兼顾工程进度的要求和现有资源的限制，多次综合平衡 下面列举一个拉平资源需要量最高峰的实例在例下面列举一个拉平资源需要量最高峰的实例在例5中，若加工工人中，若加工工人为为65人，并假定这些工人可完成这人，并假定这些工人可完成这5个工序任一个，下面来寻求一个时间个工序任一个，下面来寻求一个时间-资源最优方案如表资源最优方案如表-16所示：所示： 管管 理理 运运 筹筹 学学83§§6 6　统筹方法　统筹方法表表-16工序工序需要人需要人数数最早开最早开始时间始时间所需时所需时间间时差时差d5860200f22701847g428030h391001520i26110250 若上述工序都按最早开始时间安排，那么从第若上述工序都按最早开始时间安排，那么从第60天至第天至第135天的天的75天天里，所需的机械加工工人人数如图里，所需的机械加工工人人数如图-17所示。

所示管管 理理 运运 筹筹 学学84§§6 6　统筹方法　统筹方法 在图的上半部中，工序代号后的数字是人数，线下面的数字是非关键在图的上半部中，工序代号后的数字是人数，线下面的数字是非关键工序时差长度图的下半部表示从第工序时差长度图的下半部表示从第60天至天至135天内的天内的75天里，所需机械天里，所需机械加工工人数，这样的图称为资源负荷图加工工人数，这样的图称为资源负荷图 274635 f(22人）人）18h(39人人)1558人人64人人80人人81人人42人人26人人65人人60 80 100 120 130 d(58人）人） i(26人）人） g(42人）人）302025图图12-17管管 理理 运运 筹筹 学学85§§6 6　统筹方法　统筹方法 同时我们应优先安排关键工序所需的工人，再利用非关键工序的时同时我们应优先安排关键工序所需的工人，再利用非关键工序的时差，错开各工序的开始时间，从而拉平工人需要量的高峰经过调整，我差，错开各工序的开始时间，从而拉平工人需要量的高峰。

经过调整，我们让非关键工序们让非关键工序f从第从第80天开始，工序天开始，工序h从第从第110天开始找到了时间天开始找到了时间-资源资源优化的方案，如图优化的方案，如图12-18所示，在不增加工人的情况下保证了工程按期完所示，在不增加工人的情况下保证了工程按期完成246753 f(22人）人） h(39人）人） d(58人）人） i(26人）人） g(42人）人）工人数工人数65人人60 80 100 120 13058人人42人人64人人26人人65人人图图12-18管管 理理 运运 筹筹 学学86§§6 6　统筹方法　统筹方法2.时间时间-费用优化费用优化 需要考虑时间与费用的问题：在既定的时间前工程完工的前提下，使需要考虑时间与费用的问题：在既定的时间前工程完工的前提下，使得所需的费用最少，或者在不超工程预算的条件下使工程最早完工这些得所需的费用最少，或者在不超工程预算的条件下使工程最早完工这些是时间是时间-费用优化要研究和解决的问题费用优化要研究和解决的问题 直接费用：为了加快工程进度，需要增加人力、设备和工作班次，这直接费用：为了加快工程进度，需要增加人力、设备和工作班次，这需要增加一笔费用，成为直接费用。

需要增加一笔费用，成为直接费用 间接费用：由于工程早日完工，减少了管理人员的工资办公费等费用间接费用：由于工程早日完工，减少了管理人员的工资办公费等费用称为间接费用一般说工序越短，直接费用越多，间接费用越少称为间接费用一般说工序越短，直接费用越多，间接费用越少管管 理理 运运 筹筹 学学87§§6 6　统筹方法　统筹方法 工序的最快完成时间：指完成时间的最高限度工序的最快完成时间：指完成时间的最高限度 我们设完成工序我们设完成工序j的正常所需时间为的正常所需时间为Tj;直接费用为直接费用为cj;完成工序完成工序j的最快完成时的最快完成时间为间为T`j,直接费用为直接费用为c`j这样我们可以计算出缩短工序这样我们可以计算出缩短工序j的一天工期所增加的直接的一天工期所增加的直接费用，用费用，用kj表示，称为直接费用变动率有表示，称为直接费用变动率有 时间时间--费用优化问题可建立两个线性规划模型费用优化问题可建立两个线性规划模型 模型一，在既定的时间模型一，在既定的时间T完工的前提下，问各工序的完成时间为多少才使因完工的前提下，问各工序的完成时间为多少才使因缩短工期而增加的直接费用最少。

缩短工期而增加的直接费用最少 设工序（设工序（i ,j)的提前完工时间为的提前完工时间为Yij,我们用我们用Tij,T`ij分别表示正常完工时间与最快分别表示正常完工时间与最快完工的时间，则有工序（完工的时间，则有工序（i ,j)的实际完工时间为：的实际完工时间为：Tij-Yij我们用Cij,C`ij表示用正表示用正常完工时间和最快完成时间完成工序所需要的费用，常完工时间和最快完成时间完成工序所需要的费用，Kij为工序（为工序（i ,j)的直接费用的直接费用变动率得到这个问题的线性规划模型如下：变动率得到这个问题的线性规划模型如下： minf= （（Kij*Yij) （（i,j)S.t. Xj-Xi  Tij-Y`ij,对一切弧（对一切弧（i, j) Yij  Tij-T`ij, 对一切弧（对一切弧（i, j) Xn-X1  T, Xi  0，， Yij  0。

管管 理理 运运 筹筹 学学88§§6 6　统筹方法　统筹方法例例7. 例例5所提供的信息都作为本例的信息，另外还给出了在装配过程中各道工序所提供的信息都作为本例的信息，另外还给出了在装配过程中各道工序所需正常完工时间与最快完工时间，以及对应正常完工时间与最快完工时间的所需正常完工时间与最快完工时间，以及对应正常完工时间与最快完工时间的所需的直接费用和每缩短一天工期所需增加的直接费用，如表所需的直接费用和每缩短一天工期所需增加的直接费用，如表12-17所示 表表12-17工序工序Tij正常正常完工完工Cij直接直接费用费用T`ij最快最快完工完工C`ij直接直接费用费用直接费用直接费用变动率变动率a60100006010000-b454500306300120c10280054300300d2070001011000400e40100003512500500f183600105440230g3090002012500350h153750105750400i256250159150290j35120003512000-管管 理理 运运 筹筹 学学89§§6 6　统筹方法　统筹方法 该工程要求在该工程要求在150天内完工，问每个工序应比正常完工时间提前多少天天内完工，问每个工序应比正常完工时间提前多少天完成，才能使整个工程因缩短工期而增加的直接费用为最少。

如果工期要完成，才能使整个工程因缩短工期而增加的直接费用为最少如果工期要求在求在140天完工呢？天完工呢？12345678abfechgijd图图12-19管管 理理 运运 筹筹 学学90§§6 6　统筹方法　统筹方法解：绘出如图解：绘出如图12-19所示，根据此网络图建立数学模型所示，根据此网络图建立数学模型 设此网络图上第设此网络图上第i点发生的时间为点发生的时间为xi，工序提前完工的时间为，工序提前完工的时间为yij 目标函数目标函数minf=120y27+300y23+400y24+500y25+230y37+350y46+400y57+290y67.s.t. x2-x1  60-y12, x7- x2  45-y27 x3-x2 10-y23 x4-x2 20-y24 x5-x2 40-y25 x7-x3 18-y37 x6-x4 30-y46 x5-x4 0虚拟弧（虚拟弧（4，，5）） x7-x5 15-y57 x7-x6 25-y67管管 理理 运运 筹筹 学学91§§6 6　统筹方法　统筹方法 x1 =0, y12 0, y27 15, y23  5 y24  10 y25  5 y37  8 y46  10 y57  5 y78  0 x8  150 xi  0，，yij  0.（对一切可能的（对一切可能的ij)运算得到结果：运算得到结果：f=6400。

管管 理理 运运 筹筹 学学92§§6 6　统筹方法　统筹方法 模型二，我们知道直接费用是随着完成时间的缩短而增加，而间接模型二，我们知道直接费用是随着完成时间的缩短而增加，而间接费用却会随着完成时间的缩短而减少，设单位时间的间接费用为费用却会随着完成时间的缩短而减少，设单位时间的间接费用为d,计划计划期的间接费用与总工期成正比，即为期的间接费用与总工期成正比，即为d(xn-x1),那么求使包括间接费用与那么求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间直接费用在内的总费用最少的整个工程最优完成时间T和各个工序最优和各个工序最优完成时间的模型为：完成时间的模型为： 目标函数目标函数min f=d(xn-x1)+ s.t. xj-xi   Tij-yij，对一切弧（，对一切弧（i ,j) yij Tij-T`ij ，对一切弧（，对一切弧（i ,j) xi  0，， yij  0。

管管 理理 运运 筹筹 学学93§§6 6　统筹方法　统筹方法 例例8 如果在例如果在例7中，每天的间接费用为中，每天的间接费用为330元，求使包括间接费用与直接费元，求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间用在内的总费用最少的整个工程最优完成时间T和各个工序最优完成时间和各个工序最优完成时间 解：决策变量的含义同例解：决策变量的含义同例7 此数学模型的目标函数为：此数学模型的目标函数为： min f=330(x8-x1) +120y27+300 y23 +400y24+500y25+230y37+350y46+290y67 此模型的约束条件与例此模型的约束条件与例7的约束条件基本相同，只要在例子的约束条件中去的约束条件基本相同，只要在例子的约束条件中去掉掉x8  150就得到了例就得到了例8模型的约束条件了模型的约束条件了 计算得到以下结果：计算得到以下结果： f=55700. x1=0, y12=0, y67 =10, x2=60, y27 =0, y78=0.管管 理理 运运 筹筹 学学94§§6 6　统筹方法　统筹方法x3 =125, y23 =0, x4 =107, y24 =0, x5 =110, y25 =0, x6 =110, y37 =0, x7 =125, y46 =0, x8 =160, y57 =0, 也就是说整个工程工期为也就是说整个工程工期为160天时总费用最少为天时总费用最少为55700元，各个元，各个工序开始时间如解所示，工序工序开始时间如解所示，工序 i 要提前要提前10天完工，其余的工序按正天完工，其余的工序按正常时间完工。