运筹学图与网络.ppt

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

1、第十一章 图与网络规划Graph Theory and Network Analysis11.1 图与网络的基本概念图与网络的基本概念11.2 最短路问题最短路问题11.3 网络最大流问题网络最大流问题11.4 最小费用最大流问题最小费用最大流问题内容简介内容简介n是近几十年来运筹学领域中发展迅速、而且十分活跃的一个分支n对实际问题的描述具有直观性n广泛应用于物理学、化学、信息论、控制论、计算机科学、社会科学以及现代经济管理科学等许多科学领域n图与网络分析的内容十分丰富本章只介绍图与网络的基本概念以及图论在路径问题、网络流问题等领域中的应用重点讲明方法的物理概念、基本原理及计算步骤11.1 图

2、与网络的基本概念图与网络的基本概念n图的理论研究已有200多年的历史了早期图论与“数学游戏”有着密切关系所谓“哥尼斯堡七桥”问题就是其中之一200多年前的东普鲁士有一座哥尼斯堡城，城中有一条河叫普雷格尔河，河中有两个岛屿共建七座桥平时城中居民大都喜欢来这里散步，并提出这样一个问题：一个散步者能否经过每座桥恰恰一次再回到原出发点11.1 图与网络的基本概念图与网络的基本概念n当时有许多人都探讨了这个问题，但不得其解n著名数学家欧拉（Euler）将这个问题简化为一个如右图所示图形图4个点A、B、C、D表示两岸和小岛两两点间连线表示桥11.1 图与网络的基本概念图与网络的基本概念n于是问题转化为一笔

3、画问题，即能否从某一点开始一笔画出这个图形，不许重复，最后回到原出发点n欧拉否定了这种可能性n原因是图中与每一个点相关联的线都是奇数条n为此他写下了被公认为世界第一篇有关图论方面的论文（1736年）11.1 图与网络的基本概念图与网络的基本概念n1859年哈密尔顿提出了另一种游戏：在一个实心的12面体（见图）的20个顶点上标以世界上著名的城市名称，要求游戏者从某一城市出发，遍历各城市恰恰一次而返回原地，这就是所谓“绕行世界问题”11.1 图与网络的基本概念图与网络的基本概念n作图，此问题变成在从某一点出发寻找一条路径，过所有20个点仅仅一次，再回到出发点n解决这个问题可以按序号1234一一20

4、1所形成的一个闭合路径，并称此路径为哈密尔顿圈n具有哈密尔顿圈的图称为哈密尔顿图11.1 图与网络的基本概念图与网络的基本概念n由此可见，图论中所研究的图是由实际问题抽象出来的逻辑关系图n这种图与几何中的图形和函数论中所研究的图形是不相同的n这种图的画法具有一定的随意性，在保持相对位置和相互关系不变的前提下，点的位置不一定要按实际要求画，线的长度也不一定表示实际的长度而且画成直线或曲线都可以n通俗地说，这种图是一种关系示意图11.1 图与网络的基本概念图与网络的基本概念n图的概念图的概念 n所谓图，就是顶点和边的集合，点的集合记为所谓图，就是顶点和边的集合，点的集合记为V V，边的集合记为边的

5、集合记为E E，则图可以表示为：，则图可以表示为：G G（V V，E E），），点代表被研究的事物，边代表事物之间的联系，点代表被研究的事物，边代表事物之间的联系，因此，边不能离开点而独立存在，每条边都有两因此，边不能离开点而独立存在，每条边都有两个端点。个端点。n在画图时，顶点的位置、边和长短形状都是无关在画图时，顶点的位置、边和长短形状都是无关紧要的，只要两个图的顶点及边是对应相同的，紧要的，只要两个图的顶点及边是对应相同的，则两个图相同。则两个图相同。图的表示图的表示 e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9点与边点与边 n顶顶点点数数 集集合合V中中元元素

