第3章-图论初步与物流工程项目计划编制

物流运筹学教学课件第3章图论初步与物流工程项目计划编制图的基本概念1路径、回路与连通性2生产加工顺序的安排3工程项目计划的横道图表示法4计划评审方法与关键路线法53.1图的基本概念3.13.1.1图定义1

图G是由非空结点集合

以及边集合

所组成。其中每条边可以用一个结点表示，亦即

3.1.1图定义中的结点对可以是有序的，也可以是无序的。若边e所对应的结点对（a，b）是有序的，则称e是有向边。

a称为e的起点，

b称为e的终点。若边e所对应的结点对（a，b）是无序的，则称e是无向边。图中所有边均是有向边的图称为有向图；图中所有边均是无向边的图称为无向图；同时含有有向边和无向边的图称为混合图。3.1.1图例3.1（1）设无向图

其中

，

，

，

.

（2）设有向图

，其中

，

，

画出G与G’的图形。3.1.1图图G图G’3.1.1图对于边ei{vk,vt}不管ei为有向还是无向，都称边ei与结点vk及vt相关联，而vk与vt称为邻接的。若干条边关联于同一个结点，则这些边称为邻接的。一条边若与两个相同的结点相关联则称为环。不与任何结点邻接的结点称为孤立点。3.1.1图一个具有n个结点、m条边所组成的图G称为（n，m）图，其中结点个数n称为图G的阶数。如果图G是一个（n，0）图，则称G为零图。在有向图中，两结点间（包括结点自身间）若有同起点和终点的几条边，则这几条边称为平行边。在无向图中，两结点间（包括结点自身间）若有几条边，则这几条边称为平行边。含有平行边的图称为多重图。不含平行边的图称为简单图。有时在一个图中，边的旁侧加一些数字一刻画某些特征，称为边的权。每条边都有权的图称为加权图。3.1.1图定义2设G=<V，E>是一个无向图，结点v所关联的边数（有环时计算两次），称为

结点v的度数，记为deg（v）。定义3

设G=<V，E>是一个有向图，以结点v为起点的边数称为结点v的出度，记为deg（v

）；

以结点v为终点的边数称为结点v的入度，记为deg（v）；对G中每个结点v，

deg（v

）+deg（v）称为结点v的度数，也记为deg（v）。定义4设G=<V，E>是一个图，度数为奇（偶）数的结点称为奇（偶）结点。

3.1.1图结点的度数的性质：设G=<V，E>是一个（n，m）图，它的结点集合为V={v1，

v2

，…，

vn}，则在有向图中，上式也可以写成

在（n，m）图中，奇结点必为偶数个。在有向图中，所有结点的出度之和与所有结点的入度之和相等，即3.1.1图定义5设G是有n个结点的简单无向图，若它的任何两个不同结点之间恰有一条边，这样的无向图称为无向完全图，记为Kn

定义6设G是有向简单图，若将它的所有边都代之以无向边后成为一个无向完全图，则G称为有向完全图。

3.1.1图定理1一个有n个结点的完全图共有

条边。推论

完全图Kn的每一结点的度数为n-1,

图的总度数为n（n-1）

3.1.2图的同构用图形表示图的时候，可能会有这样的情形：两个看似很不一样的图形，实际上表示的是同一个图。或者说，两个图形仅仅是点的名字或位置不同，而作为图来讲，他们的结构是一样的。我们把这样的两个图形所表示的两个图形称为同构。3.1.2图的同构定义7

设G=<V，E>

，

G’=<V’，E’>是两个图，若存在从V到V’的双射函数f，使得对任意

当且仅当

则称G和G’是同构的，记作G

≌G’。3.1.2图的同构3.1.2图的同构若两个图同构，则结点数相等；若两个图同构，则边数相等；若两个图同构，则度数相同的结点数相等。以上三个条件只是两个图同构的必要条件而不是充分条件，利用它们不能判定图的同构性，它们仅是判定两个图不同构的有效方法。3.1.3补图与子图定义8

设G=<V，E>是无相图，

