Step 0. (初始化)记录第一阶段得到的解, 即: pi(k), gi,k(i=1,2,",I, k=1,2,",K). 然后, 置k=0.

(49)~(55)式是一个(光滑)凸规划问题.

证明: 根据问题(49)―(55)的结构特点, 可以发现约束(50)~(55)中, 除约束(53)外, 其余约束均为优化变量的线性等式/不等式约束, 所以如果能证明约束(53)的凸性, 结论(i)即可得证.

将约束(53)改写为:

Step 1. 若 k = K, 停止; 否则置 k =k+1继续. Step 2. 根据(12)~(13)式计算i(gi,k?1,gi,k)和

i(gi,k?1,gi,k).

Step 3. 按定理3证明中指出的方法在区间

max

t∈[(k?1)τ,kτ]上计算uimin,k(t)和ui,k(t)(阶梯函数).

Step 4. 根据(58)式计算θk.

P(gi,k?1,gi,k)?pi(k)≤0, (66)

Step 5. 根据(60)―(61)式在区间t∈[(k?1)τ,kτ]

pi(k)?i(gi,k?1,gi,k)≤0, (67) 上计算u(t)和g(t), 返回Step 1.

i

i

根据定理2, i(?,?)是光滑的凸函数, i(?,?)是光滑的凹函数, 从而?i(?,?)是光滑的下凸函数, 由此观察约束(66)和(67)可知(66)和(67)的左端均为决策

变量的凸函数, 又因为这两个约束都是“≤0”型约束, 因此问题(49)~(55)的可行域是一个闭凸集.

在结论(i)的基础上, 结论(ii)是显然的. 定理4证毕. 在电力系统生产调度等很多实际问题中, 生产制造成本或费用是凸函数, 如火电机组的煤耗曲线常取为二次凸函数, 即Ci(?)为凸函数, 此时求解非

图3 两阶段法框架

49

管晓宏等: 一类含积分约束的生产制造系统优化调度

以上两阶段算法最主要的特点体现在两个方面: 第一, 问题模型准确, 考虑了生产率积分约束, 保证了产量优化调度结果的可实现性, 克服了传统模型的缺陷; 第二, 当生产成本为凸函数时, 得到的是全局最优解.

成本(发电煤耗成本)函数表达式为:

Ci(pi(k))=ai(pi(k))2+bipi(k)+ci, (68)

其中ai,bi,ci均为非负常数, 因此生产成本为产量的光滑凸函数. 各机组的主要参数及系统在各时段的负荷需求分别在表2和表3中给出.

我们在PⅣ2. 0GHz Windows工作站上应用Matlab 6.5优化工具箱中的序列二次规划函数对问题求解, 时间约为418 s, 获得机组1和机组3的最优生产率曲线如图4所示.

在图4中, 每个圆圈标示出了在相邻时段交界点处的机组瞬时出力. 对比系统负荷需求数据(表3)和机组参数(表2)可以发现, 机组1的生产成本最低, 因此在负荷需求较大时处于满负荷运转; 机组3的生产成本较高, 因此仅在负荷需求较大时发电功率较大, 在负荷需求很低时发电功率处于较低水平. 对于机

5 应用示例

我们将本文的理论结果应用于电力系统生产优化调度(亦称经济分配), 经大量实例测试, 验证了本文提出的求解方法非常有效, 本节简要介绍8机组优化调度案例的测试结果.

考虑一个8台机组的电力系统生产优化调度问题, 调度周期为24 h, 每个时段1 h. 对应于模型(1)~ (8)有: I=8,K=24h,τ=1h. 标准的离散时间经济分配模型可参见文献[22,23]. 各机组(生产设备)的生产

表2 各机组物理参数

Unit No. (i)

i(MW) gi(MW)

Δi (MW/h)

ai ($/(MWh)2) bi ($/MWh) ci ($) gi(0) (MW)

1 455 150 600.6 0.00031 17.62 970 300 2 455 150 600.6 0.00031 17.62 970 300 3 180 25 247 0.00395 19.5 456 60 4 170 25 243 0.00395 19.7 450 55 5 162 25 243 0.00399 19.8 445 55 6 162 25 240 0.00398 19.7 450 60 7 80 25 144 0.00712 22.26 370 30 8 65 10 102.3 0.00222 27.27 665 10

表3 系统在各时段的负荷需求

k 1 2 3 4 5 6 7 8 9 10 11 12 D(k) (MWh) 765 805 875 915 976 1055 1265 1270 1465 1465 1683 1688

k 13 14 15 16 17 18 19 20 21 22 23 24 D(k) (MWh) 1470 1420 1360 1360 1390 1450 1370 1320 1350 1300 840 760

图4 机组1(a)和机组3(b)的最优出力曲线

50

中国科学: 技术科学 2010年 第40卷 第1期

组3, 初始时刻发电功率较高是因为受到初值约束(约束(8)).

在此必须说明, 对于第一阶段得到的pi(k)和gi,k, 可能有无穷多gi(t)和ui(t)使得约束(4)~(9)成立, 即第二阶段可能有无穷多组解. 这种现象已在定理3的证明中有所暗示. 定理3的证明是一种构造性证明, 仅指出了解的存在性和一种最自然的构造方法, 并未讨论解的唯一性. 上节的算法中给出的也是最易于理解和编程实现的一种构造算法. 在实际应用中, 可以根据可能的二级优化目标或其他要求从多组gi(t)和ui(t)中选出最合适的一组作为最终解. 在本节的算例中, 我们基于一种系统化算法从众多的gi(t)和ui(t)中选出了一组最“光滑”的gi(t)及其对应的ui(t)作为最终解, 其物理意义为使机组出力尽量平稳, 在满足系统需求和总成本最低的前提下机组出力爬升尽量小. 由于详细的实现过程与本文主题关系不大, 对此问题我们已另文讨论.

