《第七章 动态规划方法建模Word版》由会员分享，可在线阅读，更多相关《第七章 动态规划方法建模Word版（24页珍藏版）》请在金锄头文库上搜索。
1、第七章 动态规划方法建模动态规划是由理查德贝尔曼（Richard Bellman）所建立的，它是解最优化问题的一个特殊“技术”.我们这里用“技术”，是因为动态规划不是一个或一种特殊算法.7.1 动态规划的基本概念在生产和科学实验中，有一类活动的过程，由于它的特殊性，可将过程分为若干个互相联系的阶段，在它的每一个阶段都需要作出决策，从而使整个过程达到最好的活动效果.因此，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展.当各个阶段决策确定后，就组成了一个决策序列，因此也就决定了整个过程的一条活动路线.这种把一个问题可看作是一个前后关联具有链状结构的多阶段过程（如图7.1
2、）就称为多阶段决策过程，也称序贯决策过程.这种问题就称为多阶段决策问题.在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前的状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义.因此，把处理它的方法称为动态规划方法.但是，一些与时间没有关系的静态规划（如线性规划、非线性规划等）问题，只要人为地引进“时间”因素，也可把它视为多阶段决策问题，用动态规划方法来处理.涉及到动态规划，总会有下面几个概念：7.1.1 动态规划的基本概念（）阶段把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序求解.描述阶段的变量称为阶段变量
3、，常用表示.阶段的划分，一般是根据时间和空间的自然特征来划分，但要便于把问题的过程能转化成为多阶段决策的过程.（）状态状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题的状况，又称不可控因素.在最短路问题中，状态就是某阶段的出发位置.它既是该阶段某支路的起点，又是前一阶段某支路的终点.通常一个阶段有若干个状态（一般第一个阶段只有一个状态，它构成动态规划的递推方程的出口），每一个阶段的所有状态构成一个集合，叫做状态集合.用一个变量来描述在第个阶段的状态集合上的取值，此变量称为状态变量（如7.2节中最短路问题中的，以及后面要介绍的背包问题、分割问题及设备更新问题中的参数）.这里所说的状
4、态是具体的属于某阶段的，它应具备下面的性质：如果某阶段状态给定后，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响.换句话说，过程的过去历史只能通过当前的状态去影响它未来的发展，当前的状态是以往历史的总结.这个性质称为无后效性，也称马尔可夫（Markov）性.如果状态仅仅描述过程的具体特征，则并不是任何实际过程都能满足无后效性的要求.所以，在构造决策过程的动态规划模型时，不能仅由描述过程的具体特征这点着眼去规定状态变量，而要充分注意到是否满足无后效性的要求.如果状态的某种规定方式可能导致不满足无后效性，则应适当地改变状态的规定方法，达到能使它满足无后效性的要求.（）决策决策表示当过程处于
5、某一阶段的某一状态时，可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策.在最优控制中也称为控制（只有它才是我们能够控制的）.描述决策的变量称为决策变量.它可以用一个数、一组数或一个向量来描述.常用表示第阶段当状态处于时的决策变量，它是状态或状态变量的函数（可能是向量值函数或多值函数）.在实际问题中，决策变量的取值往往限制在某一范围之内，此范围称为允许决策集合.常用表示第阶段当状态处于出发的允许决策集合，显然有.例如，在最短路问题中，.（）策略策略是一个按顺序排列的决策组成的集合.由过程的第阶段开始到终止状态为止的过程，称为问题的后部子过程.由每段的决策按顺序排列组成的决策
6、函数序列称为子策略，记为当时，此决策函数序列即为一个策略.在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集合.从允许策略集合中找到达到最优效果的策略称为最优策略.（）状态转移方程状态转移方程式确定过程有一个状态到另一个状态的演变过程.若给定第阶段状态和该阶段的决策变量，则第阶段的状态也就完全确定.即的值随和的值变化而变化.这种确定的对应关系，记为，它描述了由第阶段到第阶段的状态转移规律，称为状态转移方程.称为状态转移函数.例如，在最短路问题中，状态转移方程为.（）指标函数和最优值函数用来衡量所实现过程优劣的数量指标，称为指标函数.它是定义在全过程和所有后部子过程上确定的函数.对于
7、要构成动态规划模型的指标函数，应具有可分性，并满足递推关系（详见文献），在实际问题中，很多指标函数都满足此性质.指标函数的最优值，称为最优值函数.根据问题，取min或max之一.在动态规划模型中，总会出现一个或一组递推关系，我们把它称为动态规划的基本方程.7.1.2 动态规划方法的基本思想现将动态规划方法的基本思想归纳如下：一、动态规划方法的关键在于正确写出基本的递推关系式和恰当的边界条件（基本方程）.要做到这一点，必须先将问题的整个过程分成几个相互联系的阶段，恰当地选取状态变量和决策变量及定义最优值函数，从而把一个大问题化成一族同类型的子问题，然后逐个求解.即从边界条件开始，逐段递推寻优，在
8、每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解.二、在多阶段决策过程中，动态规划方法是既把当前一段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法.因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的.三、在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐次变换得到，从而确定了最优策略.动态规划的理论基础叫做动态规划的最优化原理，它是这样描述的：作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面决策所形成的
9、状态而言，余下的诸决策必须构成最优策略.简言之，一个最优策略的子策略总是最优的.动态规划的优劣：优点：（1）易于确定全局最优解.因为它求解的全是一维问题，所以容易确定.（2）能得到一族（全部的）最优解，有利于分析结果.（3）能利用经验，提高求解效率.缺点：（1）到目前为止，没有一个统一的标准模型可供应用.由于问题的不同，有时要将问题转化成满足条件（无后效性、目标函数的可分性）的多阶段决策过程是非常困难的，需要丰富的想象力和灵活的技巧.（2）应用的局限性.“无后效性”条件的限制，降低了动态规划的通用性.（3）在数值计算时，存在所谓的“维数灾难”.当阶段数目较多且每一阶段的允许状态也较多时，计算成
10、本变得非常昂贵，有时使得计算不可能进行下去.在二维或三维动态规划中，问题显得更加突出.7.2 最短路问题问题：某人想进行一次旅行.他住在城市1，而希望到达城市10，见图7.2.这是一次长途的旅行，而且他还必须进行三次中间停留.对他旅行中的三个中间停留站的每一站，都有两到三个不同的城市可供他选择.选择不同的中间站，旅行的花费是不同的.两城市之间的花费以及连接示于图7.2中.由于他希望为这次旅行付出的总花费达到最小，他将确定哪些城市作为他的中间站，显然，它可以用枚举法来解决此问题，总的可能的路线有18条（33218）.但问题肯定有更好的解法，下面我们用更好的方法来解决此问题.我们从终点（城市10）
11、逆序来分析这个问题.第一步：若我们处在第3站，可通过城市8或城市9到达城市10.可用表7.2.1（1）说明： 表7.2.1（1）城市最小花费路径第3站89380280810910第二步：现在假设在第2站，并问哪一条是到达城市10且花费最小的路径.若在城市5，最小花费是510，即（210380，230280）中的最小值，将选用路径5910.同理，若在城市6，最小花费是660，即（350380，380280）中的最小值，将选择路径6910.此结果列于表7.2.1（2）中.表7.2.1（2）城市最小花费路径第2站567510660670591069107810第三步：假定处在第1站.用类似于第2站的
12、分析方法进行分析，例如，由城市2到达城市10的最小花费是830min（320510，350660，400670）括号中和式的第一项是由城市2到城市5、6、7的花费，第二项是城市5、6、7到城市10的最小花费，它可由表31（2）查到，最小花费路径是25910.第1站的所有计算结果有表7.2.1（3）给出.表7.2.1（3）城市最小花费路径第1站234830860810259103591045910第四步：假设处在城市1，这是起点.必须由城市1到城市2、3、4中的一个.最小花费的路径是那一条呢？应用表7.2.1（3）的结果和由城市1到城市2、3、4的花费，则可计算出全旅程的最小花费为： min（3
13、00830，200860，350810）min（1130，1060，1160）1060最小花费路径是：135910.上面的解决非常简单.它是基于这样的思考：不论现在处于那一个城市，从最后一个城市开始，将总是选择最优（最小花费）的路径.若在城市10（第4站），就留在那里.若在城市5（第3站），则从城市8或9到达城市10.如此继续下去，直到发现自己在城市1（第0站），并且顺序地找到了最小花费的解，以及实现最小花费的路径.应当注意，即使没有达到第0站，最优解将是什么样，也是清楚的.我们注意到，在第1站，最小费用将是由城市3到城市10的最小费用加上200.另外，如果他改变了他的愿望，并决定从任何其它城
14、市起始，我们也知道最优解是什么.上面的解法虽然简单，但它却富有启发性.一方面，在计算过程中，我们使用了已经计算出的数据，这大大的节约了计算成本；另一方面，我们得到了比我们预期多得多的信息，我们不仅仅解得了从城市1（起点）到城市10的最小费用路径，而且还得到了其它任何一个城市到达城市10的最小费用路径.显然，如果在原问题的旅行图前又增添了一些新的城市，我们已经计算出的数据仍然可以利用，并且进一步的计算不会比上面的计算更复杂.下面我们将上面的解法步骤用符号表示，以期望得到更一般的形式.用符号()表示10个城市.表示城市到城市的距离.如果城市到城市必须经过其它城市，则.于是所有数据构成一个矩阵，即为
15、用表示第站所有城市构成的集合.即，.用表示从第站的城市到目的地的最小费用值.于是上面的解题过程可由下面的递推公式完成： (7.2.1)当然，在每步极小化时，应记住极小值点，这样才能确定最小费用路径.显然，根据对称性，你还可以使用“顺推法”.与之对应，上面的过程称为“逆推法”.7.3 背包问题问题：有人在某地旅游结束后，决定购买一些“特产”，打算带回家，再卖给他的一些同事，指望得到一笔诚实无欺的利润.他知道在他的行李中最多只能带20，才不会超重.他可以购买四种不同类型的特产，其特征如见表7.3.1.表7.3.1项目重量（）估计利润（元）12342354110160260210由于这些项目不可能分割包装，这就限制了只能取其整数倍.根据第六章，此问题可以用整数线性规划来描述.设，表示准备带回家的各种特产的数量，则问题变为求解 (7.3.1) (7.3.2)下面我们将用动态规划技
