第六章 网络规划与网络分析优秀PPT.ppt

《第六章 网络规划与网络分析优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第六章 网络规划与网络分析优秀PPT.ppt（91页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章第六章 网网络规划与网划与网络分析分析第一页，本课件共有91页内内 容容 图与网络图与网络树树最短路问题最短路问题网络最大流问题网络最大流问题最小费用最大流最小费用最大流案例：网络的中心与选址问题案例：网络的中心与选址问题习习 题题第二页，本课件共有91页6.1 图与网络图与网络自自然然界界和和人人类类社社会会中中许许多多事事物物以以及及事事物物之之间间的的关关系系，都都可可以以用点和线连接起来的图形来描述。用点和线连接起来的图形来描述。例如例如用用点点表表示示城城市市，点点间间联联线线表表示示城城市市间间的的道道路路，就就可可描描述述城城市市间间的的交交通通，如如果果联联线线旁旁标标注

2、注城城市市间间的的距距离离网网络络图图中中称称为为权权，形形成成加加权权图图，就就称称为为网网络络图图，就就可可进进一一步步研研究究从从一一个个城城市市到到另另一一个个城城市市的的最最短短路路径径；或或者者标标上上单单位位运运价，就可分析运费最小的运输方案。价，就可分析运费最小的运输方案。第三页，本课件共有91页例6-1由点及不带箭头的连线所组成的图形。由点及不带箭头的连线所组成的图形。点的相对位置如何、点与点之间联线的长短曲点的相对位置如何、点与点之间联线的长短曲直，对反映对象之间的关系并不重要。直，对反映对象之间的关系并不重要。表示表示5个球队之间的赛事关系。个球队之间的赛事关系。点点a,

3、b,c,d,e,f-5个球队，个球队，两点的连接两点的连接-两球队之间的赛事关系。两球队之间的赛事关系。第四页，本课件共有91页例例 6-2 由点及带箭头的连线所组成的图形。由点及带箭头的连线所组成的图形。图图 6-2 是一张管道运输网示意图是一张管道运输网示意图-城市间物资运输关系，城市间物资运输关系，v1,v2,v3,v4,v5,v6,v7-7个城市，个城市，箭箭线线旁旁的的数数字字-物物流流的的最最大大容容量量。现现在在要要求求出出从从v1地地到到v7地地的可运送的最大流方案。的可运送的最大流方案。边边-两点间不带箭头的连线两点间不带箭头的连线弧弧-带箭头的连线。带箭头的连线。第五页，本

4、课件共有91页一、无向图一、无向图由点和边由点和边组成的图称为无向图，图组成的图称为无向图，图 6-3即为无向图即为无向图（1）无向图）无向图定义定义6-1 无向图无向图是一个无序二元组（是一个无序二元组（V，E），记为），记为G=（V,E），其中是），其中是p个点的集合，简称定点集；个点的集合，简称定点集；E=（e1，e2，eq）是是条条边边的的集集合合，简简称称边边集集合合，并并且且是是一个无序二元组，记为一个无序二元组，记为 。顶点数：点集顶点数：点集V中中元素的个数称为图元素的个数称为图G的顶点数，记为的顶点数，记为。如图。如图 6-3，第六页，本课件共有91页为为的端点，的端点，为为

5、的关联边。的关联边。若点若点vi,vj有边相连，即有边相连，即，则称，则称vi,vj相邻，相邻，vi,vj与与e关联关联。v3,v5相邻，相邻，v3,v5与与e7关联关联。图图63。如图。如图 6-3，端点：对于边端点：对于边，称，称vi，vj为为e的端点。的端点。e为为vi,vj的关联边。的关联边。边数边数：边集：边集 E中元素的个数，记为中元素的个数，记为第七页，本课件共有91页（2）简单图不含环和多重边的图称为简单图，含有多重边的图称为多重图。不含环和多重边的图称为简单图，含有多重边的图称为多重图。(3)点的次（度）点的次（度）以点以点v为为端点的边数叫做点端点的边数叫做点v的次，记作的

