图论与网络优化dzm.ppt

《图论与网络优化dzm.ppt》由会员分享，可在线阅读，更多相关《图论与网络优化dzm.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、主讲：段主讲：段滋明滋明2012暑期数学建模网网 络络 优优 化化图是一种直是一种直观形象的描述已知信息的方式，它形象的描述已知信息的方式，它使事物之使事物之间的关系的关系简介明了，是分析介明了，是分析问题的有用工的有用工具。用点表示研究具。用点表示研究对象，用点之象，用点之间的的连续表示表示对象象之之间的相互关系。的相互关系。图论与网与网络分析是运筹学的一个分支，内容十分析是运筹学的一个分支，内容十分丰富，分丰富，应用非常广泛。用非常广泛。一、一、图v6v7v5v4v3v2v1603020251815152030无向图有向图赋权图（网络）完全完全图K5K3,3二分二分图二、几个著名问题二、几

2、个著名问题图论中著名中著名问题.1736年，年，图论的的创始人始人Euler巧妙巧妙地将此地将此问题化化为图的不重复的不重复一笔画一笔画问题，并，并证明了明了该问题不存在肯定回答，不存在肯定回答，发表了第一篇表了第一篇论文文.例：七桥问题例：七桥问题ABCD问题：一个散步者能否走：一个散步者能否走过七座七座桥，且每座，且每座桥只走只走过一次，最后回到出一次，最后回到出发点。点。例：四色猜想例：四色猜想 能否用四种能否用四种颜色色给地地图染色，使相染色，使相邻的国家有不的国家有不同的同的颜色。色。点：国家；点：国家；边：两个国家有公共：两个国家有公共边界。界。问题：能否用四种能否用四种颜色色给平

3、面平面图的点染色，使有公的点染色，使有公共共边的点有不同的的点有不同的颜色。色。公元公元1852年，格里斯年，格里斯发现无无论多么复多么复杂的地的地图，只要用四种，只要用四种颜色就能将相色就能将相邻的区域区分开来，的区域区分开来，这就是所就是所谓“四色猜想四色猜想”。直到公元直到公元1976年，才由美国数学家同年，才由美国数学家同时操作三台超大型汁算机操作三台超大型汁算机作了近作了近200亿个个逻辑判断，花判断，花费1200个机个机时，才取得了，才取得了“四色四色猜想猜想”的的证明。明。例：例：Hamilton图哈密哈密尔顿游游戏：用正十二面体上：用正十二面体上20个个顶点表示点表示20个城个

4、城市，要求参加游市，要求参加游戏者沿着各者沿着各边行走，走遍每一个城市行走，走遍每一个城市且且仅走一次，最后回到出走一次，最后回到出发城市。城市。旅行商售旅行商售货(TSP)问题：在如上在如上问题中，若已知任中，若已知任意两城市意两城市间的旅行的旅行费用，用，问如何安排旅行路如何安排旅行路线使使总费用最少？用最少？例：中国例：中国邮路路问题 一个一个邮递员送信，要走完他所送信，要走完他所负责的全部街道的全部街道分送信件，最后返回分送信件，最后返回邮局。局。邮递员都会本能地以尽都会本能地以尽可能少的行程完成送信任可能少的行程完成送信任务。如何走路。如何走路线最短。最短。点：路口；点：路口；边：两

5、路口之：两路口之间道路，第道路，第i条道路条道路长ei。1962年，由我国数学家管梅谷提出，国年，由我国数学家管梅谷提出，国际上称上称为中中国国邮递员问题。问题：求一个圈，：求一个圈，过每每边至少一次，并使圈的至少一次，并使圈的长度度最最短。短。三、最短路三、最短路问题最短路最短路问题是网是网络理理论中中应用最广泛的用最广泛的问题之一之一.许多多优化化问题可以使用可以使用这个模型如个模型如设备更新、更新、管道管道铺设、线路安排、厂区布局等路安排、厂区布局等.n最短路最短路问题：在一个：在一个赋权图G上，上，给定两个定两个顶点点u和和v，在所有，在所有连接接顶点点u和和v的路中，的路中，寻找路找

