Ch8动态规划F.ppt

《Ch8动态规划F.ppt》由会员分享，可在线阅读，更多相关《Ch8动态规划F.ppt（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八章第八章 动态规划动态规划Dynamic Programming 8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 8.2 资源分配问题资源分配问题 Resource Assignment Problem8.3 生产与存储问题生产与存储问题Production and inventory problem8.4 背包问题背包问题 Knapsack Problem8.5 其它动态规划模型其它动态规划模型 Other Model of DP运筹学运筹学Operations Research4/12/20238.1 动态规划数学模型动态规划数学模型Mathe

2、matical Model of DP4/12/2023v2v3v4v7v5v9v6v8v1028512131071013112865885405847【例例8.1】最短路径问题最短路径问题 图图81表示从起点表示从起点A到终点到终点E之间各之间各点的距离。求点的距离。求A到到E的最短路径。的最短路径。图图81v1第1阶段第2阶段第3阶段第4阶段阶段：第5阶段1217142019Min2+5,8+8,6+4=74/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 4 2347596810285121310710

3、131128658854图图821第1阶段第2阶段第3阶段第4阶段阶段：第5阶段用用WinQSB软件计算时软件计算时,需要对状态重新编号需要对状态重新编号,如下图所示如下图所示.8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 5 12348576910285121310M10413111128658864用用WinQSB软件计算时软件计算时,当某状态没有路到下阶段某状态时，添加当某状态没有路到下阶段某状态时，添加一条

4、虚拟决策（线条），距离很大，如下图点一条虚拟决策（线条），距离很大，如下图点3到点到点5.8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 6 动态规划问题具有以下动态规划问题具有以下基本特征基本特征 1.问问题题具具有有多多阶阶段段决决策策的的特特征征。阶阶段段可可以以按按时时间间划划分分，也也可以按空间划分。可以按空间划分。2.每一阶段都有相应的每一阶段都有相应的“状态状态”与之对应。与之对应。3.每每一一阶阶段段

5、都都面面临临一一个个决决策策，选选择择不不同同的的决决策策将将会会导导致致下下一一阶阶段段不不同同的的状状态态，同同时时，不不同同的的决决策策将将会会导导致致这这一一阶阶段段不不同同的目标函数值。的目标函数值。4.每每一一阶阶段段的的最最优优解解问问题题可可以以递递归归地地归归结结为为下下一一阶阶段段各各个个可可能能状状态态的的最最优优解解问问题题，各各子子问问题题与与原原问问题题具具有有完完全全相相同同的的结结构构。能能否否构构造造这这样样的的递递推推归归结结，是是解解决决动动态态规规划划问问题题的的关关键键。这种递推归结的过程，称为这种递推归结的过程，称为“不变嵌入不变嵌入”。8.1 动态

6、规划数学模型动态规划数学模型Mathematical Model of DP 4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 7 5.状态具有无后效性状态具有无后效性 当某阶段状态确定后，此阶段以后过当某阶段状态确定后，此阶段以后过程的发展不受此阶段以前各阶段状态的影响。如下图所示：程的发展不受此阶段以前各阶段状态的影响。如下图所示：9AB1B2B3D1C1C4C3D2E7812121441213651064C2908.1 动态规划数学模型动态规划数学模型Mathematical Model of DP

7、4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 8 动态规划基本原理动态规划基本原理是将一个问题的最优解转化为求子问题的最是将一个问题的最优解转化为求子问题的最优解，研究的对象是决策过程的最优化，其变量是流动的时间优解，研究的对象是决策过程的最优化，其变量是流动的时间或变动的状态，最后到达整个系统最优。或变动的状态，最后到达整个系统最优。基本原理一方面基本原理一方面说明原问题的最优解中包含了子问题的最优解，说明原问题的最优解中包含了子问题的最优解，另一方面另一方面给出了一种求解问题的思路，将一个难以直接解

8、决的给出了一种求解问题的思路，将一个难以直接解决的大问题，分割成一些规模较小的相同子问题，每一个子问题只大问题，分割成一些规模较小的相同子问题，每一个子问题只解一次，并将结果保存起来以后直接引用，避免每次碰到时都解一次，并将结果保存起来以后直接引用，避免每次碰到时都要重复计算，以便各个击破，分而治之，即分治法，是一种解要重复计算，以便各个击破，分而治之，即分治法，是一种解决最优化问题的算法策略。决最优化问题的算法策略。动态规划求解可分为三个步骤动态规划求解可分为三个步骤：分解、求解与合并。：分解、求解与合并。8.1 动态规划数学模型动态规划数学模型Mathematical Model of D