6、素的的个个数数，记作记作p(G)。n边数边数 集合集合E中元素的个数，记中元素的个数，记作作q(G)。n若若e=u,vE，则称，则称u和和v为为e的的端点端点，而称，而称e为为u和和v的的关联边关联边，也称也称u，v与边与边e相相关联关联。n例如图中的图例如图中的图G，p(G)=6，q(G)=9，nv1，v2是是e1和和e2的端点，的端点，e1和和e2都都是是v1和和v2的关联边。的关联边。e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9点边关系点边关系n若若点点u和和v与与同同一一条条边边相相关关联联，则则u和和v为为相相邻邻点点；若若两两条条边边ei和和ej有有同同一

7、一个个端端点点，则则称称ei与与ej为为相相邻邻边边。n例如在图中例如在图中v1和和v2为相为相邻点，邻点，v1和和v5不相邻；不相邻；e1与与e5为相邻边，为相邻边，e1和和e7不相邻。不相邻。e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9简单图简单图n若若一一条条边边的的两两个个端端点点是是同同一一个个顶顶点点，则则称称该该边边为为环环；又又若若两两上上端端点点之之间间有有多多于于一一条条边，则称为边，则称为多重边多重边或或平行边平行边。n例例如如图图的的e8为为环环，e1，e2为为两两重边，重边，e4，e5也是两重边。也是两重边。n含有多重边的图称作含有多重边的图

8、称作多重图多重图。n无无环环也也无无多多重重边边的的图图称称作作简简单图单图。e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9图的次图的次n次次 点点v作为边的端点的作为边的端点的次数，记作次数，记作d(v)，如图中，如图中，d(v1)=5,d(v4)=6等等n端端点点次次为为奇奇数数的的点点称称作作奇奇点点；次次为为偶偶数数的的点点称称作作偶点偶点。n次次为为1的的点点称称为为悬悬挂挂点点，与与悬悬挂挂点点连连接接的的边边称称作作悬挂边悬挂边；n次为次为0的点称为的点称为孤立点孤立点。n图图中中的的点点v5即即为为悬悬挂挂点点，边边e9即即为为悬悬挂挂边边，而而点点v6

9、则是弧立点。则是弧立点。e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9定理定理 n若图若图G中所有点都是孤中所有点都是孤立点，则称图立点，则称图G为为空图空图。n定理定理1 所有顶点的次的所有顶点的次的和，等于所有边数的和，等于所有边数的2倍。即倍。即 e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9n定理定理2 在任一图中，在任一图中，奇点的个数必为偶数。奇点的个数必为偶数。n设设V1和和V2分别是图分别是图G中次数为奇数和偶数中次数为奇数和偶数的顶点集合。由定理的顶点集合。由定理1有有 e1 e2 e3 e4 e5v2 v3v1v4v5v6e6

10、e7e8e9链链 n由两两相邻的点及由两两相邻的点及其相关联的边构成其相关联的边构成的点边序列称为的点边序列称为链链。nv0称为链的称为链的起点起点，vn称为链的称为链的终点终点。n若若v0 vn则称该链为则称该链为开链开链，反之称为，反之称为闭闭链链或或回路回路。e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9简单链简单链 n若链中所含的边均不若链中所含的边均不相同，则称为相同，则称为简单链简单链；若点均不相同，则称若点均不相同，则称为为初等链初等链或或通路通路。n除起点和终点外点均除起点和终点外点均不相同的闭链，称为不相同的闭链，称为初等回路初等回路或称为或称为圈圈。

11、n例如图中例如图中e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9是一条链，且是开链，也是简单链，但不是初等链，因是一条链，且是开链，也是简单链，但不是初等链，因为为v1出现两次。出现两次。圈圈 n若链中所含的边均不若链中所含的边均不相同，则称为相同，则称为简单链简单链；若点均不相同，则称若点均不相同，则称为为初等链初等链或或通路通路。除。除起点和终点外点均不起点和终点外点均不相同的闭链，称为相同的闭链，称为初初等回路等回路或称为或称为圈圈。n例如图中例如图中e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9是一个圈。是一个圈。连通性连通性 n若一个图

