枝状流体网计算机求解新方法

D0I:10.13374/i.issn1001-053x.2002.01.053 第24卷第1期 北京科技大学学报 VoL24 No.1 2002年2月 Journal of University of Science and Technology Beijing Feb.2002 枝状流体网计算机求解新方法 彭力”武玉钊”涂序彦》余宝法) 1)北京科技大学信息I程学院，北京1000832请华同方人环，北京100083 摘要针对枝状流体网的特点，在比较了以往传统计算方法后，提出了一种与常规完全不 同的方法，即不采用矩阵或方程组而棋仿人的思维过程使用逐点暴积的线性方法，大大提高了 计算的效率和精度. 关绩词枝状流体网：网络建模：计算机求解：逐点系积法 分类号TP183 1枝状流体网 关联矩阵”，用矩阵求解或用解方程组的方法， 下面比较几种矩阵求解的方法. 供热网络是一种以流体为介质的网络，介 (1)直接高斯消去法.用逐次消去列元素的 质运行于地下，其压力、流量、阻力、热量等参数 方法把方程化成与其等价的三角形方程组，这 很难准确获得，只有通过设在各个热力站的仪 种方法的优点是程序短小精悍，计算结果准确， 表可以测得这些末梢节点的参数值，进而估算 占用存储单元少，缺点是计算时间长，随着方程 其他节点、管段上的参数.目前，广泛使用的供 组阶数的提高，程序计算时间以指数级数速度 热系统是一种称为“枝状网”的单热源供热网络 增加，有可能产生“数据风暴” 形式，结构类似数据结构中定义的“树型结构” (②)高斯赛德尔迭代法.主要是将方程组 它要求有一个根节点且子节点只有惟一的父节 AX=B改写成X=GX+F,即X=GX+F,并以此式 点，如图1所示. 进行迭代计算.该方法的优点是程序短小，占用 存储单元少.在正常情况下计算时间较短，但随 着方程组结束的提高，计算时间略有增加.缺点 热源1 8 是计算过程需要迭代，而且在某些非正常情况 下，如病态矩阵等，这一方法的收敛性差，影响 图】枝状网片断示例图 了计算结果的准确性和计算速度. Fig.I Confguration of part branch-shape flow network (3)双因子分解法.建立在三角分解法基础 图1是一热源为某生活小区供热的片断管 ·上专门针对大型稀疏线性矩阵方程组的直接求 网图.设热源为节点1，圆圈代表热力站.这种 解法.由于考虑了矩阵的对称性和稀疏性，因 供热问题是当已知各热力站的某一参数时，如 此，双因子分解法的计算速度较快.但该方法的 预处理和实时计算程序结构复杂、庞大.其子程 节点2,4,6,7,8的流量g,g,g6,g,g,需要求出节 序的长度约为高斯消去法的5到7倍，其模拟 点3,5的流量g,8s. 定序结果需要18个数组存储. 2枝状网的常规解法比较 (4)改进型高斯消去法.在高斯消去法的基 传统的做法，往往借助于矩阵运算，即借助 础上，增加了对矩阵对称性、稀疏性处理.由于 于网络图论的研究成果，将流体网络问题转化 流体网络对应的系数矩阵为对称、稀疏矩阵，只 为矩阵运算问题，进而用数学的手段求解各种 要节点编号选择合理，则矩阵的非零元素将主 矩阵. 要集中在对角线附近.对于这样的矩阵，采用上 图1中共有8个节点，7个支路，可以建立. 述处理方法，可大大节省计算时间，计算速度虽 和双因子分解法差不多，但程序相对简单许多 收稿日期2001-07-06彭力男.35岁，副数授 *国家自然科学基金资助课题(No.60075012) 以上几种方法会因矩阵规模庞大而无法求

