第8章 动态规划.ppt

1、主要内容： 7.1多阶段决策问题7.2动态规划的基本概念和原理7.3动态规划的应用实例，例如，分阶段求解最短路径，C1 T3-: B1 C1 T4-:a2b1c 1t 7-:qa2 B1 c 11q-a3b1 c 1t 1q-a3b2c 2t 11，最短路径，-多阶段决策问题2。在整个过程的最短路径中，会有各阶段的最优路径；-递归3。确定前端点，确定后端路径，与前端路径无关(如何找到该端点)；动态规划，7.1多阶段决策问题。动态规划是一种求解多阶段最优决策的方法，由美国数学家贝尔曼于1951年首次提出；1957年，伯曼出版了第一本关于动态规划的专著，这标志着运筹学的一个新分支的建立。动态规划将

2、复杂的多阶段决策问题分解成一系列简单离散的单阶段决策问题，并采用顺序解法通过解决一系列小问题来解决整个问题；动态规划的每个决策阶段不仅要考虑该阶段的决策目标，还要考虑整个决策过程的总体目标，从而实现总体最优决策。动态规划的分类是：离散确定离散随机连续确定连续随机，动态规划的特征是3360。动态规划没有精确的数学表达式和精确的算法。它强调对具体问题的具体分析，并依赖于分析师的经验和技能。它与运筹学的其他方法有很好的互补关系，特别是在处理非线性和离散问题时。一般来说，多阶段决策过程的发展是通过一系列的状态转换来实现的。一般来说，一个系统在某一阶段的状态转换不仅与该阶段的状态和决策有关，还与系统过去

3、的状态和决策有关。因此，解决这个问题既困难又复杂。然而，这只是一个特殊的多阶段决策问题，适合用动态规划方法来解决，即“无后效”的多阶段决策过程。所谓无后效性，也称马尔可夫性，是指系统从某一阶段发展到未来，它只由这一阶段的状态及其未来的决策决定，与系统以前的状态和决策(历史)无关。无后效的多阶段决策过程的特征是系统的过去历史，它只能通过当前状态影响系统的未来，当前状态是后过程发展的初始条件。动态规划的应用广泛应用于工程技术、企业管理和军事部门；它可以解决资源分配、生产调度、库存管理、路径优化、设备更新、投资规划、生产过程调度和优化控制等问题；用动态规划方法解决决策问题，首先必须将问题转化为满足动

4、态规划要求的形式，这涉及到以下概念： (1)阶段(2)状态(3)决策和策略(4)状态转移方程(5)指标函数(6)基本方程，7.2动态规划的基本概念和基本思想，1 .基本概念，1 .将阶段分成复杂的一个阶段变量描述当前阶段的位置，通常用下标k表示；每一个阶段都有几个状态，它们代表了某一决策阶段所面临的条件或位置以及运动特征的数量，称为状态。反映状态变化的量称为状态变量。k级的状态特征可以用状态变量sk来描述；每个阶段的所有状态构成这个阶段的状态集Sk，并且有skSk。每个阶段的状态可以分为初始状态和结束状态，或者输入状态和输出状态。每个阶段的初始状态表示为sk，结束状态表示为sk 1，这也是下一

5、阶段的初始状态。，(2)确定状态，(3)决策，决策变量，所谓决策就是确定系统过程的发展计划，决策的实质是关于状态的选择，是决策者从一个给定的状态阶段到下一个状态阶段的选择。用来描述决策变化量的称为决策变量和状态变量，决策变量可以用一个数来描述，一组数或一个向量也可以是状态变量的函数，记住，用K阶段状态sk表示的决策变量，决策变量的值往往有一定的允许范围，称为允许决策集决策变量xk(sk)允许决策集用XK(SK)表示， XK (SK) (4)策略和允许策略集，策略也称为决策序列策略，它可以分为全过程策略和K个子策略。 全过程策略是指有N个阶段的全过程，是由N个阶段的决策依次组成的决策序列。从第k

6、阶段到第n阶段，由连续阶段决策形成的决策序列称为k个子策略，这意味着当k=1时，k个子策略显然是整个过程策略。(5)确定从一个状态到另一个状态的转变过程的状态转变方程，用状态转变方程描述： sk 1=T (sk，xk)；在大多数情况下，状态转移方程可以用数学公式表示，如： sk1=skxk(6)指数函数是用来衡量战略或子战略或决策效果的量化指标，称为指数函数。它是在整个过程或子过程或阶段中定义的一个确定的数量函数。对于不同的问题，指标函数可以是成本、成本、产值、利润、产量、消耗、距离、时间、效用等。当第k个段处于状态sk且决策为xk时，以vk(sk，xk)作为索引，则它是第k个段索引函数，缩写

