输电线扩展规划分支定界算法.pdf

第３８卷第１１期２０１０年６月１日电力系统保护与控制ＰｏｗｅｒＳｙｓｔｅｍＰｒｏｔｅｃｔｉｏｎａｎｄＣｏｎｔｒｏｌＶｏｌ－３８Ｎｏ．１１Ｊｕｎ．１，２０１０输电线扩展规划分支定界算法赵洪山，陈亮（华北电力大学电力．２－程系，河北保定０７１００３）摘要：研究了输电线扩展规划的分支定界算法。为了对输电线扩展规划的各种预选方案进行综合分析，提出了规划集的概念，并建立了输电线扩展规划分支定界算法的优化数学模型。该模型以投资费用和运行成本最小为目标，以电力系统潮流为约束条件，利用内点法作为求解松弛予问题的算法，给出了输电线扩展规划分支定界算法的详细计算步骤，并在ＩＥＥＥ３９节点测试系统和某地区实际电网的输电线扩展规划中运用所提出的方法进行了仿真。仿真结果表明，该方法不必进行遍历搜索就能够快速得到投资和运行成本最低的投建线路，计算量小，效率高。关键词：输电线规划；规划集；分支定界法Ｔｒａｎｓｍｉｓｓｉｏｎｌｉｎｅｅｘｐａｎｓｉｏｎｐｌａｎｎｉｎｇｂｒａｎｃｈａｎｄｂｏｕｎｄｍｅｔｈｏｄ—ＺＨＡＯＨｏｎｇｓｈａｎ，ＣＨＥＮＬｉａｎｇ（ＮｏｒｔｈＣｈｉｎａＥｌｅｃｔｒｉｃＰｏｗｅｒＵｎｉｖｅｒｓｉｔｙ，Ｂａｏｄｉｎｇ０７１００３，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｔｒａｎｓｍｉｓｓｉｏｎｌｉｎｅｅｘｐａｎｓｉｏｎｐｌａｎｎｉｎｇｂｒａｎｃｈａｎｄｂｏｕｎｄｍｅｔｈｏｄｉｓｇｉｖｅｎ．Ｆｉｒｓｔ，ｔｏａｎａｌｙｚｅａｌｌｃａｎｄｉｄａｔｅｓｔｒａｔｅｇｉｅｓｓｙｎｔｈｅｔｉｃａｌｌｙ，ａｐｌａｎｎｉｎｇｓｅｔｉｓｄｅｆｉｎｅｄ，ａｎｄｔｒａｎｓｍｉｓｓｉｏｎｌｉｎｅｅｘｐａｎｓｉｏｎｐｌａｎｎｉｎｇｂｒａｎｃｈａｎｄｂｏｕｎｄｏｐｔｉｍａｌｃｏｍｐｕｔａｔｉｏｎｍｏｄｅｌｉｓｆｏｕｎｄｅｄ．Ｔｈｅｏｂｊｅｃｔｏｆｔｈｉｓｍｏｄｅｌｉｓｔｏｍｉｎｉｍｉｚｅｔｈｅｉｎｖｅｓｔｍｅｎｔｓａｓｗｅｌｌａｓｏｐｅｒａｔｉｏｎａｌｃｏｓｔｓ，ａｎｄｉｔｓｃｏｎｓｔｒａｉｎｔｉｓｔｈｅｅｑｕｍｉｏｎｏｆｐｏｗｅｒｆ—ｌｏｗ．Ｔｈｅｎ，ｔｈｅｉｎｔｅｒｉｏｒｐｏｉｎｔｍｅｔｈｏｄｉｓｕｓｅｄａｓｔｈｅａｌｇｏｒｉｔｈｍｔｏｓｏｌｖｅｒｅｌａｘｅｄｓｕｂｐｒｏｂｌｅｍｓ，ｔｈｅｄｅｔａｉｌｓｔｅｐｓｏｆｔｒａｎｓｍｉｓｓｉｏｎｌｉｎｅｅｘｐａｎｓｉｏｎｐｌａｎｎｉｎｇｂｒａｎｃｈａｎｄｂｏｕｎｄｍｅｔｈｏｄａｒｅｐｒｅｓｅｎｔｅｄ．Ｆｉｎａｌｌｙ，ｔｈｅｐｒｏｐｏｓｅｄｍｅｔｈｏｄｉｓａｐｐｌｉｅｄｔｏｔｈｅＩＥＥＥ３９ｂｕｓｅｓｔｅｓｔｓｙｓｔｅｍ’ａｎｄａｎａｃｔｕａｌｐｏｗｅｒｓｙｓｔｅｍｉｎＣｈｉｎａ．Ｔｈｅｓｉｍｕｌａｔｉｎｇｒｅｓｕｌｔｓｉｎｄｉｃａｔｅｔｈａｔｔｈｅｍｅｔｈｏｄｎｅｅｄｎｔａｎｅｘｈａｕｓｔｉｖｅｓｅａｒｃｈｆｏｒｗｈｏｌｅｃｏｍｂｉｎａｔｉｏｎｓｃｈｅｍｅ，ａｎｄｃａｎｑｕｉｃｋｌｙｆｉｎｄｔｈｅｏｐｔｉｍａｌｅｘｐａｎｄｌｉｎｅｓｗｉｔｈｔｈｅｌｏｗｅｓｔｉｎｖｅｓｔｍｅｎｔｓａｎｄｏｐｅｒａｔｉｏｎｃｏｓｔｓ．ＴｈｉｓｗｏｒｋｉｓｓｕｐｐｏｒｔｅｄｂｙＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａ（Ｎｏ．Ｎ５０５７７０１７）．Ｋｅｙｗｏｒｄｓ：ｔｒａｎｓｍｉｓｓｉｏｎｌｉｎｅｅｘｐａｎｓｉｏｎｐｌａｎｎｉｎｇ；ｐｌａｎｎｉｎｇｓｅｔ；ｂｒａｎｃｈａｎｄｂｏｕｎｄｍｅｔｈｏｄ中图分类号：ＴＭ７１５文献标识码：Ａ—文章编号：１６７４。３４１５（２０１０）１１－００６００７０引言随着经济的迅速发展，电力负荷也迅速地增长。当负荷增长接近输电网运行极限的同时，事故率增加，将严重影响电力系统的安全稳定运行。进行输电线扩展是增加输电容量的有效方法之一。在实际电力系统中，规划者可以制定出多种输电线扩展规划方案，每种方案的投建线路不同，投资成本也不同。对不同的方案，其投建后系统的运行成本也不同。为了使投资和运行成本最小，而又保证电网可靠性，电力工作者尝试了很多优化技术对各种方案进行分析计算，进而找到最优的电网规划方案。文基金项目：国家自然科学基金项目（Ｎ５０５７７Ｏ１７）献［１．３］采用改进遗传算法来求解多目标电网规划问题，能取得较好结果；文献【４］提出了计算资源依搜索效率合理分配的全新概念，并给出了多种群中心解搜索电网规划算法；文献【５】提出了基于区间层次分析法的城网规划综合评判决策方法；文献【６．７】将启发式算法混合使用来求解电网规划的最优方案；文献［８１提出了一种基于风险度评估的配电网多目标灵活规划模型，并采用改进生成树法进行求解；文献『９．１ｏ］采用粒子群算法求解最优电网网架规划方案。这些算法大多数都是启发式算法。文献ｆ１１】采用基于分支定界的模糊集理论来求解输电线扩展规划问题。国外在研究电网规划问题时常用的方法还有塔布搜索法¨引、Ｂｅｎｄｅｒｓ分解法ｌｌ川、混合整数分离模型【ｌ、改进遗传算法【Ｊ等。本文提出了输电网规划集的概念，利用分支定赵洪山，等输电线扩展规划分支定界算法一６１．界法在规划集上研究了输电线扩展规划优化算法，该方法的特点是不必对解空间进行遍历搜索就能够找到全局最优解。１输电线规划优化计算模型１．１规划集的概念在电力系统规划过程中，总是存在多种方案可以解决系统运行的安全性、可靠性和经济性问题。这些方案包括扩展输电线、建设变电站和电厂等。实际电力系统的规模往往非常庞大，规划人员在制定预选方案时很难找到最优的规划策略。为了对所有预选方案进行综合分析进而得到最优策略，在优化计算过程中就必须同时考虑各种方案中涉及到的所有输电线、变电站和电厂等元素，由此，我们提出规划集的概念。假设某电力系统规划问题有种预选方案．，ｉ＝１，２，．．．，，．中涉及到的所有电力元件表示为…Ｅｉ＝｛ｅｔ，ｃ２，，ｅ），ｍ，是，中涉及到的电力元件的个数。集合．”．∑…＝ＵＥｉ；巨ｕｕｕｉ＝１称作规划集。规划集是由所有预选方案中的预投建、拆除或者更换的线路、变压器和发电厂还有其他电力元件构成的。这些元件对电力系统运行的安全性、可靠性和经济性都起着至关重要的作用，合理地对这些元件进行规划能有效提高系统运行的可靠性和经济性，这就需要通过优化算法对规划集中所有元素进行综合分析。优化分析得到的最优规划策略中涉及到的元件是规划集的一个新的子集，是最优的规划方案。对于输电线扩展规划来说，预选方案中的每一条候选线路都存在两种状态：投建和不投建。在优化计算模型中，用二进制变量来表示候选线路的投建与否，二进制变量的个数和规划集中元素的个数相同。１．２输电线扩展规划优化数学模型输电线扩展规划优化数学模型如下：ＮＮＮＮ∑∑∑∑ｍｉｎ｛Ｃ＝ｃ啊＋ｆｌ，ｑ，）（１）ｔ＝ｌｇ＝ｌｔ＝ｌｂ＝ｌｔｓ．ｔ．Ｐ，一∑∑∑［（＋）ｃｏｓ＋∑∑（＋ｇＢ；）ｓｉｎ￣ｊ，卜０（２）ｒ＝ｌＢｙ一∑∑∑ｕ，，［（＋）ｓｉｎ一，＝ｌ２－＝ＩＢ∑∑（＋％）ｃｏｓ，］＝０ｆ１Ｂｙ≤ｅｏ≤Ｐｏ。ＱｏＱｏ≤≤ｅｅ，ｐｅＥｔ≠，ｑｂｔ０≤∑０ｑ１（３）（４）（５）（６）（７）（８）（９）其中：Ｃｏ：ａ２ｇｐ２＋尸Ｇ＋ａｏ；＝‘一，Ｕｊ，（ＣＯＳ，＋Ｂｓｉｎ）；＝一ＵＵ，，（ＣＯＳ＋∈∈∑…Ⅳｓｉｎ），ｂ，ｑ６ｆ，（，＝１，２，，ｖ）；ＮⅣ是规划期的年数；ｎ是发电机的个数；ｈ、，是一年内的小时数，值为８７６０ｈ／年：Ｃ和．分别是发电机ｇ在第ｆ时的燃料价格和耗量特性，，的单位是吨／年；是规划集中候选投建线路的个数；是∈∑输电线投建后第ｆ年折旧费；ｑ是二进制变量，ｑ＝１表示第ｂ条候选线路在第ｔ年进行投建，０表示不投建；Ｃ是候选线路ｂ在第ｆ年投建的费用；，和．，分别是第年注入节点ｉ的有功和无功功率；【，．，是节点ｉ在第ｔ年的电压幅值；是节点个数；和是由已有线路形成的节点导纳矩阵中的元素；Ｇ：和是候选线路ｂ的形成的节点导纳∈矩阵中的元素；ｂＢ．．表示第ｂ条候选线路连接节点ｉ和节点，；＝一０．是节点和节点，之间的∑相角差；是规划集。输电线扩展规划的目标函数为发电机的发电成本和候选线路的投资成本。候选线路的投建能够有效改变系统潮流的分布，在保证电压、功率和频率不越界的前提下，使发电成本低的机组优先发电，从而降低系统运行成本；而投建大量的候选线路会增加投资成本，这就需要平衡运行成本和投资成本，找到一个经济性最优的输电线扩展规划方案。等式（２）和等式（３）是潮流约束；不等式（４）～（７）分别是发电机的有功和无功出力极限约束、节点电压上下限约束和输电线有功潮流极限约束；不等式（８）是候选线路的有功潮流极限约束；不等式（９）是候选线路一次性投建约束。上述模型中，二进制变量ｇ，只影响潮流的分布和运行效益，对流过预选线路潮流的不等式约束没有影响，因此，只有目标函数和等式约束中才含有不等式约束（８）中则不含ｇ，。一６２．电力系统保护与控制２输电线扩展规划分支定界算法２．１基本思想“”输电线扩展规划分支定界算法是以松弛、“”“”“”分支、定界、剪枝为基础的。基本思想是：首先，将表示候选线路投建与否的二进制变量在０－１区间连续化，形成松弛问题，即松弛化；其次，分别研究某条线路在投建和不投建两种情况下系统运行成本和投资费用之和的最小值问题，即分支；然后，将运行成本和投资成本之和的最小值作为这两种情况的下界，即定界；最后，对于无法得到全局最优解的情况不做进～步分支和定界，即剪枝。迭代上述过程，直到得到全局最优的规划方案时结束。２．２分支定界法（ＢｒａｎｃｈａｎｄＢｏｕｎｄ，Ｂ＆Ｂ）分支定界法的模型如下：Ｐ：ｍｉｎｆ（ｘ，ｑ）ｓ．ｔ．ｈ（ｘ，ｑ１＝０（ｊ窖）０∈…ｑ｛０，１），ｉ＝１，，设置初始上界Ｕ＝＋ｏｏ，将二进制变量连续化得到下列松弛问题Ｐ０。Ｐ０：ｍｉｎｆ（ｘ，ｑ）ｓ．ｔ．ｈ（ｘ，ｑ、＝０ｇ（ｘ，ｑ１０≤０ｑ１用内点法求解Ｐ０得到最优解，以及下界值Ｌｏ＝ｆ（ｘ＇ｏ，ｑｏ）。选择满足下列条件的变量ｇ，作为分支变量：∈ｑ－－ｍｉｎ｛Ｊｑ－０．５Ｉ），ｑ将分支变量分别置为０和１得到下列两个松弛子问题：Ｐ１：ｍｉｎｆ（ｘ，ｑ）ｓ．ｔ．（ｑ）＝０擘（ｊ；）００ｑ１ｑ，＝０Ｐ２：ｍｉｎｆ（ｘ，口）ｓ．ｔ．ｈ（ｘ，ｑ、＝０ｇ（；）００ｑ１ｑ＝１用内点法对松弛子问题Ｐ１和Ｐ２进行求解，得到最优解，，，以及下界值Ｌ＝ｌ厂（，），厶＝厂（，）。如果或者是整数解并且下界值小于上界值，我们就将这个整数解对应的目标函数值作为上界。否则，我们选择子问题Ｐ１和Ｐ２中下界值较小的进行分支。上述过程进行迭代，直到分支子问题的下界值大于或等于上界时，迭代结束。在上述迭代过程中，遇到下列条件之一则对子问题进行剪枝：（ａ）无解；（ｂ）最优解为整数可行解；（ｃ）下界值小于或等于上界值。３输电线扩展规划分支定界法的计算步骤根据上节的规划计算模型，下面给出了详细的输电线扩展规划分支定界算法的计算步骤。第一步：初始化。置迭代次数ｋ＝１，初始上界＝＋ｏ。。将问题（１）～（９）松弛化得到松弛问题Ｐ０，用内点法求解Ｐ０得到最优解和下界值厶。如果是整数解，那么就是全局最优解，如果Ｐ０无解则程序结束，否则执行第五步。第二步：选择分支子问题。在未进行剪枝的子问题中选择下界值最小的子问题进行分支，记作Ｐｆ，执行第三步。如果所有子问题都剪枝，那么迭代结束，执行第四步。第三步：判断是否满足终止条件。如果分支子问题Ｐｆ的下界值满足条件：厶，迭代结束，执行第四步，否则执行第五步。第四步：当前上界值对应的整数解就是问题（１）～（９）的全局最优解，程序停止。第五步：选择分支变量。选择满足下列条件的二进制变量作为分支变量：ｍｉｎ（Ｉｑ一０．５１），记作ｇ。分别将置成０和１得到两个新的子问题Ｐ２１和Ｐ２ｋ，执行第六步。第六步：求解新形成的子问题。用内点法对新形成的子问题Ｐ２１和Ｐ２ｋ进行求解，得到最优解一，和以及下界值三和￡：。置ｋ＝ｋ＋１。第七步：更新上界值。如果新形成的子问题有整数最优解并且下界值小于当前上界值［厂，则将【厂更新为这个子问题的下界值。第八步：剪枝。如果新形成的子问题满足剪枝条件，则进行剪枝，然后执行第二步。４算例分析４．１算例１将所提出的算法应用到ＩＥＥＥ３９节点测试系统赵洪山，等输电线扩展规划分支定界算法一６３．来分析优化计算过程。如图１所示。０变电站及负荷节点…一一候选线路图１算例１测试系统网络结构Ｆｉｇ．１Ｃａｓｅ１ｔｅｓｔｉｎｇｓｙｓｔｅｍｎｅｔｗｏｒｋ测试系统的节点３、１８、２６、２７、２８的负荷将以每年３％的速度增长，达到线路传输极限，对网络进行两年规划，年折旧率为０．８。电源３１、３２、３６投建较早，发电成本高于其他电源，各电源有功出力极限见表１，节点３、１８、２６、２７、２８的当前负荷见表２。表１各电源有功出力极限Ｔａｂ．１Ｐｏｗｅｒｌｉｍｉｔｏｆｅａｃｈｓｏｕｒｃｅ电源极限／ＭＷ电源极限／Ｍｗ３０３５０３５ｌ０００３ｌ１１４５３６６６０３２７５０３７６４０３３７３２３８９３０３４８０８３９１ｌ０Ｏ表２负荷增长点的当前负荷值Ｔａｂ．２Ｌｏａｄｓｏｆｌｏａｄｇｒｏｗｉｎｇｐｏｉｎｔ节点Ｉ３ｌ１８Ｉ２６Ｉ２７２８负荷／ＭＷＪ３２２Ｉ１５８ｌ１３９『２８１２Ｏ６输电线扩展规划有三种预选方案Ａｌ，Ａ２，Ａ３。———Ａ１：在支路２－３、２２５、２６－２７、２６２９、２８２９分别增加一条输电线；Ａ２：在支路２－３、分别增加一条输电线；Ａ３：在支路３．１８、分别增加一条输电线。这三种方案中分别涉及到的候选线路的集合为：Ｅ＝｛／２－２３，２，／２６－２７／２６－２９｝；：｛ｆ１，／２－２５／２５－２６／２６－２７，２。｝；：｛，，，／２５－２６，２。｝。∑‘则规划集＝ＥｌＵＥＵ＝｛，２＿，，，，。，，５６，，２６＿２７，６－２８，６Ｉ２９，３－２９｝。规划集中候选线路的传输功率极限及投建费用见表３，其他线路功率均未达到极限。表３候选线路功率传输极限及投建费用１１ａｂ．３Ｌｉｍｉｔｓａｎｄｃｏｓｔｓｏｆｃａｎｄｉｄａｔｅｌｉｎｅｓ线路极限／Ｍｗ费用／百万元—２３３３０１．５—２２５２００４３．１８２００１－３—１７１８２００Ｏ．７１７．２７２００１．５—２５２６２００２—２６２７２００１．４—２６２８２００３．１２６．２９２００４．５—２８２９２００１．４采用输电线扩展规划分支定界算法进行求解，各条候选线路的分支过程见图２，图２中每一个子问题的下界值见表４。整数解整数解图２算例１分支定界过程Ｆｉｇ．２Ｂｒａｎｃｈａｎｄｂｏｕｎｄｐｒｏｃｅｓｓｉｎｃａｓｅ１由图２可见，对二进制变量进行９次分支，输电线扩展规划分支定界算法满足了终止条件。分支过程中，子问题１６首先得到整数解，进行剪枝，并且将子问题１６的下界值作为当前的上界，即Ｕ：２０８０５８．８７８９５；随后子问题１７和子问题１８也得到整数可行解，其下界值分别为２０６７８７．８３２２２和２０７４８６．８３９１２；子问题１７的下界值小于当前上界值，则将更新为２０６７８７．８３２２２；子问题１８．．６４．．电力系统保护与控制的下界值则大于当前上界值，进行剪枝；然后选择分支子问题，在所有未进行分支且未剪枝的子问题中，子问题８的下界值是最小的，因此将子问题８作为分支子问题，但是子问题８的下界值为２０６８０９．４６６３１，大于当前上界值２０６７８７．８３２２２，满足了分支定界法的终止条件。此时上界值ｕ对应的子问题为１７，则子问题１７的最优整数可行解就是初始问题的最优解。表４算例１各子问题下界—Ｔａｂ．４Ｌｏｗｅｒｂｏｕｎｄｏｆｅａｃｈｓｕｂｐｒｏｂｌｅｍｉｎｃａｓｅ１子问题下界值子问题下界值Ｏ２０５５８６．８ｌ５６７ｌＯ２０６６４８３９ｌ４３１２０５７０４０７８６３ｌ１２０８３５８．９１９ｌ０２２０６０４８．９３８００１２２０７６４５．０９０９５３２ｏ６４８８．７２６２ｌ】３２０８５８２．１９３７５４２０５９１７．９１４０７１４２０６７３５．６３８４２５２０８９１０．６９９９９ｌ５２０６７５８．７０１６０６２０６４６３．４４１５１ｌ６２０８０５８．８７８９５７２０７０７１．９４１４０１７２０６７８７．８３２２２８２０６８０９．４６６３１１８２０７４８６．８３９１２９２０８１０７．Ｉｌ２９４优化计算的结果：规划期第一年投建候选线路—２．３、２．２５、２８２９，第二年投建线路１７．１８，系统在这两年期间的运行成本和线路投资总共为２０６７．８７８３亿元。在规划期第一年中，由于负荷点３和２８功率相对较大，负荷增长３％后系统无法满—足运行条件。投建线路２３表明节点３的负荷主要由电源３０和３７提供；候选线路２８．２９的投建表明节点２８的负荷功率主要由电源３８提供；电源３７的功率输出的路径只有２．２５和２５．２６，这两条线路的功率传输极限都为２００ＭＷ，而电源３７的出力极限为６４０ＭＷ，候选线路２．２５的投建能够增大电源—３７的输出功率，虽然候选线路２２５的投建成本很高，但是电源３７的发电成本较低，长时期内系统总的运行成本会降低。在规划期第二年中，系统无法满足负荷点１８的持续增长，由于节点１６连接着四个电源点，其中电源３３、３４、３５发电成本较低且出力极限较高，是主力电源点，负荷点１８的功率主要通过线路１７．１８进行传输，因此需要对线路１７．１８进行扩展。算例中，优化计算结果与三个预选方案都不同，是规划集的一个新的子集。这说明规划人员在对较大规模电网进行规划时，很难凭经验得到最优方案，而通过规划集我们就可以得到比任何预选方案都更优的规划策略，可见规划集在寻找电网规划的最优策略中起着重要作用。４．２算例２将所提出的算法应用到某实际地区电网中来分析优化计算过程，如图３所示。该地区电网的东北部区域为新兴工业城市，负荷增长迅速。负荷点１４、１６和１７以每年３％的速度增长，达到线路运行极限，对网络进行两年规划，折旧率为０．８。图３算例２网络结构Ｆｉｇ．３Ｃａｓｅ２ｎｅｔｗｏｒｋ输电线扩展规划有４种预选方案Ａ１，Ａ２，Ａ３，Ａｄ。Ａ１：在支路１２一ｌ４、１５．１７、１６．１７分别增加一条输电线：Ａ２：在支路ｌ２．１６、１４．１５、１７．１８分别增加一条输电线：Ａ３：在支路１４．１５、１５．１７、１７－３１分别增加一条输电线；—Ａ４：在支路ｌ２．１４、１２１６、１５．１７分别增加一条输电线。这４种方案中分别涉及到的候选线路的集合为：Ｅ１＝｛１１２．１４，Ｅ２＝｛１１２．１６，Ｅ３＝｛１１４．１５，Ｅ４＝｛１１２．１４，—，１５．１７，ｌｌ６１，１４．１５，，１７．１，１５．１７，，１７．３—Ｚ１２．１６，１１５１∑则规划集＝ＥｌＵＥ２ＵＥ３ＵＥ４－－｛ｔ１２－ｌ４，，１２．１６，，ｌ４．１５，，１５．１７，，１６．１７，１１７１８，ｌｌ７．３１｝。采用输电线扩展规划分支定界算法进行求解，各条候选线路的分支过程见图４，图４中每一个子问题的下界值见表５。赵洪山，等输电线扩展规划分支定界算法一６５．图４算例２分支定界过程Ｆｉｇ．４Ｂｒａｎｃｈａｎｄｂｏｕｎｄｐｒｏｃｅｓｓｉｎｃａｓｅ２ｌ解表５算例１各子问题下界Ｔａｂ．５Ｌｏｗｅｒｂｏｕｎｄｏｆｅａｃｈｓｕｂ－ｐｒｏｂｌｅｍｉｎｃａｓｅ２子问题下界值子问题下界值Ｏｌ２１４．７１８５４１２１２５３．８９８８６１１２２０．５３０１３１３１２３３．２４３２６２１２４３．８ｌ５７７ｌ４１２６６．４２４２２３１２２２．９７４５７１５１２３４．７２６１８４１２３１．９１０９９１６１２５１．６３５９７５无解１７无解６１２２９．１６８３ｌｌ８ｌ２５５．７７０５８７１２３０．３６９６８１９１２４７．３５０７５８１２６５．６２２２８２０１２５９．８４１５Ｏ９１２３１．５２４４５２ｌ无解１０ｌ２５０．２９８６７２２１２５９．６２６３０１１无解由图４可见，对二进制变量进行了１１次分支，输电线扩展规划分支定界算法满足了终止条件。分支过程中，子问题５首先出现了无解情况，进行剪枝，这说明第一年中如果候选线路１２１４、１２．１６和１６．１７都不投建则无法满足负荷增长的需求；子问题８首先得到整数解，将子问题８对应的下界值１２６５．６２２２８（表５）作为当前的上界，并对子问题８进行剪枝；此时，子问题７在当前所有未进行剪枝的子问题中下界值最小，进行分支，得到子问题９和子问题１０；子问题１０有整数解，并且下界值为１２５０．２９８６７，小于当前上界，因此将上界更新为１２５０．２９８６７；在随后的分支定界过程中所有得到整数解的子问题的下界值都大于当前上界１２５０．２９８６７，因此上界不进行更新，直到所有子问题都被剪枝，计算终止。当前上界对应子问题１０，因此，子问题１０的解就是输电线扩展规划的最优解。子问题１０的最优解为ｑｌｏ＝｛ｏｏｏｏｌｏｏ，１００００００｝，即第一年投建候选线路ｌ６．１７，第二年投—建候选线路１２１４。投建线路１６．１７说明节点１６增长的负荷需要通过电源１５、１８和３１提供：第二年投建线路１２．１４说明原有线路从第二年开始无法满足节点１４的负荷增长，节点ｌ４增加的负荷需要由电源１２提供。５结论文章提出了规划集的概念，并通过此概念给出了输电线扩展规划分支定界算法。将此方法应用到ＩＥＥＥ３９母线测试系统和实际某地区输电网的输电线扩展规划中，结论表明本文给出的方法在处理大规模多阶段电网输电线扩展规划问题中是合理有效的；通过规划集得到的规划策略优于任何预选方案；内点法与分支定界法的结合使用能够找到输电线扩展规划问题的最优策略，并且计算量明显减小。未来研究工作：将规划集的概念及分支定界法应用到更广泛的电力系统规划问题中，例如线路的更换和检修，增加新的变电站或电源，电容器组的投建等。参考文献［１］程浩忠，高赐威，马则良，等．多目标电网规划的分层最优化方法【Ｊ】．中国电机工程学报，２００３，２３（１０）：１１．１６．——ＣＨＥＮＧＨａｏｚｈｏｎｇ，ＧＡＯＣｉ－ｗｅｉ，ＭＡＺｅｌｉａｎｇ，ｅｔａ１．ＴｈｅｌｅｘｉｃｏｇｒａｐｈｉｃａＵｙｓｔｒａｔｉｆｉｅｄｍｅｔｈｏｄｆｏｒｍｕｌｔ－ｏｂｋｅｃｔｏｐｔｉｍａｌｅｌｅｃｔｒｉｃｐｏｗｅｒｎｅｔｗｏｒｋｐｌａｎｎｉｎｇ［Ｊ］．ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＣＳＥＥ，２００３，２３（１０）：ｌ１．１６．［２］叶在福，单渊达．基于边界搜索策略的遗传算法在电网扩展规划中的应用［Ｊ］．中国电机工程学报，２０００，—２０（１１）：４１４５．ＹＥＺａｉ一，ＳＨＡＮＹｕａｎ－ｄａ．Ａｎｅｗｔｒａｎｓｍｉｓｓｉｏｎｎｅｔｗｏｒｋｅｘｐａｎｓｉｏｎｐｌａｎｎｉｎｇｕｓｉｎｇｉｍｐｒｏｖｅｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｂａｓｅｄｂｏｒｄｅｒｌｉｎｇｓｅａｒｃｈｓｔｒａｔｅｇｙ［Ｊ］．ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＣＳＥＥ，２０００，２０（１１）：４１．４５．［３］叶在福，单渊达．多种群遗传算法在电网扩展规划中应用的改进【Ｊ］．电力系统及其自动化学报，１９９９，１１（５－６）：５５．６１．ＹＥＺａｉ．，ＳＨＡＮＹｕａｎ．ｄａ．Ａｎｅｗｔｒａｎｓｍｉｓｓｉｏｎｎｅｔｗｏｒｋ—ｅｘｐａｎｓｉｏｎｐｌａｎｎｉｎｇｕｓｉｎｇｉｍｐｒｏｖｅｄｍｕｌｔｉｐｌｅｐｏｐｕｌａｔｉｏｎｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ［Ｊ］．ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＥＰＳＡ，１９９９，１１—（５．６）：５５６１．［４］高赐威，程浩忠，王旭．基于计算资源效率分配的多种群中心解搜索电网规划算法［Ｊ】．中国电机工程学报，２００４，２４（１０）：８－１４．——ＧＡＯＣｉｗｅｉ，ＣＨＥＮＧＨａｏｚｈｏｎｇ，ＷＡＮＧＸｕ．Ｍｕｌｔｉ－－ｐｏｐｕｌａｔｉｏｎｃｅｎｔｒａｌｓｏｌｕｔｉｏｎｓｅａｒｃｈｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｃｏｍｐｕｔａｔｉｏｎｒｅｓｏｕｒｃｅｄｉｓｔｒｉｂｕｔｉｏｎｆｏｒｅｌｅｃｔｒｉｃｎｅｔｗｏｒｋｐｌａｎｎｉｎｇ［Ｊ］．ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＣＳＥＥ，２００４，２４（１０）：８．１４．［５］肖峻，王成山，周敏．基于区间层次分析法的城市电网规划综合评判决策［Ｊ］．中国电机工程学报，２００４，．６６．电力系统保护与控制（上接第５９页ｃｏｎｔｉｎｕｅｄｆｒｏｍｐａｇｅ５９）—ＬＩＵＹａｏ－ｎｉａｎ，ｅｔａ１．ＡｓｈｏｒｔｔｅｒｍｌｏａｄｆｏｒｅｃａｓｔｉｎｇａｐｐｒｏａｃｈｂａｓｅｄｏｎｉｍｐｏｓｉｎｇｓｐａｒｓｅｎｅｓｓｕｐｏｎＬＳＳＶＭｉｎｔｅｇｒａｔｅｄＳＭＯａｌｇｏｒｉｔｈｍｓ［Ｊ］．Ｒｅｌａｙ，２００８，３６（４）：—６３６６．［１２］杨立成．基于最小二乘支持向量机的短期电力负荷预测方法研究［Ｄ】．南宁：广西大学，２００８．—ＹＡＮＧＬｉ・ｃｈｅｎｇ．ＲｅｓｅａｒｃｈＯｆｆｓｈｏｒｔｔｅｒｍｅｌｅｃｔｒｉｃｌｏａｄｆｏｒｅｃａｓｔｉｎｇｂａｓｅｄｏｎｌｅａｓｔｓｑｕａｒｅｓｓｕｐｐｏｒｔｖｅｃｔｏｒｍａｃｈｉｎｅ［Ｄ］．Ｎａｎｎｉｎｇ：ＧｕａｎｇｘｉＵｎｉｖｅｒｓｉｔｙ，２００８．［１３］王德意，杨卓，杨国清．基于负荷混沌特性和最小二乘支持向量机的短期负荷预测［Ｊ］．电网技术，２００８，３２（７）：６６．７１．——ＷＡＮＧＤｅｙｉ，ＹＡＮＧＺｈｕｏ，ＹＡＮＧＧｕｏｑｉｎｇ．Ｓｈｏｒｔ－ｔｅｒｍ１ｏａｄｆｏｒｅｃａｓｔｉｎｇｂａｓｅｄｏｎｃｈａｏｔｉｃｃｈａｒａｃｔｅｒｉｓｔｉｃｏｆｌｏａｄｓａｎｄｌｅａｓｔｓｑｕａｒｅｓｓｕｐｐｏｒｔｖｅｃｔｏｒｍａｃｈｉｎｅｓ［Ｊ］．ＰｏｗｅｒＳｙｓｔｅｍＴｅｃｈｎｏｌｏｇｙ，２００８，３２（７）：６６．７１．［１４］廖向旗，等．基于灰色关联聚类的负荷特性分类［Ｊ】．电力科学与技术学报，２００７，２２（２）：２８．３３．ＬＩＡＯＸｉａｎｇ．ｅｌｉ．ｅｔａ１．ＣｌａｓｓｉｆｉｃａｔｉｏｎｏｆｓｕｂｓｔａｔｉｏｎｌｏａｄｃｈａｒａｃｔｅｒｉｓｔｉｃｓｂａｓｅｄＯｆｆｇｒａｙｒｅｌｅｖａｎｃｙｃｌｕｓｔｅｒｉｎｇ［Ｊ］．ＪｏｕｒｎａｌｏｆＥｌｅｃｔｒｉｃＰｏｗｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，２００７，２２（２）：２８．３３．［１５］钱卫华，等．基于负荷特性分析的短期负荷预测相似日选择方法［Ｊ】．华中电力，２００７，２０（１）：１７．２１．ＱＩＡＮＷｅｉ－ｈｕａ，ｅｔａ１．Ｔｈｅｓｅｌｅｃｔｓｉｍｉｌａｒｄａｙｓｍｅｔｈｏｄｆｏｒｓｈｏｒｔ．ｔｅｒｍｌｏａｄｆｏｒｅｃａｓｔｉｎｇｂａｓｅｄｏｎｌｏａｄｃｈａｒａｃｔｅｒｉｓｔｉｃａｎａｌｙｓｉｓ［Ｊ］．ＣｅｎｔｒａｌＣｈｉｎａＥｌｅｃｔｒｉｃＰｏｗｅｒ，２００７，２０（１）：—】７２】．—收稿日期：２００９０７－２５作者简介：李光珍（１９８５一），男，硕士研究生，研究方向为电力系统负荷预测、电力系统智能调度；Ｅ．ｍａｉｌ：８５１ｇｚ＠１６３．ｔｏｍ刘文颖（１９５５－），女，教授，博士生导师，研究方向为电力系统智能调度、负荷预测、电力系统分析与控制。