12、若一个图G的任意两点的任意两点之间均至少有一条通之间均至少有一条通路（初等链）连接起路（初等链）连接起来，则称这个图来，则称这个图G是一是一个个连通图连通图，否则称作，否则称作不连通图不连通图。n例如图中，例如图中，v1和和v6之间之间没有通路，因此它不没有通路，因此它不是连通图，而如果去是连通图，而如果去掉掉v6，则构成一个连通，则构成一个连通图。图。e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9连通的意义连通的意义 n连通是一个很重要的连通是一个很重要的概念，如果一个问题概念，如果一个问题所对应的图是一个不所对应的图是一个不连通图，则该问题一连通图，则该问题一定可以

13、分解成互不相定可以分解成互不相关的子问题来加以研关的子问题来加以研究，即可以把不连通究，即可以把不连通图分解成连通的子图图分解成连通的子图来研究。来研究。e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9子图子图 n子图的定义子图的定义 设，设，G1=(V1,E1),G2=(V2,E2)，如果如果V1 V2，又，又E1 E2，则称，则称G1是是G2的的子图子图。e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9e1 e2 e3 e4 e5v2 v3v1必须指出，并不是从图必须指出，并不是从图G2中任选一些顶点和边中任选一些顶点和边在一起就组成在一起就组成

14、G2的子图的子图G1，而只有在，而只有在G2中的一中的一条边以及连接该边的两条边以及连接该边的两个端点均选入个端点均选入G1时，时，G1才是才是G2的子图。的子图。特殊子图特殊子图 n当当G1中不包含中不包含G2中所有中所有的顶点和边，则称的顶点和边，则称G1是是G2的的真子图真子图。n部分图部分图 若若V1=V2，E1 E2，则称，则称G1为为G2的的一个一个部分图部分图。n若若V1 V2，nE1=u,v|uV1,vV1，则称，则称G1是是G2中中 由由V1导出的导出的导出子图导出子图。e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9e1 e2 e3 e4 e5v2 v

15、3v1有向图有向图n在有些图中，边是没有方向的，即在有些图中，边是没有方向的，即u,v=v,u，这，这种图称为种图称为无向图无向图。n而有些关系是不对称的，例如父子关系、上下级关而有些关系是不对称的，例如父子关系、上下级关系、加工工序的先后顺序等都具有单向性，用图来系、加工工序的先后顺序等都具有单向性，用图来表示这些关系时，得到的边是具有方向的，用带箭表示这些关系时，得到的边是具有方向的，用带箭头的线来表示，称为头的线来表示，称为弧弧。n从顶点从顶点u指向指向的弧的弧a，记作，记作a=(u,v),(u,v)(v,u)，其，其中中u称为称为a的起点，的起点，v称为称为a的终点，这样的图称为的终点

16、这样的图称为有向图有向图。仍以。仍以V表示点的集合，以表示点的集合，以A表示弧的集合，表示弧的集合，则有向图表示为则有向图表示为D（V，A）有向图例有向图例e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9有向图的链路有向图的链路 n有向图中，在不考虑边的方向时，有向图中，在不考虑边的方向时，也可以相同地定义也可以相同地定义链链，若有向图，若有向图D（V，A）中，）中，P是一个从是一个从u到到v的链，且对的链，且对P中每一条弧而中每一条弧而言，在序列中位于该弧前面的点言，在序列中位于该弧前面的点恰好是其起点，而位于该弧后面恰好是其起点，而位于该弧后面的点恰好是其终点，这个