9、P 4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 9（1）阶段阶段(Stage)：表示决策顺序的时段序列，阶段可以按时间表示决策顺序的时段序列，阶段可以按时间或空间划分，阶段数或空间划分，阶段数k可以是确定数、不定数或无限数可以是确定数、不定数或无限数 8.1.2基本概念基本概念（2）状态状态（State）：）：描述决策过程当前特征并且具有无后效性描述决策过程当前特征并且具有无后效性的量。状态可以是数量，也可以是字符，数量状态可以是连续的，的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以

10、是离散的。每一状态可以取不同值，状态变量记为也可以是离散的。每一状态可以取不同值，状态变量记为sk。各各阶段所有状态组成的集合称为状态集。阶段所有状态组成的集合称为状态集。8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 10（3）决策决策（Decision）xk：从某一状态向下一状态过度时所做的从某一状态向下一状态过度时所做的选择。决策变量记为选择。决策变量记为xk，xk是所在状态是所在状态sk的函数。的函数。在状态

11、在状态sk下，允许采取决策的全体称为决策允许集合，记为下，允许采取决策的全体称为决策允许集合，记为Dk(sk)。各阶段所有决策组成的集合称为决策集。各阶段所有决策组成的集合称为决策集。(4)策略策略(Strategy)：从第从第1阶段开始到最后阶段全过程的决策构阶段开始到最后阶段全过程的决策构成的序列称为策略，第成的序列称为策略，第k阶段到最后阶段的决策序列称为子策略。阶段到最后阶段的决策序列称为子策略。4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 11（5）状态转移方程状态转移方程(State tra

12、nsformation function)：某一状态某一状态以及该状态下的决策，与下一状态之间的函数关系，记为以及该状态下的决策，与下一状态之间的函数关系，记为sk+1=T(sk,xk)（6）指标函数或收益函数指标函数或收益函数(Return function)：是衡量对决策过是衡量对决策过程进行控制的效果的数量指标，具体可以是收益、成本、距离程进行控制的效果的数量指标，具体可以是收益、成本、距离等指标。分为等指标。分为k阶段指标函数、阶段指标函数、k子过程指标函数及最优指标函子过程指标函数及最优指标函数。数。8.1 动态规划数学模型动态规划数学模型Mathematical Model of

13、DP 4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 12 k阶段指标函数阶段指标函数 从从k阶段状态阶段状态sk出发，选择决策出发，选择决策xk所产生的第所产生的第k阶段指标，称为阶段指标，称为k阶段指标函数阶段指标函数,记为记为vk(sk,xk)。从从k阶段状态阶段状态sk出发，选择决策出发，选择决策xk,xk+1,xn所产生的过程指标，所产生的过程指标，称为称为k子过程指标函数或简称过程指标函数，记为子过程指标函数或简称过程指标函数，记为Vk(sk,xk,xk+1,xn)或或Vk，n为阶段数。为阶段

14、数。过程指标函数过程指标函数8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 13 最优指标函数最优指标函数从从k阶段状态阶段状态sk出发，对所有的子策略，最优的过程指标函数称出发，对所有的子策略，最优的过程指标函数称为最优指标函数，记为为最优指标函数，记为fk(sk)，通常取通常取Vk的最大值或最小值。的最大值或最小值。（Optoptimization表示表示“max”或或“min”4/12/2023第第8章章 动态

15、规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 14 动态规划要求过程指标满足动态规划要求过程指标满足递推关系递推关系，即，即(8.2)连和形式：连和形式：(8.3)最优指标函数是最优指标函数是(8.4)8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 15 动态规划数学模型由式动态规划数学模型由式(8.4)或或(8.6)、边界条件及状态转移方、边界条件及状态转移

16、方程构成。如连和形式的数学模型程构成。如连和形式的数学模型 连乘形式连乘形式(vj0)：(8.5)最优指标函数是最优指标函数是(8.6)8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 16 对于可加性指标函数，上式可以写为对于可加性指标函数，上式可以写为上上式式中中“opt”表表示示“max”或或“min”。对对于于可可乘乘性性指指标标函函数数，上式可以写为上式可以写为上上式式称称为为动动态态规规划划最最优优指指标标

