《第九章网络优化模型PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第九章网络优化模型PPT讲稿.ppt（70页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第九章网络优化模型第九章网络优化模型第1页，共70页，编辑于2022年，星期二教学要求：教学要求：掌握图论基础，掌握最短路问题，最大流问题和最小费用流掌握图论基础，掌握最短路问题，最大流问题和最小费用流问题等网络优化模型及其基本算法。问题等网络优化模型及其基本算法。会应用模型和方法解决一些管理中的基本问题会应用模型和方法解决一些管理中的基本问题第2页，共70页，编辑于2022年，星期二p 目录目录p图与网络图与网络p树树p最短路问题最短路问题p最大流问题最大流问题p最小费用流问题最小费用流问题第一节第一节 图与网络图与网络第3页，共70页，编辑于2022年，星期二12341234一、图的概念及
2、分类图是由作为研究对象的有限个集合和表达这些顶点之间关系的m条线的集合组成的,记顶点集合为V=v1,v2,vn，线集合为L=l1,l2,.lm图则记为G=(V，L)，线又分为弧和边，顶点也称为结点 弧是由一对有序的顶点组成，表示两个顶点之间可能运动的方向取消弧的方向就变成了边，边是只要任两点之间有连线，两个方向均可使用，弧可作为城市道路的单行道，边则是双行道第一节第一节 图与网络图与网络第4页，共70页，编辑于2022年，星期二顶点、弧、有向图、无向图、链、道路、环、连通图、连通子图、顶点、弧、有向图、无向图、链、道路、环、连通图、连通子图、次的基本概念次的基本概念12341234123452
3、13次道路顶点无向图链有向图弧环连通图 弧是由一对有序的顶点组成，表示了两个顶点之间可能运动的方向 连通子图 由顶点集和弧 组成的图称为有有向图向图 由顶点集和边组成的图称为无向图无向图 链有一序列弧，如果每一个弧与前一个弧恰有一个公共顶点，则称这一序列弧为一个链。道路 如果链中每一个弧的终点是下面一个弧的起点，则这个链称为一个道路。环环 连接连接a a点与点与b b点的点的一条链，如果一条链，如果a a与与b b是是同一个点时，称此链同一个点时，称此链为环。为环。连通图连通图 一个图中一个图中任意两点间至少任意两点间至少有一个链相连，有一个链相连，则称此图为连通则称此图为连通图。图。任何一个
4、不连通图都可任何一个不连通图都可以分为若干个连通子图，以分为若干个连通子图，每一个子图称为原图的每一个子图称为原图的一个分图。一个分图。次次:以以a点为顶点为顶点的边的条数点的边的条数称为顶点的次称为顶点的次 第一节第一节 图与网络图与网络第5页，共70页，编辑于2022年，星期二l 点或边带有某种数量指标的图叫网络图网络图，简称网络网络。l 与点或边有关的某些数量指标，我们经常称之为权权，权可以代表如距离、费用、容量等。左图可以看作：左图可以看作：从发电厂（节点1）向某城市（节点6）输送电力，必须通过中转站（节点2，3，4，5）转送，边上数字代表两节点间的距离。电力公司希望选择合适的中转站，
5、使从电厂到城市的传输路线最短。一个输油管道网。节点1表示管道的起点，节点6表示管道的终点，节点2到5表示中转站，旁边的数字表示该段管道能通过的最大输送量。应怎样安排输油线路，使从节点1到节点6的总输送量最大？一张城市分布图。现在要在各城市之间架设电话线，应如何架设，使各城市之间既能通话，又使总的架设路线最短？二、网络二、网络第一节第一节 图与网络图与网络第6页，共70页，编辑于2022年，星期二一、树：连通且不含环的无向图一、树：连通且不含环的无向图 树的性质树的性质：任意两顶点之间必有一条且仅有一条链。去掉任一条边，则树成为不连通图。不相邻的两个顶点间添上一条边，恰好得到一个环。如果树有n个
6、结点，则边的数目刚好为n-1第二节第二节 树树第7页，共70页，编辑于2022年，星期二部分图生成子图部分树如果如果如果如果V1V1 V V，E1 E1 E E则称则称则称则称G1G1为为为为GG的部分图；的部分图；的部分图；的部分图；设设设设G=(VG=(V，E E)和和和和G1=(V1G1=(V1，E1E1)如果如果如果如果G1=(V1G1=(V1，E1E1)，G=(VG=(V，E E)，并且，并且，并且，并且V1V1 V V，,则称则称则称则称G1G1为为为为GG的生成子图；的生成子图；的生成子图；的生成子图；如果如果如果如果G=(VG=(V，E E)的部分的部分的部分的部分图图图图G1
7、=(VG1=(V，E1E1)是树是树是树是树，则称，则称，则称，则称G1G1为为为为GG的一个部分树。的一个部分树。的一个部分树。的一个部分树。二、部分图、生成子图、部分树二、部分图、生成子图、部分树第二节第二节 树树第8页，共70页，编辑于2022年，星期二求连通图部分树的方法(1)破圈法：在G中任取一个圈，去掉圈中的任何一条边，对余下的图重复这一步，直到无圈为止，最后得到一棵部分树第二节第二节 树树第9页，共70页，编辑于2022年，星期二求连通图部分树的方法(2)避圈法：在G中任取一条边e1，找一条与e1不构成圈的边e2，然后再找一条与e1,e2不构成圈的边e3、直到无边可选为止V1V3
8、V2V5V4V6e1e2e3e6e7e5e8e8e4第二节第二节 树树第10页，共70页，编辑于2022年，星期二1325464332322最小生成树不一定唯一最小生成树不一定唯一三、最小生成树：三、最小生成树：设有一连通图设有一连通图G=(V，L)，对于每一条边，对于每一条边e=(vi,vj),有一个权有一个权wij，一棵生成树所有树枝上权的总和，称为这个生成树的权，一棵生成树所有树枝上权的总和，称为这个生成树的权，具有最小权的生成树称为最小生成树，简称最小树具有最小权的生成树称为最小生成树，简称最小树第二节第二节 树树第11页，共70页，编辑于2022年，星期二(1)最小生成树的求法破圈法
9、:每一步任找一个圈，划去权值为最大的边，直到图中没圈为止，即得最小树V1V3V2V5V4V6651532447第二节第二节 树树第12页，共70页，编辑于2022年，星期二(2)最小生成树的求法避圈法:每一步从未选的边中，选一条权值最小的边，使已选出的边不构成圈直至不能进行为止，即得最小树V1V3V2V5V4V6651532447第二节第二节 树树第13页，共70页，编辑于2022年，星期二V1V4V2V5V7V864523854V3V64543637练习：用破圈法或避圈法求下图的最小生成树，并指出其权重和 第二节第二节 树树第14页，共70页，编辑于2022年，星期二避圈法：V1V4V2V5
10、V7V864523854V3V64543637最小生成树如上图红线所示，最小权重为：4+3+3+3+4+5+2=24第二节第二节 树树第15页，共70页，编辑于2022年，星期二破圈法：V1V4V2V5V7V864523854V3V64543637最小生成树如上图所示，最小权重为：4+3+3+3+4+5+2=24第二节第二节 树树第16页，共70页，编辑于2022年，星期二练习：下图是6个城市的交通图，为将部分道路改造成高速公路，使各个城市均能通达，又要使高速公路的总长度最小，应如何做使总长度最小,总长度是多少?第二节第二节 树树第17页，共70页，编辑于2022年，星期二避圈法求解：第二节第
11、二节 树树最优改造路线如上图红线所示，最短路径为：1400第18页，共70页，编辑于2022年，星期二求下面两个连通图的最小生成树：第二节第二节 树树第19页，共70页，编辑于2022年，星期二第二节第二节 树树第20页，共70页，编辑于2022年，星期二某地有10个村庄，它们之间的交通道路如下图所示，图中边旁权为道路长度(单位：百米)，现在要沿道架设电线，实现村村通电话工程，问应如何架设电线才能使总长度最短？第二节第二节 树树第21页，共70页，编辑于2022年，星期二解：本题实质是最小树问题，利用避圈法可求得最短路线，如下图粗线所示：最优架设路线如上图粗线所示，架设电线最短长度为18(百米
12、)。第二节第二节 树树第22页，共70页，编辑于2022年，星期二某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如图所示，图中vi表示7个学院办公室，图中的边为可能联网的途径，边上的所赋的权数为这条路线的长度，单位为百米，请设计一个网络能联系7个学院办公室，并使总的线路长度为最短V1V6V5104873V2V7335V4V3124第23页，共70页，编辑于2022年，星期二V1V6V5104873V2V7335V4V312破圈法求解：4最短路径如上图所示，最短为：19百米第24页，共70页，编辑于2022年，星期二V1V6V5104873V2V7335V4V312避圈法
13、求解：最短路径如上图所示，最短为：19百米4第25页，共70页，编辑于2022年，星期二p图与网络图与网络p树树p最短路问题最短路问题p最大流问题最大流问题p最小费用流问题最小费用流问题第三节第三节 最短路问题最短路问题第26页，共70页，编辑于2022年，星期二特点：从一特殊的节点出发，找出从该节点到网络中任何其它节点的最短路径问题某人买了一辆价值1200美元的新车，一辆车每年的维护费用依赖于年初时的车龄，具体费用见下表。为了避免旧车的高维护费用，他决定卖掉旧车买新车。旧车的价格依赖于交易时的车龄，见下表。为计算简单起见，假设任何时间新车的价格不变均为1200美元。他希望在今后5年内的净费用
14、最小（即：净费用=购买价+维护价-售出价）。车龄每年的维护费用交易费用012345200040005000900012000700060002000100002112第三节第三节 最短路问题最短路问题第27页，共70页，编辑于2022年，星期二结点i表示第i年的年初，当ij时，弧(i,j)表示第i年年初购买一辆新车并一直用到第j年年初。弧的长度cij表示：如果第i年年初购买一辆新车并这辆车在第j年年初卖掉更换一辆新新，从第i年年初到第j年年初期间总的净费用，于是有cij=(i,i+1,.j-1年的维护费用）（第i年年初购买新车的费用）（第j 年年初该车的交易费用）123456777771212
15、1221313144122121第三节第三节 最短路问题最短路问题第28页，共70页，编辑于2022年，星期二车龄每年的维护费用交易费用01234520004000500090001200070006000200010000c12=2+12-7=7 c13=2+4+12-6=12c14=2+4+5+12-2=21c15=2+4+5+9+12-1=31c16=2+4+5+9+12+12-0=44c23=2+12-7=7 c24=2+4+12-6=12c25=2+4+5+12-2=21c26=2+4+5+9+12-1=31c34=2+12-7=7 c35=2+4+12-6=12c36=3+4+5+
16、12-2=21c45=2+12-7=7 c46=2+4+12-6=12c56=2+12-7=71234567777712121221313144122121第三节第三节 最短路问题最短路问题第29页，共70页，编辑于2022年，星期二Dijkstra最短路算法：假设每个弧的权是非负的，即wij0，给每个支点vi记一个数(称标号)，标号分临时性标号T和永久性标号P，永久性标号表示从v1到该点vi的最短路权，得到永久性标号的不再改变标号，临时性标号表示从开始点v1到该点vi的最短路权的上界，算法每一步都把某一点的T标号改为P标号，开始时给初始支点v1标号记为0，即P(v1)=0，其他支点(记为临时
17、性标号)的标号记为+，即T(vi)=+,若vi点是刚得到P标号的点，考虑L中与vi点相连的弧(vi,vj)且vj 是T标号，对vj的标号进行如下更改：T(vj)=minT(vj),P(vi)+Wij比较所有具有T标号的点，把最小者改为P标号，当存在两个以上最小者时，可以同时改为P标号，直到全部点均改为P标号为止第三节第三节 最短路问题最短路问题第30页，共70页，编辑于2022年，星期二 例：从发电厂（记为节点1）向某城市（记为节点6）输送电，必须通过中转站（记为节点2，3，4，5）转送。图给出了两节点间的距离。电力公司希望选择合适的中转站，使从电厂到城市的传输路线最短。即从节点1到节点6的最
18、短路径。这就是一个最短路问题。第三节第三节 最短路问题最短路问题第31页，共70页，编辑于2022年，星期二1325464332322 第0步：P(1)=0,T(i)=+；第1步：与1相连的标号为2,3，均是T标号，修改2,3的标号，T(2)=minT(2),P(1)+w12=4,T(3)=3；在所有的T标号中，3的标号最小，改3的标号为P(3)=3；第2步：修改与3相连的T标号；在所有剩下的T标号中，2的标号最小，改为P(2)=4；第3步：修改与2相连的T标号；在所有剩下的T标号中，5的标号最小，改为P(5)=6；第4步：修改与5相连的T标号；在所有剩下的T标号中，4的标号最小，改为P(4)
19、=7；第5步：修改与4相连的T标号；只剩下节点6是T标号，修改6的标号，P(6)=8。从节点6开始回退，得到最短路。P(1)=0T(3)=+T(2)=+T(3)=3T(5)=+P(3)=3T(5)=6T(2)=4T(4)=+T(6)=+P(2)=4T(4)=7P(5)=6T(6)=8P(4)=7P(6)=8P(6)=8P(5)=6P(3)=3P(1)=0第三节第三节 最短路问题最短路问题第32页，共70页，编辑于2022年，星期二P(1)=0T(2)=+T(4)=+T(3)=+T(5)=+T(6)=+T(7)=+第2步：与4相连的标号为2,3,5,6，均是T标号，修改2,3,5,6的标号，T(
20、2)=minT(2),P(4)+w42=4,T(3)=minT(3),P(4)+w43=3T(5)=minT(5),P(4)+w45=7T(6)=minT(6),P(4)+w46=9在所有的T标号中，3的标号最小，改3的标号为P(3)=3；T(2)=4T(3)=3T(4)=2P(4)=2 第1步：与1相连的标号为2,3，4，均是T标号，修改2,3,4的标号，T(2)=minT(2),P(1)+w12=4,T(3)=minT(3),P(1)+w13=3T(4)=minT(4),P(1)+w14=2在所有的T标号中，4的标号最小，改4的标号为P(4)=2；T(2)=4T(3)=3T(5)=7T(6
21、)=9 第3步：与3相连的是T标号,为5，修改5的标号，T(5)=minT(5),P(3)+w35=6在所有的T标号中，2的标号最小，改2的标号为P(2)=4；P(3)=3T(5)=6 第4步：与2相连的是T标号,为6，修改6的标号，T(6)=minT(6),P(4)+w46=9在所有的T标号中，5的标号最小，改5的标号为P(5)=6；P(2)=4P(5)=6 第5步：与5相连的是T标号,为6,7，修改6,7的标号，T(6)=minT(6),P(5)+w56=8T(7)=minT(7),P(5)+w56=12在所有的T标号中，6的标号最小，改6的标号为P(6)=8；13254643523267
22、22572T(6)=8T(7)=12 第6步：与6相连的是T标号,为7，修改7的标号，T(7)=minT(7),P(6)+w67=10在所有的T标号中，7的标号最小，改7的标号为P(7)=10；P(6)=8T(7)=10P(7)=10最短路径为P(7)-P(6)-P(5)-P(3)-P(1)最短路长度为10；T(6)=9求1到7的最短路第三节第三节 最短路问题最短路问题第33页，共70页，编辑于2022年，星期二1325465462352572求1到6的最短路最短路径为1356长度为9第三节第三节 最短路问题最短路问题第34页，共70页，编辑于2022年，星期二用用ExcelExcel求解最短
23、路算法求解最短路算法 净流量净流量=流出该节点的流量流出该节点的流量 流入该节点的流量流入该节点的流量 中间节点的平衡值为中间节点的平衡值为0 0，起点为，起点为1 1，终点为，终点为-1-1。各个点的净流量等于平衡值。各个点的净流量等于平衡值 最短路平衡流最短路平衡流第三节第三节 最短路问题最短路问题第35页，共70页，编辑于2022年，星期二P(6)=8P(5)=6P(3)=3P(1)=0第三节第三节 最短路问题最短路问题第36页，共70页，编辑于2022年，星期二 城市出租车公司在纽约市为出租车司机已经确定了城市出租车公司在纽约市为出租车司机已经确定了1010个搭乘车站。为个搭乘车站。为
24、了减少运行时间，提高服务质量以及最大化利用公司的车队，管理方了减少运行时间，提高服务质量以及最大化利用公司的车队，管理方希望出租车司机尽可能地选择最短路线。使用下面公路与街道的网络希望出租车司机尽可能地选择最短路线。使用下面公路与街道的网络图，请说明司机从车站图，请说明司机从车站1 1到车站到车站1010应选择什么样的路线。运行时间如图应选择什么样的路线。运行时间如图所示。所示。第三节第三节 最短路问题最短路问题第37页，共70页，编辑于2022年，星期二 这里我们仅通过Excel电子表格求解，在表格中，我们并不是把每一对连接的点都输入进去，比如，我们输入了从V7到V10，很明显不需要再输入从
25、V7到V8，从V8到V10这两对点对，因为他们加起来的距离明显要比前者长。第三节第三节 最短路问题最短路问题第38页，共70页，编辑于2022年，星期二最优路线为：最优路线为：1 11010，最短距离是，最短距离是25 25 第三节第三节 最短路问题最短路问题第39页，共70页，编辑于2022年，星期二p图与网络图与网络p树树p最短路问题最短路问题p最大流问题最大流问题p最小费用流问题最小费用流问题第四节第四节 最大流问题最大流问题第40页，共70页，编辑于2022年，星期二最大流量问题：给了一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出发点到收点的最大流量第
26、四节第四节 最大流问题最大流问题第41页，共70页，编辑于2022年，星期二V1V4V2V5V76634252V3V62321例：某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如图所示，由于管理的直径的变化，它的各段管道(vi,vj)的流量（容量）cij也是不一样的，cij的单位为万加仑/小时，如果使用这个网络系统从采地v1向销地v7运送石油，问每小时能运行多少加仑石油？第四节第四节 最大流问题最大流问题第42页，共70页，编辑于2022年，星期二设弧(vi,vj)上流量为fij，网络上总的流量为F，则有目标函数：max F=f12+f14约束条件：
27、f12=f23+f14f14=f43+f46+f47f23+f43=f35+f36f25+f35=f57f36+f46=f67f57+f67+f47=f12+f14fij cijfij0i=1,2,6 j=2,3,7守恒条件小于容量的可行流可行流中一组流量最大的称为最大流第四节第四节 最大流问题最大流问题第43页，共70页，编辑于2022年，星期二最大流问题网络图论的解法1、对网络上弧的容量的表示作改进，对条一条弧(vi,vj)的容量用一对数据cij,0标在弧(vi,vj)上，以cij靠近vi点，0靠近vj点，表示从vi到vj容许通过的容量为cij，而从vj到vi容许通过的容量为0，这样可能省
28、云弧的方向vivjcijvivjcijc0对于存在两条相反的弧(vi,vj)和(vj,vi)，也可以用一条过和一对数组cij，cji来表示它们的容量vivjcijvivjcijcji第四节第四节 最大流问题最大流问题第44页，共70页，编辑于2022年，星期二V1V4V2V5V76634252V3V6232100000000000第四节第四节 最大流问题最大流问题第45页，共70页，编辑于2022年，星期二求最大流的基本算法（1）找出一条从发点到收点的路，在这条路上的每条弧顺流方向的容量都大于零，如果不存在这样的路，则已求得最大流（2）找出这条路上各条弧的最小的顺流的容量pf，通过这条路增加网
29、络的流量pf(3)在这条路上，减少每条弧的顺流容量pf，同时增加这些弧的逆流容量pf,返回步骤（1）由于所选路不一样，计算过程也不一样，但最终结果是一样的，为了使算法快捷有效，我们一般在步骤（1）中尽量选择包含弧数最少的路第四节第四节 最大流问题最大流问题第46页，共70页，编辑于2022年，星期二第一次迭代选择路为v1-v4-v7，弧（v4,v7)的顺流容量为2，决定pf=2，改进网络流量V1V4V2V5V76634252V3V62321000000000000422F=2第四节第四节 最大流问题最大流问题第47页，共70页，编辑于2022年，星期二第二次迭代选择路为v1-v2-v5v7，弧
30、（v2,v5)的顺流容量c35=3，决定pf=3，改进网络流量V1V4V2V5V763452V3V623210000000000422F=5032333第四节第四节 最大流问题最大流问题第48页，共70页，编辑于2022年，星期二第三次迭代选择路为v1-v4-v6v7，弧（v4,v6)的顺流容量c46=1，决定pf=1，改进网络流量V1V4V2V5V742V3V623210000000422F=6032333303113第四节第四节 最大流问题最大流问题第49页，共70页，编辑于2022年，星期二第四次迭代选择路为v1-v4-v3v6 v7，弧（v3,v6)的顺流容量c36=2，决定pf=2，
31、改进网络流量V1V4V2V5V72V3V6232000002F=803233330311311015223第四节第四节 最大流问题最大流问题第50页，共70页，编辑于2022年，星期二第五次迭代选择路为v1-v2-v3v5 v7，弧（v2,v3)的顺流容量c23=2，决定pf=2，改进网络流量V1V4V2V5V72V3V620002F=10032333011101522310005225第四节第四节 最大流问题最大流问题第51页，共70页，编辑于2022年，星期二V1V4V2V5V7V3V602F=1003011101522310005225网络图中，逆流就是流过每条路径的流量第四节第四节 最
32、大流问题最大流问题第52页，共70页，编辑于2022年，星期二24531142010519152730流流 量量容量 容量网络：容量网络：标有弧容量的网络。网络流的两个条件：网络流的两个条件：每个弧的流量不能超过该弧的最大通过能力，即容容量；量；中间支点的流量为零。可行流：可行流：中间点的流量为零。而发点和收点的流量必须相等。156104610150可行流可行流第四节第四节 最大流问题最大流问题第53页，共70页，编辑于2022年，星期二增广链增广链13425201051419152730156104610150饱和弧非饱和弧零弧增广链增广链增广链增广链:设设f f是一个可行流，是一个可行流，
33、C C 是从发点是从发点VsVs到收点到收点VtVt的一条链，若的一条链，若C C 满足以满足以 下条件，则称下条件，则称C C 为一条增广链：为一条增广链：(1)(1)在弧在弧(v(vi i,v,vj j)C+上，上，0 0fijcij，即，即C C+(弧的方向与链的方向一致弧的方向与链的方向一致)中每一条弧是非饱和弧中每一条弧是非饱和弧(2)(2)在弧在弧 (vi,vj)C+上，上，0fijcij ，即，即C C-(弧的方向与链的方向相反弧的方向与链的方向相反)中每一条弧是非零流弧中每一条弧是非零流弧 C中每一条弧是非饱和弧中每一条弧是非饱和弧;C中每一条弧是非零流弧。中每一条弧是非零流弧
34、。第四节第四节 最大流问题最大流问题第54页，共70页，编辑于2022年，星期二21st28811 任给一个包含收点但不包含发点的支点集V*，则称i(弧起点)不属于V*，j(弧终点)属于V*的弧(i,j)的全体为割集。割集的容量是割集中所有弧的容量的总和。如果将割集从网络中移去，则就不可能有从起点到终点的路径。一个网络可能有许多割集。任何从发点到收点的可行流小于等于任何割集的容量。V*割集割集任何割集的容量是从起点到终点的最大流的上界。如果能找到一个可行流和一个割集使得割集从起点到终点的容量等于可行流的流量，则该可行流就是 一个最大流。最大流-最小割定理 V*=1,t割集是割集是(s s,1)
35、,1)，(2,(2,t t)支点集支点集V V*=1,2,*=1,2,t t,割集？割集？(s,1)，(s,2)第四节第四节 最大流问题最大流问题第55页，共70页，编辑于2022年，星期二求最大流的标号算法求最大流的标号算法 从一个可行流从一个可行流f=ff=fij ij 出发，（若网络中没有给定出发，（若网络中没有给定f f，则可以设，则可以设f f是零流）需要经过标号是零流）需要经过标号过程与调整过程。过程与调整过程。1 1标号过程标号过程 在这个过程中，网络中的点或是标号点或是未标号点。每个标号点的标号包含两部分：在这个过程中，网络中的点或是标号点或是未标号点。每个标号点的标号包含两部
36、分：第一标号表示它的标号是从哪一点得到的，以便找出增广链；第二个标号是为确定第一标号表示它的标号是从哪一点得到的，以便找出增广链；第二个标号是为确定增广链的调整量用的。增广链的调整量用的。标号过程开始时，总是先给发点标号过程开始时，总是先给发点VsVs标上标上(0,+(0,+)。其余各点标号的规则是：。其余各点标号的规则是：设设v vi i 是是已标号的点，检查与已标号的点，检查与VjVj点关联的另一顶点未标号的弧：点关联的另一顶点未标号的弧：（1 1）如果在弧）如果在弧(v(vi i,v,vj j)上（即前向弧），上（即前向弧），f fij ijc00，则给，则给vjvj标号标号(-v(-v
37、i i,l(v,l(vj j)，其中，其中l(vl(vj j)=minl(v)=minl(vi i),f),fji ji，负号说明经后向弧到，负号说明经后向弧到 。如果。如果f fij ij=0=0，则，则 v vi i不标号。不标号。重复上述步骤，直到被重复上述步骤，直到被v vj j 标上号，表明得到一条从标上号，表明得到一条从v vi i 到到v vj j的增广链的增广链C C，转入调整过程。，转入调整过程。第四节第四节 最大流问题最大流问题第56页，共70页，编辑于2022年，星期二求最大流的标号算法求最大流的标号算法 2 2调整过程调整过程 由收点由收点 标号算出的标号算出的 作为调
38、整量（即作为调整量（即 ）。对增广链各弧的调整）。对增广链各弧的调整如下：如下：增广链以外各弧流量不变。去掉所有标号，对新的可行流增广链以外各弧流量不变。去掉所有标号，对新的可行流 ，重新进入标号过程。直到标号过程中断。当前流就是最大流。，重新进入标号过程。直到标号过程中断。当前流就是最大流。第四节第四节 最大流问题最大流问题第57页，共70页，编辑于2022年，星期二vsv2v1v3vt32223(0,+)找到初始可行流。找到初始可行流。给网络中的各个点标号：给网络中的各个点标号：总是先给发点总是先给发点v vs s标上标上(0,+)(0,+)。其余各点标号的规则是：设其余各点标号的规则是：
39、设v vi i是已标号的点，检查是已标号的点，检查与点与点v vi i关联的另一顶点未标号的弧：关联的另一顶点未标号的弧：（1 1）如果在弧）如果在弧(v(vi i,v,vj j)上（即前向弧），上（即前向弧），f fij ijc00，则给，则给v vj j标号标号(-v(-vi i,l(v,l(vj j)，其中，其中l(vl(vj j)=minl(v)=minl(vi i),f),fji ji，负号说明，负号说明经后向弧到经后向弧到v vi i。如果。如果f fji ji=0=0，则，则v vj j不标号。不标号。调整：调整：按照第一标号找到增广链，按照第一标号找到增广链，按第二标号的最小值
40、调整可行流，得到新的可行按第二标号的最小值调整可行流，得到新的可行流。流。重复标号过程，直到没有增广链，即得到最大流。重复标号过程，直到没有增广链，即得到最大流。2112114(vs,2)(v3,1)(-v2,1)(v1,1)222022如下图所示，弧上数字表示该弧的容量，如下图所示，弧上数字表示该弧的容量，求该网络的最大流。求该网络的最大流。增广链以外各弧流量不变增广链以外各弧流量不变 第四节第四节 最大流问题最大流问题第58页，共70页，编辑于2022年，星期二vsv2v1v3vt32223(0,+)重复标号过程重复标号过程。给网络中的各个点标号：给网络中的各个点标号：先给发点先给发点v
41、vs s标上标上(0,+)(0,+)。检查检查vsvs给给v v2 2标上标上(v(vs s,1),1)，检查，检查v v2 2,在弧在弧(v(v2 2,v,vt t)上上,f,f2t2t=c=c2t2t=2,=2,不满足不满足标号条件，在弧标号条件，在弧(v(v1 1,v,v2 2)上，上，f f1212=0,=0,也不满足标号条件，标号也不满足标号条件，标号无法继续。算法结束。无法继续。算法结束。4(vs,1)222022如下图所示，弧上数字表示该弧的容量，如下图所示，弧上数字表示该弧的容量，求该网络的最大流。求该网络的最大流。最大流量为从发点流出的量最大流量为从发点流出的量 这时的可行流
42、就是所求的最大流这时的可行流就是所求的最大流 第四节第四节 最大流问题最大流问题第59页，共70页，编辑于2022年，星期二第四节第四节 最大流问题最大流问题第60页，共70页，编辑于2022年，星期二从一个费用最小的可行流 f=fij 出发（这样的可行流一定存在，因为费用bij0，所以f=0 就是一个流量为0的最小费用流），找出这个可行流f 的费用最小的一条增广链L，沿L调整f，直到找不到费用最小的增广链，就得到了最小费用最大流。对于网络图G中的弧，除标明弧的容量cij外，还要标明流过该弧单位流量的费用bij，G的一个可行流f=fij，使得流的总运输费用：达到最小。特别，如果可行流是最大流时
43、，此问题就是最小费用最大流问题。最小费用流问题最小费用最大流的基本思路第五节第五节 最小费用流问题最小费用流问题第61页，共70页，编辑于2022年，星期二用用ExcelExcel求解最大流和最小费用最大流问题求解最大流和最小费用最大流问题 用用ExcelExcel求解例求解例9.59.5 第五节第五节 最小费用流问题最小费用流问题第62页，共70页，编辑于2022年，星期二最小费用最大流问题的最小费用最大流问题的ExcelExcel电子表格求解电子表格求解 用用ExcelExcel求解例求解例9.69.6 第五节第五节 最小费用流问题最小费用流问题第63页，共70页，编辑于2022年，星期二
44、第五节第五节 最小费用流问题最小费用流问题第64页，共70页，编辑于2022年，星期二例1，一个邮递员应选择怎样的送信路线，使得他走完所负责的全部街道后，回到邮局，所走的路程最短（不重复或少重复）13274568910中国邮递员问题中国邮递员问题第65页，共70页，编辑于2022年，星期二例2“七桥问题”哥尼斯堡（现叫加里宁格勒）有一条河，河中有二个岛，河上有七座桥，数学家欧拉证明了从一点出发，经过每座桥一次且仅一次，再回到原出发点是办不到的。这就所谓的一笔画问题CD中国邮递员问题中国邮递员问题第66页，共70页，编辑于2022年，星期二一笔画问题（1）欧拉图：图中每个顶点的次均为偶数的图（2
45、）欧拉链：经过图中G的每一条边仅一次的链以下两种图可以一笔画出（1）每个顶点的次均为偶数的图，画时可以从任一点出发（2）有且仅有两个奇点的图，画时必须从其中一个奇点出发，在另一个奇点结束除以上两种情形，其图一律不能一笔画出中国邮递员问题中国邮递员问题第67页，共70页，编辑于2022年，星期二在例1中，由于每个顶点的次均为偶数，所以可以一笔画出，也即邮递员可以一次走完所有街道，最后回到邮局，可任选一个点为出发点。13274568910中国邮递员问题中国邮递员问题第68页，共70页，编辑于2022年，星期二可以把七桥问题看作为如下图的一笔画问题。由于d(A)=3,d(B)=3,d(C)=5,d(D)=3，即度为奇数的个数为4，所以不能一笔画出，也即不能一次走完七座桥。DCBA中国邮递员问题中国邮递员问题第69页，共70页，编辑于2022年，星期二试确定以下图能否一笔画出？第70页，共70页，编辑于2022年，星期二