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

(49)~(55)式是一個(光滑)凸規(guī)劃問題.

證明: 根據(jù)問題(49)―(55)的結(jié)構(gòu)特點(diǎn), 可以發(fā)現(xiàn)約束(50)~(55)中, 除約束(53)外, 其余約束均為優(yōu)化變量的線性等式/不等式約束, 所以如果能證明約束(53)的凸性, 結(jié)論(i)即可得證.

將約束(53)改寫為:

Step 1. 若 k = K, 停止; 否則置 k =k+1繼續(xù). Step 2. 根據(jù)(12)~(13)式計算i(gi,k?1,gi,k)和

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

Step 3. 按定理3證明中指出的方法在區(qū)間

max

t∈[(k?1)τ,kτ]上計算uimin,k(t)和ui,k(t)(階梯函數(shù)).

Step 4. 根據(jù)(58)式計算θk.

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

Step 5. 根據(jù)(60)―(61)式在區(qū)間t∈[(k?1)τ,kτ]

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

i

i

根據(jù)定理2, i(?,?)是光滑的凸函數(shù), i(?,?)是光滑的凹函數(shù), 從而?i(?,?)是光滑的下凸函數(shù), 由此觀察約束(66)和(67)可知(66)和(67)的左端均為決策

變量的凸函數(shù), 又因?yàn)檫@兩個約束都是“≤0”型約束, 因此問題(49)~(55)的可行域是一個閉凸集.

在結(jié)論(i)的基礎(chǔ)上, 結(jié)論(ii)是顯然的. 定理4證畢. 在電力系統(tǒng)生產(chǎn)調(diào)度等很多實(shí)際問題中, 生產(chǎn)制造成本或費(fèi)用是凸函數(shù), 如火電機(jī)組的煤耗曲線常取為二次凸函數(shù), 即Ci(?)為凸函數(shù), 此時求解非

圖3 兩階段法框架

49

管曉宏等: 一類含積分約束的生產(chǎn)制造系統(tǒng)優(yōu)化調(diào)度

以上兩階段算法最主要的特點(diǎn)體現(xiàn)在兩個方面: 第一, 問題模型準(zhǔn)確, 考慮了生產(chǎn)率積分約束, 保證了產(chǎn)量優(yōu)化調(diào)度結(jié)果的可實(shí)現(xiàn)性, 克服了傳統(tǒng)模型的缺陷; 第二, 當(dāng)生產(chǎn)成本為凸函數(shù)時, 得到的是全局最優(yōu)解.

成本(發(fā)電煤耗成本)函數(shù)表達(dá)式為:

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

其中ai,bi,ci均為非負(fù)常數(shù), 因此生產(chǎn)成本為產(chǎn)量的光滑凸函數(shù). 各機(jī)組的主要參數(shù)及系統(tǒng)在各時段的負(fù)荷需求分別在表2和表3中給出.

我們在PⅣ2. 0GHz Windows工作站上應(yīng)用Matlab 6.5優(yōu)化工具箱中的序列二次規(guī)劃函數(shù)對問題求解, 時間約為418 s, 獲得機(jī)組1和機(jī)組3的最優(yōu)生產(chǎn)率曲線如圖4所示.

在圖4中, 每個圓圈標(biāo)示出了在相鄰時段交界點(diǎn)處的機(jī)組瞬時出力. 對比系統(tǒng)負(fù)荷需求數(shù)據(jù)(表3)和機(jī)組參數(shù)(表2)可以發(fā)現(xiàn), 機(jī)組1的生產(chǎn)成本最低, 因此在負(fù)荷需求較大時處于滿負(fù)荷運(yùn)轉(zhuǎn); 機(jī)組3的生產(chǎn)成本較高, 因此僅在負(fù)荷需求較大時發(fā)電功率較大, 在負(fù)荷需求很低時發(fā)電功率處于較低水平. 對于機(jī)

5 應(yīng)用示例

我們將本文的理論結(jié)果應(yīng)用于電力系統(tǒng)生產(chǎn)優(yōu)化調(diào)度(亦稱經(jīng)濟(jì)分配), 經(jīng)大量實(shí)例測試, 驗(yàn)證了本文提出的求解方法非常有效, 本節(jié)簡要介紹8機(jī)組優(yōu)化調(diào)度案例的測試結(jié)果.

