高維動(dòng)態(tài)規(guī)劃試驗(yàn)選優(yōu)及其在大型渠道工程系統(tǒng)設(shè)計(jì)中的應(yīng)用(1)

1、    高維動(dòng)態(tài)規(guī)劃試驗(yàn)選優(yōu)及其在大型渠道工程系統(tǒng)設(shè)計(jì)中的應(yīng)用(1)    本文用高維動(dòng)態(tài)規(guī)劃模型進(jìn)行大型渠道工程系統(tǒng)的優(yōu)化設(shè)計(jì)，提出了高維動(dòng)態(tài)規(guī)劃的試驗(yàn)選優(yōu)方法，使高維動(dòng)態(tài)規(guī)劃問(wèn)題的求解成為可能. 關(guān)鍵詞：動(dòng)態(tài)規(guī)劃 高維 優(yōu)化方法 渠道工程 目前，動(dòng)態(tài)規(guī)劃的“維數(shù)災(zāi)”問(wèn)題受到計(jì)算機(jī)高速存儲(chǔ)量和計(jì)算時(shí)間的限制，在求解高維問(wèn)題時(shí)，常遇困難.近40年來(lái)，各國(guó)學(xué)者對(duì)動(dòng)態(tài)規(guī)劃的計(jì)算方法進(jìn)行了多方面的探索，提出了各種方法，如旨在減少維數(shù)的拉格朗日乘子法1、動(dòng)態(tài)規(guī)劃逐次漸近法2，聚合法3，旨在減少離散狀態(tài)數(shù)的離散微分動(dòng)態(tài)規(guī)劃法

2、4、雙狀態(tài)動(dòng)態(tài)規(guī)劃法5、狀態(tài)增量動(dòng)態(tài)規(guī)劃法6和不離散狀態(tài)直接求解以減少計(jì)算量的微分動(dòng)態(tài)規(guī)劃7(求目標(biāo)函數(shù)、約束條件三階可微)以及H.R.Howson等人1975年提出的以減少階段數(shù)為手段的漸進(jìn)優(yōu)化法7.這些方法雖然一定程度上減輕了“維數(shù)災(zāi)”，但進(jìn)展并不很大.作者在對(duì)大型渠道工程系統(tǒng)優(yōu)化設(shè)計(jì)研究時(shí)也遇到了這些問(wèn)題，本文另辟其徑，采用文獻(xiàn)812中的系統(tǒng)試驗(yàn)選優(yōu)基本思想，來(lái)求解高維動(dòng)態(tài)規(guī)劃問(wèn)題，則可在該領(lǐng)域內(nèi)取得突破性的進(jìn)展.1大中型渠道工程優(yōu)化設(shè)計(jì)的高維動(dòng)態(tài)規(guī)劃模型及求解方法1.1大中型渠道工程優(yōu)化設(shè)計(jì)的高維動(dòng)態(tài)規(guī)劃模型 文獻(xiàn)13提出了大中型渠道工程系統(tǒng)的定性定量混合系統(tǒng)動(dòng)態(tài)規(guī)劃模型，模型的決策變

3、量為各渠段縱坡(Ii)和各渠段的定性方案(Si)，目標(biāo)函數(shù)為工程計(jì)算分析期內(nèi)的總支出費(fèi)用，并考慮首末水位、不沖不淤、渠道最小水位銜接和工程總投資約束.為了進(jìn)一步提高模型決策的精度，在文獻(xiàn)13的模型基礎(chǔ)上，再考慮以下約束：(1) 填挖土方量約束. 若獲得滿足約束條件，且使文獻(xiàn)13目標(biāo)函數(shù)最小的解，而渠道工程的填方量大于挖方量，附近又沒(méi)有土方資源，此時(shí)文獻(xiàn)13中模型獲得的解就不一定為最優(yōu)解，因此，還應(yīng)加上填挖方量約束方程(1) 式中Vis(Ii,Si)和Vis(Ii,Si)為i渠段的填方和挖方量.(2)流量損失約束.不同的襯砌方式、不同的渠道過(guò)水?dāng)嗝嬗绊懬蔚牧髁繐p失和投資，而輸配水渠道的設(shè)計(jì)主在

