动态规划课件

1、动态规划（DP）Dynamic Programming1 多阶段决策过程最优化问题（掌握）2 基本概念、基本方程与最优化原理 （掌握）3 动态规划应用（掌握）动态规划（DP）Dynamic Programming1 动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，可以把困难的多阶段决策问题变换成一系列互相联系较容易的单阶段问题，解决了这一系列较容易的单阶段问题，也就解决了这个困难的多阶段决策问题。 动态规划是用来解决多阶段决策过程最优化的一种每个阶段都要进行决策,目的是使整个过程的决策 达到最优效果。多阶段决策问题：是动态决策问题的一种特殊形式；在多阶段决策过程中,系统的动态

2、过程可以按照时间进程分为状态相互联系而又相互区别的各个阶段；每个阶段都要进行决策,目的是使整个过程的决策 需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。 需指出：动态规划是求解某类问题的一种方法，是考察问题的一种多阶段决策问题的典型例子： 1 . 生产决策问题：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。12n状态决策状态决策状态状态决策多阶段决策问题的典型例子：12n

3、状态决策状态决策状态状态决动态规划课件 2. 航天飞机飞行控制问题：由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和实现目的（如软着落问题）。 不包含时间因素的静态决策问题（本质上是一次决策问题）也可以适当地引入阶段的概念，作为多阶段的决策问题用动态规划方法来解决。 2. 航天飞机飞行控制问题：由于航天飞机的运动的环 3 . 最短路问题：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从A点到G点的最短距离（总费用最小）。123456AB1B2C1C2C3C4D1D2D3E1E2E3

4、F1F2G531368763685338422213335256643 3 . 最短路问题：给定一个交通网络图如下，其中两点动态规划课件动态规划课件2 基本概念、基本方程及最优化原理一、基本概念1、阶段（stage）指一个问题需要作出决策的步骤。通常按时间和空间的自然特征划分阶段。如例1是按距A点距离划分的阶段。2 基本概念、基本方程及最优化原理一、基本概念动态规划课件2、状态（state）-最关键参数指每个阶段初所处的自然状况或客观条件。它既反映前面各阶段决策的结局，又是本阶段作出决策的出发点和依据。通常第k个阶段的有若干个状态，用状态变量sk来描述。例1中某个阶段的状态就是所在的位置。通常

5、状态数比阶段数多1。2、状态（state）-最关键参数指每个阶段初所处的自然状3、决策（decision）指某一阶段内的抉择，通常用决策变量xk(sk)表示第k阶段状态是sk时所做的选择，这个决策决定了第k+1阶段的状态。如： x2(B1)=C2表示第2阶段处于状态B1时选择了由B1到C2，即以C2做终点。又如： x3(C1)=D23、决策（decision）指某一阶段内的抉择，通常用决策变4、策略（policy）由所有各阶段的决策组成的序列称为全过程策略，记作p1,n(s1)能够达到总体最优的策略叫做最优策略。从第k个阶段开始到最后阶段的决策组成序列称为k子过程策略简称K子策略（subpol

6、icy）。记作pk,n(sk)4、策略（policy）由所有各阶段的决策组成的序列称为全过动态规划课件动态规划课件5、指标函数指标函数和最优值函数：用来衡量所实现过程优劣的一种数量指标，为指标函数。指标函数的最优值，称为最优值函数，记作f1(s1)或fk(sk) 。在不同的问题中，指标函数的含义是不同的，它可能是距离、利润、成本、产量或资源消耗等。fk(sk)就是指对某一确定状态选取最优策略后得到的指标函数值，即对某一最优子策略的效益度量值。阶段指标函数：rk(sk,xk)表示在第k阶段的sk状态下做出xk决策时的指标值。5、指标函数指标函数和最优值函数：用来衡量所实现过程优劣的一6、状态转移