17、链的点恰好是其终点，这个链P就就称为是称为是D中从中从u到到v的一条的一条路路。n当路的起点与终点相同，即当路的起点与终点相同，即u=v时，称作一条时，称作一条回路回路。n顶点全不相同的路称为顶点全不相同的路称为初等路初等路。n除起点和终点外点均不相同的回除起点和终点外点均不相同的回路称为路称为初等回路初等回路。e1 e2 e3 e4 e5v2 v3v1v4v5v6e6e7e8e9树及最小树问题树及最小树问题任何树至少有一个悬挂节点243512435124351如果树的节点个数为m，则边的个数为m-1树中任意两个节点之间只有唯一的一条链在树的任意两个不相邻的节点之间增加一条边，则形成唯一的圈树

18、及最小树问题树及最小树问题一个没有圈的图称为一个一个没有圈的图称为一个无圈图无圈图或称为或称为林林。一一个个连连通通的的无无圈圈图图则则称称为为树树，一一个个林林的的每每个个连连通通子子图图都都是一个树。是一个树。定理定理 以下关于树的六种不同描述是等价的：以下关于树的六种不同描述是等价的：1.无圈连通图。无圈连通图。2.无圈，无圈，q=p-1。3.连通，连通，q=p-1。4.无圈，但若任意增加一条边，则可得到一个且仅一个圈。无圈，但若任意增加一条边，则可得到一个且仅一个圈。5.连通，但若任意舍弃一条边，图便不连通。连通，但若任意舍弃一条边，图便不连通。6.每一对顶点之间有一条且仅有一条链。每

19、一对顶点之间有一条且仅有一条链。网络概念网络概念n图图只只能能用用来来研研究究事事物物之之间间有有没没有有某某种种关关系系，而而不不能能研究这种关系的强弱程度。研究这种关系的强弱程度。n网络网络 赋权的图赋权的图 n权权 程度的度量，数量描述。程度的度量，数量描述。v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2网络概念网络概念n节点与（有向）边 每一条边和两个节点关联，一条边可以用两个节点的标号表示（i，j）ji 路径（Path）前后相继并且方向相同的边序列 P=(1,2),(2,3),(3,4)42314231 网络由节点和边组成网络概念网络概念 回路（Circuit）起

20、点和终点重合的路径称为回路 =(1,2),(2,4),(4,1)回路中各条边方向相同4231 链（Chain）前后相继并且方向不一定相同的边序列称为链 C=(1,2),(3,2),(3,4)4231网络概念网络概念 连通图 任意两个节点之间至少有一条链的图称为连通图24351 圈(Cycle)起点和终点重合的链称为圈 =(1,2),(2,4),(3,4),(1,3)圈中各条边方向不一定相同4231 树(Tree)无圈的连通图称为树 树中只与一条边关联的节点称为悬挂节点网络概念网络概念n平面图(planar graph)，若在平面上可以画出该图而没有任何边相交n走过图中所有边且每条边仅走一次的闭

21、行走称为欧拉回路n定理：偶图一定存在欧拉回路(一笔画定理)n图中都是偶点的图称为偶图(even graph)哈密尔顿回路(Hamiltonian circuit)问题n连通图G(V,E)中的回路称为哈密尔顿回路，若该回路包括图中所有的点。显然哈密尔顿回路有且只有 n 条边，若|V|=nn连通图具有哈密尔顿回路的充分必要条件是什么？这个问题是由爱尔兰数学家哈密尔顿1859年提出的，但至今仍未解决n欧拉回路是对边进行访问的问题，哈密尔顿回路是对点进行访问的问题n搜索哈密尔顿回路的难度是 NP-completen任两点间都有边的图称为完全图(或全连接图)n完全图中有多少个不同的哈密尔顿回路？(n1)

22、/2n完全图中有多少个边不相交的哈密尔顿回路？(n1)/2n最小哈密尔顿回路问题(NP-complete)n哈密尔顿路径：包含图中所有点的路径n为什么说找两点间的最长路是非常困难的问题？中国邮递员问题n中国邮递员问题(Chinese Postman Problem,CPP)是由我国管梅谷教授于1962年首先提出并发表的n问题是从邮局出发，走遍邮区的所有街道至少一次再回到邮局，走什么路由才能使总的路程最短？n如果街区图是一个偶图，根据定理 3，一定有欧拉回路，CPP问题也就迎刃而解了n若街区图不是偶图，则必然有一些街道要被重复走过才能回到原出发点n显然要在奇次点间加重复边n如何使所加的边长度最

23、少n归结为求奇次点间的最小匹配(minimum weighted match)由Edmons 给出多项式算法(1965)旅行推销员问题(Traveling Salesman Problem)nTSP：设v1,v2,.,vn 为 n 个已知城市，城市之间的旅程也是已知的，要求推销员从 v1出发，走遍所有城市一次且仅一次又回到出发点，并使总旅程最短n这种不允许点重复的旅行推销员问题就是最小哈密尔顿回路问题n一般旅行推销员问题(GTSP)：允许点重复的TSPn典型的应用：n乡邮员的投递路线n邮递员开邮箱取信的路线问题n邮车到各支局的转趟问题n运钞n送奶、送水n.网络最短树问题 n最最短短树树问问题题

24、的的一一般般提提法法是是：选选取取网网络络中中的的部部分分图图，使得网络连通，且使总权数最短。使得网络连通，且使总权数最短。n在在实实际际应应用用中中，经经常常碰碰到到需需要要求求一一个个赋赋权权连连通通图图的的最最短短树树的的问问题题。例例如如，用用节节点点表表示示城城市市，用用边边表表示示可可以以在在两两个个城城市市之之间间架架设设光光缆缆，边边上上的的权权表表示示光光缆缆的的长长度度，试试求求应应如如何何架架设设光光缆缆，才才能能使使任任意意两两城城市市之间均由光缆相通，且使光缆的总长度最短。之间均由光缆相通，且使光缆的总长度最短。n求求最最短短树树的的方方法法，依依据据的的是是树树的的

25、特特点点，即即无无圈圈和和连连通通，加加上上最最短短的的要要求求，方方法法主主要要有有两两种种：一一种种称称为为破圈法破圈法，一种称为，一种称为避圈法避圈法 11.2 最短路问题最短路问题n最最短短路路问问题题的的一一般般提提法法是是：欲欲寻寻找找网网络络中中从从起起点点1 1到到终终点点n n的的最最短短路路线线，即即寻寻求求连连接接这这两两点点的的边边的的总总长长度度为为最最小小的的通通路路，最最短短路路线线中中的的网网络络大大都都是是有有向向网网络络，也也可可以以是是无无向向网络。网络。n最最短短路路问问题题是是网网络络分分析析中中的的一一个个基基本本问问题题，它它不不仅仅可可以以直直接

26、接应应用用于于解解决决生生产产实实际际的的许许多多问问题题，如如管管道道铺铺设设、线线路路安安排排、厂厂区区布布局局等等，而而且且经经常常被被作作为为一一个个基基本本工工具具，用用于于解解决决其其它的优化问题。它的优化问题。最短路问题的最短路问题的Dijkstra算法算法(双标号法）双标号法）步骤：步骤：1.1.给出点给出点V V1 1以标号以标号(0,s)(0,s)2.2.找出已标号的点的集合找出已标号的点的集合I I，没标号的点的集合，没标号的点的集合J J以及弧的集合以及弧的集合3.3.如果上述弧的集合是空集，则计算结束。如果如果上述弧的集合是空集，则计算结束。如果v vt t已标号已标

27、号（lt,ktlt,kt），则），则 v vs s到到v vt t的距离为的距离为ltlt，而从，而从 v vs s到到v vt t的最短路径，的最短路径，则可以从则可以从ktkt反向追踪到起点反向追踪到起点v vs s 而得到。如果而得到。如果v vt t 未标号，则可未标号，则可以断言不存在从以断言不存在从 v vs s到到v vt t的有向路。如果上述的弧的集合不是空的有向路。如果上述的弧的集合不是空集，则转下一步。集，则转下一步。4.4.对上述弧的集合中的每一条弧，计算对上述弧的集合中的每一条弧，计算 s sijij=l=li i+c+cij ij。在所有。在所有的的 s sijij中

28、找到其值为最小的弧。不妨设此弧为（中，找到其值为最小的弧。不妨设此弧为（Vc,VdVc,Vd），则），则给此弧的终点以双标号（给此弧的终点以双标号（s scdcd,c,c）,返回步骤返回步骤2 2。n例例1 求下图中求下图中v1到到v6的最短路的最短路n解：采用解：采用Dijkstra算法，可解得最短路径为算法，可解得最短路径为v1 v3 v4 v6n各点的标号图如下：各点的标号图如下：v23527531512v1v6v5v3v4(3,1)v23527531512 V1（0,s)v5(8,4)v6(2,1)v3(3,3)v4n例例2 电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使电

