《运筹学》 课件 第7章-图与网络

第7章图与网络17/16/2024CONTENTS2目录7/16/20247.1

图与网络的基本概念7.2

树7.3

最短路问题7.4

最大流问题7.5

最小费用流问题7.6

中国邮递员问题7.7

网络计划37/16/202418世纪，欧洲有一个风景秀丽的小城哥尼斯堡（今俄罗斯加里宁格勒）。那里的普莱格尔河上有七座桥，将河中的两个岛和河岸连结。城中的居民经常沿河过桥散步，于是提出了一个问题：一个人怎样才能一次走遍七座桥，每座桥只走过一次，最后回到出发点？大家都试图找出问题的答案，但是谁也解决不了这个问题………这就是哥尼斯堡七桥问题。

哥尼斯堡七桥问题47/16/2024LeonhardEuler(1707-1783)瑞士数学家他把这个难题进行了转换：把二岸和小岛缩成点，桥化为边，于是“七桥问题”就等价于下图（B）中所画图形的一笔画问题了。哥尼斯堡七桥问题经过研究，欧拉发现了一笔画的规律：i)能一笔画的图形必须是连通图ii)全部由偶点组成的连通图只有两个奇点其余均为偶点的连通图哥尼斯堡七桥问题57/16/202467/16/20241857年，英国数学家Hamiltion发明了一种游戏。他用一个实心正12面体象征地球，正12面体的20个顶点分别表示世界上20座名城，要求游戏者从任一城市出发，寻找一条可经由每个城市一次且仅一次再回到原出发点的路，也称“环球旅行”问题。图与网络哈密顿圈问题有位农夫，携带一匹狼、一只羊和一挑草要过一条小河。河中只有一条小船，一次摆渡农夫只能带狼、羊、草中的一样。当农夫不在场时，狼要吃羊，羊要吃草。试问农夫怎样才能将这三样东西摆渡到河对岸。至少要摆渡几次？农夫过河77/16/2024用M、W、S、G分别代表人、狼、羊、草。①[M,W,S,G][Ø]②[M,W][S,G]③[M,S][W,G] ④[M,G][W,S]⑤[M,W,S][G] ⑥[M,W,G][S]⑦[W,S,G][M] ⑧[M,S,G][W]上面组合中②、④、⑦是不允许的。去掉这三个组合中的六个状态，那么可能的状态有10个。按照状态中是否有人存在，将它们分为两组，如图所示。[M,W,S,G]V16VV72VV38VV49VV510V[M,S][W,G][

][G

][S

][W

][M,W,S][M,W,G][M,S,G]87/16/2024农夫过河中国邮递员问题(ChinesePostmanProblem,CPP):

一个邮递员负责一个地区的信件投递，他每天要从邮局出发，走遍该地区所有街道，最后返回到邮局，问如何安排送信的路线使所走路程最短？旅行售货商问题(TravelingSalesmanProblem,TSP):卖货郎走遍一个区域内的所有村庄一次，使得所走路程最短?要在若干个城市之间架设电网(或铺设管道),如何选择一个联系所有城市的电网(管网结构)?在一个已有的道路网络(管网、通信网络等)，已知每条线路(管道)的容量，网络上可通行的最大流量是多少？…………97/16/2024更多实用意义的问题实际应用7.1图与网络的基本概念自然界和人类社会中，大量的事物以及事物之间的关系可以用图形来描述。电路网络、城市规划、交通运输、物资调配……我们生活在一个网络社会中，从某种意义上说，现代社会是一个由各种网络所组成的复杂的网络系统。计算机信息网络电话通信网络运输服务网络能源和物资分派网络……01图与网络的基本概念7.1图与网络基本概念117/16/2024VS平面几何中的图关心图中有多少个点

关心点与点之间有无连线这里研究的图是反映对象之间关系的一种工具从形形色色的具体实际问题中抽象而来

研究其共同的性质、规律和方法7.1图与网络基本概念127/16/2024137/16/20247.1.1图与子图顶点/节点

(Vertex)物理实体、事物、概念一般用

vi

表示边

(Edge)节点间的连线，表示有关系一般用

eij

表示图

(Graph)节点和边的集合一般用

G(V,E)表示点集

V={v1,v2,…,vn}边集

E={eij}

无向图，有向图147/16/2024边都没有方向的图称为无向图，即

eij=eji或

(vi,vj)=(vj,vi)当边都有方向时，称为有向图，即在有序对

(vi,vj)中，vi表示始点，vj表示终点在有向图中，有向边又称为弧，用

aij表示，i,j的顺序是不能颠倒的，图中弧的方向用箭头标识图中既有边又有弧，称为混合图7.1.1图与子图环多重边注：有向图中两点之间有不同方向的两条边，不是多重边。

简单图，多重图一个边的两个端点如果相同，称为环两个点之间如果多于一条边，称为多重边不含环和多重边的图称为简单图；含有多重边的图称为多重图01图与网络的基本概念157/16/20247.1.1图与子图

完全图，偶图一个简单图中，若任意两点之间均有边相连，则称为完全图