V有n个结点，又设Ek是完全图Kn的边集，则一个由G的点集V和Ek

-E为边集的图称为G的补图，记作

3.1.3补图与子图定义9设有图G=<V，E>，

G’=<V’，E’>若

和

则称G’为G的子图。特别是在V=V’而同时有

时，称G’为G的生成子图。3.2路径、回路与连通性3.23.2.1路径与回路定义1设有向图G=<V，E>，

并且vi-1

,vi分别是边ei

的起点与终点（

i=1,2，…，k），则称点边的交错序列L:v1

e1

v2e3…vk-1ekvk为图中从v0至vk的路径，K称为该路径的长度。3.2.1路径与回路在路径L中，如果vi

=vk

，则称L为回路。在路径L中，如果e1e2…ek互不相同，则称L为简单路径。在路径L中，如果v1v2

…vk互不相同，则称L为基本路径。3.2.1路径与回路【例3.2】

图3-7中所给出的从结点v1出发而终止于结点v3的一些路径是：。

基本路径简单路径既不基本，又不简单3.2.1路径与回路部分回路基本回路简单回路既不基本，又不简单3.2.1路径与回路定理1一个有向（n，m）图中任何基本路径长度均小于或等于n

-1，而任何基本回路长度均小于或等于n。证明在基本路径中各结点均是不同的，在长度为K的基本路径中，不同结点的数目为k-1，因图中仅有n个不同结点，所以基本路径的长度不会超过n-1，对于长度为K的基本回路，不同结点的数目也为k，因图中仅有n个不同结点，所以基本回路的长度不会超过n。3.2.1路径与回路定义2设u，v是有向图的两个结点，如果存在一条从u到v的路径，则称结点u到v是可达的，否则称在该图u到v是不可达。约定，图的任意一结点到它自身是可达的。3.2.1路径与回路定义3

设u，v是有向图的两个结点，若u到v是可达的，则u到v的一切路径的长度的最小值称为u到v的距离，记为d（u，v）。如果u到v是不可达的，则记

。约定d（u，v）=03.2.2连通性定义4在无向图G中，如果它的任何两结点间均是可达的，则称图G为连通图，否则称图G为非连通图。定义5在无向图G中，如果忽略其边的方向后得到的无向图是连通的，则称此有向图G是连通的；否则称为非连通图。定义6一个有向连通图G如果其任何两结点间是互相可达的，则称图G为强连通的；如果其任何两结点间至少存在一方向是可达的，则称图G为单向连通的；如果忽略边的方向后其无向图是连通的，则称图G是弱连通的。3.2.2连通性连通的无向图非连通的无向图强连通的有向图单连通的有向图弱连通的有向图3.2.3哥尼斯堡七桥问题与欧拉回路“七桥问题”：哥尼斯堡（现俄罗斯的加里宁格勒）有一条布勒尔河，其两个支流在城中心汇成一条大河。河中间有两个岛，河的两岸与这两个岛之间有七座桥连接。哥尼斯堡大学的学生们傍晚散步时，总想一次走过这七座桥，每座桥只走一遍。可是试来试去总办不到。于是，有学生写信去请教欧拉，欧拉回信解答了这个问题。3.2.3哥尼斯堡七桥问题与欧拉回路欧拉把七桥问题中的桥与岛、陆地（连接点）之间的关系用点与线组成的图表示：把桥对应为几何线，把两岸和岛对应为几何点，得到如图3-10所示的图。问题转变为：从某一点开始画，笔不离开纸，一笔画成又回到出发点，且各条线只画一次。3.2.3哥尼斯堡七桥问题与欧拉回路欧拉的推理如下：凡是一笔画中出现的交点处，线一出一进总应该通过偶数条，只有作为起点和终点的两点才有可能通过奇数条线。因此，凡是奇点个数多于两个的平面图都不可能一笔画出。图中的四个点均为奇点，因此不可能一笔画出。这样，欧拉就解答了这个问题。欧拉这种处理问题的方法标志着图论的诞生。3.2.3哥尼斯堡七桥问题与欧拉回路经过图中所有边一次，且访问每个顶点至少一次的一个回路，称为欧拉回路。具有欧拉回路的图称为欧拉图。3.2.3哥尼斯堡七桥问题与欧拉回路3.2.3哥尼斯堡七桥问题与欧拉回路定理2

