（电力系统及其自动化专业论文）大规模电网潮流计算关键技术研究.pdf

a b s t r a c t p o w e rs y s t e ms i m u l a t i o ni sa ne f f e c t i v ea n dn e c e s s a r yt o o l i np o w e rs y s t e m a n a l y s i s d u et o t h er a p i de x p a n s i o no fc h i n a sp o w e rs y s t e m a sw e l ia st n e i n c r e a s i n gc o m p l e x i t y ，t h es i m u l a t i o nw o r k l o a de s c a l a t e ds h a r p l y a t t h es a m et l m e ， a st h ec o n c e p t i o no fo n l i n ep o w e rs y s t e md y n a m i cs e c u r i t ya s s e s s m e n t a n dc o n 仃oll s p r o p o s e da n da p p l i e dg r a d u a l l y , t h e r ea r ec o m p e t i n gd e m a n d sf o rt h er e a l 。t l m e o r e v e ns u p e r - r e a l - t i m e p o w e rs y s t e ms i m u l a t i o n t h ec a i c u l a t i o no ft r a n s i e n ts t a b i l i t yo fp o w e rs y s t e m i sat i m e - c o n s u m i n gt a s k m o s tc o m p u t a t i o n a lt i m eh a sb e e ns p e n t0 nt h es o l u t i o no fs p a r s el i n e a re q u a t l o n s ，s o i t i so fs i g n i f i c a n c et os p e e du pt h ec o m p u t a t i o np r o c e s sb ya d o p t i n gt h es p a r s e t e c h n i q u e t os o l v et h e s ep r o b l e m s ，t h i sp a p e rs t u d i e do nt h es u b j e c t s o tp o w e r t l o w a i g o r i t h m s o m ei m p o r t a n tc o m p o n e n t s f o rs u c c e s s f u lp r o g r a ml m p l e m e n t a t l o na r e a s f o i l o w s ：t h eo p t i m i z e ds o r t i n ga l g o r i t h m o fn o d e s ，t h ep a r t i t i o n i n ga n d5 0 r t i n g a l g o r i t h m o fn e t w o r k s ，s p a r s e m a t r i xt e c h n i q u e s ，t h eo p t i m i z e dp o w e rf l o w c a l c u l a t i o np r o g r a mc o m p o n e n t s e t c a no p t i m i z e dp o w e rf l o wp r o g r a mi s c o d e du s i n gt h es o r t i n g ，p a n l t l o n m g a l g o r i t h m sa n d t h es p a r s et e c h n i q u em e n t i o n e da b o v e t h er e s u l t sw e r ec o m p a r e dt 0 t h ei n t e im k lc o m m e r c i a ls o f t w a r eo nt h es h a n x ip r o v i n c ea n d n o r t hc h i n ap o w e r g r i d w h i c hs h o w st h ep o w e rf l o wc a l c u l a t i o ns p e e di s e n h a n c e dg r e a t l yo nt h e p r e m i s eo fc o n v e r g e n c e i th a sag o o dp o t e n t i a lt o b ea p p l i e dt ot h er a p l de v e n s u p e r - r e a l t i m es i m u l a t i o no f l a r g e s c a l ep o w e rs y s t e m s k e yw o r d s ：n o d er a n k i n g ，n e tp a r t i t i o na l g o r i t h m ，s p a r s et e c h n o l o g i e s ， p o w e rf l o wp r o c e d u r e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：7 勿斑签字日期：2 刃矿年多月2 日 学位论文版权使用授权书 本学位论文作者完全了解苤鲞态堂有关保留、使用学位论文的规定。 特授权苤鲞苤鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：杨晓波 签字日期：细7 年莎月互日 导师签名：i 易疋# 签字吼妣j 年6 月2 日 第章绪论 1 1 课题研究背景和意义 第一章绪论 随着电力改革的深入进行，电网网际之间的互联逐步加快，电网规模迅速扩 大。1 9 9 0 年华中与华东电网实现了直流非同步联网：2 0 0 1 年5 月东北与华北 电网实现了交流同步联网；2 0 0 1 年1 1 月福建电网实现了与华东电网的交流同 步联网。至此，以国家电网公司和南方电网公司为代表的超大规模电网形成了。 全国联网是“西电东送”、“南北互供工程的基础，同时也是电力市场化改 革的要求。区域电网互联组成全国联网系统，有利于实现全国范围内电力资源的 优化配置和电力结构的战略性调整，可以提高电网的整体经济效益，并适时解决 发电盈亏区域间的供用电需求矛盾。 大规模电网的在带来巨大的整体经济效益的同时，对于这样一个正在形成的 全国范围内的交直流联合运行的超大规模电力系统，如何保证其安全、稳定和经 济运行，成为了世界级的研究课题。因此对大规模电力系统运行特性进行全面、 详尽、快速、准确的认识和把握，是保证全国联网安全经济运行的首要问题。与 此同时，我国电力系统新发展阶段的规划和实际运行迫切需要把解决大规模电力 系统仿真，尤其是实时和超实时仿真问题提到紧迫的日程上来。然而超大规模互 联电网的地域跨度大、电网结构复杂、负荷特征差异大、系统运行方式变化大等 特点，这些都对电力系统在线安全仿真软件的要求越来越高。 电力系统数字仿真是分析系统的运行状态和动态性能的有效工具，在电力系 统的系统设计、规划、运行和调度等方面有广泛的应用。电力系统仿真软件可以 模拟实际电力系统运行，用于培训调度及运行技术人员，帮助熟悉系统特性和运 行规律；可进行输电线短路、断路及发电机断开等大扰动故障及处理的模拟和仿 真，一方面有利于发现系统弊端、防范于未然，另一方面实现事故处理预演，有 利于发掘更好的事故处理方案，并提高系统操作人员的事故应变能力。 随着计算机科技和计算技术的发展，并行计算技术应运而生，成为提高计算 速度的有效方法。同时全国各大电网的能量管理系统( e n e r g ym a n a g e m e n ts y s t e m ， e m s ) 已经相继建成，通讯网络不断完善，使在线获取电力系统实时数据和实时 的并行计算仿真成为可能。 因此，如何提高电力系统仿真计算的速度，解决电力系统实时仿真的问题， 第一章绪论 成为近几年电力系统仿真计算的热点问题 。本文在深入研究电力系统仿真分析 的基础上，着重针对潮流计算程序进行优化设计，对潮流仿真计算中的几个关键 因素进行了深入研究，并实现其组件程序设计。 1 2 稀疏技术的应用与研究现状 绝大多数科学和工程计算问题均代表了由数学模型所表示的一个物理系 统。为了适合于计算机求解，连续物理系统的定义域必须离散化，其常用方法就 是将定义域网格化，这样在离散域上求解数学模型，就可在各个点上获得某些所 要求的物理量。 在电力网络之中，由于母线的平均出线度在3 7 ，因此大规模电网的导纳矩 阵和仿真计算中的雅可比矩阵就非常的稀疏，适当利用稀疏矩阵非零元素的位置 与数量可以有效减少计算时间和存储空间。 通常我们用数组来存放的矩阵，但对于稀疏矩阵而言，这种存储方式效率 不高。采用有效的矩阵存储方式，不仅可以节省存储单元，而且也可以节省计算 时间，对于大规模矩阵方程组来说，优化存储的方法可以扩大处理问题的规模， 使很多过去用稠密存储方式无法求解的问题得以解决。 但存储稀疏矩阵没有一种通用的最佳的数据结构，不同的数据结构适合于 不同的操作变换和不同的并行实现，不同类别的稀疏矩阵由于结构可以选用自己 最佳的存储方式。目前研究中最常用的稀疏矩阵存储方式f 2 】有以下几种： 坐标存储法：当利用坐标法存储一个稀疏矩阵a 时，需要利用一个数 据类型与a 相同的一维数组为v a l 存储非零元数值，两个整型数组x 与y 存储非零元的行列。a 的非零元可按照顺序存放到中，而与其对 应的行号和列号分别依次放到x 与y 中。 对角存储法：在许多实际应用问题中，经常遇到这样的矩阵，其每行中 只有几个元素不为零，而且这些元素分布在与对角线或与对角线平行的 几条直线上。如常见的三对角，五对角或是分块对角矩阵以及带状矩阵。 对这种矩阵只需要存储矩阵中处于这几条直线上的元素即可。为了寻址 方便，尚需引入一个整型数组，其长度为各行中非零元素个数的最大值， 其中每个整数指明非零元所在的位置偏离对角线的偏移量。 当然，稀疏矩阵的存储不止上述方法，常见的方法还有变带宽存储法、k n u t h 存储法、k r m 循环方法、l a r c o m b e 方法p j 、s h e r m a n s 存储法、超矩阵存储法等。 它们各有各自的适用范围和优点，具体细节不再赘述。 第章绪论 1 3 网络分区策略的研究现状 对大规模电力系统而言，网络方程涉及高维稀疏线性方程组的计算，是暂态 稳定计算中最耗时的部分。在电力系统仿真计算中，网络分区的意义在于将整体 高维线性方程组转化为多个低维线性方程组，从而减少仿真的计算量。在电力系 统暂稳空间并行算法中，按处理器数目把网络分割为多个子网，是最常用的并行 化方法，也是关乎并行计算效率的基础性工作。 目前暂态稳定分区的研究可分为两类：静态分区和动态分区。 静态分区是在实际的暂态稳定仿真计算之前进行，对同_ 个网络只进行一次 分区。 现有的静态分区算法主要有基于因子表路径树的分区1 4 , 5 1 、基于种子节点的 分区和基于e p s i l o n 分解的分区等。 文献【4 】首先确定每个分区权重的上下限，从因子表路径树的根节点开始， 找出遇到的对应子树权重小于上限的节点，将这些节点的子树组合成所需数量的 分区，使得每个分区的权重在上下限范围内，其它节点作为分割节点集。 文献【6 】选取与分区数相同的种子节点，其它节点根据计算的权重聚合到某 个种子节点。这种方法强烈依赖于种子节点的选取，选取不当，所得的分区将很 不均匀。 文献【7 】的目标是将强耦合的节点放在一个分区中，加快收敛速度。方法为： 舍弃系统雅可比矩阵中绝对值小于e p s i l o n 的元素，将剩下元素排成对角块矩阵， 各对角块就是一个分区，对最大的分区规模加一个限制，调整e p s i l o n 的大小， 得到所要的分区结果。 动态分区的基础是：在暂态过程中，故障对其附近区域的影响较大，对远离 故障的区域影响较小，因此，故障附近区域应该用小步长，而其它区域可用较大 的步长【引。为了使得各处理机计算量均衡，要根据故障的位置和严重程度对分区 进行动态调整。这种分区放大伴随产生大量的附加通信，对于集群机这样通信相 对较慢的并行机效果不会太好。 1 4 本文的主要工作 本文着眼于提高电力系统仿真计算的速度，设计开发基于节点排序技术、稀 疏技术的电力系统潮流计算，同时研究了网络自动分区算法，实现了基于因子树 的分区算法，主要研究成果如下： 将电力网络按照半动态或者动态排序技术进行节点优化排序，利用基于 3 第一章绪论 因子树的树形分区排序算法将网络分割为适度规模的多个子网，使得仿 真计算时雅可比矩阵为对角加边( b b d f ) 的形式，为电力系统的细粒 度并行计算打下基础； 针对矩阵的符号分解和数值分解的特点，设计相应的稀疏矩阵存储结 构，开发出针对电力系统仿真的符号分解和l u 分解程序，并与i n t e l m k l 9 1 数值计算程序作对比，在保证求解精度的前提下，大幅度提高 了仿真计算速度； 利用节点优化排序技术和稀疏技术，针对潮流计算程序进行程序架构优 化分析和设计实现，最终开发出优化后的潮流计算程序，并且实现程序 的标准化和模块化，为在暂态仿真程序中的应用奠定基础； 本文较为系统地介绍了针对潮流计算进行优化的总体流程和具体实现方法， 主要内容包括：电力网络的节点优化排序和自动分区、稀疏矩阵的符号分解、l u 分解，以及潮流计算程序的优化改进等。 4 第二章稀疏技术应用和l u 分解效率研究 第二章稀疏技术应用和l u 分解效率研究 电力系统仿真计算中要遇到大量的矩阵和矩阵的运算以及矩阵和矢量的运 算。由于电力网络本身的结构特点，这些矩阵中往往只有少量的非零元素，大部 分的元素都是零元，参加矢量运算的非零元素也不是很多，这就是我们所称的稀 疏矩阵。针对稀疏矩阵和系数矢量，其中的零元素是没有必要参与运算的，同时 对这些元素的存储也是多余的，因此可以采用“排零存储 、“排零运算”等方法， 并且针对相应的存储结构来设计合适的算法来提高计算速度。和不采用稀疏技术 相比，采用稀疏技术可以是计算速度提高几十甚至上百倍，同时对计算机内存的 要求也可以大大降低1 1 0 。电力系统的规模越大，使用稀疏技术带来的效益就越明 显。 电力系统潮流计算是电力系统分析中最基本的计算。文献【11 ，1 2 】采用数组存 储稀疏矩阵来求解潮流方程。文献【1 3 2 1 】分别采用邻接表、卡字链表存储稀疏 矩阵来求解潮流方程。邻接表存储方式和十字链表存储方式同属于链表存储方 式，只不过邻接表只存储横向指向其右边相邻元素的指针，而十字链表还存储纵 向指向下面相邻元素的指针，因此，邻接表存储方式可以认为是十字链表存储方 式的简化形式。 数组存储节省内存是其突出的优势；但矩阵结构变化时，伴随着较多的操作。 而链表存储要多付出内存开销，但对于矩阵结构变化，其操作方便。因此，这两 种稀疏存储方式，对于不同系统规模综合效率的优劣比较，是一值得探讨的问题， 其结论对于编制更为高效的潮流分析软件或其它相关的问题都有一定的意义。 l u 分解是解线性方程组最常用的方法，本章对l u 分解算法，结合多种稀 疏存储方式和数据排序、检索算法进行分析，得到了如下结论：在符号分解阶段 采用基于列指针的动态数组可以实现链表存储和数组存储方式的融合，实现快速 符号分解，而在数值分解阶段由于不涉及内存的释放和创建因此采用数组存储方 式更有优势。 2 1 稀疏矩阵存储方式比较 2 1 1 基本概念 稀疏矩阵( s p a r s e m a t r i x ) ：是矩阵中的一种特殊情况，其非零元素的个数远 第二章稀疏技术应用和l u 分解效率研究 小于零元素的个数。 设m 行n 列的矩阵含t 个非零元素，则称万= 上为稀疏因子，通常认为 m 咒 万o 。0 5 的矩阵为稀疏矩阵( m 为行数，1 1 为列数) 。 以二维数组表示高阶的稀疏矩阵时，会产生零值元素占的空间很大且进行 了很多和零值的运算的问题。 特殊矩阵：值相同的元素或0 元素在矩阵中的分布有一定的规律。如下三 角阵、三对角阵、稀疏矩阵。 压缩存储：为多个值相同的元素只分配一个存储空间；对0 元素不分配空间。 目的是节省大量存储空间。t ，l 的矩阵一般需要，1 2 个存储单元，当为对称矩阵 时需要n ( n + 1 ) 2 个单元。 2 1 2 三元组顺序表 三元组顺序表又称有序的双下标法，对矩阵中的每个非零元素用三个域分别 表示其所在的行号、列号和元素值。它的特点是，非零元在表中按行序有序存储， 因此便于进行依行顺序处理的矩阵运算。当矩阵中的非0 元素少于1 3 时即可节 省存储空间。稀疏矩阵m 的三元表存储格式如图2 1 所示。 11 2 o4 30 0o oo o1 8 1 50 90 00 50 o7 2 40 00 0 4 oo0 1 1o0 030 006 8oo o 20 0o1 3 l j 图2 1稀疏矩阵m 及其三元表存储格式 6 慨眩9 45 3 7 6 m 8 他2 b 4 b l 2 3 2 5 3 6 4 7 3 5 2 6 l 4 7 1 ，1 2 2 3 3 3 4 4 5 5 6 6 7 7 7 第二章稀疏技术应用和l u 分解效率研究 2 1 3 行( 列) 逻辑联接的顺序表 行( 列) 逻辑联接的顺序表：稀疏矩阵中为了随机存取任意一行( 列) 的非 0 元素，需要知道每一行( 列) 的第一个非0 元素在三元组表中的位置，每一行 ( 列) 对应一个单链表，每个单链表都有一个表头指针，这种“带行( 列) 链接 信息”的三元组表即称为行( 列) 逻辑联接的顺序表。稀疏矩阵m 的行逻辑联接 的顺序表存储格式如图2 2 所示。 1 0 - 3 0 0 o 1 5 1 2 4 o 0 0 1 8 0 9 0 5 0 2 4 0 o 2 1 4 十字链表 o l l 0 0 8 0 0 o 0 0 0 0 6 0 o 1 3 1 专叵皿寸圆寸匡扣寸n u l l 2 _ 匡刃_ 团_ n u l l 3 一圃匡扣专叵扣_ n u l l 4 一区_ 匦如哼n u l l 5 一团斗匡扣寸n u l l 6 专圆专区扣寸舰 7 斗圆斗区刃圆斗n u l l 图2 - 2稀疏矩阵m 及其行逻辑联接的顺序表存储格式 十字链表：是既带行指针又带列指针的链接存储方式，每个三元组结点处 于所在行单链表与列单链表的交点处，当矩阵的非零元个数和位置在操作过程中 变化较大时，用这种存储结构更为恰当。 在十字链表中，每个非零元可用一个含五个域的结点表示，其中“j 和e 三 个域分别表示该非零元所在的行、列和非零元的值，向右域r i g h t 用以链接同一 行中下一个非零元，向下域d o w n 用以链接同一列中下一个非零元。同一行的 非零元通过r i g h t 域链接成一个线性链表，同一列的非零元通过d o w n 域链接成 一个线性链表，每个非零元既是某个行链表中的一个结点，又是某个列链表中的 一个结点，整个矩阵构成了一个十字交叉的链表，故称这样的存储结构为十字链 表，可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示之。例 如：矩阵m 的十字链表如图2 3 所示。 第二章稀疏技术应用和l u 分解效率研究 图2 - 3十字链表存储结构示意图 2 2 计算机检索、排序算法比较 2 2 1 基本概念 稳定排序( s t a b l es o r t ) 和非稳定排序：稳定排序是所有相等的数经过某种排序 方法后，仍能保持它们在排序之前的相对次序，反之，就是非稳定的排序。 内排序( i n t e r n a ls o r t i n g ) 和外排序( e x t e r n a ls o r t i n g ) ：在排序过程中，所有需 要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；在排序过 程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法 称为外排序。 算法的时间复杂度和空间复杂度：所谓算法的时间复杂度，是指执行算法所 需要的计算工作量。一个算法的空间复杂度，一般是指执行这个算法所需要的内 存空间。 2 2 2 常见排序算法 冒泡排序：冒泡排序方法是最简单的排序方法。这种方法的基本思想是，将 待排序的元素看作是竖着排列的“气泡，较小的元素比较轻，从而要往上浮。 在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是 自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果 发现两个相邻元素的顺序不对，即“轻 的元素在下面，就交换它们的位置。显 然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻 的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最 第二章稀疏技术应用和l u 分解效率研究 轻元素，所以不必检查。一般地，第i 遍处理时，不必检查第i 高位置以上 的元素，因为经过前面i 】遍的处理，它们已正确地排好序。 冒泡排序是稳定的。算法时间复杂度是o ( ，1 2 ) 。 选择排序：选择排序的基本思想是对待排序的记录序列进行n - l 遍的处理， 第i 遍处理是将l i 1 3 】中最小者与l 啪交换位置。这样，经过i 遍处理之后， 前i 个记录的位置已经是正确的了。 选择排序是不稳定的。算法复杂度是o ( 以2 ) 。 插入排序：插入排序的基本思想是，经过i 1 遍处理后，l 1 。i - l 】己排好序。 第i 遍处理仅将l e i 插入l 1 i 1 】的适当位置，使得l 1 。i l y 是排好序的序列。要 达到这个目的，我们可以用顺序比较的方法。首先比较l 【i 】和l 【i - l 】，如果l 【- - 1 】 l i 】，则l 1 i 】已排好序，第i 遍处理就结束了：否则交换l 【i 与l i - 1 1 的位置， 继续比较l i 一1 1 和l i 2 】，直到找到某一个位置j ( 1 j i - 1 ) ，使得l j 】l d + l 】 时为止。 直接插入排序是稳定的。算法时间复杂度是o ( n 2 ) 堆排序：堆排序是一种树形选择排序，在排序过程中，将a 【n 】看成是完全 二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系 来选择最小的元素。 堆排序是不稳定的。算法时间复杂度o ( n l o g n ) 。 归并排序：设有两个有序( 升序) 序列存储在同一数组中相邻的位置上，不 妨设为a 1 m 】，a m + l h 】，将它们归并为一个有序数列，并存储在a 【1 h 】。 其时间复杂度无论是在最好情况下还是在最坏情况下均是o ( 珂i 0 9 2 n ) 。 快速排序：快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一 遍扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能 确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1 。快速排序 通过一遍扫描，就能确保某个数( 以它为基准点吧) 的左边各数都比它小，右边 各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只 有一个元素为止。 快速排序是不稳定的。最理想情况算法时间复杂度o ( n i 0 9 2 n ) ，最坏o ( n 2 ) 。 希尔排序：在直接插入排序算法中，每次插入一个数，使有序序列只增加1 个节点，并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离( 称为 增量) 的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元 素交换。d l s h e l l 于1 9 5 9 年在以他名字命名的排序算法中实现了这一思想。算 法先将要排序的一组数按某个增量d 分成若干组，每组中记录的下标相差d 对每 组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排 9 第二章稀疏技术应用和l u 分解效率研究 序。当增量减到1 时，整个要排序的数被分成一组，排序完成。 希尔排序是不稳定的。算法时间复杂度是o ( n 2 ) 。 2 2 3 常见排序算法复杂度比较 空间性能是排序所需辅助空间大小，所有简单排序和堆排序都是0 ( 1 ) ，快 速排序为o ( 1 0 9 n ) ，要为递归程序执行过程栈所需的辅助空间，归并排序和基数 排序所需辅助空间最多，为o ( n ) 。 表2 1常见排序算法复杂度比较 序号排序类别时间复杂度空间复杂度稳定 1 插入排序 0 ( 甩2 ) 10 2 希尔排序 o ( n 2 ) 1 3冒泡排序 o ( n 2 ) l 4 选择排序 0 ( 玎2 ) l 5 快速排序 0 ( n l o g 胛) o ( 1 0 9 n ) 6堆排序 0 ( 刀l o g 刀) 1 7 归并排序 0 ( n l o g 聆)o ( n ) 0 2 2 4 常见排序算法选择 因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法 应综合考虑下列因素 2 2 j ： 待排序的记录数目n ； 记录的大小( 规模) ； 关键字的结构及其初始状态； 对稳定性的要求； 语言工具的条件； 存储结构； 时间和辅助空间复杂度等。 l o 第二章稀疏技术应用和l u 分解效率研究 不同条件下，排序方法的选择： ( 1 ) 若1 1 较小( 如n 5 0 ) ，可采用直接插入或直接选择排序。当记录规模较小 时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插入，应选直 接选择排序为宜。 ( 2 ) 若文件初始状态基本有序( 指正序) ，则应选用直接插入、冒泡或随机的快 速排序为宜； ( 3 ) 若1 1 较大，则应采用时间复杂度为o ( 力l o g n ) 的排序方法：快速排序、堆 排序或归并排序。 快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关 键字是随机分布时，快速排序的平均时间最短； 堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最 坏情况。这两种排序都是不稳定的。 若要求排序稳定，则可选用归并排序。但从单个记录起进行两两归并的排序 算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接 插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定 的，所以改进后的归并排序仍是稳定的。 ( 4 ) 在基于比较的排序方法中，每次比较两个关键字的大小之后，仅仅出现 两种可能的转移，因此可以用一棵二叉树来描述比较判定过程。 当文件的i l 个关键字随机分布时，任何借助于“比较”的排序算法，至少需 要o ( n l o g n ) 的时间。 箱排序和基数排序只需一步就会引起m 种可能的转移，即把一个记录装入 m 个箱子之一，因此在一般情况下，箱排序和基数排序可能在o ( n ) 时间内完成 对n 个记录的排序。但是，箱排序和基数排序只适用于像字符串和整数这类有明 显结构特征的关键字，而当关键字的取值范围属于某个无穷集合( 例如实数型关 键字) 时，无法使用箱排序和基数排序，这时只有借助于“比较”的方法来排序。 若n 很大，记录的关键字位数较少且可以分解时，采用基数排序较好。虽然 桶排序对关键字的结构无要求，但它也只有在关键字是随机分布时才能使平均时 间达到线性阶，否则为平方阶。同时要注意，箱、桶、基数这三种分配排序均假 定了关键字若为数字时，则其值均是非负的，否则将其映射到箱( 桶) 号时，又要 增加相应的时间。 ( 5 ) 有的语言( 如f o r t r a n ，c o b o l 或b a s i c 等) 没有提供指针及递归，导致实现 归并、快速( 它们用递归实现较简单) 和基数( 使用了指针) 等排序算法变得复杂。 此时可考虑用其它排序。 ( 6 ) 本章给出的排序算法，输入数据均是存储在一个向量中。当记录的规模 第二章稀疏技术应用和l u 分解效率研究 较大时，为避免耗费大量的时间去移动记录，可以用链表作为存储结构。譬如插 入排序、归并排序、基数排序都易于在链表上实现，使之减少记录的移动次数。 但有的排序方法，如快速排序和堆排序，在链表上却难于实现，在这种情况下， 可以提取关键字建立索引表，然后对索引表进行排序。然而更为简单的方法是： 引入一个整型向量t 作为辅助表，排序前令t i l = i ( o i j j t a g 】 c n u m + + ；j t 口g + 七； e l s e i fi i t a g 】 j j t a g ； c n u m + + ；以鳄+ + ； e l s e i fi i t a g 】一j j t a g ； c n u m + + ；i t n g + 七；j t 口g + + ； e n d i f ； e n d i f ； e r i d i f ； w h i l e ( i t a g l n u m & & j t a g j j t a g 】 t j t j t a g + - f 】_ j j t a g + + 】； e l s e i fi i t a g 】 j j t a g ； t j t j t a g + + 】= ， 口g + + 】； e l s e i fi i t a g 】一j j t a g ； t j t j t a g + + 】= i i t a g ；l t a g + + ；j t a g + + ； 1 7 第二章稀疏技术应用和l u 分解效率研究 e n d i f ； e n d i f ； e n d i f ； w h i l e ( r a g i n u r e & & j t a g j n u m ) 如 t j t j t a g + + 】= i i t a g + + 】； w h i l e ( i t a g i n u r e ) ； 如 t j t j t a g + + 】= j j t a g + + 】； w h i l e ( j t a g 表示。 无向图( u n d i g r a p h ) ：图g 中顶点的偶对若是无向的，形成的图称为无向图， 其偶对用( v x ，v y ) 表示，如图3 2 中g l 所示。 o 啼o 匝巫巫圈 图3 - 2 无向图和有向图 电力网络的拓扑连接可以用一个无向图来表示，因此对电力网络的分割就转 化为对相应无向图的分割，因此可以借用图论的理论来实现电力网络的节点排序 和网络分割。 3 3 2 图的搜索算法 图的搜索( t r a v e r s i n gg r a p h ) 是指从图中指定顶点出发访问图中每一个顶点， 且使每个顶点只被访问一次，该过程为图的搜索f 3 4 3 5 1 。 图的搜索要比树结构复杂的多。出发点不同，任顶点的邻接点就不相同， 路径也就不同。 常用的图的搜索方法有两种：深度优先法，广度优先法。 深度优先搜索算法d f s ( d e p t hf i r s ts e a r c h ) ，深度优先搜索法类似于树的 先根遍历法 鐾 第三章大规模电网节点优化排序与网络分割 算法思想： s t e p l 从图中某个顶点v 0 出发，并访问此项点； s t e p 2 从v 0 出发，访问与v o 邻接的顶点v l 后，再从v 1 出发，访问与 v 1 邻接且未被访问过的顶点v 2 。重复上述过程，直到不存在未 访问过的邻接点为止。 s t e p 3 如果是连通图，从任一顶点v 0 出发，就可以遍历所有相邻接 的顶点；如果是非连通图，则再选择一个未被访问过的顶点作 为出发点，重复s t e p l 、s t e p 2 ，直到全部被访问过的邻接点都被 访问为止。 广度优先搜索b f s ( b r e a d t hf i r s ts e a r c h ) 广度优先搜索法类似于树的按层次遍历的过程。即先访问第1 个顶点所有邻 接点后：再访问下一个顶点所有未被访问的邻接点。 算法思想： s t e p l 从图中某个顶点v o 出发，并访问此顶点； s t e p 2 从v 0 出发，访i 口j v o 的各个未曾访问的邻接点w 1 ，w 2 ，w k ； 然后，依此从w 1 ，w 2 ，w k 出发访问各自未被访问的邻接点。 s t e p 3 重复s t e p 2 ，直到全部顶点都被访问为止。 3 4 基于因子树的分区排序算法 本文讨论的电力网络的分割，在半动态优化排序算法和基于因子树网络分割 算法的基础上提出了基于因子树的网络分区排序思想，根据计算节点的数目对电 力网络进行灵活的分割方案制定，实现对网络的节点进行b b d f 形式的重排。 最后按照分割方案将电力网络划分为若干子网络，对子网络及其相关计算数据进 行重组达到并行计算的目的。 具体实现过程：首先进行半动态节点优化排序，形成优化后的节点顺序：对 树支集进行合适的排序，然后生成相应的因子树；树上的每一个节点都是其子节 点的父节点，在因子树中找到合适的多个节点并以这几个节点将原来的因子树进 行拆分形成多个子树，达到网络分区的目的。直观的解释就是在在一棵“树 上 选择找到合适的一条或者多条“树枝”进行砍伐，得到几个大小相对均匀的“树 2 4 第三章大规模电网节点优化排序与网络分割 枝”，即规模相对均匀的子网络。基于因子树的半动态优化分区排序算法流程如 图3 3 所示。 本节中以具有3 8 9 条母线的山西电网为例来说明基于因子树的分区排序算 法。山西电网的网络结构图如图3 4 所示，其对应的生成树如图3 5 所示，进行 三分区排序之后结果如图3 - 6 所示。 形成因子树之后，从根节点开始向上寻找符合子树规模的树枝，进行子树 的拆分，下面以三分区的过程为例说明基于因子树的树形分区算法思想。 s t e p i 判断分区数a r e a ，若大于等l ，则进行2 ) ，若小于l 则退 出程序；树的节点总数为3 8 9 ，目标分区数为3 ，则子树理想 规模为n = 3 8 9 3 = 1 2 7 s t e p 2 以根节点位出发点寻找规模为0 9 1 2 7 1 1 1 2 7 的树枝或者 树枝集合，对其中尚未着色的节点进行着色( 即标出分区号) ， 设此子树规模为n s t e p 3a r e a 减一，若a r e a 等于零则退出程序，大于1 则重新设 置子树规模为( 3 8 9 0 n ) a r e a + n ，返回s t e p l 。 以此利用此分区算法对山西电网进行二分区、三分区、五分区，得到的分 区结果分别如图3 7 ，3 8 ，3 - 9 所示。 第三章大规模电网节点优化排序与网络分割 因子树分区算法流程 因子树的度 因子树的每个节点度 定义为以自身节点为 根节点的子树节点数目 图3 - 3基于因子树的半动态优化分区排序算法流程 第三章大规模电同节点优化捧序与网络分割 第三章大规模电网节点优化排序与网络分剖 第三章太规模电阿节点优化排序与同络分割 第三章大规模屯网节点优化捧序与网络分割 第三章大规模电网节点优化排序与网络分割 图3 - 8山西电网三分区结果图 3 l 第三章大规模电网节点优化排序与网络分割 图3 - 9 山西电网五分区结果图 采用基于因子树的分区算法对山西电网进行分区后得到的各子区的网络规 模如表3 1 所示，可以看出子网的规模并不是呈均匀分布，在进行自动分区之后 可以结合动态优化或者结合人工调整来达到最优分区效果，对此本文没有进行深 入的研讨，在后续的工作中可以进行相关的研究。 第三章大规模电网节点优化排序与网络分割 表3 1山西电网分区规模比较 分区规模比较 分区1分区2分区3分区4分区5 二分区2 lll7 8 三分区 1 3 315 89 8 ， 五分区 7 08 96 21 0 76 l 3 5 小结 本章着重研究了电力网络的优化排序和分割算法，并进行了程序的设计和 实现：在电力网络优化分割中，首先采用半动态优化排序算法和广度优先算法生 成原始的因子树，然后根据计算节点数，进而进行子网分割。在此基础上，本章 利用基于因子树的分区排序思想成功的在具有3 8 9 个节点的山西电网上实现网 络分割。 本章没有对网络分割后的并行算法讨论，只是对电力网络的优化分割进行 探讨和实践，并且在较大规模的电网上成功实现了网络分割，对程序进行封装之 后可以为进一步的网络并行计算所应用，因此有较好的应用潜力和进行进一步完 善的必要。 第四章电力系统潮流计算程序架构优化与算例分析 第四章电力系统潮流计算程序架构优化与算例分析 4 1 概述 在电力系统运行和规划方案研究中，都需要根据当前系统的发电运行方式及 系统接线方式求解电力系统的稳态运行情况，确定电力系统稳态运行状态 4 0 , 4 1 】。 给定电力系统的网络结构参数和电力系统运行状况的边界条件确定电力系统稳 态运行状态的方法之一是潮流计算。 电力系统潮流计算问题在数学上是一组多元非线性方程式的求解问题，其解 法离不开迭代。因此，对潮流计算方法，首先要它尽可能的收敛，并给出正确的 解1 4 2 1 。随着电力系统规模的日益扩大，潮流问题的方程式阶数越来越高，对这样 规模的方程式并不是采用任何数学方法都能保证给出正确答案的，这种情况促使 电力系统的研究人员不断寻求新的更可靠的算法。 在数字计算机解电力系统潮流问题的初级阶段，普遍采取以节点导纳矩阵为 基础的高斯迭代法。这个方法原理比较简单，要求的数字计算机内存量也比较小， 适应当时电子数字计算机制造水平，但收敛性较差。2 0 世纪6 0 年代出现的阻抗 法改善了系统潮流的收敛性，获得了广泛的应用，但是阻抗法占用计算机内存大， 每次迭代的计算量大。 克服阻抗法缺点的一种途径就是采用牛顿一拉夫逊法，牛顿一拉夫逊法是数 学中解决非线性方程式的典型方法，有较好的收敛性。解决电力系统潮流计算问 题是以导纳矩阵为基础的，因此，只要在迭代过程中尽可能保持方程式稀疏矩阵 的稀疏性，就可以大大提高牛顿一拉夫逊法潮流程序的效率。自从2 0 世纪6 0 年 代中期利用了最佳顺序消去法之后，牛顿一拉夫逊法在收敛性、内存要求、速度 方面都超过了阻抗法，成为目前仍在广泛应用的优秀方法。随后出现的p q 分 解法对纯数学的牛顿一拉夫逊法进行了改进，在计算速度方面有很大的提高，迅 速得到了推广。 近2 0 多年来，潮流问题算法的研究仍非常活跃，但大多数都是围绕改进的 牛顿法和p q 分解法进行的。此外随着人工智能理论的发展，遗传算法、人工 神经网络、模糊算法也逐渐引入潮流计算。但到目前为止这些新模型和算法还不 能取代牛顿一拉夫逊法和p q 分解法的地位。 本节将介绍牛顿拉夫逊法的原理和针对潮流计算程序进行优化的流程框 第四章电力系统潮流计算程序架构优化与算例分析 图，并以山西电网和华北电网系统进行算例分析。 4 2 潮流计算问题的数学模型 电力系统是一个复杂而庞大的系统，在建立数学模型时，必须抓住主要矛 盾，正确地模拟那些对运行状态影响较大的因素，忽略一些次要的因素，否则就 会导致方程组的阶数急剧增加。此外，这也将给上机算题带来一定困难，因为这 不仅使上机计算人员需填写大批原始数据，而且其中有些数据可能很难提供。因 此在编制任何具体程序以前，不需对电力系统有关元件物理特性进行深入的分 析，然后根据问题的性质建立合理的数学模型。 4 2 1 潮流计算的节点类型 电力系统由发电机、变压器、输电线路及负荷等构成。在进行电气计算时， 系统中的静止元件如变压器、输电线、并联电容器、电抗器等可以用尺，lc 组成 的等值模拟电路来模拟。因此，有这些静止元件所连成的电力网在潮流计算中可 以看作是线性网络，并用相应的导纳矩阵或阻抗矩阵来描述。在潮流计算中发电 机和负荷都作为非线性元件来处理，不能包括在线性网络部分。 电力系统的网络方程表示成节点电压和节点注入功率的形式如下： 一 只+ j q f = v i 芝：y ov j 0 = 1 川2 一，n )( 4 - 1 ) 面 上式含有n 个非线性方程式，是潮流计算问题的基本方程式，对这个方程 式不同的应用和处理就形成了不同的潮流程序。 电力系统潮流计算中，表征各节点运行状态的参数是该节点的电压向量和 复功率，也就是说每个节点都有四个表征节点运行状态的量：v ，秒，p ，q ，因此在 那个节点中共有4 甩个运行参数。 在一般的电力系统潮流计算中，对每个节点往往给出两个运行参数作为已 知条件，而另外两个作为待求量。根据原始数据给出的方式，电力系统中的节点 分为以下3 种类型： 1 p q 节点这类节点给出的参数是该点的有功功率和无功功率( p ，q