n个顶点的完全图，边数有n(n-1)/2条若图的顶点能分成两个互不相交的非空集合

V1和V2，使在同一集合中的任意两个顶点均不相邻，称为偶图（二分图，bipartition）V1V2167/16/20247.1.1图与子图无向图中，与节点v关联的边数，称为该节点的次或度，记为deg(v)，或d(v)对任意节点v，若度数d(v)为奇数，则称此节点为奇点，若度数d(v)为偶数，则称此节点为偶点次为1的点称为悬挂点，所关联的边称为悬挂边次为0的点称为孤立点有向图中，由节点指向外的弧的数目称为正次数，记为d+，指向该节点的弧的数目称为负次数，记为d–177/16/2024

顶点的次（度，vertexdegree）7.1.1图与子图

顶点的次（度，vertexdegree）

定理1：图G=(V,E)中，所有点的次之和是边数的2倍：

其中m=|E|为边数。

定理2：任何图中，奇点的个数必为偶数。定理3：有向图中，所有顶点的入次之和等于所有顶点的出次之和。01图与网络的基本概念187/16/20247.1.1图与子图

子图设有图

G＝(V,E)和图

G’＝(V’,E’),若

G

和

G’满足：若V’

V，E’

E，则称G’是G的子图

Subgraph,记为

G’

G；特别,若V’＝V，E’

E，则称G’是G的生成子图(支撑图)

SpanningSubgraph;197/16/20247.1.1图与子图207/16/20247.1.2赋权图与图联系在一起的，通常还有与点或边有关的某些数量指标，我们常称之为“权”，权可以代表距离、费用、通过能力（容量）等等。这种点或边带有某种数量指标的图称为赋权图（weightedgraph）权矩阵weightedmatrix867452493v1v5v4v2v3v1v2v3v4v5v1v2v3v4v5217/16/20247.1.2赋权图邻接矩阵adjacentmatrixv1v2v4v3v5v6若G为无向图，则邻接矩阵为对称矩阵。v1v2v3v4v5v6v1v2v3v4v5v67.1.2赋权图227/16/2024关联矩阵incidencematrixv1v2v4v3v5v6e1e2e3e4e5e6e7e8e9e10v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10

A

每一列元素和等于2

A每一行元素和等于对应顶点的次数237/16/20247.1.2赋权图

链，圈，道路，回路设G

=

(V,

E)

是一个无向图，考虑图G中边的序列：[v0,v1],[v1,v2],[v2,v3],…,[vk-1,vk]，简单地记为(v0,v1,v2,v3,…,vk-1,vk)，在这个序列中，任意一条边的终点都是下一条边的始点，称此边的序列为图的一条链link若一条链中v0＝vk，则称为圈loop对有向图,可以类似地定义链和圈对有向图G=(V,E)，当链（圈）上边的方向相同时，称为道路path（回路circuit）01图与网络的基本概念7.1.3链，路，圈与回路247/16/2024连通图(Connectedgraph)：在一个图中，每一对顶点之间至少存在一条链否则为不连通图257/16/2024

连通图7.1.3链，路，圈与回路7.2树

树的定义：连通且不含圈的无向图多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图ExploitingSection开发部Programming规划发展部GeneralWorker’s总工办Property物业部Engineering工程部MaterialPurchasing材料采购部FinancingSection财务部Multioffice综合办公室董事会Directorate监事会Intendancy副总经理DeputyGeneralManager总经理GeneralManager经营部门ManagementDepartment职能部门FunctionDepartment某公司组织结构图7.2.1树的概念277/16/2024连通、无圈；设顶点数为|V|=n，边数为|E|=m，那么m=n-1;任意两点之间有且仅有一条链；去掉任意一条边，就不连通；增加任意一条边，就得到一个且仅一个圈；287/16/20247.2.1树的概念设G＝(V,E)是一个连通的无向图，若G的某个生成子图是一棵树，则称该树为G的生成树(支撑树)SpanningTree，记为TG。图(c)是上图(a)的生成子树，而图(d)所示的树T3，则不是图(a)的生成子树。图(b)是(a)的生成子图但不是生成树。7.2.2图的支撑树297/16/2024定理：图G有生成树（支撑树）的充要条件是图G是连通的。如何找到一棵生成树？破圈法：每次去掉圈中的一条边，其去掉的边的总数为m－(n－1)；避圈法：每次选取G中的一条边，该边不能与已经选取的边构成回路，此时，选取的边的总数为(n－1)。307/16/20247.2.2图的支撑树求右图(a)中的生成子树。317/16/20241.破圈法：7.2.2图的支撑树求右图(a)中的生成子树。327/16/20242.避圈法：7.2.2图的支撑树破圈法337/16/20247.2.2图的支撑树在架设电话线，铺设自来水或暖气管道的工程设计中会遇到如下的优化问题：如何相互连通，由使得总线路长度最短？例：某居民区五栋楼的分布如图。每条边旁的数字表示水塔与各楼间的距离。试求最短的管道铺设方案。最小支撑树问题7.2.3最小支撑树问题347/16/2024设有一个连通图G=(V,E)，每一边

eij=[vi,vj]有一个非负权

w(eij)=wij(wij≥0)如果T=(V,E’)，是

G的一个支撑树，称E’中所有边的权之和为支撑树

T

的权，记为

w(T)如果支撑树

T*的权

w(T*)是

G的所有支撑树的权中最小者，则称

T*是

G的最小支撑树（最小生成树），即357/16/20247.2.3最小支撑树问题求G的最小生成树的方法有二：避圈法Kruskal破圈法该算法是克鲁斯克尔(Kruskal)于1956年将构造生成树的避圈法推广到求最小生成树的结果，其要点是，在与已选取的边不构成圈的边中选取最小者。避圈法：367/16/20247.2.3最小支撑树问题7.3最短路问题例

已知如图所示的单行线交通网，每弧旁的数字表示这条单行线的距离。现在某人要从

v1出发，通过这个交通网到达

v8

，求使总距离最短的旅行线路。387/16/2024v1v7v2v5616321v32v4v610310v8v924623403最短路问题7.3.1最短路问题概述例

已知如图所示的单行线交通网，每弧旁的数字表示这条单行线的距离。现在某人要从

v1出发，通过这个交通网到达

v8

，求使总距离最短的旅行线路。397/16/20241+10+2+4=176+1+6=133+2+1+3+4=133+2+10+10+6=31可行路线有多条！哪一条最短？v1v7v2v5616321v32v4v610310v8v924623403最短路问题7.3.1最短路问题概述给定一个赋权有向图D=(V,A),对每一弧a=(vi

,

vj

)相应地有权w(a)=wij给定D中的两个顶点

vs和

vt，设

P是D中从

vs到

vt的一条路，定义路P的权是P中所有弧的权之和，即w(P)最短路问题就是要在所有从vs到vt的可行路中，求一条权最小的路记P0是从vs到vt的最短路，路P0的权为从vs到vt的距离，记为d(vs

,

vt

)

407/16/20247.3.1最短路问题概述——求无负权网络最短路的最好方法之一基本原理：v1

v4

v6

v5

v7如果这是v1到达v7的最短路，那么也是v1到达该路径上任意点的最短路。Dijkstra算法逐点求最短路03最短路问题7.3.2Dijkstra算法417/16/2024对每个节点，用两种标号：T和P（表示从始点到该节点的距离）T是目前路径的距离(TentativeLabel)P是最短距离(PermanentLabel)开始时，令始点有P=0，记P标号，其它节点有T=M/∞不断改进T值，当其最小时，将其改为P标号当所有的标号都为P时，找到最短路427/16/20247.3.2Dijkstra算法标号过程分为两步：437/16/2024Step1.修改T标号。Step2.产生新的P标号。原则：在现有的T标号中将值最小者改为P标号。03最短路问题7.3.2Dijkstra算法v1

v7的最短路径？447/16/20247.3.2Dijkstra算法-例题03最短路问题457/16/20247.3.2Dijkstra算法-例题467/16/20247.3.2Dijkstra算法-例题03最短路问题477/16/20247.3.2Dijkstra算法-例题487/16/20247.3.2Dijkstra算法-例题497/16/20247.3.2Dijkstra算法-例题=12507/16/20247.3.2Dijkstra算法-例题517/16/20247.3.2Dijkstra算法-例题使用双标号527/16/20247.3.2Dijkstra算法-例题Ford算法算例537/16/20247.3.2Dijkstra算法-例题Dijkstra算法提供了从网络图中某一点到其它点的最短路。但实际问题中往往要求网络任意两点之间的最短距离，用Dijkstra算法就要对每个点分别计算，很麻烦。Floyd算法（基于权矩阵）n个顶点：的元素就是vi到vj的最短路权。7.3.3Floyd算法547/16/2024例：求图中各点之间的最短距离557/16/2024v1v2v3v4v5v10512∞v25010∞2v323028v42∞604v5∞24405242121026348D(0)v1v2v5v4v37.3.3Floyd算法-例题v1v2v3v4v5v10512∞v25010∞2v323028v42∞604v5∞2440D(0)v1v2v3v4v5v10512∞v250672v323028v427304v5∞2440D(1)D(2)D(3)v1v2v3v4v5v105127v250672v323025v427304v572440v1v2v3v4v5v104126v250672v323025v426304v56244003最短路问题567/16/20247.3.3Floyd算法-例题D(3)v1v2v3v4v5v104126v250672v323025v426304v562440D(4)v1v2v3v4v5v104126v250672v323025v426304v562440D(5)v1v2v3v4v5v104126v250662v323025v426304v562440577/16/20247.3.3Floyd算法-例题587/16/20247.3.4旅行销售商的问题在线路优化中，从起始节点开始，要选择一条合适的路径经过所有已知的节点各一次，并最后回到起始节点，要求所走距离最短。这一问题就是著名的旅行销售商问题(TSP,TravelingSalesmanProblem，也称货郎担问题）它可以抽象地叙述如下：从一个起始点出发到达所有要求服务的n个点，而且只到达一次，再回到起始点（即哈密尔顿回路）。已知任意两点i、j间的距离dij，要求在所有可供考虑的路线中选择路径最短的旅行路线597/16/2024TSP的数学模型如下：这里

xij=1表示从

i直接去

j，否则

xij=0。第3个约束条件，式（7.6）保证路径无子回路(subtour)，其中参数

ui为连续变量(i=1,2,…,n)，也可以取整数值7.3.4旅行销售商的问题607/16/2024求解TSP问题的一种著名启发式算法——最近插入法（closestinsertionalgorithm），它是由Rosenkrantz和Stearnes等人在1977年提出的一种TSP算法,步骤为：找到d1m最小的节点vm，形成一个子回路T={v1,vm,v1}在剩下的节点中，寻找一个离上子回路中某一节点最近的节点vk；在子回路中找到一条弧(i,j)，使得dik+dkj-

dij最小，然后将节点vk插入到节点vi，vj之间，用两条新的弧(i,k)，(k,j)代替原来的弧(i,j)，并将节点vk加入到子回路中；重复2、3步骤，直到所有的节点都加入子回路中。

此时的回路就演变成了TSP的一个解（哈密尔顿回路）。最近插入法可以方便地用计算机求解。7.3.4旅行销售商的问题617/16/2024求解TSP问题时，对于小型问题还可以求得最优解，最简单的方法是枚举法。但是对于大型问题，由于枚举法的例举次数为(n-1)!次，它的数量是非常庞大的！整数规划的分枝定界法也可以解决部分TSP问题，但也只能是小规模的求解。如果模型中去掉“无子回路”的约束，它就是线性的指派问题（LAP）了，可以用匈牙利算法求出最优解。因此先求出TSP对应的LAP问题，可以为TSP问题提供一个下界，再用分枝定界法求解。总之，TSP模型是一个非线性规划NP-Hard问题，对于大规模问题无法获得最优解，只有通过启发式算法获得近似解。启发式算法不仅可以用于各种复杂的TSP问题，也适用于中小规模问题7.3.4旅行销售商的问题7.4最大流问题

对网络流的研究是在容量网络上进行的容量网络是指网络上的每一条弧(vi,vj)都有一个最大的通过能力，称为该弧的容量

c(vi,vj)，

cij在网络图中通常规定一个发点（s）和一个收点（t），其余为中间点网络最大流是指从发点到收点间允许通过的最大流量对有多个发点或收点的网络，另虚设一个总发点或总收点容量网络637/16/20247.4.1网络流的基本概念流与可行流流是加在网络各条弧上的一组负载量对加在弧

(vi,vj)上的负载量记作

f(vi,vj),

fij若网络上所有的

fij

=0，则这个流称为零流满足容量限制条件和平衡条件的一组流为可行流容量限制条件：对所有弧有

0≤fij

≤cij中间点平衡条件：

∑

fij－∑fji＝0(i≠s,t)若以

W

表示网络中从s

t的流量，则有647/16/2024

收发点平衡条件7.4.1网络流的基本概念任何网络上一定存在可行流（零流就是可行流）所谓求网络最大流，是指满足容量限制条件和中间点平衡条件下，使

W

值达到最大这是一个线性规划问题，但图论方法更简单657/16/20247.4.1网络流的基本概念割：将容量网络中的发点和收点分开，并使发点到收点的流中断的一组边的集合667/16/2024v1s8(8)2(0)9(4)5(4)7(5)v3v2v49(9)6(1)t10(8)5(5)KKKK将网络上的点分割成V和V’两个集合，且有s∈V,t∈V’。边的集合

(V,V’)={(v3,t),(v4,v3),(v2,v4)}是一个割。7.4.1网络流的基本概念v1s8(8)2(0)9(4)5(4)7(5)v3v2v49(9)6(1)t10(8)5(5)割集容量是指所有始点在V，终点在V’的弧的容量之和7+8=159+5+7=219+9=185+9=14KK割集有多个，其中割集容量最小者称为最小割。677/16/20247.4.1网络流的基本概念若用

f(V,V’)表示通过割(V,V’)中所有V

V’方向弧的流量的总和

f(V’,V)表示通过割(V,V’)中所有V’

V方向弧的流量的总和从s

t的流量实际上等于通过割的从V

V’的流量减去V’

V的流量，即W

=f(V,V’)－f(V’,V)7.4.2求解网络最大流的基本原理687/16/2024若用W*代表网络中从s

t的最大流，C*(V,V’)代表网络中最小的一个割的容量，则W*=C*(V,V’)割集是从s

t

的必经之路任何一个可行流的流量不会超过任一割集的容量W≤C(V,V’)

——

最大流-最小割定理MaxW≤Min

C(V,V’)

697/16/20247.4.2求解网络最大流的基本原理如果在网络的发点和收点之间存在一条链，那么在这条链上所有指向为“发点到收点”的弧称为前向弧，记为m+所有指向为相反的弧称为后向弧，记为m－在所有的前向弧上，流量

<容量；在所有的后向弧上，流量

>0；则称这条链为增广链(不饱和链)前向弧，后向弧增广链如果707/16/20247.4.2求解网络最大流的基本原理显然f’仍然是一个可行流，但比原来的可行流f在s

t方向上增大了一个正的q

值因此只有当网络上找不到增广链时，s

t的流才不可能再增大

当有增广链存在时，找出再令717/16/20247.4.2求解网络最大流的基本原理定理：可行流

f为最大流的充分必要条件是当且仅当网络不存在增广链给出一初始可行流，例如寻找增广链，若存在，则通过该增广链调整、增加网络流若不存在增广链，则网络流不可再增加。求得最大流727/16/20247.4.2求解网络最大流的基本原理标号算法Ford-Fulkerson

1.首先给发点标号(

0,δs)737/16/2024使这个点得到标号的前一个点的代号。因s是发点，故记为0δs

是从上一标号点到这个标号点的流量的最大允许调整值。因s是发点，不允许调整，故

δs=+∞7.4.3求解网络最大流的标号法2.列出与已标号点相邻的所有未标号点：(1)考虑从标号点

i出发的所有弧(i,j)，如果fij=cij，不给点j标号若fij<cij对j标号，记为(+vi,δj

),其中δj

=min{δi

,cij-fij}(2)考虑所有指向点i的弧(j,i)，如果fji=0，不给点j标号若fji>0

对j标号，记为(-vi,δj

),其中δj

=min{δi

,fji}747/16/2024如果某未标号点k

有两个以上相邻的标号点，为减少迭代次数，可按(1)(2)分别计算出δk

值，并取其中最大一个标记。7.4.3求解网络最大流的标号法3.重复第2步，可能出现两种结局：(1)标号过程中断，点

t得不到标号，说明该网络中不存在增广链，给定的流量即为最大流记已标号点的集合为V，未标号点集合为V’(V,V’)即为网络的最小割(2)点t得到标号，这时可用反向追踪法在网络中找出一条从s

t的由标号点及相应弧连接而成的增广链4.修改流量。设图中原有可行流为

f，令757/16/20247.4.3求解网络最大流的标号法5.抹掉图上所有标号。重复第1到第4步，直到图中找不出任何增广链，即第3步中的(1)为止，这时网络图中的流量即为最大流。767/16/2024v1s8(8)2(0)9(4)7(5)v3v2v49(9)6(1)t10(8)5(5)5(4)7.4.3求解网络最大流的标号法v1s8(8)2(0)9(4)5(4)7(5)v3v2v49(9)6(1)t10(8)5(5)(0,∞)(s,2)(v2,2)(v1,2)(v3,1)(v4,1)增广链7(6)5(3)9(5)6(0)10(9)777/16/2024标号法算例v1s8(8)2(0)v3v2v49(9)t5(5)(0,∞)(s,1)(v2,1)(v1,1)重复上述标号过程7(6)5(3)9(5)6(0)10(9)已再无增广链，故可行流即为最大流W*=14KK787/16/2024标号法算例7.5最小费用流问题给定网络

G=(V,A,C,d)和经过网络的流量

W(f)=v，求流在网络上的最佳分布，使总费用最小。807/16/20247.5.1最小费用流的问题定义增广链费用，最小费用增广链。对于最小费用可行流，沿最小费用增广链调整流，可使流增加，并保持流费用最小。给定初始最小费用可行流，求最小费用增广链，若存在，则沿该增广链调整网络流，直到达到给定的网络流或不存在增广链为止，后一种情况为最小费用最大流。若给定网络流超过最大流，则不可能实现。817/16/20247.5.2求解最小费用流的赋权图法生成最小费用可行流的剩余网络：将饱和弧反向将非饱和非零流弧加一反向弧零流弧不变所有前向弧的权为该弧的费用，后向弧的权为该弧费用的相反数剩余网络又叫长度网络最小费用增广链对应剩余网络的最短路827/16/20247.5.2求解最小费用流的赋权图法837/16/20247.5.2求解最小费用流的赋权图法第1次剩余网络最短路847/16/2024赋权图法-算例第1次调整网络流857/16/2024赋权图法-算例第2次剩余网络最短路867/16/2024赋权图法-算例第2次调整网络流877/16/2024赋权图法-算例第3次剩余网络最短路887/16/2024-2赋权图法-算例第3次调整网络流897/16/2024赋权图法-算例剩余网络已不存在最短路907/16/2024赋权图法-算例917/16/2024赋权图法-算例

7.6中国邮递员问题937/16/20247.6中国邮递员问题一个邮递员送信，要走完负责投递的全部街道，完成任务后回到邮局，应该按照怎样的线路走，所走的路程最短。这是我国学者管梅谷1962年提出的问题，在国际上通称为中国邮递员问题。这一问题的介绍首先要从图论中最早的哥尼斯堡七桥问题开始947/16/20247.6.1哥尼斯堡七桥问题与欧拉图连通图G中，若存在一条链，经过每条边一次且仅一次，则称这条链为欧拉链（Eulerpath）。若存在一条圈，经过每条边一次且仅一次，则称这条回路为欧拉圈（Eulercircuit）。定理1：无向连通图G是欧拉图，当且仅当G中无奇点推论

连通多重图G有欧拉圈，当且仅当G恰有两个奇点根据定理来检查哥尼斯堡七桥问题，从图(B)中可以看到d(A)=3,d(B)=3,d(C)=5,d(D)=3，有四个奇点，所以不是欧拉图，即这样的走法不存在957/16/20247.6.2中国邮递员问题定义定义：给定一个连通图G，每边有非负权l(e)，要求一条回路过每边至少一次，且满足总权最小。此种问题为中国邮递员问题。由定理知，如果G没有奇点，则是一个欧拉图，显然按欧拉回路走就是满足要求的过每边至少一次且总权最小的回路。

如果G中有奇点，要求连续走过每边至少一次，必然有些边不止一次走过，这相当于在图G中对某些边增加一些重复边，使所得到的新图G*没有奇点且满足总路程最短。967/16/2024由于总路程的长短完全取决于所增加的重复边的长度，所以中国邮路问题也可以转为如下问题在连通图G=(V,E)中，求一个边集E1∈E，把G中属于E1的边均变为二重边得到图G*=G+E1，使其满足G*无奇点，且最小。定理2

已知图G*=G+E1无奇点，则最小的充要条件为：(1)每条边最多重复一次；(2)对图G中每个初等圈来讲，重复边的长度和不超过圈长的一半。7.6.2中国邮递员问题定义977/16/2024定理2的证明，给出了中国邮路问题的一种算法，称为“奇偶点图上作业法”，它的思路是：先对一个有奇点的图增加重复边转变为不含奇点的欧拉图，这样的重复边方案为可行方案，然后再寻求对重复边总长减少的改进方案，最后找到使总长最短的可行方案就是所求的解。下面举例说明这个算法求解下图所示网络的中国邮路问题。图a图b7.6.2中国邮递员问题的求解7/16/202498第1步：确定初始可行方案先检查图中是否有奇点，如无奇点则已是欧拉图，找出欧拉回路即可。如有奇点，由前知奇点个数必为偶数个，所以可以两两配对。每对点间选一条路，使这条路上均为二重边。图中有四个奇点v2,v4,v6,v8（空心点表示），将v2与v4，v6与v8配对，联结v2与v4的路有好几条，任取一条，如｛v2,v3,v6,v9,v8,v7,v4｝，类似地，对v6与v8取｛v6,v3,v2,v1,v4,v7,v8｝。得到图b，已是欧拉图。对应这个可行方案，重复边的总长为2l23+2l36+l69+l98+2l87+2l74+l41+l12=517.6.2中国邮递员问题的求解7/16/202499第2步：调整可行方案，使重复边最多为一次去掉[v2,v3]，[v3,v6]，[v4,v7]，[v7,v8]各两条，得到图c，重复边总长度下降为：l12+l14+l69+l98=21第3步：检查图中每个初等圈是否满足定理7.10条件(2)。如不满足则进行调整，直至满足为止。检查图c，发现圈｛v1,v2,v5,v4,v1｝总长度为24，而重复边的长为14，大于该圈总长度的一半，可以作一次调整，以[v2,v5]，[v5,v4]代替[v1,v2]，[v1,v4]，得到图d，重复边总长度下降为：l25+l43+l69+l98=17再检查图d，圈｛v3,v6,v9,v8,v5,v2,v3｝总长度为24，而重复边长为13。再次调整得图e，重复边总长度为15。检查图e，条件(1),(2)均满足，得到最优方案7.6.2中国邮递员问题的求解7/16/2024100图c图d图e图中任一欧拉回路即为最优邮递路线。7.6.2中国邮递员问题的求解7.7网络计划网络计划起源与发展1917年，亨利·甘特发明了著名的甘特图GanttChart（也称横道图），使项目经理按日历制作任务图表，用于日常工作安排1956年，美国杜邦公司将关键路径法（CPM）应用于设备维修，使维修停工时间由125小时锐减为7小时

1958年，美国海军特种计划局在北极星导弹设计中，应用计划评审技术（PERT），将项目任务之间的关系模型化，使设计完成时间缩短了2年

1962年美国国防部规定：以后承包有关工程的单位都应采用网络计划技术来安排计划前言7/16/202410260年代初，我国著名数学家华罗庚教授将此技术介绍到中国，并把它称为“统筹法”国内外应用网络计划的实践表明，它具有一系列优点

特别适用于生产技术复杂，工作项目繁多、且联系紧密的一些跨部门的工作计划新产品研制开发、大型工程项目、生产技术准备、设备大修等计划、资源安排、工作流程以下主要介绍CPM。编制网络计划包括绘制网络图，计算时间参数，确定关键路线及网络优化等环节网络计划起源与发展7/16/2024103前言网络计划与横道计划的比较简单、清晰、形象、易懂、使用方便；施工过程施工进度（天）2468101214161820支模10人绑钢筋15人浇混凝土10人优点：可以直接在图中进行各项资源需要量统计。102510劳动力动态消耗图1047/16/2024前言不能直接反映各施工过程之间相互联系、相互制约的逻辑关系不能明确指出那些工作是关键工作，那些工作不是关键工作不能计算各工作的时间参数，看不到计划的潜力不能应用计算机进行调整和优化缺点：网络计划与横道计划的比较1057/16/2024前言1213456支模1绑钢筋1浇混凝土1446支模2绑钢筋2浇混凝土2426施工过程施工进度（天）2468101214161820支模10人绑钢筋15人浇混凝土10人网络计划与横道计划的比较1067/16/2024前言1213456支模1绑钢筋1浇混凝土1446支模2绑钢筋2浇混凝土2426能全面而明确地反映各施工过程之间相互联系、相互制约的逻辑关系；通过时间参数的计算，能够找出关键施工过程和关键线路，便于管理者抓住主要矛盾；通过时间参数的计算，可以对网络计划进行调整和优化；优点：网络计划与横道计划的比较1077/16/2024前言7.7.1网络图绘制网络图绘制1网络图的构成2网络图的基本画法3绘制网络图的基本原则1087/16/2024网络图是由作业、事项（节点）和路线三大部分组成作业（工作、工序、活动），箭线表示，一般箭线之上表示工作名称，之下表示工作时间1097/16/2024作业一般分为两种：消耗一定的时间与资源的工作――实工作，用实箭线表示既不消耗时间也不消耗资源的工作――虚工作，虚设的工作，只表示前后工作之间的逻辑关系，用虚箭线表示“双代号表示法”网络图的构成

事项，节点表示，表示前面工作结束和后面工作开始的时间点，表示工作结束和开始的瞬间，既不消耗时间也不消耗资源1213456支模1绑钢筋1浇混凝土1446支模2绑钢筋2浇混凝土2426起始节点终点节点中间节点1107/16/2024网络图的构成1213456支模1绑钢筋1浇混凝土1446支模2绑钢筋2浇混凝土2426节点的编号:从左到右，由小到大；箭尾编号小于箭头编号,即i＜j

；编码可以不连续，但不可以重复。1117/16/2024网络图的构成

路线，网络图中，从起始节点开始，沿箭线方向连续通过一系列节点和箭线，最后到达终点节点的若干条通道，称为路线124AC5B2D4E5G3F56351①→②→④→⑥（8天）①→②→③→④→⑥（10天）①→②→③→⑤→⑥（9天）①→③→④→⑥（14天）①→③→⑤→⑥（13天）1127/16/2024网络图的构成第四条线路耗时最长（14天），对整个工程的完工起着决定性的作用，称为关键线路；其余线路均称为非关键线路。处于关键线路上的各项工作称为关键工作。关键工作完成的快慢将直接影响整个计划工期的实现。关键线路上的箭线常采用粗线、双线或其它颜色的箭线突出表示。

位于非关键线路上的工作除关键工作外，都称为非关键工作，它们都有机动时间(即时差)；非关键工作也不是一成不变的，它可以转化成关键工作；利用非关键工作的机动时间可以科学地、合理地调配资源和对网络计划进行优化。

1137/16/2024网络图的构成1147/16/2024网络图的基本画法在一个大的工程项目中，各作业之间的关系是很复杂的，有的按顺序进行，有的同时进行，有的需要在几项作业完成后才能开始，有的交叉进行，等等。为了表示这些不同的情况，引入四种不同的表示法作业的串联：表示按时间的先后次序进行的作业之间的关系。必须完成的作业称为先行作业（紧前作业），继这些作业之后开始的称为紧后作业。例如在下图中，作业G完成之后H才能开始，则G是H的紧前作业，H是G的紧后作业。1157/16/2024作业的并联：表示两个或两上以上的作业同时进行的关系，如图7.21作业B,C是在作业A之后平行进行的。则A为B,C的紧前作业，或者说B,C为A的紧后作业。3和4之间的虚作业表示E的紧前作业是B,C，只有在B,C都完成后E才能开始。网络图的基本画法1167/16/2024作业的交叉：两个及以上的作业，部分地交错进行时，要用作业的交叉表示，如图所示。作业的合并：把两个及以上的作业简化合并成一个更大的作业称为作业的合并，合并后的作业时间，按原图中两个结点之间的最长路线计算。网络图的基本画法网络图只能一个开始节点，一个终止节点网络图应从左向右延伸，编号应从小到大，且不重复。箭头事项编号大于箭尾事项编号不能出现循环路线（即不允许有回路）236541绘制网络图的基本原则1177/16/2024两事项间只能有一项作业改为箭线的首尾都必须有节点131211配砂造型14131211造型配砂2配砂1

1187/16/2024绘制网络图的基本原则网络图要布局规整、条理清晰、重点突出。绘制网络图时，应尽量采用水平箭线和垂直箭线而形成网格结构，尽量减少斜箭线，使网络图规整、清晰。其次，应尽量把关键工作和关键线路布置在中心位置，尽可能把密切相连的工作安排在一起，以突出重点，便于使用。1197/16/20241234EBDACF（a）有交叉和斜向箭线的网络图1234EFDCAB（b）调整后的网络图绘制网络图的基本原则ABABCABCABCACB序号工作之间的逻辑关系网络图中的表示方法说明1A工作完成后进行B工作A工作制约着B工作的开始，B工作依赖着A工作2A、B、C三项工作同时开始

A、B、C三项工作称为平行工作3A、B、C三项工作同时结束A、B、C三项工作称为平行工作4有A、B、C三项工作。只有A完成后，B、C才能开始A工作制约着B、C工作的开始，B、C为平行工作5有A、B、C三项工作。C工作只有在A、B完成后才能开始C工作依赖着A、B工作，A、B为平行工作1207/16/2024绘制网络图的基本原则BACDACBDiDA1B1A2A3B2B3ADBCE6有A、B、C、D四项工作。只有当A、B完成后，C、D才能开始通过中间节点i正确地表达了A、B、C、D工作之间的关系7有A、B、C、D四项工作。A完成后C才能开始，A、B完成后D才能开始D与A之间引人了逻辑连接（虚工作），从而正确地表达了它们之间的制约关系8有A、B、C、D、E五项工作。A、B完成后C才能开始，B、D完成后E才能开始虚工作i-j反映出C工作受到B工作的制约；虚工作i-k反映出E工作受到B工作的制约9有A、B、C、D、E五项工作。A、B、C完成后D才能开始，B、C完成后E才能开始虚工作反映出D工作受到B、C工作的制约10A、B两项工作分三个施工段，平行施工每个工种工程建立专业工作队，在每个施工段上进行流水作业，虚工作表达了工种间的工作面关系ACBE

i

j

k1217/16/2024绘制网络图的基本原则任务分解(WorkBreakdownStructure,WBS)绘制网络图节点编号作业分析表网络图的绘制实例1227/16/2024试探性绘制法：试探1237/16/2024网络图的绘制实例试探性绘制法：修改1247/16/2024网络图的绘制实例流程图过渡绘制法：流程图1257/16/2024网络图的绘制实例流程图过渡绘制法：加事项1267/16/2024网络图的绘制实例流程图过渡绘制法：去方框1277/16/2024网络图的绘制实例流程图过渡绘制法：修改1287/16/2024网络图的绘制实例网络图绘制，只是用网络的形式表达出了工作之间的逻辑关系。还必须通过计算求出工期，得到一定的时间参数计算网络图中有关的时间参数，主要目的是找出关键路线，为网络计划的优化、调整和执行提供明确的时间概念时间参数：工序所需时间、事项最早、最迟的时间、工序的最早、最迟时间及时差7.7.2网络图的时间参数计算1297/16/2024完成一项工序所需时间确定，只给出一个时间值CPM在影响工序因素较多，作业时间难以准确估计时，采用三点时间PERTa—最快可能完成时间m—最可能完成时间b—最慢可能完成时间1307/16/2024确定型概率型作业时间的确定事项（节点）的最早时间——tE(j)表示以j为始点的各工序最早可能开始的时间，也表示以j为终点的各工序均完成的最早可能时间起始节点的最早开始时间为0，即tE(1)=0

tE(j)=max{tE(i)+t(i,j)}i,j

分别代表箭尾和箭头事件从起始节点开始,正向计算1317/16/2024i节点时间参数及计算事项（节点）最迟时间——tL(i)表示在不影响任务总工期的条件下，以i为始点的各工序最迟必须开始时间，或以i为终点的各工作的最迟必须完成时间一般将任务的最早完工时间作为任务的总工期

tL(n)=tE(n)

n为终点事项

tL(i)=min{tL(j)–t(i,j)}i,j

分别代表箭尾和箭头事件从终点节点开始,反向计算，即从编号大到小顺序1327/16/2024j节点时间参数及计算计算各事项的最早时间和最迟时间。1337/16/2024节点时间参数及计算-例题时间参数的图上计算法1347/16/2024节点时间参数及计算-例题工序的最早可能开工时间——tES(i,j)任何一个工序都必须在其所有紧前工序全部完成后才能开始工序的最早可能完工时间——tEF(i,j)表示工作按最早开工时间开始所能达到的完工时间tES(1,j)=0tES(i,j)=max{tES(k,i)+t(k,i)}tEF(i,j)=tES(i,j)+t(i,j)tES(i,j)=tE(i)1357/16/2024EarlyFinishEarlyStarttEF(i,j)=tE(i)+

t(i,j)作业时间参数及计算

工序的最迟必须开工时间——tLS(i,j)表示工序(i,j)在不影响整个任务如期完成的前提下，必须开始的最晚时间工序的最迟必须完工时间——tLF(i,j)表示工作(i,j)按最迟时间开工，所达到的完工时间tLF(i,n)=tL(n)=tE(n)tLS(i,j)=min{tLS(j,k)-t(i,j)}tLF(i,j)=tLS(i,j)+t(i,j)