大学精品课件：Ch8动态规划.ppt

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 Research8.1 动态规划数学模型动态规划数学模型Mathematical M

2、odel of DPv2v3v4v7v5v9v6v8v1028512131071013112865885405847【例【例8-1】最短路径问题最短路径问题 图图81表示从起点表示从起点A到终点到终点E之间各点的距离。求之间各点的距离。求A到到E的最短路径。的最短路径。图图81v1第1阶段第2阶段第3阶段第4阶段阶段：第5阶段1217142019Min2+5,8+8,6+4=7第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 4 2023年3月1日星期三2347596810285121310710131128658854图图8

3、21第1阶段第2阶段第3阶段第4阶段阶段：第5阶段用用WinQSB软件计算时软件计算时,需要对状态重新编号需要对状态重新编号,如下图所示如下图所示.8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 5 2023年3月1日星期三12348576910285121310M10413111128658864用用WinQSB软件计算时软件计算时,当某状态没有路到下阶段某状态时，添加当某状态没有路到下阶段某状态时，添加一条虚拟决策（线条），距离很大

4、，如下图点一条虚拟决策（线条），距离很大，如下图点3到点到点5.8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 6 2023年3月1日星期三动态规划问题具有以下动态规划问题具有以下基本特征基本特征 1.问题具有多阶段决策的特征。阶段可以按时间划分，也问题具有多阶段决策的特征。阶段可以按时间划分，也可以按空间划分。可以按空间划分。2.每一阶段都有相应的每一阶段都有相应的“状态状态”与之对应。与之对应。3.每一阶段都面临一个决策，选择不同的

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

6、数学模型动态规划数学模型Mathematical Model of DP 第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 7 2023年3月1日星期三 5.状态具有无后效性状态具有无后效性 当某阶段状态确定后，此阶段以后过当某阶段状态确定后，此阶段以后过程的发展不受此阶段以前各阶段状态的影响。如下图所示：程的发展不受此阶段以前各阶段状态的影响。如下图所示：9AB1B2B3D1C1C4C3D2E7812121441213651064C2908.1 动态规划数学模型动态规划数学模型Mathematical Model of DP

7、 第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 8 2023年3月1日星期三动态规划基本原理动态规划基本原理是将一个问题的最优解转化为求子问题的最是将一个问题的最优解转化为求子问题的最优解，研究的对象是决策过程的最优化，其变量是流动的时间优解，研究的对象是决策过程的最优化，其变量是流动的时间或变动的状态，最后到达整个系统最优。或变动的状态，最后到达整个系统最优。基本原理一方面基本原理一方面说明原问题的最优解中包含了子问题的最优解，说明原问题的最优解中包含了子问题的最优解，另一方面另一方面给出了一种求解问题的思路，将一个难以

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

9、f DP 第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 9 2023年3月1日星期三（1）阶段阶段(Stage)：表示决策顺序的时段序列，阶段可以按时间：表示决策顺序的时段序列，阶段可以按时间或空间划分，阶段数或空间划分，阶段数k可以是确定数、不定数或无限数可以是确定数、不定数或无限数 8.1.2基本概念基本概念（3）决策决策（Decision）xk：从某一状态向下一状态过度时所做的：从某一状态向下一状态过度时所做的选择。决策变量记为选择。决策变量记为xk，xk是所在状态是所在状态sk的函数。的函数。在状态在状态sk下，允

10、许采取决策的全体称为决策允许集合，记为下，允许采取决策的全体称为决策允许集合，记为Dk(sk)。各阶段所有决策组成的集合称为决策集。各阶段所有决策组成的集合称为决策集。（2）状态状态（State）：描述决策过程当前特征并且具有无后效性）：描述决策过程当前特征并且具有无后效性的量。状态可以是数量，也可以是字符，数量状态可以是连续的，的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。每一状态可以取不同值，状态变量记为也可以是离散的。每一状态可以取不同值，状态变量记为sk。各。各阶段所有状态组成的集合称为状态集。阶段所有状态组成的集合称为状态集。8.1 动态规划数学模型动态规

