运筹学基础及应用第五图与网络分析.pptx

《运筹学基础及应用第五图与网络分析.pptx》由会员分享，可在线阅读，更多相关《运筹学基础及应用第五图与网络分析.pptx（81页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023/4/221 1图的基本概念与模型 2树图和图的最小部分树 3最短路问题 4网络的最大流 5最小费用流第六章第六章 图与网络分析图与网络分析第1页/共81页2023/4/222BACD 当地的居民热衷于这样一个问题：一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。哥尼斯堡的七桥问题第2页/共81页2023/4/223 为了寻找答案，1736年欧拉把陆地缩为一点，把桥作为连接点的边，将这个问题抽象成图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶

2、点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。BACD第3页/共81页2023/4/224 在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。例 有六支球队进行足球比赛，我们分别用点v1v6 表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1 队战胜v2 队，v2 队战胜v3队，v3 队战胜v5 队，如此等等。这个胜负情况，可以用下图所示的有向图反映出来。v v3 3v v1 1v v2 2v v4 4v v6 6v v5 5第4页/共81页2023/4/2256.16.1图的基本概念与模型图的基本概念与模型

3、 图（graph）是由一些结点或顶点（nodes or vertices）以及连接点的边（edges）构成。记做G=V,E，其中 V 是顶点的集合，E 是边的集合。给图中的点和边赋以具体的含义和权值，我们称这样的图为网络图（赋权图）一、基本概念第5页/共81页2023/4/226 图中的点用 v 表示，边用 e 表示，对每条边可用它所联结的点表示，如图，则有：e1=v1,v1，e2=v1,v2或e2=v2,v1用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。通常用点表示研究对象,用点与点之间的线表示研究对象之间的特定关系。一般情况下，图中点的相对位置如何，点与点之

4、间线的长短曲直，对于反映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图，工程图等本质上是不同的。第6页/共81页2023/4/227端点，关联边，相邻 若边 e 可表示为e=vi,vj，称 vi 和 vj 是边 e 的端点，同时称边 e 为点 vi 和 vj 的关联边，若点 vi,vj 与同一条边关联，称点 vi 和 vj 相邻；若边 ei 与 ej 有公共端点，称边 ei 和 ej 相邻；如果边 e 的两个端点相重，称该边为环，如果两个点之间的边多于一条，称为具有多重边，对无环、无多重边的图称为简单图。环，多重边，简单图第7页/共81页2023/4/228次，奇点，偶点，孤立点

5、与某个点相关联的边的数目，称为该点的次（或度、线度），记作 d(v)。次为奇数的点称为奇点，次为偶数的点称为偶点，次为零的点称为孤立点。如图：奇点为 v5，v3偶点为 v1,v2,v4,v6孤立点为 v6第8页/共81页2023/4/229链，圈，路，回路，连通图 图中有些点和边的交替序列=v0,e1,v1,e2,ek,vk，若其各边 e1,e2,ek 各不相同，且任意 vi,t-1,vit(2 t k)都相邻，称 为链，如果链中所有的顶点 v0,v1,vk也不相同，这样的链成为路，起点和终点重合的链称为圈，起点和终点重合的路称为回路，若在一个图中，每一对顶点之间至少存在一条链，称这样的图为连

6、通图，否则称该图为不连通的。链路圈第9页/共81页2023/4/2210完全图，偶图 一个简单图中若任意两点之间均有边相连，称这样的图为完全图，含有 n 个顶点的完全图，其边数有 条。如果图的顶点能分成两个互不相交的非空集合 V1 和V2,使在同一集合中任意两个顶点均不相邻，称这样的图为偶图（也称二分图），如果偶图的顶点集合V1 和V2 之间的每一对顶点都有一条边相连，称这样的图为完全偶图，完全偶图中V1 含m 个顶点，V2 含有 n 个顶点，则其边数共 m n 条。第10页/共81页2023/4/2211子图，部分图 图 G1=V1,E1 和 G2=V2,E2，如果有 和 ，称 G1 是 G