29、信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。公路的长度（单位：公里）。n解：这是一个求无向图的最短路的问题。可以把无向图的每一边解：这是一个求无向图的最短路的问题。可以把无向图的每一边（vi,vj）都用方向相反的两条弧（）都用方向相反的两条弧（vi,vj）和（）和（vj,vi）代替，就化为有向）代替，就化为有向图，即可用图，即可用Dijkstra算法来求解。也可直接在无向图中用算法来求解。也可直接在无向图中用Dijkstra算法算法来求解。

30、只要在算法中把从已标号的点到未标号的点的弧的集合改成来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。已标号的点到未标号的点的边的集合即可。V1（甲地）（甲地）151762444 31065v2V7（乙地）（乙地）v3v4v5v6n例例2最终解得：最终解得：n最短路径最短路径v1 v3 v5 v6 v7，每点的标号见下图，每点的标号见下图（0,s）V1（甲地）（甲地）1517624431065(13,3)v2 (22,6)V7（乙地）（乙地）V5(14,3)V6(16,5)V3(10,1)V4(18,5)n例例3 设备更新问题。某公司使用一台设备

31、在每年年初，公司就要决设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。备的计划，使得五年内购置费用和维修费用总的支付费用最小。n 已知：设备每年年初的价格表已知：设备每年年初

32、的价格表n 设备维修费如下表设备维修费如下表年份年份12345年初价格年初价格1111121213使用年数使用年数0-11-22-33-44-5每年维修每年维修费用费用5681118n例例3的解：将问题转化为最短路问题，如下图：的解：将问题转化为最短路问题，如下图：用用vi表示表示“第第i年年初购进一台新设备年年初购进一台新设备”,弧（弧（vi,vj）表示第）表示第i年年初购进的年年初购进的设备一直使用到第设备一直使用到第j年年初。年年初。n把所有弧的权数计算如下表：把所有弧的权数计算如下表：v1v2v3v4v5v6123456116223041592162230413172331417235

33、186(继上页继上页)把权数赋到图中，再用把权数赋到图中，再用Dijkstra算法求最短路。算法求最短路。最终得到下图，可知，最终得到下图，可知，v1到到v6的距离是的距离是53，最短路径有两条：，最短路径有两条：v1-v3-v6和和 v1-v4-v6v1v2v3v4v5v6162230415916223041312317181723 V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723 V2（16,1）16(30,1)(53,3)(53,4)11.4 网络最大流问题网络最大流问题所所谓谓最最大大流流问问题题就就是是在在一一定定的的条条件件

34、下下，要要求求流流过过网网络络的的物物流流、能能量量流流或或信信息息流流等等流流量量为为最最大大的的问问题题，在在最最大流问题中一般有如下规定：大流问题中一般有如下规定：1)网络有一个起点网络有一个起点s和一个终点和一个终点t2)网络是有向网络，即流有方向性。网络是有向网络，即流有方向性。3)在在网网络络各各条条弧弧上上都都有有一一个个权权，表表示示允允许许流流过过的的最最大大流流量量。若若以以bij表表示示由由i到到j的的弧弧上上允允许许流流过过的的最最大大流流量量，以以xij表示实际流过该弧的流量，则表示实际流过该弧的流量，则0 xij bij4)网网络络中中，除除起起点点s和和终终点点t