7、为vk。用f(sk，xk)表示第k个子过程的指数函数。它表示在第k个sk状态下决策为xk时从sk到终点的距离。因此，f(sk，xk)不仅与当前状态sk相关，(2)过程指标函数(也称为目标函数)，(1)阶段指标函数(也称为阶段效应)，还与子过程策略pk(sk)相关，严格来说应该表示为fk(sk，pk(sk)。它是由每个阶段的阶段索引函数vk(sk，xk)的累积形成的。K个子过程的指数函数可以表示为：其中，一些运算可以加、减、乘、除、导等。在多阶段决策问题中，一个常见的目标函数是每个阶段的效果之和，即：存在一些问题，例如系统可靠性。目标函数的形式是各阶段效应的乘积，(7)最优解。fk* (sk)用

8、于表示在状态sk，即：时，kth子过程的索引函数fk(sk，pk(sk)的最佳值，Fk(sk)称为kth子过程的最佳索引函数。相应的子策略pk(sk)被称为状态sk中的最优子策略，它被记录为pk*(sk)。例如，最短路径问题是通过动态规划解决的。最短路径求解阶段：可分为四个阶段，k=1，4。州：可以使用城市编号，S1=Q，S2=A1，A2，A3，S3=B1，B2，B3，S4=C1，C2，S5=T。决策变量也可以使用城市编号。状态转移方程： sk 1=xk阶段索引函数：过程索引(阶段递归)函数：k=4f4 (C1)=3，F4(C2)=4k=3 F3(B1)=min 1 F4(C1)=4 *，4

9、F4(C2)=8=4f3 (B2)=min 6 F4(C1)=3 F4(C2)=7 *=7 F3(B3)=min 3 F4(C1)=6 *，3 f4(C2)=7=6 k=2 f2(A1)=min7 f3(B1)，4 F3(B2)，6 F3(F3) 1 f3(B2)，5 F3(B3)=min 8*，8 *，11=8 k=1 f1(Q)=min2 f2(A1)，4 f2(A2)，最短路径3 f2(A3)=min13，11*，11*=11是：Q A2 B1 C1 T，p=A2，B1，C1，T Q A3 B1 C1 T，p=A3，B1，C1，T Q A3 B2 C2 T，p=A3，B2，C2，T，整个

10、过程的最优策略应该如下其次，动态规划的最优性原则。在一个例子中，求解最短路径的公式可以概括为：其中，vk表示由决策xk确定的从状态sk到状态sk 1的距离。F5(s5)=0是一个边界条件，表示整个过程在第四阶段结束时结束。一般来说，对于n阶段的决策过程，假设只有指标函数是“和”和“积”的形式，第k阶段和第k-1阶段之间的递推公式可以表示为：当过程指标函数是下面的“和”形式时，对应的基本函数方程为：当过程指标函数是下面的“积”形式时，对应的基本函数方程为3360。很容易找到全局最优解；可以得到一组解；动态规划的缺点：没有标准的应用模型，模型的构建依赖于个人的经验和技能；状态变量需要满足无后效的要

11、求，这有很大的局限性；7.3应用动态规划方法，动态规划的步骤：1 .将问题分成在时间或空间上满足递归关系的几个阶段，人为地引入非时间序列问题的“时间段”概念；2.正确选择状态变量sk，满足：可知性，正确描述动态过程演化，直接或间接确定状态变量的值；无后效：背后的决定与之前的决定无关；3。确定决策变量xk和允许决策集Xk；4.写出状态转移方程sk 1=T (sk，xk)；5.决策变量的取值范围6。写出过程指标函数(阶段函数)的递归关系，它应满足： a)是在所有阶段定义的定量函数的要求；b)具有可分性，满足递归关系；c)舞台功能应严格单调。动态编程应用示例：1。最优路径问题2。资源分配问题3。生产

12、和库存问题4。机器负载分配问题5。复合系统工作可靠性问题6。二维背包问题7。设备更新问题推销员问题非线性规划解1。最优路径问题，一个工厂应该在未来五年内确定一个新产品的价格，并且已经提出只在5元、6元、7元和8元四个单价中执行。预计在未来五年内不同价格下的年利润(万元)如下表所示，但是每个相邻年份的价格增减不得超过1元。询问未来五年的年度定价，但总利润将是七五年多来最大的。13、14、11、8、4、3、4、10、18、22、23、17、24、28、28、30、37、35、36、38、解决方案：1。建立动态规划模型：阶段：如果状态变量sk是每个阶段开始时的价格，SK=5，6，7，8；如果决策变量

13、xk是每年确定的价格，那么xk=5，6，7，8；状态转移方程：阶段指数函数vk(sk，xk)为每个阶段选择xk获得的利润；例如，v(sk)的过程指数函数是当状态为sk时从第k阶段到最后阶段的总利润。基本函数的方程是：逆解：k=5f5 (S5，X5) V5 (S5，X5)F6 *(S6)F5 *(S5)X5 * s x 567 85 08 56 40 67 303 78 404 8，k=4f4 (S4， x4)v4 x4)F5 *(S5)F4 *(S4)x4 * s x 5 6 7 8 5 8 5 4 13 5 6 8 6 4 6 3 14 5 7 4 7 3 7 4 11 6，8 6 3 6

14、4 10 7，k=3 f3(s3，x3) v3(s3， x3)F4 *(S4)F3 *(S3)x3 * s 5 x 6 7 8 5 4 13 4 14 18 6 8 13 8 14 8 11 22 7 9 14 9 11 9 10 23 6 8 6 11 6 10 17 7、k=2 f2(s2，x2) v2(s2， x2)F3 *(S3)F2 *(S2)x2 * s 5 6 7 8 5 2 18 2 22 24 6 5 18 5 22 5 23 28 7 5 22 5 23 5 17 28 7 8 7 23 7 17 30 7、k=1 f1(s1，x1) v1(s1， x1)F2 *(S2)f1 *(S1)x1 * s 5 x 6 7 8 5 9 24 9 28 37 6 7 24 7 28 7 28 35 6，7 7 6 28 6 28 6 30 36 8 8 28 8 30 38 8、S1=8 x1=8 S2=8 X2=7 S3=7X 3=6 S4=6X 4=5 S5=5X 5=5、2。 资源分配问题，即如何将有限的资源分配给几种生产活动，并使资源利用的效益最大化，是经济活动中常见的问题。动态规划可以解决一些线性规划无法解决的问题。一般的资源分配问题可以描述为以下规划问题：max: