运筹学06图与网络分析.ppt

《运筹学06图与网络分析.ppt》由会员分享，可在线阅读，更多相关《运筹学06图与网络分析.ppt（115页珍藏版）》请在三一办公上搜索。

1、图与网络分析Graph Theory and Network Analysis,图的基本概念Basic Concepts of Graph最小支撑树问题The Minimal Spanning Tree Problem最短路问题The Shortest Route/Path Problem最大流问题The Maximal Flow Problem最小费用最大流The Minimal Cost&Maximal Flow中国邮递员问题Chinese Postman Problem网络计划技术Network Planning Technology,1 图的基本概念,案例导引图论中的图图的矩阵描述,案

2、例导引,图论是运筹学的一个重要分支，对其最早的研究可以追溯到著名的哥尼斯堡七桥问题(Konigsberg Bridges Problem)。18世纪，欧洲的哥尼斯堡城有一条流经全城的普雷戈尔河，河的两岸与河中两个小岛及两岛之间有七座桥彼此相通(如左图)。当时人们关心这样的问题，即从陆地A,B,C,D中的任意地方出发，能否通过每座桥一次且仅通过一次，就能返回原出发地。,1736年，瑞士数学家欧拉(E.Euler,1707-1783)当时正在圣彼得堡科学院工作，为俄罗斯女皇凯瑟琳服务。欧拉将这个问题抽象化，用含有4个点7条边的图形表示此问题(如右图)，发表依据几何位置的解题方法的论文，有效地解决了

3、哥尼斯堡七桥问题。标志着欧拉创立了一个数学分枝，即后来人们所熟知的拓扑学(Topology)。图论的第一部专著是匈牙利数学家O.Konig于1936出版的有限图与无限图的理论。,哥尼斯堡七桥问题：在图中找一条经过每边一次且仅一次的路欧拉回路。,由点和边组成,环球旅行问题在图中找一条经过每个点一次且仅一次的路哈密尔顿回路。中国邮路问题在图中找一条经过每边的最短路类似带权的欧拉回路。货郎担问题在图中找一条经过每个点一次且仅一次的最短路带权的哈密尔顿回路。,图论中的图,图论中的图：人们只关心有多少个点，这些点可以形成多少条边，它们的连接形式如何；不关心这些点的地理位置，边的长短和形状。,设V=v1,

4、v2,vn是n个元素的非空集合，E=e1,e2,em是m个元素的集合，若对于任意ejE，均有vs,vtV与之对应，则称VE为图，记为G=(V,E)。在G中，称vi为G的顶点，ej为G的边，并记ej=(vs,vt)=(vt,vs)，称vs,vt是ej的端点，ej是与vs,vt关联的边，称vs,vt为邻接的点。如果图中某一边的两个端点相同，则称为环。如果图中的两边(或多边)具有相同的一对端点，则称为多重边(或平行边)。无环和无多重边的图称为简单图。,例1：用图符号表示右图。解：(1)图G=(V,E)(2)V=v1,v2,v3,v4(3)E=e1,e2,e7，其中e1=(v1,v2)=(v2,v1)

5、多重边e2=(v1,v2)=(v2,v1)多重边e3=(v2,v3)=(v3,v2)e4=(v3,v4)=(v4,v3)e5=(v1,v4)=(v4,v1)e6=(v1,v3)=(v3,v1)e7=(v4,v4)环,与顶点v相关联的边数称为v的次数，记为d(v)。次数为零的点称为孤立点；次数为奇数的点为奇点；次数为偶数的点称为偶点；次数为1的点为悬挂点；与悬挂点关联的边称为悬挂边。右图中各点的次数：d(v1)=4偶点d(v2)=3奇点d(v3)=4偶点d(v4)=1悬挂点d(v5)=0孤立点,定理1 任一图中顶点次数之和等于边数的二倍，即d(vi)=2m。证明：次数表示与顶点相关联的边数，同一

6、条边有两个邻接的点，即每一条边被邻接的点合计计算了2次，故次数之和等于边数的二倍。定理2 任一图中奇点的个数必为偶数。证明：若奇点的个数是奇数，则这些顶点的次数之和必为奇数，所有顶点次数之和就是奇数，这与定理1矛盾。故奇点的个数必为偶数。,在图G中，从一个顶点出发，经过边、点、边、点、，最后到达某一点，称为G中的一条链，用经过这条链的顶点或边表示。如上图中有一条链=(v1,v2,v3,v4)=(e2,e4,e6)。若链中的顶点均是不同的，则称为初等链；若链中所含的边均不相同，则称为简单链，也称为通路，简称路。上述链是初等链，也是简单链，是通路。,链=(v1,v2,vn)中，若v1=vn，则称此

