《《ch网络模型》ppt课件》由会员分享，可在线阅读，更多相关《《ch网络模型》ppt课件（81页珍藏版）》请在金锄头文库上搜索。
1、运 筹 学 Operations Research,Chapter 6 网络模型 Network Modeling,6.1 最小(支撑)树问题 Minimal (Spanning)Tree Problem 6.2 最短路问题 Shortest Path Problem 6.3 最大流问题 Maximal Flow Problem 6.4 旅行售货员与中国邮路问题 Traveling Salesman and China Carrier Problem,2019年1月17日星期四,5,v1,v2,v3,v4,v5,v6,8,4,3,7,5,2,6,1,8,图61,运筹学中研究的图具有下列特征：
2、（1）用点表示研究对象，用边（有方向或无方向）表示对象之间某种关系。 （2）强调点与点之间的关联关系，不讲究图的比例大小与形状。 （3）每条边上都赋有一个权，其图称为赋权图。实际中权可以代表两点之间的距离、费用、利润、时间、容量等不同的含义。 （4）建立一个网络模型，求最大值或最小值。,2019年1月17日星期四,边用vi,vj表示或简记为i，j，集合记为,如图61所示，点集合记为,边上的数字称为权，记为wvi,vj、wi，j或wij，集合记为,连通的赋权图称为网络图，记为 GV，E，W,5,v1,v2,v3,v4,v5,v6,8,4,3,7,5,2,6,1,8,图61,6.1 最小(支撑)树
3、问题 Minimal (Spanning)Tree Problem,2019年1月17日星期四,6.1.1树的概念,一个无圈并且连通的无向图称为树图或简称树(Tree)。组织机构、家谱、学科分支、因特网络、通讯网络及高压线路网络等都能表达成一个树图 。,可以证明： （1）一棵树的边数等于点数减1； （2）在树中任意两个点之间添加一条边就形成圈； （3）在树中去掉任意一条边图就变为不连通。,在一个连通图G中，取部分边连接G的所有点组成的树称为G的部分树或支撑树(Spanning Tree )。图62是图61的部分树。,6.1 最小树问题 Minimal tree problem,2019年1月1
4、7日星期四,6.1.2 最小部分树,将网络图G边上的权看作两点间的长度（距离、费用、时间），定义G的部分树T的长度等于T中每条边的长度之和，记为C(T)。 G的所有部分树中长度最小的部分树称为最小部分树，或简称为最小树。,最小部分树可以直接用作图的方法求解，常用的有破圈法和加边法。 破圈法：任取一圈，去掉圈中最长边，直到无圈。,6.1 最小树问题 Minimal tree problem,2019年1月17日星期四,5,v1,v2,v3,v4,v5,v6,8,4,3,7,5,2,6,1,8,图61,【例6-1】用破圈法求图61的最小树。,图64,图64就是图61的最小部分树，最小树长为 C(T
5、)=4+3+5+2+1=15。 当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同,6.1 最小树问题 Minimal tree problem,2019年1月17日星期四,加边法：取图G的n个孤立点v1，v2， vn作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有n1条边）,v1,v2,v3,v4,v5,v6,图65,在图65中，如果添加边v1, v2就形成圈v1, v2, v4，这时就应避开添加边v1, v2，添加下一条最短边v3, v6。破圈法和加边法得到树的形状可能不一样，但最小树的长度相等,Min C(
6、T)=15,6.1 最小树问题 Minimal tree problem,【例6-2】用加边法求图61的最小树,图61,2019年1月17日星期四,下一节：最短路问题,1.树、支撑树、最小支撑树的概念 2.掌握求最小树的方法： （1）破圈法 （2）加边法,作业：教材习题 6.1，6.4，6.5,6.1 最小树问题 Minimal tree problem,6.2 最短路问题 Shortest Path Problem,2019年1月17日星期四,最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等问题，还有些如设备更新、投资等问题也可以归结为求最短路问题,求最短路有两种算法： 一是求从某一
7、点至其它各点之间最短离的狄克斯屈拉(Dijkstra)算法 另一种是求网络图上任意两点之间最短路的Floyd(弗洛伊德)矩阵算法。,最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路,6.2.1最短路问题的网络模型,6.2 最短路问题 Shortest Path Problem,2019年1月17日星期四,6,10,12,3,2,14,6,7,5,8,11,16,5,图66,9,【例6-3】图66中的权cij表示vi到vj的距离（费用、时间），从v1修一条公路或架设一条高压线到v7，如何选择一条路线使距离最短，建立该问题的网络数学模型。,6.2 最短路问题 Short
8、est Path Problem,2019年1月17日星期四,【解】 设xij为选择弧(i，j)的状态变量，选择弧(i，j)时xij1，不选择弧(i，j)时xij0，得到最短路问题的网络模型：,6.2 最短路问题 Shortest Path Problem,2019年1月17日星期四,6.2.2有向图的狄克斯屈拉(Dijkstra)标号算法,点标号：b(j) 起点vs到点vj的最短路长；,边标号：k(i，j)=b(i)+cij，,步骤：(1)令起点的标号；b(s)0。,先求有向图的最短路，设网络图的起点是vs ,终点是vt ,以vi为起点vj为终点的弧记为（i，j）,距离为cij,(2)找出所
9、有vi已标号vj未标号的弧集合 B=(i，j)，如果这样的弧不存在或vt已标号则计算结束；,(3)计算集合B中弧k(i，j)=b(i)+cij的标号,(4)选一个点标号 返回到第(2)步。,6.2 最短路问题 Shortest Path Problem,2019年1月17日星期四,6,10,12,3,2,14,6,7,5,8,11,16,5,图66,9,0,6,10,12,9,20,9,18,6,16,12,17,16,24,32,18,29,29,【例6-4】用Dijkstra算法求图66 所示v1到v7的最短路及最短路长,v1 到v7的最短路为：p17=v1, v2, v3, v5, v7
10、，最短路长为L17=29,6.2 最短路问题 Shortest Path Problem,14,2019年1月17日星期四,从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj 。,6.2.3 无向图最短路的求法,无向图最短路的求法只将上述步骤（2）改动一下即可。,点标号：b(i) 起点vs到点vj的最短路长；,边标号：k(i，j)=b(i)+cij，,步骤：(1)令起点的标号；b(s)0。,(3)计算集合B中边标号：ki，j=b(i)+cij,(4)选一个点标号: 返回到第(2)步
11、。,(2)找出所有一端vi已标号另一端vj未标号的边集合 B=i，j如果这样的边不存在或vt已标号则计算结束；,6.2 最短路问题 Shortest Path Problem,2019年1月17日星期四,【例6-5】求图6-10所示v1到各点的最短路及最短距离,0,4,5,2,2,3,10,3,9,6,12,6,4,11,6,6,18,8,12,24,8,24,18,所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。,图6-10,6.2 最短路问题 Shortest Path Problem,2019年1月17日星期四,6.2.4 最短路的Floyd算法,Floyd算法
12、基本步骤 :,(1)写出vi一步到达vj 的距离矩阵 ，L1也是一步到达的最短距离矩阵。如果vi 与vj 之间没有边关联，则令cij=+,(2)计算二步最短距离矩阵。设vi 到vj 经过一个中间点vr 两步到达vj，则vi到vj的最短距离为,最短距离矩阵记为,(3)计算k步最短距离矩阵。设 vi经过中间点vr 到达vj，vi 经过k1步到达点vr 的最短距离为 ，vr 经过k1步到达点vj 的最短距离为 ，则 vi 经k步 到达vj 的最短距离为,(6-1),6.2 最短路问题 Shortest Path Problem,2019年1月17日星期四,最短距离矩阵记为,(4)比较矩阵Lk与Lk1
13、，当LkLk1时得到任意两点间的最短距离矩阵Lk。 设图的点数为n并且cij0，迭代次数k由式(6-3) 估计得到。,(6-2),(6-3),6.2 最短路问题 Shortest Path Problem,2019年1月17日星期四,【例6-6】图6-14是一张8个城市的铁路交通图，铁路部门要制作一张两两城市间的距离表。这个问题实际就是求任意两点间的最短路问题。,【解】 (1)依据图6-14,写出任意两点间一步到达距离表L1。见表6-1所示。本例n=8， ，因此计算到L3,图6-14,6.2 最短路问题 Shortest Path Problem,2019年1月17日星期四,表6-1 最短距离
14、表 L1,6.2 最短路问题 Shortest Path Problem,2019年1月17日星期四,表6-2 最短距离表L2,计算说明：L(2)ij等于表6-1中第i行与第j列对应元素相加取最小值。如,6.2 最短路问题 Shortest Path Problem,2019年1月17日星期四,表6-3计算示例: 等于表6-2中第i行与第j列对应元素相加取最小值。例如，v3经过三步（最多三个中间点4条边）到达v6的最短距离是,表6-3 最短距离表L3,6.2 最短路问题 Shortest Path Problem,2019年1月17日星期四,【例6-7】求图615中任意两点间的最短距离。 【解
15、】图615是一个混合图，有3条边的权是负数,有两条边无方向。依据图615,写出任意两点间一步到达距离表L1。表中第一列的点表示弧的起点，第一行的点表示弧的终点，无方向的边表明可以互达，见表6-4所示。计算过程见表6-56-7。,4,4,5,7,4,3,2,7,10,2,8,图615,1,5,6.2 最短路问题 Shortest Path Problem,2019年1月17日星期四,表6-4一步到达距离表L1,6.2 最短路问题 Shortest Path Problem,2019年1月17日星期四,表6-7 最短距离表L4,经计算L4L5，L4是最优表。表6-7不是对称表，vi到vj与vj到vi的最短距离不一定相等。对于有负权图情形，公式(6-3)失效。,6.2 最短路问题 Shortest Path Problem,2019年1月17日星期四,6.2.4 最短路应用举例,6.2 最短路问题 Shortest Path Problem,【例6-8】设备更新问题。企业在使用某设备时，每年年初可购置新设备，也可以使用一年或几年后卖掉重新购置新设备。已知4年年初购置新设备的价格分别为2.5、2.6、2