6、次，记作d(v)。如图如图6-3中中,d(v1)=4,d(v2)=4。若若，则称，则称称为图称为图G的次序列。的次序列。环（自回路）：一条边的两个端点如果相同，称此边为环。如环（自回路）：一条边的两个端点如果相同，称此边为环。如 图图6-3中的中的e1。多重边多重边：两个点之间多于一条边的，如图：两个点之间多于一条边的，如图6-3中的中的e4，e5.第八页，本课件共有91页 次为次为 1 的点的点-悬挂点，连接悬挂点的边悬挂点，连接悬挂点的边-悬挂边。悬挂边。次为次为0的点的点-孤立点。孤立点。次为奇数的点次为奇数的点-奇点，次为偶数的点奇点，次为偶数的点-偶点。偶点。定定理理 6-1 任任何

7、何图图G=（V,E）中中，所所有有点点的的次次数数之之和和等等于于边边数的数的2倍。即倍。即 证证：由由于于每每条条边边必必有有两两个个顶顶点点关关联联，在在计计算算点点的的次次时时，每每条条边边均均被计算了两次，所以顶点次数之和等于边数的被计算了两次，所以顶点次数之和等于边数的2倍。倍。第九页，本课件共有91页定理定理 6-2 任何图任何图G=（V,E）中，奇点的个数必为偶数。）中，奇点的个数必为偶数。证：设图证：设图 中奇点与偶点的集合分别为中奇点与偶点的集合分别为V1和和V2，由定理由定理 6-1 知知由于由于2q(G)为偶数，而为偶数，而 是若干个偶数之和，也是若干个偶数之和，也为偶数

8、。所以为偶数。所以 必为偶数，即奇点的个数必为偶数，即奇点的个数 必必为偶数。为偶数。第十页，本课件共有91页（4）链）链 链：链：对于无向图对于无向图G=（V,E）,称顶点和边交替的序列称顶点和边交替的序列 为连接为连接和和的一条链，简记为的一条链，简记为。其中。其中-链的两个端点。链的两个端点。-是链。是链。和和两个端点重合的链，称为圈。在一个图中，如果任何两个顶点之两个端点重合的链，称为圈。在一个图中，如果任何两个顶点之间都有一条链，该图称为连通图。间都有一条链，该图称为连通图。第十一页，本课件共有91页二、有向图二、有向图（1）有向图）有向图 有向图是一个有序二元组有向图是一个有序二元

9、组（V,A），记为），记为D（V,A），其中），其中是是p个顶点的集合，个顶点的集合，是是q条弧条弧的集合，并且的集合，并且是一个有序二元组，记为是一个有序二元组，记为并称并称 是以是以vi为始点，为始点，vj为终点的弧，为终点的弧，i，j的顺序不能颠倒，的顺序不能颠倒，弧的方向弧的方向-箭头标识。箭头标识。由点和弧组成的图称为有向图由点和弧组成的图称为有向图第十二页，本课件共有91页（2）简单有向图）简单有向图 两个端点重合的弧称环。如图两个端点重合的弧称环。如图 6-4 中的中的a1.图图6-4两个端点之间的同向弧数大于等于两个端点之间的同向弧数大于等于2，称为多重弧。，称为多重弧。无环也

10、无多重弧的有向图称为简单有向图。无环也无多重弧的有向图称为简单有向图。第十三页，本课件共有91页（3）点的出次和入次）点的出次和入次以点以点v为起点的弧数叫做点为起点的弧数叫做点v的出次，记作的出次，记作以点以点v为终点的弧数叫做点为终点的弧数叫做点v的入次，记作的入次，记作 称称 为点为点v的次。的次。（4）路）路 在有向图在有向图D=(V,A)中，点和弧交替的序列中，点和弧交替的序列，若有，若有或或，则称，则称P是一条链接是一条链接和和的有向路。的有向路。第十四页，本课件共有91页三、网络三、网络 实实际际问问题题中中，往往往往只只用用图图来来描描述述所所研研究究对对象象之之间间的的关关系

