第七章 动态规划

1、第七章第七章 动动 态态 规规 划划 (Dynamic programming)7.2 动态规划的基本概念和基本原理动态规划的基本概念和基本原理7.3 动态规划模型的建立和求解动态规划模型的建立和求解7.4 动态规划的应用动态规划的应用本章学习要求n掌握动态规划数学模型的建立n掌握几种典型问题的动态规划求解方法 动态规划动态规划(Dynamic Programming)是用来解决多阶段决是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一策过程最优化的一种数量方法。其特点在于，它可以把一个个n 维决策问题变换为几个一维最优化问题，从而一个一维决策问题变换为几个一维最优化问题，从

2、而一个一个地去解决。个地去解决。 需指出：动态规划是求解某类问题的一种方法，是考需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。型，然后再用动态规划方法去求解。12n状态状态决策决策状态状态决策决策状态状态状态状态决策决策多阶段决策问题的典型例子：多阶段决策问题的典型例子：1.1.生产决策问题生产决策问题：企业在生产过程中，由于需求是随时间变化的，：企业在生产过程中，

3、由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地逐季度地根据库存和需求决定生产计划。根据库存和需求决定生产计划。2.2.机器负荷分配问题：机器负荷分配问题：某种机器可以在高低两种不同的负荷下进行某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量生产。在高负荷下进行生产时，产品的年产量g g和投入生产的机器数量和投入生产的机器数量u1u1的关系为的关系为 g=g(u1)g=g(u1)这时，机器的年完好率为这时，机器的年完好率为a a，即如果年初完好机器的数量为，

4、即如果年初完好机器的数量为u u，到年，到年终完好的机器就为终完好的机器就为au, 0a1au, 0a1在低负荷下生产时，产品的年产量在低负荷下生产时，产品的年产量h h和投入生产的机器数量和投入生产的机器数量u2u2的关系的关系为为h=h(u2)h=h(u2)相应的机器年完好率相应的机器年完好率b, 0b1b, 0b1。假定开始生产时完好的机器数量为假定开始生产时完好的机器数量为s1s1。要求制定一个五年计划，在。要求制定一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到

5、最高。数量，使在五年内产品的总产量达到最高。3.3.航天飞机飞行控制问题：航天飞机飞行控制问题：由于航天飞机的运动的环境是由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和实现目的（如软着落问题）。使之能最省燃料和实现目的（如软着落问题）。不包含时间因素的静态决策问题（本质上是一次决策不包含时间因素的静态决策问题（本质上是一次决策问题）也可以适当地引入阶段的概念，作为多阶段的决策问题）也可以适当地引入阶段

6、的概念，作为多阶段的决策问题用动态规划方法来解决。问题用动态规划方法来解决。4.4.线性规划、非线性规划线性规划、非线性规划等静态的规划问题也可以通过适等静态的规划问题也可以通过适当地引入阶段的概念，应用动态规划方法加以解决。当地引入阶段的概念，应用动态规划方法加以解决。 5 . 最短路问题最短路问题：给定一个交通网络图如下，其中两点之：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从间的数字表示距离（或花费），试求从A点到点到G点的最短距离点的最短距离（总费用最小）。（总费用最小）。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763

7、685338422213335256643 一、引例（例一、引例（例4）7.2 动态规划的基本概念动态规划的基本概念12345AB1B2C1C2C3C4D1D2D3E1E2F452368774585348433526134：枚举法枚举法每个线路每个线路4次加法次加法24条线路条线路66次加法次加法23次比较次比较：逆向递推法逆向递推法用用fA表示起点到终点的表示起点到终点的最短路长，最短路长，fF=0用用dky表示某节点表示某节点k到某到某节点节点Y的路段长度的路段长度345k21EEff时时：73543minfdfdmin4kE2D1E2E1D1E11Df时时：53246minfdfdmin

8、E2D2E2E1D2E1D2f53341minfdfdminE2D3E2E1D3E1D3f125875minfdfdmin3kD2C1D2D1C1D11Cf时时：015574minfdfdminD2C2D2D1C2D1C2f8453minfdfdminD3C3D3D2C3D2C35f9458minfdfdminD3C4D3D2C4D2C45f1386103122mindfdfdmin2k331C2B1C2C1B1C11BCCBf时时：1597871084422mindfdfdminC3B2C3C2B2C2BCCBf17155134minfdfdmin1kB2AB2B1AB1Af时时： 二、基本

