高维动态规划试验选优及其在大型渠道工程系统设计中的应用

摘要：本文用高维动态规划模型进行大型渠道工程系统的优化设计，提出了高维动态规划的试验选优方法，使高维动态规划问题的求解成为可能.

关键词：动态规划 高维 优化方法 渠道工程

　　目前，动态规划的“维数灾”问题受到计算机高速存储量和计算时间的限制，在求解高维问题时，常遇困难.近40年来，各国学者对动态规划的计算方法进行了多方面的探索，提出了各种方法，如旨在减少维数的拉格朗日乘子法［1］、动态规划逐次渐近法［2］，聚合法［3］，旨在减少离散状态数的离散微分动态规划法［4］、双状态动态规划法［5］、状态增量动态规划法［6］和不离散状态直接求解以减少计算量的微分动态规划［7］(要求目标函数、约束条件三阶可微)以及H.R.Howson等人1975年提出的以减少阶段数为手段的渐进优化法［7］.这些方法虽然一定程度上减轻了“维数灾”，但进展并不很大.作者在对大型渠道工程系统优化设计研究时也遇到了这些问题，本文另辟其径，采用文献［8—12］中的系统试验选优基本思想，来求解高维动态规划问题，则可在该领域内取得突破性的进展.

1　大中型渠道工程优化设计的高维动态规划模型及求解方法

1.1　大中型渠道工程优化设计的高维动态规划模型 文献［13］提出了大中型渠道工程系统的定性定量混合系统动态规划模型，模型的决策变量为各渠段纵坡(Ii)和各渠段的定性方案(Si)，目标函数为工程计算分析期内的总支出费用，并考虑首末水位、不冲不淤、渠道最小水位衔接和工程总投资约束.

　　为了进一步提高模型决策的精度，在文献［13］的模型基础上，再考虑以下约束：

　　(1) 填挖土方量约束. 若获得满足约束条件，且使文献［13］目标函数最小的解，而渠道工程的填方量大于挖方量，附近又没有土方资源，此时文献［13］中模型获得的解就不一定为最优解，因此，还应加上填挖方量约束方程
　　　　　　(1)

式中Vis(Ii，Si)和Vis(Ii，Si)为i渠段的填方和挖方量.

　　(2)流量损失约束.不同的衬砌方式、不同的渠道过水断面影响渠段的流量损失和投资，而输配水渠道的设计主要在于保证下游获得在一定水位时的流量，因此，在可能的情况下还应进一步考虑流量损失约束：
　　　　　　　　(2)

　　式中h4i(Ii，Si)为i渠段的流量输水损失，取决于i渠道的定性方案Si(沿渠衬砌方式等)、土壤性质、流量和过水断面；Q0，QN 分别为渠道工程的渠首设计引水量和渠末应获得的设计流量

　　1.2 求解方法 考虑全部约束条件，则模型为四维问题，该模型的求解工作量、难度比文献［13］的二维问题大大增加了，为此本文在模型的求解方面进行了一定的探讨，提出了高维动态规划的试验选优方法.

　　1.2.1 基本原理 本文对高维动态规划的降维传统技术之一——拉格朗日乘子法［1］进行了修正，提出了广义拉氏方法，使加入到目标函数中去的约束检验在计算迭代过程中进行，而不是传统的计算迭代结束后检验，因而不管拉格朗日乘子取值多少，采用广义拉氏方法的解均为满足约束条件的可行解.此时的问题就转化为寻找最优拉氏乘子的问题，根据数学模型和拉氏乘子的物理意义，容易知道拉氏乘子的取值范围，在此基础上则可采用部分试验选优方法［8—12］(如正交试验法)确定最优的乘子值.

　　1.2.2 拉氏乘子已知时的优化技术 对于一般的高维问题(下面方程式依次为(3)(4))

　　　　　　Wj(λ1，X1)=bj-hj1(X1)，(8)

