运筹学教材(第五章-图与网络分析)课件.ppt

《运筹学教材(第五章-图与网络分析)课件.ppt》由会员分享，可在线阅读，更多相关《运筹学教材(第五章-图与网络分析)课件.ppt（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学（普通高等教育运筹学（普通高等教育“十二五十二五”经经济与管理类专业核心课程规划教材）济与管理类专业核心课程规划教材）n主主编：n出版社：出版社：n出版出版时间：2013-12-01运 筹 学运 筹 学n 绪论n 第1章 线性规划n 第2章 线性规划的对偶理论n 第3章 特殊线性规划n 第4章 动态规划n 第第5 5章章 图与网络分析图与网络分析n 第6章 排队论n 第7章 库存论n 第8章 决策论n 第9章 对策论运 筹 学第5章 图与网络分析 n5.1 图的基本概念 n5.2 最小树问题 n5.3 最短路问题n5.4 最大流问题n5.5 最小费用最大流问题 n5.6 网络计划技术 熊

2、国强制作熊国强制作ACBDCBA引例：哥尼斯堡七桥问题引例：哥尼斯堡七桥问题18世纪游戏世纪游戏:你能从你能从A、B、C或或D任意一点出发任意一点出发走遍走遍7座桥并且每座桥只走一次最座桥并且每座桥只走一次最后回到原出发点吗？后回到原出发点吗？D瑞士数学家E.Euler证明(1736年）：5.1 图的基本概念 我们在实际生活、生产和科研活动中经常看到许多的网络，如我们在实际生活、生产和科研活动中经常看到许多的网络，如互联网、通信网、公路网、管道网、销售网等。对网络进行研互联网、通信网、公路网、管道网、销售网等。对网络进行研究是希望解决其中的一些优化问题，网络最优化能为人们管理究是希望解决其中的

3、一些优化问题，网络最优化能为人们管理和控制这些网络系统提供一套有效的方法。和控制这些网络系统提供一套有效的方法。ACBD5.1 图的基本概念 例例 某家电配送中心需要为多个销售点送货，配送中心与销售点以及销售点之间的相对位置和运输情况可以用图来表示。其中，点v1，v2，v7代表销售点，边表示运输路线。若已知每条路线行走所需的时间，请帮助配送中心管理人员设计一条送货路线，使送货车辆用最短的时间送完货物，并回到配送中心。v9v7v8v6v4v5v3配送中心v2v15.1 图的基本概念 基本的网络最优化问题有4个，即最小树问题，最短路问题、最大流问题、最小费用最大流问题。这些问题的数学模型实际上大都

4、是线性规划问题，但使用线性规划的单纯形法去求解，过程非常繁琐，本章介绍的网络分析方法能有效的解决这些问题。5.1 图的基本概念 如图5-1定义定义1 端点，关联边端点，关联边 若边e表示为e=vi,vj,称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。例如图5-1：v2和v4是边e5的端点，而边e5是点v2、v4的关联边。图5-1e2可记作：几个定义：几个定义：5.1 图的基本概念 v1 v4 v3 v2e1e3e4e5e7e6e2定义定义2 有向图：有向图：如果图的每条边都有一个方向则称为有向图定义定义3 混合图：混合图：如何图G中部分边有方向则称为混合图有向图5.1 图的基本概

5、念定义定义5 子图、子图、支撑子图（生成子图（生成子图）图G1=V1、E1和图G2=V2，E2如果 称G1是G2的一个子图。图5-2（a）是图 5-1的一个子图。图52(a)5.1 图的基本概念图5-1 v1 v4 v3 v2e1e2e3e4e5 v5e6e7 v1 v4 v3 v2 v5 定义6 链、回路（圈）链、回路（圈）无向无向图中有些点和边的交替序列对任意vi,t1 和vit(2tk)均相邻，称从v0到vk的链。图5-1中，1=v5,e6,v3,e2,v2,e4,v4,e5,v1是一条链。当v0与vk重合时称为回路（或圈）。3=v1,e1,v2,e4,v4,e5,v1是一条回路。5.1

6、 图的基本概念图5-1 v1 v4 v3 v2e1e2e3e4e5 v5e6e7定义定义7 连通图连通图若在一个图中，如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称该图是不连通的。图5-1是连通图。5.1 图的基本概念图5-1 v1 v4 v3 v2e1e2e3e4e5 v5e6e7ACBD哥尼斯堡七桥问题：寻找一条欧拉回路CBAD5.1 图的基本概念定理：无向连通图G是欧拉图，当且仅当G中无奇点。ACBDv1v2v3七桥问题：d(A)=3,d(B)=3,d(C)=5,d(D)=3有四个奇点，故不是欧拉图5.1 图的基本概念树的概念 树是图论中结构最简单但又十分重要的图，在许多领

7、域都有应用。如：运动员抽签结构图5.2最小树问题定义：定义：树、支撑树树、支撑树无圈的连通图称为树；若G1是G2的一个支撑子图并且是一棵树，则称G1是G2的一棵支撑树。图53(a)是一棵树，图53(a)是图51的一棵支撑树。图图53(a)5.2最小树问题图5-1 v1 v4 v3 v2e1e2e3e4e5 v5e6e7 v1 v4 v3 v2 v5定理：定理：图图G=G=（V V，E E）有）有支撑支撑树的充分必要条件为树的充分必要条件为G G是连通图。是连通图。v3e7e4e8e5e6e1e2e3v1v2v4v55.2最小树问题 v1 v4 v3 v2e1e2e3e4e5 v5e6e7（）深

8、探法（）深探法支撑支撑树：树：5.2最小树问题(2)广探法广探法任取一点任取一点v，给，给v以标号；以标号；检查其所有端点检查其所有端点wi是否已标号；是否已标号；若端点若端点w未标号，则给所有未标号，则给所有wi以标号以标号i+1;对标号对标号i+1的点重复的点重复。0111221222333435.2最小树问题最小最小支撑支撑树树定义：设定义：设GV,E是一个连通图，每一条边是一个连通图，每一条边eiE具有长度具有长度C(ei)0,G的任意支撑树的任意支撑树T各条边的长度之和称为树各条边的长度之和称为树T的长度，的长度，记为记为C（T）。长度最小的支撑树称为最小树。）。长度最小的支撑树称为

9、最小树。23641222233135.2最小树问题避圈法避圈法（加边法）加边法）：去掉G中所有边，得到n个孤立点；然后加边；加边的原则：从最短边开始添加，加边的过程中不能形成圈，直到连通（n1条边）。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521Min C(T)=15求最小树的方法：避圈法和破圈法破圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。v1v2v3v4v5v6435215v1v2v3v4v5v68437526185.2最小树问题有有些些问问题题，如如选选址址、管管道道铺铺设设时时的的选选线线、设设备备更更新新、投投资资、某某些些整整数数规规划划和和动动

10、态态规规划划的的问问题题，也也可可以以归归结结为为求求最最短短路路的的问问题题。因因此此这这类问题在生产实际中得到广泛应用。类问题在生产实际中得到广泛应用。求求最最短短路路有有两两种种算算法法，一一是是求求从从某某一一点点至至其其它它各各点点之之间间最最短短离离的的狄狄克克斯斯拉拉(Dijkstra)算算法法；另另一一种种是是求求网网络络图图上上任任意意两两点点之之间间最最短短的的动动态规划算法。态规划算法。最短路问题，就是从给定的网络图中找出一点到各点或任意两点之最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路间距离最短的一条路.5.3最短路问题 渡河问题渡河问题

11、 一老汉带了一只狼、一只羊、一棵白菜想要从左岸过河到右岸，一老汉带了一只狼、一只羊、一棵白菜想要从左岸过河到右岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。个问题就可以用求最短路方法解决。5.3最短路问题设：M人 W狼 S羊 V白菜分析：河左岸允许出现的情况有以

12、下分析：河左岸允许出现的情况有以下10种情况：人狼羊菜、人狼羊、人狼菜、种情况：人狼羊菜、人狼羊、人狼菜、人羊菜、人羊、狼菜、狼、菜、羊及空（各物品已安全渡河），我们把这人羊菜、人羊、狼菜、狼、菜、羊及空（各物品已安全渡河），我们把这10种状态视为种状态视为10个点，若一种状态通过一次摆渡后变为另一种状态，则在两种个点，若一种状态通过一次摆渡后变为另一种状态，则在两种状态（点）之间画一直线，得到下图状态（点）之间画一直线，得到下图。这样摆渡问题就转化成在图中找出以这样摆渡问题就转化成在图中找出以“人狼羊菜人狼羊菜”为起点，以为起点，以“空空”为终为终点的点的 最短路。最短路。5.3最短路问题【

13、例例】某公司拟将一批货物从v1运到v7，这两点间的交通网络图如图所示，每条边上的数字表示这条路的长度。试问：从v1到v7的各条路线中，哪一条的总长度最短.5.3.1 最短路的Dijkstra算法有向图最短路的有向图最短路的Dijkstra算法算法v3v65v1v2v5v4v737662318354l有向图最短路的有向图最短路的Dijkstra算法算法点标号：b(j)起点vs到点vj的最短路长；弧标号：k(i，j)=b(i)+dij，先求有向图的最短路。设网络图的起点是先求有向图的最短路。设网络图的起点是vs,终点是终点是vt ,以以vi为起点为起点vj为为终点的弧记为（终点的弧记为（i，j）,

14、距离为距离为dij5.3.1 最短路的Dijkstra算法v1v2v5v4v737662318354步骤：1.令起点的标号；b(s)0。2.找出所有起点vi已标号但终点vj未标号的弧集合 B=(i，j),如果这样的弧不存在或vt已标号则计算结束；3.计算集合B中各个弧k(i，j)=b(i)+dij的标号4.选一个点标号 返回到第2步。5.3.1 最短路的Dijkstra算法v1v2v5v4v737662318354【例例】某公司拟将一批货物从v1运到v7，这两点间的交通网络图如图所示，每条边上的数字表示这条路的长度。试问：从v1到v7的各条路线中，哪一条的总长度最短.5.3.1 最短路的Dij

15、kstra算法有向图最短路的有向图最短路的Dijkstra算法算法v3v65v1v2v5v4v737662318354063359105108816991312101513从v1到v7的最短路是 v1,v2,v3,v4,v6,v7，其最短路权值为13。【例例】求下图v1到v7的最短路长及最短路线86252353421057086225441114751071211v7已标号，计算结束。从v1到v7的最短路长是 11最短路线是：v1 v4 v6 v7【例例】求下图v1到各点的最短路及最短距离452617839326121618无向图最短路的无向图最短路的Dijkstra算法算法5.3.1 最短路

16、的Dijkstra算法无向图最短路的求法只将上述步骤2改动一下即可。点标号：b(i)起点vs到点vj的最短路长；边标号：k(i，j)=b(i)+dij，步骤：1.令起点的标号；b(s)0。3.计算集合B中边标号：ki，j=b(i)+dij4.选一个点标号:返回到第2步。2.找出所有一端vi已标号另一端vj未标号的边集合 B=i，j 如果这样的边不存在或vt已标号则计算结束；6.3.2 无向图最短路的无向图最短路的Dijkstra算法算法5.3.1 最短路的Dijkstra算法【例例】求下图求下图v1到各点的最短路及最短距离到各点的最短路及最短距离452617839326121618045223

17、1039612641166188122482418所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。5.3.1 最短路的Dijkstra算法动态规划算法基本步骤动态规划算法基本步骤:5.3.2 最短路的动态规划算法步骤1：令k=1,步骤2：令k=k+1，计算 5.3.2 最短路的动态规划算法动态规划算法基本步骤动态规划算法基本步骤:步骤3：对j=2,n，判断 与 是否相等。若全部相等，则 就是从v1到vj的最短路的权值，否则，转入步骤2。【例例】求下图所示网络中从求下图所示网络中从v1到各个点的最短路到各个点的最短路5.3.2 最短路的动态规划算法v4v2v3v1v52

18、23135-4表表5-1 最短距离表最短距离表 5.3.2 最短路的动态规划算法【解解】利用上述算法，求解过程可以在表上进行（见表5-1）。表的左边部分是初始数据wij；右边部分是各次迭代的计算结果，简记为dj(k)；最右边的一列数字就是从v1到各个vj的最短路的权值。表表5-1 最短距离表最短距离表 5.3.2 最短路的动态规划算法【解解】由表5-1可知，从v1到v1，v2，v3，v4，v5各点最短路的权值分别是0，1，3，2，-1。为了得到具体的最短路线，可以在求出最短路的权值dj后，采用反向追踪的办法来寻找，即在表5-1中找一点vi，使 ，记下边vi，vj；再对di，找到另一点vs，使，

19、记下边vs，vi；如此继续下去，直至达到v1为止。许多系统中都涉及到流量问题，例如网络系统中有信息流、公路系统中有车辆流、金融系统中有现金流等等。对于这些包含了流量问题的系统，我们往往需要求出其系统的最大流量。例如，某公路系统的容许通过的最大车辆数，某网络系统的最大信息流量等，以便于对某个系统加以认识并进行管理。5.4 最大流问题例例 某石油公司建有一个可以把石油从采地输送到不同销售点的管道网络，如下图。由于管道的直径变化，使得各段管道（vi,vj）的最大通过能力（容量）Cij也是不一样的，Cij的单位为万加仑/小时。要求我们制定一个输送方案，将石油从v1输送到v6，使得输送的石油达到最大.4

20、8441226795.4 最大流问题基本概念基本概念4844122679网络中所有流起源于一个网络中所有流起源于一个叫做发点的节点（源）叫做发点的节点（源）所有的流终止于一个叫做收点的节点所有的流终止于一个叫做收点的节点其余所有的节点叫做中间点（转运点）其余所有的节点叫做中间点（转运点）通过每一条弧的流只允许沿着弧的箭头方向流动通过每一条弧的流只允许沿着弧的箭头方向流动,目标是使得从发点到收点的总流量最大。目标是使得从发点到收点的总流量最大。5.4 最大流问题基本概念基本概念4844122679容量：在某时期内弧容量：在某时期内弧(i，j)上的最大通过能力。记为上的最大通过能力。记为C(i，j

21、)或或Cij 在上图中，C12=4，C138，C234等，怎样安排输送方案，才能使在某一时间内从怎样安排输送方案，才能使在某一时间内从v1运到运到v6的物资最多，的物资最多，这样的问题就是最大流问题这样的问题就是最大流问题.5.4 最大流问题68441226794220222204流量：流量：弧(i，j)的实际通过量，记为f(i，j)或f ij.流量流量容量容量5.4 最大流问题68441226794220222204可行流：如果可行流：如果f ij 满足：满足：1.对于所有弧对于所有弧(i，j)有有0f ijCij 则称流量集合则称流量集合f ij为网络的一个可行流，简记为为网络的一个可行流

22、，简记为 f 。2.对于中间点对于中间点vm有：有：（进量（进量=出量）出量）5.4 最大流问题前向弧：与链的方向相同的弧称为前向弧。前向弧：与链的方向相同的弧称为前向弧。后向弧后向弧：与链的方向相反的弧称为后向弧。与链的方向相反的弧称为后向弧。增广链增广链 设设 f 是一个可行流，如果存在一条从是一个可行流，如果存在一条从vs到到vt的链，满足：的链，满足：1.所有前向弧上所有前向弧上fij0则该链称为增广链则该链称为增广链.前向弧后向弧8446952346容量容量流量流量想一想，这是一条增广链吗？5.4 最大流问题【定理定理】设网络设网络G的一个可行流的一个可行流f，如果存在一条从，如果存

23、在一条从vs到到vt的增广的增广链，那么就可改进一个值更大的可行流链，那么就可改进一个值更大的可行流f1，并且流量，并且流量 v(f1)v(f 2)【证证】设设val fv对改进的可行流f1：5.4 最大流问题 最大流的标号算法最大流的标号算法步骤步骤 1.找出第一个可行流，例如所有弧的流量找出第一个可行流，例如所有弧的流量fij=0 2.用标号的方法找一条增广链用标号的方法找一条增广链.A：发点标号（：发点标号（，），），B：选一个已标号的点：选一个已标号的点 vi，对于对于vi的所有未给标号的邻接点，按下的所有未给标号的邻接点，按下列规则处理：列规则处理：如果是如果是前向弧前向弧并且有并且

24、有fij0 则则vj就可标号（就可标号（Cijfij）【例例】求下图求下图v1到则到则v7标的最大流标的最大流71292085148691316(10)(6)(10)(8)(2)(3)(7)(6)(5)(13)(0)(13)239935.4 最大流问题71292085148691316(12)(6)(10)(8)(4)(3)(7)(6)(7)(13)(2)(15)377171292085148691316(12)(7)(10)(8)(4)(3)(7)(6)(8)(13)(3)(16)V=291056615.4 最大流问题本章小结与展望本本章章介介绍绍了了图图的的一一些些基基本本概概念念；研研究

25、究了了网网络络最最优优化化的的4个个基基本本问问题题，即即最最小小树树问问题题，最最短短路路问问题题、最最大大流流问问题题和和最最小小费费用用最最大大流流问问题题的的基基本本理理论论和和求求解解算算法法；讨讨论论了了网网络络计计划划的的编编制制以以及及网网络络优优化化的的方方法法；给给出出了了网网络络最优化的应用案例。最优化的应用案例。近近几几十十年年来来，由由于于计计算算机机技技术术的的发发展展和和许许多多离离散散化化问问题题的的出出现现，使使得得图图与与网网络络的的理理论论及及其其应应用用得得到到飞飞速速发发展展，在在组组合合数数学学、地地图图着着色色、情情报报检检索索、可可靠靠性性理理论论、通通讯讯网网络络的的设设计计分分析析、电电力力网网络络分分析析、信信号号流流图图与与反反馈馈理理论论、印印刷刷线线路路板板设设计计、人人工工智智能能、故故障障诊诊断断等等众众多多领领域域都都大大显显身身手手。图图与与网网络络不不但但能能应应用用于于自自然然科科学学，也也能能应应用用于于社社会会科科学学，例例如如语语言言学学、社社会会管管理理、经经济济学学等等方方面面。目目前前随随着着信信息息科科学学与与网网络络技技术术的的迅迅速速发发展展，图图与与网网络理论将会在越来越多的领域取得丰硕的成果。络理论将会在越来越多的领域取得丰硕的成果。