动态规划是解决多阶段决策过程最优化的一种方法

《动态规划是解决多阶段决策过程最优化的一种方法》由会员分享，可在线阅读，更多相关《动态规划是解决多阶段决策过程最优化的一种方法（2页珍藏版）》请在金锄头文库上搜索。

1、动态规划是解决多阶段决策过程最优化的一种方法。 动态规划把困难的多阶段决策问题变换成一系列互相联系比较容易的单阶段问题，解 决了这一系列比较容易的单阶段问题，也就解决了这困难的多阶段决策问题。 多阶段决策问题，是指这样一类活动的过程：在它的每个阶段都需要做出决策，并且 一个阶段的决策确定以后，常影响下一个阶段的决策，从而影响整个过程决策的效果。多 阶段决策问题就是要在允许的各阶段的决策范围内，选择一个最优决策，使整个系统在预 定的标准下达到最佳的效果。 有时阶段可以用时间表示，在各个时间段，采用不同决策，它随时间而变动，这就有 “动态”的含意。动态规划就是要在时间的推移过程中，在每个时间阶段选

2、择适当的决策， 以便整个系统达到最优。 用动态规划可以解决管理中的最短路问题、装载问题、库存问题、资源分配、生产过 程等最优化问题。 近几十年来，动态规划在理论、方法和应用等方面取得了突出的进展，并在工程技术、 经济、工业生产与管理、军事工程等领域得到广泛的应用。 建立动态规划中最优目标函数一般需要用到下列术语： 1. 阶段 用动态规划求解多阶段决策系统问题时，要根据具体情况，将系统适当地分成若干个 阶段，以便分阶段求解，一般是根据时间与空间的自然特征去划分阶段，描述阶段的变量 称为阶段变量。 2. 状态 状态表示系统在某一阶段开始时所处的自然状况或客观条件。过程的状态可用状态变量来描述，如：

3、，某个阶段所有可能状态的全体可用状态集合来描述，如：A B11,L，。sA B211,sAB CD32222,L3.决策 某一阶段的状态确定以后，从该状态演变到下一阶段某一状态所作的选择称为决策。 第阶段的决策与第个阶段的状态有关，通常用表示第阶段处于状态时的nn)(nnxunnx决策变量，而这个决策又决定了第阶段的状态。如上例中在第阶段用表示1nkuxkk()处于状态时的决策变量。决策变量限制的范围称为允许决策集合。用表示第xkDxkk()阶段从出发的决策集合。kxk 4. 策略 由每阶段的决策组成的决策函数序列称为全过程策略或简称u xinii()(, , ) 1 2 L 策略，用表示。即

4、pp xu xuxuxnn()(),(),()11122L由系统的第阶段开始到终点的决策过程称为全过程的后部子过程，相应的策略称为后部k 子过程策略。用表示子过程策略。即pxkk()kpxuxuxuxkkkkkknn()(),(),()11L对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称 为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。 5. 状态转移 某一阶段的状态变量及决策变量取定后，下一阶段的状态就随之而定。设第个阶段k 的状态变量为，决策变量为，则第阶段的状态，用xkuxkk()k 1xk1表示从阶段到阶段的状态转移规律，称它为状态转移方程。x

5、k1 Txukkk(,)kk 1 6. 阶段效益 系统某阶段的状态一经确定，执行某一决策所得的效益称为阶段效益，它是整个系统效益的一部分，是阶段状态和阶段决策的函数，记为。xkukyxukkk(,) 7. 指标函数 指标函数是衡量全过程策略或子过程策略优的数量指标，指标函数的最优值称之为最 优指标函数。系统用某一策略而产生的效益用数量表示, 根据不同的实际，效益可以是利 润、距离、产量或资源的耗量等。指标函数可以定义在全过程上也可以定义在后部子过程 上。指标函数往往是各阶段效益的某种和式，取最优策略时的指标函数称为最优策略指标。对于对于阶段的动态规划阶段的动态规划问题，在求子过程上的最优指标函数时，子过程与子过nk1k 程有如下递推关系： 0)(1 , 2 , 1,)(),(min)(1111nnkkkkkkk xfnnkxfxsrsfL其中第一式子里的求最小值是指在的状态下，在所有作出的各种决策中，取一个第kskx阶段的指标值与以为第状态的子过程的最优指标函数值之和中k),(kkkxsrkx1k1k的最小值。对于求指标函数最大的动态规划问题的基本方程则把改为就行了。minmax作为整个过程的最优策略具有如下的性质：不管在此最优策略上的个状态以前的状态和 决策如何，对该状态来说，以后的所有决策必定构成最优子策略。也就是说最优策略的任 一子策略都是最优的。