《运筹学》课程教学讲义（Operations Research）第十二章（12.1）统筹图

运筹学讲义 §12.1统筹图 统筹方法是利用数学方法和网络图来研究、分析工程项目的合理组织、协调管理的一种科学管理 方法 这一方法于20世纪50年代产生于美国.1956年,美国杜邦公司为协调公司不同业务部门的系统 规划,利用网络方法制订了第一套网络计划,称为关键路线法(CPM, Critical path Method).1958 年,美国海军武器局在制订“北极星”导弹研制计划时,同样利用了网络方法,但更注重于对各项任 务安排的评价和审查,称为计划评审技术(PERT, Program Evaluation and Review Technique) 1965年,著名数学家华罗庚先生在我国大力推广应用CPM和PERT两种方法(初中《语文》收录 有华罗庚的科普文章《统筹方法》),并根据其主要特点:统筹安排,将二者合称为统筹方法 60年代,钱塘江大桥的修建(茅以升)和“引滦λ津”工程等重大工程都广泛地使用了统筹方 法,并获得了极为显著的经济效益. 目前,基于统筹方法的项目管理软件 Project98/2000已经开发并成为进行项目管理的强有力的 工具 基本概念: 工序:一项有具体内容(人、物、财等的投入),需要经过一定时间才能完成的生产过程(有开 始、延续和结束时间).如修建一座大楼,可分为设计、挖地基、打地基、主体工程、上顶、安装水 电暖汽设备、室内装修等工序 工序是生产过程中的一些相对独立和相互关联的任务.相邻的两个工序,前者称为后者的紧前工 序,后者称为前者的紧后工序 事项:生产过程的始点,终点以及其中的两道或两道以上工序的交点 某一工序的开工时刻称为开工事项,完工时刻称为完工事项 个生产过程的最初开工时刻称为总开工事项,最终完工时刻称为总完工事项 在统筹图中,一般用弧来表示工序,用弧的起点和终点分布来表示工序的开工事项和完工事项 A,B为工序,且A是B的紧前工序,B是A的紧后工序 ①,@,@为事项,其中①为总开工事项,Q为总完工事项;@既为工序A的完工事项,又为工 序B的开工事项 工序时间:完成一个关系所需的时间. 显然,工序时间在工序开工之前难以准确确定.一般地,可根据以下经验公式/=+b+△C来估 6 计,其中a为乐观时间(一切顺利时,完成工序的最少可能的时间),b为悲观时间(遇到意想不到 的困难时,完成工序的最多可能的时间),C为最可能时间(一般情况下,完成工序的时间) 统筹方法的基础是画出统筹图

运 筹 学 讲 义 1 §12.1 统筹图 统筹方法是利用数学方法和网络图来研究、分析工程项目的合理组织、协调管理的一种科学管理 方法. 这一方法于 20 世纪 50 年代产生于美国.1956 年，美国杜邦公司为协调公司不同业务部门的系统 规划，利用网络方法制订了第一套网络计划，称为关键路线法（CPM，Critical Path Method）.1958 年，美国海军武器局在制订“北极星”导弹研制计划时，同样利用了网络方法，但更注重于对各项任 务安排的评价和审查，称为计划评审技术(PERT，Program Evaluation and Review Technique). 1965 年，著名数学家华罗庚先生在我国大力推广应用 CPM 和 PERT 两种方法（初中《语文》收录 有华罗庚的科普文章《统筹方法》），并根据其主要特点：统筹安排，将二者合称为统筹方法. 60 年代，钱塘江大桥的修建（茅以升）和“引滦入津”工程等重大工程都广泛地使用了统筹方 法，并获得了极为显著的经济效益. 目前，基于统筹方法的项目管理软件 Project 98/2000 已经开发并成为进行项目管理的强有力的 工具. 基本概念： 工序：一项有具体内容（人、物、财等的投入），需要经过一定时间才能完成的生产过程（有开 始、延续和结束时间）.如修建一座大楼，可分为设计、挖地基、打地基、主体工程、上顶、安装水 电暖汽设备、室内装修等工序. 工序是生产过程中的一些相对独立和相互关联的任务.相邻的两个工序，前者称为后者的紧前工 序，后者称为前者的紧后工序. 事项：生产过程的始点，终点以及其中的两道或两道以上工序的交点. 某一工序的开工时刻称为开工事项，完工时刻称为完工事项. 一个生产过程的最初开工时刻称为总开工事项，最终完工时刻称为总完工事项. 在统筹图中，一般用弧来表示工序，用弧的起点和终点分布来表示工序的开工事项和完工事项 如 A, B 为工序，且 A 是 B 的紧前工序， B 是 A 的紧后工序. ○1 ，○2 ，○3 为事项，其中○1 为总开工事项，○3 为总完工事项；○2 既为工序 A 的完工事项，又为工 序 B 的开工事项. 工序时间：完成一个关系所需的时间. 显然，工序时间在工序开工之前难以准确确定.一般地，可根据以下经验公式 6 a b 4c t + + = 来估 计，其中 a 为乐观时间（一切顺利时，完成工序的最少可能的时间）， b 为悲观时间（遇到意想不到 的困难时，完成工序的最多可能的时间），c 为最可能时间（一般情况下，完成工序的时间）. 统筹方法的基础是画出统筹图