7、2 的一个子图；若有 ，则称 G1 是 G2 的一个部分图。注意：部分图也是子图，但子图不一定是部分图。子图：部分图第11页/共81页2023/4/221222树图和最小部分树树图和最小部分树 树图（简称树，记作 T(V,E)）是无圈的连通图。（无圈，无多重边）一.树的性质性质1.任何树中必存在次为1 的点。次为1的点称为悬挂点，与之关联的边称为悬挂边。性质2.具有 n 个顶点的树恰有（n-1）条边。性质3.任何具有n 个点、(n-1)条边连通图是树。说明：1.树中只要任意再加一条边，必出现圈。2.树中任意两点之间有且只有一条通路，从树中任意删掉一条边，就不再连通。（树是最脆弱的连通图）第12

8、页/共81页2023/4/2213二.图的最小部分树如果 G1 是 G2 的部分图，又是树图，则称 G1 是 G2 的部分树（或支撑树）；树图的各条边称为树枝(假定各边均有权重)；树枝总长最小的部分树，称为该图的最小部分树(也称最小支撑树)。定理1.图中任一个点 i，若 j 是与 i 相邻点中距离最近的，则边 i,j 一定包含在该图的最小部分树中。推论.把图的所有点分成 V 和 两个集合，则两集合之间连线的最短边一定包含在最小部分树内。第13页/共81页2023/4/2214三.避圈法和破圈法 寻找最小部分树的方法主要有避圈法和破圈法两种。避圈法步骤：1.从图中任选一点 vi，让 vi V，图

9、中其余点均包含在 中；2.从 V 与 的连线中找出最小边，这条边一定包含在最小部分树中，不妨设这条边为vi ,vj将其加粗，标记为最小部分树中的边。3.令 VvjV，-vj ；4.重复2、3两步，一直到图中所有点均包含在 V 中。第14页/共81页2023/4/2215 避圈法另一种做法：1.在所有各边中找到边权最小的一条，将其作为最小部分树中的第一边；在剩余的边中，仍然找到边权最小的作为最小部分树的第二条边；2.在剩余的边中，找到边权最小的边，查看其是否与前面的边形成圈，如果没有，则在最小部分树中添加该边，如果形成了圈，则不再考虑该边；3.重复进行第二步，直到找到第 n-1 条边为止。（因为

10、有 n 个顶点的树中一定有 n-1 条边）第15页/共81页2023/4/2216例：分别用两种避圈法构造下图的最小部分树。第一种解法：1.在点集中任选一点，不妨取 S，令 V=S 2.找到和 S 相邻的边中，权值最小的 S,A。第16页/共81页2023/4/22173.V=S,A4.重复第2，3步，找到下一个点。第17页/共81页2023/4/2218 第二种做法求解过程：第18页/共81页2023/4/2219破圈法求解步骤：1.从图 N 中任取一回路，去掉这个回路中边权最大的边，得到原图的一个子图 N1。2.从剩余的子图中任找一回路，同样去掉回路中边权最大的一条边，得一新的子图；3.重

11、复第 2 步，直到图中不再含有回路为止。用破圈法求解上例：1.任意找到一回路，不妨取 DETD，去掉边权最大的边T,E;第19页/共81页2023/4/22202.从剩余的子图中任找一回路，同样去掉回路中边权最大的一条边，得一新的子图；依次类推。第20页/共81页2023/4/2221破圈法的另一种解法：1.从剩余图中找到边权最大的一条边，如果将其删除后图仍然是连通的，则删除此边，否则不再考虑此边；2.重复上述步骤，直到剩余边数为 n-1 为止。用此法求解上述问题：第21页/共81页2023/4/2222注意：1.一个图的最小部分树不唯一，该题中用几种解法得到的结果都是相同的，是特殊情况；2.

