（电力系统及其自动化专业论文）基于内点分支定界法的最优机组投入研究.pdf

摘要 关键词：机组投入发电计划电力市场原始对偶内点算法分支定界法内点割平 面法拉格朗日松弛法半定规划 n r e s e a r c ho nu n l tc o m m i t m e n tb a s e do ni n t e r i o r p o i n t - b r a n c ha n db o u n dm e t h o d a b s t r a c t u n i tc o m m i t m e n tp r o b l e mi sa ni m p o r t a n tt a s ki nb u i l d i n gu pg e n e r a t i o np l a n n i n go f m o d e mp o w e rs y s t e m s ，w h i c hh a sp r o m i n e n te c o n o m i cb e n e f i tt oo p t i m i z ei t t h e r e f o r e , i t i sag r e a t l yp o p u l a rs u b j e c t f r o mt h ev i e wo fm a t h e m a t i c s , i ti san p - h a r dc o m b i n a t i o n a l o p t i m i z a t i o np r o b l e mw i t hc o n s t r a i n t sa n di ti sd i f f i c u l tt of i n dt h eg l o b a lo p t i m a ls o l u t i o n i nt h e o r y n l i sp a p e rm a i n l yp r o p o s e si n t e r i o rp o i n t - b r a n c ha n db o u n dm e t h o df o ru n i t c o m m i t m e n tp r o b l e m f i r s t l y , t h i sp a p e rs u m m a r i z e st h em a i nc o n t e n to fg e n e r a t i o np l a n n i n g , d e s c r i b e st h e r e s e a r c hm e a n i n go fu n i tc o m m i t m e n tp r o b l e m ，m a k e sc o m p a r ew i t he c o n o m i cd i s p a t c h a n dt h eo p t i m a lp o w e rf l o w , b r i e f l yd e s c r i b e su n i tc o m m i t m e n tp r o b l e mi ne l e c t r i c i t y m a r k e li n t r o d u c e st h er e s e a r e hs i t u a t i o na b o u tt h i ss u b j e c t s e c o n d l gt h em a t h e m a t i c a lm o d e lo fu n i tc o m m i t m e n tp r o b l e mi nt r a d i t i o na n di n e l e c t r i c i t ym a r k e ti sc o n c r e t e l yr e s e a r c h e d ；k i n d so fo p t i m a lm e t h o d sf o ru n i tc o m m i t m e n t a r er e v i e w e da n ds u m m a r i z e d t h e n ，t w oa l g o r i t h m sa r em a i n l yi n t r o d u c e di nd e t a i la n d r e s p e c t i v e l y - - - p r i m a l d u a li n t e r i o rp o i n tm e t h o d ( p d i p m ) ，b r a n c h - a n d b o u n dm e t h o d ( b b m ) a n d i n t e r i o rp o i n t b r a n c ha n db o u n dm e t h o d ，w h i c hi sm i x e db yt h et w om e t h o d s i nu n i tc o m m i t m e n tp r o b l e m ，b e c a u s et h eb o u n d a r yo fi n e q u a l i t yc o n s t r a i n t sc o n t a i n s v a r i a b l e s ，w h i l es o l v i n gt h er e l a x e du n i tc o m m i t m e n tp r o b l e m ，t h ep a p e ra d o p t s p r i m a l d u a li n t e r i o rp o i n tm e t h o dt os o l v en o n l i n e a rp r o g r a m m i n gm o d e l sw h o s e i n e q u a l i t yc o n s t r a i n t sa r eu n i l a t e r a lb o u n d a r y t h i sm i x e da l g o r i t h mo p t i m i z e st h er e l a x e d z e r o - o n ev a r i a b l e sa n dt h ea c t i v ep o w e rc o n t i n u o u sv a r i a b l e ss i m u l t a n e o u s l y i n t e r i o rp o i n t m e t h o db a s e do np e r t u r b e dk a r u s h k u h n t u c k e r ( k k t ) c o n d i t i o n s ，w h i c hc o n v e r g e n c e s r a p i d l ya n di sn o ts e n s i t i v et ot h ei n i t i a lp o i n t ，i sa d o p t e dt os o l v eas e r i e so ft h er e l a x e d p r o b l e m s ，w h e nb r a n c h a n d b o u n dm e t h o di su s e dt od e a lw i t ht h e0 - 1d i s c r e t ev a r i a b l e s ， t w ok i n d so f p r o g r a m m i n gt h o u g h ta l ea d o p t e d t h r e ec a s e so f3u n i t sf o r4h o u r s 、10u n i t sf o r2 4h o u r sa n d4u n i t sf o r3h o u r si n e l e c t r i c i t ym a r k e ta r es i m u l a t e d a tt h ef i r s t e c o n o m i cd i s p a t c h , i ts h o w st h a to p t i m i z i n g l i t t w oe a s e s c o m p a r e d 、) l ，i mt h er e s u l t so f u n i tc o m m i t m e n tp r o b l e mh a sp r o m i n e n t e c o n o m i cs i g n i f i c a n c e ；w h i l ec o m p a r e dw i t hl i t e r a t u r e 【1 0 ，1 3 ，1 9 ，n u m e r i c a lr e s u l t s d e m o n s t r a t et h a ta d o p t i n gi n t e r i o rp o i n t - b r a n c ha n db o u n dm e t h o df o ru n i tc o m m i t m e n t p r o b l e mc a ng e tb e t t e ro p t i m a ls o l u t i o n ，a n da l s od e m o n s t r a t et h ef e a s i b i l i t ya n dv a l i d i t yo f i n t e r i o rp o i n t b r a n c ha n db o u n dm e t h o d t h ep a p e ra l s oa d o p t si n t e r i o r - p o i n t c u t t i n g - p l a n em e t h o d st os o l v et h ed u a lt ot h e u n i tc o m m i t m e n tp r o b l e m l a g r a n g i a l lr e l a x a t i o nm e t h o di su s e da st h em a i na l g o r i t h m ； t h ed u a li sd i s a g g r e g a t e di n t ot h ep e rt h e r m a l - u n i tc o m m i t m e n tp r o b l e m s , w h i c hi ss o l v e d b ys e m i - d e f i n i t ep r o g r a m m i n gs o f t w a r e ；t h em a x i m i z a t i o no ft h eu n i tc o m m i t m e n t p r o b l e mi ss o l v e db yi n t e r i o r - p o i n f f c u t t i n g - p l a n em e t h o d sb a s e do nt h ea n a l y t i cc e n t e r , t h ep r i m a lo p t i m a ls o l u t i o nc a nb eg o t t e n n u m e r i c a lr e s u l t so nt h ec 黜o f3u n i t sf o r4 h o u r sd e m o n s t r a t et h a ta d o p t i n gi n t e r i o r - p o i n t c u t t i n g p l a n em e t h o d sf o ru n i tc o m m i t m e n t p r o b l e mi sf e a s i b l e k e y w o r d s ：u n i tc o m m i t m e n t ；g e n e r a t i o np l a n n i n g ；e l e c t r i c i t ym a r k e t ；p r i m a l d u a li n t e r i o r p o i n t m e t h o d ( p d i p m ) ； b r a n c h - a n d - b o u n d m e t h o d ( 8 8 m ) ； i n t e r i o r - p o i n t c u t t i n g - p l a n em e t h o d s ( i p c p ) ；l a g r a n g i a nr e l a x a t i o nm e t h o d ： s e m i - d e f i n i t ep r o g r a m m i n g i v 主要符号说明 f r “ g q 、以、q 己 s 。 s m h x 。 x 唾 乙 q 足 只一 只。 只 x 厂( ) f 1 g ( ) ( ) 、( ) ，甜 z w 主要符号说明 总发电成本 时段总数 机组总数 机组f 在第，时段的状态 机组f 在第，时段的发电成本 机组i 发电费用函数的参数 机组i 在第t 时段的有功出力 机组珀q 启动成本 机组i 的热启动成本 机组i 的冷启动成本 机组i 的冷启动时间 机组f 到第t 时刻已连续运行的时间段 机组f 到第f 时刻已连续停机的时间段 机组i 的最小运行时间 机组i 的最小停机时间 第，时段的系统总负荷 第，时段的系统总备用 机组i 的最大有功出力 机组i 的最小有功出力 机组i 在第f 时段的有功输出速度 机组i 在第，时段出力的单位电量报价 原始目标函数 等式约束 不等式约束 变量或参数的上下界 不等式约束的松弛变量 不等式约束的拉格朗日乘子 v 主要符号说明 y 厶u ，z ，矿 ，l r 2 册 v f ( ) 7 v h ( - ) 7 取 v 2 ，( ) v 2 ( ) v 2 9 ( ) g a p q e 一 占。 仃 k m a x ，幽，：，a w s t e p p s t e p d n u m 工 五 五 岛，$ t l ( ) 甲( ) q 等式约束的拉格朗日乘子 以，甜，：，w 为对角元的对角矩阵 仅含下界的不等式约束的维数 仅含上界的不等式约束的维数 等式约束的维数 目标函数的j a c o b i a n 矩阵 等式约束的j a c o b i a n 矩阵 不等式约束的j a c o b i a n 矩阵 目标函数的h e s s i a n 矩阵 等式约束的h e s s i a n 矩阵 不等式约束的h e s s i a n 矩阵 互补间隙 扰动因子 仅含下界的不等式约束对应的单位向量 仅含上界的不等式约束对应的单位向量 计算精度 中心参数 最大迭代次数 迭代修正量 最大原始步长 最大对偶步长 机组状态变量的上界 机组状态变量的下界 总的未知变量的个数 原始变量 机组珀q 微增率 拉格朗日乘子 半定规划中引入的松弛变量 对偶目标函数 对偶目标函数的次梯度 凸的闭区域 v i 第一章绪论 1 1 发电计划概述 第一章绪论 电力系统是由发电、输电、配电和负荷组成的。制定发电计划是电力系统首先要 解决的问题。其目的是在满足系统安全和电能质量要求的条件下，依据电厂的发电能 力、电网的输送能力和用户的要求，预先制定系统的运行方式，尽可能满足系统运行 的经济性，以最低的运行费用保证对用户可靠而满意的供电。 在能量管理系统( e m s ) 中，狭义的发电计划是指火电计划，广义的发电计划主 要包括以下几个部分的内容i l j ； 1 负荷预测 由于发电计划是要预先制定系统运行方式，所以首先要进行负荷预测，作为制定 发电计划的依据。负荷预测的精度直接影响发电计划的准确性，进而影响系统的运行 成本和发电计划的效益，所以高精度的负荷预测可以降低备用容量，减少临时功率调 整和避免计划外开停机。 2 机组投入 机组投入用于解决调度周期内丁| ：停机问题。系统负荷在调度周期内变化范围很大 时，有时仅改变机组出力大小而不改变机组组合方式时，调节范围难以满足负荷变化 的要求。机组投入是在调度周期内合理地选择运行的机组，并且经济地分配有功负荷， 使系统的总运行费用最小。 3 机组间经济功率分配 经济功率分配是在已确定开停机的情况下，在运行的机组之间合理的分配有功负 荷，使系统的运行费用最低。 4 水火电协调 火电调度的特点是按发电费用微增曲线调度，使系统运行费用最小；而水电机组 的调叟则名巫调整峰荷，使火电厂平秘运行，从而降低运行费用；同时兼顾水i 乜的特 点使非径流式水电厂尽量维持高水头运行，在同样来水情况下多发电。水火电协调就 是协调这两方面的利益，使系统运行费用最低。 5 发电与输电协调 除了发电具有经济性外，网络也有经济性，主要表现为网络传输损耗的多少。有 第一幸绪论 的电厂靠近燃料基地，发电经济性好，但送电到负荷中心则会引起较大的网损；有些 电厂靠近负荷中心，发电经济性差，但增加功率却使网络损耗下降。因此，发电与输 电协调就是解决发电与输电的综合经济性最优问题。 发电计划的构成如图1 1 所示： 1 2 机组投入问题 图1 - 1发电计划的构成 f i g 1 1 t h ec o n s t r u c t i o no f g e n e r a t i o np l a n 1 2 1 机组投入问题的提出 电力系统运行的基本目的是安全地向用户提供质量合格的电能【2 l 。而系统的负荷 是时刻在变化的。机组运行时，发电机发出的有功功率不同，运行效率及燃料消耗量 也不同，一般机组的最高效率运行点都在接近额定功率处 若不增减或变换参加运行的机组，当系统负荷较大时，各机组的运行效率将较高； 而当系统负荷减少时，各机组运行点将降低，效率也会降低。因此，若在系统负荷变 小的同时，减少参加运行的机组台数或改投容量较小的发电机组，将有可能使各个运 行机组维持较高的运行效率，使系统有更小的燃料损耗。 另外，有时会出现下列情况，即对较大负荷安排的机组组合，用于较低负荷d t 时， 各机组出力下限总和会大于d ，这也从技术上迫使人们改变运行的机组组合方式。 除此之外，在根据负荷的不同选取技术上可行且运行耗量低的机组组合方式时， 还要考虑机组自身的一些因素。其中最重要的两个因素是： 1 机组不能频繁启停，即要求机组停机和运行的时间段分别满足最小停机时间 和最小运行时间的要求，而不能频繁启停； 2 机组停机后再启动时要额外消耗一定的燃料，称为启动耗量。 2 第一幸绪论 综上，合理地选择各时段上参加运行的机组，不仅可以提高机组的发电效率，而 且可以产生可观的经济效益。 1 2 2 机组投入问题的研究意义 在整个发电计划中，机组投入是基础，主要是解决机组的丌停机问题，其经济效 益显著。机组投入的效益大致可达2 5 ，经济负荷分配的效益为o 5 n 1 5 。有资 料显示，对大的电力公司，每年燃料费用减少o 5 ，就可以节省上百万美元p j ，由此 可见，合理的丌停机方案将会产生可观的经济效益。 传统的机组投入问题( u n i tc o m m i t m e n t ，简称u c 问题) 也称开停机计划，指的 是：根据负荷预测，在满足系统负荷、备用容量和启停时间等约束条件下，确定一个 调度周期( 通常是2 4 h ) 内，各时段机组的组合方式和各机组在运行时段的出力，使 得在该周期内的总发电费用最d , 1 4 1 。 从数学角度讲，机组投入问题是一个混合o - l 整数的非线性规划问题，到目前为 止还很难找到理论上的最优解。但是由于机组投入问题具有显著的经济效益，所以人 们一直在积极研究它，提出各种方法解决该问题，如启发式方法、优先顺序法、动态 规划法、整数规划和混合整数规划法、分支定界法、拉格朗日松弛法、专家系统法、 人工神经网络法、模拟退火算法、遗传算法等【3 j 。 1 2 3 机组投入和经典经济调度的比较 经典经济调度是指在系统中参加运行的机组已经预先确定的情况下，将负荷优化 地分配给各个运行的发电机组，使全系统的发电费用最小。 “ 经济调度发展大致经历了基本负荷法、最优负荷法和等微增率法三个阶段。模型 中的目标函数多为燃料耗量或发电费用最小，且只含有发电机的有功功率约束和少量 的线路安全约束。然而，经典经济调度的优势是原理简单、计算迅速，具有很高的实 用价值，但是它主要考虑系统运行的经济性，忽略了安全性、稳定性等约束，给系统 运行带来了安全隐患。 由上可知，经济调度主要是解决有功出力的分配问题，是一个只含有连续变量的 优化问题。而在机组投入问题中，不仅要求解机组出力变量，同时还要求解机组状态 变量，即是一个含有j 生续变量和离敞变量的混合整数上兕划问题，这使求解十分团难。 1 2 4 机组投入和最优潮流的比较 最优潮流简称o p f ( o p t i m a l p o w e rf l o w ) ，是电力系统在满足特定运行和安全约束 条件下，通过调整系统中可利用的控制手段，实现预定目标最优的系统稳定运行状态。 第一幸绪论 最优潮流把电力系统经济调度和潮流计算有机结合起来，以潮流方程为基础，进 行经济与安全的优化，是一个复杂的非线性规划问题。其优化目标可以为线路有功损 耗最小、线路无功损耗最小、发电费用最小、系统有功损耗最小、无功补偿费用最小 等。其等式约束一般为潮流方程，不等式约束一般为发电机有功功率约束、无功功率 输出约束、电压幅值、线路功率约束等。 由上可知，最优潮流也是一个只含连续变量的非线性规划问题随着计算机技术 和数学的发展，现在能求解的问题规模也越来越大 综上，机组投入与经典经济调度和最优潮流的区别为：机组投入是一个含有离散 变量和连续变量的混合整数非线性规划问题，而且时间段间存在耦合关系，这使得机 组投入问题的求解变得十分困难 1 3 电力市场下的机组投入问题 在仅开放发电侧的电力市场下，机组投入问题是指各个发电公司申报竞价上网数 据，交易管理员根据这些竞价数据，按照“公平、公正、公开”的原则，以全网购电 费用最小为目标，在满足电力系统各种约束条件下，制定机组组合计划以及各个机组 在各个时段的出力1 5 】。 机组投入计划的制定和执行是电力市场运转的核心，如何制定公平、合理的机组 投入计划直接关系到电力市场能否健康、顺利地进行和发展。在传统的电力运营模式 下，调度部门对下属电厂拥有完全的控制权，机组投入计划的制定和调整是调度员根 据运行规则来制定的，以保证系统的可靠运行。但是，在电力市场条件下，调度运行 部门作为电力经纪人出现，他的职责要求制定出使电网运营效益甚至是全社会效益最 大的机组投入计划。虽然这个计划要满足各种约束，但是它是在保证系统安全的条件 下，以全网购电费用最小为目标。 。制定机组投入计划是一个非常复杂的过程。交易管理员在接收到各个发电公司上 报来的竞价数据后，在考虑多个约束条件下，经过一系列的复杂计算才能得到一个可 行的机组投入计划。这些约束条件可以分为以下三类： 1 系统约束，包括系统功率平衡约束和系统旋转备用约束； 2 机组约束，包括机组出力约束、机组爬坡速度约束和机组最小启停时间约束； 3 网络约束，包括区域内线路传输能力约束和区域联络线传输能力约束 4 第一章绪论 由于这些约束的限制，使得机组投入计划的制定成为一个带约束条件的最优化问 题。如何快速准确地得到满足这些约束条件的最优解或次优解，足交易管理员面临的 首要问题。 在仅开放发电侧的电力市场环境下，机组投入问题同传统的经济调度模式下的机 组投入问题有所不同，这种差异主要体现在： 1 在电力市场环境下，编制发电计划的目的是以购电费用最小，而不是以总发 电费用最小为目标： 2 为了获取最大利润，各发电公司的报价是任意的，而不再像在经济调度模式 下那样，发电机的煤耗曲线是固定的，启动费用也大致相同； 3 相应地，发电机组的技术参数在电力市场环境下也是不确定的。 1 4 本课题的研究现状 机组投入问题无论是在传统的经济调度下还是在电力市场环境下都是一个 n p - h a r d 问题。但是由于该问题具有显著的经济效益，所以国内外众多学者一直在积 极地研究它。 1 4 1 国外研究现状 1 9 9 7 年，美国旧金山太平洋燃气和电气公司( p g & e ) 李朝安等人介绍了一种基 于机组退出过程的动态规划方法，用于解决电力能源规划问题。它是从所有可以利 用的机组全部投入这一初始方案丌始，按照某一具体的经济指标，利用动态规划法一 次退出一台机组。动态规划法能保证解的可行性，但是该法最大的缺点就是“维数灾” 问题，这就导致了计算时间令人难以接受。 为了克服动态规划法“维数灾”的问题，常采取一定的措施限制状态的数目。1 9 9 8 年，印度学者s e n 等人用修剪的动态规划法求解多区域的u c 问题并且把该法用于 i n d i a n 电力系统的两个具有不同的运行特征的区域。但是该法是选取优先顺序表前面 一定数目的机组的丌停机状态组合方式作为各阶段的状态，有可能丢失最优解。 在求解u c 问题的诸多方法中，拉格朗日松弛法是应用最广泛的一种方法。1 9 9 5 年，荚国德克萨斯州大学b a l d i c k 建立了一个通用的机组组合梭型”3 ，可以包括最小 开停机时问约束、潮流约束、线路潮流约束、电压约束、旋转备用约束、机组爬坡速 率、总燃料和能量约束等，并用拉格朗日松弛法和辅助问题原理来解这个模型，但是只 对一个小的算例进行了计算。 5 第一章绪论 1 9 9 7 年，文献 9 考虑了火电厂和水电厂的机组组合问题，分解成火电厂和水电 厂子问题，火电厂用常规的拉格朗日松弛法求解，水电厂子问题分为流域，流域再分为 水库，流域级用网络流规划法，水库级的水力机组组合问题用动态规划顺序联合法 ( d y n a m i cp r o g r a m m i n gs e q u e n t i a lc o m b i n a t i o n ) 求解，使用连续逼近法优化水电厂子 问题的拉格朗日乘子 t 2 0 0 0 年，台北大学程川平等人把遗传算法结合到拉格朗日松弛法中以修正 l a g r a n g i a n 乘子，结果得到了近似最优解“”。同年，加拿大w a t e r l o o 大学m a d r i g a l 等人在文献 1 1 中应用内点一割平面法求解l a g r a n g i a n 函数的对偶问题，加入割平面 后，将对偶问题转化为线性规划问题，再用内点算法求解，它是基于内点算法良好的 收敛性以及不受参数困扰的特点。 。 2 0 0 2 年，西安交通大学翟桥柱等人指出在求解l a g r a n g i a n 子问题时，相同的机 组会得到同样的解，而这可能导致对偶解偏离最优解以及引起解的振荡。基于这种分 析，他们结合增广拉格朗日法和次梯度法，在高标准下产生一个好的搜索方向，这样 低水平的子问题也可以求解。因此即使有相同的机组投入方式，在对偶问题中也不会 产生相同的解n 一。 。 1 9 9 6 年，文献 1 3 将遗传算法应用于机组组合问题，为克服简单遗传算法过早收 敛的缺陷，引入变化性质函数( v a r y i n gq u a l i t yf u n c t i o n ) 技术，并对具体问题加入了特 殊的算子，计算结果表明，对于大系统，遗传算法比拉格朗日松弛法优化效果更好。 1 9 9 9 年，澳大利亚西门子公司r u d o l f 等人把遗传算法应用于水火电力系统“”。 首先用遗传算法确定机组的启停状态，然后采用拉格朗日松弛法求解一个非线性规划 问题，以便进行经济分配为了节省时间，只有给定的机组组合方式满足功率平衡等 约束条件时，才进行负荷分配 2 0 0 2 年，文献 1 5 】等人采用遗传算法求解u c 问题，并且在数学模型中考虑了启 动费用、最小启停时间约束和旋转备用约束，使用了一种新的方法来表示染色体，并 且对搜索空间进行了编码，结果证明是有效的。并且该方法能处理大规模u c 问题。 遗传算法比较灵活，可以考虑多种约束，适合于并行处理。但是由于是随机优化算法， 不能保证得到全局最优解；计算量比较大，所需时间长“”。 2 0 0 3 年，日本冲绳r y u k y u s 大学s e n j y u 等人使用扩展的优先顺序法求解u c 问 题。该法由两步构成：第一步是运用优先顺序法快速地得到一些初始机组组合方式， 但是没有考虑运行约束；第二步是使用启发式的方法来修正这些组合方式，以满足运 行约束。但是，如果要提高计算效率，必须要改进一些启发式的方法” 1 9 9 8 年，埃及k i n ga n df a h d 大学m a n t a w y 等人把u c 问题分成两个子问题“”： 6 第一章绪论 一个联合优化问题和一个非线性规划问题。前者采用模拟退火法求解，而后者使用二 次规划法求解。并称模拟退火法与初始解无关，并且不需要很复杂的数学模型。但是 花费的c p u 时间很长。 1 9 9 9 年，日本札幌北海道大学j u s t e 等人采用进化算法求解u c 问题。即通过任 意的变换、竞争和选择来进化那些包含有解的种群“。2 0 0 1 年，文献 2 0 把蚁群搜 索算法应用于水力发电规划问题。首先是确定多区域规划的中心搜索空j 日j ，然后通过 有记忆的“蚂蚁”的相互交流和合作，得到近似最优解。该法本身的不足在于容易出 现“停滞”现象，导致最后只能收敛于局部最优解。 2 0 0 2 年，文献 2 1 提出了一种改进的t a b u 搜索算法求解经济调度问题。称改进 的t a b u 搜索算法使用一个灵活的记忆系统以避免陷入局部最优解，并且采用并行算 法来减弱该算法的收敛速度对初始条件的依赖。 2 0 0 2 年，文献 2 2 提出了一种联合进化算法解u c 问题，该算法是传统的进化算 法的扩展。这种方法结合拉格朗日松弛法和遗传算法的基本思想，先用次梯度法优化 拉格朗日乘子，再用遗传算法求解单个机组的组合子问题。 1 9 9 9 年，埃及m a n t a w y 等人将遗传算法、t a b u 搜索和模拟退火法结合到一起形 成混合算法来求解机组投入问题1 。把t a b u 搜索法加入到遗传算法中以产生新的种 群成员，再用模拟退火法加速遗传算法的收敛。这种混合算法的优势就是能够“取长 补短”。 2 0 0 3 年，印度m a l n a d 大学p u r u s h o t h a m a 等人将模拟退火法和基于优先顺序的机 组退出过程结合到一起。该混合算法将模拟退火法作为主算法，在每一个温度，任意 的产生新解，这些新解可能都是可行的。再采用启发式的退出过程技术，在最优解的 邻域内做局部的搜索，寻找最优解。这种组合算法提高了收敛性，有很强的鲁棒性嘲1 。 1 4 2 国内研究现状 1 9 9 4 年，哈尔滨工业大学韩学山、柳焯对发电机组输出功率速度限制下的u c 问 题进行了研究，提出了基于拉格朗同松弛原理的协调求解方法。构造了在松弛功率平 衡约束情况下的分离单机子问题的网络模型。从而利用最短路径算法求出可行的组合 方案。在此基础上，利用积流量法进行调整，从而达到机组组合与运行的良好协调。1 。 1 9 9 7 年，华i | j 理工大学赵宏伟、任震构造了基于直流潮流法的线路安全约水模 型汹3 。在改进遗传算法的基础上，提出了求解的方法。它克服了机组最优投入和负荷 安全经济调度互相分割，导致调度的发电水平和机组投入建设的水平严重偏离而使燃 料消耗增加的问题。 7 第一幸绪论 2 0 0 0 年，西安交通大学赖菲等人提出了一种机组优化启停的新型启发式方法 首先用动态规划法求出计算负荷下各个待丌机组的优化启停状态及相应的启停费用， 将效率最高的机组投入运行，然后用拉格朗日松弛法进行最优经济分配。该方法克服 了优先顺序表法没有考虑启停机费用对机组优先级影响的不足，缩短了计算时间乜力 2 0 0 1 年，哈尔滨工业大学王承民等人考虑了包括发电机爬坡约束等动态约束在 内的各种约束条件。对机组投入问题的o 、l 变量进行松弛，并在目标函数中增加一 个惩罚函数项，将问题变换成一个非线性连续变量的目标规划问题，用二次规划法求 解嗍同年，他们在电力市场环境下提出了一种组合优化方法解决u c 问题，即用启 发式方法确定机组组合，再用分段线性规划算法分配功率，并满足各种约束条件嘲 2 0 0 2 年，重庆大学郝晋、周家启等人尝试用蚁群优化算法求解u c 问题。尝试把 u c 问题设计成类似于t s p 问题的模式，并灵活处理各种约束，用t a b u 表来限制不 满足旋转备用约束和机组最小启停时间约束的状态，通过附加惩罚项来处理n 安全性 约束咖。 2 0 0 3 年，武汉大学赵小利等人提出了以利润最大为目标函数的优化火电机组启 停的改进遗传算法。”。该算法提出了启发式初始解和改进遗传操作，克服了基本遗传 算法处理u c 问题的不足，能方便有效地处理火电机组优化组合的复杂约束问题，提 高了收敛速度，有实用价值。 2 0 0 3 年，华中科技大学吴金华等人提出了一种适合解决机组组合问题的扩展 h o p f i e l d 神经网络算法，该算法结合了h o p f i d d 神经网络法和模拟退火算法的优点， 对整数变量取值范围进行了可行的扩展，有效地避免了陷入局部最优的情况。同时， 该算法无需进行额外的负荷经济分配，故能迅速、高效地搜索到系统的优化解d 习 2 0 0 3 年，清华大学丁军威等人提出了一种适合中国现阶段国情的发电侧逐步市 场化的竞价新模式。其核心思想是在电力市场化的初期，将发电机组划分为市场内、 外两组。市场内机组实现竞价上网；市场外仍按核定成本发电，并可保留合同。并且 已经在实际系统中得到应用嘲。 2 0 0 4 年，深圳供电公司金毅等人提出了一种松弛算法解决电力市场环境下的机 组组合问题。主要思想是在满足机组时间约束的基础上，对原问题进行松弛，从而形 成一个以松弛子问题序列为依据的切机过程。切机的原则是机组的出力最小，因为松 弛子问题的目标函数值是逐渐增大逼近到最优解，通过一个上界算法作为迭代过程终 止的判据。但是，该算法只是一种启发式方法，不能得到原问题的最优解。 8 第一幸绪论 1 5 本文的算法选择和主要研究内容 1 5 1 算法选择 由于机组投入问题中机组状态变量为o 1 变量，因此机组投入问题是一个连续变 量和离散变量共存的非线性混合整数规划问题，求解十分困难。 本文主要采用现代内点算法和分支定界法相结合，组成混合算法一内点分支定 界法求解机组投入问题。分支定界法是一种求解整数规划问题或混合整数规划问题的 有效方法。该方法通过逐步细分可行域，将求解原问题转化为求解一系列的松弛子问 题，即非线性规划问题。采用现代内点算法求解这些松弛子问题。通过分支，将松弛 的离散变量逐步逼近到整数值，从而找到原问题的最优解。因此，采用内点分支定 界法求解机组投入问题是可行的。 本文还尝试采用内点割平面法求解机组投入问题的对偶问题。割平面法是通过 增加线性约束( 称之为割平面方程) ，不断缩小可行域的范围，从而取得整数最优解。 1 5 2 主要研究内容 通过对近十年发表的学术资料的研究和分析，本文主要研究内容概括如下： 1 由于机组投入问题的不等式约束的边界上含有待求变量，本文尝试把不等式 约束转化为两种类型的不等式：即只含有上界的不等式和只含有下界的不等式。 具体模型形式和求解过程可参看第3 章。 通过计算3 个算例的一系列的松弛子问题，检验了这种模型的正确性。通过调节 各个l a g r a n g i a n 乘子的初值，使用现代内点算法求解，均能很快地收敛到最优解。 2 在用分支定界法处理离散变量时，由于待分支变量在分支时只是取值为o 或 1 两种情况，本文分别采用了两种编程思想： ( 1 ) 通过设置上、下界相同，即u 。= u i 血= o 或l ，达到取值为0 或l 的目的。 ( 2 ) 在调用内点法求解一系列的松弛子问题时，直接把待分支变量取为定值0 或1 ，不作为待求变量，即随着分支的进行，待求的机组状态变量的数目越束越少。 分别通过3 个算例，编程实现了如上的两种思想。结果表明，这历种思路都是u ， 行的。具体可参看第4 章。 3 初步研究了电力市场下的机组投入问题。 在一个4 机3 时段的算例中，报价曲线分别按各个机组的报价结算和按统一边际 电价结算时，得到了不同的结果，且结果与实际情况是相符的。 结果表明，把内点分支定界法应用于电力市场下的机组投入问题也是可行的。 9 第一幸绪论 4 编写了多时段的经济调度程序 为了与最优投入计划下的机组投入问题的结果进行比较，编写了多时段的经济调 度程序。 通过对2 个3 机4 时段和l o 机2 4 时段的算例进行仿真计算和比较，结果表明， 在经济调度下得到的总发电费用远远大于最优投入计划下的总发电费用。由此可见， 对机组投入问题进行优化研究具有显著的经济效益。 5 内点割平面法求解机组投入问题 ， 使用拉格朗日松弛法作为主算法，通过拉格朗日乘子，将功率平衡约束和旋转备 用约束加入到目标函数中，形成对偶目标函数；将对偶问题解耦成单个机组的子问题， 将单个机组的子问题数学模型转化为半定规划的标准形式，调用半定规划软件包求 解；采用解析中心的内点名0 平面法求解对偶问题，修正拉格朗日乘子，从而得到原 问题的最优解。 本文通过一个3 机4 时段的算例，验证了内点名0 平面法求解机组投入问题的可 行性。 i o 第= 章机组投入问题的数擘模型 第二章机组投入问题的数学模型 2 1 机组投入问题的数学模型 机组投入问题( u c 问题) 就是在一个运行周期内，在满足系统和机组自身约束 的条件下，确定机组的最佳组合方式和有功出力情况，使得该周期内的总发电费用最 小。总发电费用包括两项：发电费用和启动费用。其数学模型表示如下： 2 1 1 目标函数 本文以总发电费用( 包括发电费用和启动费用) 最小作为目标函数。具体表示为： m i n f = 【玑巴+ 玑( 1 一。) s 】 ( 2 - 1 ) r l li = l 其中：f ：总发电成本； t ：时段总数； n ：机组总数； u 。：机组i 在第t 时段的状态，即 f l ，机组处于运行状态 “2 1 0 ，机组处于停机状态 q ：机组f 在时刻f 的发电成本，表示为巳= q + 6 j 只+ q 只2 ( 2 2 ) ( q 、岛、q 为机组f 发电成本函数的参数) ； 只：机组，在第，时段的实际出力； 墨：机组j 的启动成本，简化为 i s h ，瓦矿x 够r 矽+ 日川 s ，= ( 2 - 3 ) s m x 呵 t 呵+ h 。q 式中瓯。为机组f 的热启动成本；瓦为机组珀冷启动成本；以为机组，的 冷启动时间；x 面为机组f 到第t 时刻已连续停机的时间段； ：机组i 的最小停机时间。 第：幸机组投八问题的数学模型 2 1 2 等式约束 机组投入问题的等式约束为功率平衡约束。所有运行机组的总发电量必须满足负 荷要求。本文忽略了网络损耗。具体表示为： 吼只一q = o ( r = 1 ，2 ，d j l ( 2 - 4 ) 其中：口：第t 时段的系统总负荷。 2 1 3 不等式约束 1 旋转备用约束 为了维持系统的可靠性，还要提供充足的旋转备用( 即在一个时间段内，如果一 台机组停运的话，其他机组必须有足够的备用容量以弥补这一损失) 以只一a d , + 置 ( f = l ，2 ，丁) ( 2 - 5 ) ，一l 其中：置：第，时段的系统总备用，一般取为系统总负荷的百分数，本文取为1 0 的d ， 2 机组出力约束 每台机组的出力都有一定的范围，即 乩只。只以只一 ( 2 6 ) 其中，只一为机组珀q 最大有功出力，e 。为机组f 的最小有功出力。 3 最小启停时间约束 机组只有在运行( 或停机) 一段时间之后才能再停机( 或起动) ，即机组要满足 最小启停时间约束： jl乙(2-7) 【如t o n 其中，。y 0 为机组f 到第t 时刻已连续运行的时间段，乙为机组f 的最小运行时问。 4 机组输出功率速度约束 只- l 一己只s 只- l + 己 ( 2 - 8 ) 其中，只为机组f 在第t 时段的有功输出功率速度。 1 2 第二章机组投八问题的数学模型 2 2 电力市场下机组投入问题的数学模型 在电力市场中，根据实际系统不p j 的要求，时机组投入问题可以建立不同的模型。 一般情况下，应以系统各发电机组的丌停机状念和机组出力为待求变量，在满足系统 负荷和备用要求、线路潮流限制、机组爬坡速率、最小丌停机时问以及市场条件下独 立发电厂和用户问、交易中心和电厂日j 的合同交易等约束条件下，使系统向发电机组 的购电费用最小。 本文对仅开放发电侧的电力市场进行了初步研究。忽略了某些约束，如线路潮流 约束和合同交易约束等。本文所采用的数学模型描述如下嘲： 2 - 2 1 目标函数 本文以总购电费用最小作为目标函数。具体表示如下： 其中，为机组f 在第，时段出力的单位电量报价。 ( 2 9 ) 2 2 2 等式约束 电力市场下，机组投入问题的等式约束为功率平衡约束。本文忽略了网络损耗。 具体表示为： u 。只一d = 0 ( f = 1 ，2 ，r ) i - i 2 2 3 不等式约束 ( 2 1 0 ) 1 旋转备用约束 为了维持系统的可靠性，还要提供充足的旋转备用( 即在一个时间段内，如果一 台机组停运的话，其他机组必须有足够的备用容量以弥补这一损失) 。 u 。p 。口+ r ， ( 扛1 ，2 ，7 1 ) ( 2 1 1 ) i = l 其中，冠为第t 时段的系统总备用，一般取为系统总负荷的百分数，本文取为1 0 p 。 2 机组出力约束 每台机组的出力都有一定的范围，即 匕 u h ， nm 第-