无向连通图具有一条欧拉路径的充分必要条件是有零个或两个次数为奇数的结点。由该定理2可知，一个图是否存在欧拉路径，主要考察：该图是否连通；结点的度数为奇数的个数。推论无向连通图G为欧拉图的充分必要条件是G的每个结点的度数均为偶数。3.2.3哥尼斯堡七桥问题与欧拉回路【例3.3】邮递员从邮局v1出发沿邮路投递信件，其邮路如图3-12所示。试问是否存在一条投递路线使邮递员从邮局出发通过所有路线而不重复且最后回到3.2.3哥尼斯堡七桥问题与欧拉回路解：此问题即为求证图3-12是否为欧拉图。由于图中每个结点的度数均为偶数，故由上述推论可知这样的一条投递路线是存在的3.2.3哥尼斯堡七桥问题与欧拉回路【例3.4】甲、乙两只蚂蚁分别位于图3-13中的a、b两处，并设图中的每条长度均相等。甲、乙进行比赛：从它们所在的点出发，走过图中的所有边，最后到达c处。如果它们速度相同，问谁先到达目的地？3.2.3哥尼斯堡七桥问题与欧拉回路解：在图中，

b、c两个点的度数均为奇数，因而存在从b到c的欧拉路径，蚂蚁乙从b走到c

，只要走一条欧拉路径，边数为9。而蚂蚁甲要走完所有的边到达c，必须先走到b，再走一条欧拉路径，因而它至少要走10条边才能到达

。所以乙先到达目的地。3.3生产加工顺序的安排3.33.3生产加工顺序的安排【例3.5】某车间生产四种产品，都要依次经过甲、乙两台设备的加工，假定每种产品都必须在设备甲上加工完毕后，才能进入设备乙上加工，每种产品在每台设备上所需要的加工时间如表3-1所示。问如何安排这些产品的加工顺序，可使总的加工时间最短？1234甲3745乙62733.3生产加工顺序的安排在设备甲上一种产品加工完后就马上可以加工另一种产品，但是，在设备乙上一种产品加工完后，由于后面要加工的产品还在设备甲上未加工完，就要出现设备乙不得不空闲着等待设备甲正加工着的另一种产品的情况。因此，要想使总的加工时间尽可能短，即是要求设备的空闲时间的总和尽可能小。如果安排在两个设备上的加工顺序不一样的话，我们总可以将其调换成同样的顺序，而不会增加设备乙的空闲时间。如图3-22所示，将设备乙上的加工顺序换成与设备甲上的加工顺序一样后，并不增加设备乙的等待时间，甚至还可缩短等待时间。因此，我们只考虑两台设备上加工顺序相同的安排，也就是确定一个顺序。3.3生产加工顺序的安排3.3生产加工顺序的安排排好时间表，从中数最小，属于第一行，应该尽先排，属于第二行，次序往尾排，划掉已排者，剩下照样办。3.3生产加工顺序的安排1234甲3745乙6273最小数，位于第二行，安排在最后最小数，位于第一行，第一个生产3.3生产加工顺序的安排3.3生产加工顺序的安排【例3.6】某车间生产五种产品，都要依次经过甲、乙两台设备的加工，产品都必须在设备甲上加工完毕之后，才能进入设备乙加工。每种产品在每台设备上加工所需时间如表3-2所示。可如何安排这些产品的加工顺序使总的加工时间最少？12345甲62734乙374573.3生产加工顺序的安排3.4工程项目计划的横道图表示法3.43.4工程项目计划的横道图表示法引例