6、路长最短的路（称最短的路（称为u和和v最短路最短路.）nu和和v最短路的路最短路的路长也称也称为u和和v的的距离距离-d(u,v).有些最短路有些最短路问题也可以求网也可以求网络中某指定点到其余所中某指定点到其余所有有结点的最短路、或求网点的最短路、或求网络中任意两点中任意两点间的最短路的最短路.1、网、网络无无负权的最短路的最短路本算法由本算法由Dijkstra于于1959年提出，可用于求解指定两年提出，可用于求解指定两点点间的最短路，或从指定点到其余各点的最短路，目的最短路，或从指定点到其余各点的最短路，目前被前被认为是求无是求无负权网网络最短路最短路问题的最好方法。的最好方法。Dijks

7、tra算法算法Ford算法基本思想：算法基本思想：为逐次逼近的方法。每次求出逐次逼近的方法。每次求出从出从出发点点v0到其余点的有限制的最短路，逐次放到其余点的有限制的最短路，逐次放宽条条件。最多迭代件。最多迭代|V|-1次次.2、网、网络有有负权的最短路的最短路Ford算法算法3、网、网络上任意两点上任意两点间的最短路的最短路Floyd算法算法常用的几种解法常用的几种解法例例1设备更新更新问题.某工厂使用一台某工厂使用一台设备，每年年初工厂都要作出决，每年年初工厂都要作出决定如果定如果继续使用旧的，要付使用旧的，要付维路路费；若；若购买一一台新台新设备要付要付购买费。试制定一个制定一个5年的

8、更新年的更新计划，使划，使总支出最少。支出最少。若已知若已知设备在各年年初的价格在各年年初的价格为：年度年度第第1年年第第2年年第第3年年第第4年年第第5年年购买费购买费1111121213还知使用不同年数的知使用不同年数的设备所需要的所需要的维修修费用用为：使用年数使用年数0-11-22-33-44-5维修费用维修费用5681118可把可把这个个问题化化为最短路最短路问题。用点用点vi表示第表示第i年年初年年初购进一台新一台新设备虚虚设一个点一个点v6,表示第五年年底。表示第五年年底。弧弧(vi,vj)表示第表示第i年初年初购进的的设备一直使用到第一直使用到第j年年年年初初(即第即第j-1年

9、年底年年底).v1v2v3v4v5v6161617171830412322312359413022这样设备更新更新问题就就变为：求从：求从v到到v6的最短路。的最短路。求解得：求解得：v1,v3,v6 及及v1,v4,v6 均均为最短路。最短路。总的支付的支付费用均用均为53。v1v2v3v4v5v6161617171830412322312359413022已知某地区的交通网已知某地区的交通网络如如图所示，其中点代表居民所示，其中点代表居民小区，便表示公路，小区，便表示公路，wij为小区小区间公路距离公路距离问区中区中心医院心医院应建在哪个小区，可使离医院最建在哪个小区，可使离医院最远的小区

10、居的小区居民就民就诊时所走的路程最近所走的路程最近?v6v7v5v4v3v2v1603020251815152030例例2选址址问题.解解：实际要求出要求出图的中心，可以化的中心，可以化为一系列求最短一系列求最短路路问题。先求出先求出v1到其它各点的最短路到其它各点的最短路长dj,令令D(v1)max(d1,d2,d7)表示若医院建在表示若医院建在v1，则离医院最离医院最远的小区的小区距离距离为D(v1)。再依次。再依次计算算v2,v3,v7到其余各点的到其余各点的最短路，最短路，类似求出似求出D(v2),D(v3),D(v7)。D(vi)中最小者即中最小者即为所求，所求，计算算结果果见下表。

11、下表。v6v7v5v4v3v2v1603020251815152030由于由于D(v6)48最小，所以医院最小，所以医院应建在建在v6，此，此时离医院最离医院最远的小区的小区(v5)距离距离为48.树（tree）是一个不包含圈的）是一个不包含圈的简单连通通图。n个个顶点的点的树有有n-1条条边。树中度中度为1的点称的点称为树叶叶，度大于，度大于1的点称的点称为分枝点分枝点.具有具有k个个连通分支的不包含圈的通分支的不包含圈的图称称为k-树，或，或森林森林.四、最小生成四、最小生成树和最和最优连接接图的（最小）生成的（最小）生成树v连通通图G的子的子图T，如果它的，如果它的顶点集与点集与G的的顶