12、不同解法得到的最小部分树所包含的边虽然可能不相同，但是，每个最小部分树中所有边权的总和一定都是相同的，即都达到了最小。第22页/共81页2023/4/222333最短路问题最短路问题最短路问题是指从给定的网络图中找出任意两点之间距离最短（权值和最小）的一条路。某些整数规划和动态规划问题可以归结为求最短路的问题。如选址问题、管道铺设选线问题、设备更新、投资等问题。最短路的求法：1.从某一点至其它各点之间最短距离的狄克斯屈拉(Dijksrta)算法;2.求网络图中任意两点之间的最短距离的矩阵算法。第23页/共81页2023/4/2224 一.Dijkstra 算法1.设 dij 表示图中两相邻点

13、i 与 j 的距离，若 i 与 j 不相邻，令 dij=，显然 dii=0。Dijkstra 算法假设：基本思路：如果 v1 v2 v3 v4 是 v1 v4 的最短路径，则 v1 v2 v3 一定是 v1 v3 的最短路径。v2 v3 v4 一定是 v2 v4 的最短路径。2.设 Lsi 表示从 s 点到 i 点的最短距离。第24页/共81页2023/4/2225Dijkstra 算法步骤：1.对起始点 s，因 Lss=0，将 0 标注在 s 旁的小方框内，表示 s 点已标号；2.从点 s 出发，找出与 s 相邻的点中距离最小的一个，设为 r，将 Lsr=Lss+dsr 的值标注在 r 旁的

14、小方框内，表明点 r 也已标号；3.从已标号的点出发，找出与这些点相邻的所有未标号点 p，若有 Lsp=min Lss+dsp,Lsr+drp，则对 p 点标号，并将 Lsp 的值标注在 p 点旁的小方框内；4.重复第 3 步，直到 t 点得到标号为止。求从起始点 s 到终止点 t 的最短路径。第25页/共81页2023/4/2226例.求下图中从 v1 到 v7 的最短路。解：(1)从 v1 点出发，对 v1 点标号，将 L11=0 标注在 旁的小方框内，令 v1V，其余点属于 ；第26页/共81页2023/4/2227L1r=min 0+d12,0+d13 =min5,2=2=L13(2)

15、同 v1 相邻的未标号点有v2、v3，第27页/共81页2023/4/2228对 v3 标号，将 L13 的值标注在v3 旁的小方框内；将(v1,v3)加粗，并令 Vv3 V，。第28页/共81页2023/4/2229L1p=min L11+d12,L13+d34,L13+d36 =min0+5,2+7,2+4=5=L12(3)同 v1,v3 相邻的未标号点有v2、v4、v6，第29页/共81页2023/4/2230对 v2 标号，将 L12 的值标注在 v2 旁的小方框内；将(v1,v2)加粗，并令 Vv2 V，第30页/共81页2023/4/2231L1p=min L12+d25,L12+

16、d24,L13+d34,L13+d36 =min5+7,5+2,2+7,2+4 =6 =L16。(4)同 v1,v2,v3 相邻的未标号点有v4、v5、v6，第31页/共81页2023/4/2232对 v6 标号，将 L16 的值标注在 v6 旁的小方框内；将(v3,v6)加粗，并令 Vv6 V，第32页/共81页2023/4/2233L1p=min L12+d25,L12+d24,L13+d34,L16+d64,L16+d65,L16+d67 =min5+7,5+2,2+7,6+2,6+1,6+6 =7 =L14 =L15(5)同 v1,v2,v3,v6 相邻的未标号点有v4、v5、v7，第

17、33页/共81页2023/4/2234对 v4,v5 同时标号，将 L14=L15 的值标注在 v4,v5 旁的小方框内；将(v2,v4),(v6,v5)加粗，并令Vv4v5V，第34页/共81页2023/4/2235L1p=min L15+d57,L16+d67 =min7+3,6+6=10=L17(6)同 v1,v2,v3,v4,v5,v6 相邻的未标号点只有 v7，第35页/共81页2023/4/2236 对 v7 标号，将 L17 的值标注在 v7 旁的小方框内；将(v5,v7)加粗。图中粗线表明从点 v1 到网络中其它各点的最短路，各点旁的数字就是点 v1 到各点的最短距离。第36页

