确定机组组合的一种改进的动态规划方法

1、第25卷第5期2001年5月电网技术Power System TechnologyVol. 25 No. 5May. 2001文章编号:1000-3673 (2001) 05-0020-05确定机组组合的一种改进的动态规划方法王承民1,郭志忠1,于尔铿(1.哈尔滨工业大学，黑龙江省 哈尔滨市150001; 2中国电力科学研究院，北京100085)AN IMPROVED DYNAMIC PROGRAMMING METHODFOR DETERMINING UNIT COMMITMENT1 1 2WANG Cheng-min , GU O Zhi-zhong , YU Er- keng(1. Har

2、bi n In dustry Un iversity , Harbi n 150001, Heilo ngjia ng Provi nee, Chi na;2. Electric Power Research Institute, China, Beijing 100085, China)ABSTRACT : In this paper an improv ed dynamic programming method t o determine unit commitment is proposed T his proposed method is also named interpolated

3、 dynamic programming algor ithm. It is a heuristic method, which can be combined with other economic generation dispatching methods, to solve unit commitment problem under multi- constraints, specially the unit ramp constraint. I n this method the start-up ramp and the shut-down ramp of the units ar

4、e considered, and the curse of dimensionality can be effectively avoided. The results of practical tests show that this algorithm is simple and effective.KEY WORDS: unit commitment ; dynamic programming; interpolated dynamic prog ramming摘要：提岀了 一种确定 机组组合的 改进动态 规划方法,称为 插值动态规划算 法。这是一种启发 式方法，可以和其他的经 济调度

5、算法相结合，用以解决多种约束条件下的机组组合问 题,特别是可以处理机组功率上升、 下降速度 约束,且考虑了 机组的开、停机特性，并有效避免了“维数灾”问题,经实践检 验是一种简单、有效的实用算法。关键词：机组组合；动态规划；插值动态规划中图分类号：TM732文献标识码：A1引言机组组合就是在一定的运行周期内满足各种运 行条件情况下，通过合理地开、停机组达到总运行成 本最低的目标。目前用于解决机组组合问题的算法 主要有排队法1、动态规划法2、混合整数规划法3 和拉格朗日松弛法4等,动态规划算法是应用比较 广泛且行之有效的一种算法。以往对动态规划法的研究大多是针对动态规划方法的“维数灾”问题。DP

6、- SC法5,6 (dy namic programm ing seque ntial comb in ati on)将动 态规划法 与 排序法相结合，机组只能按优先顺序开停，虽然显著 地减少了状态数，但可能丢失最优解或次优解； 、丄【2, 7, 8DP-TC 法 (dynamic programming truncated combination)只考虑机组开停机表后面一定数量的 机组组合作为各阶段的状态数，优化的范围有所扩 大，但计算时间也随着激增；此外机组组合问题还可 以分解为一系列的子问题，每一子问题用动态规划 法求解，常用的分解方法有SA ( successiveapproxi-ma

7、-tion)法禾口 HA ( hierarchical approx imation)法,SA 法在用动态规划法解一个子问题时，将其他子问题的状态变量固定，来回迭代求解，直到所得的最优解 不再变化为止；HA法是将子问题独立解出，然后用 一协调因子将各子问题的解变换为全局最优解。在处理运行约束方面，大多数文献并没有解决机组功率上升、下降速度约束(ramp constrains简称 爬坡约束)特别是机组启动、停机时的爬坡问题【9 (starup ramp, shut down ramp),而这些约束又是机 组运行所不能违背的，因为机组组合确定后，经济调 度算法就会在在线的发电机组之间分配功率，但机

8、组的开机或停机是有一定过程的，特别是火电机组， 必须考虑锅炉的燃烧特性。 在表1中列出了一些发电 机组的启动特性。由此可见，在某时段确定某台机开 (停)后，在此时段的前若干时段(后若干时段)这台机就应该逐步加负荷(减负荷),也就是说，考虑了机 组的开机(停机)特性后，在某些时段，这些机组等值 于有固定出力的发电机组。第25卷第5期电网技术21它无法计入机组的开、停机特性。本文提出的插值动 态规划法是在 DP-TC法的基础上提出了路径的概 念,在满足时间约束的路径中寻找满足其他约束的 最优路径。表1机组的启动特性Tab. 1 Unit starting characters机组机组类型出力上限/

