第5章图与网络模型.ppt

《第5章图与网络模型.ppt》由会员分享，可在线阅读，更多相关《第5章图与网络模型.ppt（94页珍藏版）》请在优知文库上搜索。

1、管管 理理 运运 筹筹 学学1 第五章图与网络模型第五章图与网络模型1 1图与网络的基本概念图与网络的基本概念2 2最短路问题最短路问题3 3最小生成树问题最小生成树问题4 4最大流问题最大流问题5 5车间作业计划车间作业计划6 6统筹法（网络规划）统筹法（网络规划）管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学.管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹

2、 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学221 1图与网络的基本概念图与网络的基本概念 图论中图是由点和边构成，可以反映一些对象之间的关系。图论中图是由点和边构成，可以反映一些对象之间的关系。例如：在一个人群中，对相互认识这个关系我们可以用图例如：在一个人群中，对相互认识这个关系我们可以用图来表示，下图就是一个表示这种关系的图。来表示，下图就是一个表示这种关系的图。(v1)赵赵(

3、v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈e2e1e3e4e5管管 理理 运运 筹筹 学学23 1 1图与网络的基本概念图与网络的基本概念 当然图论不仅仅是要描述对象之间关系，还要研究特定关当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以表示如下，可见的，如对赵等七人的相互认识关系我们也可以表示如下，可见图论中的

4、图与几何图、工程图是不一样的。图论中的图与几何图、工程图是不一样的。(v1)赵赵(v2)钱钱孙孙(v3)李李(v4)周周(v5)吴吴(v6)陈陈(v7)e2e1e3e4e5管管 理理 运运 筹筹 学学241 1图与网络的基本概念图与网络的基本概念a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈 如果我们把上面例子中的如果我们把上面例子中的“相互认识相互认识”关系改为关系改为“认识认识”的关系，那么只用两点之间的联线就很难刻画他们之间的关的关系，那么只用两点之间的联线就很难刻画他们之间的关

5、系了，这时我们引入一个带箭头的联线，称为弧。下图就是系了，这时我们引入一个带箭头的联线，称为弧。下图就是一个反映这七人一个反映这七人“认识认识”关系的图。相互认识用两条反向的关系的图。相互认识用两条反向的弧表示。弧表示。管管 理理 运运 筹筹 学学25 1 1图与网络的基本概念图与网络的基本概念 无向图：无向图：由点和边构成的图，记作由点和边构成的图，记作G=（V，E）。）。有向图：有向图：由点和弧构成的图，记作由点和弧构成的图，记作D=（V，A）。）。连通图连通图：对无向图对无向图G，若任何两个不同的点之间，至少存在一条链，则，若任何两个不同的点之间，至少存在一条链，则G为为连通图。连通图。

6、回路：回路：若路的第一个点和最后一个点相同，则该路为回路。若路的第一个点和最后一个点相同，则该路为回路。赋权图：赋权图：对一个无向图对一个无向图G的每一条边的每一条边(vi,vj)，相应地有一个数，相应地有一个数wij，则称图，则称图G为赋权图，为赋权图，wij称为边称为边(vi,vj)上的权。上的权。网络：网络：在赋权的有向图在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，中的每一条弧的赋权数称为弧的容量，D就就称为网络。称为网络。管管 理理 运运 筹筹 学学2

7、62 2最短路问题最短路问题最短路问题：对一个赋权的有向图最短路问题：对一个赋权的有向图D中的指定的两个点中的指定的两个点Vs和和Vt找到一条找到一条从从 Vs 到到 Vt 的路，使得这条路上所有弧的权数的总和最小，这条路被称的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从之为从Vs到到Vt的最短路。这条路上所有弧的权数的总和被称为从的最短路。这条路上所有弧的权数的总和被称为从Vs到到Vt的距离。的距离。解最短路的解最短路的Dijkstra算法算法(双标号法）双标号法）步骤：步骤：1.给出点给出点V1以标号以标号(0,s)2.找出已标号的点的集合找出已标号的点的集合I，没标号的点的集

8、合，没标号的点的集合J以及弧的集合以及弧的集合3.如果上述弧的集合是空集，则计算结束。如果如果上述弧的集合是空集，则计算结束。如果vt已标号（已标号（lt,kt），则），则 vs到到vt的距离为的距离为lt，而从，而从 vs到到vt的最短路径，则可以从的最短路径，则可以从kt 反向追踪到起点反向追踪到起点vs 而得到。如果而得到。如果vt 未标号，则可以断言不存在从未标号，则可以断言不存在从 vs到到vt的有向路。如果上的有向路。如果上述的弧的集合不是空集，则转下一步。述的弧的集合不是空集，则转下一步。4.对上述弧的集合中的每一条弧，计算对上述弧的集合中的每一条弧，计算 sij=li+cij。

9、在所有的。在所有的 sij中，找到其中，找到其值为最小的弧。不妨设此弧为（值为最小的弧。不妨设此弧为（Vc,Vd），则给此弧的终点以双标号），则给此弧的终点以双标号（scd,c）,返回步骤返回步骤2。(,)|,ijijv vvI vJ管管 理理 运运 筹筹 学学 最短路问题是网络分析中的一个基本问题，它不仅可以直接应用最短路问题是网络分析中的一个基本问题，它不仅可以直接应用于于解决生产实际的许多问题，若管道铺设、线路安排、厂区布局于于解决生产实际的许多问题，若管道铺设、线路安排、厂区布局等，而且经常被作为一个基本工具，用于解决其它的优化问题等，而且经常被作为一个基本工具，用于解决其它的优化问题

10、.定义 给定一个赋权有向图D=(V,A)，记D中每一条弧 上的权为为 。给定D中一个起点 和 终点，设P是D中从 到 的一条路.则定义路P的权是P中所有弧的权之和.记为 ，即 又若P*是D图中 到 的一条路，且满足 则称P*为从 到 的最短路。ija)(svtvsvtv)(PPvvijjiP),()(svtv)(min*)(PPtvsv管管 理理 运运 筹筹 学学28最短路问题最短路问题 网络：网络：规定起点、中间点和终点的赋权图；有向网络：有向网络：网络中每个边都是有向边；无向网络：无向网络：网络中每个边都是无向边；混合网络：混合网络：网络中既有有向边，又有无向边；网络最短路线问题：网络最短

11、路线问题：寻找网络中从起点 v1 到终点 vn 的最短路线。Min L()=lij 为从 v1 到 vn 的通路；lij 其中，lij为从 vi 到 vj 的一步距离。管管 理理 运运 筹筹 学学29 结合例题学习、掌握求最短路的狄克斯拉、海斯和福德三个方法：1、狄克斯拉方法：适用于满足所有权系数大于等于0（lij0）的网络最短路问题，能求出起点 v1 到所有其它点 vj 的最短距离；2、海斯方法：基本思想是在最短路线上任意两点间路线也是最短路线。利用 vi 到 vj 的一步距离求出 vi 到 vj 的两步距离再求出 vi 到 vj 的四步距离经有限次迭代可求出 vi 到 vj 的最短距离；3

12、、福德方法：适用于有负权系数，但无负回路的有向或无向网络的最短路问题，能求出起点 v1 到所有其它点 vj 的最短距离。管管 理理 运运 筹筹 学学302 2最短路问题最短路问题 例例1 求下图中求下图中v1到到v6的最短路的最短路解：采用解：采用Dijkstra算法，可解得最短路径为算法，可解得最短路径为v1 v3 v4 v6 各点的标号图如下：各点的标号图如下：v23527531512v1v6v5v3v4(3,1)v23527531512 V1（0,s)v5(8,4)v6(2,1)v3(3,3)v4管管 理理 运运 筹筹 学学31 网络最短路线问题：网络最短路线问题：寻找网络中从起点 v1

13、 到终点 vn 的最短路线。标注 vk(lk，k-1)定义：k=1时，l1=0，k-1=s，v1(0，s）min(lij)Min L()=lij 为从 v1 到 vn 的通路；lij 其中，lij为从 vi 到 vj 的一步距离。最短路问题最短路问题管管 理理 运运 筹筹 学学322 2最短路问题最短路问题 例例2 电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。地间公路的长度（单位：公里）

14、。解：这是一个求无向图的最短路的问题。可以把无向图的每一边解：这是一个求无向图的最短路的问题。可以把无向图的每一边（vi,vj）都用方向相反的两条弧（）都用方向相反的两条弧（vi,vj）和（）和（vj,vi）代替，就化为有向）代替，就化为有向图，即可用图，即可用Dijkstra算法来求解。也可直接在无向图中用算法来求解。也可直接在无向图中用Dijkstra算法算法来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。已标号的点到未标号的点的边的集合即可。V1（甲地）（甲地）151762443

15、1065v2V7（乙地）（乙地）v3v4v5v6管管 理理 运运 筹筹 学学332 2最短路问题最短路问题例例2最终解得：最终解得：最短路径最短路径v1 v3 v5 v6 v7，每点的标号见下图，每点的标号见下图（0,s）V1（甲地）（甲地）1517624431065(13,3)v2 (22,6)V7（乙地）（乙地）V5(14,3)V6(16,5)V3(10,1)V4(18,5)管管 理理 运运 筹筹 学学例设备更新问题设备更新问题某工厂使用一台设备，每年年初工厂要作出决定：继续使用，购某工厂使用一台设备，每年年初工厂要作出决定：继续使用，购买新的？如果继续使用旧的，要负维修费；若要购买一套新

16、的，要买新的？如果继续使用旧的，要负维修费；若要购买一套新的，要负购买费。试确定一个负购买费。试确定一个5年计划，使总支出最小。若已知设备在各年计划，使总支出最小。若已知设备在各年的购买费，及不同机器役龄时的残值与维修费。年的购买费，及不同机器役龄时的残值与维修费。项目第1年第2年第3年第4年第5年购买费1111121213机器役龄0-11-22-33-44-5维修费5681118残值43210解：解：把这个问题化为最短路问题。把这个问题化为最短路问题。设设bi 表示设备在第表示设备在第i 年年初的购买费年年初的购买费,ci 表示设备使用表示设备使用i 年后的维修费年后的维修费,V=v1,v2,v6,点点vi表示第表示第i 年年初购进一台新设备年年初购进一台新设备,虚设一个点虚设一个点v6表示第表示第5 5年年年底年底.E=vivj|1ij6.2 2最短路问题最短路问题管管 理理 运运 筹筹 学学352 2最短路问题最短路问题例的解：例的解：将问题转化为最短路问题，如下图：将问题转化为最短路问题，如下图：用用vi表示表示“第第i年年初购进一台新设备年年初购进一台新设备”,弧弧 （vi,