4、于保證下游獲得在一定水位時(shí)的流量，因此，在可能的情況下還應(yīng)進(jìn)一步考慮流量損失約束：(2)式中h4i(Ii,Si)為i渠段的流量輸水損失，取決于i渠道的定性方案Si(沿渠襯砌方式等)、土壤性質(zhì)、流量和過(guò)水?dāng)嗝?；Q0，QN 分別為渠道工程的渠首設(shè)計(jì)引水量和渠末應(yīng)獲得的設(shè)計(jì)流量1.2 求解方法 考慮全部約束條件，則模型為四維問(wèn)題，該模型的求解工作量、難度比文獻(xiàn)13的二維問(wèn)題大大增加了，為此本文在模型的求解方面進(jìn)行了一定的探討，提出了高維動(dòng)態(tài)規(guī)劃的試驗(yàn)選優(yōu)方法.1.2.1 基本原理 本文對(duì)高維動(dòng)態(tài)規(guī)劃的降維傳統(tǒng)技術(shù)之一拉格朗日乘子法1進(jìn)行了修正，提出了廣義拉氏方法，使加入到目標(biāo)函數(shù)中去的約束檢驗(yàn)在計(jì)算

5、迭代過(guò)程中進(jìn)行，而不是傳統(tǒng)的計(jì)算迭代結(jié)束后檢驗(yàn)，因而不管拉格朗日乘子取值多少，采用廣義拉氏方法的解均為滿足約束條件的可行解.此時(shí)的問(wèn)題就轉(zhuǎn)化為尋找最優(yōu)拉氏乘子的問(wèn)題，根據(jù)數(shù)學(xué)模型和拉氏乘子的物理意義，容易知道拉氏乘子的取值范圍，在此基礎(chǔ)上則可采用部分試驗(yàn)選優(yōu)方法812(如正交試驗(yàn)法)確定最優(yōu)的乘子值.1.2.2 拉氏乘子已知時(shí)的優(yōu)化技術(shù) 對(duì)于一般的高維問(wèn)題(下面方程式依次為(3)(4)(3)(4)Xi0,(i=1,2,N)    對(duì)m-1個(gè)約束考慮松馳變量Wj(j=1,2,，m-1),則約束(4)中m-1個(gè)約束轉(zhuǎn)化為Wj0；模型(3)、(4)轉(zhuǎn)化為一維問(wèn)

6、題，其模型為：（下面方程式依次為(5)(6)(5)(6)若 uj 已知，j=1,2，m-1，則有對(duì)應(yīng)的遞推關(guān)系：1階段：(7)Wj(1,X1)=bj-hj1(X1),(8)Wi(1)=Wi(1,X*1),j=1,2,，m-1,(9)式中1為hm1(1)=1 的解，0X11，同時(shí)迭代過(guò)程中X1應(yīng)滿足加入至目標(biāo)函數(shù)中去的m-1個(gè)約束，Wj(1,X1)0，j=1,2,m-1.i 階段：(10)Wj(i,Xi)=Wj(i-1)-hji(Xi),(11)i-1=i-hmi(i),(i=2,3,，N)(12)式中為hmi(i)=i 的解，0Xii，同時(shí)迭代過(guò)程中Xi應(yīng)滿足 Wj(i,Xi)0(j=1,2,

7、，m-1),最后i=N時(shí)式(9)中的松馳變量Wj=Wj(*N).由上遞推關(guān)系可獲得uj(j=1,2,，m-1)已知情況下的最優(yōu)決策X*i(i=1,2,，N).1.2.3 拉氏乘子的優(yōu)化技術(shù) 由式(5)目標(biāo)函數(shù)可知(F)/(bj)=uj,uj 的物理意義為某種資源(bj)的影子價(jià)格，uj 的數(shù)值大小取決于該資源的利用情況.在求解實(shí)際問(wèn)題時(shí)，使式(3)、(4)最優(yōu)的u*j 獲得是困難的，但確定uj的數(shù)值范圍是容易的.例如已知uj(j=1,2,，m-1)的數(shù)值范圍來(lái)確定其對(duì)應(yīng)的最優(yōu)值 u*j，最直接的方法是把uj在其數(shù)值范圍內(nèi)離散，然后將所有組合代入模型(5)、(6)，以獲得最優(yōu)解，若m較大時(shí)，這樣

8、工作量太大，顯然是不太實(shí)際的，但可以采用部分試驗(yàn)選優(yōu)方法如正交試驗(yàn)法1417，在全部可能組合中選取少量組合， 采用模型(5)、(6)以獲得優(yōu)化解，然后通過(guò)正交分析來(lái)獲得所有可能組合中的最優(yōu)解及依次的次優(yōu)解.1.2.4 正交試驗(yàn)和正交表 采用正交試驗(yàn)在uj(j=1,2,，m-1)的取值范圍內(nèi)確定u*j,其最優(yōu)性、精度和計(jì)算工作量的關(guān)鍵在于正交表的構(gòu)造選擇.正交試驗(yàn)的最優(yōu)性在文獻(xiàn)1517中已被廣泛討論和確認(rèn)，精度和uj在其對(duì)應(yīng)取值范圍內(nèi)的離散步長(zhǎng)有關(guān)，并直接影響計(jì)算優(yōu)化的工作量.若構(gòu)造一般型正交表Lp(tq),t為uj 在其可行域內(nèi)離散的個(gè)數(shù)，其為素?cái)?shù)或素?cái)?shù)冪；q為該正交表最多可以按排uj的個(gè)數(shù)，