运筹学讲义 统筹图:将一个生产过程中各工序之间相互制约的先后顺序关系从左至右表示出来,所得到由 点和弧构成的网络图 显然,从图论的观点看,统筹图即为一张赋权有向图 统筹图反映一个生产过程的全貌和各工序之间的关系 统筹图的制作步骤 1.工序的分解:将一个生产过程分解为若干个工序,确定各工序之间的相互关系,并以表格表示 出来. 如某项建筑工程可分解为7道工序,各工序间的先后关系及工序时间可列表(工序分解表)如下: 工序代号 工序名称 紧前工序工序时间 设计 挖地基 打地基 CDEF 主体工程 上顶 ABcDD 安装水电暖汽 室内装修 显然,工序名称无关紧要,可用工序代号来表示工序 这一步骤需要工程技术人员与统筹工作者共同完成 2.画图:用弧来表示工序,用弧的两个顶点(圈起的数字)来表示工序的两个事项.根据步骤1 得到的工序分解表,由第一个工序开始,按照各工序的先后顺序,从左至右,直至最后一个工序为止 画出一个图 例某生产过程可分解为如下工序: 序紧前工序 ABCDE A, B C C 据此,画图如下: 统筹图的绘制规则 (1)图中不能含有有向圈:否则,会致使工序的先后顺序混乱,应重新分解工序 如某生产过程可分解为5个工序,且画图如下

运 筹 学 讲 义 2 统筹图：将一个生产过程中各工序之间相互制约的先后顺序关系从左至右表示出来，所得到由顶 点和弧构成的网络图. 显然，从图论的观点看，统筹图即为一张赋权有向图. 统筹图反映一个生产过程的全貌和各工序之间的关系. 统筹图的制作步骤： 1.工序的分解：将一个生产过程分解为若干个工序，确定各工序之间的相互关系，并以表格表示 出来. 如某项建筑工程可分解为 7 道工序，各工序间的先后关系及工序时间可列表（工序分解表）如下： 工序代号 工序名称 紧前工序 工序时间 A B C D E F G 设计 挖地基 打地基 主体工程 上顶 安装水电暖汽 室内装修 - A B C D D E，F 8 20 10 60 13 15 20 显然，工序名称无关紧要，可用工序代号来表示工序. 这一步骤需要工程技术人员与统筹工作者共同完成. 2.画图：用弧来表示工序，用弧的两个顶点（圈起的数字）来表示工序的两个事项.根据步骤 1 得到的工序分解表，由第一个工序开始，按照各工序的先后顺序，从左至右，直至最后一个工序为止， 画出一个图. 例 某生产过程可分解为如下工序： 工序 紧前工序 A B C D E - - A，B C C 据此，画图如下： 统筹图的绘制规则： （1）图中不能含有有向圈；否则，会致使工序的先后顺序混乱，应重新分解工序. 如某生产过程可分解为 5 个工序，且画图如下：

运筹学讲义 显然,图中含有一个有向圈@→③→①回,致使工序B,C,D的先后顺序混乱.故应重新分 解工序 (2)图中任意两个顶点之间不能有重弧:否则,会致使工序的先后顺序混乱,应引入虚工序 令虚工序的工序时间为0. 虚工序用虚线表示,仅起到衔接前后工序之间先后关系的作用,不占用时间 某生产过程可分解为如下工序 工序紧前工序 ABcDEF 据此,画图如下 显然,图中的顶点回与,与④之间有重弧,致使工序D的紧前工序为B,C,与原来的工序 的先后顺序不符.引入虚工序,将上图修改如下: 0才0800⑥ (3)图中只能有一个总开工事项和一个总完工事项:否则,应将所有总开、完工事项分别合并 为一个总开、完工事项

