教案_动态规划1_1

1、动态规划动态规划（Dynamic Programming） R. Bellman50年代执教于普林斯顿和斯坦福大学，年代执教于普林斯顿和斯坦福大学，后进入兰德（后进入兰德（Rand）研究所。）研究所。1957年发表年发表“Dynamic Programming”一书，标识动态规划的正式诞生。一书，标识动态规划的正式诞生。 动态规划的研究对象和引例动态规划的理论基础和具体迭代方动态规划的理论基础和具体迭代方 法法动态规划的基本思想和基本方程动态规划的基本思想和基本方程动态规划的基本概念和定义动态规划的基本概念和定义 动态规划是解决复杂系统优化问题的一种方法。是动态规划是解决复杂系统优化问题的一种

2、方法。是解决解决动态系统多阶段动态系统多阶段决策过程的基本方法之一决策过程的基本方法之一。AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643123456第一节 动态规划的引例和研究对象引例引例1 最短路问题最短路问题一、一、 引例引例引例引例2：投资金额分配问题：投资金额分配问题投资项目投资额（百万元）0 1 2 3 4ABC 41 48 60 66 42 50 60 6648 64 68 78 76 某公司有资金4百万元，可以向 A、B、C三个项目追加投资，各项目可以有不同的投资额，相应的效益值如表所示。如何分配资金使总效

3、益值最大？状态（未分的资金额）决策（分配资金额） 0 1 2 3 4最优决策最优决策的效益值01234- - - -48 64 - - -48 64 68 - -48 64 68 78 -48 64 68 78 760123348646878781.对于项目C投资项目投资额（百万元）0 1 2 3 4ABC 41 48 60 66 42 50 60 6648 64 68 78 76 求解过程2.对于项目B状态对B的决策C的状态B的效益值C的效益值最优总效益值011222333344444001012012301234010210321043210404042404250404250604042

4、506066486448686448786864487878686448881049010810698118110114108118120118124114状态（未分的资金额）决策（分配资金额） 0 1 2 3 4最优决策最优决策的效益值0123488 - - - -104 90 - - -108 106 98 - -118 110 114 103 -118 120 118 124 1140000388104108118124状态（未分的资金额）决策（分配资金额） 0 1 2 3 4最优决策最优决策的效益值4162 159 156 164 15431643.对于A项目对于项目B最优决策：A项目

5、3万，B项目0万，C项目1万 包含包含随时间变化随时间变化的因素和变量的系统。的因素和变量的系统。系统在某个时刻的状态，往往要依某系统在某个时刻的状态，往往要依某种形式受过去某些决策的影响；种形式受过去某些决策的影响；将时间作为决策变量之一的决策问将时间作为决策变量之一的决策问题称为动态决策问题。题称为动态决策问题。如经济系统如经济系统,生产系统等生产系统等。动态系统动态系统： 线性系统、非线性系统。线性系统、非线性系统。动态系统动态系统的特点：的特点： 动态决策动态决策 问题：问题：而系统的当前状态和决策又会影响而系统的当前状态和决策又会影响系统今后的发展。系统今后的发展。二、动态规划的研究

6、对象每个阶段都要进行每个阶段都要进行决策决策,目的是使整个过程的决策目的是使整个过程的决策 达到最优效果。达到最优效果。多阶段决策问题：多阶段决策问题：是动态决策问题的一种特殊形式；是动态决策问题的一种特殊形式；在多阶段决策过程中在多阶段决策过程中,系统的动态过程可以按照时间系统的动态过程可以按照时间进程分为进程分为状态状态相互相互联系联系而又相互而又相互区别区别的各个的各个阶段阶段；多阶段决策问题的典型例子：多阶段决策问题的典型例子： 12n状态状态决策决策状态状态决策决策状态状态状态状态决策决策生产存贮决策问题生产存贮决策问题最短路问题最短路问题机器负荷分配问题机器负荷分配问题资源分配问题