11、系还还不不够够，如如果果在在图图中中赋赋予予边边一一定定的的数数量量指指标标，我我们们常常称称之之为为“权权”。依依据据研研究究问问题题的的需需要要，权权可可以以代代表表距距离离，也也可可以以代代表表时时间间、费费用用、容容量量、可可靠靠性性等等。通通常常把把这种这种赋权图称为网络赋权图称为网络。与与无无向向图图和和有有向向图图相相对对应应，网网络络又又分分为为无无向向网网络络和和有有向网络。向网络。第十五页，本课件共有91页图的矩阵表示方法：，其中，其中 则称则称A为为G的的关关联矩阵联矩阵。关联指顶点与边的关系。关联指顶点与边的关系。关联矩阵：在图关联矩阵：在图G=(V,E)中，中，V=(

12、v1,v2,vp),E=(e1,e2,eq),构造一个矩阵构造一个矩阵第十六页，本课件共有91页，其中，其中 则称则称A为为G的邻接的邻接矩阵。邻接指顶点与顶点的关系。矩阵。邻接指顶点与顶点的关系。邻接矩阵：邻接矩阵：在图在图G=(V,E)中，中，V=（v1,v2,vp),E=(e1,e2,eq),构造一个矩阵构造一个矩阵第十七页，本课件共有91页权矩阵权矩阵：在图在图G=(V,E)中，中，V=(v1,v2,vp),E=(e1,e2,eq),其边其边vi,vj有权有权wij。构造一个矩阵。构造一个矩阵 ，其中，其中则则称称A为为G的权的权矩阵。矩阵。第十八页，本课件共有91页6.2 6.2 树

13、树a）b）实例：已知有实例：已知有 5个城市，要在它们之间架设电话线网，要求任何个城市，要在它们之间架设电话线网，要求任何两个城市都可以彼此通话（允许通过其他城市），并且电话线的两个城市都可以彼此通话（允许通过其他城市），并且电话线的条数最少。条数最少。满足要求的电话网必须是：满足要求的电话网必须是：连通的；连通的；不含圈的。满足这两点要求的图称为不含圈的。满足这两点要求的图称为“树树”。第十九页，本课件共有91页6.2.1 6.2.1 树的基本概念与性质树的基本概念与性质定义定义：连通且不含圈的无向图称为树。树中次为：连通且不含圈的无向图称为树。树中次为1的顶点称为树叶的顶点称为树叶(悬挂点

14、悬挂点)，次大于，次大于 1的顶点称为分枝点。的顶点称为分枝点。树的性质可用下面定理给出：树的性质可用下面定理给出：设有图设有图G=(V,E)，n和和m分别为图分别为图G的顶点数和边数，则下列命的顶点数和边数，则下列命题是等价的：题是等价的：（1）G是一个树。是一个树。（2）G无圈，且无圈，且m=n-1。（3）G连通，且连通，且m=n-1。（4）G无圈，但每加一条新边即存在唯一一个圈。无圈，但每加一条新边即存在唯一一个圈。（5）G 连通，但每舍去一条边就变成不连通。连通，但每舍去一条边就变成不连通。（6）G中任意两点，有唯一路相连。中任意两点，有唯一路相连。第二十页，本课件共有91页定义定义6

15、-7 图图G=(V,E)，若，若E是是E的子集，的子集，是是V的子集，且的子集，且中的边仅与中的边仅与中的顶点相关联，则称中的顶点相关联，则称是是的一个子图。特别地，若的一个子图。特别地，若，则，则称为称为子图（或支撑子图）。子图（或支撑子图）。的生成的生成定义定义6-8 若图若图G的生成子图是一棵树，则称该树为的生成子图是一棵树，则称该树为G的生成树，的生成树，或简称为图或简称为图G的树。的树。图图G中属于生成树的边称为树枝，不在生成树中的边称为弦。中属于生成树的边称为树枝，不在生成树中的边称为弦。第二十一页，本课件共有91页定理定理 6-4 图图G=(V,E)有生成树的充分必要条件为有生成

