大规模机组组合问题计及网络约束的线性化求解方法.pdf

第 3 8卷 第 1 8 期 2 0 1 0 年 9月 l 6日 电 力 系统 保护 与控制 V 0 1 3 8 N O 1 8 ； e p t 1 6， 201 0 Powe r Sys t e m Pr o t e ct ion a nd Co nt r ol 大规模机组组合 问题计及网络约束的线性化求解方法 苏济归，舒 隽，谢国辉，张粒子 ( 华北电力大学电气与电子工程学院，北京 1 0 2 2 0 6 ) 摘要：为了提高求解机组组合问题计算效率，给出线性化方法， 将 目标函数分段线性化 ， 将启机费用作为约束并将其线性化， 同时将网络安全约束通过直流潮流模型进行线性化，从而建立较完备的混合整数线性规划的机组组合模型 采用世界上广为 流行的C P L E X优化求解器求解，在对偶间隙设定为较合理的情况下，求解速度快。不同测试算例表明，该方法速度快，精度 较高，能够求解较大规模的机组组合问题。 关键词：机组组合；线性化方法；混合整数线性规划； C P L E X Lin e a r iz a t io n me t h o d o f l a r g e s ca l e u n i t co mmit me n t p r o b l e m wit h n e t wo r k co n s t r a in t s S U J i g u i，S HU J u n，XI E Gu o h u i，ZHANG Li z i ( S ch o o l o f E l e ct r i c a n d E l e ct r o n ic E n g i n e e r i n g ，No r t h C h i n a E l e ct r i c P o we r U n i v e r s i t y ，B e r in g 1 0 2 2 0 6 ，C h i n a ) Ab s t r a ct ： T o i mp r o v e co mp u t a t i o n a l e ffi cie n cy o f u n R co mmi t me n t ( UC ) p r o b l e m， l i n e a r i z a t i o n me t h o d i s p u t f o r w a r d F i r s t o b j e ct f u n ct io n is l in e a r iz e d t h r o u g h p ie ce wis e - l in e ar me t h o d ， s t a r t u p co s t is t r e a t e d a s co n s t r a in t s wh ich are a l s o l in e a r iz e d ， an d n e t wo r k s e cu r i ty co n s t r a i n t s a r e l i n e a r i z e d thr o u g h d i r e ct cu r r e n t ( DC )fl o w mo d e l ， S O a co mp l e t e mi x e d i n t e g e r l i n e ar p r o g r a m mi n g u n it co mmit me n t m o d e l is b u il t Th e n the mo d e l is s o l v e d t h r o u g h a p o p u l ar CP L EX s o l v e r Dif f e r e n t e x am p l e s s h o w t h a t ca l cu l a t io n is v e r y f a s t wh e n t h e d u a l g a p is r e a s o n a b l e ， a n d t h e a b o v e me n t io n e d me t h o d ca n imp r o v e co mp u t a t io n a l e ffi cie n cy t o s o l v e l arg e s ca l e u n it co mm it me n t p r o b l e m Ke y wor ds ： un it commit me n t ； l in e a r iz a t ion me t h od： mix e d in t e g e r l ine ar pr o gr am ming； CPLEX 中图分类号： T M7 1 文献标识码 ：A 文章编号： 1 6 7 4 - 3 4 1 5 ( 2 0 1 0 ) 1 8 0 1 3 5 0 5 0 引言 电力系统机组组合 ( un it C o mmit me n t ，UC) 是要 在满足 系 统各种 约 束 的条件 下制 定 出合 理 的开停机 方案 ，实现总发 电费用最小 目标 。从数 学角度 而言，UC 问题是一个 NP h a r d问题 ， 目 前很难在合 理的时间 内找到最优解 。专家学者 已 提出求解 U C问题的若干算法，如优先次序法l 、改 进的动态规划法L 2 J 、拉格 朗日松弛法【 J 、进化算 法【 7 - 9 、内点半定规划法【 、混合整数线性规划 ( Mi x e d I n t e g e r L i n e a r P r o g r a mmi n g ， MI L P ) 法I l 2 - 。 其中优先次序法实现简单 ，计算速度快 ，但对于有 些约束难以处理，并且计算精度不高；动态规划法 难以处理时段间耦合的爬坡约束且易出现维数灾： 拉格朗 日松弛法是 目前研究较多的一种算法，这是 一 种解耦算法，通过不断修正 L a g r a n g r a n乘子来进 行协调 ，但是对于复杂多约束模型，在实际操作中 将很难协调乘子，无法有效抑制震荡；进化算法是 全局优化，但是求解时间过长，不利于工程实际应 用；内点半定规划法能处理离散变量 ，可 以在多项 式时间里收敛 ，但是在半正定矩阵的形成上 需要花 费较长时间，尤其是针对大规模机组组合问题，并 且如果是复杂多约束模型优化问题 ，优化结果中会 出现过多非整数解 的启停变量。 本文将传统机组组合模型线性化，建立较完备 的 MI L P模型，采用 C P L E X求解器求解该模型。 1 线性 化的机组组合模 型 1 1 目标函数的线性化 发 电 费 用 一 般 可 用 二 次 曲 线 表 征 ： f ( P i J = + h i p f + 。 将该二次费 用曲 线除去 常数项之后， 将该二次费用曲线f ( P ) = q p + p 分段 线性化 。 以分三 段为例 ，分段线性化后的费 用 曲线如图 1 。 - 1 3 6 电力 系统保护 与控瑚 r ( p ) ， $ Pf M W 图 1发电费用曲线的分段 线性 化 F ig 1 P ie e wis e l in e a r o f g e n e r a t io n co s t c u r v e 目标函数线性化模型为： N T L m i n F ( u i t ， P i t) - ( P ， + u i ， + )( 1 ) i= l t = - I ， 式中： ， 为机组 f 发电费用曲线分段线性化后第， 段斜率； ， 为机组 f 在第f 时段第 l f J 3 ；U 为 机组 f 在第 f 时段的启停状态；U = 1 、0分别表示 开机状态和停机状态；a i， b i， C 为机组 f 发电费用二 次函数的二次项、一次项、常数项系数； 、 、 分别为机组数、 时段数和线性分段的段数；S 表 示机组f 在第 f 时段的启机费用 。 1 2约束条件的线性化 ( 1 )分段 出力中每一段出力的约束 ， l , min r ， ， r ， ， a x ( 2) 式中， ， i 、 分别为机组出力分段后机组 f 的第 ， 段 出力的最小值和最大值 。 ( 2 )功率平衡约束 P 厂 。 = 0 ( 3 ) = 1 ， =l 式 中， 。 为第 时段 的系统总负荷 。 ( 3 )爬 坡约束 同时考虑两类爬坡约束 ：启停爬坡约束和连 续运行爬坡约束 。 一 ，f - l ， f _ l( 一 ) + ( 4 ) 1 - 1 l = 1 L 一 厶 ， ( 一 )+ ( 5 ) 1 = 1 1 = 1 式中： 印、 。 分别为机组 f 连续运行的升出力 速率和降出力速率；s 7、 一 分别为机组f 的 启 机升出力速率和停机降出力速率。 ( 4 )启机费用约束 考虑热启动和冷启动 ，约束判据分别为： f c ， 1 ， 。 行 。 行 + M f a ， t i ,t f f o ff + T c o 埘 式中：c 、c 分别为机组 的热启动费用和冷 启动费用： 、 分别为机组 f 的允许最小连 续停机时间和冷启动时I- 1 ；f o ff为机组 f 在第f 时段 之前 ( 不包括第f 时段 )的连续停机时间。 常规线性化机组组合模型之所以难 以考虑启动 费用 ，是因为启机费用是非线性 ，文献 1 3 】 将启机 费用与停机时间的函数曲线梯级分段，但模型中没 有考虑机组的初始启停状态 ，本文只考虑冷启和热 启，相当于梯级分段只分两段，且考虑机组的初始 启停状态 。 对于热启动费用约束，只需知道机组在前一时 段的启停状态；对于冷启动费用约束，需要知道机 组前 。 仃+ 洲 +1 时段的启停状态。具体的线性约 束如式 ( 6 )( 8 ) ： 厂 ，m I n 卜 1 ， 1 2 一 f 、 ， 一 一 l ( 6 ) m=1 m =1 f ， 叫 + 卜 l】 钉 、 ， 1 一 一 l 7 ) 稍 0 ( 8 ) 式中： 为前一个 日前发电计划中机组 f 从最后 一 个时段倒数 向前数第 m个时段的启停状态； 热启 动费用约束不等式 ( 6 ) 右边括号内的表达式含义为 机组 f 的 时段的启停状态与前一 时段的启停状态 之差 ( t = l时，前一时段指初始启停状态 。 ) ；冷 启动费用约束不等式 ( 7 ) 右边括号内的表达式含义 为 机 组 的 时 段 的 启 停 状 态 依 次 减 去 前 。 + + 1 时段的启停状态 ( f + 训 十 1 时， 还要减去机组 f 的初始启停状态 ) 。 ( 5 )启停时间约束 ( “ 一 。 一 ) ( 一 ) 0 ( 9 ) ，一 ,t -IX 一 蚰) 0 ( 1 0 ) 该约束参照 文献 1 0 】 中提 出的方法进 行线性 化 ： ( z ) + a ( t 一 1 ( 1 1 ) ( 1 一 ) 一 一 ( z ) + a ( t 一 1 ( 1 2 ) 苏济归，等 大规模机组组合问题计及网络约束的线性化求解方法 - 1 3 7 - 式 中 ： 口 ( z ) ： n t + z - l,T ， b ( z ) = n i n Z ， 一 f + 1) ， = Ui 。，U i ,1 r I 1a ) 【 0 ， 一 ， a ( t 一 1 ) 为 单 位 冲 激 函 数 ， b o = ( 1 - 4i ,1 ) ( 1 一 ) m a x 0 ， + 。 】 ； 、 r 。行 分别为机组 f 的允许最小连续开机时间和最小连续 停机时间， 。 为机组 的初始启停 时间， o 0 表 示初始状态 已经连续运行的时间， 。 0表示初始 状态 已经连续停运的时间。 ( 6 )备用约束 “ 。 ( 1 + R ) ( 1 3 ) 式 中： 为机组 f 最大出力； 。 为负荷备用率。 ( 7 )机组启停状态约束 = 1 o r 0 ( 1 4) ( 8 )直流潮流网络约束 一 ， Sj ,k ， 。 ， ( 1 5) j = l 式中：S 为第J节点注入功率对第k 条线路潮流 的灵敏度； 为第J节点的净注入功率； ， 为 第 k条线路的稳定极限。 2 算例分析 针对不同测试算例进行仿真分析 ，仿真计算在 P C机上进行，C P U 为 C e l e r o n 一 1 8 6 G Hz ，内存为 1 0 G B， 在 Ma t l a b 7 0环境下调用 C P L E X 1 6 1 求解器 进行求解。 2 1不考虑网络约束和启停爬坡约束 1 0机参数及各时段总负荷数据见文献 4 ， 参照 文 献 1 1 】 ，机 组1 、3、4 的运 行 爬 坡 速 率 为 印 ： = 4 0 MW h ，负荷备用率R 取 1 0 。收 敛曲线见图 2和图 3 ，图 2 、图 3的横坐标均为迭代 过程中依次出现的可行解序号，图 2 、图3的纵坐标 分别指各个可行解对应的目标函数和对偶间隙， 目标 函数最终收敛到 5 6 4 6 6 4 5 4 ，计算时间为 0 6 2 5 S 。 可行解 图 2目标函数收敛曲线 F ig 2 C o n v e r g e n t cu r v e o f o b j e ct f u n ct io n 0 1 8 0 1 6 n 1 4 篷 0 1 2 星0 - 靛 0 0 8 0 06 0 0 4 0 0 2 0 可行解 图 3对偶 间隙收敛 曲线 F ig 3 Co n v e r g e n t cu r v e o f d u a l g a p 1 0机 2 4时段机组组合结果如表 1 。 表 1机组组合结果 1 1a b 】 Re s u l t s o f I 7 C 机组编号 2 4 个时段机组启停状态 为 了验证系统规模增大 时的计算效率 ，以文 献 4 】 中的 1 0机参数为基础 ，扩展到 2 0 、4 0 、6 0 、 8 0 、1 0 0 、2 0 0 、4 0 0 台机组，各时段的系统总负荷 也按 比例 扩 展 。计算 终 止条 件 为对 偶 间隙达 到 0 5 ，总费用为将各机组各时段的出力代回到各机 组 的二次费用 曲线 计算 的结果 ，求得 的结果与文 献【 1 1 1 列出的结果 比较如表 2 。 表 2 不同算法优化结果 比较 T a b 2 Re s u l t s co mp a ri s o n o f d iffe r e n t a l g o r it h ms 注：表 2中，N a指文献中未进行仿真计算 1 ， O O O O O O O O l 1 O l O O O O O 0 1 1 l 1 O 0 1 O O O l l 1 l l 1 1 O O O 1 1 l 1 1 l l 1 O O l 1 1 l l l O O O O 1 l l 1 1 O O O O O l l l l l O O O O 0 1 l l 1 1 O 0 O O 0 l l 1 1 l O O O 0 0 1 1 1 l 1 l 1 O O O i i 1 l O 0 ；l ；i nu l l l 1 1 l 1 l O O 1 1 l l l 1 1 O O O l l l 1 l O 0 O 0 O l 1 l l l O O O O O l l l 1 l O 0 O O O 1 O O O O O O l l O O l O 0 O O O 1 1 0 O 1 O O O O 0 1 1 O O 0 O O O O 0 1 l 0 O O 0 0 0 O 0 O l 2 3 4 5 6 7 8 9 l 1 3 8 电力 系统保护与控捌 从表 2看出，相 比其他算法，本文基于 C P L E X 求解器的计算结果均优于表 2中列出的其他算法， 4 0 0机 2 4时段求解时间仅用 6 2 2 7 s ， 因此本文的方 法适合求解大规模机组组合问题 ，计算效率较高。 2 2考虑网络约束和启停爬坡约束 本文对 3 0 节点算例和 1 1 8 节点算例进行考虑网 络和启停爬坡约束的机组组合优化 ，3 0节点和 1 1 8 节点算例数据分别参照文献 1 7 】 和文献【 5 ，启停爬 坡率取机组的最小出力 。文献【 1 7 】 和文献【 5 考虑了 污染物排放 ，而本文没有考虑，故本文的计算结果 与文献【 1 7 】 和文献【 5 】 的计算结果没有可比性，结果 如 表 3 。 表 3不同算例的求解结果 T a b 3 Re s u l t s o f d i ffe r e n t e x a mp l e s 图 4为 1 1 8节点 5 4机 2 4时段算例考虑网络安 全约束时的对偶间隙收敛曲线。 可行解 图 4对偶 间隙收敛 曲线 F ig 4 Co n v e r g e n t cu r v e o f d u a l g a p 从图4可以看 出，迭代过程中收敛很快，找到 第 5 个可行解的时候对偶 间隙就已经达到0 3 7 了， 已经找到了较满意的解，但是在之后寻找更优解或 最优解的过程中，需要较多的迭代次数，如迭代终 止条件设定为对偶间隙 G a p达到 0 0 5 ，计算时间 为 2 8 9 3 6 s ， 总费用为 8 5 6 0 1 6 7 5$ ， 表 4列出了 l 1 8 节 点算 例考 虑 网络安 全和 启停 爬坡 约束 情况 下 G a p取一系列不同值对应的 目标函数和计算时间。 表 4不 同对偶 间隙的求解结果 Ta b4Res u l t sofd iffe r e ntd ua lga p 分析表 4可知， 对偶间隙设定为 0 5 0 和 0 , 0 1 的求解 时间相 差甚远 ，前者 为 3 2 3 9 s ，后 者为 6 9 8 1 3 S ，但是两者的 目标函数仅相差 8 1 8 4 9$ ，占 总费用的比例为 O 0 9 6 ， 为了同时兼顾求解时间和 求解精度，对偶间隙设定为 0 5 0 较为合理。 3 结论 本文给 出并设计有效地线性化方法，对传统机 组组合模型目标函数分段线性化，通过启停爬坡约 束的线性化 ，启动费用的线性化约束处理，以及基 于直流潮流模型的网络安全约束，建立了考虑多约 束的线性混合整数规划的机组组合模型 。在此基础 上，采用 C P L E X 求解器进行求解。不同测试算例 研究表明，本文的方法能够求解较大规模网络约束 机组组合问题 ，计算精度合理，速度快， 算法稳定。 本文不足之处是尚不能考虑交流潮流模型，未能计 及网损 ，这将作进一步深入研究。 参考文献 1 S e n j y u T ，S h ima b u k u r o K，Ue z a t o K，e t a 1 A f a s t t e ch n iq u e f o r u n i t co mmi t me n t p r o b l e m b y e x t e n d e d p r i o r i t y l is t J I E E E T r a n s a ct i o n s O i l P o w e r S y s t e ms ， 2 0 0 3 ， 1 8 ( 2) ：8 8 2 8 8 8 2 王成文，韩勇，谭忠富 ，等 一种 求解机组组合优化问 题的降维半解析动态规划方法 J 电工技术学报， 2 0 0 6 ，2 1 ( 5) ： l l 0 1 1 6 W ANG Ch e n g - we n ，HAN Yo n g ，T AN Z h o n g - f u，e t a 1 Di me n s i o n - -r e d u ce d s e mi analy t i ca l d y n am i c p r o g r a mmi n g a p p r o a ch for s o l v in g u n i t co mmi t me n t p r o b l e m J T r ans a ct i o n s o f C h i n a E l e ct r o t e ch n i cal S o ci e t y，2 0 0 6 ，2 1 ( 5)： 1 1 0 - 1 1 6 3 王承民，郭志忠，于尔铿 确定机组组合的一种改进 的动态规划方法 J 电网技术，2 0 0 1 ，2 5( 5 ) ：2 0 2 4 W ANG C h e n g