第 24 卷 第 1期 20 2 年 2 月 北 京 科 技 大 学 学 报 OJ u r n a l o f U. vle 比 l yt o f s e贻 n e e a o d eT e h n o如 gy Be IJ i . g 、勺 L2 4 N o . l eF b . 20 2 枝状流体网计算机求解新方法 彭 力 ” 武玉 钊 ” 涂序彦 ” 余宝法 ” l )北京科技大学信息工程学院 , 北京 10 0 83 2睛华同方人环 , 北京 10 0 0 83 摘 要 针对枝状流体网的特点 , 在比较了以往传统计算方法后 , 提出 了一 种与常规 完全不 同的方法 , 即不 采用矩 阵或 方程 组而模仿人的思维 过程使用 逐点 象积的线性 方法 , 大大 提高 了 计算 的效 率和精 度 . 关扭 词 枝状 流体网 ; 网络建模 ; 计算机求解 ; 逐 点 象积 法 分 类号 T P 15 3 1 枝状流体网 供热 网络是一 种 以流体 为介质 的网络 , 介 质运行于地下 , 其压力 、 流量 、 阻力 、 热t 等参数 很难 准确获得 , 只有通过设在各个热力站 的仪 表可 以测得这些末 梢节点的参 数值 , 进而估算 其 他节点 、 管段上的参数 . 目前 , 广泛使用 的供 热 系统是一种称为 “ 枝状 网 ” 的单热源供热 网络 形 式 , 结构类似数据结构 中定义 的 “ 树 型结构 ” . 它 要 求有一个根节点 民子 节 点 只有惟 一 的父节 点 , 如 图 l 所示 . } 、 〔 一 二 · 圈 1 枝状 网片断 示例 圈 F i .g I C o n 飞 u .r 目0 . o f aP rt b ar . c b心卜a 尹口。 , 二wt o r k 图 1是一热源为某生活小 区供热 的片断管 网图 . 设热源为节点 l , 圆圈代表热力站 . 这种 供热问题是 当已知各热力站的某一参数时 , 如 节点 2 ,4 6 , 7, 8 的流量承 , g4 , g6 , 乡 ,承 , 需要求 出节 点 3 , 5 的流量矛 , .gs 2 枝状网的常规解法 比较 传统 的做法 , 往 往借助 于矩 阵运算 , 即借助 于 网络图论 的研究成果 , 将 流体网络 问题转化 为矩 阵运 算问题 , 进 而用数学 的手段求解各种 矩阵 . 图 1 中共有 8 个节 点 , 7 个支路 , 可 以 建立 收稿 日期 20 0 一刁7 es O6 彭力 男 , 3 5 岁 , 副教授 * 国家 自然 科学基 金资助 课题( N o . 6 0 0 7 501 2) 关联矩阵川 , 用矩阵求解或用解 方程组 的方法.lz] 下 面 比较几种矩阵求解 的方法 . ( l) 直接高斯消去法 . 用逐次 消去列 元素的 方法把方程化成与其等价 的三 角形方程组 . 这 种方法 的优点是程序短小精悍 , 计算结果准确 , 占用存储单元少 . 缺点是计算时间长 , 随着方程 组阶数的提高 , 程序计算 时间以 指数 级数速度 增加 , 有可能产生 “ 数据风暴 ” . (2 ) 高斯赛德 尔迭代 法 . 主要是将 方程组 月火导召改写 成=X G X干F , 即广 ,= G X 盘+ 尸 , 并 以此式 进行迭代计算 . 该方法的优点是程序短小 , 占用 存储单 元少 . 在正 常情况下计算时间较短 , 但随 着方程组结束的 提高 , 计算时间略有增加 . 缺点 是计算过程需要迭代 , 而且 在某些非正常情况 下 , 如病态矩 阵等 , 这 一 方法的收敛 性差 , 影响 了计算结果 的准确性 和计算速度 . (3 )双 因子分解法 . 建立 在共 角分解 法基础 _ 上专门针对大型 稀疏线性矩阵方程组 的直接求 解法 . 由于考虑 了矩 阵的对称性和 稀疏性 , 因 此 , 双因子分解法的计算速度较快 . 但该方法 的 预处理和实时计算程序结构复杂 、 庞大 . 其子程 序的长度约为 高斯 消去 法 的 5 到 7 倍 , 其模拟 定序结果需要 18 个数组存储 . (4 )改进 型 高斯 消去法 . 在高斯消去 法的基 础 t , 增加 了对矩 阵对称性 、 稀疏性处理 . 由于 流体网络对应 的系数矩 阵为对称 、 稀疏矩阵 , 只 要 节 点编号选择合理 , 则矩 阵的 非 零元素将 主 要集 中在对角线附近 . 对于 这样的矩阵 , 采用 L 述处理方法 , 可大大节省计算时间 , 计算速度虽 和双 因子分解法差不 多 , 但程序相对简单许多 . 以上 几种方法会 因矩阵规模 庞大 而无法求 DOI: 10. 13374 /j . issn1001 -053x. 2002. 01. 053