7、资源分配问题 但要便于把问题的过程能转化为多阶段决策但要便于把问题的过程能转化为多阶段决策 的过程。的过程。 状态变量的取值有一定的允许集合或范围，此集状态变量的取值有一定的允许集合或范围，此集合称为合称为状态允许集合状态允许集合。 第二节第二节 动态规划的基本概念和定义动态规划的基本概念和定义 1. 阶段、阶段变量阶段、阶段变量 把所给问题的过程，适当地分为若干个相互联系把所给问题的过程，适当地分为若干个相互联系的的阶段阶段; 描述阶段的变量称为描述阶段的变量称为阶段变量阶段变量，常用，常用k表示；表示； 阶段的划分，一般是按时间和空间的自然特征来阶段的划分，一般是按时间和空间的自然特征来划

8、分划分 ；2. 状态、状态变量状态、状态变量每个阶段开始所处的自然状态或客观条件。每个阶段开始所处的自然状态或客观条件。通常一个阶段有若干个状态。通常一个阶段有若干个状态。 描述过程状态的变量称为描述过程状态的变量称为状态变量状态变量，常用，常用sk表示表示第第k阶段的状态。阶段的状态。年、月、年、月、路段路段一个数、一个数、一组数、一组数、一个向量一个向量 在实际问题中决策变量的取值往往在某一范围在实际问题中决策变量的取值往往在某一范围之内，此范围称为之内，此范围称为允许决策集合允许决策集合。常用。常用Dk(sk)表示第表示第k阶段从状态阶段从状态sk出发的允许决策集合，显然有出发的允许决策

9、集合，显然有 一个数一个数一组数一组数一个向量一个向量决定下一阶段的状态，这种决定称为决定下一阶段的状态，这种决定称为决策决策。在最优控制中也称为在最优控制中也称为控制控制。描述决策的变量，称为描述决策的变量，称为决策变量。决策变量。决策变量是状态变量的函数。决策变量是状态变量的函数。常用常用uk(sk) 表示第表示第k阶段当状态为阶段当状态为 sk时的决策变量。时的决策变量。3. 决策、决策变量决策、决策变量 过程的某一阶段、过程的某一阶段、 某个状态某个状态, 可以做出不同的决可以做出不同的决定定(选择选择),uk(sk) Dk(sk) 系统在某一阶段的状态转移不但与系统的当前的系统在某一

10、阶段的状态转移不但与系统的当前的状态和决策有关，而且还与系统过去的历史状态和决状态和决策有关，而且还与系统过去的历史状态和决策有关。其策有关。其状态转移方程状态转移方程如下（一般形式）如下（一般形式）),(),(),(221112211231112kkkkusususTsususTsusTs 图示如下：图示如下：状态转移方程状态转移方程是确定是确定过程由一个状态到另过程由一个状态到另一个状态的演变过程。一个状态的演变过程。如果第如果第k阶段状态变量阶段状态变量sk的值、该阶段的决策的值、该阶段的决策变量一经确定，第变量一经确定，第k+1阶段状态变量阶段状态变量sk+1的值的值也就确定。也就确定

11、。4. 多阶段决策过程多阶段决策过程 可以在各个阶段进行决策，去控制过程发展的可以在各个阶段进行决策，去控制过程发展的多段过程；多段过程； 其发展是通过一系列的状态转移来实现的；其发展是通过一系列的状态转移来实现的；12ks1u1s2u2s3skukSk+1 能用动态规划方法求解的多阶段决策过程是一能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即类特殊的多阶段决策过程，即具有无后效性具有无后效性的多阶的多阶段决策过程。段决策过程。 如果状态变量不能满足无后效性的要求，应适当如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。地改变状态的定义或规定方法。),(

12、),(),(122231112kkkkusTsusTsusTs 动态规划中能动态规划中能处理的状态转移处理的状态转移方程的形式方程的形式。 状态具有无后效性的多阶段决策过程的状态转状态具有无后效性的多阶段决策过程的状态转移方程如下移方程如下无后效性无后效性(马尔可夫性马尔可夫性) 如果某阶段状态给定后，则在这个阶段以后过程如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响；的发展不受这个阶段以前各段状态的影响； 过程的过去历史只能通过当前的状态去影响它未过程的过去历史只能通过当前的状态去影响它未来的发展；来的发展； 构造动态规划模型时，要充分注意是否满足构造动态规划

13、模型时，要充分注意是否满足无后效性的要求；无后效性的要求；状态变量要满足无后效性的要求状态变量要满足无后效性的要求； 由每段的决策按顺序排列组成的决策函数序列由每段的决策按顺序排列组成的决策函数序列称为称为k子过程策略，子过程策略， 当当k=1时，此决策函数序列成为全过程的一个时，此决策函数序列成为全过程的一个策略，简称策略，简称策略策略，记为，记为p1,n (s1).即即 可供选择的策略有一定范围，此范围称为可供选择的策略有一定范围，此范围称为允许策允许策略集合略集合，用，用p表示。从允许策略集合中找出达到最优表示。从允许策略集合中找出达到最优效果的策略称为效果的策略称为最优策略最优策略。)