9、概念二、基本概念把一个问题的过程，恰当地分为若干个相互联系的把一个问题的过程，恰当地分为若干个相互联系的阶段阶段，以便于按一定的次序，以便于按一定的次序去求解。去求解。描述阶段的变量称为描述阶段的变量称为阶段变量阶段变量,用用k表示表示。阶段的划分，一般是根据时间和空间。阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。的自然特征来进行的，但要便于问题转化为多阶段决策。表示每个阶段开始所处的表示每个阶段开始所处的自然状况或客观条件自然状况或客观条件。既是某阶段过。既是某阶段过程演变的起点，又是前一阶段某种决策的结果。描述过程状态的变量称为程演变的起点，又是前一阶

10、段某种决策的结果。描述过程状态的变量称为状态变量状态变量,用用Sk表示表示。状态变量的取值有一定的允许集合或范围，此集合称为状态变量的取值有一定的允许集合或范围，此集合称为状态允许集合状态允许集合。表示当过程处于某一阶段的某个状态时，可以作出表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态不同的决定，从而确定下一阶段的状态，这种决定称为这种决定称为决策决策。按一定顺。按一定顺序排列的决策序列称为策略。序排列的决策序列称为策略。 描述决策的变量，称为描述决策的变量，称为决策变量决策变量,用用Uk(Sk )。决策变量是状态变量。决策变量是状态变量的函数。可用一个数、一

