《运筹学课件Ch8动态规划》由会员分享，可在线阅读，更多相关《运筹学课件Ch8动态规划（66页珍藏版）》请在金锄头文库上搜索。
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 Research7/21/20248.1 动态规划数学模型动态规划数学模型Mathe
2、matical Model of DP7/21/2024v2v3v4v7v5v9v6v8v1028512131071013112865885405847【例例8.1】最短路径问题最短路径问题 图图81表示从起点表示从起点A到终点到终点E之间各点的距离。求之间各点的距离。求A到到E的最短路径。的最短路径。 图图81v1第1阶段第2阶段第3阶段第4阶段阶段：第5阶段1217142019Min2+5,8+8,6+4=77/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 4 234759681028512131071
3、0131128658854图图821第1阶段第2阶段第3阶段第4阶段阶段：第5阶段用用WinQSB软件计算时软件计算时,需要对状态重新编号需要对状态重新编号,如下图所示如下图所示.8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 5 12348576910285121310M10413111128658864用用WinQSB软件计算时软件计算时,当某状态没有路到下阶段某状态时，添加当某状态没有路到下阶段某状态时，添加一
4、条虚拟决策（线条），距离很大，如下图点一条虚拟决策（线条），距离很大，如下图点3到点到点5.8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 6 动态规划问题具有以下动态规划问题具有以下基本特征基本特征 1. 问问题题具具有有多多阶阶段段决决策策的的特特征征。阶阶段段可可以以按按时时间间划划分分，也也可以按空间划分。可以按空间划分。 2. 每一阶段都有相应的每一阶段都有相应的“ 状态状态”与之对应。与之对应。 3. 每
5、每一一阶阶段段都都面面临临一一个个决决策策，选选择择不不同同的的决决策策将将会会导导致致下下一一阶阶段段不不同同的的状状态态，同同时时，不不同同的的决决策策将将会会导导致致这这一一阶阶段段不不同同的目标函数值。的目标函数值。 4. 每每一一阶阶段段的的最最优优解解问问题题可可以以递递归归地地归归结结为为下下一一阶阶段段各各个个可可能能状状态态的的最最优优解解问问题题，各各子子问问题题与与原原问问题题具具有有完完全全相相同同的的结结构构。能能否否构构造造这这样样的的递递推推归归结结，是是解解决决动动态态规规划划问问题题的的关关键键。这种递推归结的过程，称为这种递推归结的过程，称为“ 不变嵌入不变
6、嵌入”。8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 7 5 . 状态具有无后效性状态具有无后效性 当某阶段状态确定后，此阶段以后过当某阶段状态确定后，此阶段以后过程的发展不受此阶段以前各阶段状态的影响。如下图所示：程的发展不受此阶段以前各阶段状态的影响。如下图所示：9AB1B2B3D1C1C4C3D2E7812121441213651064C2908.1 动态规划数学模型动态规划数学模型Mathematical
7、Model of DP 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 8 动态规划基本原理动态规划基本原理是将一个问题的最优解转化为求子问题的最是将一个问题的最优解转化为求子问题的最优解，研究的对象是决策过程的最优化，其变量是流动的时间优解，研究的对象是决策过程的最优化，其变量是流动的时间或变动的状态，最后到达整个系统最优。或变动的状态，最后到达整个系统最优。基本原理一方面基本原理一方面说明原问题的最优解中包含了子问题的最优解，说明原问题的最优解中包含了子问题的最优解，另一方面另一方面给出了一种求解问题
8、的思路，将一个难以直接解决的给出了一种求解问题的思路，将一个难以直接解决的大问题，分割成一些规模较小的相同子问题，每一个子问题只大问题，分割成一些规模较小的相同子问题，每一个子问题只解一次，并将结果保存起来以后直接引用，避免每次碰到时都解一次，并将结果保存起来以后直接引用，避免每次碰到时都要重复计算，以便各个击破，分而治之，即分治法，是一种解要重复计算，以便各个击破，分而治之，即分治法，是一种解决最优化问题的算法策略。决最优化问题的算法策略。动态规划求解可分为三个步骤动态规划求解可分为三个步骤：分解、求解与合并。：分解、求解与合并。8.1 动态规划数学模型动态规划数学模型Mathematica
9、l Model of DP 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 9 （1）阶段阶段(Stage)：表示决策顺序的时段序列，阶段可以按时间：表示决策顺序的时段序列，阶段可以按时间或空间划分，阶段数或空间划分，阶段数k可以是确定数、不定数或无限数可以是确定数、不定数或无限数 8.1.2基本概念基本概念（3）决策决策（Decision）xk：从某一状态向下一状态过度时所做的：从某一状态向下一状态过度时所做的选择。决策变量记为选择。决策变量记为xk，xk是所在状态是所在状态sk的函数。的函数。 在状态
10、在状态sk下，允许采取决策的全体称为决策允许集合，记为下，允许采取决策的全体称为决策允许集合，记为Dk(sk)。各阶段所有决策组成的集合称为决策集。各阶段所有决策组成的集合称为决策集。（2）状态状态（State）：描述决策过程当前特征并且具有无后效性）：描述决策过程当前特征并且具有无后效性的量。状态可以是数量，也可以是字符，数量状态可以是连续的，的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。每一状态可以取不同值，状态变量记为也可以是离散的。每一状态可以取不同值，状态变量记为sk。各。各阶段所有状态组成的集合称为状态集。阶段所有状态组成的集合称为状态集。8.1 动态规
11、划数学模型动态规划数学模型Mathematical Model of DP 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 10 (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 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与
13、教学 武汉理工大学管理学院 熊伟 Page 11 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的最大值或最小值。的最大值或最小值。 （Optoptimization表示表示“max”或或“min” 8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 12 动态规划要求过程指标满足动态规划要求过程指标满足递推关系递推关系 ，即，即(8.2)连和形式：连和形式：(8.3)最优指标函数
15、是最优指标函数是 (8.4)8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 13 动态规划数学模型由式动态规划数学模型由式(8.4)或或(8.6)、边界条件及状态转移方、边界条件及状态转移方程构成。如连和形式的数学模型程构成。如连和形式的数学模型 连乘形式连乘形式(vj0) ：(8.5)最优指标函数是最优指标函数是 (8.6)8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 7
16、/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 14 对于可加性指标函数，上式可以写为对于可加性指标函数，上式可以写为上上式式中中“ opt”表表示示“ max”或或“ min”。对对于于可可乘乘性性指指标标函函数数，上式可以写为上式可以写为上上式式称称为为动动态态规规划划最最优优指指标标的的递递推推方方程程，是是动动态态规规划划的的基基本本方方程。程。终终端端条条件件：为为了了使使以以上上的的递递推推方方程程有有递递推推的的起起点点，必必须须要要设设定定最最优优指指标标的的终终端端条条件件，即即确确定定最
17、最后后一一个个状状态态n下下最最优优指指标标fn(sn)的的值。值。8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 15 用逆序法列表求解例用逆序法列表求解例8.1 k=n=5 时，时，f5(v10)0 k=4，递推方程为，递推方程为 s4D4(s4)s5v4(s4,x4)v4(s4,x4)+f5(s5)f4(s4)最优决策最优决策x4*v7v7v10v1055+0=5*5v7 v10v8v8v10v1088+08*
18、8v8 v10v9v9v10v1044+0=4*4v9 v108.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 16 k=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
19、8v v6 6v9 9v7v8v9125812+5=175+8=138+4=12*12v6v9 98.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 17 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
20、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 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 18 k=1，递推方程为，递推方程为表8-4 s1D1(s1)s2v1(s1,x1)v1(s1,x1)+f2(s2)f1(s1)最优决策最优决策x1*v1v1v2 2v v1 1v3
21、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 动态规划数学模型动态规划数学模型Mathematical Model of DP 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 19
22、作业：教材作业：教材P188 T2下一节：资源分配问题下一节：资源分配问题 8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 7/21/20248.2 资源分配问题资源分配问题Resource Assignment Problem7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 21 【例例8.2】公公司司有有资资金金8万万元元，投投资资A、B、C三三个个项项目目，一一个个单单位位投投资资为为2万万元元。每每个个项项目目的的投投资资效效益益率率与与投投入入该该项项目目
23、的的资资金金有有关关。三三个个项项目目A、B、C的的投投资资效效益益(万万元元)和和投投入入资资金金（万万元元）的的关关系系见见表表8-5。求求对对三三个个项项目目的的最最优优投资分配，使总投资效益最大。投资分配，使总投资效益最大。 8.2 资源分配问题资源分配问题Resource Assignment Problem 项目项目投入资金投入资金ABC2万元万元89104万元万元1520286万元万元3035358万元万元384043表表8-5【解解】设设xk为第为第k个项目的投资，该问题的静态规划模型为个项目的投资，该问题的静态规划模型为7/21/2024第第8章章 动态规划动态规划Dynam
24、ic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 22 阶段阶段k：每投资一个项目作为一个阶段，：每投资一个项目作为一个阶段，k=1,2,3,4。k=4为虚设为虚设的阶段的阶段状态变量状态变量sk：投资第：投资第k个项目前的资金数个项目前的资金数决策变量决策变量xk：第：第k个项目的投资额个项目的投资额决策允许集合：决策允许集合：0xksk状态转移方程：状态转移方程：sk+1=skxk阶段指标：阶段指标：vk(sk，xk)见表见表8-5中的数据中的数据 递推方程：递推方程： 终端条件：终端条件：f4(s4)=0数学模型为数学模型为 8.2 资源分配问题资源分配问
25、题Resource Assignment Problem7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 23 k=4，终端条件f4(s4)=0。 k=3，0x3s3，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=1040282
26、8+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 Problem7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 24 s2x2(s2)s3v2(s2,x2)f3(s3)v2(s2,x2)+f3(s3)f2(s2)x2*000000+0=0002020100+10=10
27、*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，0x2s2，s3=s2x2 8.2 资源分配问题资源分配问题Resource Assignment Problem7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊
28、伟 Page 25 k=1，0x1s1，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。投资的最优策略是，项目投资的最优策略是，项目A不投资，项目不投资，项目B投资投资4万元，项目万元，项目C投投资资4万元，最大效益为万元，最大效益为48万元万元 8.2
29、资源分配问题资源分配问题Resource Assignment Problem7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 26 【例例8.3】某种设备可在高低两种不同的负荷下进行生产，设在某种设备可在高低两种不同的负荷下进行生产，设在高负荷下投入生产的设备数量为高负荷下投入生产的设备数量为x,产量为产量为g=10x，设备年完好率设备年完好率为为a=0.75；在低负荷下投入生产的设备数量为；在低负荷下投入生产的设备数量为y，产量为产量为h=8y，年完好率为年完好率为b=0.9。假定开始生产时完好的设备数
30、量。假定开始生产时完好的设备数量s1=100。制定一个五年计划，确定每年投入高、低两种负荷下生产的设制定一个五年计划，确定每年投入高、低两种负荷下生产的设备数量，使五年内产品的总产量达到最大。备数量，使五年内产品的总产量达到最大。 阶段阶段k：运行年份运行年份（k=1,2,3,4,5,6），），k=1表示第一年初，表示第一年初，k=6表表示第五年末（即第六年初）；示第五年末（即第六年初）；状态变量状态变量sk：第第k年初完好的机器数（年初完好的机器数（k=1,2,3,4,5,6），也是第），也是第k1年末完好的机器数，其中年末完好的机器数，其中s6表示第五年末（即第六年初）的表示第五年末（即第
31、六年初）的完好机器数，完好机器数，s1100。决策变量决策变量xk：第第k年初投入高负荷运行的机器数；年初投入高负荷运行的机器数；状态转移方程：状态转移方程：sk+1=0.75xk+0.9(skxk)8.2 资源分配问题资源分配问题Resource Assignment Problem7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 27 决策允许集合：决策允许集合：Dk(sk)=xk|0 xk sk阶段指标：阶段指标：vk(sk，xk)=10xk+8(skxk)终端条件终端条件：f6(s6)=0递推方程：
32、递推方程：8.2 资源分配问题资源分配问题Resource Assignment Problem7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 28 8.2 资源分配问题资源分配问题Resource Assignment Problem7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 29 8.2 资源分配问题资源分配问题Resource Assignment Problem7/21/2024第第8章章 动态规划动态规
33、划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 30 因为因为s1=100，五年的最大总产量为，五年的最大总产量为f1(s1)=25.75251003443.75。由由x1*= x2*= x3*=0，x4*s4，x5*s5，设备的最优分配策略是，设备的最优分配策略是，第一年至第三年将设备全部用于低负荷运行，第四年和第五年将第一年至第三年将设备全部用于低负荷运行，第四年和第五年将设备全部用于高负荷运行。每年投入高负荷运行的机器数以及每设备全部用于高负荷运行。每年投入高负荷运行的机器数以及每年初完好的机器数为：年初完好的机器数为：s1=100x1*=0
34、,s2=0.75x1+0.9(s1x1)=90x2*=0,s3=0.75x2+0.9(s2x2)=81x3*= 0， s4=0.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 Problem7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 31 一般地，设一个周期为一般地，设一个周期为n年
35、，高负荷生产时设备的完好率为年，高负荷生产时设备的完好率为a，单台产量为单台产量为g；低负荷完好率为；低负荷完好率为b，单台产量为，单台产量为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次方累加次方累加.由由
36、a0=11.3333a0+a11.75知，知，nt10，t=4，则，则13年低负年低负荷运行，荷运行，45年为高负荷运行年为高负荷运行 8.2 资源分配问题资源分配问题Resource Assignment Problem(8.7)7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 32 作业：教材作业：教材P188 T1，6，8，98.2 资源分配问题资源分配问题Resource Assignment Problem下一节：下一节：生产与存储问题生产与存储问题7/21/20248.3 生产与存储问题生产与存
37、储问题Production and inventory problem7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 34 8.3 生产与存储问题生产与存储问题Production and inventory problem【8.4】一个工厂生产某种产品，一个工厂生产某种产品，16月份生产成本和产品需求量月份生产成本和产品需求量的变化情况见表的变化情况见表8-9 月份月份(k)123456需求量需求量(dk)203035402545单位产品成本单位产品成本(ck)151216191816表表8-9没有生产
38、准备成本，单位产品一个月的存储费为没有生产准备成本，单位产品一个月的存储费为hk0.6元，元，月底交货。分别求下列两种情形月底交货。分别求下列两种情形6个月总成本最小的生产方案。个月总成本最小的生产方案。（1）1月初与月初与6月底存储量为零，不允许缺货，仓库容量为月底存储量为零，不允许缺货，仓库容量为S=50件，生产能力无限制；件，生产能力无限制；（2）其它条件不变，）其它条件不变，1月初存量为月初存量为10 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 35 8.3 生产与存储问题生产与存储问题Pro
39、duction and inventory problem【解解】动态规划求解过程如下。动态规划求解过程如下。阶段阶段k：月份，：月份，k=1,2,7状态变量状态变量sk：第：第k个月初的库存量个月初的库存量决策变量决策变量xk：第：第k个月的生产量个月的生产量状态转移方程：状态转移方程：sk+1=sk+xkdk 决策允许集合决策允许集合: 阶段指标：阶段指标： 终端条件：终端条件：f7(s7)=0, s7=0递推方程：递推方程：7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 36 8.3 生产与存储问题
40、生产与存储问题Production and inventory problem当当k=6时，因为时，因为s7=0，有，有 当当k=5时，时， 由于由于s550，则当，则当25s50时时x5的值取的值取“0”，决策允许集合为，决策允许集合为 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 37 8.3 生产与存储问题生产与存储问题Production and inventory problemk=4时， 决策允许集合为决策允许集合为 7/21/2024第第8章章 动态规划动态规划Dynamic Progra
41、mming 制作与教学 武汉理工大学管理学院 熊伟 Page 38 8.3 生产与存储问题生产与存储问题Production and inventory problem显然该决策不可行显然该决策不可行,x5=0，s4+x4=65d4+d5，s5=s4+x4d4=25，x6=45，与，与s525矛盾。因此有矛盾。因此有 k=3，当，当0s440时，时， 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 39 8.3 生产与存储问题生产与存储问题Production and inventory problem
42、当当40s450时，时， 当当k=2时，由时，由 x2的决策允许集合为的决策允许集合为 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 40 8.3 生产与存储问题生产与存储问题Production and inventory problem当当k=1时，由时，由 只要期初存量只要期初存量s120，则，则x1的决策允许集合为的决策允许集合为(1)期初存储量期初存储量s1=0，由各阶段的最优决策，由各阶段的最优决策xj*及状态转移方程，及状态转移方程，回朔可求出最优策略。回朔可求出最优策略。 7/21/20
43、24第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 41 8.3 生产与存储问题生产与存储问题Production 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，与前面计算类似，得到，与前面计算类似，得到x
44、110，x280，x335，x40，x515，x645。 16月份生产、存储详细计划表见表月份生产、存储详细计划表见表8-10所示。所示。 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 42 8.3 生产与存储问题生产与存储问题Production and inventory problem表表8-10月份月份(k)123456合计合计需求量需求量(dk)203035402545195单位产品成本单位产品成本(ck)151216191816单位存储费单位存储费hk0.60.60.60.60.60.6产量
45、产量xk20803501545195期初存量期初存量sk005050100110生产成本生产成本CK(xk)30096056002707202810存储成本存储成本Hk(sk)0030306066合计合计28767/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 43 8.3 生产与存储问题生产与存储问题Production and inventory problem7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 44
46、8.3 生产与存储问题生产与存储问题Production and inventory problem作业：教材作业：教材P189 T 7下一节：背包问题下一节：背包问题 7/21/20248.4 背包问题背包问题Knapsack Problem7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 46 8.4 背包问题背包问题Knapsack Problem背包问题数学模型为背包问题数学模型为式中：式中：ck为第为第k种物品的单位价值，种物品的单位价值，wk是第是第k种物品的单位重量或体积，种物品的单位重量或体
47、积，W是背包的重量或体积限制。动态规划的有关要素如下。是背包的重量或体积限制。动态规划的有关要素如下。阶段阶段k：第：第k次装载第次装载第k种物品（种物品（k=1,2,n）状态变量状态变量sk：第：第k次装载时背包还可以装载的重量次装载时背包还可以装载的重量(或体积或体积)决策变量决策变量xk：第：第k次装载第次装载第k种物品的件数种物品的件数决策允许集合：决策允许集合：Dk(sk)=dk|0 xk sk/wk，xk为整数为整数状态转移方程：状态转移方程：sk+1=skwkxk阶段指标：阶段指标：vk=ckxk7/21/2024第第8章章 动态规划动态规划Dynamic Programming
48、 制作与教学 武汉理工大学管理学院 熊伟 Page 47 8.4 背包问题背包问题Knapsack Problem递推方程：递推方程：终端条件：终端条件：fn1(sn1)=0 【例例8.5】用动态规划方法求解下列整数规划用动态规划方法求解下列整数规划【解解】终端条件：终端条件： f4(x4)=0 k=3时，递推方程时，递推方程7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 48 8.4 背包问题背包问题Knapsack Problem表表8-11s3D3(s3)=x3|s3/5s460x3+f4(s4)
49、f3(s3)x3*0000+0=0001010+0=0000501500+0=060+0=60*060111001210500+0=6060+0=60120+0=120*1202最优决策是；最优决策是；s3为为04时，时，x30，s3为为59时，时，x31，s310时，时，x32。 k=2时，递推方程时，递推方程7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 49 8.4 背包问题背包问题Knapsack Problem表表8-12 s2D2(s2)s340x2+f3(s3)f2(s2)x2*0000+f
50、3(0)=0+0=0*001 0 10+0000201200+0=040+0=40*401301310+0=040+0=40*40140124200+0=040+0=4080+0=8080250125310+60=6040+0=4080+0=80*8021001234510864200+120=12040+60=10080+60=140120+0=120160+0=160200+0=200*20057/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 50 第第2阶段的最优决策见表阶段的最优决策见表8-13 表
51、表8-13s20 1 2 3 4 5 6 7 8 9 10f2(s2)0 0 40 40 80 80 120 120 160 160 200x20 0 1 1 2 2 3 3 4 4 5k=1时，递推方程时，递推方程8.4 背包问题背包问题Knapsack Problem7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 51 s110，w1=3，D1(s1)=0，1，2，3，计算结果见表，计算结果见表8-14 表表8-14s1D1(s1)s260x1+f2(s2)f1(s1)x1*100123107410+
52、f2(10)=0+200=200*60+120=180120+80=200*180+0=1802000 , 2由表由表8-14、8-13、8-11，得到两个最优解：，得到两个最优解：X1（0，5，0），），X2（2，2，0），最优值），最优值Z200。 8.4 背包问题背包问题Knapsack Problem7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 52 作业：教材作业：教材P189 T5 8.4 背包问题背包问题Knapsack Problem下一节：其它动态规划模型下一节：其它动态规划模型7/2
53、1/20248.5 其它动态规划模型其它动态规划模型 Other Model of DP7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 54 8.5 其它动态规划模型其它动态规划模型 Other Model of DP8.5.1求解线性规划模型求解线性规划模型【例例8.6】用动态规划方法求解下列线性规划用动态规划方法求解下列线性规划【解解】首先将问题转化为动态规划模型首先将问题转化为动态规划模型 阶段数为阶段数为3，决策变量为，决策变量为xk，状态变量为第，状态变量为第k阶段初各约束条件阶段初各约束条件右
54、端常数的剩余值，用右端常数的剩余值，用s1k和和s2k表示，状态转移方程为表示，状态转移方程为 s1,k+1=s1ka1kxk，s2,k+1=s2ka2kxk 终端条件终端条件 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 55 8.5 其它动态规划模型其它动态规划模型 Other Model of DPk=2时时,决策变量决策变量x2的允许集合的允许集合 k=3时时,决策变量决策变量x3的允许集合的允许集合 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教
55、学 武汉理工大学管理学院 熊伟 Page 56 8.5 其它动态规划模型其它动态规划模型 Other Model of DP状态转移方程为状态转移方程为 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 57 8.5 其它动态规划模型其它动态规划模型 Other Model of DPk1时，决策变量时，决策变量x1的允许集合的允许集合状态转移方程状态转移方程最优解最优解: 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Pa
56、ge 58 8.5 其它动态规划模型其它动态规划模型 Other Model of DP8.5.1求解非线性规划模型求解非线性规划模型【例例8.7】用动态规划方法求解下列非线性规划用动态规划方法求解下列非线性规划 【解解】阶段数为阶段数为3，决策变量为，决策变量为xk，状态变量，状态变量sk为第为第k阶段初约阶段初约束条件右端常数的剩余值，状态转移方程为束条件右端常数的剩余值，状态转移方程为sk+1=skakxk，阶，阶段指标是段指标是xk，递推方程为，递推方程为7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Pa
57、ge 59 8.5 其它动态规划模型其它动态规划模型 Other Model of DP终端条件终端条件 k3时，决策变量允许集合时，决策变量允许集合递推方程递推方程7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 60 8.5 其它动态规划模型其它动态规划模型 Other Model of DPk2时，决策变量允许集合时，决策变量允许集合状态转移方程状态转移方程s3=s25x2递推方程递推方程7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理
58、学院 熊伟 Page 61 8.5 其它动态规划模型其它动态规划模型 Other Model of DPk1时，决策变量允许集合时，决策变量允许集合状态转移方程状态转移方程s2=20x1递推方程递推方程得到最优解得到最优解 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 62 8.5 其它动态规划模型其它动态规划模型 Other Model of DP8.5.3设备更新问题设备更新问题设备更新问题在第设备更新问题在第6章的例章的例6.8曾用曾用Dijkstra算法求解，也能用算法求解，也能用动态规划方法
59、求解。设一台设备已使用了动态规划方法求解。设一台设备已使用了(役龄役龄)T年，对一台年，对一台使用寿命为使用寿命为n年的设备，怎样制定在年的设备，怎样制定在n年中每年是更新年中每年是更新(Keep)还是继续使用还是继续使用(Replace)策略，使策略，使n年的总收益最大或总成本年的总收益最大或总成本最低。下面以总成本最低为标准讨论设备更新的动态规划求最低。下面以总成本最低为标准讨论设备更新的动态规划求解方法。解方法。P(t)：第：第t年新设备的购置成本，年新设备的购置成本，t=0，1，2，n。C(t)是设备第是设备第t年的维修费用。这里的年的维修费用。这里的t从从T年后开始计算，年后开始计算
60、，t=0，1，2，n，新设备的役龄为，新设备的役龄为t=0。如设备已使用了两年。如设备已使用了两年(T=2)，继续使用时第，继续使用时第1年年t等于等于0，不是等于，不是等于1。S(t)为旧设备第为旧设备第t年出售的价格；年出售的价格；R(t)为在为在n年末，役龄为年末，役龄为t的设备残值；的设备残值；7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 63 阶段阶段k：设备运行年份；：设备运行年份；状态变量状态变量sk：设备的役龄：设备的役龄t；决策变量决策变量xk：8.5 其它动态规划模型其它动态规划模型
61、 Other Model of DP状态转移方程状态转移方程 阶段指标是更新或继续使用的总成本：阶段指标是更新或继续使用的总成本：7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 64 8.5 其它动态规划模型其它动态规划模型 Other Model of DP递推方程递推方程 终端条件终端条件 fn(t)=R(t) 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 65 作业：教材作业：教材P189 T 3，4，108.5 其它动态规划模型其它动态规划模型 Other Model of DPThe End of Chapter 8 7/21/2024第第8章章 动态规划动态规划Dynamic Programming 制作与教学 武汉理工大学管理学院 熊伟 Page 66 习题习题8.10(1)7/21/2024
