运筹学06图与网络分析课件

《运筹学06图与网络分析课件》由会员分享，可在线阅读，更多相关《运筹学06图与网络分析课件（115页珍藏版）》请在装配图网上搜索。

1、ABCD图与网络分析图与网络分析Graph Theory and Network Analysisv图的基本概念Basic Concepts of Graphv最小支撑树问题The Minimal Spanning Tree Problemv最短路问题The Shortest Route/Path Problemv最大流问题The Maximal Flow Problemv最小费用最大流The Minimal Cost & Maximal Flowv中国邮递员问题Chinese Postman Problemv网络计划技术Network Planning Technology1 图的基本概念v

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

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

4、以形成多少条边，它们的连接形式如何；不关心这些点的地理位置，边的长短和形状。v设V=v1,v2,vn是n个元素的非空集合，E=e1,e2,em是m个元素的集合，若对于任意ejE，均有vs,vtV与之对应，则称VE为图图，记为G=(V,E)。v在G中，称vi为G的顶点顶点，ej为G的边边，并记ej=(vs,vt)=(vt,vs)，称vs,vt是ej的端点端点，ej是与vs,vt关联的边关联的边，称vs,vt为邻接的点邻接的点。v如果图中某一边的两个端点相同，则称为环环。如果图中的两边(或多边)具有相同的一对端点，则称为多重边多重边(或平行边)。无环和无多重边的图称为简单图简单图。 例1：用图符号

5、表示右图。解：(1)图G=(V,E)(2)V=v1,v2,v3,v4(3)E=e1,e2,e7，其中e1=(v1,v2)=(v2,v1)多重边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)环1v2v3v4v1e2e3e4e5e6e7ev与顶点v相关联的边数称为v的次数次数，记为d(v)。次数为零的点称为孤立点孤立点；次数为奇数的点为奇点奇点；次数为偶数的点称为偶点偶点；次数为1的点为悬挂点悬挂点；与悬挂点关联的边称为悬挂悬挂边边。v右图

6、中各点的次数： d(v1)=4偶点 d(v2)=3奇点 d(v3)=4偶点 d(v4)=1悬挂点 d(v5)=0孤立点1v2v3v4v1e2e3e4e5e6e5vv定理1 任一图中顶点次数之和等于边数的二倍，即d(vi)=2m。 证明：次数表示与顶点相关联的边数，同一条边有两个邻接的点，即每一条边被邻接的点合计计算了2次，故次数之和等于边数的二倍。v定理2 任一图中奇点的个数必为偶数。 证明：若奇点的个数是奇数，则这些顶点的次数之和必为奇数，所有顶点次数之和就是奇数，这与定理1矛盾。故奇点的个数必为偶数。v在图G中，从一个顶点出发，经过边、点、边、点、，最后到达某一点，称为G中的一条链链，用经

7、过这条链的顶点或边表示。如上图中有一条链=(v1,v2,v3,v4)=(e2,e4,e6)。v若链中的顶点均是不同的，则称为初等链初等链；若链中所含的边均不相同，则称为简单链，简单链，也称为通路，通路，简称路路。上述链是初等链，也是简单链，是通路。v链=(v1,v2,vn)中，若v1=vn，则称此链为一个圈圈。若圈中的点都是不同的，则称为初初等圈等圈；若圈中所含的边均不相同，则称为简简单圈单圈。v在一个图中，若任意两点之间至少存在一条链，则称该图为连通图连通图，否则为不连通图不连通图。若有图G=(V,E)，取其全部或部分顶点V1，再取其全部或部分边E1，这里V1非空，且E1中的端点都在V1中，

8、则称图G1=(V1,E1)为图G的子图子图。v设V=v1,v2,vn是n个元素的非空集合，A=a1,a2,am是m个元素的集合，若对于任一ajA，均有有序对(vs,vt)与之对应，则称VA为有向图有向图，记为D=(V,A)。称vi为顶点，aj为弧弧，记为aj=(vs,vt)，在不至于混淆时也称为边。v在有向图D中，从一个顶点出发，顺着弧的方向，经过弧、点、弧、点、，最后达到某一点，称为D中的一条单向链单向链或通路通路，简称路路，用经过这条单向链的顶点(或弧)表示。v在有向图中，顶点次数分为入次d-(vi)和出次d+(vi)，入次入次是以该顶点为终点的边数，出次出次是以该顶点为起点的边数。v例2