17、的的递递推推方方程程，是是动动态态规规划划的的基基本本方方程。程。终终端端条条件件：为为了了使使以以上上的的递递推推方方程程有有递递推推的的起起点点，必必须须要要设设定定最最优优指指标标的的终终端端条条件件，即即确确定定最最后后一一个个状状态态n下下最最优优指指标标fn(sn)的的值。值。8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 17 用逆序法列表求解例用逆序法列表求解例8.1 k=n=5 时，时，f5(v10

18、)0 k=4，递推方程为递推方程为 s4D4(s4)s5v4(s4,x4)v4(s4,x4)+f5(s5)f4(s4)最优决策最优决策x4*v7v7v10v1055+0=5*5v7 v10v8v8v10v1088+08*8v8 v10v9v9v10v1044+0=4*4v9 v108.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 18 k=3，递推方程为递推方程为表8-2 s3D3(s3)s4v3(s3,x3)v3(s

19、3,x3)+f4(s4)f3(s3)最优决策最优决策x3*v5v5v7 7v v5 5v8 8v v5 5v9 9v7v8v92862+5=7*8+8=166+4=107v5v7 7v6v6 v7 7v v6 6v8 8v v6 6v9 9v7v8v9125812+5=175+8=138+4=12*12v6v9 98.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 19 k=2，递推方程为递推方程为表表8-3 s2D2(

20、s2)s3v2(s2,x2)v2(s2,x2)+f3(s3)f2(s2)最优决策最优决策x2*v2v2 v5 5v v2 2 v6 6v5v6101310+7=17*13+12=2517v2 v5 5v3v3 v5 5v v3 3 v6 6v5v67107+7=14*10+12=2214v3v5 5v4v4 v5 5v v4 4 v6 6v5v6131113+7=20*11+12=2320v4v5 58.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大

21、数学科学学院 李湖南 Page 20 k=1，递推方程为递推方程为表8-4 s1D1(s1)s2v1(s1,x1)v1(s1,x1)+f2(s2)f1(s1)最优决策最优决策x1*v1v1v2 2v v1 1v3 3v v1 1v4 4v2v3v42852+17=19*8+14=225+20=2519v1v2 2最优值是表最优值是表8-4中中f1(s1)的值，从的值，从v1到到v10的最短路长为的最短路长为19。最短。最短路线从表路线从表8-4到表到表8-1回朔，查看最后一列最优决策，得到最短回朔，查看最后一列最优决策，得到最短路径为：路径为：v1 v2 v5 v7 v108.1 动态规划数学

22、模型动态规划数学模型Mathematical Model of DP 4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 21 作业：教材作业：教材P188 T2下一节：资源分配问题下一节：资源分配问题 8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 4/12/20238.2 资源分配问题资源分配问题Resource Assignment Problem4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学

23、院 李湖南 Page 23【例例8.2】公公司司有有资资金金8万万元元，投投资资A、B、C三三个个项项目目，一一个个单单位位投投资资为为2万万元元。每每个个项项目目的的投投资资效效益益率率与与投投入入该该项项目目的的资资金金有有关关。三三个个项项目目A、B、C的的投投资资效效益益(万万元元)和和投投入入资资金金（万万元元）的的关关系系见见表表8-5。求求对对三三个个项项目目的的最最优优投资分配，使总投资效益最大。投资分配，使总投资效益最大。8.2 资源分配问题资源分配问题Resource Assignment Problem 项目项目投入资金投入资金ABC2万元万元89104万元万元15202

24、86万元万元3035358万元万元384043表表8-54/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 24【解解】设设xk为第为第k个项目的投资，该问题的静态规划模型为个项目的投资，该问题的静态规划模型为阶段阶段k：每投资一个项目作为一个阶段，每投资一个项目作为一个阶段，k=1,2,3,4。k=4为虚设为虚设的阶段的阶段状态变量状态变量sk：投资第投资第k个项目前的资金数个项目前的资金数决策变量决策变量xk：第：第k个项目的投资额个项目的投资额决策允许集合：决策允许集合：0 xksk状态转移方程：状态转

25、移方程：sk+1=skxk阶段指标：阶段指标：vk(sk，xk)见表见表8-5中的数据中的数据 4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 25 递推方程：递推方程：终端条件：终端条件：f4(s4)=0数学模型为数学模型为 8.2 资源分配问题资源分配问题Resource Assignment Problem4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 26 k=4，终端条件f4(s4)=0。k=3，0 x3s

