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

劉麗

【摘要】本文用高維動(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ī)劃問題的求解成為可能。

【關(guān)鍵詞】動(dòng)態(tài)規(guī)劃；高維；優(yōu)化方法；渠道工程

目前，動(dòng)態(tài)規(guī)劃的“維數(shù)災(zāi)”問題受到計(jì)算機(jī)高速存儲(chǔ)量和計(jì)算時(shí)間的限制，在求解高維問題時(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ī)劃法^[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í)也遇到了這些問題，本文另辟其徑，采用文獻(xiàn)^[8～12]中的系統(tǒng)試驗(yàn)選優(yōu)基本思想，來(lái)求解高維動(dòng)態(tài)規(guī)劃問題，則可在該領(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ī)劃模型，模型的決策變量為各渠段縱坡（Ii）和各渠段的定性方案（Si），目標(biāo)函數(shù)為工程計(jì)算分析期內(nèi)的總支出費(fèi)用，并考慮首末水位、不沖不淤、渠道最小水位銜接和工程總投資約束. 為了進(jìn)一步提高模型決策的精度，在文獻(xiàn)^[13]的模型基礎(chǔ)上，再考慮以下約束：

1.1.1填挖土方量約束。若獲得滿足約束條件，且使文獻(xiàn)^[13]目標(biāo)函數(shù)最小的解，而渠道工程的填方量大于挖方量，附近又沒有土方資源，此時(shí)文獻(xiàn)^[13]中模型獲得的解就不一定為最優(yōu)解，因此，還應(yīng)加上填挖方量約束方程。

1.2求解方法。考慮全部約束條件，則模型為四維問題，該模型的求解工作量、難度比文獻(xiàn)^[13]的二維問題大大增加了，為此本文在模型的求解方面進(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ì)算迭代過程中進(jìn)行，而不是傳統(tǒng)的計(jì)算迭代結(jié)束后檢驗(yàn)，因而不管拉格朗日乘子取值多少，采用廣義拉氏方法的解均為滿足約束條件的可行解.此時(shí)的問題就轉(zhuǎn)化為尋找最優(yōu)拉氏乘子的問題，根據(jù)數(shù)學(xué)模型和拉氏乘子的物理意義，容易知道拉氏乘子的取值范圍，在此基礎(chǔ)上則可采用部分試驗(yàn)選優(yōu)方法^[8～12]（如正交試驗(yàn)法）確定最優(yōu)的乘子值。

1.4實(shí)例分析。采用文獻(xiàn)^[13]算例，有關(guān)主要參數(shù)和可能的定性方案見表1.通過計(jì)算分析u2，u3，u4的取值范圍均取為[0，2.4]，選用L9（34）型正交表對(duì)所選的9個(gè)uj組合進(jìn)行了對(duì)應(yīng)的一維動(dòng)態(tài)規(guī)劃問題求解，其最優(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ī)劃問題求解分析，其最優(yōu)解和采用DDDP法求解結(jié)果基本相同，此時(shí)占用計(jì)算機(jī)的運(yùn)算時(shí)間不到DDDP法的1/6，有關(guān)計(jì)算主要成果摘要見表2和表3。

2. 結(jié)論

（1）尋求高維動(dòng)態(tài)規(guī)劃的求解方法是近40年國(guó)內(nèi)外眾多學(xué)者久攻不下的系統(tǒng)科學(xué)重大研究的課題.目前經(jīng)典方法一般僅能求解3～5維問題，其它近似方法也只能求解數(shù)拾維問題.本文提出的試驗(yàn)選優(yōu)方法可以使較高維數(shù)的高維動(dòng)態(tài)規(guī)劃問題求解成為可能.本文的試驗(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à)值。

參考文獻(xiàn)

[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]白憲臺(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]程吉林.某些特殊路徑問題的正交表法.系統(tǒng)工程，1991，（2）.

[11]程吉林.介紹一種大系統(tǒng)優(yōu)化的知識(shí)模型.系統(tǒng)工程理論和實(shí)踐，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]高侖彥.正交及回歸設(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é)研究所數(shù)理統(tǒng)計(jì)組.正交試驗(yàn)法.北京：人民教育出版社，1975，97～104.