16、树的充分必要条件为 G是连通图是连通图。证明：必要性由定义直接可得。证明：必要性由定义直接可得。充充分分性性的的证证明明过过程程如如下下：设设图图G是是连连通通的的。若若G不不含含圈圈，则则 G就就是是其其自自身身的的一一棵棵生生成成树树；若若G含含有有圈圈，任任取取一一个个圈圈，从从圈圈中中任任意意去去掉掉一一条条边边，得得到到图图G的的一一个个生生成成子子图图G1。如如果果G1不不含含圈圈，那那么么G1是是G的的一一棵棵生生成成树树；如如果果G1仍仍含含有有圈圈，那那么么从从G1中中任任取取一一个个圈圈，从从圈圈中中再再任任意意去去掉掉一一条条边边，得得到到图图 G的的一一个个生生成成子子

17、图图G2。重重复复使使用用此此法法使使每每个个圈圈都都受受到到破破坏坏，最最后后可可以以得得到到G的的一一个生成子图个生成子图Gk，它是不含圈的生成子图。这就是，它是不含圈的生成子图。这就是G一棵生成树。一棵生成树。第二十二页，本课件共有91页6.2.2 最小支撑树及其算法最小支撑树及其算法（1）构造支撑树的算法）构造支撑树的算法 1)破圈法破圈法 破圈法思路：任取一圈，从圈中去掉任一条边，再对余下的圈重复相同的步骤，直到图中所有的圈破掉为止。第二十三页，本课件共有91页 2）避圈法）避圈法 避圈法思路：将不连通的无圈图通过边的增加，逐步变成连避圈法思路：将不连通的无圈图通过边的增加，逐步变成

18、连 通无圈图。通无圈图。避圈法步骤：避圈法步骤：为连通图。为连通图。步骤步骤1 始取始取 ；步步骤骤 2 若若Gk 连连通通，则则Gk为为支支撑撑树树；若若Gk不不连连通通，任任选选图图G边边集集E中中 的的 一一 边边e，使使e的的 两两 个个 端端 点点 分分 属属 两两 个个 不不 同同 的的 连连 通通 分分 图图，得得 ，；步骤步骤 3 若若 ，则重复步骤，则重复步骤 2；否则，；否则，Gk一定是支撑树。一定是支撑树。第二十四页，本课件共有91页 将支撑树的构造与边权的选择结合，产生最小树的概念。将支撑树的构造与边权的选择结合，产生最小树的概念。（2）最小支撑树定义）最小支撑树定义

19、设设有有一一个个连连通通图图G=(V,E),每每一一边边e=vi,vj有有一一个个权权w(e)=wij，如果是的一个支撑树，称中所有边的权之和为支撑树的权，记为：如果是的一个支撑树，称中所有边的权之和为支撑树的权，记为：如如果果支支撑撑树树T*的的权权W(T*)是是G的的所所有有支支撑撑树树中中权权数数最最小小的的，则则称称T*是是G的最小支撑树（也称最小树），即的最小支撑树（也称最小树），即第二十五页，本课件共有91页（3）寻找最小支撑树的算法）寻找最小支撑树的算法 寻寻找找最最小小支支撑撑树树也也可可以以用用上上面面介介绍绍的的破破圈圈法法和和避避圈圈法法，但要在舍边和增边时，增加一些边的

20、权数的限制。但要在舍边和增边时，增加一些边的权数的限制。1）破圈法）破圈法 步骤：步骤：从图从图G中任取一圈，去掉这个圈中权数最大的一条边，得一中任取一圈，去掉这个圈中权数最大的一条边，得一支撑子图支撑子图G1。在。在G1中再任取一圈，再去掉圈中权数最大的一中再任取一圈，再去掉圈中权数最大的一条边，得条边，得G2。如此继续下去，一直到剩下的子图中不再含。如此继续下去，一直到剩下的子图中不再含圈为止。该子图圈为止。该子图G1就是的最小支撑树就是的最小支撑树T*。第二十六页，本课件共有91页2）Kruskal算法（避圈法）算法（避圈法）1956年年 基本思想基本思想-每次将一条权最小的弧加入子图每