9、即qm-1;P為對(duì)應(yīng)一維動(dòng)態(tài)規(guī)劃模型計(jì)算個(gè)數(shù)；P、t,q之間存在以下關(guān)系17：P=(13)q=(-1)/(t-1)(14)式中v為任意正整數(shù)，則可以獲得計(jì)算工作量(P)和m,t之間的關(guān)系P(m-1)(t-1) 1(15)選擇構(gòu)造正交表時(shí)完全可以使式(15)取等號(hào)，則若m=1001,取t=11或101，那么一個(gè)1001維動(dòng)態(tài)規(guī)劃問(wèn)題的優(yōu)化工作量相當(dāng)于104 1或105 1個(gè)對(duì)應(yīng)一維動(dòng)態(tài)規(guī)劃問(wèn)題的計(jì)算工作量，目前一般計(jì)算機(jī)均可接受，而對(duì)于現(xiàn)行動(dòng)態(tài)規(guī)劃的所有降維、簡(jiǎn)化方法是無(wú)法想象的.         

10、0;  摘本文用高維動(dòng)態(tài)規(guī)劃模型進(jìn)行大型渠道工程系統(tǒng)的優(yōu)化設(shè)計(jì)，提出了高維動(dòng)態(tài)規(guī)劃的試驗(yàn)選優(yōu)方法，使高維動(dòng)         本篇論文是由3COME文檔頻道的網(wǎng)友為您在網(wǎng)絡(luò)上收集整理餅投稿至本站的，論文版權(quán)屬原作者，請(qǐng)不用于商業(yè)用途或者抄襲，僅供參考學(xué)習(xí)之用，否者后果自負(fù)，如果此文侵犯您的合法權(quán)益，請(qǐng)聯(lián)系我們。    1.3 渠道工程優(yōu)化設(shè)計(jì)模型的求解 模型(1)(6)轉(zhuǎn)化為一維問(wèn)題： (16) Iby,iIiIbc,i(Si),i=1,2,，N ，(17)

11、I（2）kIkI（）k(18)(ki,kmaxN-1,為渠末有流量變化，且無(wú)提水節(jié)制建筑的渠段)(19)    可見(jiàn)決策變量Xi為(Ii,Si);狀態(tài)變量i為水頭損失，0ib1，由遞推關(guān)系式(7)(12)結(jié)合文獻(xiàn)13可得對(duì)應(yīng)的遞推關(guān)系：1階段：(20)Wj(1,X1)=bj-hj1(X1),(21)Wj(1)=Wj(1,X*1),(22)X1(I1,S1),式中1v1,u1，設(shè)渠段1定性方案依次代入下式：(23)得對(duì)應(yīng)的，t=1,2,，T1;t1為對(duì)應(yīng)定性方案u時(shí)的縱坡I1可行取值范圍，結(jié)合式(17)、(18)有：（下面的情況分別為：渠段末有流量變化，無(wú)