26、3，s4=s3x3 状态状态s3决策决策x3(s3)状态转移方程状态转移方程s4=s3x3阶段指标阶段指标v3(s3,x3)过程指标过程指标v3(s3,x3)+f4(s4)最优指标最优指标f3(s3)最优决策最优决策x3*00000+0=00020200+0=0102201010+0=10*40400+0=0284221010+0=10402828+0=28*60600+0=0356241010+0=10422828+0=28603535+0=35*80800+0=0438261010+0=10442828+0=28623535+0=35804343+0=43*8.2 资源分配问题资源分配问题

27、Resource Assignment Problem4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 27 s2x2(s2)s3v2(s2,x2)f3(s3)v2(s2,x2)+f3(s3)f2(s2)x2*000000+0=0002020100+10=10*10020909+0=94040280+28=28*280229109+10=194020020+0=206060350+35=35372249289+28=37*42201020+10=306035035+0=358080430+43=434842

28、69359+35=4444202820+28=48*62351035+10=458040040+0=40k=2，0 x2s2，s3=s2x2 8.2 资源分配问题资源分配问题Resource Assignment Problem4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 28 k=1，0 x1s1，s2=s1x1 s1x1(s1)s2v1(s1,x1)f2(s2)v1(s1,x1)+f2(s2)f1(s1)x1*8080480+48=48*480268378+37=4544152815+28=4362

29、301030+10=408038038+0=38最优解为最优解为:s1=8,x1*=0,s2=s1x1=8,x2*=4,s3=s2x2*=4,x3=4,s4=s3x3=0。投资的最优策略是，项目投资的最优策略是，项目A不投资，项目不投资，项目B投资投资4万元，项目万元，项目C投投资资4万元，最大效益为万元，最大效益为48万元万元 8.2 资源分配问题资源分配问题Resource Assignment Problem4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 29【例例8.3】某种设备可在高低两种不同的

30、负荷下进行生产，设在某种设备可在高低两种不同的负荷下进行生产，设在高负荷下投入生产的设备数量为高负荷下投入生产的设备数量为x,产量为产量为g=10 x，设备年完好率设备年完好率为为a=0.75；在低负荷下投入生产的设备数量为在低负荷下投入生产的设备数量为y，产量为产量为h=8y，年完好率为年完好率为b=0.9。假定开始生产时完好的设备数量假定开始生产时完好的设备数量s1=100。制定一个五年计划，确定每年投入高、低两种负荷下生产的设制定一个五年计划，确定每年投入高、低两种负荷下生产的设备数量，使五年内产品的总产量达到最大。备数量，使五年内产品的总产量达到最大。8.2 资源分配问题资源分配问题R

31、esource Assignment Problem4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 30 阶段阶段k：运行年份运行年份（k=1,2,3,4,5,6），），k=1表示第一年初，表示第一年初，k=6表表示第五年末（即第六年初）；示第五年末（即第六年初）；状态变量状态变量sk：第第k年初完好的机器数（年初完好的机器数（k=1,2,3,4,5,6），），也是第也是第k1年末完好的机器数，其中年末完好的机器数，其中s6表示第五年末（即第六年初）的表示第五年末（即第六年初）的完好机器数，完好机器数，s

32、1100。决策变量决策变量xk：第第k年初投入高负荷运行的机器数；年初投入高负荷运行的机器数；状态转移方程：状态转移方程：sk+1=0.75xk+0.9(skxk)决策允许集合：决策允许集合：Dk(sk)=xk|0 xk sk阶段指标：阶段指标：vk(sk，xk)=10 xk+8(skxk)终端条件终端条件：f6(s6)=04/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 31 递推方程：递推方程：8.2 资源分配问题资源分配问题Resource Assignment Problem4/12/2023第第8

33、章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 32 8.2 资源分配问题资源分配问题Resource Assignment Problem4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 33 8.2 资源分配问题资源分配问题Resource Assignment Problem4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 34 因为因为s1=100