运 筹 学 讲 义 3 显然，图中含有一个有向圈○2 → ○3 → ○4 → ○2 ，致使工序 B,C, D 的先后顺序混乱.故应重新分 解工序. （2）图中任意两个顶点之间不能有重弧；否则，会致使工序的先后顺序混乱，应引入虚工序， 令虚工序的工序时间为 0. 虚工序用虚线表示，仅起到衔接前后工序之间先后关系的作用，不占用时间. 例 某生产过程可分解为如下工序： 工序 紧前工序 A B C D E F - A A B B，C D，E 据此，画图如下： 显然，图中的顶点○2 与○3 ，○3 与○4 之间有重弧，致使工序 D 的紧前工序为 B,C ，与原来的工序 的先后顺序不符.引入虚工序，将上图修改如下： （3）图中只能有一个总开工事项和一个总完工事项；否则，应将所有总开、完工事项分别合并 为一个总开、完工事项. 如

运筹学讲义 AG ○ 显然,图中含有两个总开工事项和两个总完工事项,合并之: AG Q (4)平行作业的处理:为加快某一工序的进行,可将其分解为两个或两个以上的工序同时进行 是为平行作业.对平行作业的处理,可借助虚工序. 如 为加快工序B的进行,将B分解为B1,B2B3三个工序同时进行: 根据规则(2),引入虚工序,改正之为

运 筹 学 讲 义 4 显然，图中含有两个总开工事项和两个总完工事项，合并之： （4）平行作业的处理：为加快某一工序的进行，可将其分解为两个或两个以上的工序同时进行， 是为平行作业.对平行作业的处理，可借助虚工序. 如 为加快工序 B 的进行，将 B 分解为 1 2 3 B ,B ,B 三个工序同时进行： 根据规则（2），引入虚工序，改正之为

运筹学讲义 BI (5)交叉作业的处理:为加快生产过程的进度,常常在一个工序尚未完成时,就开始进行其紧 后工序,是为交叉作业.对平行作业的处理,可借助虚工序和增加顶点 如 ○O)O2O 若令A=A1+A2,B=B1+B2,C=C1+C2,则 B2 若令A=A1+A2+A3,B=B1+B2+B3,则 3.编号:给图中的每个顶点(事项)一个编号,使得每条弧(工序)的起点的编号小于终点的编 编号的方法:将总开工事项编号为①,去掉顶点①的所有出弧:从剩下的顶点中选取一个无入弧 的顶点,并编号为@;……重复上述步骤,直到图的所有顶点均被编号为止 如

运 筹 学 讲 义 5 （5）交叉作业的处理：为加快生产过程的进度，常常在一个工序尚未完成时，就开始进行其紧 后工序,是为交叉作业.对平行作业的处理，可借助虚工序和增加顶点. 如 若令 A = A1 + A2， B = B1 + B2，C = C1 +C2 ，则 若令 A = A1 + A2 + A3， B = B1 + B2 + B3 ，则 3.编号：给图中的每个顶点（事项）一个编号，使得每条弧（工序）的起点的编号小于终点的编 号. 编号的方法：将总开工事项编号为○1 ，去掉顶点○1 的所有出弧；从剩下的顶点中选取一个无入弧 的顶点，并编号为○2 ；…….重复上述步骤，直到图的所有顶点均被编号为止. 如

运筹学讲义 AG 显然,图的编号未必唯 在编号后的图中,每个工序都对应一条弧(,j),且i<j以后,工序可简称为工序(,j,而不 必再指明工序名称 在编号后的图中,每条弧赋予一个权,以表示工序时间,即得统筹图

运 筹 学 讲 义 6 显然，图的编号未必唯一. 在编号后的图中，每个工序都对应一条弧 (i, j) ，且 i  j .以后，工序可简称为工序 (i, j) ，而不 必再指明工序名称. 在编号后的图中，每条弧赋予一个权，以表示工序时间，即得统筹图. 如