枝状管网布局优化中的3类问题-论文.pdf

《枝状管网布局优化中的3类问题-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、342化工机械2014正枝状管网布局优化中的3类问题商冠琪(中国石油化工股份有限公司)摘要总结了枝状管网布局优化研究中普遍存在的3类问题，包括无向图枝状结构布置、枝状结构中心点的确定和有向图的枝状连接结构布置，分别论述了3类问题的数学模型和求解算法。指出无向图枝状管网布局优化和枝状结构中心点的确定，其求解算法比较稳定，是集输系统枝状结构布局普遍采用的方式，sI算法加入额外点，优化结果优于其他算法。有向图的枝状结构布局，由于问题的复制性，目前无较成熟和被广泛认可的求解方法，此问题的研究更能贴近实际，能达到更

2、好的优化效果。关键词枝状管网布局优化求解方法对比分析中图分类号TQ055．8文献标识码A文章编号0254—6094(2014)03-0342-03目前，针对集输管网的优化设计问题多采用分minf：∑w(e)(1)EE级优化的策略，根据不同的管网形态将系统优化分式中E——图中所有边的集合；为多个子问题来处理，比如，星枝管网的优化设(e卜边e的权值。计，通过分级优化将气田星枝状地面集输系统优在求解最小生成树时，不仅要使枝状管网的化分为井组最优划分、星式管网布局优化、干支管网管线总长度最短，还要考虑各节点气量不

3、同而造布局优化和管网参数优化4个子问题进行研究。干成的管径差异，但是流向未知，可对顶点加权，得支管网布局优化是进行站点位置的合理布置，可分到求解枝状管网最优连接方式的数学模型如下：为3方面的内容，一是无向图枝状结构，二是枝状结min／=AdW=ALq(2)构中心点，三是有向图的枝状连接。⋯，1⋯，11无向枝状结构连接其约束条件为：无向枝状结构连接关系，多采用图论的最小生1≤A≤一(3)成树算法确定无向图的连接关系。根据图论的知1≤A-<一识，管网中的站点和管段可以抽象为图中的节点和一1(4)边，对于任意两

4、个节点间，理论上都可能存在一条A(一)()，管线相连，任意两点存在边则构成了一个完备图。A“=0，1(6)n个节点的完备图存在C=n(n一1)／2条边，在式中A——0～1决策变量，当节点i、J．间有管这些边中，选择n一1条边就可以得到枝状管网的线连接时，A为1，当节点i与不连接方式，而这n一1条管线也就构成了这个完备相连时，A伪0；图的一棵生成树。一个完备图的生成树有很多，可——第节点到第_『节点间的管线长度；能的枝状管网的连接方式也就有很多，没有考虑到m——节点的总数；流向的问题，可将枝状管网连接方式的

5、优化问题转q——第i节点的集气量。变成求无向图中的最小生成树问题。1．2求解算法1．1模型的建立求解算法主要包括Kruskai、Prim和sI生成求解无向图最小生成树的数学模型为：树算法。这3种方法是图论中的经典算法，算法$商冠琪，男，1981年2月生，工程师。北京市，100728。第41卷第3期化工机械343运行稳定，是集输系统枝状结构布局普遍采用的应用较普遍的有Dijkstra算法及Floyd算法等。方式。Dijkstra算法又叫做标号法，应用一次的时间Prime算法的时间复杂度为O(n)，n为图中复

6、杂度为O(m)，它每次只能求出图中一个特定顶点的个数，由于Prime算法与边的数目无关，适顶点到其他各顶点的最短路，如果要计算像煤层合求解边稠密的网络图的最小生成树；Kruskal算气集输管网这种具有m个顶点的无向图中任意法的时间复杂度为O(1g2k+2klg2n+n)，n为顶两个顶点间的最短路径，需要将图中每一个顶点点个数，k为边的个数，由于Kruskal算法的时间依次视为起始点，然后反复应用Dijkstra算法计复杂度主要取决于边的数目，适合求解边稀疏的算。因此，应用Dijkstra算法求解该问题的时

7、间网络图的最小生成树；SI算法在管网结构中加入复杂度为O(m)。了额外点，其优化结果优于其他两种算法，但运行Floyd算法又叫做插点法，在计算时从任意一效率不高。条单边路径开始，对于每一对顶点u和，看是否学者李书文首次对3种算法在枝状管网布局存在一个顶点埘使得从u到再到比己知路径优化研究中进行了论述；康正凌和袁宗明采用的加权距离更短，如果存在就更新它，如此循环，Kruskai算法确定枝状管网连接关系；李征用直到得出最短路径。Floyd算法求解该问题最短Prim算法确定枝状天然气管网连接关系；郑清路径的时间

8、复杂性也是O(m)。高等都采用了sI算法来确定气田集输管网最优徐国栋和梁政针对海上边际油田和陆上气网络布局。。田，研究了枝状管网的中心站址选择问题。2枝状结构中心点的确定3有向枝状连接结构布置枝状结构中心点问题是在确定了枝状结构连有向枝状结构连接关系。把无向树转化为有接关系时，在给定的生成树结构中选取合理节点向树后，在无向图中确定的连接方式，不一定是有作为站点。中心点作为整个枝状管网系统的中向图的最优连接方式，所得到的管网最小