12、点集相点集相同，且同，且T是是树，则称称树T为图G的的支撑支撑树（生成生成树）。）。或或简称称为图G的的树.v支撑支撑树也称也称为连通通图的的极小极小连通支撑子通支撑子图。v很很显然，一个然，一个连通通图只要本身不是一棵只要本身不是一棵树，它的支，它的支撑撑树就不止一个。就不止一个。v如果如果图的的边有有权，则权的的总和达到最小的生成和达到最小的生成树称称为最小生成最小生成树(MST)。最小最小树12244342v1v2v4v5v31232v1v2v4v5v3最小最小树是网是网络优化中的一个重要化中的一个重要问题，在网，在网络设计中有广泛中有广泛应用。用。许多网多网络问题都可以都可以归结为最小

13、最小树问题。例如。例如:设计长度最小的公路网把若干城市度最小的公路网把若干城市联系起来系起来;设计用料最省的用料最省的电话线网把有关网把有关单位位联系起来系起来等等.这些些应用用问题统称称为最最优连线问题。p也可将最也可将最优连线问题转化化为整数整数规划求解。划求解。许多系多系统包含了流量包含了流量问题。例如在交通运。例如在交通运输网网络中有人流、中有人流、车流、流、货物流；供水网物流；供水网络中有水流；中有水流；金融系金融系统中有中有现金流；通金流；通讯系系统中有信息流，等等。中有信息流，等等。不同网不同网络中流的意中流的意义不同，流本身是一种不同，流本身是一种输送，可送，可以把它以把它们统

14、称称为运运输网网络的流。的流。五、最大流问题五、最大流问题8528796653vsv1vtv4v3v21.网网络与流与流给一个有向一个有向连通通图D=(V,A)，在，在V 中指定了一中指定了一个点，称个点，称为发点点(或或源源，记为vs，其入度，其入度为0)，和另，和另一个点，称一个点，称为收点收点(或或汇，记为vt，其出度，其出度为0)，其，其余点叫余点叫中中间点点，对D的每条弧的每条弧(vi,vj)对应有一个非有一个非负数数cij,称称为弧的容量弧的容量，这样的网的网络D称称为容量网容量网络（或运（或运输网网络），常，常记做做D=(V,A,C)。对任一任一D中的弧中的弧(vi,vj)有有流

