管理运筹学第七章网络优化模型课件.ppt

《管理运筹学第七章网络优化模型课件.ppt》由会员分享，可在线阅读，更多相关《管理运筹学第七章网络优化模型课件.ppt（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、管理运筹学第七章网络管理运筹学第七章网络优化模型优化模型第1页，此课件共57页哦哥尼斯堡七桥问题哥尼斯堡七桥问题A AB BD D C C简捷表示事物之间的本简捷表示事物之间的本质联系，归纳事物之间质联系，归纳事物之间的一般规律的一般规律A AC CD DB B第2页，此课件共57页哦在一个人群中，对相互认识这个关系我们可以用图来表示。在一个人群中，对相互认识这个关系我们可以用图来表示。(v(v1 1)赵赵赵赵(v(v2 2)钱钱钱钱(v(v3 3)孙孙孙孙(v(v4 4)李李李李(v(v5 5)周周周周(v(v6 6)吴吴吴吴(v(v7 7)陈陈陈陈e e2 2e e1 1e e3 3e e

2、4 4e e5 57.1 图与网络的基本概念第3页，此课件共57页哦4 4 当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关

3、系并不是重要的，如对赵等七人的相互认识关系我对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以用下图来表示，可见图论中的图与几何图、工程图是不一样的。们也可以用下图来表示，可见图论中的图与几何图、工程图是不一样的。们也可以用下图来表示，可见图论中的图与几何图、工程图是不一样的。们也可以用下图来表示，可见图论中的图与几何图、工程图是不一样的。(v(v1 1)赵赵赵赵(v(v2 2)钱钱钱钱孙孙孙孙(v(v3 3)李李李李(v(v4 4)周周周周(v

4、(v5 5)吴吴吴吴(v(v6 6)陈陈陈陈(v(v7 7)e e2 2e e1 1e e3 3e e4 4e e5 5第4页，此课件共57页哦5 5a a1 1a a2 2a a3 3a a4 4a a1414a a7 7a a8 8a a9 9a a6 6a a5 5a a1010a a1212a a1111a a1313a a1515(v(v1 1)赵赵赵赵(v(v2 2)钱钱钱钱(v(v3 3)孙孙孙孙(v(v4 4)李李李李(v(v5 5)周周周周(v(v6 6)吴吴吴吴(v(v7 7)陈陈陈陈 如果我们把上面例子中的如果我们把上面例子中的如果我们把上面例子中的如果我们把上面例子中的

5、“相互认识相互认识相互认识相互认识”关系改为关系改为关系改为关系改为“认识认识认识认识”的关系，的关系，的关系，的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图一个带箭头的联线，称为弧。图一个带箭头的联线，称为弧。图一个带箭头的联线，称为弧。图11-311-3就是一个反映这七人就是一个反映这七人就是一个反映这七人就是一个反映这七人“认识认识认识认识”关系关系关系

6、关系的图。相互认识用两条反向的弧表示。的图。相互认识用两条反向的弧表示。的图。相互认识用两条反向的弧表示。的图。相互认识用两条反向的弧表示。第5页，此课件共57页哦7.1 图与网络的基本概念7.1.1 图与网络的概念及分类图与网络的概念及分类1、图：图由点和边组成、图：图由点和边组成 G=(V,E)点集点集V=vV=vi i 边集边集E=ei i vjvie每一条边和两个端点关联，一条边可以用两个端点表示每一条边和两个端点关联，一条边可以用两个端点表示（v vi i，v vj j j j）边数：边数：m(G)=|E|点数：点数：n(G)=|V|n(G)=|V|第6页，此课件共57页哦7.1 图

7、与网络的基本概念无向边：无向边：有向边：有向边：无向图：由无向边构成的图无向图：由无向边构成的图无向图：由无向边构成的图无向图：由无向边构成的图有向图：由有向边构成的图有向图：由有向边构成的图有向图：由有向边构成的图有向图：由有向边构成的图 2、无向图和有向图、无向图和有向图第7页，此课件共57页哦7.1 图与网络的基本概念3、简单图和多重图、简单图和多重图环：环：环：环：e e 9 多重边：多重边：多重边：多重边：e e 6 和和 e e 7 7简单图简单图：不含环和多重边：不含环和多重边多重图：含多重边多重图：含多重边第8页，此课件共57页哦判断下列哪些图是简单图，哪些图是多重图？判断下列

8、哪些图是简单图，哪些图是多重图？7.1 图与网络的基本概念第9页，此课件共57页哦7.1 图与网络的基本概念4 4、次：以点、次：以点v v为端点的边数叫做点为端点的边数叫做点v v的的次次，d(v)d(v)奇点：次为奇数奇点：次为奇数偶点：次为偶数偶点：次为偶数悬挂点：悬挂点：悬挂点：悬挂点：d(v)=1 d(v)=1 孤立点孤立点孤立点孤立点:d(v)=0:d(v)=0定理定理7.1：任何图，任何图，d(vi)=2 m定理定理7.2：任何图，奇点有偶数个任何图，奇点有偶数个第10页，此课件共57页哦7.1 图与网络的基本概念出次出次d+(vi)：有向图中，以：有向图中，以vi为始点的边数为

9、始点的边数入次入次d-(vi)：有向图中，以：有向图中，以vi为终点的边数为终点的边数d+(v)=d-(v)=m第11页，此课件共57页哦7.1 图与网络的基本概念5 5、链、圈、路、回路、连通图：、链、圈、路、回路、连通图：链：链：无向图无向图G=G=（V,EV,E）前后相继的点边序列称为前后相继的点边序列称为链链初等链：初等链：点边序列中点边序列中没有重复的点没有重复的点和和重复边重复边的链称为的链称为初等链初等链(v(v1 1,e,e1 1 1 1,v,v,v,v2 2,e,e,e,e6 6 6 6,v,v4 4,e,e,e,e3 3 3 3,v,v3 3 3 3,e,e,e,e8 8

10、8 8,v,v,v,v5 5 5 5)第12页，此课件共57页哦7.1 图与网络的基本概念圈：圈：无向无向图G=（V,E）中起点和终点重合的链称）中起点和终点重合的链称为为圈圈初等圈：初等圈：初等圈：初等圈：没有重复点没有重复点(除起点和终点外除起点和终点外除起点和终点外除起点和终点外)和重复边的圈称为和重复边的圈称为和重复边的圈称为和重复边的圈称为初等圈初等圈(v(v(v(v1 1,e,e1 1,v,v2 2 2 2,e,e,e,e6 6 6 6,v,v4 4,e,e3 3,v,v,v,v3 3 3 3,e,e5 5,v,v,v,v1 1 1 1 )第13页，此课件共57页哦7.1 图与网络

11、的基本概念对于有向图来说，如果链和圈中边的方向与有向图对于有向图来说，如果链和圈中边的方向与有向图中所标方向相同，那么链就称为中所标方向相同，那么链就称为道路道路，圈就称为，圈就称为回回路路。连通图：连通图：无向图中，任意两个点之间至少有一条无向图中，任意两个点之间至少有一条链相连的图称为链相连的图称为连通图连通图第14页，此课件共57页哦7.1 图与网络的基本概念6 6、子图与生成子图：、子图与生成子图：子图：子图：图图G=(V,E)，E是是E的子集，的子集，V是是V的子集，的子集，且且E 的边与的边与V的顶点想关联，的顶点想关联，G=(V,E)是图是图G的的一个一个子图子图。生成子图生成子

12、图：若：若V=V，则，则G是是G的的生成子图生成子图第15页，此课件共57页哦7.1 图与网络的基本概念6 6、网络：、网络：网络（赋权图）：网络（赋权图）：由点、边以及与点边相关联的权数由点、边以及与点边相关联的权数所构成的图称为网络，记作所构成的图称为网络，记作N=V,E,Wv4v2v3v16215846v4v2v3v16215846无向网络无向网络无向网络无向网络有向网络有向网络有向网络有向网络第16页，此课件共57页哦7.1 图与网络的基本概念7.1.2 树的概念及性质树的概念及性质1、树（、树（T）：）：无圈的连通图称为无圈的连通图称为树树 树叶树叶 分枝点分枝点第17页，此课件共5

13、7页哦7.1 图与网络的基本概念7.1.2 树的概念及性质树的概念及性质2 2、树的性质、树的性质性质性质7.17.1 树中任意两点之间有且只有一条链。树中任意两点之间有且只有一条链。性质性质7.27.2 如图如图G G中任意两点之间，有且只有一条链，中任意两点之间，有且只有一条链，则该图则该图G G是一个树。是一个树。性质性质7.37.3 一个树，则一个树，则m=n-1m=n-1。性质性质7.47.4 树中任意两个不相邻的点之间增加一条树中任意两个不相邻的点之间增加一条边，则形成唯一的圈。边，则形成唯一的圈。性质性质7.57.5 一个树如果去掉任何一条边，该图就不再一个树如果去掉任何一条边，

14、该图就不再连通。连通。第18页，此课件共57页哦7.1 图与网络的基本概念7.1.2 7.1.2 树的概念及性质树的概念及性质3 3、图的生成树、图的生成树生成树（支撑树）：生成树（支撑树）：图图G G的生成子图是一棵树，则称该树的生成子图是一棵树，则称该树为为G G的的生成树生成树图图G G中属于生成树的边称为中属于生成树的边称为树枝树枝，不属于生成树的边称，不属于生成树的边称为为弦弦定理定理7.37.3：图图G=G=（V,EV,E）,有生成树的充分必要条件为有生成树的充分必要条件为G G是连通图是连通图第19页，此课件共57页哦4、最小生成树、最小生成树、最小生成树、最小生成树：图：图：图

15、：图G=(V，E)E)的生成树所有树枝上的权数的的生成树所有树枝上的权数的的生成树所有树枝上的权数的的生成树所有树枝上的权数的总和总和总和总和,称为称为生成树的权生成树的权。权数最小的生成树称为。权数最小的生成树称为。权数最小的生成树称为。权数最小的生成树称为最小生成树最小生成树最小生成树最小生成树。寻找最小生成树的方法：避圈法、破圈法寻找最小生成树的方法：避圈法、破圈法最小生成树最小生成树最小生成树最小生成树权权=11=11第20页，此课件共57页哦5 5、根树、根树有向树：有向树：有向树：有向树：若一个有向图在不考虑边的方向时是一棵树，则称若一个有向图在不考虑边的方向时是一棵树，则称这个有

16、向图为这个有向图为有向树有向树有向树有向树。根树：根树：根树：根树：有向树有向树有向树有向树T，恰有一个结点入次，恰有一个结点入次，恰有一个结点入次，恰有一个结点入次d-(vi)=0=0，其余各点入次，其余各点入次，其余各点入次，其余各点入次d-(vi)=1，则称，则称，则称，则称T为为为为根树根树根树根树根树中入次根树中入次d-(vi)=0的点称为的点称为的点称为的点称为根根出次出次d+(vi)=0=0称为称为叶叶叶叶其他点称为其他点称为其他点称为其他点称为分枝点分枝点分枝点分枝点7.1 图与网络的基本概念第21页，此课件共57页哦在根树中，若每个顶点的出次在根树中，若每个顶点的出次d d-

17、(v(vi i)mm，称这棵树为，称这棵树为m m叉树叉树。若每个顶点的出次若每个顶点的出次d d-(v(vi i)=m)=m或或0 0，则，则称这棵树为称这棵树为完全完全m m叉树叉树7.1 图与网络的基本概念第22页，此课件共57页哦v2v3v7v1v8v4v5v66 61 13 34 410105 52 27 75 59 93 34 46 68 82 2求从求从求从求从v1到到到到v8的最的最的最的最短路径短路径短路径短路径标号：标号：标号：标号：T标号（试探性标号）标号（试探性标号）P标号（永久性标号）标号（永久性标号）1、狄克斯托算法（、狄克斯托算法（Dijkstra）:标号法标号法

18、7.2 最短路问题第23页，此课件共57页哦V V2 2V V3 3V V7 7V V1 1V V8 8V V4 4V V5 5V V6 66 61 13 34 410105 52 27 75 59 93 34 46 68 82 2S=S=v1 P P(v(v1 1)=0,T(v)=0,T(vi)=)=T(vT(v2 2)=2,T(v)=2,T(v4 4)=1,T(v)=1,T(v6 6)=3)=3min min T(vT(v2 2),T(v),T(v4 4),T(v),T(v6 6)=min 2=min 2，1 1，3=13=1P(v(v4 4)=1 S=1 S=v v1,v4 P(vP(v

19、1 1)=0)=0L L1212=2=2L L1414=1=1L L1616=3=3P(vP(v4 4)=1)=1第24页，此课件共57页哦v v2 2v v3 3v v7 7v v1 1v v8 8v v4 4v v5 5v v6 66 61 13 34 410105 52 27 75 59 93 34 46 68 82 2S=S=v v1,v4 4 P(vP(v2 2)=2=2P(vP(v1 1)=0)=0P(vP(v4 4)=1)=1T(vT(v2 2)=2 T(v)=2 T(v6 6)=3 T(v)=3 T(v7 7)=3)=3min min T(vT(v2 2),T(v),T(v6

20、6),T(v),T(v7 7)=min 2=min 2，3 3，3=23=2P P(v(v2 2)=2 S=2 S=v1,v4 4,v,v2 2 L L1212=2=2L L1616=3=3L L4242=11=11L L4747=3=3第25页，此课件共57页哦v v2 2v v3 3v v7 7v v1 1v v8 8v v4 4v v5 5v v6 66 61 13 34 410105 52 27 75 59 93 34 46 68 82 2S=S=v v1,v4,v,v2 P(vP(v6 6)=3=3P(vP(v1 1)=0)=0P(vP(v4 4)=1)=1P(vP(v2 2)=2=

21、2L L1616=3=3L L4747=3=3 L L2323=8=8L L2525=7=7T(vT(v6 6)=3 T(v)=3 T(v7 7)=3 T(v)=3 T(v3 3)=8 T(v)=8 T(v5 5)=7)=7 min min T(vT(v6 6),T(v),T(v7 7),T(v),T(v3 3),T(v),T(v5 5)=min 3,=min 3,3 3,8,7=38,7=3P P(v6 6)=3 S=3 S=v v1,v v4 4,v2,v,v6 6 第26页，此课件共57页哦v v2 2v v3 3v v7 7v v1 1v v8 8v v4 4v v5 5v v6 66

22、 61 13 34 410105 52 27 75 59 93 34 46 68 82 2S=S=v v1 1,v v4 4,v2 2,v,v6 6 P(vP(v7 7)=3=3P(vP(v6 6)=3=3P(vP(v1 1)=0)=0P(vP(v4 4)=1)=1P(vP(v2 2)=2=2L L4747=3=3 L L2323=8=8L L2525=7=7 L L6767=7=7T(vT(v7 7)=3 T(v)=3 T(v3 3)=8 T(v)=8 T(v5 5)=7 )=7 min min T(vT(v7 7),T(v),T(v3 3),T(v),T(v5 5)=min 3=min 3

23、,8,7=38,7=3P(v7)=3 S=3 S=v v1,v4,v,v2,v,v6 6,v7 7 第27页，此课件共57页哦v v2 2v v3 3v v7 7v v1 1v v8 8v v4 4v v5 5v v6 66 61 13 34 410105 52 27 75 59 93 34 46 68 82 2S=S=v1,v4 4,v,v2,v,v6,v7 7 P(vP(v5 5)=6=6P(vP(v7 7)=3=3P(vP(v6 6)=3=3P(vP(v1 1)=0)=0P(vP(v4 4)=1)=1P(vP(v2 2)=2=2L L2323=8=8L L2525=7=7 L L7575

24、=6=6L L7878=11=11 T(vT(v3 3)=8 T(v)=8 T(v5 5)=6 T(v)=6 T(v8 8)=11 )=11 min min T(vT(v3 3),T(v),T(v5 5),T(v),T(v8 8)=min 8=min 8,6,11=66,11=6P P(v(v5)=6 S=6 S=v1,v4 4,v,v2 2,v6 6,v7,v v5 第28页，此课件共57页哦v v2 2v v3 3v v7 7v v1 1v v8 8v v4 4v v5 5v v6 66 61 13 34 410105 52 27 75 59 93 34 46 68 82 2S=S=v1,

25、v4 4,v,v2,v6 6,v7,v v5 P(vP(v3 3)=8=8P(vP(v5 5)=6=6P(vP(v7 7)=3=3P(vP(v6 6)=3=3P(vP(v1 1)=0)=0P(vP(v4 4)=1)=1P(vP(v2 2)=2=2L L2323=8=8L L5353=15=15 L L5858=10=10L L7878=11=11 T(vT(v3 3)=8 T(v)=8 T(v8 8)=10 )=10 min min T(vT(v3 3),T(v),T(v8 8)=min 8=min 8,10=810=8P P(v3 3)=8 S=8 S=v v1,v v4,v,v2 2,v,

26、v6 6,v,v7,v v5 5,v v3 第29页，此课件共57页哦v v2 2v v3 3v v7 7v v1 1v v8 8v v4 4v v5 5v v6 66 61 13 34 410105 52 27 75 59 93 34 46 68 82 2S=S=v v1 1,v4,v,v2,v6 6,v,v7,v5,v3 3 P(vP(v8 8)=10=10P(vP(v3 3)=8=8P(vP(v5 5)=6=6P(vP(v7 7)=3=3P(vP(v6 6)=3=3P(vP(v1 1)=0)=0P(vP(v4 4)=1)=1P(vP(v2 2)=2=2L L3838=14=14L L58

27、58=10=10L L7878=11=11 T(vT(v8 8)=10 )=10 P(v8 8)=10 S=10 S=v v1,v4 4,v,v2,v6,v,v7 7,v5,v v3,v,v8 第30页，此课件共57页哦v v2 2v v3 3v v7 7v v1 1v v8 8v v4 4v v5 5v v6 66 61 13 34 410105 52 27 75 59 93 34 46 68 82 2S=S=v v1 1,v v4 4,v2 2,v6 6,v7,v v5,v v3,v,v8 v v v v1 1 1 1到到到到v v v v8 8 8 8的最短路径为的最短路径为的最短路径为

28、的最短路径为vvvv1 1 1 1,v v v v4 4 4 4,v,v,v,v7 7 7 7,v v v v5 5 5 5,v v v v8 8 8 8 ，长度为，长度为，长度为，长度为10101010P(vP(v8 8)=10=10P(vP(v3 3)=8=8P(vP(v5 5)=6=6P(vP(v7 7)=3=3P(vP(v6 6)=3=3P(vP(v1 1)=0)=0P(vP(v4 4)=1)=1P(vP(v2 2)=2=2第31页，此课件共57页哦狄克斯托算法（狄克斯托算法（DijkstraDijkstra）的适用条件：）的适用条件：）的适用条件：）的适用条件：1、用于赋权有向图。、

29、用于赋权有向图。对于赋权无向图的处理对于赋权无向图的处理对于赋权无向图的处理对于赋权无向图的处理2、权数、权数、权数、权数 wij ij 0第32页，此课件共57页哦2 2、逐次逼近算法、逐次逼近算法可用于网络中有权数为负数的边可用于网络中有权数为负数的边7.2 最短路问题第33页，此课件共57页哦7.2 最短路问题第34页，此课件共57页哦v v1 1v v3 3v v4 4v v2 2v v5 5v vt tv vs sw ww w6 62 24 43 37 74 43 31 17 79 98 88 87.3 最大流问题第35页，此课件共57页哦1 1、流量和容量、流量和容量有向连通图有向

30、连通图G=(VG=(V，E),G的每条边（的每条边（的每条边（的每条边（v vi，vj）上有非负数）上有非负数cij ij称为称为称为称为边的容量边的容量边的容量边的容量，仅有一个入次为，仅有一个入次为，仅有一个入次为，仅有一个入次为0的点的点v vs s称为称为发点发点发点发点，一个出，一个出次为次为0 0的点的点vt称为称为称为称为收点收点收点收点，其余点为中间点，这样的网络，其余点为中间点，这样的网络G称为称为容量网络容量网络，记为，记为G=G=（V,E,CV,E,C）。7.3.1 基本概念基本概念7.3 最大流问题第36页，此课件共57页哦2 2、可行流和最大流、可行流和最大流、可行流

31、和最大流、可行流和最大流可行流必须满足的两个条件可行流必须满足的两个条件（1）容量限定条件：）容量限定条件：0fij cij ij（2 2）流量守恒条件：中间点的流入量等于流出量）流量守恒条件：中间点的流入量等于流出量）流量守恒条件：中间点的流入量等于流出量）流量守恒条件：中间点的流入量等于流出量7.3 最大流问题第37页，此课件共57页哦v vj jv vi if fij ij=5=5c cij ij=5=5饱和边、不饱和边、流量间隙饱和边、不饱和边、流量间隙(剩余流量剩余流量)（vi，vj j）是饱和的）是饱和的）是饱和的）是饱和的2 2、如果、如果、如果、如果f fijcij，流从，流从

32、v vi i到到v vj的方向是不饱和的的方向是不饱和的的方向是不饱和的的方向是不饱和的(vi i，vj)是不饱和的是不饱和的是不饱和的是不饱和的间隙为间隙为 12=c1212-f-f12=5 3=21 1、如果、如果、如果、如果c cij ij=fij，流从，流从，流从，流从vi到到到到v vj j的方向是饱和的的方向是饱和的的方向是饱和的的方向是饱和的v vj jv vi if fij ij=3=3c cij ij=5=53 3、增广链、增广链第38页，此课件共57页哦容量网络容量网络容量网络容量网络G，若，若u为网络中从为网络中从为网络中从为网络中从vs s到到到到vt t的一条链，的一

33、条链，u上的边与上的边与上的边与上的边与u u同同向的称为向的称为前向边前向边前向边前向边，与，与u u反向的称为反向的称为后向边后向边后向边后向边给定一个给定一个G的一个可的一个可行流，行流，u 如果满足：如果满足：则称则称u为从为从vs到到vt的的增广链增广链。定理定理7.47.4 可行流可行流可行流可行流f是最大流的充要条件是不存在从是最大流的充要条件是不存在从是最大流的充要条件是不存在从是最大流的充要条件是不存在从v vs s到到到到v vt的可的可的可的可增广链。增广链。增广链。增广链。7.3 最大流问题第39页，此课件共57页哦v v1 1v v3 3v v4 4v v2 2v v

34、5 5v vt tv vs sw ww w6 62 24 43 37 74 43 31 17 79 98 88 84、割集、割集、割集、割集S=(vS=(vs s,v,v3 3)=(v1,v2,v4,v5,vt)为为G的割集的割集割集割集割集割集E的容量的容量=14v v1 1v v3 3v v4 4v v2 2v v5 5v vt tv vs sw ww w6 62 24 43 37 74 43 31 17 79 98 88 8其中其中其中其中S=(vS=(vs s,v1 1,v3 3,v,v4)=(v2,v5,vt)为为G的割集的割集(vs,v1 1),(v3 3,v,v4),(v),(v

35、3,v5)的容量的容量和为割集和为割集E的容量的容量的容量的容量=13=13第40页，此课件共57页哦其中其中其中其中容量最小的容量最小的割集称为割集称为割集称为割集称为网络网络G的最小割集的最小割集的最小割集的最小割集 (最小割最小割)定理定理7.5：（流量（流量割集定理）割集定理）设设f为网络为网络G=（V,E,C）的任一可行流，）的任一可行流，S是任一割集，是任一割集，则有则有W(f)定理定理7.6：(最大流最大流-最小割定理最小割定理)任一个网络任一个网络G中，中，从从v vi i到到vj j的最大流的流量等于分离的最大流的流量等于分离v vi i，v vj的最小割的容的最小割的容的最

36、小割的容的最小割的容量量量量7.3 最大流问题第41页，此课件共57页哦v vs sv v2 2v v3 3v v1 1v v4 4v v5 5v vt tv v6 6(5,0)(5,0)(3,0)(3,0)(4,0)(4,0)(3,0)(3,0)(2,0)(2,0)(5,0)(5,0)(3,0)(3,0)(4,0)(4,0)(5,0)(5,0)(3,0)(3,0)(2,0)(2,0)ff7.3.2 最大流算法最大流算法7.3 最大流问题第42页，此课件共57页哦v vs sv v2 2v v3 3v v1 1v v4 4v v5 5v vt tv v6 6(5,0)(5,0)(3,0)(3,

37、0)(4,0)(4,0)(3,0)(3,0)(2,0)(2,0)(5,0)(5,0)(3,0)(3,0)(4,0)(4,0)(5,0)(5,0)(3,0)(3,0)(2,0)(2,0)ff解：从零流开始，寻找增广链解：从零流开始，寻找增广链解：从零流开始，寻找增广链解：从零流开始，寻找增广链v vs svv1vv4 4vvt 最小容量最小容量min 5，5，4=44=4(5,4)(5,4)(5,4)(5,4)(4,4)(4,4)v vs svv1 1v5 5vt t 最小容量最小容量最小容量最小容量min 1，3 3，3=13=1(5,5)(5,5)(3,1)(3,1)(3,1)(3,1)vs

38、 sv2vv5vt 最小容量最小容量最小容量最小容量min 4，3，2=22=2(4,2)(4,2)(3,2)(3,2)(3,3)(3,3)v vs svv2vv6vvt t 最小容量最小容量最小容量最小容量min 2min 2，2，5=2(4,4)(4,4)(2,2)(2,2)(5,2)(5,2)v vsvv3 3vv6 6vt t 最小容量最小容量最小容量最小容量min 3min 3，2，3=23=2(3,2)(3,2)(2,2)(2,2)(5,4)(5,4)网络最大流量网络最大流量网络最大流量网络最大流量=11，流量安排如上图，流量安排如上图，流量安排如上图，流量安排如上图第43页，此课

39、件共57页哦v vs sv v2 2v v3 3v v1 1v v4 4v v5 5v vt tv v6 6(5,5)(5,5)(3,2)(3,2)(4,2)(4,2)(3,0)(3,0)(2,2)(2,2)(5,2)(5,2)(3,3)(3,3)(4,2)(4,2)(5,4)(5,4)(3,3)(3,3)(2,2)(2,2)从任一可行流开始寻找最大流，采用标号法寻找增广从任一可行流开始寻找最大流，采用标号法寻找增广从任一可行流开始寻找最大流，采用标号法寻找增广从任一可行流开始寻找最大流，采用标号法寻找增广链链链链(,+,+)解：先给发点标号，即：解：先给发点标号，即：解：先给发点标号，即：解

40、：先给发点标号，即：vs标（标（，+）第44页，此课件共57页哦(vs，v v1 1)fs1=cs1=5=5(vs，v2)f fs2 s2=2 c=2 cs2=4 s2=2 所以给所以给v2标号标号标号标号(+vs s，2)2)(v(vs，v3)f fs3=2 c=2 cs3 s3=3 s3=1 所以给所以给v v3标号标号标号标号(+v(+vs s，1)1)v vs sv v2 2v v3 3v v1 1v v4 4v v5 5v vt tv v6 6(5,5)(5,5)(3,2)(3,2)(4,2)(4,2)(3,0)(3,0)(2,2)(2,2)(5,2)(5,2)(3,3)(3,3)(

41、4,2)(4,2)(5,4)(5,4)(3,3)(3,3)(2,2)(2,2)(,+,+)(+v(+vs s,2),2)(+v(+vs s,1),1)第45页，此课件共57页哦(v2 2，v5 5)f)f25 25=0 c=0 0 =3 0 5151=min3,2=2 所以给所以给v v1标号标号标号标号(-v5 5，2)v vs sv v2 2v v3 3v v1 1v v4 4v v5 5v vt tv v6 6(5,5)(5,5)(3,2)(3,2)(4,2)(4,2)(3,0)(3,0)(2,2)(2,2)(5,2)(5,2)(3,3)(3,3)(4,2)(4,2)(5,4)(5,4)

42、(3,3)(3,3)(2,2)(2,2)(,+,+)(+v(+vs s,2),2)(+v(+vs s,1),1)(+v(+v2 2,2),2)(-v(-v5 5,2),2)第47页，此课件共57页哦(v1，v v4)f14=2 c24 24=5 =5 51=min3,2=2 所以给所以给所以给所以给v2标号标号(+v1 1，2)2)v vs sv v2 2v v3 3v v1 1v v4 4v v5 5v vt tv v6 6(5,5)(5,5)(3,2)(3,2)(4,2)(4,2)(3,0)(3,0)(2,2)(2,2)(5,2)(5,2)(3,3)(3,3)(4,2)(4,2)(5,4)

43、(5,4)(3,3)(3,3)(2,2)(2,2)(,+,+)(+v(+vs s,2),2)(+v(+vs s,1),1)(+v(+v2 2,2),2)(-v(-v5 5,2),2)(+v(+v1 1,2),2)第48页，此课件共57页哦(v(v4，vt t)f4t=2 c4t=4 4t4t=min2,2=2 所以给所以给vt t标号标号标号标号(+v(+v4，2)v vs sv v2 2v v3 3v v1 1v v4 4v v5 5v vt tv v6 6(5,5)(5,5)(3,2)(3,2)(4,2)(4,2)(3,0)(3,0)(2,2)(2,2)(5,2)(5,2)(3,3)(3,

44、3)(4,2)(4,2)(5,4)(5,4)(3,3)(3,3)(2,2)(2,2)(,+,+)(+v(+vs s,2),2)(+v(+vs s,1),1)(+v(+v2 2,2),2)(-v(-v5 5,2),2)(+v(+v1 1,2),2)(+v(+v4 4,2),2)第49页，此课件共57页哦存在一条从存在一条从vs s到到v vt 的可增广链的可增广链 =2=2调整流量调整流量调整流量调整流量v vs sv v2 2v v3 3v v1 1v v4 4v v5 5v vt tv v6 6(5,5)(5,5)(3,2)(3,2)(4,2)(4,2)(3,0)(3,0)(2,2)(2,2

45、)(5,2)(5,2)(3,3)(3,3)(4,2)(4,2)(5,4)(5,4)(3,3)(3,3)(2,2)(2,2)(,+,+)(+v(+vs s,2),2)(+v(+vs s,1),1)(+v(+v2 2,2),2)(-v(-v5 5,2),2)(+v(+v1 1,2),2)(+v(+v4 4,2),2)(4,4)(4,4)(3,2)(3,2)(3,1)(3,1)(5,4)(5,4)(4,4)(4,4)第50页，此课件共57页哦(vs s，v1 1)f)fs1 s1=cs1=5=5(vs，v2)fs2=4=c=4=cs2 s2=4(vs，v v3)f fs3=2 0 0，则令，则令，则

46、令，则令j=min(f=min(fji,i)，并给，并给，并给，并给vj标号标号(-vi i,j)b b：若有向边方向为从：若有向边方向为从v vi i到到v vj，且，且fij c cij，则令，则令，则令，则令j=min(=min(c cij -f-fji,i)，并给，并给v vj标号标号标号标号(+v(+vi,j)如果如果如果如果v vt t得到标号，说明存在一条可增广链，需要调整得到标号，说明存在一条可增广链，需要调整得到标号，说明存在一条可增广链，需要调整得到标号，说明存在一条可增广链，需要调整;如果如果如果如果vt没得到标号，说明已找到最大流。没得到标号，说明已找到最大流。第53页

47、，此课件共57页哦2、调整过程：、调整过程：（1）令令（2）调整之后，重新进行标号。）调整之后，重新进行标号。3、重复、重复1、2步直到找到最大流。步直到找到最大流。第54页，此课件共57页哦 在容量网络在容量网络G=V,E,C中，每条边（中，每条边（vi,vj）上除了）上除了容量容量cij外，还给出了单位流量的费用外，还给出了单位流量的费用dij0，记为，记为G=V,E,C,D。d(f)=dijfij称为流称为流f的费用。的费用。所谓最小费用最大流问题就是找出所有最大流中总所谓最小费用最大流问题就是找出所有最大流中总费用最小的最大流。费用最小的最大流。7.4 最小费用最大流问题第55页，此课件共57页哦7.4 最小费用最大流问题 在容量网络在容量网络G=V,E,C,D中，中，f是是G上的一个可上的一个可行流，是从行流，是从vs到到vt的（关于的（关于f）的增广链，）的增广链，称为增广链的费用。称为增广链的费用。定理定理7.7：若若f是流量为是流量为W(f)的最小费用流，的最小费用流，是关于是关于f的从的从vs到到vt的一条最小费用增广链，则的一条最小费用增广链，则f经过调整流经过调整流量量得到新可行流得到新可行流f，一定是流量为，一定是流量为W(f)+的可行流的可行流中的最小费用流。中的最小费用流。第56页，此课件共57页哦7.4 最小费用最大流问题第57页，此课件共57页哦