9、：用符号表示右边的有向图。 D=(V,A)，其中 V=v1,v2,v3,v4,v5 A=a1,a2,a3,a4,a5,a6,a7 a1=(v1,v5) a2=(v5,v4) a3=(v1,v4) a4=(v3,v1) a5=(v1,v2) a6=(v2,v3) a7=(v1,v4)v1v2v3v4v5a1a2a3a4a5a6a7 d-(v1)=1；d+(v1)=3 d-(v2)=1；d+(v2)=1 d-(v3)=1；d+(v3)=2 d-(v4)=3；d+(v4)=0 d-(v5)=1；d+(v5)=1v如果对于给定的图G=(V,E)的任意一边eE，有一实数W(e)与之对应，则称G为赋权图赋

10、权图，称W(e)为边边e的权的权。v赋权图的应用比较广泛，如交通图中，权数可以是两点之间的单位运费、运能等；在工程网络图中，权数代表工序的时间。v设在赋权图中存在一条通路，则通路上所有边的权数之和称为这条通路的权通路的权。v对于一个有向图也可以定义权数使之成为有向有向赋权图赋权图。v一个连通图连同定义在其边集上的实数W(e)一起称为一个网络网络。v若一个网络的每条边均有方向，称为有向网有向网络络；每一条边均无方向，称为无向网络无向网络；若有些边有向，有些边无向，则称为混合网络混合网络。图的矩阵描述v无权图的邻接矩阵表示 两顶点之间有边相连的记为1，无边相连的记为0，对角线位置数据记为0，这样就

11、得到无权图的邻接矩阵，该矩阵一定是对称矩阵。v1v2v3v4v5终点v1v2v3v4v5起点v101100v210011v310001v401001v501110v赋权无向图的邻接矩阵表示 两顶点之间有边相连的，写上其权数，无边相连的记为，对角线上的数字为0。赋权无向图对应的矩阵也是对称的。终点v1v2v3v4v5起点v1032 v23054v3208v4502v54820v1v2v3v4v5423258v赋权有向图的邻接表示 矩阵左侧第一列为各条弧的起点，在每一行中，以该点为起点，按弧的方向依次填上到各点的权数，如果不存在到该点的弧，则权数为。终点v1v2v3v4v5起点v1032 v205

12、4v3608v4 02v5 0v1v2v3v4v542325862 最小支撑树问题v树及其性质v图的支撑树(生成树)v最小支撑树问题v根树及其应用树及其性质v树在现实中随处可见，如电话线架设、比赛程序、组织结构等。v树：连通的无圈的无向图称为树。v树的性质v图G=(V,E)，p个点、q条边，下列说法是等价的 (1)G是一个树 (2)G连通，且恰有p-1条边 (3)G无圈，且恰有p-1条边 (4)G连通，但每舍去一边就不连通 (5)G无圈，但每增加一边即得唯一一个圈 (6)G中任意两点之间恰有一条链(简单链)图的支撑树(生成树)v定义：设图T=(V,E)是图G=(V,E)的支撑子图，如果T是一个