18、/共81页2023/4/2237二.求任意两点间最短距离的矩阵算法用 Dijkstra 算法只能计算从图中某一点到其他点的最短距离，如果要计算各点之间的最短距离就需要对每个点分别计算，而用矩阵算法则可以同时求出所有各点间的最短距离。例.利用矩阵算法求上述网络图中各点间的最短距离。解.设 dij 表示图中两相邻点 i 与 j 的距离，若 i 与 j 不相邻，令 dij=，显然 dii=0。建立距离矩阵：第37页/共81页2023/4/2238第38页/共81页2023/4/2239从上述距离矩阵可以看出从 i 点到 j 点的直接距离，但从 i 到 j 的最段距离不一定就是从 i 点直接到 j 点

19、。如上述问题中，从 v1 v2 的最短距离应该是mind11+d12,d12+d22,d13+d32,d14+d42,d15+d52,d16+d62,d17+d72 即 mind1r+dr2。因此可以构造一个新的矩阵 D(1)，令 D(1)中每一个元素为：dij(1)=mindir+drj，则矩阵 D(1)给出了网络中任意两点之间直接到达及经由一个中间点时的最短距离。第39页/共81页2023/4/2240再构造矩阵 D(2)，dij(2)=mindir(1)+drj(1)。依次类推构造矩阵 D(k)，dij(k)=mindir(k-1)+drj(k-1)计算停止的控制：p是图中顶点数。第40

20、页/共81页2023/4/2241该例中 k=3第41页/共81页2023/4/2242 上述 D(2)中的元素给出了各点间的最短距离，但是并没有给出具体是经过了哪些中间点才得到的这个最短距离，如果要知道中间点具体是什么，需要在计算过程中进行记录。教材160页例5第42页/共81页2023/4/224344网络的最大流网络的最大流一.网络最大流的有关概念 1.有向图与容量网络图中每条边有规定指向的图称为有向图，有向图的边称为弧，记作(vi,vj)，表示方向从点 vi 指向点 vj，有向图是点与弧的集合，记作 D(V,A)。弧(vi,vj)的最大通过能力，称为该弧的容量，记为c(vi,vj)，或

21、简记为 cij。定义了弧容量的网络称为容量网络。第43页/共81页2023/4/2244容量网络通常规定一个发点(源点，记为s)一个收点(汇点，记为t)，网络中其余的点称为中间点。从发点到收点之间允许通过的最大流量称为最大流。多个收(发)点的网络可以转换为只含一个收(发)点。2.流与可行流流是指加在网络各条弧上的一组负载量，对加在弧(vi,vj)上的负载量记作 f(vi,vj)，或简记作 fij，若网络上所有的 fij=0，这个流称为零流。第44页/共81页2023/4/2245以 v(f)表示网络中从 st 的流量，则零流是可行流，求最大流就是求v(f)的最大值。称网络上满足下述条件(1)、