15、量流量fij，称集合，称集合f=fij 为网网络D上的一个流上的一个流。(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2例例网网络D 及其一个流及其一个流vs为发点点(源源)，vt为收点收点(汇)，其余点，其余点为中中间点点。对每条弧每条弧(vi,vj)，有，有弧的容量弧的容量cij，弧的流量弧的流量fij，常常记做做(fij ,cij).如如fs1 =5，f12 =4，f42 =2.集合集合f=fij 称称为网网络D上的一个流上的一个流.2.可行流与最大流可行流与最大流称称满足下列条件的流足下列条件的流f为可行流：可

16、行流：(1)容量限制条件：容量限制条件：对所有所有弧弧(vi,vj)，成立成立(2)平衡条件：平衡条件：对所有中所有中间顶点点v，成立，成立其中，其中，f+(v)是流出是流出v 的的总流量，流量，f-(v)是流入是流入v的的总流量，流量，对于源点于源点v s和和汇点点vt，流出源点，流出源点vs 的流量等于流入的流量等于流入汇点点v t的流量的流量.称之称之为流流 f的的值，记为val f 或或v(f).可行流可行流总是存在的。是存在的。例如令所有弧的流量例如令所有弧的流量fij=0，就得到一个可行流，就得到一个可行流f=0(称称为零流零流)，其流量，其流量v(f)=0.所所谓最大流最大流问题

17、就是在容量网就是在容量网络中，中，寻找流量找流量最大的可行流。最大的可行流。最大流最大流问题实际是个是个线性性规划划问题，但是利用，但是利用它与它与图的的紧密关系，能更密关系，能更为直直观简便地求解。便地求解。(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2v(f)=7.3.割集割集设S、S是网是网络D的两个的两个顶点子集点子集,且且且且,定定义D的一个的一个割集割集(简称称割割)为也称也称为分离分离vs和和vt一个割集一个割集，可，可简记为K.(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2

18、,6)(0,5)(0,3)vsv1vtv4v3v2割集割集六、最小费用最大流问题六、最小费用最大流问题最小最小费用最大流用最大流问题：求一个最大流求一个最大流，使流的，使流的总输送送费用达到最小用达到最小.基本假基本假设：给定有向网定有向网络,其中其中表示弧表示弧的容量，的容量，表示表示单位流通位流通过弧弧的的费用。用。流流的的费用用为例：求如下网例：求如下网络的最小的最小费用最大流，弧旁用最大流，弧旁为应用模型：无用模型：无线电信道分配（信道分配（MCM2000B）寻找找一个模型，把一个模型，把无无线电信道信道分配到分配到一个大的平面一个大的平面区域区域的一些的一些传送站的送站的均衡网均衡网

19、络上，上，以避免干以避免干扰。一个基一个基本的方法是将此区域分成正六本的方法是将此区域分成正六边形的格子形的格子(蜂蜂窝状状)，如如图。传送站安置在每个正六送站安置在每个正六边形的中心点形的中心点.频谱的一个区的一个区间容容许作作为各各传送站的送站的频率率，将将这一区一区间规则地分地分割成一些空割成一些空间信道信道，用整数用整数1,2,3,来表示来表示。每一个每一个传送站将被配置一送站将被配置一正整数信道正整数信道.同一信道可以在同一信道可以在许多多传送站送站使用使用，前提是相前提是相邻近的近的传送站送站不相互干不相互干扰。频谱需要需要根据某些限制根据某些限制来来设定信道定信道，我我们的目的目

20、标是是极小化极小化频谱的的这个区个区间宽度度。这可以用跨度可以用跨度这一概念一概念。跨度是跨度是在在滿足限制的滿足限制的所有所有配置中配置中，任何，任何传送站送站使用的最使用的最大信道的最小大信道的最小值。在一个在一个获得一定跨度的配置中不要求得一定跨度的配置中不要求小于跨度的每一信道都被使用小于跨度的每一信道都被使用。令令s为一个正六一个正六边形的形的边长.。我我们集中考集中考虑存在两种干存在两种干扰水平的情况水平的情况。要求要求A:频率配置有几个限制率配置有几个限制,第一第一,相距相距4s以内的以内的传送站送站不能配不能配给同一信道同一信道。第二第二，由于波由于波谱的的传播播，相距相距2s

21、以以内内的的传送站不送站不能能配配给相同或相相同或相邻的信道的信道：它它们至少差至少差2.在這些限制下在這些限制下,关于跨度能关于跨度能说些什么些什么.v要求要求B:假定前述假定前述图中的格子在各方向延伸到任意中的格子在各方向延伸到任意远,重重复复要求要求A.v要求要求C:更一般地更一般地，假定假定相距相距2s以内以内的的传送站的信道至送站的信道至少少相相差一个差一个给定的整数定的整数k，相距，相距4s以内以内的的传送站的至少送站的至少相相差差1。重复要求重复要求A和和B。将。将跨度和跨度和设计配置的有效策略配置的有效策略作作为k的一个函数的一个函数，能能说点什么点什么。v要求要求D:考考虑问

22、题的一般化的一般化，比如各种干比如各种干扰水平水平,或不或不规则的的传送站布局送站布局。其他什么因素在考其他什么因素在考虑中是重要的中是重要的。v要求要求E:写一篇短文写一篇短文(不超不超过两两页)给地方地方报纸,阐述你的述你的发现。这个个问题本本质上是一个上是一个图论中的染色中的染色问题，但，但问题B又与又与传统的染色的染色问题不尽相同，它不不尽相同，它不仅限制了相限制了相邻的的传送站的信道，并且送站的信道，并且还增加了增加了对“隔开一点隔开一点”的的传送站送站的信道限制，的信道限制，用用经典染色理典染色理论的方法无法的方法无法彻底解决。底解决。图图1.六边形蜂窝系统六边形蜂窝系统 图图2.无限六正则格子图无限六正则格子图p定义：定义：对简单图对简单图 ,设设 ,若对任意两个若对任意两个顶点顶点 ，有，有 则称则称 f 为为G 的一个的一个L(2,1)-标号标号或或L(2,1)-染色染色。图的图的 L(2,1)-标号：标号：更一般地，归结为更一般地，归结为图的图的 L(k1,k2,kp)-标号问题。标号问题。