13、树，则称T是G的一个支撑树。v定理5：图G=(V,E)有支撑树的充分必要条件是G是连通的。v找图中生成树的方法 求支撑树的破圈法v找图中生成树的方法 求支撑树的避圈法深探法广探法最小支撑树问题v赋权图(网络)：给定图G=(V,E), 对G中的每一条边(vi,vj)，相应地有一个数wij，则称这样的图为赋权图。wij 称为边(vi,vj)上的权。v支撑树的权：若T=(V,E) 是G的一个支撑树，E中的所有边的权之和称为支撑树的权，记为w(T)：w(T)=wij(其中(vi,vj)T)v满足w(T*)=min(w(T)的树T*称为最小支撑树(最小树)。v求最小树的方法 求最小树的避圈法 求最小树的

14、破圈法根树及其应用v有向树中的根树在计算机科学、决策论中有很重要的应用v有向树：若一个有向图在不考虑边的方向时是一棵树，则称这个有向图为有向树有向树。v根树：有向树T，恰有一个结点入次为0，其余各点入次均为1，则称T为根树根树(又称外向外向树树)。根树中入次为0的点称为根根。根树中出次为0的点称为叶叶。入次和出次均大于0的点称为分枝点分枝点。由根到某一顶点vi的道路长度(设每边长度为1)，称为vi点的层次层次。v在根树中，若每个顶点的出次小于或等于M，称这棵树为M叉树叉树。v若每个顶点的出次恰好等于M或者零，则称这棵树为完全完全M叉树叉树。v当M=2时，称为二叉树二叉树、完全二叉树完全二叉树。

15、v如图所示的树是根树。其中根、分枝点、叶；各点层次都标注在树上。v这是一棵三叉树根叶分点枝第一层第三层第二层三叉树v带权的二叉树T：令有s个叶子的二叉树T各叶子的权分别为pi，根到各叶子的距离(层次)为li(i=1,2,s)，这样二叉树T的总权数m(T)=pili。v满足总权数最小的二叉树称为最优二叉树最优二叉树(也称Huffman树)。vHuffman算法(D. A. Huffman最优二叉树算法) 将s个叶子按权由小至大排序 将二个具有最小权的叶子合并成一个分枝点，其权为两者之和，将新的分枝点作为一个叶子。转上一步，直到结束。v例3：s=6，其权分别为4,3,3,2,2,1，求最优二叉树。

16、123243365123243396515123243396515v例4：最优检索问题。使用计算机进行图书分类。现有五类图书共万册，其中有A类50万册，有B类20万册，C类5万册，D类10万册，E类15万册。问如何安排分检过程，可使总的运算(比较)次数最小？v解：构造一棵具有5个叶子的二叉树，其叶子的权分别为50,20,5,10,15。生成最优二叉树：C与D合并，之后与E合并，之后与B合并，之后与A合并。总权=5*4+10*4+15*3+20*2+50=195。分检过程：先将A类分检出来，然后分检B，然后分检E，最后分检D、C。3 最短路问题v概述v最短路算法Dijkstra算法v最短路算法矩

17、阵算法v最短路算法Floyd算法概述v最短路问题最短路问题就是在一个网络中，给定一个起点，要求找出其到另一点的且权数最小的通路。最短路问题是网络分析中最重要的最优化问题之一。v最短路问题在实际分析中有广泛的应用，如管道铺设、运输路线选择、工厂布局等。v有些问题看起来与地理方位无关，但通过适当转化也可以将其归结为最短路问题，如设备更新问题等。v最短路问题的一般描述：对D=(V,A)，aij=(vi,vj)，w(aij)=wij，P是从vs到vt的路，定义路P的权是P中所有弧的权的和，记为w(P)。最短路问题则成为求w(P0)=min(w(P)|P)。路P0的权称为从vs到vt的距离，记为：d(v

18、s,vt)。最短路算法Dijkstra算法v最短路的标号算法是由E. D. Dijkstra于1959年提出的，也称Dijkstra算法，是目前公认的求解最短路问题的较好算法，但此算法要求网络中边的权wij0。vDijkstra算法步骤： (1)从起点出发，依次寻找与起点距离最近的相邻点，并以此最短距离作为该点的标号，每次寻找一个点。 (2)若已经计算出起点到若干点S=v1,v2,vi的最短距离，在找下一点时，要充分考虑到与S集合中的点的每一邻接点的可能，也就是说要考虑S集合中的每一点到其他点的距离，从中选出最短距离点。 (3)重复上述过程，直到终点的标号被找到，则终止计算，找出最短路。v例5

19、：设有一批货物要从v1运到v7，每一边上的数字代表该段路线的长度，求最短的运输路线。v4v2v1v3v6v5v714425316227序号 与S关联边距离集合S标号(0)d(v1)=0v1d(v1)=0(1)(v1,v2)(v1,v3)k12=d(v1)+l(v1,v2)=0+1=1k13=d(v1)+l(v1,v3)=0+4=4v1,v2d(v2)=1v1(2)(v1,v3)(v2,v3)(v2,v4)(v2,v5)(v2,v6)k13=d(v1)+l(v1,v3)=0+4=4k23=d(v2)+l(v2,v3)=1+2=3k24=d(v2)+l(v2,v4)=1+4=5k25=d(v2)+

20、l(v2,v5)=1+7=8k26=d(v2)+l(v2,v6)=1+5=6v1,v2,v3d(v3)=3v2序号 与S关联边 距离集合S标号(4)(v2,v4)(v2,v5)(v6,v5)(v6,v7)k24=d(v2)+l(v2,v4)=1+4=5k25=d(v2)+l(v2,v5)=1+7=8k65=d(v6)+l(v6,v5)=4+3=7k67=d(v6)+l(v6,v7)=4+6=101,2,3,6,4d(v4)=5v2(5)(v4,v5)(v2,v5)(v6,v5)(v6,v7)k45=d(v4)+l(v4,v5)=5+2=7k25=d(v2)+l(v2,v5)=1+7=8k65=

21、d(v6)+l(v6,v5)=4+3=7k67=d(v6)+l(v6,v7)=4+6=101,2,3,6,4,5d(v5)=7v4,v6(6)(v5,v7)(v6,v7)k57=d(v5)+l(v5,v7)=7+2=9k67=d(v6)+l(v6,v7)=4+6=101,2,3,6,4,5,7d(v7)=9v5v最短运输路线：(1)v1-v2-v4-v5-v7或(2)v1-v2-v3-v6-v5-v7v最短距离=d(v7)=9最短路算法Dijkstra算法(PT标号)v(1)对源vs标以永久P标号：P(vs)=0；对其他顶点标以临时T标号：T(u)=。v(2)检查所有从P标号顶点到T标号顶点的

22、弧。重新计算所有T标号的顶点的值T(v)=min(T(v),P(u)+c(u,v)v(3)计算T(v)=min(T(i)，标号P(v)，记录对应uv(4)重复(2)-(3)，直到全部顶点为P标号。最短路采用反向追踪；最短距离=P(vt)。k123456710*21*1433*25864584*355*271067*4,61079*511 11111 11111 11111 11111 11111 11111 11111最短运输路线:(1)1-2-4-5-7;(2)1-2-3-6-5-7最短距离:d=9最短路算法矩阵算法v最短路的矩阵算法是将图表达成矩阵形式，然后用矩阵表计算出最短路。v矩阵算法

23、的基本思路与标号算法的基本思路一致。只不过一个标注在表上另一个标注在图上；标注在表上的便于计算机处理，标注在图上的直观v矩阵算法的步骤： (1)将图表示成矩阵形式 (2)确定起点行，标号为0，划去相应列 (3)在已标号行且未划去的元素中，找出最小元素aij，圈起来，划去第j列，第j行标号aij，把第j行中未划去的各元素都加上aij (4)重复(3)，如果各行均已获得标号(或终点已经获得标号)，则终止计算。利用反向追踪，获得自起始点到各点的最短路；对应标号即为最短距离。v例6：对上述例子利用矩阵算法求最短的运输路线。v解答：(1)先根据图完成矩阵表示。v1v2v3v4v5v6v7v1014v21

24、02475v34201v4402v572032v651306v7260v1v2v3v4v5v6v70v1014v2102475v34201v4402v572032v651306v7260v(2)找到起始点v1，第1行标号0，划去第1列v (3)在已标号行(第1行)且未划去的元素中(1,4)，寻找最小的元素(即为a12=1)。完成下列4项：圈：将a12圈起来；划：划去第2列；标：第2行标号1；加：第2行未划去的元素都加上1v1v2v3v4v5v6v70v10141v2102+14+17+15+1v34201v4402v572032v651306v7260v (4)重复(3)。在已标号行(第1-2

25、行)且未划去的元素中(4,3,5,8,6)，寻找最小的元素(即为a23=3)。完成下列4项：圈：将a23圈起来；划：划去第3列；标：第3行标号3；加：第3行未划去的元素都加上3v1v2v3v4v5v6v70v10141v21035863v34201+3v4402v572032v651306v7260v (5)重复(3)。在已标号行(第1-3行)且未划去的元素中(5,8,6,4)，寻找最小的元素(即为a36=4)。完成下列4项：圈：将a36圈起来；划：划去第6列；标：第6行标号4；加：第6行未划去的元素都加上4v1v2v3v4v5v6v70v10141v21035863v34204v4402v5

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

27、5行未划去的元素都加上7v1v2v3v4v5v6v70v10141v21035863v342045v44077v572032+74v6517010v7260v (8)重复(3)。在已标号行(第1-6行)且未划去的元素中(9,10)，寻找最小的元素(即为a57=9)。完成下列4项：圈：将a57圈起来；划：划去第7列；标：第7行标号9；加：第7行未划去的元素都加上9(全部划完)v1v2v3v4v5v6v70v10141v21035863v342045v44077v5720394v65170109v7260最短路算法Floyd算法v某些问题中，要求网络上任意两点之间的最短路，这类问题可以用Dijks

28、tra算法依次改变起点的办法计算，但很繁琐。Floyd算法可以直接求取任意两点间最短路。vFloyd算法又称为弗洛伊德算法，插点法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特弗洛伊德命名。该法由Floyd于1962年完成(Robert W. Floyd: Algorithm 97: Shortest path, Communications of the ACM, 1962年第5卷第6期) 。vFloyd算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。vFloyd算法的时间复杂度为O(n3

29、)，空间复杂度为O(n2)。vFloyd算法，也有专业书籍称Floyd-Warshall算法(Floyd-Warshall Algorithm)。vFloyd算法 (1)输入权矩阵D(0)=D=(dij)nn，dij取值为如果(vi,vj)E，则dij=lij为vi到vj的距离如果(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)则也可结束。v迭代步长p根据公式2p-1n-12p估计例7：

30、利用Floyd算法求上例中最短路。v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7 v1 014 v1 013585 v2 102475v2 1024639 v3 420 1v3 3206417D(0)= v4 402 D(1)= v4 5460254 v5 72032v5 8642032 v6 51306v6 5315305 v7 260v7 974250111 1111111111111111111111111 111 111111111111111111111111v1 v2 v3 v4 v5 v6 v7v1 v2 v3 v4 v5 v6 v7v1 013

31、5749v1 0135749v2 1024638v2 1024638v3 3206416v3 3206416D(2)= v4 5460254D(3)= v4 5460254v5 7642032v5 7642032v6 4315305v6 4315305v7 9864250v7 9864250v例8：若某地7个村庄之间的交通道路如图所示。旁边数字为各村庄之间道路的长度。试求各村之间的最短距离。12345672223344456771解答03470345711 13303243032458430574305569D(0)= 72026D(1)= 52502364520147452013710211

32、563102642013896320111 1111111111111111111111 111 11111111111111111111103457810034578103032457303245743055684305568D(2)= 5250235D(3)= 525023574520137452013856310285631021078532010785320例9：用Floyd算法计算有向图的最短路12345678910728612122424565104626884若v1v4方向不变，则结果如下12345678910108862042301072408D(0)=560212604712

33、058064962041050111111 111 111 111 111 111 111 111 111 111 1111234567891010886151010204141162731301072640812D(1)=56100286181660410871812140511981289064962960410175100111111 111 111 111 111 111 111 111 111 111 11112345678910108861510101420182041411627131131301072156121040821121816D(2)=5610180286121061

34、6250134108718221712130511982712218906492762129604102327221718510160111111 111 111 111 111 111 111 111 111 111 11112345678910108861510101420182041411627131131301072156121043943033821121816D(3)=5610180286121063135162501341087182217121305119827311221890649273162129604102327221718510160111111 111 111 11

35、1 111 111 111 111 111 111 11112345678910108861510101420182041411627131131301072156121043943033821121816D(4)=5610180286121063135162501341087182217121305119827311221890649273162129604102327221718510160111111 111 111 111 111 111 111 111 111 111 111若v1v4方向改变，则结果如下1234567891010881815101014201822004141162

36、7131131613010721561210461414021816121816D(4)=5246101802861210622303016250134108723182217121305119818262612218906491220206212960410282327221718510160111111 111 111 111 111 111 111 111 111 111 111若v4v1容量为-6，则结果如下1234567891010881815101014201828041411627131134120107214612104-622094481412D(4)=51261018028

37、6121061018181625013410871118191712130511986141412218906490886152960410162324221718510160111111 111 111 111 111 111 111 111 111 111 1114 最大流问题v基本概念v最大流算法1标号算法v最大流算法2改进标号算法v最大流算法3最小截集法v最大流算法4线性规划(Excel求解)基本概念v给定一个有向图D=(V,A)，如果对于每一条弧a=(vi,vj)A，均有一个非负实数cij=c(vi,vj)=c(a)C与之对应，称c(a)为弧a的容量容量；v称V中入次为0出次大于0的

38、顶点vs为源源(发点发点)，v称入次大于0出次为0的顶点vt为汇汇(收点收点)，v入次和出次均大于0的顶点为中间顶点中间顶点，v则称这个图为容量网络容量网络，有时也根据运输情况称为运输网络，简称网络，记为N=(V,A,C,vs,vt)。v一般地，如果网络N=(V,A,C,vs,vt)中，定义在弧集A上的一个函数f满足： (1)对于任意一条弧(vi,vj)，都有0fijcij； (2)对于中间顶点vk，fik=fkj； (3)对于源vs和汇vt，存在fsj=fit=Vf，v则称f为N的一个网络流网络流，简称流流，称Vf为f的流量流量。v对于给定的运输网络，一个十分实际的问题是如何求得该网络中流量

39、最大的网络流，简称最大流最大流。v设是从源vs到汇vt的一条链，定义的方向是从vs到vt。称上与同向的弧为前向弧前向弧，记前向弧的集合为+，称上与反向的弧为反向反向弧弧，记反向弧的集合为-。v设是网络N中从源vs到汇vt的一条链，f是N的一个网络流，若对于任一a+，f(a)0，则称是网络N中关于流f的一条增广链增广链。v设是网络N中关于流f的一条增广链，可以采用如下方法改进流f使流量Vf增大。v(1)令=minc(a)-f(a)|a+,f(a)|a-v(2)作g(a)= f(a)+,a+ f(a)-,a- f(a),其他v得到g一定满足网络流的三个条件，所以g仍然为N中的网络流，而Vg=Vf+

40、Vf，流量增大。最大流算法1标号算法v(1)给出初始流f=0v(2)令l(vs)=+，S=vs，B=，T=V-Sv(3)考察S-B中的顶点u 若vT，前向弧(u,v)满足f(u,v)0，给顶点v标号u,-,l(v)，其中l(v)=minl(u),f(v,u)，并将v吸纳入Sv(4)若对所有vT，前向弧(u,v)和反向弧(v,u)均检查完毕，将检查完的顶点u并入B，转(3)v(5)若vt进入S，则必然存在从vs到vt的增广链，反向追踪得到，且=l(vt)，令g(a)= f(a)+，a+ f(a)-，a- f(a)，其他vVg=Vf+，转(2)v(6)若S-B=，vt不能进入S，则f已是网络最大流

41、最大流算法2改进标号算法v(1)对弧的容量加以改进。每一条弧a=(u,v)起点端标上流量c(u,v)，终点端标上0；若为双向弧，则都标上c(u,v)。v(2)寻找增广链。找出一条从源vs到汇vt的路，要求这条路上每一条弧顺流方向的容量都大于0。 存在，转(3)； 不存在，停止，最大流Vf=。v(3)计算=minc(u,v)|a=(u,v)v(4)修改标号。对上每个弧都修改其标号：顺流容量减少，逆流容量增加。返回(2)最大流算法3最小截集法v(1)设vsV1,vtV2,V1V2=,V1V2=Vv(2)计算fi=c(u,v)(uV1,vV2,(u,v)E)v(3)调整V1和V2，转(2)v(4)遍

42、历各种组合，Vf=min(fi)v上述有关最小截集法是基于最大流量最小截集定理：最大流量=最小截集容量最大流算法4线性规划v设过弧a=(i,j)的流量是f(i,j)，容量c(i,j)。则必有0f(i,j)c(i,j)。v又由于顶点可以分成三类： (1)源vs，netflow(s)=f(s,j)-f(i,s)max (2)汇vt，netflow(t)=f(t,j)-f(i,t) (3)中间顶点vk，netflow(k)=f(k,j)-f(i,k)=0v故应有网络最大流的线性规划模型如下vmax f=f(s,i) f(k,j)-f(i,k)=0 (kV,kvs,kvt) f(i,j)c(i,j)

43、f(i,j)0例101234564482214679解答1最小截集序号 V1V2c(u,v)fiY Vf(1)12,3,4,5,6 c(1,2)=4；c(1,3)=8 128(2)1,23,4,5,6c(2,3)=4；c(2,4)=4c(2,5)=1；c(1,3)=8 17(3)1,32,4,5,6c(1,2)=4；c(3,4)=2c(3,5)=28 Y(4)1,2,34,5,6c(2,4)=4；c(2,5)=1c(3,4)=2；c(3,5)=29(5)1,2,3,45,6c(2,5)=1；c(3,5)=2c(4,6)=710(6)1,2,3,54,6c(2,4)=4；c(3,4)=2c(5,

44、4)=6；c(5,6)=921(7)1,2,3,4,5 6c(4,6)=7；c(5,6)=916解答2线性规划(Excel求解)ABCDEFGH1 From To Caption FlowNodes NetFlow Condition2124418 3138420 04234030 05244440 06251050 0734226-8 8352294677105461115691=SUMIF($A$2:$A$11,F2,$D$2:$D$11)-SUMIF($B$2:$B$11,F2,$D$2:$D$11)5 最小费用最大流v网络D=(V,A,C)的每一个弧(vi,vj)A，除了容量cij=c

45、(vi,vj)外，还给定单位流量的费用bij=b(vi,vj)0。所谓最小费用最大流问题就是要求一个最大流f，使流的总输送费用b(f)=bijfij取极小值。v对增广链，若调整流量=1，那么新可行流f的费用比原可行流f的费用增加 b(f)-b(f) =bij(fij-fij)|(i,j)+-bij(fij-fij)|(i,j)- =bij|(i,j)+-bij|(i,j)-v可以证明，若f是流量为v(f)的所有可行流中费用最小者，而是关于f的所有增广链中费用最小的增广链，那么沿着去调整f，得到的可行流f就是流量为v(f)的所有可行流中的最小费用流。当f是最大流时，就是最小费用最大流。v由于bi

46、j0，所以f=0必定是流量为0的最小费用流。这样，总可以从f=0开始，寻找对应于v(f)的最小费用流。设已知f是流量v(f)的最小费用流，余下的问题是如何寻找关于f的最小费用增广链。v构造一个赋权有向图W(f)，其顶点是原网络D的顶点，而把D中每一条弧(vi,vj)变成两个相反的弧(vi,vj)和(vj,vi)，定义W(f)中的权wij为 bij,若fij0 +,fij=0v于是在网络D中寻求关于f的最小费用增广链就等价于在赋权有向图W(f)中寻求从vs到vt的最短路。最小费用最大流算法v(1)若在第k-1步中得到最小费用流f(k-1)，则构造赋权有向图W(f(k-1)v(2)寻求从vs到vt

47、的最短路。若不存在，则f(k-1)就是最小费用最大流；否则转(3)v(3)在原网络D中得到增广链，对f(k-1)调整量为=minmin(cij-fij(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)不属于v(4)重复上述步骤例11v求如下网络D的最小费用最大流。弧旁数字为(bij,cij)。vsv2v3vtv1(4,10)(1,8)(2,5)(1,7)(6,2)(3,10)(2,4)解答v (1)取f(0)=0为初始可行流。v (2)构造赋权有向图W(f(0)

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

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

50、3)在上调整。=min(1,7,1)=1，计算fij(4)。转(2)vtvsv2v3v13847044f(4),v(f(4)=11vsv2v3vtv14-2632W(f(3)-1-1-4-2-3v (14)构造赋权有向图W(f(4)，发现没有从vs到vt的最短路，停止计算。故f(4)为最小费用最大流。v 结论： 最小费用Cost=3*4+8*1+4*2+4*3+4*2+7*1=55 最大流f=3+8=7+4=11vsv2v3vtv14-263W(f(4)-1-1-4-2-32最小费用最大流的线性规划解法ABCDEFGHI1 From To Caption Flow CostNodes NetF

51、low Condition2vsv11034vs11113vsv2881v1004v1v3206v2005v1vt771v3006v2v1542vt-117v2v310438v3vt442955(1)Max(2)Min最小费用最大流改进算法v (1)对弧(vi,vj)的标注(cij, bij)加以改进 靠近vi一端的标号(cij,bij) 靠近vj一端的标号(0,-bij) 原弧变为边，无方向v (2)以bij为权(靠近vi端的cij0) 寻找最短路，若无则停止 计算调整量pf=mincij|(i,j) 调整：vi端cij变为cij-pf，vj端的cij变为cij+pf 重复本节各步骤v (3

52、)结果 与初始图比较得到流量图和总费用v例12：计算上图的最小费用最大流。v解答：(1)重新标号，得到无向图v(2)以bij为权，计算最短路=s,2,1,tvsv2v3vtv1(10,4)(8,1)(5,2)(7,1)(2,6)(10,3)(4,2)(0,-4)(0,-1)(0,-2)(0,-3)(0,-6)(0,-1)(0,-2)v(3)pf=min(8,5,7)=5v(4)调整标号v(5)计算最短路=s,1,tvsv2v3vtv1(10,4)(3,1)(0,2)(2,1)(2,6)(10,3)(4,2)(0,-4)(5,-1)(5,-2)(0,-3)(0,-6)(5,-1)(0,-2)v(

53、6)pf=min(10,2)=2v(7)调整标号v(8)计算最短路=s,2,3,tvsv2v3vtv1(8,4)(3,1)(0,2)(0,1)(2,6)(10,3)(4,2)(2,-4)(5,-1)(5,-2)(0,-3)(0,-6)(7,-1)(0,-2)v(9)pf=min(3,10,4)=3v(10)调整标号v(11)计算最短路=s,1,2,3,tvsv2v3vtv1(8,4)(0,1)(0,2)(0,1)(2,6)(7,3)(1,2)(2,-4)(8,-1)(5,-2)(3,-3)(0,-6)(7,-1)(3,-2)v(12)pf=min(8,5,7,1)=1v(13)调整标号v(14

54、)不存在最短路，停止v结论：Cost=12+8+8+12+7+8=55；f=3+8=11vsv2v3vtv1(7,4)(0,1)(1,2)(0,1)(2,6)(6,3)(0,2)(3,-4)(8,-1)(4,-2)(4,-3)(0,-6)(7,-1)(4,-2)6 中国邮递员问题v一笔划问题 欧拉链：图中存在一条链，过每边一次且仅一次 欧拉圈：图中存在一简单圈，过每边一次 欧拉图：具有欧拉圈的图v定理：连通多重图G是欧拉图，当且仅当G中无奇点v推论：连通多重图G有欧拉链，当且仅当G恰有两个奇点v奇偶点作业法 若图中无奇点，问题已解决；否则： 第一可行方案的确定：奇点配对，找奇点间的一条链。 调

55、整可行方案，使重复边总长度下降(a)最优方案中，每一边上最多有一条重复边(b)最优方案中，每个圈上重复边的总权不大于圈总权的一半 最优性判定：满足(a)和(b)两条7 网络计划技术v概述v网络图的绘制v时间参数的计算v网络计划的优化概述v为了在生产活动或工程项目中最大限度利用人力、物力、财力等有限资源，需要编制工程计划，对进度实施组织和控制。常用工具是甘特图(Gantt Chart)，也称横道图。v网络计划技术是计划管理的新方法的统称，包括关键路线法(Critical Path Method, CPM)，计划评审技术(Program Evaluation and Review Techniqu

56、e, PERT)等。v我国已故数学家华罗庚将PERT/CPM总结概括为统筹方法，加以积极推广。v网络计划技术广泛应用于工业、农业、国防、科研等计划管理中，对缩短工期、节约资源，提高经济效益发挥了重要作用。v统筹方法基本原理是：按照活动先后顺序和相互关系作出网络图，计算时间参数，找出关键路线，优化网络，最终付诸实施。网络图的绘制v网络图分为箭头型网络图和节点型网络图，都能表示完成的任务(工序、活动等)，任务的开始、结束等事项，完成任务需要的时间。类型箭头型结点型活动箭线圆圈开始事项箭尾处圆圈圆圈处箭尾结束事项箭头处圆圈圆圈处箭头任务代号箭线上面中间 圆圈内中左任务持续时间 箭线下面中间 圆圈内中

57、中例13：箭线型网络图12345678A4D2G4C3E2B5I2F1H3J4序号序号活动活动活动代号活动代号 持续时间持续时间紧前活动紧前活动1A42B53C34D25E26F17G4、8H39I2、10J4例14：结点型网络图A 4B 5C 3D 2E 2F 1G 4H 3I 2J 4S 0T 0v箭线型网络图的绘制规则 网络图只能有一个总起点事项，一个总终点事项 网络图是有向图，不允许有回路 网络图中节点i,j之间不允许有两个及两个以上的活动 必须正确表明活动之间的前行、后继关系 可以灵活设置虚活动 活动的开始事项编号大于结束事项编号时间参数的计算v 活动时间 确定型：完成某活动所需要的

58、确切时间tij 概率型：tij=(a+4m+b)/6；ij=|a-b|/6v 事项时间参数 事项最早可能开始时间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)v 活动时间参数 活动最早可能开始时间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 活动机

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