11、划数学模型Mathematical Model of DP 第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 10 2023年3月1日星期三(4)策略策略(Strategy)：从第：从第1阶段开始到最后阶段全过程的决策构成阶段开始到最后阶段全过程的决策构成的序列称为策略，第的序列称为策略，第k阶段到最后阶段的决策序列称为子策略。阶段到最后阶段的决策序列称为子策略。（5）状态转移方程状态转移方程(State transformation function)：某一状态以：某一状态以及该状态下的决策，与下一状态之间的函数关系，记为及

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

13、 Page 11 2023年3月1日星期三k阶段指标函数阶段指标函数 从从k阶段状态阶段状态sk出发，选择决策出发，选择决策xk所产生的第所产生的第k阶段指标，称为阶段指标，称为k阶段指标函数阶段指标函数,记为记为vk(sk,xk)。从从k阶段状态阶段状态sk出发，选择决策出发，选择决策xk,xk+1,xn所产生的过程指标，所产生的过程指标，称为称为k子过程指标函数或简称过程指标函数，记为子过程指标函数或简称过程指标函数，记为Vk(sk,xk,xk+1,xn)或或Vk，n为阶段数。为阶段数。过程指标函数过程指标函数最优指标函数最优指标函数从从k阶段状态阶段状态sk出发，对所有的子策略，最优的过

