《运筹学6网络模型》由会员分享，可在线阅读，更多相关《运筹学6网络模型（105页珍藏版）》请在金锄头文库上搜索。
1、西安理工大学 经济与管理学院 熊国强,运筹学 Operations Research,运 筹 学 Operations Research,Chapter 6 Network Modeling,1. 图与网络的基本知识 最小树问题 3. 最短路问题 最大流问题,C,B,A,引例：哥尼斯堡七桥问题,18世纪游戏: 你能从A、B、C或D任意一点出发走遍7座桥并且每座桥只走一次最后回到原出发点吗？,D,数学家E.Euler证明(1736年）：,十八世纪东普鲁士哥尼斯堡城（今俄罗斯加里宁格勒）的普莱格尔河，它有两个支流，在城市中心汇成大河，中间是岛区，河上有7座桥，将河中的两个岛和河岸连结，如下图所示。
2、由于岛上有古老的哥尼斯堡大学，有教堂，还有哲学家康德的墓地和塑像，因此城中的居民，尤其是大学生们经常沿河过桥散步。,中国邮路问题：管梅谷（1962年）提出 一个邮递员，负责某一地区的信件投递。他每天要从邮局出发，走遍该地区所有街道再返回邮局，问应如何安排送信的路线可以使所走的总路程最短？,我们在实际生活、生产和科研活动中经常看到许多的网络，如互联网、通信网、公路网、管道网、销售网等。对网络进行研究是希望解决其中的一些优化问题，网络最优化能为人们管理和控制这些网络系统提供一套有效的方法。,例 某家电配送中心需要为多个销售点送货，配送中心与销售点以及销售点之间的相对位置和运输情况可以用图来表示。其
3、中，点v1，v2，v7代表销售点，边表示运输路线。若已知每条路线行走所需的时间，请帮助配送中心管理人员设计一条送货路线，使送货车辆用最短的时间送完货物，并回到配送中心。,基本的网络最优化问题有4个，即最小树问题，最短路问题、最大流问题、最小费用最大流问题。这些问题的数学模型实际上大都是线性规划问题，但使用线性规划的单纯形法去求解，过程非常繁琐，本章介绍的网络分析方法能有效的解决这些问题。,图G可 定义为点和边的集合，记作,注意上面定义的图区别于几何学中的图。在几何学中，图中点的位置、线的长度和斜率等都十分重要，而这里只关心图中有多少点以及哪些点之间有线相连。如果给图中的边赋以具体的含义，如距离
4、、费用、容量等，记作w ，把这样的图称为网络图。图和网络分析的方法已广泛应用于物理、化学、控制论、信息论、计算机科学和经济管理等各个领域。,6.1 图与网络的基本知识,式中是点的集合，是边的集合，W是边上权的集合。,如图6-1,定义1 端点，关联边 若边e表示为e=vi,vj,称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。,例如图61：,v2和v4是边e6的端点，而边e6是点v2、v4的关联边。,图6-1,e2可记作：,几个定义：,定义2 有向图： 如果图的每条边都有一个方向则称为有向图,定义3 混合图： 如何图G中部分边有方向则称为混合图,有向图,定义4 网络（赋权图）：,设图
5、G（V，E），对G的每一条边(vi,vj)相应的有一条数w (vi,vj) (或记为wij)，wij称为边(vi,vj)的权,赋有权的图G称为网络（赋权图）。,这里的权数可以是时间、费用、距离等，视不同背景代表不同的含义。,赋权图,定义5 子图、支撑子图（生成子图）,图G1=V1、E1和图G2=V2，E2如果 称G1是G2的一个子图。 若有 则称 G1是G2的一个支撑子图（部分图）。 图6-2（a）是图 6-1的一个子图，图6-2（b）是图 6-1的支撑子图，注意支撑子图也是子图,子图不一定是支撑子图。,图6-1,定义6 链、回路（圈） 无向图中有些点和边的交替序列 对任意vi,t1 和vit
6、(2tk)均相邻，称从v0到vk的链。,图61中， 1=v5,e8,v3,e3,v1,e2,v2,e4,v3,e7,v4是一条链。,当v0与vk重合时称为回路（或圈）。,3=v4,e7,v3,e3,v1,e2,v2,e6,v4,是一条回路。,定义7 连通图,若在一个图中，如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称该图是不连通的。图6-1是连通图。,图6-1,欧拉回路,定义8 连通图G中，若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。 具有欧拉回路的图称为欧拉图。,哥尼斯堡七桥问题：寻找一条欧拉回路,定理 ： 无向连通图G是欧拉图，当且仅当G中无奇点。,七桥问题
7、： d(A)=3, d(B)=3, d(C)=5, d(D)=3 有四个奇点，故不是欧拉图,6.2 最小树问题,树的概念,树是图论中结构最简单但又十分重要的图，在许多领域都有应用。 如：运动员抽签结构图,定义： 树、支撑树,无圈的连通图称为树； 若G1是G2的一个支撑子图并且是一棵树，则称G1是G2的一棵支撑树。,图63(a)是一棵树，图63(b)是图61的一棵支撑树。,v1,v1,图61,图63(a),图63(b),定理： 图G=（V，E）有支撑树的充分必要条件为G是连通图。,支撑树的寻求方法,在图中，每步选出一条边使它与已选边不构成圈，直到选够n-1 条边为止。,（）深探法 步骤：任取一点
8、v，给v以标号； 若某点u已得标号i，检查其中一个端点w是否已标号； 若端点w未标号，则给w以标号i+1;重复 若端点均已标号，则退到标号i1的点，重复。,10,11,12,13,（）深探法,支撑树：,(2) 广探法,任取一点v，给v以标号； 检查其所有端点wi是否已标号；若端点w未标号，则给所有wi以标号i+1; 对标号i+1的点重复。,最小支撑树,定义：设GV,E是一个连通图，每一条边eiE具有长度C(ei) 0, G的任意支撑树T各条边的长度之和称为树T的长度，记为C（T）。长度最小的支撑树称为最小树。,最小树的应用： 电信网络（计算机网络、电话专用线网络、有线电视网络等等）的设计 低负
9、荷运输网络的设计，使得网络中提供链接的部分（如铁路、公路等 等）的总成本最小 高压输电线路网络的设计 电器设备线路网络（如数字计算机系统）的设计，使得线路总长度最短 连接多个场所的管道网络设计,求最小树是在一个无向连通图G中求一棵最小支撑树。,避圈法（加边法）：去掉G中所有边，得到n个孤立点；然后加边；,加边的原则：从最短边开始添加，加边的过程中不能形成圈，直到连通（n1条边）。,v1,v2,v3,v4,v5,v6,4,3,5,2,1,Min C(T)=15,求最小树的方法：避圈法和破圈法,破圈法：任取一圈，去掉圈中最长边，直到无圈。,v1,v2,v3,v4,v5,v6,4,3,5,2,1,得
10、到最小树：,Min C(T)=15,6.3最短路问题,有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。,求最短路有两种算法，一是求从某一点至其它各点之间最短离的狄克斯拉(Dijkstra)算法；另一种是求网络图上任意两点之间最短的矩阵算法。,最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路 .,渡河问题,一老汉带了一只狼、一只羊、一棵白菜想要从左岸过河到右岸，河上只有一条独木舟，每次除了人以外，只能带一样东西。 另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安
11、排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。,渡河问题,设：M人 W狼 S羊 V白菜,分析：河左岸允许出现的情况有以下10种情况：人狼羊菜、人狼羊、人狼菜、人羊菜、人羊、狼菜、狼、菜、羊及空（各物品已安全渡河），我们把这10种状态视为10个点，若一种状态通过一次摆渡后变为另一种状态，则在两种状态（点）之间画一直线，得到下图 。 这样摆渡问题就转化成在图中找出以“人狼羊菜”为起点，以“空”为终点的 最短路。,【例】求下图v1到v7的最短路长及最短路线(有向图的最短路),6.3.1 有向图最短路的Dijkstra算法,狄克斯屈拉(Dijkstr
12、a)标号算法,点标号：b(j) 起点vs到点vj的最短路长；,弧标号：k(i，j)=b(i)+dij，,求有向图的最短路。设网络图的起点是vs,终点是vt ,以vi为起点vj为终点的弧记为（i，j）,距离为dij,弧:有向边,步骤：1.令起点的标号；b(s)0。,2.找出所有起点vi已标号但终点vj未标号的弧集合 B=(i，j ),如果这样的弧不存在或vt已标号则计算结束；,3.计算集合B中各个弧k(i，j)=b(i)+dij的标号,4.选一个点标号 返回到第2步。,【例】求下图v1到v7的最短路长及最短路线,0,8,6,2,2,5,4,4,11,14,7,5,10,7,12,11,v7已标号
13、，计算结束。从v1到v7的最短路长是 11,最短路线是：v1 v4 v6 v7,【例】求下图v1到各点的最短路及最短距离,6.3.2 无向图最短路的Dijkstra算法,无向图最短路的求法只将上述步骤2改动一下即可。,6.3.2 无向图最短路的Dijkstra算法,【例】求下图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到该点的最短距离，最短路线就是红色的链。,Floyd算法基本步骤 :,(1)写出vi一步到达vj 的距离矩阵 ，L1也是一步到达的最短距离矩阵。如果v
14、i 与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.3.3 最短路的Floyd算法,最短距离矩阵记为,(4)比较矩阵Lk与Lk1，当LkLk1时得到任意两点间的最短距离矩阵Lk。 设图的点数为n并且cij0，迭代次数k由式(6.3) 估计得到。,(6.2),(6.3), 6.
15、3.3 最短路的Floyd算法,【例】下图是一张8个城市的铁路交通图，铁路部门要制作一张两两城市间的距离表。这个问题实际就是求任意两点间的最短路问题。,【解】 (1)依据图, 写出任意两点间一步到达距离表L1。见表6.1所示。,图,表6-1 最短距离表 L1,本例n=8， ，因此计算到 L3。,表6-2 最短距离表L2,计算说明：L(2)ij等于表6-1中第i行与第j列对应元素相加取最小值。如,表6-3计算示例: 等于表6-2中第i行与第j列对应元素相加取最小值。例如，v3经过三步（最多三个中间点4条边）到达v6的最短距离是,表6-3 最短距离表L3,【书 P135 例6.9】服务网点设置问题。以下图为例，现提出这样一个问题，在交通网络中建立一个快速反应中心，应选择哪一个城市最好。类似地，在一个网络中设置一所学校、医院、消防站、购物中心，还有厂址选择、总部选址、公司销售中心选址等问题都属于最佳服务网点设置问题。,6.3.4 最短路应用举例,【解】 对于不同的问题，寻求最佳服务点有不同的标准。像上图只有两点间的距离，可以采用“使最大服务距离达到最小”为标准，计算步骤如下。 第一步：利用Floyd算法求出任意两点之间的最短距离表（表63）。 第二步：计算最短距离表中每行的最大距离的最小值，即,