21、次将一条权最小的弧加入子图T 中，中，并保证不形成圈。即按照边长由小到大排序，如并保证不形成圈。即按照边长由小到大排序，如果当前弧加入后不形成圈，则加入这条弧。当弧果当前弧加入后不形成圈，则加入这条弧。当弧有有n-1条条 时，即为最小树。时，即为最小树。第二十七页，本课件共有91页例例6-4 用用Kruskal算法求解下图算法求解下图(6-8)所示网络的最小树，每所示网络的最小树，每 条边上的数表示该边的权值。条边上的数表示该边的权值。第二十八页，本课件共有91页3）Prim算法算法(边割法边割法)1957年年核核心心思思想想-不不断断扩扩展展一一个个子子树树，使使其其逐逐步步包包含含所所有的

22、顶点。有的顶点。具具体体增增边边的的选选择择，是是在在当当前前子子树树的的顶顶点点集集合合与与补补集集合合所形成的边割中选择最小的边。所形成的边割中选择最小的边。Prim算算法法是是一一个个子子树树逐逐步步扩扩张张的的过过程程，Kruskal算算法法是是多个子树逐步融合的过程。多个子树逐步融合的过程。第二十九页，本课件共有91页Prim算法：算法：步骤步骤0 从图中任选一点从图中任选一点vi，让，让viS，图中其余点均包含在，图中其余点均包含在 中；中；步骤步骤2 从从S和和 之间的连线中找出最小边，这条边一定包含在之间的连线中找出最小边，这条边一定包含在 最小支撑树内，不妨设最小边为最小支撑

23、树内，不妨设最小边为vi,vj，将，将vi,vj标记成标记成 最小支撑树内的边；最小支撑树内的边；步骤步骤3 令令 ，；步骤步骤4 重复步骤重复步骤2、步骤、步骤3，一直到图中所有点均包含在，一直到图中所有点均包含在S中中 为止。为止。第三十页，本课件共有91页例题例题6-5 用用Prim算法求解图算法求解图69（a）中的最小树。）中的最小树。第三十一页，本课件共有91页解：求解结果见图解：求解结果见图69（b）第三十二页，本课件共有91页 例例6-在在一一个个地地区区有有一一个个公公共共服服务务机机构构，如如飞飞机机场场、医医院院等等，图图610中中O所所示示。三三个个乡乡镇镇（图图6-10

24、中中的的v1,v2,v3所所示示）需需要要连连接接到到这这个个公公共共服服务务机机构构。乡乡镇镇与与服服务务机机构构之之间间、乡乡镇镇与与乡乡镇镇之之间间的的连连接接高高速速公公路路的的造造价价为为边边的的权权。问问如如何何构构建建这这个连接网络并分配建设费用？个连接网络并分配建设费用？第三十三页，本课件共有91页解：是一个最小支撑树的构建和建设成本分担问题。解：是一个最小支撑树的构建和建设成本分担问题。将将v1,v2,v3分别连接到分别连接到O的建设成本为的建设成本为 C(v1)9，C(v2)10，C(v3)11；将将 v1,v2 连接到连接到O的最小树的建设成本为的最小树的建设成本为C(v

25、1,v2)17，同样，同样，C(v1,v3)18，C(v2,v3)11；将将3个顶点连接到个顶点连接到 的最小树的最小树O的建设成本的建设成本C(v1,v2,v3)18。设设分分别别承承担担的的建建设设费费用用为为x1,x2,x3，则则建建设设费费用用的的分分配配应应该该满满足：足：有有无无限限个个向向量量满满足足上上式式，每每个个向向量量都都可可以以作作为为一一个个建建设设费用的分配方案。费用的分配方案。第三十四页，本课件共有91页6.3 最短路问题最短路问题 优化问题优化问题-如设备更新、管道铺设、线路安排、如设备更新、管道铺设、线路安排、厂区布局等。厂区布局等。曾介绍动态规划解法，但某些

