动态规划课件.ppt

1、动态规划（动态规划（DPDP）Dynamic ProgrammingDynamic Programming1 多阶段决策过程最优化问题（掌握）多阶段决策过程最优化问题（掌握）2 基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理 （掌握）（掌握）3 动态规划应用（掌握）动态规划应用（掌握）动态规划是用来解决多阶段决策过程最优动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，可以把困难化的一种数量方法。其特点在于，可以把困难的多阶段决策问题变换成一系列互相联系较容的多阶段决策问题变换成一系列互相联系较容易的单阶段问题，解决了这一系列较容易的单易的单阶段问题，解决了这一系

2、列较容易的单阶段问题，也就解决了这个困难的多阶段决策阶段问题，也就解决了这个困难的多阶段决策问题。问题。每个阶段都要进行每个阶段都要进行决策决策,目的是使整个过程的决策目的是使整个过程的决策 达到最优效果。达到最优效果。多阶段决策问题：多阶段决策问题：是动态决策问题的一种特殊形式；是动态决策问题的一种特殊形式；在多阶段决策过程中在多阶段决策过程中,系统的动态过程可以按照时间系统的动态过程可以按照时间进程分为进程分为状态状态相互相互联系联系而又相互而又相互区别区别的各个的各个阶段阶段；需指出：动态规划是求解某类问题的一种方法，需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是

3、一种算法。必是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态原理和方法，建立相应的模型，然后再用动态规划方法去求解。规划方法去求解。多阶段决策问题的典型例子：多阶段决策问题的典型例子：1.1.生产决策问题生产决策问题：企业在生产过程：企业在生产过程中，由于需求是随时间变化的，因此企中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地在整个生产过程中逐月或逐季度地根据根据库存和需求决定生产计划。库存和需求决

4、定生产计划。12n状态状态决策决策状态状态决策决策状态状态状态状态决策决策 2.2.航天飞机飞行控制问题：由于航天航天飞机飞行控制问题：由于航天飞机的运动的环境是不断变化的，因此就要飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和实现目的（如软着态），使之能最省燃料和实现目的（如软着落问题）。落问题）。不包含时间因素的静态决策问题（本质不包含时间因素的静态决策问题（本质上是一次决策问题）也可以适当地引入阶段上是一次决策问题）也可以适当地

5、引入阶段的概念，作为多阶段的决策问题用动态规划的概念，作为多阶段的决策问题用动态规划方法来解决。方法来解决。3.最短路问题最短路问题：给定一个交通网络图如下，：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试其中两点之间的数字表示距离（或花费），试求从求从A点到点到G点的最短距离（总费用最小）。点的最短距离（总费用最小）。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687636853384222133352566432 基基本概念本概念、基本方程及最优化原理、基本方程及最优化原理一、基本概念一、基本概念1、阶段（、阶段（stage）指一个问题

6、需要作出决策的步骤。通常指一个问题需要作出决策的步骤。通常按时间和空间的自然特征划分阶段。按时间和空间的自然特征划分阶段。如例如例1是按距是按距A点距离划分的阶段。点距离划分的阶段。2、状态（、状态（state）-最关键参数最关键参数n指每个阶段初所处的自然状况或客观指每个阶段初所处的自然状况或客观条件。条件。n它既反映前面各阶段决策的结局，又它既反映前面各阶段决策的结局，又是本阶段作出决策的出发点和依据。是本阶段作出决策的出发点和依据。n通常第通常第k个阶段的有若干个状态，用个阶段的有若干个状态，用状态变量状态变量sk来描述。来描述。例例1中某个阶段的状态就是所在的位置。中某个阶段的状态就是

7、所在的位置。通常状态数比阶段数多通常状态数比阶段数多1。3、决策（、决策（decision）指某一阶段内的抉择，通常用决策变量指某一阶段内的抉择，通常用决策变量xk(sk)表示第表示第k阶段状态是阶段状态是sk时所做的时所做的选择，这个决策决定了第选择，这个决策决定了第k+1阶段的阶段的状态。状态。如：如：x2(B1)=C2表示第表示第2阶段处于状态阶段处于状态B1时选择了由时选择了由B1到到C2，即以，即以C2做终点。做终点。又如：又如：x3(C1)=D24、策略（、策略（policy）n由所有各阶段的决策组成的序列称为由所有各阶段的决策组成的序列称为全过程策略全过程策略，记作，记作p1,n