22、(2)的流为可行流：(1)容量限制条件:对所有弧有0f(vi,vj)c(vi,vj)(2)中间点平衡条件：f(vi,vj)-f(vj,vi)=0 (is,t)第45页/共81页2023/4/2246二.割和流量割(集）是指将容量网络中的发点和收点分割开，并使st 的流中断的一组弧的集合（截集）弧旁数字为 cij(fij)有不同的割见教材162页上图中 KK 将网络上的点分割成 V 和 两个集合，并有 sV,t ，称弧的集合 (V,)=(v1,v3),(v2,v4)是一个割。注意，这里不包含(v3,v2)。第46页/共81页2023/4/2247割的容量是组成它的集合中各弧容量之和，用c(V,)

23、表示，f(V,)表示通过割(V,)中所有 V 方向弧的流量的总和;f(,V)表示通过割 中所有 V方向弧的流量的总和，则有：第47页/共81页2023/4/2248从 st 的流量等于通过割的从V 的流量减 V的流量，有：用 v*(f)表示网络中从 st 的最大流，则有因此，上例中最大流不会超过14（所有割集中最小者）。最大流 v*(f)应 最小割的容量(用 c*(V,)表示)第48页/共81页2023/4/2249三.最大流最小割定理增广链：如果在网络的发点和收点之间能找到一条链，在这条链上：所有指向为 st 的弧（称前向弧，记作+），存在f 0(非零)，（反向弧非零流）这样的链称增广链。第

24、49页/共81页2023/4/2250当有增广链存在时，找出 再令显然，经过计算后 f 仍然为可行流，但较原来的可行流 f 流量增大了。因此，只有当网络图中找不到增广链时，st 流才不可能进一步增大。第50页/共81页2023/4/2251定理2.在网络中 st 的最大流量等于它的最小割集的容量，即证明：略（教材163页）三.求网络最大流的标号算法 Ford-Fulkerson 标号算法，其本质是判断是否存在增广链，如果存在，则找出增广链，调整流量；若不存在，则说明已达到最大流。第51页/共81页2023/4/2252第一步：首先给发点 s 标号(0,(s)。第一个数字是使这个点得到标号的前一

25、个点的代号，因 s 是发点，因此记为0。第二个数字(s)表示从上一个标号到这个标号点的流量的最大允许调整值，s 为发点，不限允许调整容量，故(s)=。第二步：列出与已标号点相邻的所有未标号点：1.考虑从标号点 i 出发的弧(i,j)（即正向弧)，如果有 fij=cij，不给点 j 标号；若fij0，则对 h 点标号，记为(i,(h)，其中(h)=min(i),fhi).3.如果某未标号点 k 有两个以上相邻的标号点，可按 (1),(2)中所述规则分别计算出(k)的值，并取其中的最大的一个标记。第三步：重复第二步可能出现如下两种结果：1.标号过程中断，t 得不到标号，说明该网络中不存在增广 链，

26、给定流量即为最大流量。记已标号点集为V，未标号点 集为 ，(V,)为网络的最小割。2.t 得到标号，这时可用反向追踪法在网络中找到一条从 st 的有标号点以及相应的弧连接而成的增广链。第53页/共81页2023/4/2254第四步：修改流量。设原图中可行流为 f，令这样得到网络上的一个新的可行流 f 。第五步：抹掉图上所有标号，重复第一到第四步。注意：在求解步骤中，第三步起到控制运算停止的作用，而不是第五步。第54页/共81页2023/4/2255例：用标号法求下述网络图 s t 的最大流量，并找出该网络图的最小割。第55页/共81页2023/4/2256解：(1)先给 s 点标号(0,)；第

27、56页/共81页2023/4/2257(2)从 s 点出发的弧(s,v2)，因有 fs20，且(v1)=min(v2),f12)=2故对 v1 点标号(v2,2)。(v2,v4)饱和，不标号。第58页/共81页2023/4/2259(4)弧(v1,v3)，因有 f130，且(v4)=min(v3),f43)=1故对 v4 点标号(v3,1)。(v3,t)饱和，不标号,v2 已标号。第60页/共81页2023/4/2261(6)弧(v4,t)，因有 f4tc4t，且(t)=min(v4),(c4t-f4t)=1故对 t 点标号(v4,1)。第61页/共81页2023/4/2262(7)由于收点