11、组数或一向量（多维情形）来描述。的函数。可用一个数、一组数或一向量（多维情形）来描述。 在实际问题中决策变量的取值往往在某一范围之内，此范围称为在实际问题中决策变量的取值往往在某一范围之内，此范围称为允允许决策集合许决策集合,用用Dk(Sk )表示表示。状态转移方程是状态转移方程是如果第如果第k阶段状态阶段状态变量变量sk的值、该阶段的决策的值、该阶段的决策变量一经确定，第变量一经确定，第k+1阶段阶段状态变量状态变量sk+1的值也就确定。的值也就确定。),(),(),(122231112kkkkusTsusTsusTs 图示如下：图示如下：12ks1u1s2u2s3skuksk+1 能用动态

12、规划方法求解的多阶段决策过程是一类特殊的多能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即阶段决策过程，即具有无后效性具有无后效性的多阶段决策过程。的多阶段决策过程。无后效性无后效性( (马尔可夫性马尔可夫性) )如果某阶段状态给定后，则在这个阶段以后过程的发展不受如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响；这个阶段以前各段状态的影响；过程的过去历史只能通过当前的状态去影响它未来的发展；过程的过去历史只能通过当前的状态去影响它未来的发展；构造动态规划模型时，要充分注意是否满足无后效性的要求；构造动态规划模型时，要充分注意是否满足无后效性的要

13、求；状态变量要满足无后效性的要求；状态变量要满足无后效性的要求；如果状态变量不能满足无后效性的要求，应适当地改变状态如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。的定义或规定方法。用用d dk k(S(Sk k, U, Uk k) )表示表示, ,指第指第k k阶段，阶段，S Sk k状态下，作出状态下，作出U Uk k决决策带来的效果。在不同的问题中，指标的含义是不同的，它可能是距离、利策带来的效果。在不同的问题中，指标的含义是不同的，它可能是距离、利润、成本、产量或资源消耗等。润、成本、产量或资源消耗等。用用V Vknkn(S(Sk k, P, Pknkn) )表示

14、表示, ,指指k k阶段，阶段，S Sk k状态下，作出状态下，作出P Pknkn子子策略带来的效果。用以衡量多阶段决策过程实现效果的一种数量指标，是定策略带来的效果。用以衡量多阶段决策过程实现效果的一种数量指标，是定义在全过程和所有后部子过程的数量函数。义在全过程和所有后部子过程的数量函数。用用f fk k(S(Sk k) )表示表示, ,过程指标函数的最优值，称过程指标函数的最优值，称为最优值函数。用为最优值函数。用f fk k(S(Sk k)=optV)=optVknkn(S(Sk k,P,Pknkn) )optopt表示最优化，常取表示最优化，常取maxmax或或minmin1、Bel

15、lman最优性定理最优性定理一个过程的最优策略具有这样的性质：即无论初始状态及初始一个过程的最优策略具有这样的性质：即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后所有的决决策如何，对于先前决策所形成的状态而言，其以后所有的决策应构成最优策略。策应构成最优策略。换句话说，最优策略只能由最优子策略构成。换句话说，最优策略只能由最优子策略构成。2、思想方法：、思想方法：在求解过程中，各阶段的状态和决策，对其在求解过程中，各阶段的状态和决策，对其后面的阶段来说，只影响其初始状态，而不影响后面的最优策后面的阶段来说，只影响其初始状态，而不影响后面的最优策略。略。无后效性无后效性方法：

16、方法：“顺序编号，逆序求解顺序编号，逆序求解”三、动态规划的基本思想和基本方程三、动态规划的基本思想和基本方程3、基本方程、基本方程 根据最优性定理，可以写出动态规划递推方程，根据最优性定理，可以写出动态规划递推方程，即基本方程：即基本方程： Vkn(Sk,Pkn）= dj(Sj, Uj),j=k,n时，时， fk(Sk)=opt dk (Sk,Uk）+ fk+1(Sk+1) fn+1(Sn+1)=0Vkn(Sk,Pkn）= dj(Sj, Uj),j=k,n时，时， fk(Sk)=opt dk (Sk,Uk） fk+1(Sk+1) fn+1(Sn+1)=1其中的其中的fn+1(Sn+1)为边界

17、条件。为边界条件。 7.3 动态规划模型的建立和步骤动态规划模型的建立和步骤 一、动态规划模型的建立一、动态规划模型的建立1 1、划分、划分正确选择正确选择N N个阶段个阶段 S Sk k可知性和无后效性可知性和无后效性2 2、确定、确定u uk k及允许及允许 3 3、确定、确定S Sk+1k+1=T=Tk k(S(Sk k,u,uk k(S(Sk k)根据根据k k 阶段状态变量和决策变量，写出阶段状态变量和决策变量，写出k+1k+1阶段状态变量，状态转移方阶段状态变量，状态转移方程应当具有递推关系。程应当具有递推关系。4 4、确定、确定和和d(Sd(Sk k,u,uk k) V) Vk,

18、nk,n f fk k(S(Sk k) )5 5、建立、建立 fk(Sk)=opt dk (Sk,Uk）+ fk+1(Sk+1) fN+1(SN+1)=0例例5 5：解法：解法1 1（逆向递推）（逆向递推）1 1、划分阶段：、划分阶段：3 3个阶段个阶段 状态变量状态变量S1,S2,S3S1,S2,S3。SkSk: :表示第表示第k k阶段可以投资于第阶段可以投资于第k k个项目到第个项目到第3 3个项个项目的资金。目的资金。S1=10,S4=0S1=10,S4=02 2、确定决策变量：、确定决策变量：x1,x2,x3 (uk=xkx1,x2,x3 (uk=xk) )3 3、建立状态转移方程：

19、、建立状态转移方程：4 4、确定指标函数：、确定指标函数：5 5、组建函数递推方程（基本方程）、组建函数递推方程（基本方程） kkkk1kxu1 , 2 , 3kuSS)(),()(33 ,kkkkkkiiikxguSdxgV23332221112x)(xg9x)(xg4x)(xg0)(f1 , 2 , 3k)()()(f4411kSSfxgMaxSkkkkk3*3232333044333303322max)()(max)(3kSxSxSfxgSfSxSx时时2222220232220332222022)xS( 29xmaxS29xmax)()(max)(2kSxSxSxSfxgSf时时的端点

20、取得。的端点取得。可能在可能在是极小值点，极大值只是极小值点，极大值只当当, 049222SSx22222222229)(S2)(0SSVxSSVx时，时，当当时，时，当当2*22222222*222222222S9)S(f299202)S(f2992xSSSSxSSSS)(4xmax)()(max)(1k22110202211101011SfSfxgSfxx时时10,10, 0,10, 0200200362max4224xmax)24xmax)(4xmax)(2)(*3*223*2*112*1121101011212111010211110102211010112222xxSSxxSSxxx

21、xSxSxSSfSfSSfxxxx（时时当当相相矛矛盾盾（舍舍去去）与与时时当当2910,090959max994xmax94xmax)(9)(2*112*11111010111101021101011222SxSSxSxSxSSSfSSfxxx例例5 5：解法：解法2 2（顺序递推）（顺序递推）Sk+1:Sk+1:表示第表示第k k阶段可以投资于第阶段可以投资于第1 1个项目到第个项目到第k k个项目的资金。个项目的资金。S1=0,S4=10S1=0,S4=10状态转移方程：状态转移方程：组建函数递推方程（基本方程）组建函数递推方程（基本方程） kkk1kkxu1 , 2 , 3kuSS0)

22、(f3 , 2 , 1k)()()(f1011kSkx01kSSfxgMaxSkkkkk123S1=10S1=10 x1x1S2S2x2x2S3S3S4=0S4=0 x3x3123S1=0S1=0 x1x1S2S2x2x2S3S3S4=10S4=10 x3x32*1212101011210214S4xmax)()(max)(1kSxSfxgSfSxSx时时3*2323232022320212232032Sx9S4x4S9xmax4S9xmax)()(max)(2kSxSxSxSfxgSf时时0Sx, 0 xSS, 0 x, 0 x10S10 x200909x2xmax9S2xmax)()(ma

23、x)(3k2*1*232*2*33*3323103032310303233103043xxxSfxgSf时时二、顺序解法和逆序解法二、顺序解法和逆序解法1 1、状态转移方式不同、状态转移方式不同S Sk+1k+1=T=Tk k(S(Sk k,u,uk k) ) S Sk k=T=Tk k(S(Sk+1k+1,u,uk k) )2 2、指标函数的定义不同、指标函数的定义不同f fk k(S(Sk k) )表示第表示第k k阶段从状态阶段从状态S Sk k出发，到终点后部子过程的最优效益出发，到终点后部子过程的最优效益值，值，f f1 1(S(S1 1) )是整体最优值。是整体最优值。f fk k

24、(S(Sk k1 1) )表示第表示第k k阶段从起点到状态阶段从起点到状态S Sk k1 1的前部子过程的最优效益的前部子过程的最优效益值，值，f fn n(S(Sn+1n+1) )是整体最优值。是整体最优值。3 3、基本方程的形式不同、基本方程的形式不同(1)(1)当指标函数为阶段指标和形式时当指标函数为阶段指标和形式时(2)(2)当指标函数为阶段指标积形式时当指标函数为阶段指标积形式时n, 1k0)(f)()u,S(dopt)(f101k11kSSfSkkkkk顺顺序序1 ,nk0)(f)()u,S(dopt)(f1n1n11kkSSfSkkkkk逆逆序序1 ,nk1)(f)().u,S

25、(dopt)(f1n1n11kkSSfSkkkkk逆逆序序n, 1k1)(f)().u,S(dopt)(f101k11kSSfSkkkkk顺顺序序7.4 动态规划在经济管理中的应用动态规划在经济管理中的应用 有一个徒步旅行者，其可携带物品重量的限度为有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有公斤，设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价值种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？作用（使用价值）最大？物品物品1 2 j

26、n重量（公斤重量（公斤/ /件）件）a1 a2 aj an每件使用价值每件使用价值c1 c2 cj cn 这就是背包问题。类似的还有工厂里的下料问题、运输中的这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。货物装载问题、人造卫星内的物品装载问题等。一、背包问题一、背包问题设设xj 为第为第j 种物品的装件数（非负整数）则问题的数学种物品的装件数（非负整数）则问题的数学模型如下：模型如下： ). 2 . 1(0max1njxaxaxcZjnijjjnjjj 且且为为整整数数例例7：且且为为整整数数0,10543654max321321321xxxxx

27、xxxxZ解：逆序求解解：逆序求解1.阶段：分阶段：分3个阶段，状态变量个阶段，状态变量Sk:代表分配给第代表分配给第k种至第种至第3种货种货物的重量物的重量2.决策变量决策变量uk=xk k=1,2,3代表装载第代表装载第k种货物的件数；种货物的件数；3.状态转移方程：状态转移方程：Sk+1=Sk-akxk a1=3,a2=4,a3=54.阶段指标：阶段指标：dk(Sk,uk)=ckxk c1=4,c2=5,c3=65.基本方程：基本方程：1 , 2 , 3k0)(f)()u,S(dmax)(f4411kkSSfSkkkkkk=3x3S3f3(S3) x3*k=2x2S2f2(S2) x2*

28、S2=S1-3x1k=1x1S1f1(S1) x1* 练习：某厂生产三种产品，各种产品重量与利润练习：某厂生产三种产品，各种产品重量与利润的关系如表所示。现将此三种产品运往市场出售，的关系如表所示。现将此三种产品运往市场出售，运输能力总重量不超过运输能力总重量不超过 6 吨，问如何安排运输，使吨，问如何安排运输，使总利润最大？总利润最大？种类种类 1 2 3重量（吨重量（吨/ /公斤）公斤） 2 3 4 单件利润（元）单件利润（元） 80 130 180最优方案：最优方案：X1 = =（0 0，2 2，0 0）X2 = =（1 1，0 0，1 1）Z=260=260 （1）阶段：按时间划分）阶

29、段：按时间划分,k=1,2,3,4（2）状态变量）状态变量Sk:为第为第k个月初的库存量，个月初的库存量，MaxSk=3, E(Sk)为储存费用为储存费用（3）决策变量）决策变量uk：为第为第k个月生产量，个月生产量，Maxuk=6，C(uk）为生产费用）为生产费用（4）状态转移方程：）状态转移方程：Sk+1=Sk+uk-gk 下月初的库存量本月初的库存量每月的生产量需求量下月初的库存量本月初的库存量每月的生产量需求量（5）最优指标函数）最优指标函数fk(Sk)：k阶段状态阶段状态Sk时采用最佳生产时从时采用最佳生产时从k月到第月到第4月的生产、存储最低费用。月的生产、存储最低费用。则基本方程

30、则基本方程 fk(Sk)=MinC(uk)+E(Sk)+fk+1(Sk+uk-gk) f5(S5)=0 k=4,3,2,1二、生产经营问题二、生产经营问题（例（例8:P212）当当k=4时时 S5=0 S4+u4-g4=0则则u4=g4-S4=4-S4u4S4f4(S4) u4*k=3u3S3f3(S3) u3*k=2u1S1f1(S1)u1*k=1u2S2f2(S2) u2* （1）阶段：按时间划分）阶段：按时间划分,k=1,2,3,4（2）状态变量）状态变量Sk:为第为第k个月初的库存量，个月初的库存量，MaxSk=1000, S1=500,S5=0（3）决策变量）决策变量:xk为第为第k

31、个月的销售计划，个月的销售计划，yk为第为第k个月的订购计划。个月的订购计划。（4）状态转移方程：）状态转移方程：Sk+1=Sk+yk-xk 下月初的库存量本月初的库存量本月的订购计划量本月销售计划量下月初的库存量本月初的库存量本月的订购计划量本月销售计划量（5）则基本方程）则基本方程 fk(Sk)=Maxpkxk-ckyk+fk+1(Sk+1) f5(S5)=0 k=4,3,2,1例例9:采购与销售问题采购与销售问题与生产和存储问题相似与生产和存储问题相似一台设备的效益函数一台设备的效益函数r(t),维修费用函数维修费用函数U(t)及更新费用函数及更新费用函数c(t)，要，要求在求在n年内的

32、每年初作出决策，是继续使用旧设备还是更换新的？使年内的每年初作出决策，是继续使用旧设备还是更换新的？使n年的年的总效益最大。总效益最大。（1）阶段：按时间划分）阶段：按时间划分,k=1,2,，n（2）状态变量）状态变量Sk:为第为第k年设备已经使用过的年数，即役龄。年设备已经使用过的年数，即役龄。（3）决策变量）决策变量xk：为第：为第k年初更新年初更新R，还是继续使用，还是继续使用K。（4）状态转移方程：）状态转移方程：（5）阶段指标：）阶段指标：则基本方程则基本方程 三、设备更新问题三、设备更新问题（例（例10:P218）更更新新）保保留留）(u1(SSkk1kRkuk1RxSckxkkkk)(0U)0(r)S(U)S(r)x