某建筑工程施工计划如表3-3：其中紧前工作是指该项工作紧接的前一项工作，要等前一项工作完成后该项工作才能开工，例如工作D的紧前工作是B和C,即B和C完工后D才能开工.工作持续时间是指工作从开始到完成后所用的时间.问：用什么方法可以将工作计划直观表示出来，能让现场管理人员和施工人员都能理解工作的进度和各项工作之间的先后各项？工作序号工作代号工作名称紧前工作工作持续时间1A支模1—42B支模2A43C绑钢筋1A24D绑钢筋2B,C25E浇混凝土1C66F浇混凝土2D,E63.4工程项目计划的横道图表示法解:如表3-4，横向为施工进度，纵向为工作项目.由水平时间刻度中画出代表工作的横道，表示出工作的开始与结束时间，横道的长度表示工作的持续时间.则结合图形与表格，就可以清晰地表达各项工作的进度和先后各项.完成该工程的总工期为18天.工作项目施工进度（d）2468101214161820支模1

支模2

绑钢筋1

绑钢筋2

浇混凝土1

浇混凝土2

3.4工程项目计划的横道图表示法【例3.7】

建设某重型机器制造厂工程进度计划如表3-5所示：试指出该工程的总工期，并指出大型机器厂房的开工时间、完工时间及工期.3.4工程项目计划的横道图表示法解:由图可以看出，工程的开工时间为2008年第3季度初，完工时间为2012年第3季度末，全部工期为4年零3个月.其中大型机器厂房的开工时间委2010年第4季度，完工时间为2012年第2季度，该子项目工期为21个月。3.4工程项目计划的横道图表示法【例3.8】某新产品推销工作计划如表3-6：试用横道图表示该工作计划，并计算项目的总工期。工作序号工作代号工作项目紧前工作工作持续时间1A广告计划—22B推销员培训计划A23C商店管理人员培训计划B24D电视、报纸广告发布A35E广告拷贝A46F准备推销资料B77G准备培训资料B68H广告后继续在新闻机构宣传D,E49I审查、选拨、训练管理人员C710J实施训练计划K,I311K正式推销新产品F,H,J43.5计划评审方法和关键路线法3.53.5计划评审方法和关键路线法计划评审方法（PERT）和关键路线法（CPM）是网络分析的一个组成部分，它广泛应用于系统分析和项目管理。已广泛应用于建筑施工和新产品的研制计划、计算机系统的安装调试、军事指挥及各种大型复杂工程的控制管理。3.5.1.1计划评审方法网络图的一些基本概念作业：指任何消耗时间或资源的行动。如新产品设计中的初步设计、技术设计、工装制造等。根据需要，作业可以划分得粗一些，也可以划分得细一些。事件：标志作业的开始或结束，本身不消耗时间或资源，或相对作业讲，消耗量可以小到忽略不计。某个事件的实现，标志着在它前面各项作业（紧前作业）的结束，又标志着在它之后的各项作业（紧后作业）的开始。如机械制造业中，只有完成铸锻件毛坯后，才能开始机加工；各种零部件都完工后，才能进行总装等。3.5.1.1计划评审方法网络图的一些基本概念事件①是开始进行初步设计的标志，称为该项作业的起点事件；事件②是初步设计的结束标志，称为该项作业的终点事件；将初步设计这项作业标记为（1，2）一般某项作业若起点事件为i，终点事件为j，将该作业标记为（i，j）作为整个计划评审方法网络图开始的事件称最初事件，整个计划评审方法网络图结束的事件称最终事件。3.5.1.1计划评审方法网络图的一些基本概念路线:指计划评审方法网络图中，从最初事件到最终事件的由各项作业连贯组成的一条路。图中从最初事件到最终事件可以有不同的路，路的长度是指完成该路上的各项作业持续事件的长度和。各项作业累计时间最长的那条路，称为关键路线，它决定完成网络图上所有作业需要的最短时间。3.5.1.1计划评审方法网络图的一些基本概念图中用双箭线表示的那条路是关键路线，需要11小时。3.5.1.2建立计划评审方法网络图的准则和注意事项任何作业在网络图中用惟一的箭线表示，任何作业其终点事件（箭头事件）的编号必须大于其起点事件（箭尾事件）的编号。若一项作业需分段进行，它应细分为不同作业，并用相应不同的箭线表示。两个事件之间只能画一条箭线，表示一项作业。对具有相同开始和结束事件的两项以上作业，要引进虚事件和虚作业。3.5.1.2建立计划评审方法网络图的准则和注意事项各项作业之间的关系及它们在计划评审方法网络图上的表达方式如下：作业a结束后可以开始b和c，见图（a）；作业c在a和b均结束后才能开始，见图（b）；b两项作业均结束后可以开始c和d，见图（c）；作业c在a结束后即可进行，但作业d必须同时在a和b结束后才能开始，见图（d）。3.5.1.2建立计划评审方法网络图的准则和注意事项任何计划评审方法网络图应有惟一的最初事件和惟一的最终事件。计划评审方法网络图中不允许出现回路计划评审方法网络图的画法一般从左到右，从上到下，同时为了方便计算和做到美观清晰,计划评审方法网络图中可以通过调整布局，尽量避免箭线之间的交叉3.5.2计划评审方法网络图的计算【例3.9】某项工程由11项作业组成（分别用代号A，B，…，J，K表示），其计划完成时间及作业间相互关系如表3-8所示D计划完成时间/d紧前作业作业计划完成时间/d紧前作业A5—G21B，EB10—H35B，EC11—I25B，ED4BJ15F，G，IE4AK20F，GF15C，D

