《第11章图与网络模型ppt课件.ppt》由会员分享，可在线阅读，更多相关《第11章图与网络模型ppt课件.ppt（73页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、8/1/2022 运运 筹筹 学学 Operations Research Chapter 11 网络模型网络模型Network Modeling11.1基本概念基本概念11.2 最小最小(支撑支撑)树问题树问题11.3 最短路问题最短路问题 11.4 最大流问题最大流问题11.5最小费用最大流最小费用最大流11.6 中国邮路问题中国邮路问题 8/1/2022欧拉早年解决著名的哥尼斯堡七桥问题，哥尼斯堡城市中有一条河，河中有两个岛，河的两岸和河中的两个小岛有7座桥。当地居民提出：一个步行者能否通过每座桥一次且仅一次就能返回原出发地。DCA岸B岸8/1/2022欧拉将此问题归为一笔画问题，即能否
2、从某点开始一笔画出这个图形，最后回到出发点，而不重复。CDAB欧拉证明了这是不可能的。8/1/2022在这一时期，还有许多游戏问题，诸如环球旅行、迷宫问题、博奕问题等难题，吸引了许多学者，这些问题看起来似乎是一些无足轻重的游戏，但常常 是由于这些游戏引出了许多实用意义的新问题，开辟了新学科。图论在现实生活中很多，如各种通信网络的合理架设，交通网络的合理分布，邮递员送信，怎么走完他负责投递的全部街道，完成任务回到邮局，使走的路线最短，电子商务物流配送中的最佳运送路线的选择等，都属于图论问题。8/1/20225v1v2v3v4v5v6843752618图图111运筹学中研究的图具有下列特征：运筹学
3、中研究的图具有下列特征：（1）用点表示研究对象，用边（有方向或无方向）表示对）用点表示研究对象，用边（有方向或无方向）表示对象之间某种关系。象之间某种关系。（2）强调点与点之间的关联关系，不讲究图的比例大小与）强调点与点之间的关联关系，不讲究图的比例大小与形状。形状。（3）每条边上都赋有一个权，其图称为赋权图。实际中权）每条边上都赋有一个权，其图称为赋权图。实际中权可以代表两点之间的距离、费用、利润、时间、容量等不同的可以代表两点之间的距离、费用、利润、时间、容量等不同的含义。含义。（4）建立一个网络模型，求最大值或最小值。）建立一个网络模型，求最大值或最小值。8/1/202211.1 图的基
4、本概念图的基本概念 8/1/2022例1：五个队比赛的图v1v3v4v1v3v4v2v1v1v58/1/2022 图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，图论中的图与几何图、工程图是不一样的。8/1/2022从以上图可看出图：（1）图是由一些点和一些点之间的连线（带箭头或不带箭头）所组成的。（2）具有“对称性”和“不对称性”概念：概念：边边：两点之间的不带箭头的连线。弧弧：两点之间的带箭头的连线。无向图无向图：由点和边组成。记为（，）点的集合边的集合8/1/2022e3一条连结
5、vi,vjV的边,记为vi,vj或vj,vi上图中：v1,v2,v3,v4 E e1,e2,.e7 e1=v1,v2, e2=v2,v1e7=v4,v4 v4v1v2v3e6e5e4e2e1e7e38/1/2022v9a2有向图有向图：由点和弧组成。记为D=(V,A)一条方向从vivj的弧,记为：（vi,vj)V=v1,.,v7 A=a1,.,a11a1=(v1,v2) a2=(v1,v3) .弧的集合v1a4a5a6a7a10a11v3v2v5v4v6v7a8a1a38/1/2022点数记为：p(G), p(D)边数记为：q(G) 弧数记为：q(D)下面介绍一些名词，先考虑无向图：e=u,v
6、,称u、v是e的端点，也称u、v是相邻的相邻的。称e是u(v)的关联边关联边。多重边多重边：两点之间有多于一条的边。简单图简单图：无环，无多重边的图。多重图多重图：无环，但允许有多重边的图。8/1/2022次次：以点v为端点的边的个数，记为d(v).悬挂点悬挂点：次为1的点。悬挂边悬挂边：悬挂点的关联边孤立点孤立点：次为0的点。定理1：在G=(V,E)中，所有点的次之和是边数的两倍。Vvqvd2)(8/1/2022奇点奇点：次为奇数的点。偶点偶点：次为偶数的点。定理2：任一个图中，奇点的个数为偶数。（因为奇点的边数为奇数，所以个数为偶数）qvdvdVvVv2d(v)()(Vv偶偶奇奇为偶数8/
7、1/2022链链：G=(V,E)，一个点、边交错序列（vi1,ei1,vi2,ei2,.,v(ik-1),e(ik-1),vik)。如满足eit=vit,v(it+1),称为一条连结vi1,vi2,.,v(ik-1),vik的链。记为（vi1,vi2,.,v(ik-1),vik）圈圈：链（vi1,vi2,.,v(ik-1),vik）中，若vi1=vik,称为圈。记为（vi1,vi2,.,v(ik-1),vi1）。初等链初等链：链中各点都不同。初等圈初等圈：圈中除头尾外，中间点都不同。8/1/2022e7e4简单链（圈）简单链（圈）：链（圈）中含的边都不相同。 （点可以相同）以后提到的链（圈），
8、除非特别交代，都指初等链（圈）。v1e1e2e3e6e8e9v2v4v3v6v5v7e10v9v8e58/1/2022(v1,v2,v3,v4,v5,v3,v6,v7)是简单链。(v1,v2,v3,v6,v7)是初等链。连通图连通图：G中，若任何两点之间，至少有一条链，否则，称为不连通图。连通分图连通分图：若 不连通，它的每个连通，部分称为连通分图。支撑子图支撑子图：G=(V,E)，如果G=(V,E),使V=V及E E,则G为G的一个支撑子图.8/1/2022有向图中有向图中:路路:如有（vi1,ai1,vi2,ai2,.,v(ik-1),a(ik-1),vik)是D中一条链，且有ait=(v
9、it,v(it+1),称从vi1vik的一条路。回路回路：若路中第一点和最后一点相同，则称为回路。支撑子图8/1/202211.2 最小最小(支撑支撑)树问题树问题 Minimal (Spanning)Tree Problem8/1/202211.2.1树的概念树的概念 一个无圈并且连通的无向图称为树图或简称树一个无圈并且连通的无向图称为树图或简称树(Tree)。组织机。组织机构、家谱、学科分支、因特网络、通讯网络及高压线路网络等构、家谱、学科分支、因特网络、通讯网络及高压线路网络等都能表达成一个树图都能表达成一个树图 。 可以证明：可以证明：（1）一棵树的边数等于点数减）一棵树的边数等于点数
10、减1；（2）在树中任意两个点之间添加一条边就形成圈；）在树中任意两个点之间添加一条边就形成圈；（3）在树中去掉任意一条边图就变为不连通。）在树中去掉任意一条边图就变为不连通。 在一个连通图在一个连通图G中，中，取部分边连接取部分边连接G的所的所有点组成的树称为有点组成的树称为G的的部分树部分树或或支撑树支撑树(Spanning Tree )。图图112是图是图111的部分树。的部分树。 v1v2v3v4v5v64321图图112711.2 最小树问题最小树问题 Minimal tree problem8/1/202211.2.2 最小部分树最小部分树将网络图将网络图G边上的权看作两点间的长度（
11、距离、费用、边上的权看作两点间的长度（距离、费用、时间），定义时间），定义G的部分树的部分树T的长度等于的长度等于T中每条边的长中每条边的长度之和，记为度之和，记为C(T)。 G的所有部分树中长度最小的部的所有部分树中长度最小的部分树称为分树称为最小部分树最小部分树，或简称为，或简称为最小树最小树。 最小部分树可以直接用作图的方法求解，常用的有破最小部分树可以直接用作图的方法求解，常用的有破圈法和加边法。圈法和加边法。破圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。：任取一圈，去掉圈中最长边，直到无圈。11.2 最小树问题最小树问题 Minimal tree problem8/1/20225
12、v1v2v3v4v5v6843752618图图111【例【例11.1】用破圈法求图】用破圈法求图111的最小树。的最小树。 图图114图图114就是图就是图111的最小部分树，最小树长为的最小部分树，最小树长为 C(T)=4+3+5+2+1=15。当一个圈中有多个相同的最长边时，不能同时都去掉，只能去当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同度相同 11.2 最小树问题最小树问题 Minimal tree problem8/1/2022加边法加边法：取图：取图G的的n个
13、孤立点个孤立点v1，v2， vn作为一个支撑作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有图，从最短边开始往支撑图中添加，见圈回避，直到连通（有n1条边）条边） v1v2v3v4v5v643521图图115在图在图115中，如果添加边中，如果添加边v1, v2就形成圈就形成圈v1, v2, v4，这时就，这时就应避开添加边应避开添加边v1, v2，添加下一条最短边，添加下一条最短边v3, v6。破圈法和加边。破圈法和加边法得到树的形状可能不一样，但最小树的长度相等法得到树的形状可能不一样，但最小树的长度相等 5v1v3v515v2v4v684375268Min C(T)=1
14、511.2 最小树问题最小树问题 Minimal tree problem8/1/2022下一节：最短路问题下一节：最短路问题1.树、支撑树、最小支撑树的概念树、支撑树、最小支撑树的概念2.掌握求最小树的方法：掌握求最小树的方法： （1）破圈法）破圈法 （2）加边法）加边法11.2 最小树问题最小树问题 Minimal tree problem8/1/202211.3 最短路问题最短路问题 Shortest Path Problem8/1/2022最短路问题在实际中具有广泛的应用，如管道铺设、线路选择最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等问题，还有些如设备更新、投资等问题也可
15、以归结为求最短等问题，还有些如设备更新、投资等问题也可以归结为求最短路问题路问题 求最短路有两种算法：求最短路有两种算法： 一是求从某一点至其它各点之间最短离的一是求从某一点至其它各点之间最短离的狄克斯屈拉狄克斯屈拉(Dijkstra)算法算法 另一种是求网络图上任意两点之间最短路的另一种是求网络图上任意两点之间最短路的Floyd(弗洛伊德弗洛伊德)矩阵算法。矩阵算法。最短路问题，就是从给定的网络图中找出一点到各点或任意两最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路点之间距离最短的一条路 11.3.1最短路问题的网络模型最短路问题的网络模型11.3 最短路问题最
16、短路问题 Shortest Path Problem 8/1/2022610123214675811165图图1169【例【例11.2】图】图116中的权中的权cij表示表示vi到到vj的距离（费用、时间），的距离（费用、时间），从从v1修一条公路或架设一条高压线到修一条公路或架设一条高压线到v7，如何选择一条路线使距，如何选择一条路线使距离最短，建立该问题的网络数学模型。离最短，建立该问题的网络数学模型。11.3 最短路问题最短路问题 Shortest Path Problem 8/1/202211.3.2有向图的狄克斯屈拉有向图的狄克斯屈拉(Dijkstra)标号算法标号算法点标号：点标号
17、：b(j) 起点起点vs到点到点vj的最短路长；的最短路长；边标号：边标号：k(i，j)=b(i)+cij，步骤：步骤：(1)令起点的标号；令起点的标号；b(s)0。先求有向图的最短路，设网络图的起点是先求有向图的最短路，设网络图的起点是vs ,终点是终点是vt ,以以vi为起为起点点vj为终点的弧记为（为终点的弧记为（i，j）,距离为距离为cij (2)找出所有找出所有vi已标号已标号vj未标号的弧集合未标号的弧集合 B=(i，j)，如果这样，如果这样的弧不存在或的弧不存在或vt已标号则计算结束；已标号则计算结束；(3)计算集合计算集合B中弧中弧k(i，j)=b(i)+cij的标号的标号(4
18、)选一个点标号选一个点标号 返回到第返回到第(2)步。步。)(,),( | ),(min)(lbvBjijiklblj处标号在终点11.3 最短路问题最短路问题 Shortest Path Problem 8/1/2022610123214675811165图图11690610129209186161217162432182929【例【例11.3】用】用Dijkstra算法求图算法求图116 所示所示v1到到v7的最短路及最短路长的最短路及最短路长 v1 到到v7的最短路为：的最短路为：p17=v1, v2, v3, v5, v7，最短路长为，最短路长为L17=29 11.3 最短路问题最短路
19、问题 Shortest Path Problem 14S=T= min0+c12, 0+c13, 0+c14S= T= min 0+c13, 0+c14, 6+c23, 6+c25S= T= min 0+c14, 6+c25, 9+c35, 9+c36,9+c34 8/1/2022从上例知，只要某点已标号，说明已找到起点从上例知，只要某点已标号，说明已找到起点vs到该点的最短路到该点的最短路线及最短距离，因此可以将每个点标号，求出线及最短距离，因此可以将每个点标号，求出vs到任意点的最短到任意点的最短路线，如果某个点路线，如果某个点vj不能标号，说明不能标号，说明vs不可达不可达vj 。11.
20、3.3 无向图最短路的求法无向图最短路的求法无向图最短路的求法只将上述步骤（无向图最短路的求法只将上述步骤（2）改动一下即可。）改动一下即可。点标号：点标号：b(i) 起点起点vs到点到点vj的最短路长；的最短路长；边标号：边标号：k(i，j)=b(i)+cij，步骤：步骤：(1)令起点的标号；令起点的标号；b(s)0。(3)计算集合计算集合B中边标号：中边标号：ki，j=b(i)+cij)(, | ,min)(lbvBjijiklblj处标号在端点(4)选一个点标号选一个点标号: 返回到第返回到第(2)步。步。 (2)找出所有一端找出所有一端vi已标号另一端已标号另一端vj未标号的边集合未标
21、号的边集合 B=i，j如如果这样的边不存在或果这样的边不存在或vt已标号则计算结束；已标号则计算结束；11.3 最短路问题最短路问题 Shortest Path Problem 8/1/2022【例【例11.4】求图】求图11-10所示所示v1到各点的最短路及最短距离到各点的最短路及最短距离4526178393261216180452231039612641166188122482418所有点都已标号，所有点都已标号，点上的标号就是点上的标号就是v1到该点的最短距离到该点的最短距离，最短路，最短路线就是红色的链。线就是红色的链。图图11-1011.3 最短路问题最短路问题 Shortest P
22、ath Problem 8/1/2022下一节：最大流问题下一节：最大流问题11.3 最短路问题最短路问题 Shortest Path Problem 1.最短路的概念及应用。最短路的概念及应用。2.有向图、无向图一点到各点最短路的有向图、无向图一点到各点最短路的Dijkstra算法算法8/1/202211.4 最大流问题最大流问题Maximal Flow Problem8/1/202211.4 最大流问题最大流问题Maximal Flow Problem11.4.1 基本概念基本概念8145633810763图图11184图图1118所示的网络图中定义了一个所示的网络图中定义了一个发点发点v
23、1，称为源，称为源(source，supply node），定义了一个），定义了一个收点收点v7，称为汇（，称为汇（sink，demand node），其余），其余点点v2，v3，v6为为中间点中间点，称为，称为转运点转运点(transshipment nodes)。如果。如果有多个发点和收点，则虚设发点和收点转化成一个发点和收点。图中有多个发点和收点，则虚设发点和收点转化成一个发点和收点。图中的权是该弧在单位时间内的最大通过能力，称为弧的的权是该弧在单位时间内的最大通过能力，称为弧的容量容量(capacity)。最大流问题是在单位时间内安排一个运送方案，将发点的物质沿着弧最大流问题是在单位时
24、间内安排一个运送方案，将发点的物质沿着弧的方向运送到收点，使总运输量最大。的方向运送到收点，使总运输量最大。 8/1/2022设设cij为弧（为弧（i，j）的容量，）的容量，fij为弧（为弧（i，j）的流量。）的流量。容量是弧（容量是弧（i，j）单位时间内的）单位时间内的最大通过能力最大通过能力，流量是弧（，流量是弧（i，j）单位时间内的单位时间内的实际通过量实际通过量，流量的集合，流量的集合f=fij称为网络的流。发点称为网络的流。发点到收点的总流量记为到收点的总流量记为v=val(f)，v也是网络的也是网络的流量流量。 图图1118最大流问题的线性规划数学模型为最大流问题的线性规划数学模型
25、为1),(000max67475713121312jicfvfffffffffvijijmvmjvimmm所有弧所有中间点11.4 最大流问题最大流问题Maximal Flow Problem8/1/2022满足下例满足下例3个条件的流个条件的流fij 的集合的集合 f = fij 称为可行流称为可行流 1) 0( , )ijijfci j（所有弧(3)stsjitvvvff发点发点vs流出的总流量等于流入收点流出的总流量等于流入收点vt的总流量的总流量(2) mmimmjmvvffv所有中间点11.4 最大流问题最大流问题Maximal Flow Problem8/1/2022链：链：从发点
26、到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的方向规定为链的方向。从发点到收点的方向规定为链的方向。前向弧：前向弧：与链的方向相同的弧称为前向弧。与链的方向相同的弧称为前向弧。后向弧：后向弧：与链的方向相反的弧称为后向弧。与链的方向相反的弧称为后向弧。增广链增广链: 设设 f 是一个可行流，如果存在一条从是一个可行流，如果存在一条从vs到到vt的链，满足：的链，满足：1.所有前向弧上所有前向弧上fij0则该链称为增广链则该链称为增广链前向弧前向弧后向弧后向弧容量容量流量流量这是一条增这是一条增广链广链84469（5）(2)(
27、3)(4)(6)11.4 最大流问题最大流问题Maximal Flow Problem8/1/2022步骤如下：步骤如下：第二步：对点进行标号找一条增广链。第二步：对点进行标号找一条增广链。（1）发点标号）发点标号（）（2）选一个点）选一个点 vi 已标号并且另一端未标号的弧沿着某条链向收已标号并且另一端未标号的弧沿着某条链向收点检查：点检查： A如果弧的方向向前（前向弧）并且有如果弧的方向向前（前向弧）并且有fij0，则，则vj标号标号: jfji当当收点收点已得到标号时，说明已找到增广链，依据已得到标号时，说明已找到增广链，依据vi 的标号反向跟的标号反向跟踪得到一条增广链。当收点不能得到
28、标号时，说明不存在增广踪得到一条增广链。当收点不能得到标号时，说明不存在增广链，计算结束。链，计算结束。第一步：第一步： 找出第一个可行流，例如所有弧的流量找出第一个可行流，例如所有弧的流量fij =011.4.2 Ford-Fulkerson标号算法标号算法11.4 最大流问题最大流问题Maximal Flow Problem8/1/2022第三步：调整流量第三步：调整流量（1）求增广链上点）求增广链上点vi 的标号的最小值，得到调整量的标号的最小值，得到调整量 minjj（2）调整流量）调整流量),(),(),(1jifjifjiffijijij得到新的可行流得到新的可行流f1，去掉所有标
29、号，返回到第二步从发点重新，去掉所有标号，返回到第二步从发点重新标号寻找增广链，直到收点不能标号为止标号寻找增广链，直到收点不能标号为止 【定理【定理11.1】 可行流可行流f是最大流的充分必要条件是不存在发点到是最大流的充分必要条件是不存在发点到收点的增广链收点的增广链 11.4 最大流问题最大流问题Maximal Flow Problem8/1/20228145633810763图图1119(10)(6)(3)(6)(3)(7)(0)(6)(1)4(3)(1)(7)【例【例11.10】求图】求图1118发点发点v1到收点到收点v7的最大流及最大流量的最大流及最大流量【解】给定初始可行流，见
30、图【解】给定初始可行流，见图11-1911.4 最大流问题最大流问题Maximal Flow Problem8/1/20228145633810763图图1120(b)(10)(6)(3)(6)(3)(7)(0)(6)(1)4(3)(1)(7)2337第一轮标号：第一轮标号：c12f12,v2标号标号2cij=fij，v4、v5不能标号不能标号后向弧后向弧f320,v3标号标号3=f32增广链增广链(1,2)，(3,2)，(3,4)，(4,7) ,+=(1,2)，(3,4)，(4,7),=(3，2)，调整量为增广链上点标号的最小值，调整量为增广链上点标号的最小值min，2，3，3，7211.4
31、 最大流问题最大流问题Maximal Flow Problem8/1/20228145633810763图图1121(10)(8)(1)(6)(3)(7)(2)(6)(1)4(5)(1)(7)调整后的可行流：调整后的可行流：11.4最大流问题最大流问题Maximal Flow Problem8/1/20228145633810763图图1122(10)(8)(1)(6)(3)(7)(2)(6)(1)4(5)(1)(7)4415第二轮标号：第二轮标号：Cij=fij，v4、v5不能标号，返回到不能标号，返回到v3增广链增广链(1,3)，(3,4)，(4,7) ，调整量为，调整量为 min，4，1
32、，5111.4 最大流问题最大流问题Maximal Flow Problem8/1/20228145633810763图图1123(11)(8)(1)(6)(3)(7)(3)(6)(1)4(6)(1)(7)调整后得到可行流：调整后得到可行流：11.4 最大流问题最大流问题Maximal Flow Problem8/1/20228145633810763图图1122(11)(8)(1)(6)(3)(7)(3)(6)(1)4(6)(1)(7)314第三轮标号：第三轮标号：增广链增广链(1,3)，(3,6)，(6,4)，(4,7) ，调整量为，调整量为 min，3，1，2，41211.4 最大流问题
33、最大流问题Maximal Flow Problem8/1/20228145633810763图图1125(12)(8)(1)(6)(3)(8)(3)(6)(2)4(7)(1)(7)调整后得到可行流：调整后得到可行流：114 最大流问题最大流问题Maximal Flow Problem8/1/20228145633810763图图1122(12)(8)(1)(6)(3)(8)(3)(6)(2)4(7)(1)(7)2第四轮标号：第四轮标号：v7得不到标号，不存在得不到标号，不存在v1到到 v7的增广链，图的增广链，图6-22所示的可行流所示的可行流是最大流，最大流量为是最大流，最大流量为 vf12
34、+f138+12=20Cij=fij，v4、v5不能标号不能标号Cij=fij，v4、v6不能标号不能标号411.4 最大流问题最大流问题Maximal Flow Problem8/1/2022无向图最大流标号算法无向图最大流标号算法无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端vi已标号另一端已标号另一端vj未标号的边只要满足未标号的边只要满足 Cijfij0 则则vj就可标号就可标号（Cijfij）【例【例11.11】求下图】求下图v1到则到则v7标的最大流标的最大流71292085148691316(10)(6)(10)(8)
35、(2)(3)(7)(6)(5)(13)(0)(13)23993211.4 最大流问题最大流问题Maximal Flow Problem8/1/202271292085148691316(12)(6)(10)(8)(4)(3)(7)(6)(7)(13)(2)(15)3771171292085148691316(12)(7)(10)(8)(4)(3)(7)(6)(8)(13)(3)(16)V=291056611.4最大流问题最大流问题Maximal Flow Problem18/1/2022 【例【例11.12】某石油公司拥有一个管道网络，使用这个】某石油公司拥有一个管道网络，使用这个网络可以把石
36、油从采地运送到一些销售点，这个网络的网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段一部分如下图所示。由于管道的直径的变化，它的各段管道（管道（vi,vj）的流量）的流量cij（容量）也是不一样的。（容量）也是不一样的。cij的单的单位为万加仑位为万加仑/小时。如果使用这个网络系统从采地小时。如果使用这个网络系统从采地 v1向向销地销地 v7运送石油，问每小时能运送多少加仑石油？运送石油，问每小时能运送多少加仑石油？v563522241263v1v2v7v4v3v6图图11-26最大流另一解法最大流另一解法只给出最大流时只给出最大流时8/1/20
37、22最大流问题网络图论的解法最大流问题网络图论的解法 对网络上弧的容量的表示作改进。为省去弧的方向，如下图对网络上弧的容量的表示作改进。为省去弧的方向，如下图: (a)和和(b)、(c)和和(d)的意义相同。的意义相同。 用以上方法对例用以上方法对例11.12的图的容量标号作改进，得下图的图的容量标号作改进，得下图vivjvivjcij0（a）（b） cijcijvivj（cji）（c）vivj cij cji（d）63522241263v1v2v5v7v4v3v600000000000最大流另一解法最大流另一解法8/1/2022 求最大流的基本算法求最大流的基本算法（1）找出一条从发点到收点
38、的路，在这条路上的每一条弧顺流方向的容量都大）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。于零。如果不存在这样的路，则已经求得最大流。（2）找出这条路上各条弧的最小的顺流的容量）找出这条路上各条弧的最小的顺流的容量pf，通过这条路增加网络的流量，通过这条路增加网络的流量pf。（3）在这条路上，减少每一条弧的顺流容量）在这条路上，减少每一条弧的顺流容量pf ，同时增加这些弧的逆流容量，同时增加这些弧的逆流容量pf，返回步骤（返回步骤（1）。）。 用此方法对例用此方法对例11.12求解：求解： 第一次迭代：选择路为第一次迭代：选择路为
39、v1 v4 v7 。弧（。弧（ v4 , v7 ）的顺流容量为）的顺流容量为2，决定了决定了pf=2，改进的网络流量图如下图：，改进的网络流量图如下图：63522241263v1v2v5v7v4v3v6000000000004202最大流另一解法最大流另一解法8/1/2022 第二次迭代：选择路为第二次迭代：选择路为v1 v2 v5 v7 。弧（。弧（ v2 , v5 ）的顺流容量为）的顺流容量为3，决定了，决定了pf=3，改进的网络流量图如下图：，改进的网络流量图如下图： 第三次迭代：选择路为第三次迭代：选择路为v1 v4 v6 v7 。弧（。弧（ v4 , v6 ）的顺流容量为）的顺流容量
40、为1，决定了，决定了pf=1，改进的网络流量图如下图：，改进的网络流量图如下图：635222413v1v2v5v7v4v3v60000000042022033303222413v1v2v5v7v4v3v600000042022033333013最大流另一解法最大流另一解法8/1/2022 第四次迭代：选择路为第四次迭代：选择路为v1 v4 v3 v6 v7 。弧（。弧（ v3 , v6 ）的顺流容）的顺流容量为量为2，决定了，决定了pf=2，改进的网络流量图如下图：，改进的网络流量图如下图： 第五次迭代：选择路为第五次迭代：选择路为v1 v2 v3 v5 v7 。弧（。弧（ v2 , v3 ）
41、的顺流容）的顺流容量为量为2，决定了，决定了pf=2，改进的网络流量图如下图：，改进的网络流量图如下图：22243v1v2v5v7v4v3v6100001203203335031200231322v1v2v5v7v4v3v61012020333501202313150020205最大流另一解法最大流另一解法8/1/2022 经过第五次迭代后在图中已经找不到从发点到收点的一条路，路上的每经过第五次迭代后在图中已经找不到从发点到收点的一条路，路上的每一条弧顺流容量都大于零，运算停止。得到最大流量为一条弧顺流容量都大于零，运算停止。得到最大流量为10。 最大流量图如下图：最大流量图如下图：22v1v
42、2v5v7v4v3v6123522355 “管理运筹学软件管理运筹学软件”中还有专门的子程序用于解决最大流问题。中还有专门的子程序用于解决最大流问题。最大流另一解法最大流另一解法8/1/202211.4.4最大流应用举例最大流应用举例1.二分图的最大匹配问题二分图的最大匹配问题 【例【例11.13】某公司需要招聘】某公司需要招聘5个专业的毕业生各一个，通过本人个专业的毕业生各一个，通过本人报名和筛选，公司最后认为有报名和筛选，公司最后认为有6人都达到录取条件。这人都达到录取条件。这6人所学人所学专业见表专业见表11-10,表中打表中打“”表示该生所学专业。公司应招聘哪几表示该生所学专业。公司应
43、招聘哪几位毕业生，如何分配他们的工作位毕业生，如何分配他们的工作 毕业生毕业生A.市场营销市场营销B.工程管理工程管理C.管理信息管理信息D.计算机计算机E.企业管理企业管理123456表表11-1011.4 最大流问题最大流问题Maximal Flow Problem8/1/2022ABCDEst(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)图图1132【解】画出一个二分图，虚设一个发点和一收点，每条弧上的【解】画出一个二分图，虚设一个发点和一收点，每条弧上的容量等于容量等于1，问题为求发点到收点的最大流，求解结果之一见，问题为求发点到收点的最大流
44、，求解结果之一见图图1132。公司录取第。公司录取第26号毕业生，安排的工作依次为管理号毕业生，安排的工作依次为管理信息、企业管理、市场营销、工程管理和计算机。信息、企业管理、市场营销、工程管理和计算机。11.4 最大流问题最大流问题Maximal Flow Problem8/1/20221.最大流的概念：容量、流量、可行流、最大流、前向弧、后最大流的概念：容量、流量、可行流、最大流、前向弧、后向弧、增广链。向弧、增广链。2.有向图、无向图最大流的有向图、无向图最大流的Ford-Fulkerson标号算法标号算法3. 本节介绍了应用：最大匹配问题本节介绍了应用：最大匹配问题11.4最大流问题最
45、大流问题Maximal Flow Problem8/1/202211.5最小费用最大流问题最小费用最大流问题8/1/202211.6 中国邮路问题中国邮路问题 China Carrier Problem8/1/2022一、一笔画问题；11.1中国邮路问题中国邮路问题(China carrier problem) 8/1/2022欧拉链欧拉链：给定一个连通多重图，若存在一条链，过每边一次，且仅一次，称这条链为欧拉链。欧拉圈欧拉圈：若存在一个简单圈，过每边一次，称为欧拉图欧拉图：一个图若有欧拉圈，称显然，一个图若能一笔画出，则这个图必是欧拉图或含欧拉链。8/1/2022定理：连通多重图是欧拉图中无
46、奇点。推论：连通多重图有欧拉链恰 有两个奇点。二、奇偶点图上作业法8/1/2022例：v1v2v3v4v5v6v7v9556944424334v88/1/2022概念： 使新图中不含奇点而增加重复边，称为可行方案。 使总权最小的可行方案，称为最优方案。1.第一个可行方案的确定第一个可行方案的确定 使原图中不含有奇点而增加重复边 奇点的个数是偶数，图中有奇点必是成对出现 在两个奇点之间增加一条链8/1/2022消除奇点 调整 v1v2v3v4v6v7v8v9556944424334(a)v58/1/20222.最优方案判断的标准最优方案判断的标准 一个方案是最优的一个方案是最优的 在最优方案中，
47、图的每一边上最多有一条重复边； 在最优方案中，图中每个圈上的重复边的总权不大于该圈总权的一半；8/1/2022在(a)图中，圈(v2,v3,v4,v9,v2)中，圈总长24，但圈上重复边权之和1424的一半；见图调整如下图(b)所示。 8/1/2022调整 后的图v1v2v3v4v6v7v8v9556944424334(b)v58/1/2022 在图(b)中，圈(v1,v2,v9,v6,v7,v8,v1)中重复边权之和为13圈的权为24的一半； 调整为图( c)8/1/2022v1v2v3v4v5v6v7v9556944424334(c)v88/1/2022图( c)满足最优方案条件。图中任何一个欧拉圈就是邮递员的最优投递路线注：“日”字型图有三个圈 “田”字型图有13个圈。8/1/2022 作业作业第第，题（不用抄题）