考慮一個8臺機(jī)組的電力系統(tǒng)生產(chǎn)優(yōu)化調(diào)度問題, 調(diào)度周期為24 h, 每個時段1 h. 對應(yīng)于模型(1)~ (8)有: I=8,K=24h,τ=1h. 標(biāo)準(zhǔn)的離散時間經(jīng)濟(jì)分配模型可參見文獻(xiàn)[22,23]. 各機(jī)組(生產(chǎn)設(shè)備)的生產(chǎn)

表2 各機(jī)組物理參數(shù)

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 系統(tǒng)在各時段的負(fù)荷需求

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 機(jī)組1(a)和機(jī)組3(b)的最優(yōu)出力曲線

50

中國科學(xué): 技術(shù)科學(xué) 2010年 第40卷 第1期

組3, 初始時刻發(fā)電功率較高是因?yàn)槭艿匠踔导s束(約束(8)).

在此必須說明, 對于第一階段得到的pi(k)和gi,k, 可能有無窮多gi(t)和ui(t)使得約束(4)~(9)成立, 即第二階段可能有無窮多組解. 這種現(xiàn)象已在定理3的證明中有所暗示. 定理3的證明是一種構(gòu)造性證明, 僅指出了解的存在性和一種最自然的構(gòu)造方法, 并未討論解的唯一性. 上節(jié)的算法中給出的也是最易于理解和編程實(shí)現(xiàn)的一種構(gòu)造算法. 在實(shí)際應(yīng)用中, 可以根據(jù)可能的二級優(yōu)化目標(biāo)或其他要求從多組gi(t)和ui(t)中選出最合適的一組作為最終解. 在本節(jié)的算例中, 我們基于一種系統(tǒng)化算法從眾多的gi(t)和ui(t)中選出了一組最“光滑”的gi(t)及其對應(yīng)的ui(t)作為最終解, 其物理意義為使機(jī)組出力盡量平穩(wěn), 在滿足系統(tǒng)需求和總成本最低的前提下機(jī)組出力爬升盡量小. 由于詳細(xì)的實(shí)現(xiàn)過程與本文主題關(guān)系不大, 對此問題我們已另文討論.

注意到圖4中的橫軸時間單位為小時, 最優(yōu)的機(jī)

組出力曲線實(shí)際上相當(dāng)平穩(wěn), 完全滿足爬升約束等對機(jī)組出力曲線的要求. 算例測試結(jié)果表明, 本文提出的方法是有效的, 得到了最優(yōu)的生產(chǎn)調(diào)度計劃.

6 結(jié)論

在“即時消費(fèi)”型產(chǎn)品的生產(chǎn)系統(tǒng)優(yōu)化調(diào)度中, 積分約束通常必須考慮. 目前廣泛采用的離散時間模型可能導(dǎo)致產(chǎn)量計劃不可實(shí)現(xiàn). 本文分析了現(xiàn)有模型的缺陷, 建立了具有積分約束的優(yōu)化問題模型, 并證明此類問題可轉(zhuǎn)化為光滑的非線性規(guī)劃問題, 當(dāng)費(fèi)用函數(shù)為凸(或效益函數(shù)為凹)時可進(jìn)一步等價為光滑凸規(guī)劃問題. 本文給出了構(gòu)造原問題等價最優(yōu)解的系統(tǒng)方法, 并提出了兩階段求解框架. 新模型及其求解算法不僅克服了傳統(tǒng)模型下的調(diào)度結(jié)果不可實(shí)現(xiàn)問題, 而且當(dāng)生產(chǎn)成本為凸函數(shù)時可以獲得全局最優(yōu)解. 基于電力系統(tǒng)調(diào)度的實(shí)例測試表明本文提出的相關(guān)理論和算法非常有效.

參考文獻(xiàn)

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松弛法解化工批處理調(diào)度問題. 自動化學(xué)報, 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 翟橋柱, 管曉宏, 郭燕, 等. 具有混合動態(tài)約束的生產(chǎn)系統(tǒng)優(yōu)化調(diào)度新算法. 自動化學(xué)報, 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 余貽鑫, 王東濤. 輸電系統(tǒng)動態(tài)安全風(fēng)險評估與優(yōu)化. 中國科學(xué)E輯: 技術(shù)科學(xué), 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