交通运筹学教学课件作者张文会第7章节网络模型课件

《交通运筹学教学课件作者张文会第7章节网络模型课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1第7章网络模型2主要内容第一节最小树问题第二节最短路问题第三节最大流问题第四节旅行售货员与中国邮路问题第五节网络模型在道路交通工程中的应用3许多研究的对象往往可以用一个图表示，研究的目的归结为图的极值问题。本章继续讨论其他几种图的极值问题的网络模型。运筹学中研究的图具有下列特征：（1）用点表示研究对象，用边（有方向或无方向）表示对象之间某种关系；（2）强调点与点之间的关联关系，不讲究图的比例大小与形状；（3）每条边上都赋有一个权，其图称为赋权图。实际中权可以代表两点之间的距离、费用、利润、时间、容量等不同的含义；（4）建立一

2、个网络模型，求最大值或最小值。下面以实例来说明图在道路交通中的应用。图7-1（a）表示某地区的公路交通网，A、B、C、D、E表示五个城镇，A、B、C、D、E之间的连线表示两城镇间的公路，我们研究的问题就是“两城镇间有无公路相通”这一特定关系，那么就可以用图7-1（b）点的网状图来代替图7-1（a）的公路交通图67.1最小树问题7.1.1树的概念一个无圈并且连通的无向图称为树图或简称树（Tree）如图7-3是一个管道铺设方案路线图，其特征是任意两点之间都有惟一的一条链（路）连通起来，是一棵树。树具有以下性质：在树中任意两点之间添

3、加一条边就形成圈。在树中去掉任意一条边图就变成不连通。一棵树的边数等于点数减1。树中任意两点之间都有惟一的一条链连通起来。87.1.2最小部分树将网络图边上的权看做两点间的长度（距离、费用、时间），定义G的部分树T的长度等于T中每条边的长度之和，记为C（T）。G的所有部分树中长度最小的部分树称为最小部分树，或简称为最小树。如果一个连通图G本身不是一棵树，那么G的部分树不惟一。最小树问题就是在所有部分树中寻找树长最短的部分树。最小部分树可以直接用作图的方法求解，常用的有破圈法和加边法。破圈法任取一圈，去掉圈中最长边，直到无圈。加

4、边法从最短边开始往支撑图中添加，见圈回避，直到连通。7.1.2最小部分树在一个连通图中，取部分边连接的所有点组成的树称为的部分树或支撑数（SpanningTree）。最小部分树可以直接用作图的方法求解，常用的有避圈法和破圈法。破圈法：取图中任一一个圈，从圈中去掉一条权最大的边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条）。在余下的图中，重复这个步骤，直到得到一个不含圈的图为止，这时的图便是最小树。7.2最短路问题所谓最短路问题,就是在一个网络中,相邻节点间的线路长度是已知的,要从某一起点到某一终点之间,找出一条

5、路长最短的通路。7.2.1有向图的Dijkstra算法147.2最短路问题7.2.1有向图的Dijkstra算法15到此，所有节点均标上了标号，算法停止。可见，从城市1到城市7的最小运费为29个单位。用Dijkstra算法求解最短路问题要注意一下问题：Dijkstra算法的条件是弧长非负，问题求最小值。Dijkstra算法求得的最短路线可能不惟一，但最短路长相等。Dijkstra算法可以求任意两点之间的最短路（最短路存在），只要将两个点看做路线的起点和终点，然后进行标号。197.2.2无向图的Dijkstra算法如果vi与vj

6、之间存在一条无方向的边相关联，说明vi与vj两点之间可以互达。当与之间至少有两条边相关联时，留下一条最短边，去掉其他关联边。对于无向图最短路的求解Dijkstra算法同样有效。【例7.4】要在八个城市间建立如图7-9所示的公路交通网。已知城市与城市见的路可以互达，网络边上的数据表示城市间公路的距离，用Dijkstra算法求解城市1到其它城市间公路的最小距离。23456784526139382616121871解227.2.4最短路的Floyd算法【例7.5】图7-11是一张8个城市的铁路交通图，铁路部门要制作一张两两城市间的距

7、离表。这个问题实际就是求任意两点间的最短路问题。表7-3就是最优表，即任意两点间的最短距离。取表中下三角得到8个城市间的铁路交通距离表。【例7.6】求图7-12中任意两点间的最短距离。解图7-12是一个混合图，有3条边的权是负数，有两条边无方向。依据图7-12，写出任意两点间一步到达距离表。表中第一列的点表示弧的起点，第一行的点表示弧的终点，无方向的边表明可以互达，如表7-4所示。计算过程见表7-5至表7-7。317.3最大流问题7.3.1基本概念7.3最大流问题7.3.1基本概念可行流与最大流可行流应满足以下条件：综上，网络

8、最大流问题就是在满足上述条件的基础上寻找一个流，使其流量达到最大。7.3最大流问题7.3.1基本概念增广链7.3最大流问题7.3.1基本概念割集与割量7.3.2Ford-Fulkerson标号算法【定理7.1】可行流是最大流的充分必要条件是不存在发点到收点的增广链。Ford-