26、最短路问题（如道曾介绍动态规划解法，但某些最短路问题（如道路不能整齐分段者）构造动态规划方程比较困难，路不能整齐分段者）构造动态规划方程比较困难，而图论方法则比较有效。另外，这个问题相对比而图论方法则比较有效。另外，这个问题相对比较简单，其算法经常做为其他问题的子算法而调较简单，其算法经常做为其他问题的子算法而调用。用。第三十五页，本课件共有91页6.3.1 基本概念与基本概念与Bellman方程方程 最最短短路路问问题题-设设N=(V,A,W)为为网网络络图图，图图中中各各边边(vi,vj)有有权权wij（wij=表表示示vi,vj之之间间没没有有边边），v1为为起起始始点点，vj为为图图中

27、中任任意意一一点点。网网络络中中有有多多条条v1vj的的路路P,每每条条路路的的权权是是其其所所有有构成弧的权之和。构成弧的权之和。求求一一条条v1vj的的路路 ，使使它它是是从从v1到到vj的的所所有有路路中中总总权权最最小小的的路。即：优化问题路。即：优化问题第三十六页，本课件共有91页 对对于于网网络络中中的的一一个个圈圈，其其权权是是其其所所构构成成边边的的权权之之和和。权为正的圈权为正的圈-正圈；正圈；权为负的圈权为负的圈-负圈；负圈；权为权为0的圈的圈-零圈。零圈。第三十七页，本课件共有91页令令uj表表示示网网络络中中v1vj的的最最短短路路的的长长度度。基基于于动动态态规规划划

28、中中递递归归方程的思想，得到求解最短路问题的递归关系如下：方程的思想，得到求解最短路问题的递归关系如下：定定理理 6-5 设设有有向向网网络络G中中只只含含正正圈圈，并并且且从从点点v1到到其其余余点点 vj都都有有限长度的有向路，那么有有限长度的有向路，那么(6.1)有唯一有限解。有唯一有限解。第三十八页，本课件共有91页定定理理 6-6 设设N=(V,A)不不含含圈圈，则则N的的顶顶点点可可以以重重新新编编号，使号，使 。3例例5.1-最短路径问题V1V8V7V5V4V3V9V10V212353313424135215V63第三十九页，本课件共有91页例例6-7 计算如下网络中计算如下网络

29、中v1到到 各点的最短路。各点的最短路。解：这是一个有圈网络图，但解：这是一个有圈网络图，但v1是起始点，故进入是起始点，故进入v1的弧可以删去。的弧可以删去。对顶点进行重新标号，得到网络图，图对顶点进行重新标号，得到网络图，图6-11(b)。第四十页，本课件共有91页Bellman方程的计算：方程的计算：按照按照ui，求出最短路网络，图，求出最短路网络，图6-11(c)。第四十一页，本课件共有91页6.3.2 Dijkstra算法算法(wij0)-1959年 双标号法双标号法-图中的每个点图中的每个点vj 赋予两个参数（标号）赋予两个参数（标号）uj-从起点从起点v1到到vj的最短路的长度，

30、是距离标号；的最短路的长度，是距离标号；-前前趋趋标标号号，是是记记录录在在v1到到vj的的最最短短路路上上，vj 前前面面一一个个邻邻点点的的下下标标，用用来来标标识识最最短短路路路路径径，从从而而可可对对终终点点到到始始点进行反向追踪，找到点进行反向追踪，找到v1到到vj的最短路。的最短路。通过不断修改这些标号，进行迭代计算。通过不断修改这些标号，进行迭代计算。第四十二页，本课件共有91页Dijkstra 算法：步骤步骤 0 给起点给起点v1标号标号(0,s)，表示从，表示从v1到到v1的距离为的距离为0，v1为起为起 点。点。步骤步骤1 如果如果S=V，则，则uj即为即为v1到到vj的最

