最优树与流量分配.doc

《最优树与流量分配.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数理与信息工程学院学科：图论及其应用姓名：文海菊学号：06200106班级：信息与计算科学0612008-11-11最优树与流量分配〔10〕【摘　要】阐述和实现了生成最优树的算法—kruskl算法,概括了流量分配优化设计方法的现状,并针对其不足提出了可用于多水源的简单易行的优化树法。这一最优化技术通过求得管网的最优树来使供水路径最短,从而使管网的总造价最小。它的应用对城市旧管网的改扩建也有着重要的意义也说明了最优树的实用价值。【关键词】图;连通图;赋权图;最优树;流量发配【引言】给水配水系统的投资,一般占给水工程投资的

2、70%以上,每年的能耗也相当庞大,因此很有必要进行最优化设计。而优化设计者们在寻求约束条件下目标函数的极值时,发现在流量已分配的情况下才可求得其最经济值,可知流量分配优化又是给水管网优化的首要任务,并且对其规划设计、调度运行及维护管理都有重要意义。从目前的文献来看,流量分配方法比较多,出现的有节点累计法、均分法、截面法、以简约梯度为指导的单纯形法,Dijkstral法和生成树变换法。前三者有两个问题,一是流量分配相对比较均匀,难以区分管网主干管线和连接管;二是在分配流量时未考虑管长的影响,对管网的经济性和可靠性不利。截

3、面法未考虑节点流量的平衡条件,会出现流量多余或不足的管段。以简约梯度为指导的单纯形法,其矩阵相当庞大,计算繁杂。Dijkstral法较简便,但它只适用于单水源的情况,且对于主干线之外的管线寻优没有交待。而生成树变换法中,由于连枝管对应的基本回路和变换顺序的不定性,常难于收敛。本文试图用图论理论中的最优树法来确定环状网的主要干管线以及其之间的连接管的供水路线,从而使初始分配流量集中在最短供水路线上,以降低管网工程的总造价。同时也能帮助管理者将最短供水路线作为重点维护目标,因为它往往集中了主要供水流量和承受最大供水压力。1

4、　基本概念和定理定义11图G=(V,U)的弧列u=(u1,u2,…,uq)叫作一条路;我们把端点重合的路叫做圈,也叫作回路.定义22不包含圈的图称为无圈图,连通的无圈图称为树,用符号T来表示.定理12在一棵树中,每一对点之间只有一条路径.定理22有nv个点的一棵树有nv-1条边.定义31如果一棵树T为一个连通图的子图,且包括G中所有的点,则该树称为G的生成树.定义42对每一条边e,可赋以一个实数ω(e),称为e的权,G连同它边上的权称为赋权图.定义52在一个加权图中一棵生成树T的权是T中各树枝的权之和,一般而言,加权图

5、G中不同的生成树将有不同的权,G的所有生成树中,权最小的那棵生成树称为G的最小生成树,或称为G的最短生成树.2　论证和分析寻找一个图的最优树可采用的算法很多,本文主要介绍一种常用的算法—kruskl算法.1956年kruskl推广了生成树的“避圈法”,给出了求最小生成树的一个算法.算法是先把图G的所有各边照递增权的次序列成一表(如果有两条以上边的权相等,则这些边可以任意次序排列),其次选出G中最短的边.然后每下一步从G中所有留下的边中选出与前次选出的诸边不构成回路的一条最短边,这样继续下去直到nv-1条边已经选出为止.

6、这些选出的边就构成这个图的一棵最小生成树.以下是kruskl算法:(1)选择一条边e1,使得ω(e1)尽可能小.(2)若边e1,e2,…,ei已经选好,则从E{e1,e2,…,ei}中依照使:(i)　G{e1,e2,…,ei+1}为无圈图.(ii)　满足(i)的条件下,使ω(ei+1)尽可能小的原则来选ei+1.(3)到第二步不能再进行时停止.定理3由kruskal算法选得的边导出子图是最优树.证明　显然,kruskal算法得出的子图T*是生成树.下证它的最优性.设T*不是最优树,T1是G的任意给的一个生成树,f(T1

7、)是{e1,e2,…,ev-1}中不在T1上的ei的足标i的最小值,令T是使f(T)最大的一个最优树.因为T*不是最优树,又E(T*)={e1,e2,…,ev-1},故e1,e2,…,ev-1中必有不在E(T)中的边.设f(T)=k即e1,e2,…,ek-1在T与T*上,而ek不在T上,于是T+ek中有一个圈C,令ek′是在T上而不在T*上的边且ek′在C上.显然,T′=(T+ek)-ek′也是生成树,又ω(Tˊ)=ω(T)+ω(ek)-ω(ek′),由算法知,ek是使G{e1,e2,…,ek}上无圈的权最小的边,又G

8、{e1,e2,…,ek-1,ek′}是T之子图,也无圈,则有ω(ek′)≥ω(ek).于是ω(T′)≤ω(T),即T′也是最优树,但f(T′)>k=f(T),与f(T)之最大性矛盾.另外,在kruskal算法中,必定会遇到一个关键性的问题:算法怎样判断被检查的一条边与至今已被选作树枝的那些边是否构成回路?由于树是连通图,那些已被选