求解一维非线性规划问题的改进动态规划算法

文章编号：1672-3791（2015）12（a）-0264-02

1 问题的提出

目前，动态规划算法在解决多决策问题中的应用比较普遍。但是，在遇到求解最小目标函数（最大化约束条件）时，状态变量在各阶段的离散不尽相同，且当状态变量离散步长过大时，会导致最优目标函数值精度不高，不利于应用到实际问题中来。

2 动态规划模型的建立与求解

2.1 动态规划方法介绍

动态规划是运筹学的一个分支，是求解多阶段决策问题的最优化方法。根据Bellman的最优化原理（对最优策略来说，无论过去状态和决策如何，从前面诸决策所形成的状态出发，相应的剩余决策序列构成最优子策略），利用逆推（初始状态给定）和顺推方法（终止状态给定）可求出最优决策和最优值[2]。它的主要解题思路：在阶段可分的前提下，把多阶段过程转化为一系列单阶段问题，逐个求解。应指出，动态规划是求解某类问题的一种方法，是考虑问题的一种途径，而不是一种特殊算法。

动态规划用来描述多阶段决策问题的基本概念[3，4]有：阶段与阶段变量k，状态与状态变量sk，决策与决策变量xk（sk），策略p1，n（s1）与最优策略p*1，n（s1），指标函数V1，n与最优指标函数fk（sk），阶段指标（阶段效益）vk（sk，xk），状态转移方程sk+1=Tk（sk，xk）等。

2.2 模型建立

4 结语

该动态规划解法在求解最小值目标函数时，可避开各阶段状态变量的离散域问题，直接从决策变量的离散域角度考虑状态变量的离散范围，最终由各决策变量构成的约束域来确定满足总约束条件的最优目标函数值，并由此求得最优路径。

参考文献

[1]伦·库柏，玛丽·W·库柏.动态规划导论[M].北京：国防工业出版社，1985：7.

[2]吴庆丰，刘兵兵.利用动态规划求解资源分配问题[J].安庆师范学院学报：自然科学版，2008，14（2）：74-75.