35、之之外外的的任任何何顶顶点点，流流入入量量总和应该等于流出量的总和。总和应该等于流出量的总和。一、最大流问题的数学模型一、最大流问题的数学模型 vs1011 65 4 7 3 915vt v5 v3 v4 v2二、最大流问题网络图论的解法二、最大流问题网络图论的解法 对网络上弧的容量的表示作改进。为省去弧的方向，如下图对网络上弧的容量的表示作改进。为省去弧的方向，如下图:(a)和和(b)、(c)和和(d)的意义相同。的意义相同。vivjvivjcij0（a）（b）cijcijvivj（cji）（c）vivj cij cji（d）求最大流的基本算法求最大流的基本算法（1）找出一条从发点到收点的路

36、在这条路上的每一条弧顺流方向的容）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。量都大于零。如果不存在这样的路，则已经求得最大流。（2）找出这条路上各条弧的最小的顺流的容量）找出这条路上各条弧的最小的顺流的容量pf，通过这条路增加网络，通过这条路增加网络的流量的流量pf。（3）在这条路上，减少每一条弧的顺流容量）在这条路上，减少每一条弧的顺流容量pf，同时增加这些弧的逆流，同时增加这些弧的逆流容量容量pf，返回步骤（，返回步骤（1）。）。例例6 6 某石油公司拥有一个管道网络，使用这个网络可以把某石油公司拥有一个管道网络，使用这个

37、网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（示。由于管道的直径的变化，它的各段管道（v vi i,v,vj j）的流）的流量量c cijij（容量）也是不一样的。（容量）也是不一样的。c cijij的单位为万加仑的单位为万加仑/小时。如小时。如果使用这个网络系统从采地果使用这个网络系统从采地 v v1 1向销地向销地 v v7 7运送石油，问每小运送石油，问每小时能运送多少加仑石油？时能运送多少加仑石油？63522241263v1v2v7v4v3v6迭代运算步骤请见演示迭代运算步骤请见

38、演示11.5 最小费用最大流问题最小费用最大流问题n最小费用最大流问题：给了一个带收发点的网络，对每一条弧最小费用最大流问题：给了一个带收发点的网络，对每一条弧（vi,vj），除了给出容量），除了给出容量cij外，还给出了这条弧的单位流量的费用外，还给出了这条弧的单位流量的费用bij，要，要求一个最大流求一个最大流F，并使得总运送费用最小。，并使得总运送费用最小。一、最小费用最大流的数学模型一、最小费用最大流的数学模型 例例7 由于输油管道的长短不一，所以在例由于输油管道的长短不一，所以在例6中每段管道（中每段管道（vi,vj）除）除了有不同的流量限制了有不同的流量限制cij外，还有不同的单位

39、流量的费用外，还有不同的单位流量的费用bij，cij的单位为万的单位为万加仑加仑/小时，小时，bij的单位为百元的单位为百元/万加仑。如图。从采地万加仑。如图。从采地 v1向销地向销地 v7运送石运送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流量和最小费用。量和最小费用。(6,6)(3,4)(5,7)(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)二、最小费用最大流的网络图论解法二、最小费用最大流的网络图论解法对网络上弧（对网络上弧（vi,vj）的（）的（cij,bij）的表示作如下改动，用）的表示作如下改动，用(b)来表示来表示(a)。vivjvivj（cij,bij）（0,-bij）（a）（b）（cij,bij）（cij,bij）vivj（cji,bji）（cij,bij）vivj（cji,bji）（0,-bji)（0,-bji)（c）（d）