　　　　Wi(λ1)=Wi(λ1，X*1)，j=1，2，…，m-1，(9)

式中ζ1为hm1(ζ1)=λ1 的解，0≤X1≤ζ1，同时迭代过程中X1应满足加入至目标函数中去的m-1个约束，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 的解，0≤Xi≤ζi，同时迭代过程中Xi应满足 Wj(λi，Xi)≥0(j=1，2，…，m-1)，最后i=N时式(9)中的松驰变量Wj=Wj(λ*N).

　　由上递推关系可获得uj(j=1，2，…，m-1)已知情况下的最优决策X*i(i=1，2，…，N).

　　1.2.3 拉氏乘子的优化技术 由式(5)目标函数可知(F)/(bj)=uj，uj 的物理意义为某种资源(bj)的影子价格，uj 的数值大小取决于该资源的利用情况.在求解实际问题时，使式(3)、(4)最优的u*j 获得是困难的，但确定uj的数值范围是容易的.

　　例如已知uj(j=1，2，…，m-1)的数值范围来确定其对应的最优值 u*j，最直接的方法是把uj在其数值范围内离散，然后将所有组合代入模型(5)、(6)，以获得最优解，若m较大时，这样工作量太大，显然是不太实际的，但可以采用部分试验选优方法如正交试验法［14～17］，在全部可能组合中选取少量组合， 采用模型(5)、(6)以获得优化解，然后通过正交分析来获得所有可能组合中的最优解及依次的次优解.

　　1.2.4 正交试验和正交表 采用正交试验在uj(j=1，2，…，m-1)的取值范围内确定u*j，其最优性、精度和计算工作量的关键在于正交表的构造选择.正交试验的最优性在文献［15—17］中已被广泛讨论和确认，精度和uj在其对应取值范围内的离散步长有关，并直接影响计算优化的工作量.若构造一般型正交表Lp(tq)，t为uj 在其可行域内离散的个数，其为素数或素数幂；q为该正交表最多可以按排uj的个数，即q≥m-1;P为对应一维动态规划模型计算个数；P、t，q之间存在以下关系［17］：

　　　　　　　　　　　P=　　(13)
　　　　　　　　　q=(-1)/(t-1)　　(14)

式中v为任意正整数，则可以获得计算工作量(P)和m，t之间的关系
　　　　　
　　　　　　　　P≥(m-1)(t-1)+1　　(15)

　　选择构造正交表时完全可以使式(15)取等号，则若m=1001，取t=11或101，那么一个1001维动态规划问题的优化工作量相当于104+1或105+1个对应一维动态规划问题的计算工作量，目前一般计算机均可接受，而对于现行动态规划的所有降维、简化方法是无法想象的.

　　　　　　　　Wj(λ1，X1)=bj-hj1(X1)，(21)

　　　　　　　Wj(λ1)=Wj(λ1，X*1)，(22)

　　X1∈(I1，S1)，式中ζ1∈［v1，u1］，设渠段1定性方案依
次代入下式：
　　　　　　　　　(23)
得对应的，t=1，2，…，T1｝;t1为对应定性方案u时的纵坡I1可行取值范围，结合式(17)、(18)有：（下面的情况分别为：渠段末有流量变化，无交叉节制提水建筑；除上情况）
　　　　(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依次代入下式：

以此递推得uj已知情况下式(16)—(19)的解.

　　关于uj(j=2，3，4)的取值范围确定.本课题根据Ii和Si的可行范围、沿渠地形的变化情况、各渠段的流量，以及模型(16)中目标函数的物理意义，可以知道：
的数值范围(Ai，Bi)即：

若设u2=u３=u４=ui，则可得：

采用最不利的(Ii，Si)代入即可获得uj的取值范围.

　　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 定性方案和基本数据

　　　　　　表2 计算成果对照表

　　　　表3 DDDP法和采用L25(56)型正交分析优化成果表