大型渠道工程系統設計中高維動態規劃試驗選優的應用探討

劉麗

【摘要】本文用高維動態規劃模型進行大型渠道工程系統的優化設計，提出了高維動態規劃的試驗選優方法，使高維動態規劃問題的求解成為可能。

【關鍵詞】動態規劃；高維；優化方法；渠道工程

目前，動態規劃的“維數災”問題受到計算機高速存儲量和計算時間的限制，在求解高維問題時，常遇困難.近40年來，各國學者對動態規劃的計算方法進行了多方面的探索，提出了各種方法，如旨在減少維數的拉格朗日乘子法^[1]、動態規劃逐次漸近法^[2]，聚合法^[3]，旨在減少離散狀態數的離散微分動態規劃法^[4]、雙狀態動態規劃法^[5]、狀態增量動態規劃法^[6]和不離散狀態直接求解以減少計算量的微分動態規劃^[7]（要求目標函數、約束條件三階可微）以及H.R.Howson等人1975年提出的以減少階段數為手段的漸進優化法^[7].這些方法雖然一定程度上減輕了“維數災”，但進展并不很大.作者在對大型渠道工程系統優化設計研究時也遇到了這些問題，本文另辟其徑，采用文獻^[8～12]中的系統試驗選優基本思想，來求解高維動態規劃問題，則可在該領域內取得突破性的進展。

1. 大中型渠道工程優化設計的高維動態規劃模型及求解方法

1.1大中型渠道工程優化設計的高維動態規劃模型。文獻^[13]提出了大中型渠道工程系統的定性定量混合系統動態規劃模型，模型的決策變量為各渠段縱坡（Ii）和各渠段的定性方案（Si），目標函數為工程計算分析期內的總支出費用，并考慮首末水位、不沖不淤、渠道最小水位銜接和工程總投資約束. 為了進一步提高模型決策的精度，在文獻^[13]的模型基礎上，再考慮以下約束：

1.1.1填挖土方量約束。若獲得滿足約束條件，且使文獻^[13]目標函數最小的解，而渠道工程的填方量大于挖方量，附近又沒有土方資源，此時文獻^[13]中模型獲得的解就不一定為最優解，因此，還應加上填挖方量約束方程。

1.2求解方法。考慮全部約束條件，則模型為四維問題，該模型的求解工作量、難度比文獻^[13]的二維問題大大增加了，為此本文在模型的求解方面進行了一定的探討，提出了高維動態規劃的試驗選優方法。

1.2.1基本原理。本文對高維動態規劃的降維傳統技術之一——拉格朗日乘子法^[1]進行了修正，提出了廣義拉氏方法，使加入到目標函數中去的約束檢驗在計算迭代過程中進行，而不是傳統的計算迭代結束后檢驗，因而不管拉格朗日乘子取值多少，采用廣義拉氏方法的解均為滿足約束條件的可行解.此時的問題就轉化為尋找最優拉氏乘子的問題，根據數學模型和拉氏乘子的物理意義，容易知道拉氏乘子的取值范圍，在此基礎上則可采用部分試驗選優方法^[8～12]（如正交試驗法）確定最優的乘子值。

1.4實例分析。采用文獻^[13]算例，有關主要參數和可能的定性方案見表1.通過計算分析u2，u3，u4的取值范圍均取為[0，2.4]，選用L9（34）型正交表對所選的9個uj組合進行了對應的一維動態規劃問題求解，其最優解和采用DDDP法求解結果目標值相差5.6%，對uj進一步離散選用L25（56）型正交表選擇對應25個uj組合進行對應的一維動態規劃問題求解分析，其最優解和采用DDDP法求解結果基本相同，此時占用計算機的運算時間不到DDDP法的1/6，有關計算主要成果摘要見表2和表3。

2. 結論

（1）尋求高維動態規劃的求解方法是近40年國內外眾多學者久攻不下的系統科學重大研究的課題.目前經典方法一般僅能求解3～5維問題，其它近似方法也只能求解數拾維問題.本文提出的試驗選優方法可以使較高維數的高維動態規劃問題求解成為可能.本文的試驗方法主要針對正交試驗法而言的，對于采用其它部分試驗選優方法進行優化分析，還有待于進一步探討。

（2）本文提出的大型渠道工程優化設計的高維動態規劃模型對大型調水工程優化設計具有較為重要的參考價值。

參考文獻

[1]Leon C， Mary W C.Introduction to Dynimic Programming.PergamonmPress， 1981， 197～207.

[2]Bellman R E， Dreyfus S E. Applied Dynamic Programming.Princeton Unversity Press， 1962， 293～3852.

[3]Turgeon A. A decomposition method for the long＼|term schednling of reservoirs in series. Water resources research， 1981，17（6）.

[4]Heidar M，Chow V T， et al. Disrete differential dynamic programming approach to water resource optimization.Water resources research， 1971，17（2）.

[5]Ozden M. A binary state DP algorithm for operation problem of multireservoir system. Water resource resecrch.1984，20（1）.

[6]Larson R E. State increment dynamic prorgamming.Management science 19， 1973，1452～1458.

[7]白憲臺，多維動態規劃.北京：水利電力出版社，1988，43～52.

[8]程吉林，金兆森，大系統模擬試驗選優方法及應用.水利學報，1993，（11）.

[9]程吉林，孫學華，模擬技術、正交設計、層次分析及其在灌區優化規劃中的應用.水利學報，1990，（9）.

[10]程吉林.某些特殊路徑問題的正交表法.系統工程，1991，（2）.

[11]程吉林.介紹一種大系統優化的知識模型.系統工程理論和實踐，1992，（4）.

[12]Jilin C， et al. Optimal test theory of 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.

[13]Jilin 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]高侖彥.正交及回歸設計方法.北京：冶金工業出版社，1985.

[15]北京大學力學系概率統計組.關于正交設計的優良性.應用數學學報，1977，（1～2）.

[16]馬希文.正交設計的數學理論.北京：人民教育出版社，1981.

[17]中科院數學研究所數理統計組.正交試驗法.北京：人民教育出版社，1975，97～104.