7、方程（状态转移率） 从sk的某一状态值出发，当决策变量 xk（sk）的取值决定后，下一阶段状态变量sk+1的取值也随之确定。这种从上一阶段的某状态值到下阶段某状态值的转移的规律称为状态转移率，又叫状态转移方程。sk+1=Tk(sk,xk)6、状态转移方程（状态转移率） 从sk的某一状态值出发，当图示：阶段kT(sk,xk)阶段k+1T(sk+1,xk+1)状态sk状态Sk+1状态Sk+2决策xk(sk)决策xk+1(sk+1)rk(sk,xk)rk+1(sk+1,xk+1)图示：阶段k状态状态状态决策xk(sk)决策rk(sk,xk二、基本方程二、基本方程三、最优化原理最优策略的性质：不管在此

8、最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。也就是说最优策略的任一个子策略也是最优的。三、最优化原理最优策略的性质：小结:方程 :状态转移方程概念 : 阶段变量k状态变量sk决策变量uk;指标: 动态规划本质上是多阶段决策过程; 效益指标函数形式: 和、积无后效性可递推小结:方程 :状态转移方程概念 : 阶段变量k状态变量sk解多阶段决策过程问题，求出 最优策略，即最优决策序列f1(s1) 最优路线，即执行最优策略时的状态序列 最优目标函数值从 k 到终点最优策略子策略的最优目标函数值解多阶段决策过程问题，求出 最优策略，即最优决策序列3 动态规划

9、的应用动态规划求解步骤：1、确定问题的阶段和编号2、确定状态变量 sk3、确定决策变量 xk（用 xk*表示该阶段的最优决策）4、确定状态转移方程5、确定指标函数3 动态规划的应用动态规划求解步骤：例1、从A 地到D 地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？ AB1B2C1C2C3D24333321114二、最短路径问题例1、从A 地到D 地要铺设一条煤气管道,其中需经过两级中间 解：整个计算过程分三个阶段，从最后一个阶段开始。 第三阶段（C D）： C 有三条路线到终点D 。 AB1B2C1C2C3D243333

10、21114DC1C2C3显然有 f3 (C1 ) = 1 ； f3(C2 ) = 3 ； f3 (C3 ) = 4 解：整个计算过程分三个阶段，从最后一个阶段开始。 第三阶 r( B1,C1 ) + f1 (C1 ) 3+1 f2 ( B1 ) = min r( B1,C2 ) + f1 (C2 ) = min 3+3 r( B1,C3 ) + f1 (C3 ) 1+4 4 = min 6 = 4 5第二阶段（B C）： B 到C 有六条路线。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为B1C1 D) 第二阶段（B C）： B 到C 有六条路线。A r( B

11、2,C1 ) + f1 (C1 ) 2+1 f2 ( B2 ) = min r( B2,C2 ) + f1 (C2 ) = min 3+3 r( B2,C3 ) + f1 (C3 ) 1+4 3 = min 6 = 3 5AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为B2C1 D) AB1B2C1C2C3D24333321114D第一阶段（ A B ）： A 到B 有二条路线。 f1(A)1 = r(A, B1 ) f2 ( B1 ) 246 f1 (A)2 = r(A, B2 ) f2 ( B2 ) 437 f1 (A) = min = min6,7=6r(

12、A, B1 ) f2 ( B1 )r(A, B2 ) f2 ( B2 )(最短路线为AB1C1 D)AB1B2C1C2C3D24333321114DC1C2C3B1B2A第一阶段（ A B ）： A 到B 有二条路线。 AB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路线为 AB1C1 D 路长为 6AB1B2C1C2C3D24333321114DC1C2C32511214106104131112396581052C1C3D1AB1B3B2D2EC2求从A到E的最短路径例：2511214106104131112396581052C1例2：资源分配问题 例2：资源分配问