3.5.2计划评审方法网络图的计算解:先按表3-8给出的资料画出计划评审方法网络图图中①为整个网络的最初事件，⑧为最终事件。标在箭线上面的时间是完成各项作业的计划时间。为了对网络图进行分析，需要计算作业的最早开始时间、最迟开始时间和作业的最早结束时间、最迟结束时间

及时差值。3.5.2计划评审方法网络图的计算第一步：作业的最早开始时间是它的各项紧前作业最早结束时间中的最大一个值，作业的最早结束时间是它的最早开始时间加上该作业的计划时间t（i，j）的值。用公式表示时有3.5.2计划评审方法网络图的计算3.5.2计划评审方法网络图的计算第二步；作业的最迟结束时间是它的各项紧后作业最迟开始时间中的最小一个，各项作业的紧后作业的开始时间应以不延误整个工期为原则。作业的最迟开始时间是它的最迟结束时间减去该项作业的时间。用公式来表示时有3.5.2计划评审方法网络图的计算3.5.2计划评审方法网络图的计算事件①是整个网络的初始事件，以它为起点的有三项作业。由此事件①的最迟实现时间为3.5.2计划评审方法网络图的计算第三步；时差。按性质可区分为作业的总时差R（i，j）和作业的自由时差F（i，j）。

R（i，j）是指网络上多于一项作业共同拥有的机动时间，并非为某项作业单独拥有。F（i，j）是指不影响它的各项紧后作业最早开工时间条件下，该项作业可以推迟的开工的最大时间限度。它是一项作业独自拥有的机动时间3.5.2计划评审方法网络图的计算

3.5.2计划评审方法网络图的计算12345678作业（i，j）t（i，j）tES（i，j）tEF（i，j）tLS（i，j）tLF（i，j）R（i，j）F（i，j）（1，2）5051610（1，3）1001001000（1，4）1101151653（2，5）45961011（3，4）41014121620（3，5）01010101000（4，6）151429163122（5，6）211031103100（5，7）251035113610（5，8）351045165166（6，7）03131363654（6，8）203151315100（7，8）1535503651113.5.2计划评审方法网络图的计算表的第1栏填写网络图上的全部作业。从起点事件中编号相同的作业，按终点事件编号由小到大填写；表的第2栏填写各项作业的计划时间

；依据公式（3-1）和（3-2）计算得出第3、4两栏的数字，其中第4栏数字为第2、3两栏数字之和。计算时假定

；依据公式（3-3）和（3-4）计算第5、6两栏数字，其中第5栏数字为第6栏数字与第2栏数字之差。计算时假定

