动态规划PPT教学课件

1、动态规划第三章 动态规划 3.1 动态规划的基本概念和方法基本概念与名词解释最优化原理与动态规划的基本方法 3.2 动态规划模型的建立与求解步骤 建立动态规划模型的基本要求动态规划的求解步骤 3.3 动态规划的应用举例定价问题资源分配问题生产存储问题第一节 动态规划的基本概念与方法1 动态规划的基本概念一、动态决策问题： 决策过程具有阶段性和时序性(与时间有关)的决策问题。即决策过程可划分为明显的阶段。二、什么叫动态规划(D.P. Dynamic Program)： 多阶段决策问题最优化的一种方法。 广泛应用于工业技术、生产管理、企业管理、经济、军事等领域。三、动态规划(D.P.)的起源： 1

2、951年,美国数学家R.Bellman(贝尔曼)等人提出最优化原理，从而建立动态规划，他的名著动态规划于1957年出版。四、动态决策问题分类：1、按数据给出的形式分为： 离散型动态决策问题。 连续型动态决策问题。2、按决策过程演变的性质分为： 确定型动态决策问题。 随机型动态决策问题。名词解释 例3-1 某公司欲将一批货物从城市A运到城市E去，如图所示，走哪条路线最好？1、阶段(stage)k： 把所给问题的过程，恰当地分成若干个相互联系的阶段。描述阶段的变量称为阶段变量，常用k表示。k = 1、2、3、4。2、状态(state)Sk：状态表示每个阶段开始所处的自然状态，即是每一阶段的出发位置

3、。阶段的起点。通常一个阶段有多个状态。记为Sk S1=A，S2=B1,B2,B3，S3=C1,C2,C3， S4=D1,D2。3、决策(decision) uk(sk) ：从一个阶段某状态演变到下一个阶段某状态的选择。常用uk(sk) 表示第k阶段当状态处于sk时的决策变量。决策集用Dn(Sk)表示。就是阶段的终点。 D1(S1)=u1(A)=B1,B2,B3= S2， D2(S2)=U2(B1),U2(B2),U2(B3)=C1,C2;C1,C2,C3 ;C2,C3 =C1,C2,C3=S3， D3(S3)=U3(C1),U3(C2),U3(C3)=D1,D2;D1,D2,D3; D1,D2

4、,D3=D1,D2,D3=S4， D4(S4)=U4(D1),U4(D2),U4(D3)=E1,E2;E1,E2;E1,E2=E1,E2=S5， D5(S5)=X5(E1),X5(E2)=F;F=F。4、策略(policy)：策略是一个按顺序排列的决策组成的集合。即是全过程中各个阶段的决策Un组成的有序总体Un。 如 A B2 C1 D1 E 5、子策略(sub-policy) ：由过程的第k阶段开始到终止状态为止的过程，即是剩下的M个阶段构成M子过程，相应的决策系列叫M子策略。 如 C1 D1 E6、状态转移方程：状态转移方程是确定过程由一个状态到另一个状态的演变过程，如果给定第k阶段的状态

5、Sk ，本阶段决策为Uk( Sk) ，则第k+1阶段的状态Sk+1也就完全确定，它们的关系可表示为Sk+1Tk(Sk ,Uk),它描述了由k阶段到k+1阶段的状态转移规律，称为状态转移方程。即是前一阶段的终点(决策)是后一阶段的起点(状态)。 如 Uk( Sk) Sk+1 7、指标函数：用来衡量各个阶段优劣的数量指标，它是定义在全过程和所有后部子过程上确定的数量函数。记为Vk,n(sk,Uk)。如上例中，用dk(sk,Uk)表示距离。d2(B3,C2)=8, d3(C2,D2)=2 等。8、目标函数：策略的数量指标值，记为 Z=optv1(s1,u1)* vn(sn,un)。其中：opt为ma