13、题 解：将问题按工厂分为三个阶段，甲、乙、丙三厂分别编号为1，2，3。设sk=分配给第K个厂至第3个厂的设备台数（K=1，2，3）Xk=分配给第K个厂的设备台数。已知 s1=5 s2=s1-x1 s3=s2-x2解：将问题按工厂分为三个阶段，甲、乙、丙三厂分别编号为1，2以下我们从第三阶段开始计算：第三阶段显然将s3（s3=0,1,2,3,4,5）台设备都分配给第3工厂时，也就是s3=x3时，第3阶段的指标值为最大，以下我们从第三阶段开始计算：第三阶段（ s3=0,1,2,3,4,5 ） x3s3r3(s3,x3)f3(s3)x3*0123450123450461112120461112120

14、12345第三阶段（ s3=0,1,2,3,4,5 ） x3r第二阶段（ s2=0,1,2,3,4,5 ）台设备分配给第2工厂和第3工厂 x2s2r2(s2,x2)+ f3(s2-x2)f2(s2)x2*0123450123450+00+40+60+110+120+125+05+45+65+115+1210+010+410+610+1111+011+411+611+011+411+0051014162101221,22第二阶段（ s2=0,1,2,3,4,5 ）台设备分配给第2第一阶段（s1=5） x1s1r1(5,x1)+ f2(5-x1)f1(x)x1*01234550+213+167+1

15、49+1012+513+0210,2 x2s2f2(s2)x2*012345051014162101221,22第一阶段（s1=5） x1r1(5,x1)+ f2(第一阶段（s1=5） x3s3r1(5,x1)+ f2(5-x1)f1(x)x1*01234550+213+167+149+1912+513+0210,2最优分配方案有两个：（1）由于x1*=0，根据s2=s1- x1*=5，可知x2*=2，可求得x3*=3。即分配给甲厂0台，乙厂2台，丙厂3台。（2）由于x1*=2，根据s2=s1- x1*=3，可知x2*=2，可求得x3*=1。即分配给甲厂2台，乙厂2台，丙厂1台。第一阶段（s1

16、=5） x3r1(5,x1)+ f2(动态规划课件例3：某公司拟将400万元，向A、B、C三个项目追加投资，三个项目可以有不同的投资额度，相应的效益值如表所示，问如何分配资金，才使总效益值最大？0 1 2 3 4ABC47 51 59 71 7649 52 61 71 7846 70 76 88 88例3：某公司拟将400万元，向A、B、C三个项目追加投资，三将问题按项目分为三个阶段：A、B、C分别编号为1，2，3。设sk分配给第k项目至第3个项目可供分配的资金数。 xk分配给第k个项目的资金数。 s1=4（百万） sk+1 = sk - xk s3= x3s3 = s2 x2将问题按项目分为

17、三个阶段：A、B、C分别编号为1，2，3。第3阶段： s3=0,1,2,3,4 x3s3r3(s3,x3)+ f4(s3-x3)f3(s3)x3*01234012344670768888467076888801234第3阶段： s3=0,1,2,3,4 x3r3(s3第2阶段： s2=0,1,2,3,4 x2s2r2(s2,x2)+ f3(s2-x2)f2(s2)x2*012340123449+4649+7049+7649+8849+8852+4652+7052+7652+8861+4661+7061+7671+4671+7078+469511912513714100003第2阶段： s2=0

18、,1,2,3,4 x2r2(s2,第2阶段： s2=0,1,2,3,4 x2s2r2(s2,x2)+ f3(s2-x2)f2(s2)x2*012340123449+049+7049+7649+8849+8852+052+7052+7652+8861+061+7061+7671+071+7078+0011912513714100023第2阶段： s2=0,1,2,3,4 x2r2(s2,第1阶段： s1=4 x1s1r1(s1,x1)+ f2(s1-x1)f1(s1)x1*012344结论：（1）由于x1*=0，根据s2=s1- x1*=4，可知x2*=3，可求得x3*=1。最优策略：分配给A 0万B 300万C 100万 最优值：188第1阶段： s1=4 x1r1(s1,x1)+ f2(第1阶段： s1=4 x1s1r1(s1,x1)+ f2(s1-x1)f1(s1)x1*01234447+14151+13759+12571+11976+