（电力系统及其自动化专业论文）基于改进拉格朗日松弛法的机组组合优化方法.pdf

声明尸明 本人郑重声明：此处所提交的硕士学位论文基于改进拉格朗同松弛法的机组组合 优化方法，是本人在华北电力大学攻读硕士学位期i 目，在导师指导下进行的研究工作 和取得的研究成果。据本人所知，除了文中特别加以标注和致谢之处外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得华北电力大学或其他教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文 中作了明确的说明并表示了谢意。 学位论文作者签名： 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权保管、 并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或其它复制手 段复制并保存学位论文：学校可允许学位论文被查阅或借阅；学校可以学术交流为 日的复制赠送和交换学位论文：同意学校可以用不同方式在不同媒体上发表、传播学 位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名：导师签名： 华北电力人学硕i j 学位论文 摘要 电力系统机组组合问题，一直是电力系统经济运行和优化调度中重要的研究课 题。拉格朗同松弛算法是求解机组组合问题应用最广泛最成功的方法之一，但由于 目标函数的非凸性，需要采取一定的措施进行可行化；算法迭代过程中容易出现振 荡现象；同时，考虑机组的爬坡约束，会使计算复杂化。 针对以上问题，论文提出了一种基于改进拉格朗日松弛法的机组组合优化方法。 采用自适应性次梯度法直接修正拉格朗同乘子从而获得可行解，可行解获得以后， 运用集结投影次梯度法，对历史信息加以利用，两种策略相互交替。6 个不同规模 算例表明，自适应性次梯度法与集结投影次梯度法的联合优化策略更易跳出单一策 略时的振荡现象，从而加快收敛。而对于考虑爬坡约束的机组组合问题，通过增加 与爬坡约束对应的拉格朗日乘子将爬坡约束直接松弛进行求解，并通过算例验证了 算法的可行性。 关键词：机组组合拉格朗日松弛法自适应性次梯度法集结投影次梯度法 a b s t r a c t u i l i tc o m m i t m e n ti sa ni m p o r t a n tr e s e a r c ht o p i co fe c o n o m i co p e r a t i o na n do p t i m a l d i s p a t c hi np o w e rs y s t e m l a g r a n g i a nr e l a x a t i o nm e t h o di sad e s i r a b l em e t h o dt os o l v et h e u n i tc o m m i t m e n t , b u tb 烈7 , a u s eo fi t sn o n - c o n v e x i t yo ft h eo b j e c t i v ef u n c t i o n , c e r t a i nm e a s u r e s a r er e q u i r e dt om a k et h ed u a ls o l u t i o nt ob eaf e a s i b l eo n eo fo r i g i n a lp r o b l e m i na d d i t i o n , t h ea l g o r i t h mi sp r o n et oo s c i l l a t eo na l li t e r a t i v ep r o c e s s f u r t h e r m o r e ，i fc o n s i d e r i n gt h e r a m pc o n s t r a i n t s t h ed i 伍c u l t yo fi t ss o l u t i o nw i l ls i g n i f i c a n t l yi n c r e a s e t oa d d r e s st h ea b o v ep r o b l e m s ，t h i sp a p e rp r o p o s e sa ni m p r o v e dl a g r a n g i 锄r e l a x a t i o n a p p r o a c hf o ru n i tc o m m i t m e n t a d a p t i v ea d j u s t m e n to fl a g r a n g i a nm u l t i p l i e ri sb r o u g h tt o m a k et h ei n f e a s i b l es o l u t i o nt oa p p r o a c haf e a s i b l eo n e a f t e rt h eg a i no ff e a s i b l es o l u t i o n , a g g r e g a t i v ep r o j e c t i o ns u b g r a d i e n tw i t ht h eu s a g eo fh i s t o r i c a li n f o r m a t i o ni sa p p l i e df o r u p d a t i n gt h em u l t i p l i e r s s i m u l a t i o ne x a m p l e ss h o wt h a tt h e s et w os t r a t e g i e su s e da l t e r n a t e l y c a na l l e v i a t et h eo s c i l l a t i o n t h ei m p r o v e dl a g r a n g i a nr e l a x a t i o na p p r o a c hc a l la l s ob eu s e d t os o l v et h er a m pc o n s t r a i n e dt m i tc o m m i t m e n t i ti ss o l v e db yad i r e c t l yr e l a x a t i o no ft h e r a m pc o n s t r a i n tv i aa d d i n gl a g r a n g em u l t i p l i e r sc o r r e s p o n d i n gt ot h er a m pc o n s t r a i n t s n u m e r i c a ls i m u l a t i o n sd e m o n s t r a t et h ef e a s i b i l i t yo ft h ep r o p o s e dm e t h o d h e x i a o y u ( e l e c t r i cp o w e re n g i n e e r i n g ) d i r e c t e db yp r o f l i z iz h a n g k e yw o r d s ：u n i tc o m m i t m e n t , l a g r a n g i a nr e l a x a t i o n , a d a p t i v es u b g r a d i e n t ， a g g r e g a t i v ep r o j e c t i o ns u b g r a d i e n t 华北i i 力大学硕i ：学位论文 目录 中文摘要 英文摘要 第一章绪论1 1 1 课题研究背景及意义1 1 2 我国电力系统发电调度方式发展概述2 1 2 1 传统经济调度2 1 2 2 计划电量发电调度3 1 2 3 节能发电调度4 1 2 4 电力市场环境下的发电调度5 1 3 机组组合问题算法研究现状5 1 3 1 优先次序法6 1 3 2 动态规划法6 1 3 3 混合整数规划法7 1 3 4 拉格朗日松弛法8 1 3 5 其它算法。9 1 3 6 总结1 0 1 4 论文主要研究思路l o 第二章拉格朗日松弛算法基本数学原理。1 2 2 1 拉格朗日松弛算法基本数学原理1 2 2 1 1 基于规划论的拉格朗日松弛法1 2 2 1 2 拉格朗日松弛理论1 3 2 1 3 对偶间隙。14 2 2 次梯度法原理l4 2 3 小结16 第三章机组组合问题的数学模型及求解原理一1 7 3 1 机组组合问题的数学模型1 7 3 2 拉格朗日松弛法求解传统机组组合问题的原理1 8 3 3 拉格朗日松弛法求解考虑爬坡约束机组组合问题的原理1 9 第四章改进的拉格朗日松弛法求解机组组合问题2 l 4 1 改进的拉格朗日松弛算法2 1 4 1 1 初始化2 1 4 1 2 动态规划求解单机问题2 2 4 1 3 自适应性次梯度法构造可行解2 3 4 1 4 集结投影次梯度法修正拉格朗f 1 乘子2 4 4 1 5 收敛准则2 6 4 1 6 改进拉格朗r 松弛法流程图2 6 4 2 算例分析2 7 4 3 j 、结31 第五章拉格朗日松弛法求解考虑爬坡约束的机组组合问题3 2 5 1 爬坡约束描述3 2 5 2 拉格朗日松弛法求解考虑爬坡约束机组组合问题3 4 5 2 1 单机动态规划3 4 5 2 2 拉格朗日乘子的修正3 4 5 2 3 算法流程图3 5 5 3 算例分析。3 6 5 4d 、结4 0 第六章结论与展望。4 l 6 1 总结4 1 6 2 展望4 1 参考文献4 3 致 射4 7 在学期间发表的学术论文和参加科研情况4 8 华北电力大学硕 ：学位论文 1 1 课题研究背景及意义 第一章绪论 现代大规模电力系统中，发电资源由众多类型的发电机组构成，不同类型的机组具 有不同的成本特性和运行、技术约束条件。随着人们生产、生活活动的规律性变化以及 气候等因素的影响，电力负荷呈现出周期性起伏波动的特性。在很多时刻，负荷的这种 变化幅度往往是很大的，如果仅靠改变机组出力大小，而不改变启停机组的数目，在已 开机机组的容量范围内往往会因调节范围过窄而难以满足负荷变化波动的要求。为了实 现电力供需平衡，最合理地利用发电资源，预先对发电机组的启停和出力进行调度安排 是非常必要的。这个问题可表述为，在一定的调度周期内( 通常是一天或一周) ，合理 安排机组的开、停机状态和开、停机时间，以满足系统负荷和备用要求以及机组运行的 技术条件约束，最小化系统的总运行费用，这就是电力系统的机组组合问题。 机组组合( u i l i tc o m m i t m e n t ) 即各机组在调度周期内各个时段上运行状态的优化。 机组的优化组合是日发电计划首先要解决的问题，由于各个不同时段的负荷是不断变化 的，各时段的机组组合状态也应各有不同，由于这些组合状态之间的转移存在机组启停 等附加费用以及机组最小启停时间等相应的技术条件约束，所以不能根据各单一时段的 负荷水平孤立的寻求最优组合，而应在整个调度周期各时段的整体决策中进行机组启停 优化组合。 机组组合的经济效益是很客观的，一般来说，机组组合的经济效益可以达到1 2 5 。 对于一个大型电力系统来说，即使优化0 5 的费用也会取得数百万元的收益因而合 理有效解决机组组合问题多年来一直是十分重视的研究课题之一【l 】。 在电力工业的起步阶段，电厂之间没有互联供电，各家电厂通过自己的网络向其周 围的电力用户供电，电厂运行管理人员关心的是自己的成本与盈利。随着交流输电技术、 变压器以及汽轮机技术等新技术的出现和发展，电力工业呈现出规模经济性。由于技术 进步，大量电力可以通过长距离输送，集中发电可以送到城市负荷中心。大容量的发电 机需要复杂的输电系统，合并的大电力公司变成垂直一体化，即单个公司拥有生产、输 送和分配电力的设施。为保证供电可靠性，互联电力系统得到充足的发展，最终形成高 度互联和集成的发电和输电系统结构，即为现代电力系统。发输配电一体的垄断式电力 工业逐步代替了无序市场竞争的分散供电模式。到上世纪6 0 年代，垄断式的大规模电 力系统在绝大多数工业国家得到了应用。系统在发电厂互联后有了统一调度的可能。如 华北电力人学硕上学位论文 何实现系统最优调度的挑战被摆在了电力工程师们的面前，由此出现了机组组合问题， 这是电力系统中最早的经济学问题。 随着经济的发展和企业的变革，电力系统规模日益迅猛发展，发电与用电地域和时 域的差异程度、系统负荷峰谷的悬殊和不确定性程度等日益增加，电力系统调度理论面 临挑战、完善和适应。庆幸的是，随着大规模优化理论的不断丰富和发展，各种成熟的 算法为电力系统运行调度理论提供了强有力的基石，如拉格朗日松弛、d a n t z i g - w o l f e 分解、b e n d e r s 分解等。各方面的研究也都取得了突破和发展，使其向大型电力系统工 程实际应用迈进了一大步。 尽管如此，随着电力工业体制改革进程的加快，电力系统运行调度又出现诸多新问 题，尤其是电力市场机制的引入、节能减排政策的出台以及特高压电网和分散电源的并 进，使电力系统运行调度理论远未达到预想的要求，因此新形势下电力系统运行调度及 其重要组成部分机组组合问题的研究具有非常重要的意义。 1 2 我国电力系统发电调度方式发展概述 机组组合问题是电力系统发电调度问题的重要组成部分，而随着社会的进步和电力 工业的发展，电力系统的发电调度方式一直都在不断的发展变化。不同时期、不同背景 下，人们对同一生产活动有着不同的优化目标和准则，其优化行为也就难于一致。 1 2 1 传统经济调度 传统经济调度经历了近百年的历史，为电力工业发电调度的发展留下了宝贵的经 验。在我国电力垂直一体化的管理体制时期，曾一直实行按照煤耗水平排序的传统经济 调度方式。此调度方式是根据动力系统调度管理规程编制动力系统和系统内各发电 厂日负荷调度曲线，使整个动力系统在最经济方式下运行，本着发电煤耗量小或发电成 本低的机组先运行，发电煤耗量大或发电成本高的机组后运行的原理。 传统经济调度通常是指基于基本负荷法和等耗量微增率法的调度方式。早在3 0 年 代以前，基本负荷法就被用来解决负荷分配问题。所谓的基本负荷法，即把机组按照某 运行点处运行效率的高低排列，首先将负荷加到效率高的机组上，依次类推。这种方法 简单易行，但是未得到理论证明，不能保证负荷分配方案最优。 到1 9 3 4 年，以数学极值理论为基础的等耗量微增率负荷分配方法被提出来，其基 本原理是：假定参与运行的机组的启停组合已给定，各台机组的煤耗及其微增率曲线连 续可微，即可对等微增率方程进行严格的数学推导【2 l ： 机组经济功率分配的目标是满足负荷平衡的条件下使系统总煤耗达到最小，即： 2 华北电力人学硕上学位论文 m i n f = m i n z ( 圪) i = i 豇p d = ( 1 2 ) i = 1 为了最小化目标函数，可由拉格朗r 乘数法构造辅助函数： f = f ，( e c , ) + a ( p d - 圪) ( 1 - 3 ) i * i i * l 其中，f 为系统总煤耗；f 为机组编号；以为机组总数；圪为机组f 的出力；z ( ) 为机组i 的耗量特性；p d 为系统总负荷。 为求得辅助函数的最小值，应满足的必要条件是：f 对所有的及旯求偏导等于 零，求得： i = 1 , 2 刀 ( 1 4 ) 其中岛= a f , ( 最，) 蛾为第i 台机组的标准煤耗微增率。 从而得n 6 , = 坟= 。= 吃，这就是著名的等耗量微增率准则。它表示，为使总耗量 最小，应按相等的耗量微增率在发电设备或发电厂之间分配负荷。 此时具体做法是：采用等耗量微增供电煤耗率法进行各发电厂间的有功负荷分配， 并进行“网损修正 ，当仅改变负荷分配无法满足负荷需求变化时，就需要通过改变机 组组合，满足系统负荷需求，使系统总煤耗最小。 1 2 2 计划电量发电调度 2 0 世纪7 0 年代，随着中国经济的迅猛发展，电力消费增速加快，电力供需缺口越 来越大，电煤以及其它因素对缺电的矛盾开始加剧，从前按煤耗水平调度的传统经济调 度方式渐渐难以适应。为了尽快解决缺电的问题，保证电力系统的安全稳定运行，国家 开始实行集资办电，鼓励大、中、小电站一齐建设。对各类发电企业平均分配发电量计 划指标逐渐成为电力调度的核心p 】 这种调度方式在安排电厂出力方面采用“平均分配 的方法，不考虑效率、环保等 因素，给各个火电厂分配基本相同的发电利用小时数。这种做法在我国电力紧缺、电网 薄弱的情况下起到了促进电源建设，缓解电力压力，增强网络强度的作用。 但是，随着我国装机容量的增长，电网结构的增强以及电力市场化改革的深入，传 统“三公 调度模式中“忽视效率 的弊端日益明显：每台发电机组每年发电利用小时 数都由调度指标决定，小火电机组没有达到预定的发电计划指标时，大机组即使还有潜 3 尼 n一，_o 名芝瑚 副 k ” 肘 华北哇三力火学硕i ：学位论文 力也不能多发。燃煤机组未完成计划发电量时，水电机组也可能弃水。而对于风能等可 再生能源也不能得到充分利用，不能实现资源的优化配置等。这种调度方式在一定程度 上演化成“为公平而公平”、简单平均的发电调度方式。一方面低效、高排放机组无 需技改降耗就能旱涝保收；另一方面使得高效、低排放机组经济压力过大，造成发 电企业投资建设节能、环保、经济型电厂的动力受到压制 4 1 。 1 2 3 节能发电调度 为提高电力工业能源利用效率，节约能源，减少环境污染，促进能源和电力结构调 整，确保电力系统安全、高效运行，实现电力工业的可持续发展，国务院办公厅于2 0 0 7 年8 月发布了国务院办公厅关于转发发展改革委等部门节能发电调度办法( 试行) 的 通知【5 1 。改革现行发电调度方式，开展节能发电调度，对于减少能源消耗和污染物排 放，推动国民经济又好又快发展，具有重要意义。同月，宣布贵州、河南、江苏、广东、 四川成为节能发电调度第一批试点地区。 电力系统节能发电调度是指在保障电力可靠供应的前提下，按照节能、经济的原则， 优先调度可再生发电资源，按机组能耗和污染物排放水平由低到高进行排序，依次调用 化石类发电资源，最大限度的减少能源、资源消耗和污染物排放。节能发电调度的基本 原则是以确保电力系统安全稳定运行和连续供电为前提，以节能、环保为目标，通过对 各类发电机组按能耗和污染物排放水平排序，以分省排序、区域内优化、区域间协调的 方式，实施优化调度，并与电力市场建设工作相结合，充分发挥电力市场的作用，努力 做到单位电能生产中能耗和污染物排放最少。 节能发电调度以机组发电排序的序位表为主要依据。各省( 区、市) 的排序表 由省级人民政府责成其发展改革委员会组织编制，并根据负荷预测和发电机组的实 际运行情况及时调整本省( 区、市) 的年、季、月发电机组组合的基础方案。各级 电力调度机构按照排序表和基础方案，并根据电力日负荷预测和发电机组的实际发 电能力、电网运行方式，综合考虑安全约束、机组启停损耗等因素，确定次日机组 发电组合的方案。 各类发电机组按以下顺序确定序位： ( 1 ) 无调节能力的风能、太阳能、海洋能、水能等可再生能源发电机组； ( 2 ) 有调节能力的水能、生物质能、地热能等可再生能源发电机组和满足环保 要求的垃圾发电机组； ( 3 ) 核能发电机组； ( 4 ) 按“以热定电 方式运行的燃煤热电联产机组，余热、余气、余压、煤矸 石、洗中煤、煤层气等资源综合利用发电机组； ( 5 ) 天然气、煤气化发电机组； 4 华北电力人学硕 ：学位论文 ( 6 ) 其他燃煤发电机组，包括未带热负荷的热电联产机组； ( 7 ) 燃油发电机组。 其中，同类型火力发电机组按照能耗水平由低到高排序，节能优先；能耗水平 相同时，按照污染物排放水平由低到高排序。 机组运行能耗水平近期暂依照设备制造厂商提供的机组能耗参数排序，逐步过 渡到按照实测数值排序，对因环保和节水设施运行引起的煤耗实测数值增加要做适 当调整。污染物排放水平以省级环保部门最新测定的数值为准。 节能发电调度改变了传统的发电调度方式，取消了按行政计划分配发电量指标的做 法，制定并实施新的调度规则，也就是以节能、环保为目标，合理调用电力系统内发、 供电设备能力，最大限度的降低能源消耗，减少污染物排放，保证电力系统的高效、清 洁运行。 1 2 4 电力市场环境下的发电调度 随着我国电力体制改革的不断深化，电力市场的发展将得到不断完善，由于竞争机 制的引入，电力工业的结构正在逐渐从一种自上而下的“父子型管理模式，发展到以 电价为核心的平等的“兄弟型”模式；调度运行部门在电力市场中居于核心位置，是发 电、输电、配电、用电各个环节以及电网运行指挥、电力市场交易和电能量结算的枢纽。 电力市场环境下的发电调度方式是指在电力行业的发、输、配、售电环节均分 离并形成竞争市场后所实施的调度方式，以市场竞价的结果为依据制定发电计划。 目前，西方发达国家已经实施了竞价上网的发电调度模式，通过有效的市场竞争手 段达到全网购电成本最低的目的。具体调度方法是，网内一定容量以上的机组参与 竞价交易，按其上网电价的报价高低来决定机组的上网电量，在满足系统各种约束 的条件下，制定机组组合计划及分配机组出力。 从电网调度运行部门的角度来看，电力市场环境下的发电调度与传统的调度方式下 发电计划制定的最大区别在于发电计划制定的目标不同，在过去的模式下，调度员根据 运行规程，以网络最稳定、安全和发电厂总发电费用最低为目标来制定发电计划；而电 力市场环境下，调度员的角色已经朝着交易管理员的方向转化，他的一切行为必须是公 平、公正、公开的，同时他的职责要求他制定出使整个电网运营效益甚至是全社会效益 最大的发电计划，虽然这个发电计划同样要满足各种约束，但它是以保证系统安全的条 件下使全网购电费用最小为目标【6 1 1 3 机组组合问题算法研究现状 机组组合问题的提出已经有几十年的历史，从数学角度来说，机组组合问题是一个 跨越多个运行时段的优化问题，需要考虑各时段间的耦合约束，在含有大量连续变量的 5 华北电力人学硕 ：学位论文 同时还含有大量离散的整数变量，使得机组组合问题呈现高维数、非凸的、离散的、非 线性混合整数规划问题，很难找出理论上的最优解。但由于其显著的经济效益，众多的 专家学者一直在积极研究，并提出了许多的解决方法【7 1 ，如优先次序法、动态规划法、 混合整数规划法、拉格朗同松弛法以及遗传算法、模拟退火算法等现代智能算法。 1 3 1 优先次序法 优先次序法是求解机组组合问题最早的一类优化方法，这类方法简单实用，速度很 快，但是没有严格的理论依据，依靠直观的判断或实际调度的经验寻找最优解，这种方 法的优化结果比较粗糙，只能得到近似的次优解。 优先次序法就是将待选机组按某种特定的经济性能指标进行排序，然后根据系统的 负荷需求和备用需求按机组的优先顺序依次投切机组，决策其启停状态。该方法简单实 用，提出时间较早，但是由于机组排序时不能考虑时间关联约束，所以对于时段间耦合 约束的处理只能是启发式的，缺少严格的理论依据。尽管如此，该方法还是得到了比较 广泛的应用，尤其是与其他方法相结合运用较多。文献【8 】采用启发式的方法来处理单 时段机组排序顺序及时段问的制约关系，增强了该方法的有效性。文献 9 则将传统的 用来排序的经济性能指标，如平均满负荷耗量成本( a v e r a g ef u l ll o a dc o s t ) 和机组投 运利用因子( c o m m i t m e n tu t i l i z a t i o nf a c t o r ) 联合起来，在优化过程中还结合了动态规 划，取得了较好的效果。后来又出现了退出组合算法，即根据机组逐一退出后系统总运 行成本的变化进行逆向组合。文献 1 0 1 l 】也是一种逆向组合算法。 1 3 2 动态规划法 动态规划法是最早用于求解机组组合的数学规划类方法，是一种解决多阶段决策问 题的系列递推算法。动态规划法用于求解机组组合问题的优点是，它是一种组合优化算 法，对目标函数的性态没有特殊要求，能得到全局最优解；结合其他方法减少状态数目 后，能得到比较实用的算法。缺点是，动态规划法求解机组组合问题时，时段中机组的 组合状态个数直接影响到该算法的计算规模和效率，假设有n 台机组，每时段的状态数 为2 一一1 ，如果进行一一穷举，计算量将十分庞大，在实际大规模电力系统中根本无法 实现，因此必须采取必要的简化措施，从而不可避免的可能丢失最优解；动态规划法要 求所求解的问题具有明显的阶段性，难于考虑与时间有关的约束条件，如机组的爬坡约 束等。 动态规划法在机组组合问题中得到了广泛的应用，被结合到经济调度软件包中，已 有许多运用成果。使用动态规划法考虑所有机组所有时段的全部组合时，会发生由于计 算量急剧增加而形成所谓“维数灾 的问题，为了降低搜索空间和维数，很多动态规划 法采用了和优先次序法结合使用的方法：如d p t c ( d y n a m i cp r o g r a m m i n gt r u n c a t e d 6 华北电力大学硕i j 学位论文 c o m b i n a t i o n ) 法、d p - s t c ( 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 lt r u n c a t e dc o m b i n a t i o n ) 法、 d p s c ( 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 ) 法等【1 2 1 3 1 4 1 。文献 1 5 n 将原优化 问题分解为规模较小的多个子优化问题，每个子问题用动态规划法进行求解，子问题间 的协调分别采用分层方法及连续逼近方法。随着优化问题的复杂程度的不断增加，动态 规划方法在机组组合问题中的应用也有了进一步的发展。文献 1 6 】考虑了系统的动稳极 限约束。文献 1 7 将系统的功率平衡约束、安全约束、发电费用约束等应用模糊理论进 行表达，采用模糊动态规划方法进行求解。文献 1 8 】将矢量化技术和并行处理技术用于 机组组合问题，采用的是经过改进后的动态规划法，计算速度比常规方法快的多。 l - 3 3 混合整数规划法 混合整数规划法用于求解既有离散变量又有连续变量的优化问题，常用的求解方法 有分支定界法、b e n d e r s 分解法等。混合整数规划法在物理模型上很适合求解机组组合 问题，从理论上讲，能找到全局最优解。且混合整数规划法与发展成熟的线性规划法结 合产生的线性混合整数规划法在求解多约束的电力系统机组组合问题上有其自身的优 势，目前也是国际上用于求解机组组合问题的热点算法之一。但其算法本身比较复杂， 对于分支定界法，需要精心构造分支策略和获取下界的算法，另外对于机组数目较多的 实际电力系统，应用分支定界方法不仅计算量庞大，而且往往需要对问题进行一定的简 化和分解。而对于b e n d e r s 分解法，构造恰当、实用的b e n d e r s 割存在一定的难度，b e n d e r s 分解法对于目标函数的性态也有一些要求。 文献 1 9 】提出将经济调度问题分为纯整数型的机组组合和连续型的负荷功率分配 两部分，考虑了多种约束条件，证明了采用此模型时算法的有效性。文献 2 0 】提出一种 基于对偶理论和拉格朗日松弛法的混合整数规划法，指出该方法非常适合应用在大型电 力系统中。文献【2 1 】 2 2 】应用线性混合整数规划法求解了包括一般机组和抽水蓄能机组 的短期水电机组组合问题的数学模型，可以处理包括机组启停机时间约束等多种离散变 量约束。 目前正在兴起的一种混合整数规划方法是基于i l o g 公司的商业软件c p l e x 的 m i p 法，这种方法是在分支定界的基础上混合了启发式方法、分支点的预处理以及割平 面等多种技术，随着c p l e x 的不断升级，性能提升迅速。2 0 0 3 年，g u a n 等的研究表 明，对于大规模机组组合问题，拉格朗日松弛法仍然具有效率优势，只是优化结果稍逊， 在求解水电机组子问题时结合m i p 法会取得更好的效果脚】。文献【2 4 】认为m i p 法与拉 格朗日松弛法相比的优点是可得到全局最优解，结果的最优性可直接测量以及更加方便 和准确的建模能力，同时他们也指出，m m 法的计算效率依赖于对问题的模型描述，特 别是对约束条件的处理，对于大规模机组组合问题，计算时间和内存量m 口法是无法 与l r 法比拟的，也许对机组组合模型进行有针对性的重构以及采用并行计算处理，该 7 华北电力人学硕1 ：学位论文 法会有所突破。文献 2 5 中，s t r e i f f e r t 等采用c p l e x9 0 开发了应用于p j m 电力市场的 考虑网络安全约束的电能和备用同时竞价的机组组合算法，在对模型中的最小开停机时 间、爬坡速率等约束进行处理后，虽然未采用并行计算，算法仍取得了满意的结果。 1 3 4 拉格朗日松弛法 拉格朗日松弛法属于一类对偶优化方法，该方法的应用研究始于7 0 年代，9 0 年代 后成为主流，被认为是机组组合问题研究中应用最广泛最成功的方法。 1 9 7 7 年，m u c k s t a d tj a 最早将拉格朗日对偶分解原理运用于机组组合问题的求解 1 2 6 1 。但其算法本质上是分支定界法，拉格朗同函数只是用来确定分支树上每个节点最 优值的下限。由m e r l i na s a n d r i np 在1 9 8 3 年提出的文1 2 7 的方成为第一种真正适用 于大规模机组组合问题并被广泛认可的拉格朗同松弛算法，它完全抛弃了分支定界的框 架，直接求解对偶问题，并结合一些启发式的调整策略得到原问题的最优解或次优解。 这种方法建立在如下思想下：一个困难的混合整数规划问题可以看成由一些边界约束条 件联系在一起的一系列相对容易的子问题组成，利用这个特点，把边界约束条件被破坏 的量和它们各自的对偶变量的乘积加在目标函数上作为惩罚项，形成相对容易解决且可 以分解求解的拉格朗r 松弛问题。应用在机组组合问题中，就是与各可启停机组均相关 的系统约束，如系统功率平衡约束、系统备用约束可看作优化问题中的边界约束条件在 主问题中考虑，只与单一可启停机组相关的机组运行约束，如机组输出功率的上下限约 束，最小启停时间约束等在子问题中考虑。系统约束可以通过拉格朗日乘予加入到目标 函数中，形成原问题的对偶问题，将显式的硬约束变为在目标函数中隐含考虑的软约束。 这样，原优化问题可以分解为两层优化问题来求解：上层以拉格朗日乘子为决策量，最 大化对偶问题；下层在给定的拉格朗日乘子下，由一系列具有单机约束的优化子问题构 成。上层决策中，由于对偶问题的不可微性，一般采用次梯度的方法对拉格朗日乘子进 行修正，下层的子优化问题一般采用动态规划方法求解。上下两层交替求解，通过拉格 朗日乘子进行衔接和协调。应用拉格朗日松弛法进行求解时，上层对偶问题的最优值总 是小于或等于相应的原优化问题的最优值，两者之间的差别被称作对偶间隙，对偶间隙 的大小，直接反映了迭代求解过程中所获得的机组组合方案的优劣程度，因而可作为算 法是否结束的标准。 用拉格朗日松弛法求解机组组合问题时，拉格朗日乘子初值的选取、所采取的乘子 的修正策略以及不同约束条件所采取的处理手段，都会对算法的计算效率产生一定的影 响。文献【2 8 】认为，将系统功率平衡所对应的拉格朗日乘子的值作为乘子的迭代初值， 可加速算法的收敛性。文献【2 9 】采用次梯度法和连续逼近法修正拉格朗日乘子。文献 3 0 】 采用变量度量法代替次梯度法对拉格朗日乘子进行修正，加速了算法的收敛性。文献f 3 1 】 则提出一种自适应调整拉格朗日乘子的方法。文献【3 2 】在对偶问题迭代计算的每一步， 8 华北电力人学硕i ：学位论文 都做了大量的努力来寻找原问题的可行解，并通过计算表明，考虑机组爬坡速率将使计 算量大大增加。文献【3 3 】考虑的模型比较复杂，包括机组爬坡速率、线路传输容量限制、 网损、燃料限制等，机组爬坡速率在子问题中用对偶法考虑。文献 3 4 】采用增广拉格朗 日松弛法求解机组组合问题，使用增广拉格朗同松弛法克服了线性费用函数造成的振荡 问题，并加快了算法的收敛性。文献 3 5 】着重机组爬坡速率的处理，将机组爬坡速率约 束作为惩罚项加入目标函数中，经验表明这种处理方法对每次迭代的时间影响很小，在 实用中得到了比较好的结果。文献【3 6 】建立了一个通用的机组组合模型，可以包括最小 开停机时间约束、潮流约束、线路潮流限制、电压限制、旋转备用约束、爬坡速率、总 燃料约束等，并用拉格朗日松弛法和辅助问题原理来求解此模型，对一个小的算例系统 进行了计算分析。 综上所述，拉格朗日松弛法是一类有着成熟理论基础的组合优化算法，适合于解决 大系统优化问题，在电力系统机组组合问题中得到了广泛的应用。 1 3 5 其它算法 近年来，随着计算机和人工智能等技术的发展，各种智能优化方法不断出现，用于 机组组合研究的现代智能优化方法主要包括：遗传算法、模拟退火算法、t a b u 搜索法、 专家系统等。智能优化类算法从理论上是一种全局寻优的计算方法，方案比较灵活，可 以考虑多种约束：但通常计算量比较大，所需时间较长。 自二十世纪八十年代末起，各种智能优化算法已陆续用于机组组合问题的求解。文 献 3 7 】对各种智能优化算法在机组组合问题中的应用进行了综述。 弘， 其中遗传算法是目前广泛研究和应用的模拟自然界生物进化过程的组合优化算法。 文献【3 8 】将遗传算法应用于机组组合问题，为克服简单遗传算法过早收敛的缺陷，引入 变化性质函数技术，并对具体问题加入特殊的算子，计算结果表明，对于大系统，遗传 算法的优化效果要优于拉格朗日松弛法。文献 3 9 】用遗传算法解决机组组合和经济调度 问题，在机组组合问题中，用惩罚项的方法处理约束，问题在于交叉操作将导致新的不 满足约束的情况，而且要选择很多在数值上毫不相干的惩罚系数。文献【4 0 】结合使用遗 传算法和模拟退火算法，在寻找优化燃料计划时使用了模糊集理论，并用启发式的方法 来形成初始种群，计算表明混合算法比常规算法效果要好 随着计算机和人工智能技术的发展，各种新方法也不断出现。文献 4 1 把模拟退火 算法应用于1 0 0 台机组的大系统的机组组合问题，能产生很好的次优解，计算速度也快 于动态规划法，能考虑复杂约束，具有广泛的适用性。文献【4 2 】采用t a b u 搜索的方法 结合广义b e n d e r s 分解法，考虑了机组时变启动费用和水火电联合系统的非线性关系， 该方法可用于已有发电计划方法的后处理或系统运行工况改变后的重新计划。文献【4 3 】 9 华北i 乜力人学硕二l ：学位论文 采用专家系统，首先从数据库中选择与当前负荷变化趋势相似情况下的调度方案，再使 用优先顺序法寻找次优解，最后用专家系统驱动的数学规划法来改进这个方案。 1 3 6 总结 综上所述，机组组合问题复杂，求解方法众多。机组组合问题是一个高维数、非凸 的、离散的、非线性混合整数优化问题，要得到理论上的最优解几乎是不可能的，如何 在计算量和计算精度间得到恰当的协调妥协，是验证一个算法是否优秀的重要标准。 回顾过去几十年机组组合问题求解算法的发展历程，众多的优化方法都被应用于求 解此问题，优先次序法简单快速但优化效果较差；动态规划法灵活有效但难于处理具有 时间耦合性质的约束，且随着系统规模增大容易出现维数灾现象；混合整数规划法在物 理模型上很适合求解机组组合问题，目前也是国际上用于求解机组组合问题的热点算法 之一，但其算法本身比较复杂，需要精心构造分支策略和获取下界的算法；现代智能优 化类算法从理论上是一种全局寻优的计算方法，但通常计算量比较大，所需时间较长。 目前电力系统机组组合实用领域，主要有两类方法：拉格朗同松弛法和线性混合整 数规划法。如a r e v a 公司应用c p l e x 为美国p j m 电力市场、s i e m e n s 为c a i s o 提供的 混合整数规划法；a r e v a 公司应用拉格朗日松弛法为美国m i s o ，i s o - n e 电力市场提供 的机组组合算法，a b b 公司为n y i s o 、c a i s o 电力市场提供的拉格朗日松弛机组组 合算法。这些实用领域中所应用的算法策略是不公开的，难以复制，各种改进策略目前 在文献中也较少涉及，而当前我国应用的机组组合算法仍以优先次序法和动态规划法为 主。因此为了促进用于求解机组组合问题的拉格朗日松弛算法在国内的开发和实用化， 有必要对此算法进行更进一步的研究 1 4 论文主要研究思路 拉格朗日松弛法用于求解机组组合问题具有其特有的优点：算法的拉格朗日乘子具 有一定实际的物理( 经济) 意义，如与系统功率平衡相对应的乘子可以反映系统的边际 发电成本：算法比较灵活，可以推广到水火电联合经济调度和电力交易等方面；同时， 随着系统规模的增加，计算量近似线性增长，非常适用于机组组合这种大规模的混合整 数规划问题，得到了广泛的应用。因此论文选取拉格朗日松弛法作为机组组合问题的求 解算法。 但是，拉格朗日松弛法算法用于求解机组组合问题时，由于费用曲线的常数项和启 动费用的存在，机组组合问题的目标函数不是连续可微的，采用对偶问题求解时，存在 对偶间隙，需要采取一定的措施进行可行化；拉格朗日松弛法求解机组组合问题时，拉 格朗日乘子初值的选取、所采用的乘子的修正策略，都会对算法的计算效率产生一定的 影响；而算法的迭代过程中容易出现振荡现象，需要采取措施加快收敛，这也是对拉格 1 0 朗同松弛算法进行改进的一个重点；同时，对于考虑机组的爬坡速率约束的机组组合问 题，爬坡约束属于单个机组的运行约束，但是拉格朗日松弛法采用动态规划求解单机问 题时，动态规划法要求所求解的问题具有明显的阶段性，难于考虑这种时段耦合的约束 条件，从而会使计算复杂化。 针对上述问题，论文提出一种改进的拉格朗日松弛法。采用自适应性次梯度法结合 集结投影次梯度法的联合优化策略加快算法收敛速度。在构造可行解时，直接采用自适 应性次梯度法将对偶问题的解沿优化方向逐步修正为可行解；获得可行解后，为了缓解 乘子迭代过程中的振荡现象，采用集结投影次梯度法，对历史信息加以利用，从而加快 收敛速度。而对于考虑爬坡约束的机组组合问题，直接采用拉格朗日乘子将爬坡约束松 弛，自适应性次梯度法修正拉格朗同乘子，最后通过考虑爬坡约束的二次规划法进行经 济功率分配。 论文主要内容如下： 第一章回顾了机组组合问题的发展历程，分析机组组合问题产生以来的各种优化求 解算法及其优缺点，并叙述了论文的主要研究思路。 第二章介绍拉格朗日松弛算法的基本数学原理。 第三章提出所要求解的机组组合问题的数学模型，并分析了本文运用拉格朗日松弛 算法求解传统机组组合问题和考虑爬坡约束的机组组合问题的求解原理。 第四章针对拉格朗日松弛算法求解机组组合问题时的特点，综合应用启发式排序 法、动态规划法和联合次梯度法，提出一种改进的拉格朗日松弛算法，基于启发式排序 法得到较优的拉格朗日乘子初值，采用自适应性次梯度法结合集结投影次梯度法的联合 优化策略加快算法收敛速度。l o 机、2 0 机、4 0 机、6 0 机、8 0 机和1