城镇天然气管网优化系统的研究 硕士论文.pdf

西安石油大学 硕士学位论文 城镇天然气管网优化系统的研究 姓名：陈晓妮 申请学位级别：硕士 专业：计算机应用技术 指导教师：爨莹 20110520 专业： 硕士生： 指导教师： 计算机应用技术 陈晓妮( 签名) 爨莹( 签名) f r illi iii i i iii iiillii i i l 19 4 3 6 8 8 摘要 随着天然气的广泛使用和天然气输配管网规模的大型化，天然气经营部门为了增加 经济效益和增大燃气管网的利用率，需要对天然气管网系统进行优化。由于城镇天然气 系统工程的建设投资巨大，工程建成后不宜轻易改建或扩建，天然气管网设计需要合理 化。 本文针对城镇天然气管网优化的问题，在研究图论、燃气管网c a d 的理论分析与 应用等基础上，首先，提出了改进的d i j k s t r a 算法，并将其与传统的d i j k s t r a 算法进行分 析对比，实现了城镇天然气管网气源节点合理优选，通过长庆燃气管网现场实验数据的 仿真算例分析，验证了改进的d i j k s t r a 算法的有效性；其次，在气源节点、用户位置确 定的情况下，采用受限最小生成树算法对城镇天然气管网的布局进行优化，仿真算例验 证了受限最小生成树算法的实用性。最后，再将改进d i j k s t r a 算法和受限最小生成树算 法应用于城镇天然气管网优化中，运用软件工程理论、混合编程技术开发了“城镇天然 气管网优化系统“ 。 通过现场数据分析，城镇天然气管网优化系统能有效地实现城镇天然气管网气源节 点优选和管网布局优化，为城镇天然气系统工程投资的评估预测提供指导作用。 关键词：燃气管网 改进的d i j k s t r a 算法受限最小生成树算法管网布局优化 论文类型：应用研究 英文摘要 s u b j e c t ： s p e c i a l i t y ： n a m e ： i n s t r u c t o r ： s t u d y o no p t i m a ls y s t e mo fu r b a nn a t u r a lg a sn e t w o r k c o m p u t e ra p p l i c a t i o nt e c h n o l o g y c h e nx i a o n i ( s i g n a t u r e ) 凼妇凶边丑i c u a n y i n g ( s i g n a t u r e ) 岢 a b s l r a c i w i t ht h ep o p u l a r i t yo fn a t u r a lg a sa n dl a r g e rs c a l eo fn a t u r a lg a sd i s t r i b u t i o nn e t w o r k , n a t u r a lg a sb u s i n e s sd e p a r t m e n th a v et oo p t i m i z en a t u r a lg a sp i p e l i n es y s t e mt oi n c r e a s e p r o f i t sa n du t i l i z a t i o no fg a sn e t w o r k s i n c et h en a t u r a lg a ss y s t e mp r o j e c tr e q u i r e se n o r m o u s i n v e s t m e n t ，i ti sn o te a s i l yr e b u i l d e do re x p a n d e da f t e rt h ep r o j e c tw a sc o m p l e t e d t h e r e f o r e ， t h ed e s i g no fn a t u r a lg a sn e t w o r kn e e dt oh er a t i o n a l i z e d t h et h e s i sm a i n l yf o c u s e so no p t i m i z a t i o no f u r b a nn a t u r a lg a sn e t w o r k , b a s e do ng r a p h t h e o r ya n dt h e o r e t i c a la n a l y s i s & a p p l i c a t i o no fg a sn e t w o r kc a d f i r s t l y , i m p r o v e dd i j k s t r a a l g o r i t h mi sp r o p o s e d ，a n di t sc o m p a r e dt ot h et r a d i t i o n a ld i j k s t r aa l g o r i t h m i tr e a l i z e d r e a s o n a b l es e l e c t i o no f g a ss o u r c en o d ei nu r b a nn a t u r a lg a sn e t w o r k , a n dt h ee f f e c t i v e n e s so f i m p r o v e dd i j k s t r aa l g o r i t h mh a sb e e np r o v e db ya n a l y z i n gs i m u l a t i n gc a s eo ft h ec h a n g q i n g g a sn e t w o r kf i e l de x p e r i m e n td a t a s e c o n d l y , a c c o r d i n gt ob e i n gg i v e nt h eg e o p o l i t i c a l l o c a t i o no fg a ss o u r c ea n dc o n s u m e r , l a y o u to fu r b a nn a t u r a lg a sn e t w o r ki s o p t i m i z e db y l i m i t e dm i n i m u ms p a n n i n gt r e ea l g o r i t h m , a n dt h ep r a c t i c a b i l i t yo fl i m i t e dm i n i m u m s p a n n i n gt r e ea l g o r i t h mi sc o n f i n n e db ys i m u l a t i n gc a s eo ft h ec h a n g q i n gg a sn e t w o r kf i e l d e x p e r i m e n td a t a f i n a l l y , i m p r o v e dd i j k s t r aa l g o r i t h ma n dl i m i t e dm i n i m u ms p a n n i n gt r e e a l g o r i t h ma r ea p p l i e dt oo p t i m i z a t i o no fu r b a nn a t u r a lg a sn e t w o r k , a n do p t i m a ls y s t e mo f u r b a nn a t u r a lg a sn e t w o r kw i t ht h e o r yo fs o f t w a r ee n g i n e e r i n ga n dt e c h n o l o g yo fm i x i n g p r o g r a m m i n gh a sb e e nd e v e l o p e d o p t i m a ls y s t e mo fu r b a nn a t u r a lg a sn e t w o r kc a ne f f e c t i v e l yr e a l i z eo p t i m i z i n gs e l e c t i o n o fg a ss o u r c en o d ei nu r b a nn a t u r a lg a sn e t w o r ka n dl a y o u to p t i m i z a t i o no fg a sn e t w o r kb y a n a l y z i n gf i e me x p e r i m e n td a t a ，w h i c hp r o v i d e sg u i d a n c ef o ra s s e s s i n ga n df o r e c a s t i n g i n v e s t m e n to fu r b a nn a t u r a lg a ss y s t e me n g i n e e r i n g k e y w o r d s ：g a sn e t w o r k , i m p r o v e dd i jk s t r aa l g o r i t h m ，l i m i t e dm i n i m u ms p a n n i n g t r e ea l g o r i t h m ，p i p en e t w o r kl a y o u to p t i m i z a t i o n t h e s i s ：a p p l i c a t i o ns t u d y i i i 第一章绪论 第一章绪论 1 1 研究的背景及意义 1 1 1 研究背景 本课题来自西安石油大学和长庆合作的“苏一东准输气管道冷弯弯管及管材咨询方 案”项目，针对城镇天然气管网布局优化在城镇天然气系统工程所面临的问题，运用图 论、燃气管网c a d 的理论分析与应用等知识，并结合长庆现场实验数据研究城镇天然 气管网优化系统的网络结构，对城镇天然气管网进行优化。 1 1 2 研究意义 进入二十一世纪后，随着国民经济高速发展，对能源的需求也越来越大。由于天然气 输气管道是朝着长距离、直径大、壁薄、高输送压力的趋势发展；天然气输配系统同趋 管理大型化、结构复杂化、管线封闭化。天然气输配系统的供气量越来越大，其中无论 气源、用户、管道或设备哪一个发生变化都将直接或间接影响整个系统的运行，以及管 网自身的复杂性和燃气流动规律的特殊性，使得输气管网整个系统的设计、管理和调度 更加困难，进而加剧了生产和销售之间的矛盾【l 羽。所以急需将优化技术应用于天然气集 输系统。 城镇天然气系统工程建设投资巨大，工程建成后不宜轻易改建或扩建，否则，将影 响城镇建设，造成人力、物力、财力的巨大浪费【4 】。因此，要保证城镇天然气的健康发 展，城镇天然气管网设计必须科学化。城镇天然气系统工程规划设计的目标：不仅要满 足用户和工艺设计的要求，而且要使城镇天然气系统工程所需的投资费用最少，保证整 个城镇天然气管网运行经济、安全和可靠。又由于城镇天然气系统不仅庞大，而且结构 复杂，限制条件又多，所以，依靠传统的手工，难以达到科学、合理、投资费用最少的 目标。因此，城镇天然气系统工程优化的设计必须利用先进的计算机技术，以及先进的 优化理论，以解决传统方法出现的计算精度低、计算效率低、规划设计难以实现优化等 问题【5 1 。 “最优化”永远是现代工程设计永恒的丰题。进入二十一世纪，随着优化技术、方案评 价技术、计算机技术的迅猛发展，为各工程领域实现最优化、自动化创造了条件；为城 镇天然气管网布局的优化设计研究提供了必要的理论基础和实现手段，利用这些理论和 手段必将减少城镇天然气管网系统工程的投资成本。城镇天然气管网系统是大系统，由 于其复杂性、多元性，其优化的工作量相当大。深入研究城镇天然气管网布局最优化设 计，走在信息化、数字化时代的前列，更新管网设计观念和模式，达到缩短设计周期、 提高设计质量、提高经济效益和社会效益的目的具有十分重要和深远的意义【6 】。 1 2 研究现状 对燃气管网系统的优化，国外比中国的研究较早，水平相对较高。在管道系统的优 化设计和运行方面，俄罗斯学者做了很多的努力，他们对输油管道的经济数学模型的选 择、参数的分析和计算、支线布局、以及长输管线沿线泵站布置进行了最优化，也对输 西安石油大学硕士学位论文 油管、油罐容量的配置问题进行了分析研究，他们将该方法运用到西伯利业的长输管道 设计中，取得了显著的经济效益 1 0 - 1 2 】。 哈克斯是第一个将优化方法运用到管道系统设计上的，在二十世纪六十年代，他为 了确定管道系统的最优条件，而利用库恩一塔克定理，但由于该方法较简单，所以在实 际的应用中很有限。后来，c h e e s m a n a p 奇斯曼提出一个关于管道优化设计的软件，这 个软件采用坐标轮换法来寻优达到费用最小。虽然对于一个有约束的非线性问题，坐标 轮换法并不是一个效率最高的算法，但是它却能使设计时间减少百分之七十，设计费用 减少百分之三十，进而也提高了设计质量【l 3 】。 1 9 7 0 年，br o t h f a r b 等利用动态规划方法，开发了一种合并技术，可以剔除那些不 经济的管径组合而无需枚举，使可能的管径组合数与节点数之间大体上呈线性关系而不 是按指数规律增加。这一技术为采用动态规划法对天然气管网进行最优化提供了一个有 效手段【4 】。 1 9 7 2 年，f l a n i g n 采用约束最速下降法给出了问题的算法，他是以管径和压缩机功 率为设计目标，在若干非线性约束条件下，将变量划分为状态和约束量，最后确定了状 态量和决策量间的相互关系【3 】。1 9 7 2 年，由美国纽约大学张希国教授提出s t e i n e r 算法， 通过引入外点( 称为s t e i n e r 点) ，使求得的网络最短树总长不大于图论方法求得的最短树 的总长，对解决具有较大规模的网络最短树问题十分有效。目前该方法常用于集输管网 的布局优化设计研究中 4 1 。 1 9 7 8 年，e d g a r 等人首先将广义简约梯度法应用于天然气输送网络的最优设计。此 项技术能同时确定压气站的数目、两座压气站之间的管段长度和管径以及压气站中压缩 机的操作工况( 进气压力、排气压力) 等设计变量的最优值，使管网投资和运行费用最低【4 1 。 1 9 7 9 年，b h a r k a r a n 布哈斯卡伦等人研究了天然气集输管网的优化设计。他们将集 输管网的优化设计问题划分为系统布局、节点位置以及直径分派三个子问题【3 】。 与国外相比，国内在管道系统优化设计方面的研究起步较晚，但却发展较快。 1 9 8 5 年，朱琦利用总折合费用最小来确定经济管径，并且给出了优化数学模型，但 是这种优化方法仅限于管径【3 】。 1 9 8 6 年，杨廷觉以输气管道年成本费用为目标函数建立输气管道经济模型，并采用 二维坐标轮换法求解，该模型及解法均较简单【6 】。 1 9 8 7 年，严大凡等通过将管径、原油输送温度、稀释比和泵站功率作为设计变量， 针对特重质原油管道的优化设计问题，提出将直接搜索的网络法用于解决该优化问题【6 】。 1 9 8 8 年，李书文、姚办华研究了天然气集输网络的最优化一静态设计。文中研究了 树枝状天然气集输网络静态数学模型，并用两种解法( 综合约束函数双速下降法和混合 罚函数法) ，既可用于现存系统又可用于新拟建的网络系统，具有一定的实际意义【6 j 。 l8 8 9 年，李书文进一步研究了气阳网络的优化布局问题，提出了简化优化法：k r u s k a l 算法、s t e i n e r 最短树法和p r i m e 算法，可为气田管网规划布局和辅助设计提供参考。在 2 第一章绪论 此之后，李书文等又继上述研究后，对气f f l 集输管网最优管径组合进行了研究，建立了 最优管径组合的系统模型，可同时求解出各管段的最优管径和各气井、节点的最优压力， 虽然结果令人满意，但是其中还有许多不足的地方仍然需要改进 6 】。 1 9 9 0 年，吴立峰提出了一种解决约束非线性混合离散变量的优化设计问题的方法， 即通过建立关于热含蜡原油管道系统优化设计的数学模型，最后通过利用混合离散变量 复合形法对该模型进行求解【6 j 。 1 9 9 2 年，蒲家宁通过将动态规划原理运用到远距离密闭输油管道的泵站和机组的优 化分析和计算中。吴长春、严大凡通过对热油管道的稳态优化运行的两级递阶数学模型 的建立，在这个数学模型中较低层次泵组合的优化被嵌入到较高层次管道输油温度的优 化中，并且利用动态规划法求解各站最佳泵组合，也利用罚函数法将输油温度的约束优 化问题模型转化为无约束优化问题，然后再通过p o w e l l 方向利用加速法求解 6 】。1 9 9 2 年，刘扬提出了数值求解法，通过将温度、压力约束处理为模糊约束，通过优化问题的 数学模型的建立，将模糊优化理论运用到油气集输管网系统优化设计这个问题中。后来， 刘扬等又提出了星式管网拓扑和环形集输管网布局的优化设计等问题 3 】。 1 9 9 3 年，江玉春通过对输气管道优化设计的数学模型的建立，利用广义几何规划法 对其进行求解，最终在理论上获得了的优化方案，并在这个优化方案的上根据工艺参数， 构造出多个该工程的预选设计方案，最后通过利用灰色关联分析法对整体进行评价，并 从中这些方案中优选出最佳方案，最终达到“优中选优”的目标 6 】。1 9 9 3 年，宋东星、肖 芳淳提出地下管道结构多目标可靠性灰色优化设计方法。本设计方法是通过利用可靠性 和狄色系统理论，并结合最优化技术，该方法也考虑了在管道结构优化设计过程中可能 遇到的白色、灰色、随机等影响因素【3 】。 1 9 9 5 年，郑清高提出了在忽略地形因素时，通过对引入s t e r n e r 点的集输管网，利 用s i 算法来确定井站以外的最短几何布局；然后，根据地形因素对其结果进行局部调整 或提出若干可行几何布局方案，最后通过关键路线法得出最优几何布局【3 】。 1 9 9 6 年，王清等通过在两条管道中选择最低进站油温为最低允许输油温度，将孤东 的两条管道作为一个输油系统进行考虑。本方法是通过用黄金分割法将孤岛首站总的输 油量合理分配给两条管道，实现了孤东管道全年压力最低，进而减少首站的节流损失， 提高孤东管道的输送量，最终达到节能降耗的目的。董正远、韩成才建立了热油管道优 化运行的数学模型，该数学模型是以单位能耗费( 热力费与动力费) 最少为优化目标，该 模型是通过对原油的摩擦牛热对沿线热力、水力特性的影响，以及在泵中原油的摩擦的 生热对输油温度的影响等方面进行考虑 6 】。 1 9 9 7 年，吴照云、项新耀、刘富润等人通过对集油系统的运行方式与用能关系进行 研究。赵洪激，刘扬，高林森等人研究了树状双管掺热水集输系统参数【6 】。 1 9 9 8 年，张增强、畅忠民提出了一种二维动态规划求解方法，用逐次逼近法进行降 维求解，这个动态规划求解方法是通过对秦京输油管道优化运行建立动态规划数学模型， 西安石油人学硕士学位论文 并将此数学模型看二维资源分配问题，也就是把全线总压头和全线总热负荷在各站之间 进行最优分配【6 j 。 1 9 9 9 年，蒲家宁、蒋明通过对管道顺序输送水力状态及工况调节的特殊性进行研究 之后，提出当油品“界面”处于管道的各特殊点时全线能量平衡方程和校核点压的通用计 算式，最终达到输送量最大的目标。刘伟、梁江通过将出站压力、管径、壁厚和管材作 为决策变量，来建立无分油支线的成品油管道工艺方案优化设计数学模型，这个模型属 于非线性混合整数规划问题，但是它没有给出利用何种方法对此数学模型进行求解【6 1 。 2 0 0 0 年，宫敬等人通过对成品油管道运行系统的分析，建立了以全线耗电费用最小 为目标函数的两个成品油管道优化运行数学模型( 定批量优化运行模型和定流量优化运 行模型) ，采用动态规划法求解全线各站泵机组与管路的最优匹配【6 】。李宏伟、谭家华为 提高海上边际油田开发的经济性，对海上边际油田群综合开发的海底油气集输管网系统 进行了分析，利用图论中的最小生成树方法和网络的加权中心问题，对海底管网布置进 行优化，得出了满意的投资方案【3 】。 2 0 0 1 年，李波、余红伟提出在进行输气管网的布局优化设计研究时，可借鉴供水管 网布局优化设计的一些先进技术和经验作参考【6 】。 2 0 0 2 年，徐严波等提出了用混合离散变量组合形法求解输油管道优化运行的数学模 型，该数学模型是根据多泵站多热站建立输油管道优化运行的目标函数【6 】。 2 0 0 3 年，刘震、潘斌通过对海底油气集输管网系统进行深入的研究，在达到管网系 统可靠性的基础上，提出了将费用最小作为优化设计的目标，然后再对系统进行优化设 计，最后得到满足该给定指标的费用最小的管网布置方案【6 】。 2 0 0 4 年，梁永图、宫敬等首先通过对最优化理论进行深入研究，以及在工艺过程及 管道沿线油品市场需求中对复杂成品油管道系统所有可能的因素进行分析，然后对成品 油管道优化运行建立数学模型，最后通过利用动态规划方法对该数学模型进行求解 6 】。 2 0 0 5 年杨毅、李长俊在研究遗传算法和模拟退火算法的基础上，根据两种算法的特 点，介绍了一种由模拟退火算法和遗传算法结合构成的混合遗传算法。结合实例，对混合遗 传算法在天然气管网运行优化中的应用进行了研究，求解了天然气管网运行优化的数学 模型。结果表明，混合遗传算法的优化结果比复合形算法提高了1 9 6 8 ，证明混合遗传 算法具有全域搜索、快速收敛的特点，更具有效性和实用性【6 ，14 1 。 2 0 0 6 年高兴国提出一种改进的遗传算法，该算法是在分析环状管网性能的基础上提 出的，利用该算法对环状管网进行优化设计，获得较好的效果【6 】。 2 0 0 7 年刘小坛提出对城市供燃气管网系统进行优化时，将可靠性考虑在内【1 3 】。郭和、 李玉星在建立了集输管网结构参数整体优化目标函数的基础上，采用遗传算法和序列二 次规划法进行经济管径的求解，并通过实例表明对复杂管网的结构参数优化问题，遗传 算法明显优于序列二次规划法。此外还采用遗传算法对集输管网结构参数进行了局部优 化，结果同样可行【l5 1 。葛翠翠和王常斌提出了管网布局优化模型，采用改进启发式求解 4 第一章绪论 方法、禁忌算法和边割法等算法对管网布局优化模型进行求解，使管网布局的优化结果 更加符合实际【17 1 。 2 0 0 9 年吕木英和范世东提出对环状燃气管网布局进行整体性优化【9 】。张艳萍、冯永 训和李玉星提出将最优化理论运用到加密井进入集输管网的最优化设计中【l6 1 。 1 3 论文的主要研究内容 本文针对城镇天然气管网优化的问题，在研究图论、燃气管网c a d 的理论分析与 应用等基础上，提出了改进的d i j k s t r a 算法，并将其与传统的d i j k s t r a 算法进行分析对比， 实现了城镇天然气管网气源节点合理优选，采用受限最小生成树算法对城镇天然气管网 的布局进行优化，仿真算例验证了算法的实用性和有效性，运用软件工程理论、混合编 程技术开发了“城镇天然气管网优化系统”。 主要内容包括： 1 城镇天然气管网c a d 的研究 通过对燃气管网c a d 的理论分析与应用的深入研究，得出城镇天然气管网优化的 两个重要方面是：城镇天然气管网的气源节点合理优选；城镇天然气管网的布局优化。 2 城镇天然气管网的气源节点的选择 通过对图论和燃气管网c a d 的理论分析与应用理论的深入研究，提出改进的 d i j k s t r a 算法，并将其与传统的d i j k s t r a 算法进行分析对比，实现了城镇天然气管网气源 节点合理优选，通过长庆燃气管网现场实验数据的仿真算例分析，验证了改进的d i j k s t r a 算法的有效性。 3 城镇天然气管网的布局优化 在气源节点、用户位置确定的情况下，通过对受限最小牛成树算法的深入研究，并 将其与p r i m 算法进行分析对比，实现了城镇天然气管网的布局优化，仿真算例验证了受 限最小牛成树算法的实用性。 4 “城镇天然气管网优化系统”的研制 采用可视化编程语言v i s u a lc + + 和f o r t r a n 9 0 的混合编程技术，充分发挥了v i s u a l c h 的可视化功能、f o r t r a n 9 0 计算精度高的功能，研究了v i s u a lc + + 和a u t o c a d 图形 接口设计，实现了管网分析计算与绘图一体化。研制“城镇天然气管网优化系统”软件。 5 模型应用 将长庆石油现场实验数据运用到“城镇天然气管网优化系统”中，通过对结果数据进 行分析，验证了“城镇天然气管网优化系统”的有效性和合理性，对长庆的城镇天然气管 网建设具有指导意义。 1 4 论文的框架内容 第一章：绪论，概要的介绍了国内外输配管网系统的发展过程、基本情况及存在的 问题，从而引出本课题应用研究的研究背景、研究意义、研究现状、本文的主要内容、 论文的框架内容。 西安石油大学硕士学位论文 第二章：图论和燃气管网c a d 的基本理论，针对本课题的研究内容，详细介绍了 与图论有关的一些理论知识，同时介绍了燃气管网c a d 的理论分析与应用，为城镇天 然气管网布局优化设计奠定基础。 第三章：城镇天然气管网布局优化的气源节点选择，通过对图论和燃气管网c a d 的理论分析与应用的深入研究，提出改进的d i j k s t r a 算法，并将其与传统的d i j k s t r a 算法 进行分析对比，结合长庆现场实验数据对城镇天然气管网进行气源节点的选择，对结果 数据的分析，验证了改进的d i j k s t r a 算法的有效性。 第四章：城镇天然气管网布局优化，通过对受限最小生成树算法的深入研究，并将 其与p r i m 算法进行分析对比，结合长庆现场实验数据，对城镇天然气管网的布局进行优 化，对结果数据进行分析，验证了受限最小生成树算法的实用性。 第五章：城镇天然气管网优化系统的设计与实现，采用软件工程理论，v i s u a lc + + 和f o r t r a n 9 0 的混合编程技术，研究了v i s u a lc + + 和a u t o c a d 图形接口设计，实现了管 网分析计算与绘图一体化。开发了“城镇天然气管网优化系统”系统，用长庆现场实验数 据验证了系统的实用性和合理性。 第六章：结论与展望，对本论文的研究内容进行了总结，同时对论文的后续工作进 行了展望。 6 第二章图论和燃气管网c a d 的基本理论 第二章图论和燃气管网c a d 的基本理论 本章详细介绍图论相关理论知识，及燃气管网c a d 的理论分析与应用理论。 2 1 图论的相关基础理论 2 1 1 图论的概念 图论中所谓的图是指某类具体事物和这些事物之间的联系，如果我们用点表示具体 事物，用线段表示两个具体事物之间的联系，那么，一个图就是由一个表示具体事物的 点的集合和表示事物之间联系的线段的集合所构成。 图( g r a p h ) 是一种数据结构，在图形结构中，结点之间的关系可以是任意的，图中 任意两个数据元素之间都可能相关。 以g 表示一个图，y ( g ) 表示图g 的节点集合，e ( g ) 表示图g 的线段集合，则图可 定义为g = ( 矿，e ) ，简而言之，图就是以点和边组成的几何图形。 一条边的端点称为与这条边关联( i n c i d e n t ) ，反之，一条边称为与它的端点关联。 因此，图的最本质内容实际上就是端点和边的关系。 燃气管网图因为具有这种关联的二元关系，因此，可把管网抽象成一个由点和边组 成的几何图形，并可作为数学模型，且具有直观性1 2 1 1 。 2 1 2 有向图和无向图 在图中的数据元素通常称做顶点( v e r t e x ) ，v 是顶点的有穷非空集合：豫是两个 顶点之间的关系的集合。若 v r ，则 表示从v 到w 的一条弧( a r c ) ，且 称v 为弧尾( t a i l ) 或初始点( 1 n i t i a ln o d e ) ，称w 为弧头( h e a d ) 或终端点( t e r r a ma l n o d e ) ，此时的图称为有向图( d i g r a g h ) 。若 v r 必有 v r ，即豫是对称 的，则以无序对( ，w ) 代替这两个有序对，表示v 和w 之间的一条边( e d g e ) ，此时的图称 为无向图( u n d i g r a g h ) 。如下图2 1 和图2 2 所示i 。 图2 1 有向图g l 图2 - 2 无向图g 2 图2 1 中g 1 是有向图，定义此图的谓词p ( v ，w ) 则表示从v 到w 的一条单向通路。 g l = ( k ， 4 ) ) 其中： k = v i ，v 2 ，v 3 ，v 4 a l = ， ， ， ) 图2 2 中g ，为无向图。 g 2 = ( ， 易) ) 7 西安石油大学硕士学位论文 其中： = “ 1 2 1 ，v 2 ，v 3 ，v 4 ，v s ) e 2 = ( m ，v 2 ) ，( h ，屹) ，( v 2 ，v 3 ) ，( v 2 ，v s ) ，( v 3 ，k ) ，( v 3 ，v 5 ) ) 2 1 3 图论的基本术语 1 图的分类 通常用n 表示图中顶点数目，用e 表示边或弧的数目。在下面的讨论中，我们不考 虑顶点到其自身的弧或边，即若 v r ，则1 ，1 ，那么，对于无向图，e 的取值 范围是0 到n ( n 一1 ) 2 。对于有向图，e 的取值范围是0 到n ( n 一1 1 2 1 】。 ( 1 ) 有向图：每条边都是有向边的图称为有向图。 ( 2 ) 无向图：每条边都是无向边的图称为无向图。 ( 3 ) 混合图：如果在一个图中一些边是有向边，而另些边是无向边，则称这个图 是混合图。 ( 4 ) 完全图：有n ( n 一1 ) 2 条边的无向图称为完全图( c o m p l e t e dg r a p h ) 。 ( 5 ) 有向完全图：具有n ( n 1 ) 条弧的有向图称为有向完全图。 ( 6 ) 稀疏图：有很少边或弧( 如e 是有向线图，其中v = “，v 2 ，屹) ，并假定各结点已经有了 从v 1 到屹的次序。定义一个矩阵a 其中各元素a 玎为 口矿=1翥羹三：三主e(2-10 e(2-1， 嘞2 1如果 诺 j 称这样的矩阵是图的邻接矩阵。 从定义可以看出，有向线图g = 的邻接矩阵不唯一而与矿中的元素标定次序 有关，对于y 中各元素不同的标定次序可得到同一图g 的不同邻接矩阵。 邻接矩阵的概念可以推广到无向线图，只需将以上定义中的 换成( v ，1 ，) 即 可，无向图的邻接矩阵是对称的。 2 网的邻接矩阵表示 网的邻接矩阵可定义为 删俨肚瓠p 黧p 搠( 2 - 2 ) l 0 0 例如图2 - 6 列出了有向网g 。和它的邻接矩阵a 6 】 6 】。 西安石油大学硕士学位论文 4 6 】 6 1 = 7 0 0o 。 5 ( a ) 有向网g 6 ( b ) 邻接矩阵 图2 - 6 网及其邻接矩阵 2 2 燃气管网c a d 2 2 1 概述 c a d ( c o m p u t e ra i d e dd e s i g n ) 即计算机辅助设计的缩写，c a d 技术是计算机与工 程设计紧密结合的综合应用技术，国外把c a d 技术作为现代化设计的方法和手段，称 它为新技术起飞的引擎。 所谓燃气管网工程设计是指从确定燃气供应区域范围和技术要求开始，直到形成为实 现该工程所必需的全部信息( 图纸、说明书、计算书、预( 概) 算书和材料设备明细表 等) 为至的一系列有序活动。计算机辅助设计燃气管网是由计算机参于燃气管网设计过 程并具有自动设计性质的一种技术。该技术包括利用计算机研究，分析或改进一个工程 设计的任何类型的活动。 若计算机存储有供设计燃气管网用的各种数据和软件，再配备图像显示和绘图仪等终 端设备，就可由计算机对燃气管网进行各种分析计算，并自动绘出管网设计图和编写材 料明细表，以及预( 概) 算。当设计人员学会使用燃气管网的计算机辅助设计系统( 以 下简称燃气管网c a d ) ，将大大提高工作效率和设计质量，因而使设计人员的主要精力 放在具有创造性的工作上【2 2 1 。 2 2 2 燃气管网c a d 系统的类型 燃气管网c a d 系统可以采用交互式设计系统和非交互式设计系统。 交互式设计系统是指具有人机对话功能的设计系统，它的设计过程需要人的直接参 与，仍然以人为中心，以人一机对话的交互设计方式进行工作。 非交互式设计系统是指不具有人机对话功能的设计系统，它在设计过程中基本上不要 人的参与。计算机会根据用户编制的程序自动地完成各个设计步骤，直到获得最优解为 止，所以这是以计算机为中心的设计系统。 现代化c a d 系统的基础是交互式计算机绘图，这是一个面向用户的系统，在这个 系统中，计算机被用来生成、改进和显示数据以及图形，用户在系统中是一个设计人员， 可以通过任何输入装置向计算机输入数据和命令。计算机同用户之间的通讯联系是通过 显示终端实现的，设计人员通过调用存储在计算机中的软件，可以在显示屏上牛成数据 1 2 9 6 8 3 第二章图论和燃气管网c a d 的基本理论 和图形1 2 2 i 。 2 2 3 燃气管网节点方程的矩阵形式 管网图可以用相应的网络图来抽象地加以表达，而网路图是以点( 节点) 和线( 支 路) 组成的，而节点和支路的关系又可以用关联矩阵加以描述，关联矩阵描述了图的 全部特性。把燃气管网的全部参数加在网路图上，图就成为分析燃气管网的一个方法， 即，管网的全部特性参数均可用矩阵来表达。 管网全部特性参数之间的关系主要表现在节点连续性方程和管道水力计算公式 上，为此，下面分别讨论它们的矩阵表达式。 1 管网的节点连续性方程的矩阵表达式 由传统的节点连续性方程可知：对任何集合参数的管路网络，流入与流出管路网 络中任一节点的所有支路的燃气流量的代数和为零。 设流入节点的支路流量为负，流出节点的支路流量为正，则对图2 7 网络图中的各 节点。 9 6 ，饩 q s ，p 5 q 4 ，p 4 图2 - 7 网络图 其中：圆圈中的数字表示用气节点号，带箭头线段中间的数字表示管段号，p 表示 支路( 管) 压力降( 压力损失) t 。q 表示支路( 管) 流量；p 表示各节点相对于基准点 的压力降：q 表示节点向用户输送的流量。可写如下节点方程组： 将方程组( 2 - 3 ) 写成矩阵形式， 节点1 一q l + q 2 = 一q l 节点2 一q 2 一q + q 5 = - q 2 羔童三，。q s q ，( 2 - 3 ) 节点4q 6 一q 7 = 一q 。 节点5 珐一幺+ 易= - q 5 节点6 q l + q 4 = 吼 如下矩阵( 2 4 ) 所示： 1 3 两安石油大学硕士学位论文 一l10000 0 iq 1 o l lo 1oo0 q 2 oooo 一1 一loif q 3 oo o oo1 一l8 q 4 oo 1 一lool 降 。轻 一9 1 一9 2 一9 3 一9 4 一9 5 q 6 ( 2 - 4 ) 其中：系数矩阵的行表示图2 7 管网中的用气节点号，列表示管段号。 ( 2 4 ) 式左边的系数矩阵就是图2 7 管网所示的有向图的完全关联矩阵a ，如定义 支路( 管) 的流量为向量q ，则有 。 q = q 。，q 2 ，q ，绕，q 5 ，q 6 ，q ，】7 定义节点向用户输出的流量向量为q ，则有 q = - q l ，- q 2 ，- q 3 ，- q 4 ，- q 5 ，+ 9 6 】r 于是( 2 4 ) 可写为 彳o q = q( 2 5 ) 事实上，对任何集合参数的管路网路，式( 2 5 ) 均成立。即对于有1 个节点， 条支路的管网，可建立n 。x n 阶完全关联矩阵a n 。 从式( 2 3 ) 可以看出，4 矩阵的诸行是线性相关的，因此，它的各列内元素之和 为零，即以中只有5 个线性无关的行，也就是a 的秩等于5 。因此，可以将( 2 3 ) 式 划去一行。一般情况下，将第6 行划去，从而( 2 5 ) 式变成 彳q = q( 2 6 ) 对任何集合参数的管路网路，( 2 6 ) 式均成立，其中 a = 一ll 0一l 0 o oo 0o 00 10 0o oo l一1 0oo 1 oo l10 o1一l 00 l q = q 。，q 2 ，q 3 ，q 。，q ，哦，q ，】2 q = 卜q l , - - q 2 ，- q 3 ，- q 4 ，- q 5 】r 节点6 为参考节点。 对于有1 个节点，条支路的管网，可建立( n i 一1 ) x n 阶完全关联矩阵a 。 进行燃气管网分析时，一般将气源所在位置的节点选作参考点( 或称作基准点) 。 对多气源的管网，则任选其中一个气源节点作为基准点，并在网络图上将基准点编号按 序排在其它节点之后。 2 管段( 支管) 压力降方程组的矩阵表达式 燃气管网中，任一支管e = f ，j ) 的压力降方程为 1 4 第二章图论和燃气管网c a d 的基本理论 p e 2 p t p j 根据( 2 7 ) 式，对图2 7 中各支路，可写出如下支路压力降方程组 f 支路l p 6 一p l = 只 1 支路2 p l p 2 = 最 1 支路3 p 5 一p 2 = 只 支路4 p 6 一p 5 = 只 1 支路5 p 2 一p 3 = 只 1 支路6 p 4 一p 3 = 只 【 支路7 p 5 一p 4 = 弓 将( 2 8 ) 式写矩阵形式 一10 11 o一1 00 ol oo 00 0 o 0 00o oo1 oo 一1 1o0 一llo o一1l e 只 b 只 忍 圪 只 ( 2 - 7 ) ( 2 - 8 ) ( 2 9 ) 比较( 2 4 ) 式和( 2 9 ) 式可看出：( 2 9 ) 式左边的系数矩阵为名；( 2 9 ) 式左边的系 数矩阵诸列线性相关，即管中只有5 个线性无关的列。于是，划去第6 列，余下的5 列恰好等于彳r 。因此，( 2 - 9 ) 式可以改写成 a 7 p = p( 2 - 1 0 ) 其中 如设 彳r = 一10 l一1 0一l 00 o1 00 0o oo0 oo0 oo1 0ol 一10o 一110 ol1 p2 憎i p 2p 3p 4p 5 l i i _ p = k 罡be 4 只圪与r 对于有。个节点，条支路的管网，彳r 是一个n ( n ，一1 ) 阶矩阵。 3 管段流量与管段压力降线性关系的矩阵表达式 管段流量q 和管段压力降尸的关系可综合表达为 尸= 口q x( 2 - 1 1 ) 1 5 a n 儿肌既仇 l 0 o 1 o o 0 西安石油大学硕士学位论文 乳南 则 q = g p ( 2 - 1 2 ) ( 2 1 3 ) g 为管段的导纳值。 ( 2 1 1 ) 式反映了q 与p 的非线性关系，经( 2 1 2 ) 式转换成线性关系( 2 1 3 ) 式。对 于图2 7 网络图 g = p = 陋只只只只忍br q = q ，q ，q 3 ，幺，g ，q 6 ，q 7 】r 显然，对于有条支路的网络图，可建立n n 对角形方阵g ，n 1 矩阵p ，1 矩阵q 。 4 燃气管网节点方程的矩阵形式 综上所述，已经建成了表述燃气管网网络拓扑性质的三个表达式， ( 2 1 0 ) 式和( 2 1 3 ) 式。将( 2 - 1 3 ) 式代入( 2 - 6 ) 式得 a g p = q 再将( 2 一l o ) 代入( 2 一1 4 ) 式得 即( 2 6 ) 式， ( 2 1 4 ) a g a 7 p = q( 2 - 1 5 ) ( 2 1 5 ) 式是燃气管网节点方程的矩阵形式，a g a r 称作节点导纳矩阵，如设 y = a g a r ( 2 1 6 ) 则( 2 1 5 ) 式变成 y p = q( 2 1 7 ) 对于燃气管网而言，从节点向用户输出的流量q 在负荷计算和管网布置时均为给 定值， ( 即q 为常数项) ，而节点相对于基准点( 一般为气源压力节点) 的压力降p 是求解的目标向量。问题归结为求解】，矩阵，由式( 2 一1 6 ) 可知，】，矩阵是一个l l 阶 方阵，因此，管网中任意节点的p 值均可由( 2 1 7 ) 式解出，然后代入( 2 1 0 ) 式解出 管段压力降p 向量，再将尸代入( 2 1 3 ) 式解出管段流量q 向量。 2 3 本章小结 本章丰要针对本课题的研究内容，详细介绍了与图论有关的一些理论知识，同时介 绍了燃气管网c a d 的理论分析与应用，为城镇天然气管网布局优化设计奠定基础。 1 6 0 0 o o 0 0 q 0 0 o o o 瓯o o 0 0 0 g 0 0 o o o q 0 0 o 0 0 g o 0 0 0 0 嚷0 0 0 0 o q 0 0 0 o 0 0 第三章城镇天然气管网优化的气源节点选择 第三章城镇天然气管网优化的气源节点选择 在图论的基础上，深入研究d i j k s t r a 算法，将修复矩阵应用于此算法中，提出了改进 的d i j k s t r a 算法，并结合长庆现场实验数据，将这两种算法用于燃气管网的气源节点的 选择。并且通过仿真算例验证改进的d i j k s t r a 算法的有效性。 3 1 引言 目前燃气管网布局优化问题主要是指在给定气源和用户的地理位置后，确定燃气管 网的最优拓扑结构【8 1 。由于气源结点的选择与拓扑结构优化有很大的关系，不同的气源 结点有不同的拓