28、t 得到标号，用反追踪法找出网络图上的一条增广链。第62页/共81页2023/4/2263(8)修改增广链上各弧的流量：非增广链上的所有弧流量不变，这样得到网络图上的一个新的可行流。第63页/共81页2023/4/2264重复上述标号过程，由于对点 s、v1、v2、v3 标号后，标号中断，故图中的可行流即为最大流，v*(f)=14已标号点集为V=s,v1,v2,v3，未标号点集 ，(V,)=(3,t),(2,4)为网络的最小割。第64页/共81页2023/4/2265三.应用举例例1：P166，例7ADECBF2321211111、方向含义2、E、D之间3、数字含义切断A、F之间的通路，相当于

29、求最小割集。第65页/共81页2023/4/2266例2：P167，例81、匹配关系1234562、匹配限制145f=1 f14 f15第66页/共81页2023/4/2267134f=1 f34 f14 3、等价网络图123456st111111111111第67页/共81页2023/4/226855最小费用流最小费用流 在产销平衡问题中，研究的是使费用最小的物资调运方案；最大流问题中考虑了联结两个点之间的弧的容量限制，但是没考虑流量通过各条弧时发生的费用。实际物资调运中，既要考虑弧的容量又要考虑调运费用的节省，这就是最小费用流要研究的问题。即要寻求一个最大流 f，使得总的运输费用 b(f)

30、最小。第68页/共81页2023/4/2269寻求最大流 f 的方法：从某可行流出发寻找增广链，然后沿着该链调整流量，直至达到最大流量。附加”费用”的因素：希望沿增广链增加流量后，增加的费用是最小的。这样在前一个最小费用流的基础上（），调整流量后，新的流量下的费用也是最小的。如何做到 沿增广链增加流量后，增加的费用最小？假设 是流 f 的一条增广链，沿此增广链调整 1 个单位流量，引起的费用增加量是：第69页/共81页2023/4/2270寻找费用增加最小的增广链就相当于：在由 bij 作为弧权的有向图中寻找从发点到收点的最短路。（增广链的费用）第70页/共81页2023/4/2271寻找最小

31、费用最大流的步骤：1、从零流 f0 开始，其费用就是最小。2、寻找费用最小的增广链：对上一个可行流 fk 构造赋权有向图W(fk),，每对结点间有正向和反向弧。方法如下：正向弧反向弧在此图中找到从发点到收点的最短路。第71页/共81页2023/4/22723、沿此最短路（费用最小的增广链）调整流量，调整量为:得到新的可行流 fk+1 。4、重复上述2、3步，直至不存在从发点到收点的最短路。(即不再存在增广链）第72页/共81页2023/4/2273 例：如图，图中弧旁数字(cij,bij)中，cij 表示弧容量，bij 表示单位费用，求从 s t 的最小费用的最大流。第73页/共81页2023

32、/4/2274解：1.先不考虑弧容量，寻找最短路：该图中路径旁数字为单位费用。2.根据各弧容量，将路径上的流量调整到最大可能：第74页/共81页2023/4/22753.构建新的网络图：(1)对于非饱和且非零的弧(i,j)，在两点间分别给出弧(i,j)和(j,i),其权值分别为 bij 和-bij；(2)对于饱和弧(i,j)，只画出弧(j,i)，其权值为-bij；(3)对于零弧(i,j)，只给出弧(i,j),其权值为bij。第75页/共81页2023/4/22764.重复第 1 步，构造最短路(即费用最小增广链)：5.重复第 2 步，在原流量不减少的前提下调整流量；第76页/共81页2023/4/2277 6.重复第 3 步，重新构造网络图，原则与第 3 步相同：7.重复第 4 步，寻找最短路：第77页/共81页2023/4/22788.重复第 5 步，在原流量不减少的前提下调整流量；9.重复第 6 步，重新构造网络图，原则与第 3 步相同：第78页/共81页2023/4/227910.重复第 7 步，构造最短路：第79页/共81页2023/4/228011.重复第 8 步；12.重复第 9 步，重新构造网络图：13.由于无法再找到最短路，因此计算停止，第11步所得流量即为最小费用的最大流。第80页/共81页2023/4/2281感谢您的观看！第81页/共81页