14、(,),(),()(11,nnkkkkknksusususp)(,),(),()(22111, 1nnnsusususp 5. 策略策略: 按顺序排列的决策组成的集合；按顺序排列的决策组成的集合； 由第由第k n(终止状态终止状态)为止的过程，称为问题的为止的过程，称为问题的后部子过程后部子过程（k子过程）。子过程）。简称简称子策略子策略，记为，记为pk,n(sk)，即，即 它是定义在全过程或所有后部子过程它是定义在全过程或所有后部子过程上确定的数量函数。上确定的数量函数。 动态规划模型的指标函数，应具有可分离性，动态规划模型的指标函数，应具有可分离性，并满足并满足递推递推关系。关系。常见的指

15、标函数的形式是：常见的指标函数的形式是： 费用、成本、利润、路长等费用、成本、利润、路长等 。nknkkkknknksususVV, 2 , 1111,),( 用用Vk, n 表示之。表示之。6. 指标函数和最优值函数指标函数和最优值函数 用来衡量所实现过程优劣的一种数量指标，称用来衡量所实现过程优劣的一种数量指标，称为指标函数；为指标函数；即即V Vk k, ,n n可以表示为可以表示为s sk k,u,uk k, ,V Vk+1,nk+1,n的函数。的函数。常见的指标函数的形式是：常见的指标函数的形式是： 过程和它的任一子过程的指标是它所包含的各过程和它的任一子过程的指标是它所包含的各阶段

16、的指标和。即阶段的指标和。即usvsusVjjnkjjnkknk,1,无后效性的结果。无后效性的结果。 其中其中vj( (s sj ) ) 表示第表示第 j 阶段的阶段的阶段指标阶段指标。这时上式。这时上式可写成可写成),(),(),(111, 11,susVusvsusVnkknkkkknkknk 过程和它的任意子过程的指标是它所包含的各阶段过程和它的任意子过程的指标是它所包含的各阶段的指标的的指标的 乘乘 积积。即。即),(),(1,usvsusVjjjnkjnkknk则可改写成则可改写成),(),(),(111, 11,susVusvsusVnkknkkkknkknk),(,),(111

17、, 1111,nkknkkkknkkkknksusVussususV 多阶段决策过程的数学模型：（具有无后效性的多阶段决策过程的数学模型：（具有无后效性的多阶段决策过程）多阶段决策过程） 第第k阶段阶段 第第n阶段阶段 状态状态sk 终止状态终止状态采取最优策略所得采取最优策略所得到的指标函数值。到的指标函数值。最优值函数最优值函数：),()(1,susVoptsfnkknkkkuunk即即可递推可递推nkUuSsusTstsusvsusVoptkkkkkkkknjjjjnkknkuuun, 2 , 1),(. .),(),(111,21 多阶段决策过程的数学模型：（具有无后效性）多阶段决策过

18、程的数学模型：（具有无后效性）小结小结:),()(1,susVoptsfnkknkkkuunk),(,111,1nkknkkkksusVus方程方程 : 状态转移方程状态转移方程),(1kkkkusTs概念概念 : 阶段变量阶段变量k状态变量状态变量sk决策变量决策变量uk;指标指标: ),(111,nkkkknknksususVV动态规划本质上是多阶段决策过程动态规划本质上是多阶段决策过程; 效益效益指标函数形式指标函数形式: 和、和、 积积无后效性无后效性),(111,nkkkknksususV可递推可递推,*2*1nuuu,*2*1nsss解多阶段决策过程问题，求出解多阶段决策过程问题，

19、求出 最优策略最优策略，即最优，即最优决策序列决策序列susvoptsfnkknkkkuunk1,f1(s1) 最优轨线最优轨线，即执行最优策略时的即执行最优策略时的状态序列状态序列 最优目标函数值最优目标函数值),(*1*1*,1*,1nnnnususVV从从k到终点最优策略到终点最优策略子策略的最优目标函数值子策略的最优目标函数值第三节：动态规划的基本思想和基本方程第三节：动态规划的基本思想和基本方程AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643123456375976713109111316 18 最短路的特性最短

20、路的特性：如果已有从起点到终点的一条如果已有从起点到终点的一条最短路，那么从最短路线上中间任何一点出发到终最短路，那么从最短路线上中间任何一点出发到终点的路线仍然是最短路。（证明用反证法）点的路线仍然是最短路。（证明用反证法）4AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687668353384221233355 26631234564k=5k=5，出发点，出发点E1E1、E2E2、E3E3 73543min,min2621516115FfFEdFfFEdu5(E1)=F1E1 F1 G 53245min,min262251612525FfFEdFfFEdfEAB1B2

21、C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643)(15Efu5(E2)=F2E2 F2 G 93646min,min262351613535FfFEdFfFEdfEu5(E3)=F2E3 F2 Gk=6k=6,F1 G f f6 6(F1)=4(F1)=4F F2 2 G ,f,f6 6(F2)=3(F2)=3k=4，f4(D4)=7 u4(D1)=E2f4(D2)=6 u4(D2)=E2f4(D3)=8 u4(D3)=E2k=2, f2(B1)=13 u2(B1)=C2 f2(B2)=16 u2(B2)=C3f3(C1)=13

22、u3(C1)=D1f3(C2)=10 u3(C2)=D1f3(C3)=9 u3(C3)=D1f3(C4)=12 u3(C4)=D3k=3,= minf1(A)= mind1(A,B1)+ f2(B1) d1(A,B2)+ f2(B2)5+133+16=18k=1,u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2u5(E1)=F1E1 F1 Gu5(E2)=F2E2 F2 Gu5(E3)

23、=F2E3 F2 G7 5 9 u5(E2)=F2u6(F2)=G最优策略最优策略用动态规划（逆序法求解的）基本特性：用动态规划（逆序法求解的）基本特性： 动态规划方法是既把当前一段和未来各段分开，动态规划方法是既把当前一段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优又把当前效益和未来效益结合起来考虑的一种最优化方法。化方法。每段决策的选取都是从全局考虑的每段决策的选取都是从全局考虑的, ,与该段与该段的最优选择答案一般是不同的。的最优选择答案一般是不同的。 求解时求解时从边界条件开始从边界条件开始，逆逆（或顺）过程行进方（或顺）过程行进方向，逐段向，逐段递推递推寻优。在每个问

24、题求解时，都要使用它寻优。在每个问题求解时，都要使用它前面已求出的子问题的最优结果，最后问题的最优解，前面已求出的子问题的最优结果，最后问题的最优解，就是整个问题的最优解。就是整个问题的最优解。 将多阶段决策过程将多阶段决策过程划分阶段划分阶段，恰当地选取，恰当地选取状态变状态变量量、决策变量决策变量、及定义、及定义最优指标函数，最优指标函数，正确写出基本正确写出基本的的递推关系式递推关系式和恰当的和恰当的边界条件边界条件（简言之为基本方（简言之为基本方程）。从而把问题化成一族同类的子问题；程）。从而把问题化成一族同类的子问题； 求解的各个阶段求解的各个阶段, ,我们利用了我们利用了k k阶段

25、与阶段与k+1k+1阶段阶段之间的递推关系之间的递推关系: : 在求整个问题的最优策略时，由于初始状态是在求整个问题的最优策略时，由于初始状态是已知的，每段的决策是该段状态的函数，故沿最优已知的，每段的决策是该段状态的函数，故沿最优化策略所经过的各段状态便可确定了最优路线。化策略所经过的各段状态便可确定了最优路线。fk(sk)=mindk(sk,uk(sk)+fk+1(uk(sk)uk Dk(sk)f7(s7)=0k=6,5,4,3,2,1 一般情况一般情况,k,k阶段与阶段与k+1k+1阶段的递推关系式（动态阶段的递推关系式（动态规划基本方程）规划基本方程） kkkkkkksDukksufs

26、usvsfoptkkk1,011nnsf边界条件为边界条件为练习：写出乘积形式指标函数的动态规划基本方程。练习：写出乘积形式指标函数的动态规划基本方程。 顺序解法：实际上没有顺序法！顺序解法：实际上没有顺序法！小结小结: 要具有可分离性，并满足递推关系。即要具有可分离性，并满足递推关系。即,),(111, 11,nkknkkkknkknksusVussksV 函数函数 k k（s sk k，u uk k，V Vk+1,nk+1,n）对于变量）对于变量V Vk+1k+1，n n要严格单调。要严格单调。将问题的过程划分成恰当的阶段；将问题的过程划分成恰当的阶段；选择状态变量选择状态变量s sk k

27、, , 既能描述过程的变化又满足无既能描述过程的变化又满足无后效性；后效性；确定决策变量确定决策变量u uk k及每一阶段的允许决策集合及每一阶段的允许决策集合D Dk k( (s sk k) )；正确写出状态转移方程；正确写出状态转移方程；正确写出指标函数正确写出指标函数V Vk,nk,n，它应满足下面三个性质：，它应满足下面三个性质： 是定义在全过程和所有后部子过程上的数量函数是定义在全过程和所有后部子过程上的数量函数; ;第四节：第四节： 动态规划的理论基础和动态规划的理论基础和 具体迭代方具体迭代方 法法 多阶段决策过程的特点：每个阶段都要进多阶段决策过程的特点：每个阶段都要进行决策，

28、策略是由行决策，策略是由n个相继进行的决策构成的个相继进行的决策构成的决策序列。前一阶段的终止状态又是下一阶决策序列。前一阶段的终止状态又是下一阶段的初始状态，因此，确定阶段最优决策不段的初始状态，因此，确定阶段最优决策不能只从阶段的效应来考虑，必须是整个过程能只从阶段的效应来考虑，必须是整个过程通盘考虑，整体规划。即阶段通盘考虑，整体规划。即阶段k的最优决策不的最优决策不应该只是本阶段效应的最优，而必须是本阶应该只是本阶段效应的最优，而必须是本阶段及其所有后续阶段的总体最优。段及其所有后续阶段的总体最优。 动态规划方法的理论基础是基于动态规划方法的理论基础是基于R. Bellman提出的提出

29、的最优性原理：最优性原理：“一个过程的最优策略具有这样的性质：一个过程的最优策略具有这样的性质：即无论其初始状态及初始决策如何，对于先前决策所形即无论其初始状态及初始决策如何，对于先前决策所形成的状态而言，余下的诸决策仍构成最优策略。成的状态而言，余下的诸决策仍构成最优策略。”AMB1 . 理论基础理论基础 适应于用动态规划方法求解的是具有无后效性的适应于用动态规划方法求解的是具有无后效性的多阶段决策过程。多阶段决策过程。 最优性原理的含义是：最优策略的任何一部分子最优性原理的含义是：最优策略的任何一部分子策略，也是它相应初始状态的最优策略。每个最优策策略，也是它相应初始状态的最优策略。每个最

30、优策略只能由最优子策略构成。略只能由最优子策略构成。),(),(),(1,1,)(1, 001, 0)(*1, 001, 01, 1,01, 01, 0psVoptpsVoptpsVnkknkkknnsPpsPpknknkkk),(),(1111,1, 01, 0kkkknkknusTsppp 动态规划的最优性定理：设阶段数为动态规划的最优性定理：设阶段数为n n的多阶段的多阶段决策过程，其阶段编号为决策过程，其阶段编号为k k=0,1,.,=0,1,.,n n-1-1。允许策略。允许策略),(*1*1*0*1,0nnuuup是最优策略的充要条件是对任意一个是最优策略的充要条件是对任意一个k k, 0, 0k k n n-1-1和和s s0 0 S S0 0，有，有 它是由给定的初始状态它是由给定的初始状态s s0 0和子策略和子策略p p0,0,k k-1-1所确定的所确定的k k段状态。当段状态。当V V是效益函数时，是效益函数时，optopt取取max;max;当当V V是损失函数是损失函数时，时，optopt取取min.min.证明：必要性（证明：必要性（ ）),(),()