8、(s1)n能够达到总体最优的策略叫做能够达到总体最优的策略叫做最优策最优策略略。n从第从第k个阶段开始到最后阶段的决策个阶段开始到最后阶段的决策组成序列称为组成序列称为k子过程策略简称子过程策略简称K子策子策略（略（subpolicy）。记作。记作pk,n(sk)5、指标函数、指标函数n指标函数和最优值函数：用来衡量所实现指标函数和最优值函数：用来衡量所实现过程优劣的一种数量指标，为过程优劣的一种数量指标，为指标函数指标函数。指标函数的最优值，称为指标函数的最优值，称为最优值函数最优值函数，记记作作f1(s1)或或fk(sk)。在不同的问题中，指标函。在不同的问题中，指标函数的含义是不同的，它

9、可能是距离、利润、数的含义是不同的，它可能是距离、利润、成本、产量或资源消耗等。成本、产量或资源消耗等。nfk(sk)就是指对某一确定状态选取最优策略就是指对某一确定状态选取最优策略后得到的指标函数值，即对某一最优子策后得到的指标函数值，即对某一最优子策略的效益度量值。略的效益度量值。n阶段指标函数阶段指标函数：rk(sk,xk)表示在第表示在第k阶段的阶段的sk状态下做出状态下做出xk决策时的指标值。决策时的指标值。6、状态转移方程（状态转移率）、状态转移方程（状态转移率）从从sk的某一状态值出发，当决策变量的某一状态值出发，当决策变量 xk（sk）的取值决定后，下一阶段状态）的取值决定后，

10、下一阶段状态变量变量sk+1的取值也随之确定。这种从上的取值也随之确定。这种从上一阶段的某状态值到下阶段某状态值一阶段的某状态值到下阶段某状态值的转移的规律称为状态转移率，又叫的转移的规律称为状态转移率，又叫状态转移方程状态转移方程。sk+1=Tk(sk,xk)图示：图示：阶段阶段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)二、基本方程二、基本方程0)(,1,2,1),(),()(0)(1,2,1,),(),()(00111111sfnnksf

11、xsroptsfsfnnksfxsroptsfkkkkkkknnkkkkkkk始点条件顺序算法终点条件逆序算法三、最优化原理三、最优化原理最优策略的性质：最优策略的性质：不管在此最优策略上的某个状态以前的不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以状态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。后的所有决策必定构成最优子策略。也就是说最优策略的任一个子策略也也就是说最优策略的任一个子策略也是最优的。是最优的。小结小结:),()(1,susVoptsfnkknkkkuunk),(,111,1nkknkkkksusVus方程方程 :状态转移方程状态转移方程),