14、程指标函数称出发，对所有的子策略，最优的过程指标函数称为最优指标函数，记为为最优指标函数，记为fk(sk)，通常取，通常取Vk的最大值或最小值。的最大值或最小值。),()(,)(nkknksDdkkPsVsfoptkkk （Optoptimization表示表示“max”或或“min”8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 12 2023年3月1日星期三动态规划要求过程指标满足动态规划要求过程指标满足递推关系递推关系，即，即11

15、11(,)(,),(,)kkkknkkkkkknV sxxxV v sxVsxx(8-2)连和形式：连和形式：1111(,)(,(,)(,KKkkknkkkKkknnjjjnj kVVsxxxv sxVsxxv sxV）(8-3)最优指标函数是最优指标函数是 nksfxsvOptsfkkkkksDxkkkkk,2,1),(,()(11)(8-4)8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 13 2023年3月1日星期三动态规划数学模

16、型由式动态规划数学模型由式(8-4)或或(8-6)、边界条件及状态转移方程、边界条件及状态转移方程构成。如连和形式的数学模型构成。如连和形式的数学模型 连乘形式连乘形式(vj0)：1111(,)(,)(,)(,)KKkkknkkkKkknnjjjnj kVVsxxxv sxVsxxv sxV=(8-5)最优指标函数是最优指标函数是 nksfdsvOptsfkkkkksDxkkkkk,2,1),(,()(11)(8-6),(0)(,2,1),(,()(111)(kkknnkkkkksDxkkxsTssfnksfxsvOptsfkkk8.1 动态规划数学模型动态规划数学模型Mathematical

17、 Model of DP 第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 14 2023年3月1日星期三对于可加性指标函数，上式可以写为对于可加性指标函数，上式可以写为nksfxsvsfkkkkksDdkkoptkkk,2,1)(,()(11)(上式中上式中“opt”表示表示“max”或或“min”。对于可乘性指标函数，。对于可乘性指标函数，上式可以写为上式可以写为nksfxsvsfkkkkksDxkkoptkkk,2,1)(,()(11)(上式称为动态规划最优指标的上式称为动态规划最优指标的递推方程递推方程，是动态规划的基

18、本方，是动态规划的基本方程。程。终端条件：终端条件：为了使以上的递推方程有递推的起点，必须要设定为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，即确定最后一个状态最优指标的终端条件，即确定最后一个状态n下最优指标下最优指标fn(sn)的的值。值。8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 15 2023年3月1日星期三用逆序法列表求解例用逆序法列表求解例8-1 k=n=5 时，时，f5(v10)0)(),(min)(

19、55444)(44444sfxsvsfsDxk=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 第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 16 2023年3月1日星期三)(),(min)(44333)(333

20、33sfxsvsfsDxk=3，递推方程为，递推方程为表8-2 s3D3(s3)s4v3(s3,x3)v3(s3,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 第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉

21、理工大学管理学院 熊伟 Page 17 2023年3月1日星期三k=2，递推方程为，递推方程为表表8-3 s2D2(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 5)(),(min)(33222)(22222sfxsvsfsDx8.1 动态规划

22、数学模型动态规划数学模型Mathematical Model of DP 第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 18 2023年3月1日星期三k=1，递推方程为，递推方程为表8-4)(),(min)(22111)(11111sfxsvsfsDxs1D1(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(s

23、1)的值，从的值，从v1到到v10的最短路长为的最短路长为19。最短路。最短路线从表线从表8-4到表到表8-1回朔，查看最后一列最优决策，得到最短路回朔，查看最后一列最优决策，得到最短路径为：径为：v1 v2 v5 v7 v108.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 19 2023年3月1日星期三作业：教材习题作业：教材习题 8.2下一节：资源分配问题下一节：资源分配问题 8.1 动态规划数学模型动态规划数学模型Mathemat

24、ical Model of DP 8.2 资源分配问题资源分配问题Resource Assignment Problem第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 21 2023年3月1日星期三【例【例8-2】公司有资金公司有资金8万元，投资万元，投资A、B、C三个项目，一个单位投资为三个项目，一个单位投资为2万万元。每个项目的投资效益率与投入该项目的资金有关。三个项目元。每个项目的投资效益率与投入该项目的资金有关。三个项目A、B、C的的投资效益投资效益(万元万元)和投入资金（万元）的关系见表和投入资金（万元）的关系见表

25、8-5。求对三个项目的最优投求对三个项目的最优投资分配，使总投资效益最大。资分配，使总投资效益最大。8.2 资源分配问题资源分配问题Resource Assignment Problem 项目项目投入资金投入资金ABC2万元万元89104万元万元1520286万元万元3035358万元万元384043表表8-5【解】设【解】设xk为第为第k个项目的投资，该问题的静态规划模型为个项目的投资，该问题的静态规划模型为112233123max()()()80,2,4,6,8jZv xv xv xxxxx第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院

26、 熊伟 Page 22 2023年3月1日星期三阶段阶段k：每投资一个项目作为一个阶段，：每投资一个项目作为一个阶段，k=1,2,3,4。k=4为虚设为虚设的阶段的阶段状态变量状态变量sk：投资第：投资第k个项目前的资金数个项目前的资金数决策变量决策变量xk：第：第k个项目的投资额个项目的投资额决策允许集合：决策允许集合：0 xksk状态转移方程：状态转移方程：sk+1=skxk阶段指标：阶段指标：vk(sk，xk)见表见表8-5中的数据中的数据 递推方程：递推方程：11()max(,)()kkkkkkkfxv sxfs终端条件：终端条件：f4(s4)=0数学模型为数学模型为 11144()m

27、ax(,)(),3,2,1()00,2,4,6,8,1,2,3kkkkkkkkkkkfxvsxfskssxfxxk8.2 资源分配问题资源分配问题Resource Assignment Problem第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 23 2023年3月1日星期三k=4，终端条件f4(s4)=0。k=3，0 x3s3，s4=s3x3 状态状态s3决策决策x3(s3)状态转移方程状态转移方程s4=s3x3阶段指标阶段指标v3(s3,x3)过程指标过程指标v3(s3,x3)+f4(s4)最优指标最优指标f3(s3)

28、最优决策最优决策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 资源分配问题资源分配问题Resource Assignment Problem第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 24 2023年3月1日星期

29、三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=43484269359+35=4444202820+28=48*62351035+10=458040040+0=40k=2，0 x2s2，s3=s2x2 8.2 资源分配问题资源分配问题Resource As

30、signment Problem第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 25 2023年3月1日星期三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=4362301030+10=408038038+0=38最优解为最优解为:s1=8,x1*=0,s2=s1x1*=8,x2*=4,s3=s2x2*=4,x3*=4,s4=s3x3*=0。投资的最优策略

31、是，项目投资的最优策略是，项目A不投资，项目不投资，项目B投资投资4万元，项目万元，项目C投投资资4万元，最大效益为万元，最大效益为48万元万元 8.2 资源分配问题资源分配问题Resource Assignment Problem第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 26 2023年3月1日星期三【例【例8-3】某种设备可在高低两种不同的负荷下进行生产，设在】某种设备可在高低两种不同的负荷下进行生产，设在高负荷下投入生产的设备数量为高负荷下投入生产的设备数量为x,产量为产量为g=10 x，设备年完好率设备年完好率

32、为为a=0.75；在低负荷下投入生产的设备数量为；在低负荷下投入生产的设备数量为y，产量为产量为h=8y，年完好率为年完好率为b=0.9。假定开始生产时完好的设备数量。假定开始生产时完好的设备数量s1=100。制定一个五年计划，确定每年投入高、低两种负荷下生产的设制定一个五年计划，确定每年投入高、低两种负荷下生产的设备数量，使五年内产品的总产量达到最大。备数量，使五年内产品的总产量达到最大。阶段阶段k：运行年份运行年份（k=1,2,3,4,5,6），），k=1表示第一年初，表示第一年初，k=6表示第五年末（即第六年初）；表示第五年末（即第六年初）；状态变量状态变量sk：第第k年初完好的机器数（

33、年初完好的机器数（k=1,2,3,4,5,6），也是第），也是第k1年末完好的机器数，其中年末完好的机器数，其中s6表示第五年末（即第六年初）的表示第五年末（即第六年初）的完好机器数，完好机器数，s1100。决策变量决策变量xk：第第k年初投入高负荷运行的机器数；年初投入高负荷运行的机器数；状态转移方程：状态转移方程：sk+1=0.75xk+0.9(skxk)8.2 资源分配问题资源分配问题Resource Assignment Problem第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 27 2023年3月1日星期三决策

34、允许集合：决策允许集合：Dk(sk)=xk|0 xk sk阶段指标：阶段指标：vk(sk，xk)=10 xk+8(skxk)终端条件终端条件：f6(s6)=0递推方程：递推方程：)(9.075.0)(810max)(),(max)(1011)(kkkkkkksxkkkkksDxkkxsxfxsxsfxsvsfkkkkk555555555556605550*555550()max 108()()max 108()max 2810 xsxsxsf sxsxfsxsxxssxs时最优8.2 资源分配问题资源分配问题Resource Assignment Problem第第8章章 动态规划动态规划Dy

35、namic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 28 2023年3月1日星期三4444444444444550444504444440*444440()max 108()()max 108()10max 108()10(0.750.9()max0.517 17.5xsxsxsxsfsxsxf sxsxsxsxxsxxssxs 时最优3333333333333440333403333330*33330()max 108()()max 108()17.5max 108()17.5(0.750.9()max 0.62523.75 23.750 xsxsxsxsf

36、 sxsxfsxsxsxsxxsxxssx 时最优8.2 资源分配问题资源分配问题Resource Assignment Problem第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 29 2023年3月1日星期三2222222222222330222302222220*22220()max 108()()max 108()23.75max 108()23.75(0.750.9()max 1.562529.375 29.3750 xsxsxsxsfsxsxf sxsxsxsxxsxxssx 时最优11111111111112

37、20111201111110*11110()max 108()()max 108()29.375max 108()29.375(0.750.9()max 2.40634.4375 34.43750 xsxsxsxsf sxsxfsxsxsxsxxsxxssx 时最优8.2 资源分配问题资源分配问题Resource Assignment Problem第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 30 2023年3月1日星期三因为因为s1=100，五年的最大总产量为，五年的最大总产量为f1(s1)=25.7525100344

38、3.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.75x3+0.9(s3x3)=73x4*=s4=73，s5=0.75x4+0

39、.9(s4x4)=55x5*=s5=55，s6=0.75x5+0.9(s5x5)=41第五年末还有41台完好设备。8.2 资源分配问题资源分配问题Resource Assignment Problem第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 31 2023年3月1日星期三一般地，设一个周期为一般地，设一个周期为n年，高负荷生产时设备的完好率为年，高负荷生产时设备的完好率为a，单台产量为单台产量为g；低负荷完好率为；低负荷完好率为b，单台产量为，单台产量为h。若有。若有t满足满足100()n tn tiiiighaag

40、ba 则最优设备分配策略是：从则最优设备分配策略是：从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 资源分配问题资源分

41、配问题Resource Assignment Problem(8-7)第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 32 2023年3月1日星期三作业：教材习题作业：教材习题 8.1，8.6，8.8，8.98.2 资源分配问题资源分配问题Resource Assignment Problem下一节：生产与存储问题下一节：生产与存储问题8.3 生产与存储问题生产与存储问题Production and inventory problem第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学

42、管理学院 熊伟 Page 34 2023年3月1日星期三8.3 生产与存储问题生产与存储问题Production and inventory problem【8-4】一个工厂生产某种产品，】一个工厂生产某种产品，16月份生产成本和产品需求量月份生产成本和产品需求量的变化情况见表的变化情况见表8-9 月份月份(k)123456需求量需求量(dk)203035402545单位产品成本单位产品成本(ck)151216191816表表8-9没有生产准备成本，单位产品一个月的存储费为没有生产准备成本，单位产品一个月的存储费为hk0.6元，元，月底交货。分别求下列两种情形月底交货。分别求下列两种情形6个月

43、总成本最小的生产方案。个月总成本最小的生产方案。（1）1月初与月初与6月底存储量为零，不允许缺货，仓库容量为月底存储量为零，不允许缺货，仓库容量为S=50件，生产能力无限制；件，生产能力无限制；（2）其它条件不变，）其它条件不变，1月初存量为月初存量为10 第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 35 2023年3月1日星期三8.3 生产与存储问题生产与存储问题Production and inventory problem【解】动态规划求解过程如下。【解】动态规划求解过程如下。阶段阶段k：月份，：月份，k=1,2,

44、7状态变量状态变量sk：第：第k个月初的库存量个月初的库存量决策变量决策变量xk：第：第k个月的生产量个月的生产量状态转移方程：状态转移方程：sk+1=sk+xkdk 决策允许集合决策允许集合:500,0)(kkkkkkkdxsxxsD阶段指标：阶段指标：(,)0.6kkkkkkkkkkv sxc xh sc xs终端条件：终端条件：f7(s7)=0,s7=0递推方程：递推方程：)(),(min)(),(min)(1)(11)(kkkkkkkkskDkxkkkkkkskDkxkkdxsfxsvsfxsvxf第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工

45、大学管理学院 熊伟 Page 36 2023年3月1日星期三8.3 生产与存储问题生产与存储问题Production and inventory problem当当k=6时，因为时，因为s7=0，有，有 766666666450,45,45ssxdsxxs s6666666677456645*666()min160.6()min160.615.472045xsxsfsxsfsxssxs 当当k=5时，时，65555555504525 45,2570ssxdsxsxs由，0得由于由于s550，则当，则当25s50时时x5的值取的值取“0”，决策允许集合为，决策允许集合为 555555()max0

46、,2570D sxsxs555555555555566()556()55655()*5555*555()min180.6()min180.615.4720min2.614.81105(25)17.41170252514.81105250 xDsxDsxDsf sxsfsxssxsssxssxsssx其中时,取下界：时,取下界：第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 37 2023年3月1日星期三8.3 生产与存储问题生产与存储问题Production and inventory problemk=4时，5440254

47、025,ssx，0有44465sxs40决策允许集合为决策允许集合为 444444()max0,4065D sxsxs444444444444455()445()44()*4444*444()min190.6()min190.617.41170min1.616.8186618.4193040,4016.818664050,0 xDsxDsxDsfsxsf sxssxsssxsssx554425504050,sxsx，=0,25有444444()6590Dsxsxs444444444(1)444455()445()44()*444()min190.6()min190.614.81105min4.

48、214.2169718.4197065xDsxDsxDsfsxsf sxssxssxs 取下界：第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 38 2023年3月1日星期三8.3 生产与存储问题生产与存储问题Production and inventory problem显然该决策不可行显然该决策不可行,x5=0，s4+x4=65d4+d5，s5=s4+x4d4=65-40=25，与，与s525矛盾。因此有矛盾。因此有 k=3，当，当0s440时，时，*4444555*4444455518.41930 040,40025,

49、25()16.81866 4050,0025,25ssxssxsf sssxsxs并且并且333540s+x0333333()max0,3575D sxsxs333333333333344()334()33()*333()min160.6()min160.618.41930min2.417.8257415.4239475xDsxDsxDsf sxsfsxssxssxs 取上界：第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 39 2023年3月1日星期三8.3 生产与存储问题生产与存储问题Production and inv

50、entory problem当当40s450时，时，33403550s+x333333()7585D sxsxs333333333333344()334()33()*333()min160.6()min160.616.81866min0.816.2245415.4238685xDsxDsxDsf sxsfsxssxssxs 取上界：当当k=2时，由时，由 43224050,0503050,sssx，0有22280sxs30 x2的决策允许集合为的决策允许集合为 222222()max0,3080D sxsxs22222222222223330652233065223065*222()min12