31、短路的长度，最短路可的最短路的长度，最短路可 以按照以按照 pred(j)记录的信息，反向追踪即可获得，结束。记录的信息，反向追踪即可获得，结束。否则，转步骤否则，转步骤2。步骤步骤2 求出弧集求出弧集 。若。若 ，表明从，表明从 所有已经赋予标号的顶点出发，不再有这样的弧，它所有已经赋予标号的顶点出发，不再有这样的弧，它 的另一顶点尚未标号，则计算结束。对于已有标号的顶的另一顶点尚未标号，则计算结束。对于已有标号的顶 点，可求得从到达这个顶点的最短路，对于没有标号的点，可求得从到达这个顶点的最短路，对于没有标号的 顶点，则不存在从顶点，则不存在从v1到达这个顶点的路。到达这个顶点的路。若弧集

32、，若弧集，转步骤转步骤3。第四十三页，本课件共有91页 步骤步骤3 对弧集对弧集A中的每一条弧中的每一条弧(vi,vj)，计算，计算 。则则vi 赋予双标号赋予双标号 ，其中，其中 。转步骤。转步骤 2 经经上上述述一一个个循循环环的的计计算算，将将求求出出v1到到一一个个顶顶点点vj的的最最短短路路及其长度，从而使一个顶点及其长度，从而使一个顶点vj得到双标号。得到双标号。若有若有n个顶点，则最多计算个顶点，则最多计算(n-1)循环，即得最后结果。循环，即得最后结果。第四十四页，本课件共有91页例例6-8 求求v1到其余各点的最短路到其余各点的最短路 第四十五页，本课件共有91页 至此，自顶

33、点至此，自顶点1至其余顶点的最短路都已求得。如下图粗线示至其余顶点的最短路都已求得。如下图粗线示 标号法是一种按标号值从小到大的逐步外探法。标号法是一种按标号值从小到大的逐步外探法。第四十六页，本课件共有91页补充补充(wij不全0，存在wij0)。抹掉图上所有标号，重复抹掉图上所有标号，重复 步骤步骤 2-步骤步骤 3。第七十二页，本课件共有91页步步骤骤 4 写写出出最最小小截截集集 和和最最大大流流 的的流流量量 ，终止计算，终止计算。例例6-10 试试用用 FordFulkerson 标标号号法法求求图图 618所所示示的的网网络络最最大流，括号中，第一个数字是容量，第二个数字是容量。

34、大流，括号中，第一个数字是容量，第二个数字是容量。第七十三页，本课件共有91页第七十四页，本课件共有91页第七十五页，本课件共有91页第七十六页，本课件共有91页第七十七页，本课件共有91页图图 619第七十八页，本课件共有91页6.5 最小费用最大流最小费用最大流 在在上上节节最最大大流流问问题题中中，每每一一个个可可行行流流在在现现实实生生活活中中，还还对对应应着着一一定定的的费费用用，许许多多情情况况下下优优化化目目标标不不但但要要求求流流量量尽尽可可能能的的大大，还还要要求求费费用用尽尽可可能能的的小小。在在一一个个网网络络中中每每条条弧弧都都有有“容容量量”和和“费费用用”两两个个限

35、限制制的的条条件件下下，寻寻求求vs到到 vt 的的最最大大流流，使使该最大流在所有最大流中费用达到最小。该最大流在所有最大流中费用达到最小。第七十九页，本课件共有91页 给给出出网网络络D=(V,A,C,B)，其其中中C是是容容量量，B是是费费用用，即即对对于于每每条条弧弧，有有容容量量cij0，有有费费用用bij0。对对于于D的的一一个个可可行行流流 ，定义其，定义其费用费用为为 求求解解最最小小费费用用最最大大流流问问题题的的基基本本思思想想是是在在寻寻求求最最大大流流的的算算法法过过程程中中，不不但但通通过过增增广广链链使使流流量量逐逐步步增增加加，还还要要考考虑虑费用的约束，即每次可