6、x或min，*为运算符号。如上例中，Z=mind1(s1,u1)+dn(sn,un)=mind1+d2+ dn最优化原理 一、R.Bellman最优化原理： 作为整个过程的最优策略，无论过去的状态和决策如何，对前面的决策形成状态而言，余下的诸决策必构成最优策略。 即：若M是从A到B最优路线上的任一点，则从M到B的路线也是最优路线。A MB二、指标递推方程： fn*(Sn) = opt vn(sn,un) * vn(sn,un) xnDn(Sn) 如上例：fn*(Sn) = min vn(sn,un)+ fn+1*(Sn+1) ， n=3、2、1 xnDn(Sn) f4*(S4) = min v

7、4(s4,u4) x4D4(S4) 三、求解过程： 用反向嵌套递推法：从最后一个阶段开始，依次对各子过程寻优，直至获得全过程的最优， 形成最优策略，获得最优策略指标值。第二节 动态规划模型的建立与求解步骤一、建立动态规划模型的基本要求 将问题划分成若干阶段。有的问题阶段性很明显，有的则不明显，需要分析后人为假设。 确定各阶段的状态变量，并给出状态转移方程，状态转移方程的形式应当与递推顺序一致。 状态变量应当满足无后效性要求。 明确指标函数，给出最优函数递推方程，递推方程的形式应当与递推顺序一致。二、动态规划的求解步骤 正确划分阶段。 确定状态变量和决策变量，并给出状态变量和决策变量的可行集合。

8、 确定求解的递推顺序，给出状态转移方程。 确定阶段、子过程(子策略)的指标函数，确定最优值函数的递推方程和边界条件。 递推求解。 与递推过程反向求出最优策略(最优决策变量值系列)和最优状态变化路线。例2：求图中A到F的最短路线及最短路线值。AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141、阶段(stage)n： n = 1、2、3、4、5。2、状态(state)Sn： S1=A，S2=B1,B2,B3，S3=C1,C2,C3，S4=D1,D2

9、,D3，S5=E1,E2。3、决策(decision)un：决策集Dn(Sn)。 D1(S1)=u1(A)=B1,B2,B3= S2， D2(S2)=u2(B1),u2(B2),u2(B3)=C1,C2;C1,C2,C3 ;C2,C3 =C1,C2,C3=S3， D3(S3)=u3(C1),u3(C2),u3(C3) =D1,D2;D1,D2,D3; D1,D2,D3=D1,D2,D3=S4， D4(S4)=u4(D1),u4(D2),u4(D3)=E1,E2;E1,E2;E1,E2=E1,E2=S5， D5(S5)=u5(E1),u5(E2)=F;F=F。AB1B2B3C1C2C3D1D2D

10、3E1E2F354954351715846442226975144、状态转移方程：un = Sn+15、指标函数(距离)：dn(sn,un)。 d2(B3,C2)=1, d3(C2,D3)=6 等。6、指标递推方程：fn*(Sn) = min rn(sn,un)+ fn+1*(Sn+1) ， n=4、3、2、1 UnDn(Sn) f5*(S5) = min V5(s5,u5) X5D5(S5)AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514n=5 f5(s5)=d5(s5,u5) u5 S5 F f5*(s5) U*5 E1 E2 11F22

11、Fn=4 f4(s4)=d4(s4,u4)+ f5*(s5) u4 S4 E1 E2 f4*(s4) U*4 D1 D2 D3 4 + 1 = 52 + 2 = 44 E26 + 1 = 79 + 2 = 117E17 + 1 = 85 + 2 = 77E2AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514n=3 f3(s3)=d3(s3,u3)+ f4*(s4) u3 S3 D1 D2 D3 f3*(s3) u3* C1 C2 C3 1 + 4 = 55 + 7 = 12 / / / 5D18+ 4 = 124 + 7 = 116 + 7 =