34、，五年的最大总产量为五年的最大总产量为f1(s1)=25.75251003443.75。由由x1*=x2*=x3*=0，x4*s4，x5*s5，设备的最优分配策略是，设备的最优分配策略是，第一年至第三年将设备全部用于低负荷运行，第四年和第五年将第一年至第三年将设备全部用于低负荷运行，第四年和第五年将设备全部用于高负荷运行。每年投入高负荷运行的机器数以及每设备全部用于高负荷运行。每年投入高负荷运行的机器数以及每年初完好的机器数为：年初完好的机器数为：s1=100 x1*=0,s2=0.75x1+0.9(s1x1)=90 x2*=0,s3=0.75x2+0.9(s2x2)=81x3*=0，s4=0

35、.75x3+0.9(s3x3)=73x4*=s4=73，s5=0.75x4+0.9(s4x4)=55x5*=s5=55，s6=0.75x5+0.9(s5x5)=41第五年末还有41台完好设备。8.2 资源分配问题资源分配问题Resource Assignment Problem4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 35 一般地，设一个周期为一般地，设一个周期为n年，高负荷生产时设备的完好率为年，高负荷生产时设备的完好率为a，单台产量为单台产量为g；低负荷完好率为低负荷完好率为b，单台产量为单台产

36、量为h。若有若有t满足满足则最优设备分配策略是：从则最优设备分配策略是：从1t1年，年初将全部完好设备投年，年初将全部完好设备投入低负荷运行，从入低负荷运行，从tn年，年初将全部完好设备投入高负荷运年，年初将全部完好设备投入高负荷运行，总产量达到最大行，总产量达到最大.在例在例8.3中，中，n=5，a=0.75，b=0.9，g=10，h=8，(g-h)/g(b-a)=1.3333式式(8.7)的求和式是完好率的求和式是完好率a的的i次方累加次方累加.由由a0=11.3333a0+a11.75知，知，nt10，t=4，则，则13年低负年低负荷运行，荷运行，45年为高负荷运行年为高负荷运行 8.2

37、 资源分配问题资源分配问题Resource Assignment Problem(8.7)4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 36 作业：教材作业：教材P188 T1，6，8，98.2 资源分配问题资源分配问题Resource Assignment Problem下一节：下一节：生产与存储问题生产与存储问题4/12/20238.3 生产与存储问题生产与存储问题Production and inventory problem4/12/2023第第8章章 动态规划动态规划Dynamic Progr

38、amming 制作与教学 华南师大数学科学学院 李湖南 Page 38 8.3 生产与存储问题生产与存储问题Production and inventory problem【8.4】一个工厂生产某种产品，一个工厂生产某种产品，16月份生产成本和产品需求量月份生产成本和产品需求量的变化情况见表的变化情况见表8-9 月份月份(k)123456需求量需求量(dk)203035402545单位产品成本单位产品成本(ck)151216191816表表8-9没有生产准备成本，单位产品一个月的存储费为没有生产准备成本，单位产品一个月的存储费为hk0.6元，元，月底交货。分别求下列两种情形月底交货。分别求下列

39、两种情形6个月总成本最小的生产方案。个月总成本最小的生产方案。（1）1月初与月初与6月底存储量为零，不允许缺货，仓库容量为月底存储量为零，不允许缺货，仓库容量为S=50件，生产能力无限制；件，生产能力无限制；（2）其它条件不变，）其它条件不变，1月初存量为月初存量为10 4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 39 8.3 生产与存储问题生产与存储问题Production and inventory problem【解解】动态规划求解过程如下。动态规划求解过程如下。阶段阶段k：月份，月份，k=1,

40、2,7状态变量状态变量sk：第：第k个月初的库存量个月初的库存量决策变量决策变量xk：第：第k个月的生产量个月的生产量状态转移方程：状态转移方程：sk+1=sk+xkdk 决策允许集合决策允许集合:阶段指标：阶段指标：终端条件：终端条件：f7(s7)=0,s7=0递推方程：递推方程：4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 40 8.3 生产与存储问题生产与存储问题Production and inventory problem当当k=6时，因为时，因为s7=0，有有 当当k=5时，时，由于由于s5

41、50，则当则当25s50时时x5的值取的值取“0”，决策允许集合为，决策允许集合为 4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 41 8.3 生产与存储问题生产与存储问题Production and inventory problemk=4时，决策允许集合为决策允许集合为 4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 42 8.3 生产与存储问题生产与存储问题Production and inventory p