12、交叉節(jié)制提水建筑；除上情況）(24)i 階段：(25)Wj(i,Xi)=Wj(i-1)-hji(Xi),(26)i-1=i-h1i(Xi),    i=2,3,，N.(27) Xi(Ii,Si).式中i(vi,ui)，渠段i的定性方案S依次代入下式：(28)得對(duì)應(yīng)定性方案uti的縱坡取值范圍，結(jié)合式(17)、(18)有：(i=2,3,，N)(29)以此遞推得uj已知情況下式(16)(19)的解.關(guān)于uj(j=2,3,4)的取值范圍確定.本課題根據(jù)Ii和Si的可行范圍、沿渠地形的變化情況、各渠段的流量，以及模型(16)中目標(biāo)函數(shù)的物理意義，可以知道：的數(shù)值

13、范圍(Ai,Bi)即：(30)若設(shè)u2=u=u=ui,則可得：,(i=1,2,，N)(31)采用最不利的(Ii,Si)代入即可獲得uj的取值范圍.1.4 實(shí)例分析 采用文獻(xiàn)13算例，有關(guān)主參數(shù)和可能的定性方案見(jiàn)表1.通過(guò)計(jì)算分析u2,u3,u4的取值范圍均取為0，2.4，選用L9(34)型正交表對(duì)所選的9個(gè)uj組合進(jìn)行了對(duì)應(yīng)的一維動(dòng)態(tài)規(guī)劃問(wèn)題求解，其最優(yōu)解和采用DDDP法求解結(jié)果目標(biāo)值相差5.6%，對(duì)uj進(jìn)一步離散選用L25(56)型正交表選擇對(duì)應(yīng)25個(gè)uj組合進(jìn)行對(duì)應(yīng)的一維動(dòng)態(tài)規(guī)劃問(wèn)題求解分析，其最優(yōu)解和采用DDDP法求解結(jié)果基本相同，此時(shí)占用計(jì)算機(jī)的運(yùn)算時(shí)間不到DDDP法的1/6，有關(guān)計(jì)算

14、主成果摘見(jiàn)表2和表3.2結(jié) 論(1)尋求高維動(dòng)態(tài)規(guī)劃的求解方法是近40年國(guó)內(nèi)外眾多學(xué)者久攻不下的系統(tǒng)科學(xué)重大研究的課題.目前經(jīng)典方法一般僅能求解35維問(wèn)題，其它近似方法也只能求解數(shù)拾維問(wèn)題.本文提出的試驗(yàn)選優(yōu)方法可以使較高維數(shù)的高維動(dòng)態(tài)規(guī)劃問(wèn)題求解成為可能.本文的試驗(yàn)方法主針對(duì)正交試驗(yàn)法而言的，對(duì)于采用其它部分試驗(yàn)選優(yōu)方法進(jìn)行優(yōu)化分析，還有待于進(jìn)一步探討.(2)本文提出的大型渠道工程優(yōu)化設(shè)計(jì)的高維動(dòng)態(tài)規(guī)劃模型對(duì)大型調(diào)水工程優(yōu)化設(shè)計(jì)具有較為重的參考價(jià)值.表1 定性方案和基本數(shù)據(jù)    渠 段 OA AB BC CD   

15、60;渠長(zhǎng)/km 15 11 32 21    設(shè)計(jì)流量/m/s 100 100 50 50    加大流量/m/s 120 120 60 60    最小流量/m/s 40 40 20 20    沿渠土壤性質(zhì) 砂土 砂土 砂壤 砂壤    斷面形狀和襯砌方案 a.梯形斷面；擴(kuò)寬系數(shù) K=2.5，2.2，2.0，1.8；換土壓實(shí).b.梯形斷面；擴(kuò)寬系數(shù) K=2.2，2.0，1.8，1.6；無(wú)襯砌

16、.    可行提水泵站方案的提水揚(yáng)程/m 023 023 234 023    沿渠地面高程/m 36.3 37.7 38.1 39.2 39.9    其它主資料 a.總投資小于1億元；b.渠道首末水頭分別為35.5m和37.5m.c.求挖方和填方之差小于10%. 表2 計(jì)算成果對(duì)照表    渠 段 DDDP 法 試驗(yàn)方法uj離散5點(diǎn) 試驗(yàn)方法uj離散3點(diǎn) 備注      &