12、 1311D24+ 4 = 84+ 7 = 112+ 7 = 98D1n=2 f2(s2)=d2(s2,u2)+ f3*(s3) u2 S2 C1 C2 C3 f2*(s2) u2* B1 B2 B3 9+ 5 = 145+ 11 = 16 / / /14C14+ 5 = 93+ 11 = 145+ 8 = 139C1 / / /1+ 11 = 127+ 8 = 15 12C2AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514n=1 f1(s1)=d1(s1,u1)+ f2*(s2) u1 S1 B1 B2 B3 f1*(s1) u1* A 3

13、+ 14 = 175+ 9 = 144+ 12 = 16 14B2最短路线值为：f1*(s1) = 14最短路线求解如下：n= 5 f5(s5)=d5(s5,U5) U5 S5 F f5*(s5) U5 E1 E2 n= 1 f1(s1)=d1(s1,U1)+ f2*(s2) U1 S1 B1 B2 B3 f1*(s1) U1* A 11F22Fn= 4 f4(s4)=d4(s4,U4)+ f5*(s5) U4 S4 E1 E2 f4*(s4) U4 D1 D2 D3 4 + 1 = 52 + 2 = 44 E26 + 1 = 79 + 2 = 117E17 + 1 = 85 + 2 = 77

14、E2n= 3 f3(s3) =d3(s3,U3) + f4*(s4) U3 S3 D1 D2 D3 f3*(s3) U3* C1 C2 C3 1 + 4 = 55 + 7 = 12 / / / 5D18+ 4 = 124 + 7 = 116 + 7 = 1311D24+ 4 = 84+ 7 = 112+ 7 = 98D1n= 2 f2(s2) =d2(s2,U2) + f3*(s3) U2 S2 C1 C2 C3 f2*(s2) U2* B1 B2 B3 9+ 5 = 145+ 11 = 16 / / /14C14+ 5 = 93+ 11 = 145+ 8 = 139C1 / / /1+ 11

15、 = 127+ 8 = 15 12C23+ 14 = 175+ 9 = 144+ 12 = 16 14B2AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514即： A B2 C1 D1 E2 F 第三节 动态规划的应用举例 定价问题 资源分配问题 生产存储问题一、定价问题 某公司考虑为某新产品定价，该产品的单价拟从每件5元、6元、7元和8元这四个中选取一个，每年允许价格有1元幅度的变动，该产品预计畅销五年，据预测不同价格下各年的利润如表3-1所示。 表3-2 每年预计利润额单价第一年 第二年 第三年 第四年 第五年5元6元7元8元10121416