9、M Wpete 1燃煤229pete 2燃煤399pete3燃煤483pete4燃煤483stout7燃油395机组.开机时段及功率/MW1234567pete 15090140180220230pete 250120160200300350400pete 360120180220280320350pete 460120180220280320350pete 7801501501802002503502问题描述机组组合问题是一个多时段的优化问题，数学模型可以描述如下目标函数：T Nz = minQ 6 Fi,( pi,(, xi,(, ton, ti,off)约束条件:N6ipi,tpd, t

10、 - pc,t - pb, tpi, min W pi,t W pi, max NQ pi, maxN61 pt-i= 1Q 卩厂 > Smax,tN6 pi, minSmin, ti= 1pi,t - pi, t- 1 W Ri ,max , pi ,t- 1 - pi ,t W R i, minonof ft i, onT i, min ti, of f T i, min(1)(2)(3)(4)(5)(6)式中i= 1,2,N ,为机组数;t= 1,2,T,为时段数;Fi,t为第i台机组在第t时段的运行成本，是发 电机出力，开停状态，运行时间的函数；卩讥为第i台 机组在第t时段的出力

11、；xi,t为第i台机组在第t时段的状态，为0、1变量,0表示停机，1表示开机；pd,t 为第t时段的负荷；pc,t为第t时段与其他区域电网 的交换功率；pb,t为第t时段的基荷，即固定出力机 组出力的总和；Pi,max, pi, min为第i台机组的最大、最 小出力；Smax，t为系统负荷旋转备用最大值；3in，t为系统负荷旋转备用最小值 ；Ri，min为第i台机组的最 大功率下降速度限值；Rimax为第i台机组的最大功 率上升速度限值；ti,on为第i台机组连续开机时间； ti，off为第i台机组连续停机时间；T；nmin为第i台机组 的最小开机时间；T：fmin为第i台机组的最小停机时 间

12、。这是一个多约束的混合整数规划问题。系统的约束可以分为两类，一是静态约束；二是动态约束。 和单一时段状态变量相关联的约束称为静态约束，式（2）、（ 3）、（ 4）表示静态约束；和多个时段状态变 量相关联的约束为动态约束，式（5）、（6）表示动态约束。下面介绍求解这种优化问题的插值动态规划 法。3 插值动态规划算法动态规划方法是一种求解多阶段决策问题的优 化方法，用它求解有离散变量的机组组合问题是比 较方便的，图1为一简单系统的动态规划法示意图 （两台机，三个时段）,其中0、1表示机组 的开停状 态,每一圆圈表示的是一时段机组的组合状态，状态数共有2N - 1个。Fig. 1 Diagram o

13、f dynamic programming method 设每一状态的运行成本为NFt = 61 Fi，t（xi，t, pi，t, ti）（ 7）式中Ft为第t时段系统的运行成本。考虑了爬坡约束和机组的开停机特性之后，在单一时段内无法确定功率pi,t的值，所以Ft的值也无法确定，使传统动态规划算法的应用受到限制，为了解决这个问题，本文在DP-TC法的基础上提出了 改进的动态规划算法插值动态规划算法，这种 算法的特点是仍取 DP-T C法的近似，但不是去求解 某一时段状态变量的值，而是求解由所有时段组成 的路径的状态变量的值。首先给出路径的定义。从时段1到时段T的所 有时段中，每一时段任取一种机

14、组组合状态，这样组成的一个决策集合称为一条路径。 如图1黑线所示,为了减少被搜索路径的数量，路径的搜索次序支路1和2组成了一条路径。是很重要的，采用分支定界法的思路来搜索满足时设满足式（6）约束条件的所有路径集合为L,则式（1）（6）所描述的问题等价于以下问题：m inFl（8）其中Fl为一子优化问题，其表达式为TFl=眄6严佝它满足约束条件（2）（5）。对于任一条路径l,因为各机组的开停状态已经 确定,且满足时间约束，所以Ft只是功率pi,t的函 数,可用线性规划或二次规划等方法解式（9）的子规划问题。因为随着机组数量的增加，每一时段机组 组合的状态数也按指数规律增加，所以求解上述问题将不可

15、避免地导致“维数灾”。可以用下面的方法 解决维数灾”问题。对于集合L,取其中的M条路径进行寻优，这 M条路径均匀地分布在集合 L中,对于M条路径中 的最优路径，在其一定的邻域内进行进一步优化 ，所 得到的解即为机组组合问题的解。间约束的路径是必要的。如图1中的黑线所示,在第 2时段累积各机组的开、停机时间，如有不满足时间 约束的，则可以不搜索与支路1相关联的路径，这样 就大大减少了计算量。此外,为了减少被搜索路径的数量，在各时段可 以以负荷值来校验各状态的旋转备用约束，除去不满足旋转备用约束的状态后，可以不搜索与之相关联的路径，这也大大减小计算量。 如图1 所示,机组 开、停状态为0的状态没有

16、表示出，这就是因为当所 有机组停机时，不可能满足旋转备用约束。4算例本算法以辽宁省2000年4月6日的发电计划为实 例,系统的技术数据如表 2所示。此发电计划的周期 为1天，将1天分为48个时段，按照运行的惯例，前几 个时段和后几个时段是不开机也不停机的，所以只计算1244时段的机组组合,前12时段的机组组合 按前1天第48时段的机组组合结果，后4个时段的机第25卷第5期电网技术23组组合同第44时段的机组组合。2000年4月 6日技术参数M可视系统的规模及计算时间确定。表2辽宁省电力系统Tab. 2 Technique parameter of Liaoning power system o

17、n 04/06/ 2000机组ID号最小开机最小停机机组出力机组出力机组出力上升机组出力下降起机费/元时间/ h时间/h上限/MW下限/ MW速度约束/ (M W/min)速度约束/ ( M W/ min )Jzpg24420012715015071 174Jzpg54420012715015072 174Jzpg64420013015015072 174Ykpg 224243201801509010 000Shpg12020200140150150100 000Ddpg1243635024024018010 000Ddpg2243635024024018010 000L1pg14131218

18、4120150150100 000Qhpg5123520013015015025 000L1pg151312184120150150100 000Qhpg6123520013015015025 000Cypg224362001351509010 000Tipg3242429018018012010 000T ipg42424290180180120200 000Jzpg14420012615015072 174Cypg12448180120909010 000Dwpg2120336192150150300 000Tipg2486300165909010 000Qhpg7123520013015

19、015025 000Dwpg1120336192150150300 000Shpg22020200140300150100 000Tipg1242429020018012010 000Fxpg12436183135906060 000Qhpg8123520013015015025 000Jzpg44420012715015072 174Jzpg3442001271509072 174Dwpg4120336192180180300 000Dwpgj|；120皿日336192 ijK180180'Fvuij300 000L |表3全局寻优和进一步局部寻优的20条路径的运行费用Tab. 3

20、Production cost of full and further partial optimiation for 20 paths全局寻优/元进一步局部寻优/元4040578040255164402551644025516440150460405733004007370040626100401035004009300040150460401504604015046040150460401504604086770040193100405094004018280040492900401466484014664840146648401466484014664840207500404900004

21、0073700400737004007370040146648401466484014664840146648401466484007370040073700400737004007370040073700第25卷第5期电网技术#第25卷第5期电网技术#首先用排队算法进行初始状态排队，其结果如表4所示，从表4中可得到边界机组为第20台机 (dwpg1),取第18、19、20 21和225台机进行重新优化组 合,并且满足各种约束条件，用插值法找到其中的20 条路径，其购电费用如表3所示,称为全局范围内寻 优,寻取其中最小的一条路径，在其上下再选取20条 路径进行优化，优化的结果称为局部寻优，选取

22、最小 购电费用的路径，最终的机组组合结果如表 5所示。表3中运行费用全局寻优结果的最优值为40 146 648元，进一步的局部寻优结果为 40 073 700 元,可见,运算结果被进一步优化了。5结论法，同其他的动态规划算法一样，只能得到局部最优 解,但同以往的动态规划算法相比 ，它解决了爬坡约 束问题，并考虑了机组的开、停机特性曲线，这些都 是系统的实际运行所必须解决的，实践证明，这种算 法是一种简单、有效的算法。插值动态规划算法在确定机组组合的过程中，在解决外层问题时，只考虑了时间变量，因此它更接 近于类举法，但因为与DP-TC法相结合，故称为插 值动态规划算法。这种算法的缺点是，当插值点

23、过少 时,可能得不到满足约束条件的可行解，而当插值点 过多时，计算量显著增大。因此对于实际的系统，M 的取值是一个关键问题，应具体问题具体分析，以保 证所得到解的最优性。第25卷第5期电网技术#本文提出的插值动态规划算法是一种近似算 表4排队法运行结果Tab. 4 Results of order method时段机组状态时段机组状态1 1111111111111111100100000000252 1111111111111111100100000000263 1111111111111111100100000000274 1111111111111111100100000000285 11

24、11111111111111100100000000296 1111111111111111100100000000307 1111111111111111100100000000318 1111111111111111100100000000329 11111111111111111001000000003310 11111111111111111001000000003411 11111111111111111001000000003512 11111111111111111001000000003613 11111111111111111001000000003714 111111111

25、11111111001000000003815 11111111111111111101000000003916 11111111111111111101000000004017 11111111111111111101000000004118 11111111111111111101000000004219 11111111111111111101000000004320 11111111111111111101000000004421 1111111111111111111 1000000004522 1111111111111111111 100000000462311004724110

26、048111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

27、111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000

28、000001100000000110000000011000000001000000000100000000010000000001000000000第25卷第5期电网技术#花 1994-2012 Chifia Academic Joiimal Electronic Publishing Houac. All righl* reserved<h(lp:；7wwu1 第25卷第5期电网技术25表5插值动态规划法的运行结果Tab. 5 Results of dynamic programming method时段机组状态时段机组状态111111111111111111001000000002

29、51111111111111111110 10000000021111111111111111100100000000261111111111111111110 10000000031111111111111111100100000000271111111111111111110 10000000041111111111111111100100000000281111111111111111110 10000000051111111111111111100100000000291111111111111111110 100000000611111111111111111001000000003

30、01111111111111111110 10000000071111111111111111100100000000311111111111111111110 10000000081111111111111111100100000000321111111111111111110 10000000091111111111111111100100000000331111111111111111110 100000000101111111111111111100100000000341111111111111111110 10000000011111111111111111110010000000

31、0351111111111111111110 100000000121111111111111111100100000000361111111111111111110 100000000131111111111111111100100000000371111111111111111110 100000000141111111111111111100100000000381111111111111111110 100000000151111111111111111110100000000391111111111111111110 100000000161111111111111111110100

32、000000401111111111111111110 100000000171111111111111111110100000000411111111111111111110 100000000181111111111111111110100000000421111111111111111110 100000000191111111111111111110100000000431111111111111111110 100000000201111111111111111110100000000441111111111111111110 1000000002111111111111111111

33、10100000000451111111111111111110000000000221111111111111111110100000000461111111111111111110000000000231111111111111111110100000000471111111111111111110000000000241111111111111111110100000000481111111111111111110000000000第25卷第5期电网技术#第25卷第5期电网技术#参考文献:1 Lee F N, Feng Q. M ulti- area unit commitmen t J

34、. IEEE T rans on PWRS, Paper 91 WM 180-0, New York, 1991.2 Pang C K, Sheble G B, Albuyyeh F. Evaluation of dynamic programming based method and multiple area representation for th ermal unit commitment .IEEE Trans on PAS , 1981, 100(3) .3 Habi bollah zadeh H, Buben ko J A. Application of decom posit

35、ion techniques to short- term operation planning of hydrothermal power system J. IEEE T rans on PWRS, 1986, 1( 1).4 Ruzic S Rajakovic N . A new approach for solvin g extended unit commitment problem J. IEEE Trans on PWRS, 1991, 6( 1).5 Tong S K, Shahidehpour S M. Hydrothermal unit comm itment with probabilistic constrai