7、链为一个圈。若圈中的点都是不同的，则称为初等圈；若圈中所含的边均不相同，则称为简单圈。在一个图中，若任意两点之间至少存在一条链，则称该图为连通图，否则为不连通图。若有图G=(V,E)，取其全部或部分顶点V1，再取其全部或部分边E1，这里V1非空，且E1中的端点都在V1中，则称图G1=(V1,E1)为图G的子图。,设V=v1,v2,vn是n个元素的非空集合，A=a1,a2,am是m个元素的集合，若对于任一ajA，均有有序对(vs,vt)与之对应，则称VA为有向图，记为D=(V,A)。称vi为顶点，aj为弧，记为aj=(vs,vt)，在不至于混淆时也称为边。在有向图D中，从一个顶点出发，顺着弧的方

8、向，经过弧、点、弧、点、，最后达到某一点，称为D中的一条单向链或通路，简称路，用经过这条单向链的顶点(或弧)表示。,在有向图中，顶点次数分为入次d-(vi)和出次d+(vi)，入次是以该顶点为终点的边数，出次是以该顶点为起点的边数。,例2：用符号表示右边的有向图。D=(V,A)，其中V=v1,v2,v3,v4,v5A=a1,a2,a3,a4,a5,a6,a7a1=(v1,v5)a2=(v5,v4)a3=(v1,v4)a4=(v3,v1)a5=(v1,v2)a6=(v2,v3)a7=(v1,v4),d-(v1)=1；d+(v1)=3d-(v2)=1；d+(v2)=1d-(v3)=1；d+(v3)

9、=2d-(v4)=3；d+(v4)=0d-(v5)=1；d+(v5)=1,如果对于给定的图G=(V,E)的任意一边eE，有一实数W(e)与之对应，则称G为赋权图，称W(e)为边e的权。赋权图的应用比较广泛，如交通图中，权数可以是两点之间的单位运费、运能等；在工程网络图中，权数代表工序的时间。设在赋权图中存在一条通路，则通路上所有边的权数之和称为这条通路的权。对于一个有向图也可以定义权数使之成为有向赋权图。,一个连通图连同定义在其边集上的实数W(e)一起称为一个网络。若一个网络的每条边均有方向，称为有向网络；每一条边均无方向，称为无向网络；若有些边有向，有些边无向，则称为混合网络。,图的矩阵描述

10、,无权图的邻接矩阵表示两顶点之间有边相连的记为1，无边相连的记为0，对角线位置数据记为0，这样就得到无权图的邻接矩阵，该矩阵一定是对称矩阵。,赋权无向图的邻接矩阵表示两顶点之间有边相连的，写上其权数，无边相连的记为，对角线上的数字为0。赋权无向图对应的矩阵也是对称的。,赋权有向图的邻接表示矩阵左侧第一列为各条弧的起点，在每一行中，以该点为起点，按弧的方向依次填上到各点的权数，如果不存在到该点的弧，则权数为。,2 最小支撑树问题,树及其性质图的支撑树(生成树)最小支撑树问题根树及其应用,树及其性质,树在现实中随处可见，如电话线架设、比赛程序、组织结构等。树：连通的无圈的无向图称为树。,树的性质图

11、G=(V,E)，p个点、q条边，下列说法是等价的(1)G是一个树(2)G连通，且恰有p-1条边(3)G无圈，且恰有p-1条边(4)G连通，但每舍去一边就不连通(5)G无圈，但每增加一边即得唯一一个圈(6)G中任意两点之间恰有一条链(简单链),图的支撑树(生成树),定义：设图T=(V,E)是图G=(V,E)的支撑子图，如果T是一个树，则称T是G的一个支撑树。定理5：图G=(V,E)有支撑树的充分必要条件是G是连通的。,找图中生成树的方法求支撑树的破圈法,找图中生成树的方法求支撑树的避圈法,深探法,广探法,最小支撑树问题,赋权图(网络)：给定图G=(V,E),对G中的每一条边(vi,vj)，相应地

