第七章动态规划方法建模

《第七章动态规划方法建模》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章动态规划方法建模动态规划是由理查德·贝尔曼（RichardBellman）所建立的，它是解最优化问题的一个特殊“技术”.我们这里用“技术”，是因为动态规划不是一个或一种特殊算法.7.1动态规划的基本概念在生产和科学实验中，有一类活动的过程，由于它的特殊性，可将过程分为若干个互相联系的阶段，在它的每一个阶段都需要作出决策，从而使整个过程达到最好的活动效果.因此，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展.当各个阶段决策确定后，就组成了一个决策序列，因此也就决定了整个过程的一条活动路线.这种把一个问题可看

2、作是一个前后关联具有链状结构的多阶段过程（如图7.1）就称为多阶段决策过程，也称序贯决策过程.这种问题就称为多阶段决策问题.在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前的状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义.因此，把处理它的方法称为动态规划方法.但是，一些与时间没有关系的静态规划（如线性规划、非线性规划等）问题，只要人为地引进“时间”因素，也可把它视为多阶段决策问题，用动态规划方法来处理.涉及到动态规划，总会有下面几个概念：7.1.1动态规划的基本概念（

3、１）阶段把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序求解.描述阶段的变量称为阶段变量，常用表示.阶段的划分，一般是根据时间和空间的自然特征来划分，但要便于把问题的过程能转化成为多阶段决策的过程.（２）状态状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题的状况，又称不可控因素.在最短路问题中，状态就是某阶段的出发位置.它既是该阶段某支路的起点，又是前一阶段某支路的终点.通常一个阶段有若干个状态（一般第一个阶段只有一个状态，它构成动态规划的递推方程的出口），每一个阶段的所有状态构成一个集合，叫做状态集合.

4、用一个变量来描述在第个阶段的状态集合上的取值，此变量称为状态变量（如7.2节中最短路问题中的，以及后面要介绍的背包问题、分割问题及设备更新问题中的参数）.这里所说的状态是具体的属于某阶段的，它应具备下面的性质：如果某阶段状态给定后，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响.换句话说，过程的过去历史只能通过当前的状态去影响它未来的发展，当前的状态是以往历史的总结.这个性质称为无后效性，也称马尔可夫（Markov）性.如果状态仅仅描述过程的具体特征，则并不是任何实际过程都能满足无后效性的要求.所以，在构造决策过程的动态规划模型时

5、，不能仅由描述过程的具体特征这点着眼去规定状态变量，而要充分注意到是否满足无后效性的要求.如果状态的某种规定方式可能导致不满足无后效性，则应适当地改变状态的规定方法，达到能使它满足无后效性的要求.（３）决策决策表示当过程处于某一阶段的某一状态时，可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策.在最优控制中也称为控制（只有它才是我们能够控制的）.描述决策的变量称为决策变量.它可以用一个数、一组数或一个向量来描述.常用表示第阶段当状态处于时的决策变量，它是状态或状态变量的函数（可能是向量值函数或多值函数）.在实际问题中

6、，决策变量的取值往往限制在某一范围之内，此范围称为允许决策集合.常用表示第阶段当状态处于出发的允许决策集合，显然有.例如，在最短路问题中，.（４）策略策略是一个按顺序排列的决策组成的集合.由过程的第阶段开始到终止状态为止的过程，称为问题的后部子过程.由每段的决策按顺序排列组成的决策函数序列称为子策略，记为当时，此决策函数序列即为一个策略.在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集合.从允许策略集合中找到达到最优效果的策略称为最优策略.（５）状态转移方程状态转移方程式确定过程有一个状态到另一个状态的演变过程.若给定第阶段

7、状态和该阶段的决策变量，则第阶段的状态也就完全确定.即的值随和的值变化而变化.这种确定的对应关系，记为，它描述了由第阶段到第阶段的状态转移规律，称为状态转移方程.称为状态转移函数.例如，在最短路问题中，状态转移方程为.（６）指标函数和最优值函数用来衡量所实现过程优劣的数量指标，称为指标函数.它是定义在全过程和所有后部子过程上确定的函数.对于要构成动态规划模型的指标函数，应具有可分性，并满足递推关系（详见文献［５］），在实际问题中，很多指标函数都满足此性质.指标函数的最优值，称为最优值函数.根据问题，取min或max之一.在动态规划模型中，

8、总会出现一个或一组递推关系，我们把它称为动态规划的基本方程.7.1.2动态规划方法的基本思想现将动态规划方法的基本思想归纳如下：一、动态规划方法的关键在于正确写出基本的递推关系式和恰当的边界条