12、(1kkkkusTs概念概念 :阶段变量阶段变量k k状态变量状态变量s sk k决策变量决策变量u uk k;指标指标:),(111,nkkkknknksususVV动态规划本质上是多阶段决策过程动态规划本质上是多阶段决策过程;效益效益指标函数形式指标函数形式:和、和、积积无后效性无后效性),(111,nkkkknksususV可递推可递推,*2*1nuuu,*2*1nsss解多阶段决策过程问题，求出解多阶段决策过程问题，求出 最优策略最优策略，即最优，即最优决策序列决策序列 susvoptsfnkknkkkuunk1,f1(s1)最优路线最优路线，即执行最优策略时的即执行最优策略时的状态序

13、列状态序列 最优目标函数值最优目标函数值),(*1*1*,1*,1nnnnususVV从从 k 到终点最优策略到终点最优策略子策略的最优目标函数值子策略的最优目标函数值3 动态规划的应用动态规划的应用动态规划求解步骤：动态规划求解步骤：1、确定问题的阶段和编号、确定问题的阶段和编号2、确定状态变量、确定状态变量 sk3、确定决策变量、确定决策变量 xk（用（用 xk*表示该阶段的最表示该阶段的最优决策）优决策）4、确定状态转移方程、确定状态转移方程5、确定指标函数、确定指标函数例例1、从、从A 地到地到D 地要铺设一条煤气管道地要铺设一条煤气管道,其中需经过两其中需经过两级中间站，两点之间的连

14、线上的数字表示距离，如图级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？所示。问应该选择什么路线，使总距离最短？AB1B2C1C2C3D24333321114二、最短路径问题二、最短路径问题 解：整个计算过程分三个阶段，从最后一个阶段开始。解：整个计算过程分三个阶段，从最后一个阶段开始。第三阶段（第三阶段（C D）：）：C 有三条路线到终点有三条路线到终点D。AB1B2C1C2C3D24333321114DC1C2C3显然有显然有 f3(C1)=1 ；f3(C2)=3 ；f3(C3)=4 r(B1,C1)+f1(C1)3+1 f2(B1)=min r(B1

15、,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)r(B2,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)第一阶段（第一阶段（A B）：）：A 到到B

16、有二条路线。有二条路线。f1(A)1=r(A,B1)f2(B1)246 f1(A)2=r(A,B2)f2(B2)437 f1(A)=min =min6,7=6r(A,B1)f2(B1)r(A,B2)f2(B2)(最短路线为最短路线为AB1C1 D)AB1B2C1C2C3D24333321114DC1C2C3B1B2AAB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路线为最短路线为 AB1C1 D 路长为路长为 62511214106104131112396581052C1C3D1AB1B3B2D2EC2求从求从A A到到E E的最短路径的最短路径例：例：例例2：资源分

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

18、标值为最大，第三阶段（第三阶段（s3=0,1,2,3,4,5）x3s3r3(s3,x3)f3(s3)x3*012345012345046111212046111212012345第二阶段（第二阶段（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第一阶段第一阶段（s1=5）x

19、1s1r1(5,x1)+f2(5-x1)f1(x)x1*01234550+21 3+16 7+14 9+10 12+513+0210,2 x2s2f2(s2)x2*012345051014162101221,22第一阶段第一阶段（s1=5）x3s3r1(5,x1)+f2(5-x1)f1(x)x1*01234550+21 3+16 7+14 9+1912+513+0210,2最优分配方案有两个：最优分配方案有两个：（1）由于）由于x1*=0，根据，根据s2=s1-x1*=5，可知，可知x2*=2，可，可求得求得x3*=3。即分配给甲厂。即分配给甲厂0台，乙厂台，乙厂2台，丙厂台，丙厂3台。台。（

20、2）由于）由于x1*=2，根据，根据s2=s1-x1*=3，可知，可知x2*=2，可，可求得求得x3*=1。即分配给甲厂。即分配给甲厂2台，乙厂台，乙厂2台，丙厂台，丙厂1台。台。0 1 2 3 4ABC47 51 59 71 7649 52 61 71 7846 70 76 88 88n将问题按项目分为三个阶段：将问题按项目分为三个阶段：A、B、C分别编号为分别编号为1，2，3。n设设sk分配给第分配给第k项目至第项目至第3个项目可个项目可供分配的资金数。供分配的资金数。xk分配给第分配给第k个项目的资金数。个项目的资金数。s1=4（百万）（百万）sk+1=sk-xk s3=x3s3=s2

21、x2第第3阶段：阶段：s3=0,1,2,3,4 x3s3r3(s3,x3)+f4(s3-x3)f3(s3)x3*01234012344670768888467076888801234第第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+70 78+469511912513714100003第第2阶段：阶段：s2=0,1,2,3,4 x2s2r2(s2,x2)+f3(s2-x2)f2(s2

22、)x2*012340123449+049+7049+7649+8849+8852+052+7052+7652+8861+061+7061+7671+071+70 78+0011912513714100023第第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 0A 0万万B 300B 300万万C 100C 100万万 最优值：最优值：188188第第1阶段：阶段：s1=4 x1s1r1(

23、s1,x1)+f2(s1-x1)f1(s1)x1*01234447+14151+13759+12571+119 76+951903（1）由于）由于x1*=3，根据，根据s2=s1-x1*=1，可知，可知x2*=0，可求得，可求得x3*=1。最优策略：分配给最优策略：分配给A 300A 300万万 B 0B 0万万 C 100C 100万万 最优值：最优值：190190第第1阶段：阶段：s1=4 x1s1r1(s1,x1)+f2(s1-x1)f1(s1)x1*01234447+14151+13159+122 71+70 76+01880（1）由于）由于x1*=0，根据，根据s2=s1-x1*=4

24、，可知，可知x2*=3，可求得，可求得x3*=1。最优策略：分配给最优策略：分配给A 0A 0万万B 300B 300万万C 100C 100万万 最优值：最优值：1881882511214106104131112396581052C1C3D1AB1B3B2D2EC2作业作业1：第第4阶段阶段第第3阶段阶段第第2阶段阶段第第1阶段阶段求从求从A A到到E E的最短路径的最短路径作业作业2某一警卫部门共有某一警卫部门共有12支巡逻队，负责支巡逻队，负责4个要害部位个要害部位A、B、C、D的警卫巡逻。的警卫巡逻。对每个部位可分别派出对每个部位可分别派出24支巡逻队，支巡逻队，并且由于派出巡逻队数的不同，各部并且由于派出巡逻队数的不同，各部位预期在一段时期内可能造成的损失位预期在一段时期内可能造成的损失有差别，具体数字见下表。有差别，具体数字见下表。问警卫部门应往各部位分别派多少支巡问警卫部门应往各部位分别派多少支巡逻队，使总的预期损失为最小。逻队，使总的预期损失为最小。部位部位巡逻队数巡逻队数ABCD234181410383531242221343125