，并从表的最下端往上推算；表中第7栏数字

按式（3-5）计算，为表中第6栏减去第4栏，或第5栏减去第3栏数字；表中第8栏数字

由公式（3-6）计算得到。3.5.3关键路线和网络计划的优化网络图中从最初事件到最终事件的不同的路中，作业总时间延续最长的一条路称关键路线。在这条路线上所有作业的总时差为零。3.5.3关键路线和网络计划的优化例3.9中关键路线的持续时间是51d，其他路线均有机动时间。为了缩短整个计划进程，就要设法缩短关键路线的持续时间，这就是网络图的优化或改进。检查关键路线上各项作业的计划时间是否订得恰当，如果订得过长，可适当缩短；将关键路线上的作业进一步分细，尽可能安排多工位或平行作业；抽调非关键路线上的人力、物力支援关键路线上的作业；有时也可通过重新制定工艺流程，也就是用改变网络图结构的办法来达到缩短时间的目的。不过这种方法工作量大，只有对整个工程的持续时间有十分严格的要求，而用其他方法均不能奏效的情况下才采用。3.5.3关键路线和网络计划的优化【例3.10】

假如例3.9所列的工程要求在49d完成。为加快进度，表3-10中列出了表3-9中可缩短工时的所有作业，表明这些作业计划完成时间（d）、最短完成时间（d）以及比原计划缩短一天额外增加的费用（元/d）。问应如何安排，使额外增加的总费用为最小。作业代号计划完成时间/d最短完成时间/d缩短1d增加的费用（1，3）B108700（1，4）C118400（2，5）E43450（5，6）G2116600（5，8）H3530500（5，7）I2522300（7，8）J1512400（6，8）K20165003.5.3关键路线和网络计划的优化3.5.3关键路线和网络计划的优化本例中关键路线上的作业有3项：B、G、K，其中作业K缩短1d的费用为最少。工期要求缩短3天，该项作业最多可缩短4天，但作业（7，8）的自由时差只有1天，即工程的工期缩短1天将出现新的关键路线，即有

，故决定先将作业（6，8）的完成时间缩短至19d，比原计划额外增加费用500元。3.5.3关键路线和网络计划的优化重复上述步骤，但注意到图3-26中有两条关键路线，工期均为50d。为进一步缩短工期，或单独缩短（1，3）工期，或在⑤—⑦—⑧或⑤—⑥—⑧两条双箭线上同时缩短工期。由于前者额外增加的费用少，故决定单独缩短作业

的工期。现工期还需缩短1d，该项作业最多可缩短2d，又工期再缩短1d后还将出现新的关键路线，即

。故决定将作业

缩短1d，再增加额外费用700元。由于已满足工期要求，就不需要继续调整。由此要求在49d完成表3.10所列工程项目，其计划评审方法网络图见图3-27，同时比正常施工，额外增加费用500+700=1200元。3.5.3关键路线和网络计划的优化3.5.3关键路线和网络计划的优化【例3.11】已知某工程双代号网络计划如图3-28所示，图中数字为工作的正常持续时间。已知该工程各项工作的优选系数和最短持续时间如表3-11。其中，优选系数是综合考虑质量、安全和费用增加情况确定的。选择关键工作压缩其持续时间时，应选择优选系数最小的关键工作。若需要同时压缩多个关键工作的持续时间时，则它们的优选系数之和最小者应优先作为压缩对象。现假设要求工期为15，试对其进行工期优化.工作代号ABCDEGHI优选系数28∞545102最短持续时间341431623.5.3关键路线和网络计划的优化3.5.3关键路线和网络计划的优化确定网络计划的关键路径和总工期。图3-28的关键路径为①—②—④—⑥，总工期为19。计算总工期应缩短的时间。用计划工期减去要求的工期，得应缩短的工期时间为19﹣15＝4。实施第1次优化。因为关键工作为A、D、H，且A的优选系数最小，所以先对A优化。由于工作A的最短持续时间为3，因此可以将工作A压缩2，即由5压缩至3。但通过计算知，改变后的网络计划中工作A变成了非关键工作。为了保证A仍为关键工作，再将工作A的持续时间延长为4，得到网络计划如图3-29所示。此时，图中有两条关键路径，即①—②—④—⑥和①—②—④—⑤。3.5.3关键路线和网络计划的优化3.5.3关键路线和网络计划的优化实施第2次优化。因为总工期为18，仍大于要求工期，所以需要继续优化。在图3-29中，有以下5个压缩方案：方案1

同时压缩工作A和B，组合优选系数为2＋8＝10。方案2

同时压缩工作A和E，组合优选系数为2＋4＝6。方案3

同时压缩工作B和D，组合优选系数为8＋5＝13。方案4

同时压缩工作D和E，组合优选系数为5＋4＝9。方案5

压缩工作H，优选系数为10。这五个方案中，由于第二个方案的组合优选系数最小，因此应该选择同时压缩工作A和E的方案。将这两项工作的持续时间各压缩1个单位（压缩至最短），再确定关键路径和计算总工期（图3-30）。此时，关键路径仍有两条，即①—②—④—⑥和①—③—④—⑤。3.5.3关键路线和网络计划的优化3.5.3关键路线和网络计划的优化实施第3次优化。因为总工期为17，仍大于要求工期，所以需要继续优化，在图3-30中，关键工作A和E已不能再压缩，因此只有两个压缩方案：方案1

同时压缩工作B和D，组合优选系数为8＋5＝13。方案2

压缩工作H，优选系数为10。这两个方案中，方案2的优选系数最小，因此应选择压缩工作H的方案。将工作H的持续时间缩短2，得到网络计划如图3-31所示。由于关键路径不变，所以总工期为15，已等于要求工期，故该方案为所求的优化方案。3.5.3关键路线和网络计划的优化【例3.12】某工程的时间成本如表3-12，工程网络图如图3-32所示。试对该工程网络计划的费用进行优化。工作代号ABCDEFGH合计时间（d）正常473521072

突击35232860

成本（万元）正常100280502001602302001001320突击2005201003601603504802002370成本费用率1001205080—60140100

3.5.3关键路线和网络计划的优化3.5.3关键路线和网络计划的优化根据正常时间，确定关键路径。由图3-32，易得网络计划的关键路径为①—②—④—⑤；关键工作为A、D、G；总工期16天，直接总成本1320万元。通过压缩关键工作的持续时间进行费用优化。方案1

将总工期压缩到15天。将关键工作中成本费用率最小的工作D压缩1天，工程的总成本增加80万元，即直接总成本为1400万元。并且关键路径和关键工作没有改变。3.5.3关键路线和网络计划的优化方案2

将总工期压缩到14天。将将关键工作中成本费用率最小的工作D再压缩1天，（图3-33），直接总成本为1480万元。这时，图3-33中有3条关键路径；①—②—⑤，①—②—④—⑤，①—④—⑤。D仍为关键工作。3.5.3关键路线和网络计划的优化方案3

将总工期压缩到13天。由图3-33可知，要缩短1天工期，必须使3条关键路径都缩短1天。但工作D已达到突击时间，所以不能再缩短了。比较各工作成本费用率后可知，使3条关键路径都缩短1天的最佳方案是：A、G各缩短1天，D增加1天，成本增加100＋140﹣80＝160（万元），直接总成本为1640万元（图3-34）3.5.3关键路线和网络计划的优化方案4将总工期压缩到天。最佳方案是：各缩短天，直接总成本为万元。方案5将总工期压缩到天。最佳方案是：各缩短天，直接总成本为万元。3.5.3关键路线和网络计划的优化如果整个工程的决定因素是工期，那么应选择方案5。如果整个工程的决定因素是成本，那么必须在这六个方案中寻则总成本最低的方案（方案2）。总工期（d）161514131211直接成本（万元）132014001480164018402100间接成本（万元）160015001400130012001100总成本（万元）2920290028882