42、roblem显然该决策不可行，显然该决策不可行，x5=0，s4+x4=65d4+d5，s5=s6=0，x6=45，与，与s525矛盾。因此有矛盾。因此有 k=3，当，当0s440时，时，4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 43 8.3 生产与存储问题生产与存储问题Production and inventory problem当当40s450时，时，当当k=2时，由时，由 x2的决策允许集合为的决策允许集合为 4/12/2023第第8章章 动态规划动态规划Dynamic Programming

43、 制作与教学 华南师大数学科学学院 李湖南 Page 44 8.3 生产与存储问题生产与存储问题Production and inventory problem当当k=1时，由时，由 只要期初存量只要期初存量s120，则，则x1的决策允许集合为的决策允许集合为(1)期初存储量期初存储量s1=0，由各阶段的最优决策由各阶段的最优决策xj*及状态转移方程，及状态转移方程，回朔可求出最优策略。回朔可求出最优策略。4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 45 8.3 生产与存储问题生产与存储问题Produ

44、ction and inventory problemx1=20，s2=s1+x1d1=0+20200，x2=80，s3=s2+x2d2=0+803050，x3=855035，s4=s3+x3d3=50+35355040，x40，s5=500401025，x525s515，s6=1015250，x645。总成本为总成本为2876(2)期初存储量期初存储量s1=10，与前面计算类似，得到与前面计算类似，得到x110，x280，x335，x40，x515，x645。16月份生产、存储详细计划表见表月份生产、存储详细计划表见表8-10所示。所示。4/12/2023第第8章章 动态规划动态规划Dyna

45、mic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 46 8.3 生产与存储问题生产与存储问题Production and inventory problem表表8-10月份月份(k)123456合计合计需求量需求量(dk)203035402545195单位产品成本单位产品成本(ck)151216191816单位存储费单位存储费hk0.60.60.60.60.60.6产量产量xk20803501545195期初存量期初存量sk005050100110生产成本生产成本CK(xk)30096056002707202810存储成本存储成本Hk(sk)003030606

46、6合计合计28764/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 47 8.3 生产与存储问题生产与存储问题Production and inventory problem4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 48 8.3 生产与存储问题生产与存储问题Production and inventory problem作业：教材作业：教材P189 T 7下一节：背包问题下一节：背包问题 4/12/20238.4

47、 背包问题背包问题Knapsack Problem4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 50 8.4 背包问题背包问题Knapsack Problem背包问题数学模型为背包问题数学模型为式中：式中：ck为第为第k种物品的单位价值，种物品的单位价值，wk是第是第k种物品的单位重量或体积，种物品的单位重量或体积，W是背包的重量或体积限制。动态规划的有关要素如下。是背包的重量或体积限制。动态规划的有关要素如下。阶段阶段k：第：第k次装载第次装载第k种物品（种物品（k=1,2,n）状态变量状态变量sk：

48、第：第k次装载时背包还可以装载的重量次装载时背包还可以装载的重量(或体积或体积)决策变量决策变量xk：第：第k次装载第次装载第k种物品的件数种物品的件数决策允许集合：决策允许集合：Dk(sk)=dk|0 xk sk/wk，xk为整数为整数状态转移方程：状态转移方程：sk+1=skwkxk阶段指标：阶段指标：vk=ckxk4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 51 8.4 背包问题背包问题Knapsack Problem递推方程：递推方程：终端条件：终端条件：fn1(sn1)=0【例例8.5】用动

49、态规划方法求解下列整数规划用动态规划方法求解下列整数规划【解解】终端条件：终端条件：f4(x4)=0 k=3时，递推方程时，递推方程4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 52 8.4 背包问题背包问题Knapsack Problem表表8-11s3D3(s3)=x3|s3/5s460 x3+f4(s4)f3(s3)x3*0000+0=0001010+0=0000501500+0=060+0=60*060111001210500+0=6060+0=60120+0=120*1202最优决策是；最优决

50、策是；s3为为04时，时，x30，s3为为59时，时，x31，s310时，时，x32。k=2时，递推方程时，递推方程4/12/2023第第8章章 动态规划动态规划Dynamic Programming 制作与教学 华南师大数学科学学院 李湖南 Page 53 8.4 背包问题背包问题Knapsack Problem表表8-12 s2D2(s2)s340 x2+f3(s3)f2(s2)x2*0000+f3(0)=0+0=0*001 0 10+0000201200+0=040+0=40*401301310+0=040+0=40*40140124200+0=040+0=4080+0=80802501