17、#160;     摘本文用高維動(dòng)態(tài)規(guī)劃模型進(jìn)行大型渠道工程系統(tǒng)的優(yōu)化設(shè)計(jì)，提出了高維動(dòng)態(tài)規(guī)劃的試驗(yàn)選優(yōu)方法，使高維動(dòng)         本篇論文是由3COME文檔頻道的網(wǎng)友為您在網(wǎng)絡(luò)上收集整理餅投稿至本站的，論文版權(quán)屬原作者，請(qǐng)不用于商業(yè)用途或者抄襲，僅供參考學(xué)習(xí)之用，否者后果自負(fù)，如果此文侵犯您的合法權(quán)益，請(qǐng)聯(lián)系我們。    運(yùn)算時(shí)間 15小時(shí)40分 2小時(shí)32分 1小時(shí)08分     

18、;目標(biāo)值：計(jì)算分析期內(nèi)總支出費(fèi)用現(xiàn)值/億元 2.802 2.802 2.96     投資現(xiàn)值/億元 0.934 0.934 0.967     總土方量/104m 1109 1109 1185     總挖方/104m 602 602 687     總填方/104m 507 507 498 表3 DDDP法和采用L25(56)型正交分析優(yōu)化成果表    渠 段 OA AB BC CD 

19、;   初砌方式 換土壓實(shí) 換土壓實(shí) 無(wú) 無(wú)    斷面形式 梯形，K=2.2 梯形，K=2.2 梯形，K=2.0 梯形，K=2.0    提水揚(yáng)程/m和泵位置 1 2 3     設(shè)計(jì)縱坡 1/25000 1/18300 1/22500 1/21000    設(shè)計(jì)底寬/m 12.0 2.0 8.0 9.0    設(shè)計(jì)水深/m 5.2 6.0 4.5 5.5 參 考

20、文 獻(xiàn)1Leon C, Mary W C.Introduction to Dynimic Programming.PergamonmPress, 1981, 197-207.2Bellman R E, Dreyfus S E. Applied Dynamic Programming.Princeton Unversity Press,1962, 293-38523Turgeon A. A decomposition method for the long|term schednling of reservoirs in series.Water resources research, 1981

21、,17(6).4Heidar M,Chow V T, et al. Disrete differential dynamic programming approach to water resource optimization.Water resources research, 1971,17(2).5Ozden M. A binary state DP algorithm for operation problem of multireservoir system. Water resource resecrch.1984,20(1).6Larson R E. State incremen

22、t dynamic prorgamming.Management science 19, 1973,1452-1458.7白憲臺(tái)，多維動(dòng)態(tài)規(guī)劃.北京：水利電力出版社，1988，43-52.8程吉林，金兆森, 大系統(tǒng)模擬試驗(yàn)選優(yōu)方法及應(yīng)用.水利學(xué)報(bào)，1993，(11).9程吉林,孫學(xué)華,模擬技術(shù)、正交設(shè)計(jì)、層次分析及其在灌區(qū)優(yōu)化規(guī)劃中的應(yīng)用.水利學(xué)報(bào)，1990，(9).10程吉林.某些特殊路徑問(wèn)題的正交表法.系統(tǒng)工程，1991，(2).11.程吉林.介紹一種大系統(tǒng)優(yōu)化的知識(shí)模型.系統(tǒng)工程理論和實(shí)踐，1992，(4).12Jilin C, et al. Optimal test theory of

23、 large scale system and applying in irrigation district scheme.System science and system engineering,(ICCSSE'93)Edited by Zheng Weimin, International Academic Publishers Press, 1993, 348-356.13Jilin C, et al. A dynamic programming medol of mixture system for conveyance canal engineering.Journal of system science and system engineering, 1993,4(2).14高侖彥. 正交及回歸設(shè)計(jì)方法.北京：冶金工業(yè)出版社，1985.15北京大學(xué)力學(xué)系概率統(tǒng)計(jì)組. 關(guān)于正交設(shè)計(jì)的優(yōu)良性.應(yīng)用數(shù)學(xué)學(xué)報(bào)，1977，(1-2).16馬希文. 正交設(shè)計(jì)的數(shù)學(xué)理論.北京：人民教育出版社，1981.17中科院數(shù)學(xué)研究所