论文部分内容阅读
【摘要】本文用高维动态规划模型进行大型渠道工程系统的优化设计，提出了高维动态规划的试验选优方法，使高维动态规划问题的求解成为可能。
【关键词】动态规划；高维；优化方法；渠道工程
目前，动态规划的“维数灾”问题受到计算机高速存储量和计算时间的限制，在求解高维问题时，常遇困难.近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.
【关键词】动态规划；高维；优化方法；渠道工程
目前，动态规划的“维数灾”问题受到计算机高速存储量和计算时间的限制，在求解高维问题时，常遇困难.近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.