第5章图与网络模型.ppt
《第5章图与网络模型.ppt》由会员分享,可在线阅读,更多相关《第5章图与网络模型.ppt(94页珍藏版)》请在三一文库上搜索。
1、1,第五章 图与网络模型,1 图与网络的基本概念 2 最短路问题 3 最小生成树问题 4 最大流问题 5 车间作业计划 6 统筹法(网络规划),图论是专门研究图的理论的一门数学分支,属于离散数学范畴,与运筹学有交叉,它有200多年历史,大体可划分为三个阶段:第一阶段是从十八世纪中叶到十九世纪中叶,处于萌芽阶段,多数问题为游戏而产生,最有代表性的工作是所谓的Euler七桥问题(1736年),即一笔画问题。,第二阶段是从十九世纪中叶到二十世纪中叶,这时,图论问题大量出现,如Hamilton问题,地图染色的四色问题以及可平面性问题等,这时,也出现用图解决实际问题,如Cayley把树应用于化学领域,K
2、irchhoff用树去研究电网络等.,第三阶段是二十世纪中叶以后,由生产管理、军事、交通、运输、计算机网络等方面提出实际问题,以及大型计算机使大规模问题的求解成为可能,特别是以Ford和Fulkerson建立的网络流理论,与线性规划、动态规划等优化理论和方法相互渗透,促进了图论对实际问题的应用。,例10-1:哥尼斯堡七桥问题 哥尼斯堡(现名加里宁格勒)是欧洲一个城市,Pregei河把该城分成两部分,河中有两个小岛,十八世纪时,河两边及小岛之间共有七座桥,当时人们提出这样的问题:有没有办法从某处(如A)出发,经过各桥一次且仅一次最后回到原地呢?,A,B,C,D,最后,数学家Euler在1736年
3、巧妙地给出了这个问题的答案,并因此奠定了图论的基础,Euler把A、B、C、D四块陆地分别收缩成四个顶点,把桥表示成连接对应顶点之间的边,问题转化为从任意一点出发,能不能经过各边一次且仅一次,最后返回该点。这就是著名的Euler问题。,A,C,B,D,有7个人围桌而坐,如果要求每次相邻的人都与以前完全不同,试问不同的就座方案共有多少种? 用顶点表示人,用边表示两者相邻,因为最初任何两个人都允许相邻,所以任何两点都可以有边相连。,1,2,3,7,6,4,5,假定第一次就座方案是 (1,2,3,4,5,6,7,1),那么第二次就座方案就不允许这些顶点之间继续相邻,只能从图中删去这些边。,1,2,3
4、,7,6,4,5,1,2,3,7,6,4,5,假定第二次就座方案是 (1,3,5,7,2,4,6,1),那么第三次就座方案就不允许这些顶点之间继续相邻,只能从图中删去这些边。,1,2,3,7,6,4,5,1,2,3,7,6,4,5,假定第三次就座方案是 (1,4,7,3,6,2,5,1),那么第四次就座方案就不允许这些顶点之间继续相邻,只能从图中删去这些边,只留下7点孤立点,所以该问题只有三个就座方案。,1,2,3,7,6,4,5,1,2,3,7,6,4,5,哈密顿(Hamilton)回路是十九世纪英国数学家哈密顿提出,给出一个正12面体图形,共有20个顶点表示20个城市,要求从某个城市出发沿
5、着棱线寻找一条经过每个城市一次而且仅一次,最后回到原处的周游世界线路(并不要求经过每条边)。,22,1 图与网络的基本概念,图论中图是由点和边构成,可以反映一些对象之间的关系。 例如:在一个人群中,对相互认识这个关系我们可以用图来表示,下图就是一个表示这种关系的图。,23,1 图与网络的基本概念,当然图论不仅仅是要描述对象之间关系,还要研究特定关系之间的内在规律,一般情况下图中点的相对位置如何、点与点之间联线的长短曲直,对于反映对象之间的关系并不是重要的,如对赵等七人的相互认识关系我们也可以表示如下,可见图论中的图与几何图、工程图是不一样的。,24,1 图与网络的基本概念,如果我们把上面例子中
6、的“相互认识”关系改为“认识” 的关系,那么只用两点之间的联线就很难刻画他们之间的关系了,这时我们引入一个带箭头的联线,称为弧。下图就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。,25,1 图与网络的基本概念,无向图: 由点和边构成的图,记作G=(V,E)。 有向图: 由点和弧构成的图,记作D=(V,A)。 连通图: 对无向图G,若任何两个不同的点之间,至少存在一条链,则G为连通图。 回路: 若路的第一个点和最后一个点相同,则该路为回路。 赋权图: 对一个无向图G的每一条边(vi,vj),相应地有一个数wij,则称图G为赋权图,wij称为边(vi,vj)上的权。 网络: 在赋
7、权的有向图D中指定一点,称为发点,指定另一点称为收点,其它点称为中间点,并把D中的每一条弧的赋权数称为弧的容量,D就称为网络。,26,2 最短路问题,最短路问题:对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条从 Vs 到 Vt 的路,使得这条路上所有弧的权数的总和最小,这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。 解最短路的Dijkstra算法(双标号法) 步骤: 1.给出点V1以标号(0,s) 2.找出已标号的点的集合I,没标号的点的集合J以及弧的集合 3. 如果上述弧的集合是空集,则计算结束。如果vt已标号(lt,kt),则 vs到vt的
8、距离为lt,而从 vs到vt的最短路径,则可以从kt 反向追踪到起点vs 而得到。如果vt 未标号,则可以断言不存在从 vs到vt的有向路。如果上述的弧的集合不是空集,则转下一步。 4. 对上述弧的集合中的每一条弧,计算 sij=li+cij 。在所有的 sij中,找到其值为最小的弧。不妨设此弧为(Vc,Vd),则给此弧的终点以双标号(scd,c),返回步骤2。,最短路问题是网络分析中的一个基本问题,它不仅可以直接应用于于解决生产实际的许多问题,若管道铺设、线路安排、厂区布局等,而且经常被作为一个基本工具,用于解决其它的优化问题. 定义 给定一个赋权有向图D = (V,A),记D中每一条弧 上
9、的权为为 。给定D中一个起点 和 终点,设P是D中从 到 的一条路.则定义路P的权是P中所有弧的权之和.记为 ,即 又若P*是D图中 到 的一条路,且满足 则称P*为从 到 的最短路。,28,最短路问题 网络:规定起点、中间点和终点的赋权图; 有向网络:网络中每个边都是有向边; 无向网络:网络中每个边都是无向边; 混合网络:网络中既有有向边,又有无向边; 网络最短路线问题:寻找网络中从起点 v1 到终点 vn 的最短路线。 Min L() = lij 为从 v1 到 vn 的通路; lij 其中, lij为从 vi 到 vj 的一步距离。,29,结合例题学习、掌握求最短路的狄克斯拉、海斯和福德
10、三个方法: 1、狄克斯拉方法:适用于满足所有权系数大于等于0(lij0)的网络最短路问题,能求出起点 v1 到所有其它点 vj 的最短距离; 2、海斯方法:基本思想是在最短路线上任意两点间路线也是最短路线。利用 vi 到 vj 的一步距离求出 vi 到 vj 的两步距离再求出 vi 到 vj 的四步距离经有限次迭代可求出 vi 到 vj 的最短距离; 3、福德方法:适用于有负权系数,但无负回路的有向或无向网络的最短路问题,能求出起点 v1 到所有其它点 vj 的最短距离。,30,2 最短路问题,例1 求下图中v1到v6的最短路 解:采用Dijkstra算法,可解得最短路径为v1 v3 v4 v
11、6 各点的标号图如下:,31,网络最短路线问题: 寻找网络中从起点 v1 到终点 vn 的最短路线。 标注 vk(lk,k-1) 定义:k=1时,l1=0,k-1=s,v1(0,s) min( lij ) Min L() = lij 为从 v1 到 vn 的通路; lij 其中, lij为从 vi 到 vj 的一步距离。,最短路问题,32,2 最短路问题,例2 电信公司准备在甲、乙两地沿路架设一条光缆线,问如何架设使其光缆线路最短?下图给出了甲乙两地间的交通图。权数表示两地间公路的长度(单位:公里)。 解:这是一个求无向图的最短路的问题。可以把无向图的每一边(vi,vj)都用方向相反的两条弧(
12、vi,vj)和(vj,vi)代替,就化为有向图,即可用Dijkstra算法来求解。也可直接在无向图中用Dijkstra算法来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。,33,2 最短路问题,例2最终解得: 最短路径v1 v3 v5 v6 v7,每点的标号见下图,(0,s) V1 (甲地),15,17,6,2,4,4,3,10,6,5,(13,3) v2,(22,6) V7 (乙地),V5 (14,3),V6 (16,5),V3 (10,1),V4 (18,5),例设备更新问题 某工厂使用一台设备,每年年初工厂要作出决定:继续使用,购买新的?
13、如果继续使用旧的,要负维修费;若要购买一套新的,要负购买费。试确定一个5年计划,使总支出最小。若已知设备在各年的购买费,及不同机器役龄时的残值与维修费。,解:把这个问题化为最短路问题。,设bi 表示设备在第i 年年初的购买费,ci 表示设备使用i 年后的维修费, V=v1, v2, , v6,点vi表示第i 年年初购进一台新设备,虚设一个点v6表示第5年年底. E =vivj | 1ij6.,2 最短路问题,35,2 最短路问题,例的解: 将问题转化为最短路问题,如下图: 用vi表示“第i年年初购进一台新设备”,弧 (vi,vj)表示第i年年初购进的设备一直使用到第j年年初。 把所有弧的权数计
14、算如下表:,若每年购置一台新设备,则购置费为:11+11+12+12+13=59,每年的维修费为5元, 共59+5*5=84. 若在1,2,3年购置一台新设备,则购置费为:11+12+13=36,每年的维修费为(5+6)+(5+6)+5=27,共36+27=63. 设备使用一年后就更新则不划算。 由表知,设备使用三年后应当更新。,这样上述设备更新问题就变为:在有向赋权图G = (V, E, F )(图解如下)中求v1到v6的最短路问题.,由实际问题可知,设备使用三年后应当更新,因此删除该图中v1到v5 ,v1到v6 ,v2到v6的连线;又设备使用一年后就更新则不划算,因此再删除该图中v1v2
15、,v2v3 ,v3v4 ,v4v5 ,v5v6 五条连线后得到,从上图中容易得到v1到v6只有两条路:,v1v3v6(费用22+31)和v1v4v6 (费用22+31).,而这两条路都是v1到v6的最短路.,39,3 最小生成树问题,树是图论中的重要概念,所谓树就是一个无圈的连通图。,图中,(a)就是一个树,而(b)因为图中有圈所以就不是树, (c)因为不连通所以也不是树。,40,3 最小生成树问题,给了一个无向图G=(V,E),我们保留G的所有点,而删掉部分G的边或者说保留一部分G的边,所获得的图G,称之为G的生成子图。在图中,(b)和(c)都是(a)的生成子图。 如果图G的一个生成子图还是
16、一个树,则称这个生成子图为生成树,在图中,(c)就是(a)的生成树。 最小生成树问题就是指在一个赋权的连通的无向图G中找出一个生成树,并使得这个生成树的所有边的权数之和为最小。,(a),(b),(c),41,3 最小生成树问题,求解最小生成树的破圈算法 算法的步骤: 1、在给定的赋权的连通图上任找一个圈。 2、在所找的圈中去掉一个权数最大的边(如果有两条或两条以上的边都是权数最大的边,则任意去掉其中一条)。 3、如果所余下的图已不包含圈,则计算结束,所余下的图即为最小生成树,否则返回第1步。,42,3 最小生成树问题,例 用破圈算法求图(a)中的一个最小生成树,43,3 最小生成树问题,例、某
17、大学准备对其所属的7个学院办公室计算机联网,这个网络的可能联通的途径如下图,图中v1,v7 表示7个学院办公室,请设计一个网络能联通7个学院办公室,并使总的线路长度为最短。,解:此问题实际上是求最小生成树,这在例中已经求得,也即按照图的(f)设计,可使此网络的总的线路长度为最短,为19百米。 “管理运筹学软件”有专门的子程序可以解决最小生成树问题。,44,4 最大流问题,最大流问题:给一个带收发点的网络,其每条弧的赋权称之为容量,在不超过每条弧的容量的前提下,求出从发点到收点的最大流量。 最大流的数学模型 例6 某石油公司拥有一个管道网络,使用这个网络可以把石油从采地运送到一些销售点,这个网络
18、的一部分如下图所示。由于管道的直径的变化,它的各段管道(vi,vj)的流量cij(容量)也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地 v1向销地 v7运送石油,问每小时能运送多少加仑石油?,v5,45,4 最大流问题,我们可以为此例题建立线性规划数学模型: 设弧(vi,vj)上流量为fij,网络上的总的流量为F,则有:,46,4 最大流问题,在这个线性规划模型中,其约束条件中的前6个方程表示了网络中的流量必须满足守恒条件,发点的流出量必须等于收点的总流入量;其余的点称之为中间点,它的总流入量必须等于总流出量。其后面几个约束条件表示对每一条弧(vi,vj)的流量fij要满
19、足流量的可行条件,应小于等于弧(vi,vj)的容量cij,并大于等于零,即0fij cij。我们把满足守恒条件及流量可行条件的一组网络流 fij称之为可行流,(即线性规划的可行解),可行流中一组流量最大(也即发出点总流出量最大)的称之为最大流(即线性规划的最优解)。 我们把例6的数据代入以上线性规划模型,用“管理运筹学软件”,马上得到以下的结果:f12=5,f14=5,f23=2,f25=3,f43=2,f46=1,f47=2,f35=2,f36=2,f57=5,f67=3。最优值(最大流量)=10。,47,5 车间作业计划模型,一、一台机器、n个零件的排序问题 例1.某车间只有一台高精度的磨
20、床,常常出现很多零件同时要求这台 磨床加工的情况,现有六个零件同时要求加工,这六个零件加工所需时间 如下表所示。 应该按照什么样的加工顺序来加工这六个零件,才能使得这六个零 件在车间里停留的平均时间为最少?,48,5 车间作业计划模型,例1解:如果我们用Pi表示安排在第i位加工的零件所需的时间,用Tj表示安排在第j位加工的零件在车间里总的停留时间,则有 Tj = P1 + P2 + Pj-1 + Pj = 不同的加工顺序得到不同的各零件的平均停留时间,如何得到一个使得各零件的平均停留时间最少的排序呢?这就是我们最后要解决的优化问题,而且我们要设法找到一种简便的算法。 对于某种加工顺序,我们知道
21、安排在第j位加工的零件在车间里总的停留时间为Tj , Tj = 可知这六个零件的停留时间为: T1 + T2 + T3 + T4 + T5 + T6 P1 + ( P1 + P2 ) + (P1 + P2 + P3 ) + (P1 + P2 + P3 + P4 ) + (P1 + P2 + P3 + P4 + P5) + (P1 + P2 + P3 + P4 + P5 + P6 ) 6 P1 + 5 P2 + 4P3 + 3P4 + 2P5 + P6. 那么各个零件平均停留时间为 从上式可知,对于一台机器n个零件的排序问题,只要系数越大,配上加工时间越少的,即按照加工时间排出加工顺序,加工时间
22、越少的零件排在越前面,加工时间越多的零件排在越后面,可使各个零件的平均停留时间为最少。,49,5 车间作业计划模型,二、两台机器、n个零件 例2.某工厂根据合同定做一些零件,这些零件要求先在车床上车削,然后再在 磨床上加工,每台机器上各零件加工时间如表12-5所示。 表-1 应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间为最少? 解:由于每个零件必须先进行车床加工,再进行磨床加工,所以在车床上加 工零件的顺序与在磨床上加工零件的顺序是一样的。 如果这些零件在车床上和磨床上加工顺序都为1,2,3,4,5。我们用图12-1 中的线条图来表示各零件加工的开始时间与完成时间,这种图
23、是由一根时间轴和 车床、磨床在每个时间段的状况的图形所构成。,50,5 车间作业计划模型,图 1 从上图中我们可以看出,加工时间的延长主要是由于磨床的停工待料 造成的,只要减少磨床的停工待料的时间就能减少整个加工任务的总时间。 为了减少磨床的停工待料,我们应该一方面把在车床上加工时间越短的零 件越早加工,减少磨床等待的时间;另一方面把在磨床上加工时间越长的 零件越晚加工,以便充分利用前面的时间,这样我们就得到了使完成全部 零件加工任务所需总时间最少的零件排序方法。,51,5 车间作业计划模型,寻找例2的最优解:我们在表12-5中找到所列出的最短加工时间是0.25,它是第二道工序磨床 加工零件2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 网络 模型
链接地址:https://www.31doc.com/p-2979894.html