36、行流的调整都使费用增加最小。费用的约束，即每次可行流的调整都使费用增加最小。第八十页，本课件共有91页当当沿沿着着可可行行流流 f 的的一一条条的的增增广广链链，以以调调整整 f，得得到到新新的的可可行行流流 f 时，时，b(f)比比 b(f)增加：增加：1时，费用的增加量是时，费用的增加量是 这这个个数数值值反反映映了了增增广广链链的的好好坏坏，这这个个数数值值越越小小，这这条条增增广广链就越好。链就越好。第八十一页，本课件共有91页 把把 称为增广链称为增广链的费用。的费用。若若 f 是流值为是流值为v(f)的所有可行流中费用最小者，而的所有可行流中费用最小者，而 是关于是关于 f 的费用

37、最小的增广链，那么沿的费用最小的增广链，那么沿去调整可行流去调整可行流 f，得到可行流，得到可行流 f，新可行流就是流值为，新可行流就是流值为v(f)的所有可行流中费用最小的可的所有可行流中费用最小的可行流。行流。确确定定一一个个最最小小费费用用可可行行流流,然然后后找找出出最最小小费费用用增增广广链链，按按照照最最小小费费用用增增广广链链对对可可行行流流进进行行调调整整，一一直直调调整整下下去去，直直到到找找不不出增广链为止，这样得到的可行流即为最小费用最大流。出增广链为止，这样得到的可行流即为最小费用最大流。第八十二页，本课件共有91页 为为了了寻寻找找最最小小费费用用增增广广链链，我我们

38、们以以原原可可行行流流 f 为为基基础础，构构造造一一个个新新赋赋权权图图D(f)=(V,A(f),W)。D(f)的的顶顶点点为为原原网网络络D的的顶顶点点V，把把D中中的的每每条条弧弧A变变为为两两条条方方向向相相反反的的两两条条弧弧，,形成弧集合形成弧集合 A(f),。弧的赋权原则如下：。弧的赋权原则如下：对于弧对于弧，有，有 对于弧对于弧,有有第八十三页，本课件共有91页最小费用最大流的算法：最小费用最大流的算法：（1）取零流为初始最小费用可行流，记为）取零流为初始最小费用可行流，记为f(0)。（2)若若第第k步步得得到到最最小小费费用用可可行行流流f(k),则则构构造造一一个个新新赋赋

39、权权图图D(f(k),在在D(f(k)中中寻寻求求从从vsvt 最最短短路路。若若不不存存在在最最短短路路，则则目目前前的的可可行行流流F(k)即即为为网网络络D的的最最小小费费用用最最大大流流；若若存存在在最最短短路路，则则在在原原网网络络D中中得得到到了了相相应应的的最最小小费费用用增增广广链链，对对F(k)进进行行调整，调整量为调整，调整量为第八十四页，本课件共有91页（3）调整方法如下：）调整方法如下：重复进行上述步骤，直到找不出增广链为止。重复进行上述步骤，直到找不出增广链为止。第八十五页，本课件共有91页第八十六页，本课件共有91页第八十七页，本课件共有91页 D(f(0)中中最最

40、短短路路见见图图6-22中中的的粗粗线线所所示示，由由此此找找到到最最小小费费用用增广链，见图增广链，见图6-21中粗线所示。中粗线所示。利用最小费用增广链对可行流进行调整，调整后的新流见图利用最小费用增广链对可行流进行调整，调整后的新流见图6-23。（2）继续进行可行流的调整：）继续进行可行流的调整：第八十八页，本课件共有91页 图图6-24中中的的最最短短路路见见粗粗线线所所示示，因因此此找找到到最最小小费费用用增增广广链链，见见图图6-23中中粗粗线线所所示示。利利用用最最小小费费用用增增广广链链对对可可行行流流进进行行调调整整，调整后的新流见图调整后的新流见图6-25。第八十九页，本课件共有91页第九十页，本课件共有91页 上上图图已已经经找找不不出出 的的路路，因因此此也也没没增增广广链链了了，即即图图6-25所所示示的的可可行行流流即即为为最最小小费费用用最最大大流流，流流值值v(f)5，其费用为，其费用为31。第九十一页，本课件共有91页