12、有一个数wij，则称这样的图为赋权图。wij 称为边(vi,vj)上的权。支撑树的权：若T=(V,E)是G的一个支撑树，E中的所有边的权之和称为支撑树的权，记为w(T)：w(T)=wij(其中(vi,vj)T),满足w(T*)=min(w(T)的树T*称为最小支撑树(最小树)。求最小树的方法求最小树的避圈法求最小树的破圈法,根树及其应用,有向树中的根树在计算机科学、决策论中有很重要的应用有向树：若一个有向图在不考虑边的方向时是一棵树，则称这个有向图为有向树。根树：有向树T，恰有一个结点入次为0，其余各点入次均为1，则称T为根树(又称外向树)。根树中入次为0的点称为根。根树中出次为0的点称为叶。

13、入次和出次均大于0的点称为分枝点。由根到某一顶点vi的道路长度(设每边长度为1)，称为vi点的层次。,在根树中，若每个顶点的出次小于或等于M，称这棵树为M叉树。若每个顶点的出次恰好等于M或者零，则称这棵树为完全M叉树。当M=2时，称为二叉树、完全二叉树。,如图所示的树是根树。其中根、分枝点、叶；各点层次都标注在树上。这是一棵三叉树,根,叶,分点枝,第一层,第三层,第二层,三叉树,带权的二叉树T：令有s个叶子的二叉树T各叶子的权分别为pi，根到各叶子的距离(层次)为li(i=1,2,s)，这样二叉树T的总权数m(T)=pili。满足总权数最小的二叉树称为最优二叉树(也称Huffman树)。Huf

14、fman算法(D.A.Huffman最优二叉树算法)将s个叶子按权由小至大排序将二个具有最小权的叶子合并成一个分枝点，其权为两者之和，将新的分枝点作为一个叶子。转上一步，直到结束。,例3：s=6，其权分别为4,3,3,2,2,1，求最优二叉树。,3,6,5,3,9,6,5,15,例4：最优检索问题。使用计算机进行图书分类。现有五类图书共万册，其中有A类50万册，有B类20万册，C类5万册，D类10万册，E类15万册。问如何安排分检过程，可使总的运算(比较)次数最小？解：构造一棵具有5个叶子的二叉树，其叶子的权分别为50,20,5,10,15。生成最优二叉树：C与D合并，之后与E合并，之后与B合

15、并，之后与A合并。总权=5*4+10*4+15*3+20*2+50=195。分检过程：先将A类分检出来，然后分检B，然后分检E，最后分检D、C。,3 最短路问题,概述最短路算法Dijkstra算法最短路算法矩阵算法最短路算法Floyd算法,概述,最短路问题就是在一个网络中，给定一个起点，要求找出其到另一点的且权数最小的通路。最短路问题是网络分析中最重要的最优化问题之一。最短路问题在实际分析中有广泛的应用，如管道铺设、运输路线选择、工厂布局等。有些问题看起来与地理方位无关，但通过适当转化也可以将其归结为最短路问题，如设备更新问题等。,最短路问题的一般描述：对D=(V,A)，aij=(vi,vj)

16、，w(aij)=wij，P是从vs到vt的路，定义路P的权是P中所有弧的权的和，记为w(P)。最短路问题则成为求w(P0)=min(w(P)|P)。路P0的权称为从vs到vt的距离，记为：d(vs,vt)。,最短路算法Dijkstra算法,最短路的标号算法是由E.D.Dijkstra于1959年提出的，也称Dijkstra算法，是目前公认的求解最短路问题的较好算法，但此算法要求网络中边的权wij0。,Dijkstra算法步骤：(1)从起点出发，依次寻找与起点距离最近的相邻点，并以此最短距离作为该点的标号，每次寻找一个点。(2)若已经计算出起点到若干点S=v1,v2,vi的最短距离，在找下一点时

17、，要充分考虑到与S集合中的点的每一邻接点的可能，也就是说要考虑S集合中的每一点到其他点的距离，从中选出最短距离点。(3)重复上述过程，直到终点的标号被找到，则终止计算，找出最短路。,例5：设有一批货物要从v1运到v7，每一边上的数字代表该段路线的长度，求最短的运输路线。,最短路算法Dijkstra算法(PT标号),(1)对源vs标以永久P标号：P(vs)=0；对其他顶点标以临时T标号：T(u)=。(2)检查所有从P标号顶点到T标号顶点的弧。重新计算所有T标号的顶点的值T(v)=min(T(v),P(u)+c(u,v)(3)计算T(v)=min(T(i)，标号P(v)，记录对应u(4)重复(2)

18、-(3)，直到全部顶点为P标号。最短路采用反向追踪；最短距离=P(vt)。,最短路算法矩阵算法,最短路的矩阵算法是将图表达成矩阵形式，然后用矩阵表计算出最短路。矩阵算法的基本思路与标号算法的基本思路一致。只不过一个标注在表上另一个标注在图上；标注在表上的便于计算机处理，标注在图上的直观,矩阵算法的步骤：(1)将图表示成矩阵形式(2)确定起点行，标号为0，划去相应列(3)在已标号行且未划去的元素中，找出最小元素aij，圈起来，划去第j列，第j行标号aij，把第j行中未划去的各元素都加上aij(4)重复(3)，如果各行均已获得标号(或终点已经获得标号)，则终止计算。利用反向追踪，获得自起始点到各点

19、的最短路；对应标号即为最短距离。,例6：对上述例子利用矩阵算法求最短的运输路线。解答：(1)先根据图完成矩阵表示。,(2)找到起始点v1，第1行标号0，划去第1列,(3)在已标号行(第1行)且未划去的元素中(1,4)，寻找最小的元素(即为a12=1)。完成下列4项：圈：将a12圈起来；划：划去第2列；标：第2行标号1；加：第2行未划去的元素都加上1,(4)重复(3)。在已标号行(第1-2行)且未划去的元素中(4,3,5,8,6)，寻找最小的元素(即为a23=3)。完成下列4项：圈：将a23圈起来；划：划去第3列；标：第3行标号3；加：第3行未划去的元素都加上3,(5)重复(3)。在已标号行(第

20、1-3行)且未划去的元素中(5,8,6,4)，寻找最小的元素(即为a36=4)。完成下列4项：圈：将a36圈起来；划：划去第6列；标：第6行标号4；加：第6行未划去的元素都加上4,(6)重复(3)。在已标号行(第1-3,6行)且未划去的元素中(5,8,7,10)，寻找最小的元素(即为a24=5)。完成下列4项：圈：将a24圈起来；划：划去第4列；标：第4行标号5；加：第4行未划去的元素都加上5,(7)重复(3)。在已标号行(第1-4,6行)且未划去的元素中(8,7,7)，寻找最小的元素(即为a45=a65=7)。完成下列4项：圈：将a45和a65圈起来；划：划去第5列；标：第5行标号7；加：第

21、5行未划去的元素都加上7,(8)重复(3)。在已标号行(第1-6行)且未划去的元素中(9,10)，寻找最小的元素(即为a57=9)。完成下列4项：圈：将a57圈起来；划：划去第7列；标：第7行标号9；加：第7行未划去的元素都加上9(全部划完),最短路算法Floyd算法,某些问题中，要求网络上任意两点之间的最短路，这类问题可以用Dijkstra算法依次改变起点的办法计算，但很繁琐。Floyd算法可以直接求取任意两点间最短路。Floyd算法又称为弗洛伊德算法，插点法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特弗洛伊德命名。该法由Floyd于1962年完成(Ro

22、bert W.Floyd:Algorithm 97:Shortest path,Communications of the ACM,1962年第5卷第6期)。,Floyd算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd算法的时间复杂度为O(n3)，空间复杂度为O(n2)。Floyd算法，也有专业书籍称Floyd-Warshall算法(Floyd-Warshall Algorithm)。,Floyd算法(1)输入权矩阵D(0)=D=(dij)nn，dij取值为如果(vi,vj)E，则dij=lij为vi到vj的距离如果

23、(vi,vj)不属于E，则dij=(2)计算D(k)=(dij(k)nn，其中dij(k)=min(dij(k-1),dis(k-1)+dsj(k-1)(3)D(n)=(dij(n)nn中元素dij(n)就是vi到vj的最短路长。若D(p)=D(p-1)则也可结束。迭代步长p根据公式2p-1n-12p估计,例7：利用Floyd算法求上例中最短路。,例8：若某地7个村庄之间的交通道路如图所示。旁边数字为各村庄之间道路的长度。试求各村之间的最短距离。,解答,例9：用Floyd算法计算有向图的最短路,若v1v4方向不变，则结果如下,若v1v4方向改变，则结果如下,若v4v1容量为-6，则结果如下,4

24、 最大流问题,基本概念最大流算法1标号算法最大流算法2改进标号算法最大流算法3最小截集法最大流算法4线性规划(Excel求解),基本概念,给定一个有向图D=(V,A)，如果对于每一条弧a=(vi,vj)A，均有一个非负实数cij=c(vi,vj)=c(a)C与之对应，称c(a)为弧a的容量；称V中入次为0出次大于0的顶点vs为源(发点)，称入次大于0出次为0的顶点vt为汇(收点)，入次和出次均大于0的顶点为中间顶点，则称这个图为容量网络，有时也根据运输情况称为运输网络，简称网络，记为N=(V,A,C,vs,vt)。,一般地，如果网络N=(V,A,C,vs,vt)中，定义在弧集A上的一个函数f满

25、足：(1)对于任意一条弧(vi,vj)，都有0fijcij；(2)对于中间顶点vk，fik=fkj；(3)对于源vs和汇vt，存在fsj=fit=Vf，则称f为N的一个网络流，简称流，称Vf为f的流量。对于给定的运输网络，一个十分实际的问题是如何求得该网络中流量最大的网络流，简称最大流。,设是从源vs到汇vt的一条链，定义的方向是从vs到vt。称上与同向的弧为前向弧，记前向弧的集合为+，称上与反向的弧为反向弧，记反向弧的集合为-。设是网络N中从源vs到汇vt的一条链，f是N的一个网络流，若对于任一a+，f(a)0，则称是网络N中关于流f的一条增广链。,设是网络N中关于流f的一条增广链，可以采用

26、如下方法改进流f使流量Vf增大。(1)令=minc(a)-f(a)|a+,f(a)|a-(2)作g(a)=f(a)+,a+f(a)-,a-f(a),其他得到g一定满足网络流的三个条件，所以g仍然为N中的网络流，而Vg=Vf+Vf，流量增大。,最大流算法1标号算法,(1)给出初始流f=0(2)令l(vs)=+，S=vs，B=，T=V-S(3)考察S-B中的顶点u若vT，前向弧(u,v)满足f(u,v)0，给顶点v标号u,-,l(v)，其中l(v)=minl(u),f(v,u)，并将v吸纳入S,(4)若对所有vT，前向弧(u,v)和反向弧(v,u)均检查完毕，将检查完的顶点u并入B，转(3)(5)

27、若vt进入S，则必然存在从vs到vt的增广链，反向追踪得到，且=l(vt)，令g(a)=f(a)+，a+f(a)-，a-f(a)，其他Vg=Vf+，转(2)(6)若S-B=，vt不能进入S，则f已是网络最大流,最大流算法2改进标号算法,(1)对弧的容量加以改进。每一条弧a=(u,v)起点端标上流量c(u,v)，终点端标上0；若为双向弧，则都标上c(u,v)。(2)寻找增广链。找出一条从源vs到汇vt的路，要求这条路上每一条弧顺流方向的容量都大于0。存在，转(3)；不存在，停止，最大流Vf=。(3)计算=minc(u,v)|a=(u,v)(4)修改标号。对上每个弧都修改其标号：顺流容量减少，逆流

28、容量增加。返回(2),最大流算法3最小截集法,(1)设vsV1,vtV2,V1V2=,V1V2=V(2)计算fi=c(u,v)(uV1,vV2,(u,v)E)(3)调整V1和V2，转(2)(4)遍历各种组合，Vf=min(fi)上述有关最小截集法是基于最大流量最小截集定理：最大流量=最小截集容量,最大流算法4线性规划,设过弧a=(i,j)的流量是f(i,j)，容量c(i,j)。则必有0f(i,j)c(i,j)。又由于顶点可以分成三类：(1)源vs，netflow(s)=f(s,j)-f(i,s)max(2)汇vt，netflow(t)=f(t,j)-f(i,t)(3)中间顶点vk，netflo

29、w(k)=f(k,j)-f(i,k)=0故应有网络最大流的线性规划模型如下max f=f(s,i)f(k,j)-f(i,k)=0(kV,kvs,kvt)f(i,j)c(i,j)f(i,j)0,例10,解答1最小截集,解答2线性规划(Excel求解),=SUMIF($A$2:$A$11,F2,$D$2:$D$11)-SUMIF($B$2:$B$11,F2,$D$2:$D$11),5 最小费用最大流,网络D=(V,A,C)的每一个弧(vi,vj)A，除了容量cij=c(vi,vj)外，还给定单位流量的费用bij=b(vi,vj)0。所谓最小费用最大流问题就是要求一个最大流f，使流的总输送费用b(f

30、)=bijfij取极小值。对增广链，若调整流量=1，那么新可行流f的费用比原可行流f的费用增加b(f)-b(f)=bij(fij-fij)|(i,j)+-bij(fij-fij)|(i,j)-=bij|(i,j)+-bij|(i,j)-,可以证明，若f是流量为v(f)的所有可行流中费用最小者，而是关于f的所有增广链中费用最小的增广链，那么沿着去调整f，得到的可行流f就是流量为v(f)的所有可行流中的最小费用流。当f是最大流时，就是最小费用最大流。由于bij0，所以f=0必定是流量为0的最小费用流。这样，总可以从f=0开始，寻找对应于v(f)的最小费用流。设已知f是流量v(f)的最小费用流，余下

31、的问题是如何寻找关于f的最小费用增广链。,构造一个赋权有向图W(f)，其顶点是原网络D的顶点，而把D中每一条弧(vi,vj)变成两个相反的弧(vi,vj)和(vj,vi)，定义W(f)中的权wij为bij,若fij0+,fij=0于是在网络D中寻求关于f的最小费用增广链就等价于在赋权有向图W(f)中寻求从vs到vt的最短路。,最小费用最大流算法,(1)若在第k-1步中得到最小费用流f(k-1)，则构造赋权有向图W(f(k-1)(2)寻求从vs到vt的最短路。若不存在，则f(k-1)就是最小费用最大流；否则转(3)(3)在原网络D中得到增广链，对f(k-1)调整量为=minmin(cij-fij

32、(k-1)|+,min(fij(k-1)|-，得到新的可行流f(k)。令fij(k)=fij(k-1)+，(i,j)+fij(k-1)-，(i,j)-fij(k-1)，(i,j)不属于(4)重复上述步骤,例11,求如下网络D的最小费用最大流。弧旁数字为(bij,cij)。,解答,(1)取f(0)=0为初始可行流。(2)构造赋权有向图W(f(0)，并求出从vs到vt的最短路：vs-v2-v1-vt，距离d=4。(3)原图中与这条最短路相应的增广链=vs,v2,v1,vt。(4)在上调整。=min(8,5,7)=5，计算fij(1)。转(2),(5)构造赋权有向图W(f(1)，并求出从vs到vt的

33、最短路：vs-v1-vt，距离d=5(6)原图中与这条最短路相应的增广链=vs,v1,vt(7)在上调整。=min(10,2)=2，计算fij(2)。转(2),(8)构造赋权有向图W(f(2)，并求出从vs到vt的最短路：vs-v2-v3-vt，距离d=6(9)原图中与这条最短路相应的增广链=vs,v2,v3,vt(10)在上调整。=min(3,10,4)=3，计算fij(3)。转(2),(11)构造赋权有向图W(f(3)，并求出从vs到vt的最短路：vs-v1-v2-v3-vt，距离d=7(12)原图与这条最短路相应的增广链=vs,v1,v2,v3,vt(13)在上调整。=min(1,7,1

34、)=1，计算fij(4)。转(2),(14)构造赋权有向图W(f(4)，发现没有从vs到vt的最短路，停止计算。故f(4)为最小费用最大流。结论：最小费用Cost=3*4+8*1+4*2+4*3+4*2+7*1=55最大流f=3+8=7+4=11,最小费用最大流的线性规划解法,(1)Max,(2)Min,最小费用最大流改进算法,(1)对弧(vi,vj)的标注(cij,bij)加以改进靠近vi一端的标号(cij,bij)靠近vj一端的标号(0,-bij)原弧变为边，无方向(2)以bij为权(靠近vi端的cij0)寻找最短路，若无则停止计算调整量pf=mincij|(i,j)调整：vi端cij变为

35、cij-pf，vj端的cij变为cij+pf重复本节各步骤(3)结果与初始图比较得到流量图和总费用,例12：计算上图的最小费用最大流。解答：(1)重新标号，得到无向图(2)以bij为权，计算最短路=s,2,1,t,(3)pf=min(8,5,7)=5(4)调整标号(5)计算最短路=s,1,t,(6)pf=min(10,2)=2(7)调整标号(8)计算最短路=s,2,3,t,(9)pf=min(3,10,4)=3(10)调整标号(11)计算最短路=s,1,2,3,t,(12)pf=min(8,5,7,1)=1(13)调整标号(14)不存在最短路，停止结论：Cost=12+8+8+12+7+8=5

36、5；f=3+8=11,6 中国邮递员问题,一笔划问题欧拉链：图中存在一条链，过每边一次且仅一次欧拉圈：图中存在一简单圈，过每边一次欧拉图：具有欧拉圈的图定理：连通多重图G是欧拉图，当且仅当G中无奇点推论：连通多重图G有欧拉链，当且仅当G恰有两个奇点,奇偶点作业法若图中无奇点，问题已解决；否则：第一可行方案的确定：奇点配对，找奇点间的一条链。调整可行方案，使重复边总长度下降(a)最优方案中，每一边上最多有一条重复边(b)最优方案中，每个圈上重复边的总权不大于圈总权的一半最优性判定：满足(a)和(b)两条,7 网络计划技术,概述网络图的绘制时间参数的计算网络计划的优化,概述,为了在生产活动或工程项

37、目中最大限度利用人力、物力、财力等有限资源，需要编制工程计划，对进度实施组织和控制。常用工具是甘特图(Gantt Chart)，也称横道图。网络计划技术是计划管理的新方法的统称，包括关键路线法(Critical Path Method,CPM)，计划评审技术(Program Evaluation and Review Technique,PERT)等。我国已故数学家华罗庚将PERT/CPM总结概括为统筹方法，加以积极推广。,网络计划技术广泛应用于工业、农业、国防、科研等计划管理中，对缩短工期、节约资源，提高经济效益发挥了重要作用。统筹方法基本原理是：按照活动先后顺序和相互关系作出网络图，计算时

38、间参数，找出关键路线，优化网络，最终付诸实施。,网络图的绘制,网络图分为箭头型网络图和节点型网络图，都能表示完成的任务(工序、活动等)，任务的开始、结束等事项，完成任务需要的时间。,例13：箭线型网络图,例14：结点型网络图,箭线型网络图的绘制规则网络图只能有一个总起点事项，一个总终点事项网络图是有向图，不允许有回路网络图中节点i,j之间不允许有两个及两个以上的活动必须正确表明活动之间的前行、后继关系可以灵活设置虚活动活动的开始事项编号大于结束事项编号,时间参数的计算,活动时间确定型：完成某活动所需要的确切时间tij概率型：tij=(a+4m+b)/6；ij=|a-b|/6事项时间参数事项最早

39、可能开始时间tE(1)=0;tE(j)=max(tE(i)+tij)事项最迟必须结束时间tL(n)=tE(n);tL(i)=min(tL(j)-tij)事项机动时间t(i)=tL(i)-tE(i)活动时间参数活动最早可能开始时间tES(i,j)=max(tES(k,i)+tki)活动最早可能结束时间tEF(i,j)=tES(i,j)+tij活动最迟必须开始时间tLS(i,j)=min(tLS(j,k)-tij)活动最迟必须结束时间tLF(i,j)=tLF(i,j)+tij活动机动时间rij=tES(j,k)-tEF(i,j),例15：计算例1的时间参数,方框里面的数据：从左往右计算，采用加法三

40、角形里面数据：从右往左计算，采用减法机动时间：方框数据-三角形数据关键路线：活动时差为零的活动组成。,网络计划的优化,工程计划除了进度外，还应考虑资源、成本等指标，实现网络计划的优化要以时间、资源、费用的综合平衡为前提网络计划的优化包括(1)总工期优化(2)工期-资源优化(3)工期-费用优化,(1)总工期优化：缩短工期采取技术措施缩短关键工序的作业时间更新设备更新工艺采用平行工作交叉工作采取组织措施缩短关键工序时间利用非关键工序的机动时间合理利用非关键工序的人力、物力、财力支援关键工序,(2)工期-资源优化：减少资源同时投入量原则确保关键工序资源需求量按时保证推迟非关键工序开工期，平衡使用资源工具Gantt图线性规划,(3)工期-费用优化：减少费用原理强行压缩工期，有好处，但也付出成本必须在关键工序处压缩工期找单位时间内花费成本最低的工序压缩公式赶工费用斜率c=(c2-c1)/(t1-t2)(1正2赶)找工序的c最少的压缩1个单位工期,