·84 北京科技大学学报 2002年第1期 解或求解速度很慢，且占用空间太多，其计算速 外特性及管网的阻力特性系数时，流体网络的 度都将指数级或级的O(n),编程实现比较庞 流量及压力分布即可求出，可以模拟流体网络 大.因此，需要找到一种摆脱矩阵或方程组求解 的各种运行工况；（⑤）调节阀的选型：(6)系统扩 的方法，使网络计算处于代数级O(),这样，不 供影响分析及对策研究等 论网络多大计算起来都不会出现困难.下面介 绍一种基于拟人推理的逐点累积求解枝状网的 程序初始化 新方法. 取一个节点 3枝状流体网新解法 是叶节点 从求解枝状流体网络问题及通常的研究其 加到其父节点上 调节方法中发现如下规律：(1)任何一个枝状有 向流体网络中除根节点之外的任意一节点的父 父节点是根节点 节点惟一；(2)任何一个枝状有向流体网络的任 一节点（除根节点外）有且仅有一条路径可以寻 所有节点取完工 N 找到根节点：(3)实际运行调节方法中，在对每一 Y 环路的调节时忽略其对网络中其他环路的影 图2枝状流体网程序流程图 响.下面以图1为例说明新算法的思想. Fig.2 Computer flow chat for branch-shape flow network 图1要求已知各站的流量，计算全网的流 量分布.设根节点（热源）为源，各叶节点（热力 4算例与结论 站)为汇.每个叶节点的流量均来自于根节点， 逐点累计求解网络新方法求解，结果很满 那么连接于每个叶节点与根节点之间的所有管 意该法充分考虑了枝状流体网的特点，对拥有 路均含有该叶节点的流量.可构造算法为：从每 102个热力站大网用简单、高效，在枝状流体网 一个叶节点出发，分别逐次沿着其父节点的方 计算方面摆脱了基于矩阵的计算思路，为其他 向搜索，每搜索到一个管路就将该叶节点的流 网络计算探索出了一条新路. 量加到这个管路上，直到寻到根节点.当所有叶 节点均把其流量加到了与根节点相连的所有管 参考文献 路上之后，整个网络的流量分布就求出来了.算 1江忆，流体网络求解M北京：清华大学出版社，1993 法编程框图如图2. 2杨绍祺，谈根林.稀疏矩阵一算法及其程序实现M0 该算法除能完成全网的流量分布计算外， 北京：高等教育出版社，1985 3谢茂清.热工流体网络的月动建模算法清华大半 还可以解决以下问题：(I)已知参考点的压力及 学报，1997,37(6)：17 各管路的压降，计算全网的压力分布；(2)管网管 4刘靖.供热系统的计算机模拟分析调节法研究[]，节 径的确定，即根据管网的拓扑结构及流置分布， 能，2000(2)：3 则可初选各管段管径：(3)最大管道输配能力的 5吴靖仿真培训系统体网络的动态仿真模型与实时 确定：(4)网络运行工况模拟分析，即当已知泵的 仿真方法综述[】.电站系统工程，1998,14：49 New Computer Resolution Method on Branch-Shape Flow Network PENG Li",WU Yuzhao",TU Xuyan", YU Baofa 1)Information Engineering School,UST Beijing,Beijing 100083,China 2)Tsinghua Tongfang Renhuan,Beijing 10084,China ABSTRACT Network calculation is still an important question.By being compared with traditional me- thods,a new method is proposed.The new coputer resolution method uses a linear accumulation method which imitating human mind activity to resolve the network point by point.The results show that it gets a good result. KEY WORDS branch-shape flow network;network modeling;computer resolution;accumulation point by point

北 京 科 技 大 学 学 报 2 0 2 年 第 1期 解或求解速度很慢 , 且占用空 间太多 , 其计算速 度都将 指数级或矿级的 口(n 今 , 编程实现 比较庞 大 . 因此 , 需要找到一种摆脱矩阵或方程组求解 的方法 , 使网络计算处于 代数级口(n) , 这样 , 不 论 网络多大计算起来都不会 出现 困难 . 下面 介 绍一种基 于拟人推理 的逐点累积求解枝状 网的 新方法 . 外特性及管 网的阻力特性 系数 时 , 流体 网络 的 流 t 及压力 分 布即 可求 出 , 可 以 模拟流体 网络 的各种运行 工况 ; (5) 调 节阀 的选型 ; (6 ) 系统 扩 供影 响分析 及 对策研究等 . 程序初始化 3 枝状流体网新解法 从 求解枝状流体网络问题 及通常 的研究其 调节方法 中发现如下规律 : (l) 任何 一个枝状有 向流体网络 中除根节点 之外 的任意一节点 的父 节点惟一 ; (2 )任何 一 个枝状有 向流体 网络 的任 一 节点( 除根节点外 )有且仅有一条路径 可以寻 找到根节点 ; (3) 实际运 行调节方法 中 , 在对每一 环 路 的调 节 时忽略 其对 网络 中其 他环路 的影 响 . 下面 以 图 1 为例说明新算法 的思想 . 图 1 要求已知各站 的流量 , 计算全 网的流 量分布 . 设根 节点 (热源 )为源 , 各叶节点 (热力 站 ) 为汇 . 每个 叶节点 的流量均来 自于根 节点 , 那 么连接于 每个 叶节点与根节点之间的所有管 路均含有该叶节点 的流t . 可 构造算法为 : 从每 一 个叶 节点出 发 , 分别逐次沿着其父节 点的方 向搜索 , 每搜索到一 个管路就将该 叶节 点的流 量加 到这个管路上 , 直到寻到根节点 . 当所有叶 节点均把其流盆加到了与根节点相连 的所有管 路上之后 . 整个 网络的流量分 布就求 出来 了 . 算 法编程框 图如 图 .2 该算法 除能完成全 网的流量分布计算外 , 还可 以解决 以下 问题 : ( l) 已 知参考点的压力及 各管路的压降 , 计算全网的压力分布 ; (2) 管 网管 径 的确定 , 即根据管 网的拓扑结构及流 t 分布 , 则可 初选各管段 管径 ; (3 )最大管道输配能力 的 确定 ; (4 )网络运行工况模拟分析 , 即 当已知泵 的 圈 2 枝状流体网租序流 租圈 F ig · 2 C o m p u te r fl o w e 胜. t fo r b ar n e 卜. 血a 件 fl o w . e幻即 o r k 4 算例与结论 逐 点累计求解 网络新方法求 解 , 结果很满 意 . 该法充分考虑 了枝状流体 网 的特点 , 对拥有 10 2 个 热力站大网用简单 、 高效 , 在枝状流体 网 计算 方面摆脱 了基于矩阵 的计算思 路 , 为其 他 网络计算探索 出了一条新路 . , 考 文 献 1 江忆 , 流体网络求解 M[ 】 . 北京 :清华大 学出版社 , 19 93 2 杨绍棋 , 谈根林 . 稀疏矩 阵一算法及其程序实现 l阅 . 北京 : 高等教 育出版社 , 19 85 3 谢茂清 . 热工 流体网络的 自动建模 算法 [J] . 清华大学 学报 , 19 9 7 , 37 ( 6 ) : 17 4 刘靖 . 供热系统 的计算机模拟分析调节法 研究 J[] . 节 能 , 2 0 0 (2 ):3 5 吴靖 . 仿真培训 系统流体网络的 动态仿真模型与 实时 仿真方 法综述 [J] . 电站 系统工程 , 19 98 , 14 : 49 N e w C o m P ut e r R e s o lut i o n M e t h o d o n B arn e h 一 S h ap e F l o w N e tw o rk 尸石刀口 i’L ), 甲 U h招 h a ’o) , r U 尤妙a n ,) YU B a oj 份, l ) I n of mr at i o n E叩i朋e inr g S c h o l , U S T B e ij i n g , B e ij i n g 10 0佣 3 , C h ian Z )sT i n gh u a OT n gf 如 g R e hn aun , B e ij in g l 0 0 84 , C ih n a A B S T R A C T N e tw o r k e a l e u l at i o n 1 5 s t ill an im P o rl ” n t q u e s t i o n . B y b e i n g e om P are d w it h tr a d it i o n a l m e - ht o d s , a n e w m e ht o d 1 5 Pr o Po s e d . T h e n e w co Put e r er s o lut i o n m e ht o d u s e s a lin e ar a e e um u l at i o n m e th do w h i c h 而iat in g h 山m an m in d a ct i v iyt ot r e s o l v e het n e 勺四 o r k po int by P o int . T七e er su lt s hs ow ht a t lt g e t s a g o do r e s u lt . K E Y WO R D S b r an e h 一 s h a Pe fl o w n e wt o kr : n e wt o r k nt o d e l ign : c o m P uet r er s o lut i o n : ac c nUI ul at i o n Po iin by P o i n t