（电力系统及其自动化专业论文）基于动态规划法的日发电计划及不同报价曲线研究.pdf

华北电力大学硕士学位论文 中文摘要 交易计划的制定和执行是电力市场运作的核心。在全面了解日发电计划优化理 论研究的基础上，论文从对动态规划法的改进及不同报价曲线意义的讨论展开研 究。具体如下： ( 1 ) 在分析按时段或按全天平均报价排队确定机组优先上网次序的不足的基础 上，采用综合报价排队的办法来减少状态数，算例表明能提高解的质量。 ( 2 ) 分析了局部加密法的不足，给出了在逐步加密的过程中选取负荷寻优范围 和步长的办法。在程序实现时，以报价功率段最小值与满足一定计算速度的最小步 长二者的最大值作为计算步长。 ( 3 ) 通过理论分析和算例说明，市场采用下降型及以v 型为代表的波动起伏型 报价曲线时，不能同时做到既对市场成员公平合理，又实现电网购电费用最小的目 标。 关键词：电力市场，动态规划法，f t 发电计划，报价曲线 a b s i r a c i t h ed e v e l o p m e n ta n de x e c u t i o no fg e n e r a t i o ns c h e d u l i n gi st h ek e yi ne l e c t r i c i t ym a r k e t a f t e rc o m p r e h e n s i v eu n d e r s t a n d i n go ft h eo p t i m a lt h e o r yo fd a i l yg e n e r a t i o ns c h e d u l i n g n l i s p a p e rc a r r i e so u tt h er e s e a r c hb a s e do nt h ei m p r o v e m e n to fd y n a m i cp r o g r a m m i n ga n dt h e p r a c t i c a lm e a n i n go f d i f f e r e n tb i dc u r v e 1 1 1 ed e t a i l sa r ea sf o l l o w s ： ( 1 ) a f t e rf i n i s h i n ga n a l y z i n gt h ed i s a d v a n t a g e so f a v e r a g e - b i d p r i c ei nt h ef o r mo f p e r i o d o ft i m eo rt h ew h o l ed a yt os o l v eu n i tc o m m i t m e n tp r o b l e m ，t h ep a p e rr a i s e st h em e t h o do f s y n t h e s i s b i d - p r i c et or e d u c et h es t a t eo f u n i t i th a sb e e np r o v e dt h r o u g ht h es i m u l m i o n ( 2 ) t h i sp a p e ra n a l y z e st h ep r o b l e mo fl o c a ir e f i n e dd y n a m i cp r o g r a m m i n g ，a n dg i v e so u t t h er a n g eo fl o a d o p t i m i z i n ga n dt h em e t h o dt oc h o o s ep a c e i ft h em i n i m u mp o w e rs e c ti s l a r g e rt h a nt h es t e p 一一l e n g t hi nc e r t a i ns p e e d ，t h e nt h el a s ts t e p l e n g t hi st h ef o r m e r i nt h e o p p o s i t e ，t h el a s ts t e p l e n g t hi st h el a t t e r ( 3 ) c a l c u l a t i o na n da c a d e m i ca n a l y s i si n d i c a t et h a t ，i tc a nn o tb ei m p a r t i a l ，a n dc a nn o t r e a l i z et h ed e s t i n a t i o no fm i n i m i z i n gt h ec o s tf o rp o w e ra tt h es a m et i m e ，w h e ne l e c t r i cp o w e r c o m p a n i e st a k ed e c r e a s e - m o d e l b i dc u r v ea n dv - m o d e lb i dc u r v ew h i c hb e l o n g st o f l u c t u a n t m o d e lb i dc u r v e b a i c h a n g b o f p o w e rs y s t e m i t sa u t o m a t i o n ) d i r e c t e db yp r o f z h a n g l i z i k e yw o r d s ：e l e c t r i c i t ym a r k e t ，d y n a m i cp r o g r a m m i n gm e t h o d ，d a i l yg e n e r a t i o n s c h e d u l i n g ，b i dc u r v e 声明 本人郑重声明：此处所提交的硕士学位论文基于动态规划法的日发电计划及 不同报价曲线研究，是本人在华北电力大学攻读硕士学位期间，在导师指导下进 行的研究工作和取得的研究成果。据本人所知，除了文中特别加以标注和致谢之处 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得华北电力 大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究 所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 学位论文作者签名：妄 必盘日 期： 巡：! ：? 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权 保管、并向有关部门送交学位论文的原件与复印件：学校可以采用影印、缩印或 其它复制手段复制并保存学位论文：学校可允许学位论文被查阅或借阅；学校 可以学术交流为目的，复制赠送和交换学位论文；同意学校可以用不同方式在不同 媒体上发表、传播学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名：k 丛必盘 日期：凼：! r ? 导师签名： 日期： 华北电力大学硕十学位论文 1 1 研究的目的和意义 第一章绪论 1 1 1 市场化是电力工业发展的方向 电力作为国民经济的基础行业，其运行效益和它的价格直接决定了一个国家的 产品在全球经济中的竞争能力。传统的电力工业在经济学上被归为自然垄断性行 业，在垄断模式下运行了一个相当长的时期。而随着现代控制、网络与信息技术的 进步和发展，电力工业内部具有建立一定的自由竞争空间的基础。科学技术的发展 为在电力工业中引入市场竞争机制提供了可能。从1 9 9 0 年英国开始电力市场改革 至今的十多年中，全球各国电力工业纷纷走上了电力市场改革之路。 建立电力市场的目的，就是要将电力工业纳入市场经济的大框架中，通过市场 竞争的方式来调整社会资源的分配，即而实现全社会资源优化配置。传统电力系统 主要可以分为输、发、配、售四个环节，他们之间的关系是相互依存，统一管理， 正是由于他的这一结构，造成了生产力发展缓慢的局面。进行市场化改革，就需要 市场具有相对独立的市场成员，这就迫使改革必须打破原有的产业结构，实现输、 发、配、售的独立经营，切断发电、输电和供电之间的资本纽带，使各电厂、电网 公司和供电公司成为独立经营的市场成员。在这一模式下，各市场成员为了参与市 场竞争，必须不断提高生产效益和生产力，从而实现了各类资源的优化，提高了整 个系统的运行效率，促进了系统的发展，这是进行市场化改革的主要目的。 从世界范围来看，英国、美国、澳大利亚、智利、阿根廷等国的电力市场给电 力工业带来的活力及其效益是有目共睹的。其运行经验表明：电力市场对降低电力 的生产与传输的成本，提高电力工业运行效率产生了重要的影响。降低电价，改善 服务已成为引入电力市场新机制是否成功的重要标志。 我国”3 1 的电力工业改革起步较晚，而且存在诸多问题。例如电网结构不合理， 电源建设缺乏规划性且分布不合理，传统模式根深蒂固，市场经济概念仍处于发展 阶段，这些都阻碍着我国电力市场改革的发展，但是为了实现提高效率，降低成本， 优化资源配置，促进电力发展的目标，市场化改革就刻不容缓。我国的电力市场化 改革于上世纪9 0 年代术有序的开展起来。首先实现了电力资产的重组，至2 0 0 2 年 底为止，国家电网公司己重组为两家电网公司和5 家发电公司，与此同时，山东、 上海、浙江、辽宁、吉林和黑龙江电网也被确定成为了首批电力市场试点单位，2 0 0 1 年山东一e 海、浙江的发电侧电力市场相继投入商业化试运营，同年6 月，东北三 省的发电市场也正式启动，这标志着我国电力市场化改革已经进入到实质性阶段。 华北电力犬学硕士学位论文 目前我国正积极建立竞争、开放、有序的区域电力市场，跨省电网已经形成，区域 电网之间的联系正逐渐加强。 1 1 2 日前交易计划优化理论研究意义 交易计划的制定和执行是电力市场运作的核心内容，而日前交易又是电能量交 易的重要环节，也是电能量交易的主要形式，制定公平、合理的目前交易计划直接 关系到电力市场能否健康、顺利、稳定地运行和发展。 市场环境下的日前交易计划和传统的闩调度计划相比，有以下几点重要区别： ( 1 ) 目标函数不同。传统的经济调度以整个系统总的运行费用最低为目标。 而市场模式下，电网公司依据各发电公司的报价制定发电计划，以全网总购电成本 最小为目标。由此可见，在电力市场下，用于电网经济调度的目标函数发生了变化。 ( 2 ) 经济性质不同。 传统的调度计划是作为企业内部的生产计划命令，调度 中心的调度员可以根据系统的需要对可操作的各机组或电力设备进行修改，或指定 调峰、调频、调压调度；而电力市场中，交易计划的实质是买卖双方的经济合同， 对系统所需要的调度调整，需向其他市场成员支付相应的费用，弥补其损失。 ( 3 ) 约束条件不同。传统调度模型中要细致考虑线路的传输容量、传输断面 的输送功率、节点电压等安全约束。在电力市场下，发电商在追求利益最大化时不 会自发的考虑系统的安全约束问题，电网的安全约束需要在制定发电计划时进行详 细考虑并强制执行。同时，由于交易模式确定的电量合同、双边合同等多种贸易形 式，也成为新的约束条件。 ( 4 ) 采用的算法不同。在传统的经济调度模式下，各发电机组申报的煤耗曲 线和机组启动费在一定时期是基本固定的，按照发电成本大小的机组排序在各时段 也是大致相同的，各类数学规划方法、优化算法和启发式算法得到了广泛的应用。 而在电力市场中，由于市场规则的造成的各类不确定性，例如机组报价的不确定性， 竞价电量的不确定性等，会在调度过程中造成阻塞、容量分摊、机组频繁启停等问 题。综上所述，市场环境下，交易算法要处理的约束条件比传统模式下的多，处理 约束的方法也发生了变化，采用的调整方式复杂多变。 从上述分析可见，在市场模式下，传统模式的发电计划已经不能适用。因此， 进行市场模式下的交易计划优化理论研究是十分必要的，开发出电力市场下的交易 计划优化软件，尤其是日前交易计划优化软件具有重要的现实意义。 1 2 ，本文的主要工作 本文主要进行了以下几项工作： ( 1 ) 查阅国内外相关文献，全面了解电力市场下日前发电计划编制的相关优化 2 华北电力大学硕十学位论文 理论研究的进展情况。从目标函数，约束条件，交易算法等方面深入研究和分析电 力市场下日前发电计划编制所出现的新特点。 ( 2 ) 采用动态规划法求解f 1 发电计划 a 针对基于各时段机组平均报价或机组全天平均报价排队确定各机组优先 级，以便得到各时段临界机组。本文在分析这两种排队办法不足的基础上，提出了 采用综合报价排队的办法。即以机组在各时段的中标价格之和的平均值来排队确定 机组的优先次序，该办法能有效避免前者的不足之处，且从市场的角度出发，显得 更有说服力。 b 分析了局部加密法的不足，给出了在局部加密的过程中选取负荷寻优范围 和步长的办法。在程序实现时，以机组报价功率段最小值与满足一定计算速度的最 小步长二者的最大值作为计算步长。 c 采用d e l p h i 编程语言编制了具有一定实用价值的日前发电计划制定软件。 ( 3 ) 理论上讲，发电公司可以报任何类型的报价曲线。但并不是每种类型的报 价曲线都有意义。本文从理论上分析了，在处理下降型及以v 型为代表的波动起伏 型报价曲线时，不能同时做到既对市场成员公平合理，又实现电网最小购电费用的 目标。通过算例说明下降型及以v 型为代表的波动起伏型报价曲线在电力市场中是 没有意义的。 华北电力人学硕士学位论文 21 引言 第二章国内外的研究现状 电力市场下的日前发电计划，是指在电力市场下，充分考虑负荷平衡，系统安 全备用，机组技术特性和交易规则的约束，制定下个交易日各个时段( 一般划分4 8 或9 6 个时段) 的电量交易计划，并以全网的购电费用最小为目标。也就是预先制 定下个交易日各个时段由哪些机组发电，发多少电的问题。 发电计划包括机组组合和经济功率分配两部分。电力系统的负荷在一天之内是 不断变化的，负荷的这种变化如果仅靠改变机组出力而不改变机组的组合数目，其 机组出力的调节范围往往难以满足要求。根据相应的负荷曲线，在满足负荷需求和 一定的约束条件下，在计算周期内确定机组的开、停机计划使计算周期内的总费用 为最小，这就是机组最优组合。合理的机组组合计划能节省一次能源，延长机组使 用寿命，带来可观的经济效益，同时它也是包括经济功率分配在内的其他经济性优 化的基础。在市场条件下，机组间的经济功率分配所得机组的出力基于机组的报价。 从市场的角度以及电力系统本身的特点，来衡量发电计划制定的好坏，就是要 兼顾经济性与安全性。同时有效减少实时调度对原发电计划的修正，也非常重要。 发电计划制定的过程，要尽可能简单，快速，精确。考虑的约束尽可能全面，合理。 结果尽可能接近最优解。 目前国内外的相关研究主要从两个方面展开： ( 1 ) 数学模型。在不同的电力市场模式及交易种类下，建立的发电计划数学 模型会有所不同。 ( 2 ) 优化算法。目前应用于发电计划编制的算法主要有优先排序法、线性规 划法、网络流法、拉格朗日松弛法、动态规划法等方法。在这些优化算法中，计算 速度快，能更好的处理约束条件，优化效果明显的算法得到了更为广泛的应用。但 任何一种算法都有它的局限性，因此为使问题得到很好的解决，优化算法的研究出 现两个重要的特点：算法改进和不同算法的组合使用。 2 2b 前发电计划数学模型 机组组合问题是一个高维数、非凸的、离散的、多约束的、非线性的优化问题。 2 2 1 目标函数( 计及机组的启动费用) r a i n f ( u 。只) = u 。f ( 异) + u ，( 1 一u v 1 ) s ，】 ( 2 1 ) 1 1 1f = 1 4 华北屯力大学硕士学位论文 式中：f _ 一机组号，f - 1 , 2 ，为机组总数； r 一一时段号，r = 1 , 2 ，r ，r 为时段数； u ，一一机组i 在，时段的运行状态，u 。= 1 运行，u 。= 0 停机； p ，一一机组j 在f 时段的有功出力； s 一一机组i 的启动费。 f ( p ，) 一一电网在r 时段付给机组i 的购电费； 关于f ( 只) 的进一步说明； 在日前市场中一般采用s m p ( s y s t e mm a r g i n a lp r i c e ) 结算方式 r m i n 瓦。( 只) = c 。，b ( 2 2 ) t = l ，= 1 c ，= m a x 0 ( 只) 】 ( 2 3 ) 符号说明： s m p 系统统一边际电价； 。一一f 时段系统统一边际电价； c ，时段机组，的报价。 2 2 2 约束条件 ( 1 ) 有功功率平衡约束 只一珞一已= o ( 2 4 ) 式中：如f 时段电网负荷功率： p 一一f 对段电网网损。 ( 2 ) 机组最大最小出力约束 只m 。兰鼻，只。( 2 - - 5 ) 式中：只，只一一机组i 的最大、最小出力限值a ( 3 ) 机组升降功率速度约束 异一只，。s 峨，一只蔓峨， ( 2 - - 6 ) 式中：只，。机组f 的上升功率速度限值； a p d ，一一机组i 的下降功率速度限值。 ( 4 ) 机组的启停约束 t o n ，t o n ，i o f f ， ， ( 2 - - 7 ) 式中：。，机组i 的最短连续运行和连续停运时间限值。 ( 5 ) 系统旋转备用约束 r a i n u , , ( p j 一b ，醌，) 】 b e o ( 2 8 ) i = l m i n u ，( 只一只m ，a p d ，) 】b 驯v ( 2 - - 9 ) 式中：b r o , u i ，。，。分别为电网f 时段的t 旋转备用和下旋转备用限值 ( 6 ) 负荷备用约束 华北电力大学硕十学位论文 ? ( u 。只一一尸j 。) b 。，。 f _ l ， ( 一u 。瓦。) 。 j = i ( 2 1 0 ) ( 2 一1 1 ) 式中：，b 。一一分别为电网负荷上备用和下备用限值。 ( 7 ) 计划运行、停运约束，该约束由检修、供热及机组申报连续运行等情况引起 计划运行：= l ( 2 1 2 ) 计划停运：u。=0(2-13) 2 3 日前发电计划算法综述 2 3 1 启发式方法 7 1 启发式方法( h e u r i s t i cm e t h o d ) 是最早使用的一类优化方法，这种方法没有严 格的理论依据。依靠直观的判断或实际调度的经验寻找最优解。启发式方法在机组 组合问题中的应用有以下两种情况： a 局部寻优法。 其基本的思路是从一个尽可能好的初始解出发，在其邻域内寻优，通过迭代求 得最优解或次优解。这种方法计算速度快，所需内存少，但往往找不到最优解。但 局部寻优法可与专家系统方法结合使用。 b 优先顺序法( p r i o r i t yl i s t ) 。 ( 1 ) 逆序排序法( u n i td e c o m m it m e n t ) 在这种方法中，首先把所有可以参与运行的机组设置成全时段开机在这种情 况下，系统将有过多的旋转备用，从而导致额外的运行费用。为了得到一个经济的 运行方案，把一台经济性最差的机组变成停运状态，从而可以节省出一部分运行费 用，同时减少了多余的旋转备用。继续选择下一台经济性较差的机组安排停机。这 个过程进行直到整个系统的总运行费用不再下降，并且满足系统负荷和旋转备用的 要求为止。这种方法的一个显著特点是系统总费用随着迭代过程的进行单调减少， 并且总是保证旋转备用满足要求。 ( 2 ) 顺序组合法( s e q u e n t i a lu n i tc o m m i t m e n t ) 这种方法也就是我们通常采用的排队法，文献“1 中提到将系统可调度的机组按 某种经济特性指标事先排出顺序，根据系统负荷大小按这种顺序依次投切机组。文 献“1 将其用于经济功率分配的求解，求解过程分排序选择，越限校正。排序选择可 解决竞价，负荷平衡和边际电价确定，越限校正主要是校j 下每个时段约束是否满足。 文献”1 将其用于机组组合和经济功率分配求解，表明排队法只能用于单段或多段水 平报价曲线，且不能有下降段，另外它难以处理跟时间有关的约束，如机组的爬坡 华北电力大学硕士学位论文 速度约束和启停时间约束。 总之，优先顺序法简单，计算速度快，占用内存少，常常找不到最优解，但能 满足一般的应用要求，这种方法既可单独使用，也可与动态规划法等方法结合使用。 优先顺序法提出较早，现在仍在研究和应用之中。 2 3 2 线性规划法”“ 线性规划法是目前较为实用的算法，主要优点是：快速、可靠；能有效地处理 网络安全约束：可以直接解决与时间有关的约束；同时还可以处理下降型的报价曲 线；其缺点是：处理网损比较麻烦；对于非线性的目标函数和约束，必须使用逐次 线性化的手段才能求解，确定步长的大小是一个困难的问题，而且逐次线性化也会 造成计算精度的损失。 2 3 3 混合整数规划法“1 混合整数规划( m i x e d i n t e g e rp r o g r a m m i n g ) 是变量中既有整数又有非整数的 数学规划问题，根据除整数变量以外的其它变量的函数类型，又可分为线性混合整 数规划和非线性混合整数规划。这种规划问题解决起来十分困难，常用的方法有分 支定界( b r a n c h a n d b o u n d ) 法、b e n d e r s 分解( b e n d e r sd e c o m p o s i t i o n ) 法、广义 b e n d e r s 分解( g e n e r a l i z e db e n d e r sd e c o m p o s it i o n ) 法等 混合整数规划法的优点是： a 直接求解机组组合问题的数学模型，不需要加入过多的限制或假设： b 从理论上来说，能找到全局最优解。 其缺点是： a 方法比较复杂，不直观，对于分支定界法，为得到比较高的效率，需要精心 构思分支策略和求下界的算法，b e n d e r s 分解法和广义b e n d e r s 分解法使用也较复 杂： b 对于实际系统，直接使用计算量太大，必须对问题进行分解： c b e n d e r s 分解法或广义b e n d e r s 分解法对目标函数的性态有一些要求。 混合整数规划法在机组组合问题中实用化的成果不太多，但有一些理论成果有 价值，后来应用十分广泛的拉格朗日松弛法最早也是以分支定界法的形式出现的。 2 3 4 拉格朗日松弛法“”7 3 拉格朗日松弛法的基本思想是把全系统的约束，如负荷约束、旋转备用约束等， 写成目标函数的惩罚项的形式，即进行松弛。约束条件松弛后的对偶问题可分解为 单机组的子问题。求解子问题的过程和整体协调( 即优化拉格朗日乘子) 的过程交替 迭代进行，直到找出最优或次优的对偶问题解，再从对偶解形成原问题的最终解。 拉格朗同松弛法优点： 华北电力大学硕士学位论文 a 随着机组数的增加，计算量近似线性增长，克服了维数障碍，且机组数目 越多，算法效果越好： b 方法十分灵活，不但可以成功地解决机组组合问题，也可以推广到水火电 联合经济调度问题和电力交易的问题： c 算法的一些因子具有实际的物理( 经济) 意义，如与系统负荷约束相关的拉 格朗同乘子即等于系统边际发电成本。 拉格朗日松弛法缺点： a 由于目标函数的非凸性，用对偶法求解时，存在对偶间隙，需要根据对偶问 题的优化解采取一定的措施构造原问题的优化可行解，这是拉格朗日松弛法的一 个难点： b 算法的迭代过程中有可能出现振荡或奇异现象，需要采取措施加快收敛： c 考虑某些约束条件( 如机组爬坡速率) 会使计算复杂化。 2 3 5 网络流规划法“”“1 网络流规划法是针对网络问题的一类特殊算法，适合解高维数、多约束线性和 非线性优化问题，非常适用于日发电计划的制定。网络流规划法求解日发电计划数 学模型的基本思想是：根据网络的性质和特点，将各种约束条件用一个网络流模型 来表示，逐次以一次的步长增加报价最小的机组功率，直至负荷达到要求，使购电 成本最小。网络流法的优点在于它能针对不同的约束建立不同的网络流模型，因此 它能处理与时间相关的约束和网络安全约束。网络流规划法实用化的技术关键：一 个是网络流法和动态规划法一样，随着组合机组数目的增加，也存在“维数灾”的 问题，需要解决降阶可行解的搜索范围，另一个是解决潮流与实际潮流一致性问题。 2 ，3 ，6 动态规划法“”“ 动态规划法是求解多阶段决策问题的一种优化算法，其原理可叙述为：“对于整 个过程的最优化策略具有这样的性质，即无论过去的状态与决策如何，对于前面的 决策形成的状态而言，余下的决策必须构成最优策略”。它既能处理机组优化组合， 又能求解经济功率分配。由于此法自身的特性，它是赢接从报价曲线上取值进行优 化的，与曲线的导数没有关系，因此它可以解决各种类型报价曲线的负荷经济分配 问题。 但动态规划法存在的问题是当解题规模较大时，每个阶段需处理的状态量太 多，速度很慢，如果人为减少状态量，则有可能造成优化解的丧失，甚至可能造成 算法不收敛。同时，要求所求解的问题具有明显的阶段性。另外，动态规划法在求 解经济功率分配的时候，顺序造表的步长选取是个难点。步长选择过大，虽然计算 量减小，速度也提高了，但是计算精度却下降了：步长选择得越小，计算精度越高， 8 华北电力人学硕士学位论文 但计算量却显著增加。 针对动态规划法在求解机组优化组合时出现的维数灾问题，如d p - - s c ( d y n a m i c p 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 ) 将动态规划法与排序法相结合，机组只能 按优先顺序开停，虽然显著地减少了状态数。d p t c ( d y n a m i cp r o g r a m m i n g t r u n c a t e dc o m b i n a t i o n ) 只考虑机组开停机表后面一定数量的机组组合作为各阶 段的状态数，优化的范围有所扩大，但计算时间也随着增加。插值动态规划法是在 d p t c 法的基础上提出了路径的概念，在满足时间约束的路径中寻找满足其他约 束的最优路径，可以处理机组功率上升、下降速度约束，且考虑了机组的开、停机 特性，在一定程度上避免了“维数灾”。但是寻优路径选择是个难点，面且所得结 果很可能是局部最优解。 对于动态规划法在求解经济功率分配时出现的步长选取困难的情况，局部加密 动态规划法可比较好的协调步长与精度之间的关系，具体办法是对于状态先取稀疏 网格，求出较粗糙的优化解，在优化解轨迹附近取密网格，进一步求得优化解，继 续下去直到求出满意的最优解。该方法适用于目标函数比较平滑的情况。但邻域及 减小后的步长的确定是个难点，如果确定不准确，则有可能丢失最优解。 2 3 7 其他优化算法。”3 ”4 叩 除了上述介绍的优化算法以外，还有专家系统法，人工神经网络法模拟退火 算法，遗传算法( g a ) ，粒子群算法( p s o ) 等用于发电计划的求解。这些算法的优 点是智能性高，解的质量较好。缺点是算法复杂，计算时间长。另外其中一些算法 并不适合大规模系统的求解，如传统的遗传算法：同时，还有一些算法在求解过程 中易出现停滞现象，最终可能收敛于局部最优解，如粒子群算法。 2 4 本章小结 由上述的发电计划数学模型可知，它是一个高维数、非凸的、离散的、多约束 的、非线性优化问题。尤其是在电力市场下，问题变得更加复杂，要处理的约束更 多。因此，要解这样一个优化问题，深入研究和分析各种优化算法的优缺点，就显 得十分必要。从中选取适合的算法或算法组合，并针对算法的缺点进行有益的改进， 扬长而避短，最大限度地追求问题的最优解。 无论是经典算法还是现代智能算法，都有它自身的局限性。从发电计划优化问 题本身来讲，需要这样的优化算法来解，该算法具有计算速度快，能很好地处理各 种约束条件，最后解的质量高等特点。 9 华北电力大学硕十学位论文 3 1 引言 第三章基于动态规划法的日发电计划求解 多阶段决策问题是指这样一类问题，这些问题的决策过程可分成几个相互联系 的阶段，每个阶段都有若干种方案可供选择，要求分别在每个阶段做出决策，使问 题整体取得最优结果。而日前发电计划包括机组组合和经济功率分配两个部分，在 时间上交易同被分为多个交易时段，在空间上机组组合及经济功率分配是多台机组 的累加组合及出力。因此，日前发电计划问题本身就是一个多阶段决策问题。 动态规划法( d y n a m i cp r o g r a m m i n g ，d p ) 是求解多阶段决策问题的一种最优 化方法，它的最大优点就在于能把相对困难的多阶段决策问题转换成一系列比较容 易求解的单阶段决策问题。 动态规划法目前存在的问题是，当解题规模较大时，每个阶段需处理的状态量太 多，速度很慢，如果人为减少状态量，则有可能造成优化解的丧失，甚至可能造成 算法不收敛。针对这个问题，本文采用按综合报价排队确定机组优先次序来得到各 时段临界机组，在临界机组附近适当选取寻优范围来得到各时段可行状态组合。根 据程序实际运行的情况，能做到在运算速度较快的情况下的计算结果接近最优解。 3 2 动态规划法的基本原理n 3 2 1 动态规划法的发展及其研究内容 动态规划是运筹学的一个分支，是求解决策过程( d e c i s i o np r o c e s s ) 最优化的 数学方法。2 0 世纪5 0 年代初美国数学家r e b e l m a n 等人在研究多阶段决策过程 ( m u l t i s t e pd e c i s i o np r o c e s s ) 的优化问题时，提出了著名的最优化原理 ( p r i n c i p l eo fo p t i m a l i t y ) ，把多阶段过程转化为一系列单阶段问题，逐个求解， 创立了解决这类过程优化问题的新方法一动态规划。1 9 5 7 年出版的他的名著 d y n a m i cp r o g r a m m i n g ，这是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到 了广泛的应用“例如最短路线、库存管理、资源分配、设备更新、组合、排序、装 载等问题，采用动态规划法求解比用其它方法更为方便。 3 2 2 动态规划法的基本概念 一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。 1 阶段 1 0 华北电力人学硕士学位论文 阶段( s t a g e ) 是对整个过程的自然划分。通常根据时间顺序或者空间特征来划分 阶段，对于与时间，空间无关的“静态”优化问题，可以根据其自然特征，人为地 赋予“时段”概念，将静态问题动态化，以便按阶段的次序解优化问题。阶段变量 一般用k = l ，2 ，n 表示。 2 状态 状态( s t a t e ) 是我们所研究的问题( 也叫系统) 在各个阶段的初始形态或客观条 件。它应能描述过程的特征并且具有无后效性，即当某阶段的状态给定时，这个阶 段以后的过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是直接或者 间接可以观测的。描述状态的变量称为状态变量( s t a t ev a r i a b l e ) 。变量允许取值 的范围称为允许状态集合( s e to fa d m i s s i b l es t a t e s ) 。用x ( ) 表示第k 阶段的状 态变量，它可以是一个数或一个向量。用x ( t ) 表示第k 阶段的允许状态集合。 n 个阶段的决策过程有n + 1 个状态变量，x ( n + 1 ) 表示z ( ”) 演变的结果。 根据过程演变的具体情况，状态变量可以是离散的或连续的。为了计算的方便 有时将连续变量离散化：为了分析的方便有时又将离散变量视为连续的。 3 决策 当一个阶段的状态确定后，可以做出各种选择从而演变到下一阶段的某个状 态，这种选择手段称为决策( d e c i s i o n ) ，在最优控制问题中也称为控制( c o n t r 0 1 ) 。 描述决策的变量称决策变量( d e c i s i o nv a r i a b l e ) 。变量允许取值的范围称为允许 决策集合( s e to fa d m i s s i b l ed e c i s i o n s ) 。用( 工( _ j ) ) 表示第k 阶段处于状态x ( k ) 时的决策变量，它是x ( k ) 的函数。用u 。( x ( ) ) 表示x ( k ) 的允许决策集合决策变量简 称决策。显然，( x ( 七) ) u 。( 工( 七) ) 。 4 策略 决策组成的序列称为策略( p o l i c y ) 。由初始状态薯开始的全过程的策略记作 e 。( x ( 1 ) ) 。 鼻。( x ( 1 ) ) = “1 ( x ( 1 ) ) ，“2 ( x ( 2 ) ) ，u n ( x ( 聆) ) 。 ( 3 1 ) 由第k 阶段的状态x ( k ) 开始到终止状态的后部子过程的策略吃( x ( ) ) ， 只h ( x ( 后) ) = “女( x ( 七) ) ，“。( x ( n ) ) ， k = 2 ，”一1 。 ( 3 2 ) 可供选择的策略有一定的范围，称为允许策略集合( s e to fa d m is s i b l e p o l i c i e s ) ，用# 。 ( 1 ) ) ，咒( x ( 尼) ) 等表示。 5 状态转移方程 在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全可确 定。用状态转移方程( s t a t et r a n s f e re q u a t i o n s ) 表示这种演变规律，写作 x ( k + 1 ) = 丁( x ( ) ，“i ( x ( ) ) ) ，k = 1 ，2 ，n 。 ( 3 3 ) 6 阶段指标函数 对于k 阶段的状态x ( ) ，当执行了决策“。( x ( 后) ) 时，除带来系统状态的转移之 华北电力大学硕士学位论文 外，还产生第k 阶段的局部效益，它是总效益的一部分，称为阶段指标函数( s t a g e e f f e c t i v ef u n c t i o n ) ，拓j 作r 女( x ( 七) ，“( x ( 女) ) ) 。 7 过程指标函数 用来衡量策略或子策略执行效果的数量指标称为过程指标函数( p r o c e s s e f f e c t i v ef u n c t i o n ) ，它定义在所有k 后部子过程上，常用圪表示，即 k = 吒( x ( ) ，“i ( x ( 七) ) ，x ( k + 1 ) ，“女( x ( k + 1 ) ) ，一，x ( n ) ，“。( x ( h ) ) ) ( 3 4 ) k = 1 , 2 ，一，” 当k = 1 时，就是全过程指标函数。 如果状态x ( k ) 和子策略o ( 七) ) 给定，那么吒也就被确定了，所以k 是x ( ) 和 气( x ( ) ) 的函数。记为： 圪= k ( x ( 女) ，只。( x ( ) ) ) ( 3 5 ) 常见的过程指标函数是连和形式或连积形式： 旦 吒= _ ( x ( f ) ，z f 。( x ( f ) ) ) ，k = 1 , 2 ，甩 ( 3 6 ) i = k 月 圪= i i ( z ( f ) ，“，( x ( f ) ) ) ，k = 1 , 2 ，咒 ( 3 7 ) t = k 8 最优指标函数 过程指标函数圪= k ( x ( ) ，( x ( 七) ”的最优值，称为最优指标函数( o p t i m u m e f f e c t i v e f u n c t i o n ) ，记为，( x ( 七) ) 。它表示，采取了最优子策略 p 二( 工( 七) ) = 姐：( x ( i ) ) ，甜：o ( n ) ) ) 之后，后部子过程所获得的总效益，表示为 厂( x ( ) ) = o p t 圪( x ( 女) ，p h ( x ( 女) ) ) ，k = 1 , 2 ，- 一，n ( 3 8 ) 式中o p t 是o p t i m i z a t i o n 的缩写，意为最优化，可根据具体问题取m a x 或m i n 3 2 3 动态规划法的最优性原理和基本函数方程 在动态规划法中起核心作用的最优性原理：“作为整个过程的最优策略具有这 样的性质，无论过去的状态和决策如何，相对于前面决策所形成的状态而言，余下 的决策序列必须构成最优子策略。” 动态规划解法的关键在于给出一种递推关系，一般把这种关系称为基本函数方 程， k ( x ( 七) ，鼻。( x ( 七) ) ) = “( x ( 七) ，“t ( x ( 七) ) ) + 圪“( x ( 七+ 1 ) ，只k + 1 ) n ( x ( 七) ) ) ( 3 9 ) 注意到无后效性，最优指标函数为 ，( z ( 女) ) = o p t k ( x ( 意) ，只。( z ( 七) ) ) = o p t r k ( x ( t ) ，“女( x ( 七) ) ) + k + l ( x ( k + 1 ) ，鼻+ m ( x ( k + 1 ) ) ) = o p t r k ( x ( | i ) ，h ( x ( 七) ) ) + o p tk “( x ( 七十1 ) ，只+ l h ( x ( k + 1 ) ) ) “只 十1 1 ” = o p t r ( z ( 女) ， 女( x ( 七) ) ) + f ( x ( k + 1 ) ) ) ( 3 l o ) 1 2 华北电力大学硕+ 学位论文 当k = ”时，由于x ( n + 1 ) 是整个决策过程的终止状态，以后不再做出决策，因此， k 。( x ( h + 1 ) ，甜。( x ( n + 1 ) ) ) = 0 ，从而f ( x ( n + 1 ) ) = 0 。这样就得到了可以用来递推的基 本函数方 厂( x ( ) ) = o p t r k ( x ( 七) ，“l ( x ( 七) ) ) + f ( x ( k + 1 ) ) ) ，k = ，n l ，- ，1 ( 3 1 1 ) “ f ( x ( n + 1 ) ) = 0 类似地，可以得到乘法形式的基本函数方程： 厂( x ( | 】 ) ) = o p t r k ( x ( 女) ，甜i ( x ( 七) ) ) f ( x ( k + 1 ) ) ) ，k = ，”一1 ，一一，1 ( 3 1 2 ) h f ( x ( n + 1 ) ) = 1 3 2 4 建立动态规划模型的基本步骤 1 阶段： 2 、状态变量及可能状态集合； 3 决策变量及允许决策集合： 4 状态转移方程； 5 阶段指数函数； 6 基本函数方程。 建立动态规划模型，基本上是按照上述顺序，逐步确定1 6 的内容。 3 2 5 动态规划法的递推方向及求解形式 1 逆推解法 基本方程： ，( x ( _ j ) ) = o p t r k ( x ( 七) ，”t ( z ( 女) ) ) + f ( x ( k + 1 ) ) ，k = ，船一l ，- ，1 ( 3 1 3 ) “t f ( x ( n + 1 ) ) = 0 状态转移方程为 x ( k + 1 ) = r ( x ( 七) ，”( x ( 尼) ) ) ，k = ”，n l ，一，1 ( 3 1 4 ) 计算步骤是，利用终端条件从k = 开始由后向前逆推基本方程，求得各阶段的 最优决策和最优函数，最后算出，( z ( 1 ) ) 时就得到了最优决策序列 k ( x ( 后) ) ，x ( k ) 肖( 七) k = 1 , 2 ，” ) 。再按照状态转移方程x ( k + 1 ) = r ( x ( ) ，“t ( x ( ) ) ) 从k = 1 开始由前向后确定x ( k ) ，序列 x ( k ) ，k = 1 , 2 ，n ) 为最优轨线，f “( x ( ) ) ， k = 1 , 2 ，竹 为最优策略。 2 顺推解法 使用顺推解法时，一些概念的含义须作相应调整。 状态变量x ( 女) 表示第k 阶段末系统的形态、状况， 第l 阶段到第k 阶段总效益的最优值，状态转移方程为 x ( k 一1 ) = 丁( x ( ) ，“。( x ( ) ) ) ，k = 1 , 2 ，- ，” 最优值函数，( x ( ) ) 表示从 ( 3 1 5 ) 华北电力大学硕士学位论文 基本函数方程为 ，( x ( ) ) = o p t r k ( x ( ) ，u 女( x ( 女) ) ) + f ( x ( k 一1 ) ) ) ，k = 1 , 2 ，一，” ( 3 1 6 ) 毗 ，( x ( 0 ) ) = 0 或l 3 求解形式 求解动态规划问题，一般有两种形式：解析形式和表格形式，解析形式是利用 函数的解析表达式，在每个阶段用经典求极值的方法得到最优解。表格形式是指各 阶段的计算过程均在表格中进行，这种形式便于分析和比较，操作过程直观且简练， 适用于没有解析表达式的离散型问题。 3 3 动态规划法在该问题中的具体实现 3 3 1 选取各时段运行状态 3 3 1 1 基于动态规划法的日前发电计划数学模型 目标函数( 计及机组的启动费用) f = 。m 。i 。n 。、 b ( x ( f ) ) + s o ( t - 1 ) ，x ( f ) ) ) u ( 1 ) u ( 2 ) 上，( r ) p ( 1 ) 尸( 2 ) ，z ) ：，