16、12131415151616152020181425241814建立数学模型 按年划分阶段，k=1,2,.,5 每阶段的状态变量为本年(上一年已确定)的价格，状态变量的可行集合Sk=(5,6,7,8)。 决策变量为每年依据当年价格为下一年度决定价格，根据题意决策变量的可行集合是： 采用逆序算法，因此状态转移方程是 最优值函数递推方程为) 1, 1(kkkkSSSu)(1kkkSuS)()(max)(11kkkkukkSfudSfk进行各阶段的计算 采用逆序法，设 当k=5时，S5=(5,6,7,8)，由表3-1得到 当k=4时， S4=(5,6,7,8)，由递推方程 得0)(66Sf14)8(

17、,18)7(,24)6(,25)5(5555ffff)()(max)(5544444SfudSfu5)5(,4524202520max)6()6()5()5(max)5(454544ufdfdf继续求解 同理得其它各阶段的最优解8) 8 (,92) 8 (, 8) 7 (,90) 7 (, 7) 6 (,87) 6 (6) 5 (,84) 5 (,17) 8 (,76) 8 (, 7 , 6) 7 (,75) 7 (, 7 , 6) 6 (,74) 6 (6) 5 (,73) 5 (,27) 8 (,57) 8 (, 6) 7 (,61) 7 (, 6 , 5) 6 (,61) 6 (6 ,

18、5) 5 (,60) 5 (,37) 8 (,32) 8 (, 6) 7 (,42) 7 (, 5) 6 (,45) 6 (111111112222222233333333444444ufufufufkufufufufkufufufufkufufuf时当时当时当反推得最优路线 按照与求最优值函数方向相反的顺序求最优状态路线：最优决策变量。即从第一年单价应为8元开始，向后推算。 得第二年定价8元，第三年定价7元，第四年定价6元，第五年定价5元。 最大利润值为92万元。也可用决策图求解二、资源分配问题 某公司将5台加工中心分配给甲、乙、丙、丁四个工厂，各工厂得设备后可产生如表3-2所示的利润，应怎

19、么分配设备可使公司总利润最大？ 工厂设备数甲乙丙丁012345067101215037912130510111111046111212建立数学模型 按工厂次序划分阶段，k=1，2，3，4 状态变量为各阶段可用于分配的设备总台数 决策变量是分配给第k工厂的设备数 采用逆序算法，状态转移方程 最优值函数递推方程kkkxSS10)()()(max)(5511SfSfudSfkkkkukkk第4阶段的最优解 当k=4时，S4=(0,1,2,3,4,5)0123450123450461112120461112120123454S4u),(444Sud)(44Sf)(4*4Su第3阶段的最优解 当k=3时

20、，S3=(0,1,2)0000000101054045512012051064069101023S3u),(333Sud)(334uSf*3u33fd )(33Sf第3阶段的最优解（续） 当k=3时，S3=33012305101111640111114111423S3u),(333Sud)(334uSf*3u33fd )(33Sf第3阶段的最优解（续） 当k=3时，S3=44012340510111112116401216161511161，23S3u),(333Sud)(334uSf*3u33fd )(33Sf第3阶段的最优解（续） 当k=3时，S3=55012345051011111112

21、12116401217211715112123S3u),(333Sud)(334uSf*3u33fd )(33Sf第2阶段的最优解 当k=2时，S2=(0,1,2)0000000101035053502012037105010871002S2u),(222Sud)(223uSf*2u22fd )(22Sf第2阶段的最优解（续）当k=2时，S2=330123037914105014131291402S2u),(222Sud)(223uSf*2u22fd )(22Sf第2阶段的最优解（续）当k=2时，S2=4401234037912161410501617171412171，22S2u),(222

22、Sud)(223uSf*2u22fd )(22Sf第2阶段的最优解（续）当k=2时，S2=55012345037912132116141050211921191715210，22S2u),(222Sud)(223uSf*2u22fd )(22Sf第1阶段的最优解（续）当k=1时，S1=5 50123450671012152117141050212321201715231 1S1u),(111Sud)(112uSf*1u11fd )(11Sf反向求最佳状态路线0 , 10 , 122 , 32 , 141*44*33*22*1uSuSuSu由方案一方案二工厂名分配设备数工厂名分配设备数甲乙丙丁1

23、121甲乙丙丁1220三、生产存储问题 某公司生产并销售某产品。根据市场预测，今后四个月的市场需求量如表3-7所示。时期（月）需求量（dk）12342324三、生产存储问题 某公司生产并销售某产品。根据市场预测，今后四个月的市场需求量如表3-7所示。时期（月）需求量（dk）12342324已知的其它条件 已知生产一件产品的成本是1千元，每批产品的生产准备成本是3千元，每月仅能生产一批，每批6件。每件存储成本为0.5千元，且第一个月初无存货，第四个月末的存货要求为零。求最优生产计划。 设第k月的生产量uk，存储量为Sk,则总成本为kkkkkSuuSC5 . 003),(建立数学模型 以月划分阶段

24、，k=1,2,3,4 各阶段决策变量为该阶段生产量uk，状态变量为该阶段存储量Sk。 采用逆序算法，则状态转移方程为 最低成本递推公式是kkkkduSS10)()(),(min)(551160SfSfuSCSfkkkkkduSukkkkkk第四阶段的最优解 当k=4时，d4=4,因第四阶段末无存货，因此S4=(0,1,2,3,4)S4u4本期成本C4S5f5(S5)f4(S4)生产存储01234432107654000.511.5276.565.52000000000076.565.52第三阶段最优解 当k=3时，由于 ，且第三阶段需求量d3=2，S3=(0,1,2,3,4,5,6)44SS3

25、u3本期成本C3S4f4(S4)f3(S3)生产存储0234565678900000567890123476.565.521212.51313.511第三阶段最优解:S3=1S3u3本期成本C3S4f4(S4)f3(S3)生产存储112345456780.50.50.50.50.54.55.56.57.58.50123476.565.5211.512.012.513.010.5第三阶段最优解:S3=2S3u3本期成本C3S4f4(S4)f3(S3)生产存储2012340456711111156780123476.565.52811.512.012.510.0第三阶段最优解:S3=3,4S3u3

26、本期成本C3S4f4(S4) f3(S3)生产存储3012304561.51.51.51.51.55.56.57.512346.565.52811.512.09.5401204522226723465.52811.59第三阶段最优解:S3=5,6S3u3本期成本C3S4f4(S4) f3(S3)生产存储501042.52.52.56.5345.5288.560033425第二阶段最优解 当k=2时，d2=3，由于最生产能力为6，而d1=2，因此S2=(0,1,2,3,4)S2u2本期成本C2S3f3(S3)f2(S2)生产存储03456678900006789012311.010.58.08.

27、01717.51617第二阶段最优解:S2=1S2u2本期成本C2S3f3(S3)f2(S2)生产存储123456567890.50.50.50.50.55.56.57.58.59.50123411.010.58.08.08.016.51715.516.517.5第二阶段最优解:S2=2S2u2本期成本C2S3f3(S3)f2(S2)生产存储2123456456789111111567891001234511.010.58.08.08.08.016.016.515.016.017.018.0第二阶段最优解:S2=3S2u2本期成本C2S3f3(S3) f2(S2)生产存储30123456045

28、67891.51.51.51.51.51.51.51.55.56.57.58.59.510.5012345611.010.58.08.08.08.05.012.516.014.515.516.517.515.5第二阶段最优解:S2=4S2u2本期成本C2S3f3(S3) f2(S2)生产存储4012345045678222222267891012345610.58.08.08.08.05.012.51415161715第一阶段最优解 当k=1时，d1=2，S1=0S1u1本期成本C1S2f2(S2)f1(S1)生产存储0234565678900000567890123416.015.515.0

29、12.512.52121.52220.521.5最优解 从第一阶段向后反推最优路线，总结可得时期K期初存货期末存货最优生产量该期成本总成本SkSk+1123403043040506081.59220.512.5112已知的其它条件 已知生产一件产品的成本是1千元，每批产品的生产准备成本是3千元，每月仅能生产一批，每批6件。每件存储成本为0.5千元，且第一个月初无存货，第四个月末的存货要求为零。求最优生产计划。 设第k月的生产量uk，存储量为Sk,则总成本为kkkkkSuuSC5 . 003),(建立数学模型 以月划分阶段，k=1,2,3,4 各阶段决策变量为该阶段生产量uk，状态变量为该阶段存

30、储量Sk。 采用逆序算法，则状态转移方程为 最低成本递推公式是kkkkduSS10)()(),(min)(551160SfSfuSCSfkkkkkduSukkkkkk第四阶段的最优解 当k=4时，d4=4,因第四阶段末无存货，因此S4=(0,1,2,3,4)S4u4本期成本C4S5f5(S5)f4(S4)生产存储01234432107654000.511.5276.565.52000000000076.565.52第三阶段最优解 当k=3时，由于 ，且第三阶段需求量d3=2，S3=(0,1,2,3,4,5,6)44SS3u3本期成本C3S4f4(S4)f3(S3)生产存储0234565678900000567890123476.565.521212.51313.511第三阶段最优解:S3=1S3u3本期成本C3S4f4(S4)f3(S3)生产存储112345456780.50.50.50.50.54.55.56.57.58.50123476.565.5211.512.012.513.010.5第三阶段最优解:S3=2S3u3本期成本C3S4f4(S4)f3(S3)生产存储2012340456711111156780123476.565.52811.512.012.510.