注意到图4中的横轴时间单位为小时, 最优的机

组出力曲线实际上相当平稳, 完全满足爬升约束等对机组出力曲线的要求. 算例测试结果表明, 本文提出的方法是有效的, 得到了最优的生产调度计划.

6 结论

在“即时消费”型产品的生产系统优化调度中, 积分约束通常必须考虑. 目前广泛采用的离散时间模型可能导致产量计划不可实现. 本文分析了现有模型的缺陷, 建立了具有积分约束的优化问题模型, 并证明此类问题可转化为光滑的非线性规划问题, 当费用函数为凸(或效益函数为凹)时可进一步等价为光滑凸规划问题. 本文给出了构造原问题等价最优解的系统方法, 并提出了两阶段求解框架. 新模型及其求解算法不仅克服了传统模型下的调度结果不可实现问题, 而且当生产成本为凸函数时可以获得全局最优解. 基于电力系统调度的实例测试表明本文提出的相关理论和算法非常有效.

参考文献

1 Talluri T T, Van Ryzin G J. The Theory and Practice of Revenue Management. Heidelberg: Springer, 2004

2 Bannister C H, Kaye R J. A rapid method for optimization of linear systems with storage. Oper Res, 1991, 39(2): 220—232

3 Chen H, Chu C, Proth J M. An improvement of the Lagrangian relaxation approach for Job Shop Scheduling: A dynamic programming

method. IEEE Trans Rob Autom, 1998, 14(5): 786—795

4 Cohen A I, Sherkat V. Optimization-based methods for operations scheduling. Proc IEEE, 1987, 75(12): 1574—1591 5 王朝晖, 陈皓勋, 胡保生. 用Lagrangian松弛法解化工批处理调度问题. 自动化学报, 1998, 24(1): 1—8

6 Muiser R F H, Evans L B. An approximated method for the production scheduling of industrial batch process with parallel units. Comp

Chem Eng, 1989, 13(2): 229—238

7 Salam M S, Nor K M, Hamdan A R. Hydrothermal scheduling based Lagrangian relaxation approach to hydrothermal coordination. IEEE

Trans Power Syst, 1998, 13(1): 226—235

8 Bard J F. Short-term scheduling of thermal-eglectric enerators using Lagrangian relaxation. Oper Res, 1988, 36(5): 756—766 9 翟桥柱, 管晓宏, 郭燕, 等. 具有混合动态约束的生产系统优化调度新算法. 自动化学报, 2004, 30(4): 539—546

10 Sand G, Engell S. Modeling and solving real-time scheduling problems by stochastic integer programming. Comp Chem Eng, 2004, 28(6-7): 1087—

1103

11 Guan X, Guo S, Zhai Q. The conditions for obtaining feasible solutions to security-constrained unit commitment problems. IEEE Trans

Power Syst, 2005, 20(4): 1746—1756

12 Fu Y, Shahidehpour M. Fast SCUC for large-scale power systems. IEEE Trans Power Syst, 2007, 22(4): 2144—2151

13 Silva B, Stursberg O, Krogh B, et al. An assessment of the current status of algorithmic approaches to the verification of hybrid systems.

Proceedings of IEEE Conference on Decision and Control. Orlando: IEEE, 2001, 12: 2867—2874

14 Till J, Engell S, Panek S, et al. Applied hybrid system optimization: An empirical investigation of complexity. Control Eng Practice, 2004,

12(10): 1291—1303

15 Ferreira L A F M, Anderson T, Imparato C F, et al. Short-term resource scheduling in multi-area hydrothermal power systems. Electric

Power & Energy Systems, 1989, 11(3): 200—212

16 Guan X, Gao F, Svoboda A J. Energy delivery capacity and generation scheduling in the deregulated electric power Market. IEEE Trans

Power Syst, 2000, 15(4): 1275—1280

17 Wang C, Shahidehpour S M. Optimal generation scheduling with ramping costs. IEEE Trans Power Syst, 1995, 10(1): 60—67 18 余贻鑫, 王东涛. 输电系统动态安全风险评估与优化. 中国科学E辑: 技术科学, 2009, 39(2): 286—292

19 Si B F, Long J C, Gao Z Y. Optimization model and algorithm for mixed traffic of urban road network with flow interference. Sci China Ser

E-Tech Sci, 2008, 51(12): 2223—2232

20 Hiriart-Urruty J, Lemarechal C. Fundamentals of Convex Analysis. Heidelberg: Springer, 2001

21 Bazaraa M S, Sherali H D, Shetty C M. Nonlinear Programming: Theory and Algorithms. 2nd ed. New York: John Wiely, 1993 22 Travers D, Kaye R J. Dynamic dispatch by constructive dynamic programming. IEEE Trans Power Syst, 1998, 13(1): 72—78

23 Han X S, Gooi H B, Kirschen D S. Dynamic economic dispatch: Feasible and optimal solutions. IEEE Trans Power Syst, 2001, 16(1): 22—28

51