大学精品课件：8动态规划.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 DP8.1 动态规划数学模型动态规划数学模型Mathematical Model of DPv2v3

2、v4v7v5v9v6v8v1028512131071013112865885405847【例例8.1】最短路径问题最短路径问题 图图81表示从起点表示从起点A到终点到终点E之间各点的距离。求之间各点的距离。求A到到E的最短路径。的最短路径。图图81v1第1阶段第2阶段第3阶段第4阶段阶段：第5阶段1217142019Min2+5,8+8,6+4=7动态规划问题具有以下动态规划问题具有以下基本特征基本特征 1.问题具有多阶段决策的特征。阶段可以按时间划分，也问题具有多阶段决策的特征。阶段可以按时间划分，也可以按空间划分。可以按空间划分。2.每一阶段都有相应的每一阶段都有相应的“状态状态”与之对应

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

4、的过程，称为“不变嵌入不变嵌入”。8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 5.状态具有无后效性状态具有无后效性 当某阶段状态确定后，此阶段以后过当某阶段状态确定后，此阶段以后过程的发展不受此阶段以前各阶段状态的影响。如下图所示：程的发展不受此阶段以前各阶段状态的影响。如下图所示：9AB1B2B3D1C1C4C3D2E7812121441213651064C2908.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 研究某一个过程研究某一个过程,这个过程可以分解为若干个互相联系的阶这个过程可以分解为若干个互相联

5、系的阶段。段。每一阶段都有其初始状态和结束状态每一阶段都有其初始状态和结束状态,其结束状态即为下一其结束状态即为下一阶段的初始状态。第一阶段的初始状态就是整个过程的初始阶段的初始状态。第一阶段的初始状态就是整个过程的初始状态状态,最后一阶段的结束状态就是整个过程的结束状态。在过最后一阶段的结束状态就是整个过程的结束状态。在过程的每一个阶段都需要作出决策程的每一个阶段都需要作出决策,而每一阶段的结束状态依赖而每一阶段的结束状态依赖于其初始状态和该阶段的决策。于其初始状态和该阶段的决策。动态规划问题就是要找出某种决策方法动态规划问题就是要找出某种决策方法,使过程达到某种使过程达到某种最优效果。最优

6、效果。这种把问题看作前后关联的多阶段过程称为这种把问题看作前后关联的多阶段过程称为多阶多阶段决策过程段决策过程.动态规划基本原理动态规划基本原理是将一个问题的最优解转化为求子问题的最是将一个问题的最优解转化为求子问题的最优解，研究的对象是决策过程的最优化，其变量是流动的时间优解，研究的对象是决策过程的最优化，其变量是流动的时间或变动的状态，最后到达整个系统最优。或变动的状态，最后到达整个系统最优。基本原理一方面基本原理一方面说明原问题的最优解中包含了子问题的最优解，说明原问题的最优解中包含了子问题的最优解，另一方面另一方面给出了一种求解问题的思路，将一个难以直接解决的给出了一种求解问题的思路，

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

8、：表示决策顺序的时段序列，阶段可以按时间表示决策顺序的时段序列，阶段可以按时间或空间划分，阶段数或空间划分，阶段数k可以是确定数、不定数或无限数可以是确定数、不定数或无限数 8.1.2基本概念基本概念（3）决策决策（Decision）xk：从某一状态向下一状态过度时所做的从某一状态向下一状态过度时所做的选择。决策变量记为选择。决策变量记为xk，xk是所在状态是所在状态sk的函数。的函数。在状态在状态sk下，允许采取决策的全体称为决策允许集合，记为下，允许采取决策的全体称为决策允许集合，记为Dk(sk)。各阶段所有决策组成的集合称为决策集。各阶段所有决策组成的集合称为决策集。（2）状态状态（St

9、ate）：）：描述决策过程当前特征并且具有无后效性描述决策过程当前特征并且具有无后效性的量。状态可以是数量，也可以是字符，数量状态可以是连续的，的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。每一状态可以取不同值，状态变量记为也可以是离散的。每一状态可以取不同值，状态变量记为sk。各各阶段所有状态组成的集合称为状态集。阶段所有状态组成的集合称为状态集。8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP(4)策略策略(Strategy)：从第从第1阶段开始到最后阶段全过程的决策构成阶段开始到最后阶段全过程的决策构成的序列称为策略，第

10、的序列称为策略，第k阶段到最后阶段的决策序列称为子策略。阶段到最后阶段的决策序列称为子策略。（5）状态转移方程状态转移方程(State transformation function)：某一状态以某一状态以及该状态下的决策，与下一状态之间的函数关系，记为及该状态下的决策，与下一状态之间的函数关系，记为sk+1=T(sk,xk)（6）指标函数或收益函数指标函数或收益函数(Return function)：是衡量对决策过是衡量对决策过程进行控制的效果的数量指标，具体可以是收益、成本、距离程进行控制的效果的数量指标，具体可以是收益、成本、距离等指标。等指标。分为分为k阶段指标函数、阶段指标函数、k子

11、过程指标函数及最优指标函子过程指标函数及最优指标函数。数。8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP k阶段指标函数阶段指标函数 从从k阶段状态阶段状态sk出发，选择决策出发，选择决策xk所产生的第所产生的第k阶段指标，称为阶段指标，称为k阶段指标函数阶段指标函数,记为记为vk(sk,xk)。从从k阶段状态阶段状态sk出发，选择决策出发，选择决策xk,xk+1,xn所产生的过程指标，所产生的过程指标，称为称为k子过程指标函数或简称过程指标函数，记为子过程指标函数或简称过程指标函数，记为Vk(sk,xk,xk+1,xn)或或Vk，n为阶段数。为阶段数

12、。过程指标函数过程指标函数最优指标函数最优指标函数从从k阶段状态阶段状态sk出发，对所有的子策略，最优的过程指标函数称出发，对所有的子策略，最优的过程指标函数称为最优指标函数，记为为最优指标函数，记为fk(sk)，通常取通常取Vk的最大值或最小值。的最大值或最小值。),()(,)(nkknksDdkkPsVsfoptkkk （Optoptimization表示表示“max”或或“min”8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 动态规划要求过程指标满足动态规划要求过程指标满足递推关系递推关系，即，即1111(,)(,),(,)kkkknkkkkk

13、knV 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.4)或或(8.6)、边界条件及状态转移方程、边界条件及状态转移方程构成。如连和形式的数学模型构成。如连和形式的数学模型 连乘形式连乘形式(vj0)：1111(,

14、)(,)(,)(,)KKkkknkkkKkknnjjjnj kVVsxxxv sxVsxxv sxV=(8.5)最优指标函数是最优指标函数是 nksfdsvOptsfkkkkksDxkkkkk,2,1),(,()(11)(8.6),(0)(,2,1),(,()(111)(kkknnkkkkksDxkkxsTssfnksfxsvOptsfkkk8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 对于可加性指标函数，上式可以写为对于可加性指标函数，上式可以写为nksfxsvsfkkkkksDdkkoptkkk,2,1)(,()(11)(上式中上式中“opt”表

15、示表示“max”或或“min”。对于可乘性指标函数，对于可乘性指标函数，上式可以写为上式可以写为nksfxsvsfkkkkksDxkkoptkkk,2,1)(,()(11)(上式称为动态规划最优指标的上式称为动态规划最优指标的递推方程递推方程，是动态规划的基本方，是动态规划的基本方程。程。终端条件：终端条件：为了使以上的递推方程有递推的起点，必须要设定为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，即确定最后一个状态最优指标的终端条件，即确定最后一个状态n下最优指标下最优指标fn(sn)的的值。值。8.1 动态规划数学模型动态规划数学模型Mathematical Model o

16、f DP 用逆序法列表求解例用逆序法列表求解例8.1 k=n=5 时，时，f5(v10)0)(),(min)(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)(),(min)(44333)(33333sfxsvsfsDxk=3，递推方程为

17、递推方程为表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 k=2，递推方程为递推方程为表表8-3 s2D2(s2)s3v2(s2,x2)v2(s2,x2)+f3(s3)f2(s2)最优决

18、策最优决策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 动态规划数学模型动态规划数学模型Mathematical Model of DP k=1，递推方程为递推方程为表8-4)(),(min)(22111)(11111sfxsvsfsDxs1D1(s1)s2

19、v1(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 动态规划数学模型动态规划数学模型Mathematical Model of DP 作业：教材作业：教材P18

20、8 T2下一节：资源分配问题下一节：资源分配问题 8.1 动态规划数学模型动态规划数学模型Mathematical Model of DP 8.2 资源分配问题资源分配问题Resource Assignment Problem【例例8.2】公司有资金公司有资金8万元，投资万元，投资A、B、C三个项目，一个单位投资为三个项目，一个单位投资为2万万元。每个项目的投资效益率与投入该项目的资金有关。三个项目元。每个项目的投资效益率与投入该项目的资金有关。三个项目A、B、C的的投资效益投资效益(万元万元)和投入资金（万元）的关系见表和投入资金（万元）的关系见表8-5。求对三个项目的最优投求对三个项目的最

21、优投资分配，使总投资效益最大。资分配，使总投资效益最大。8.2 资源分配问题资源分配问题Resource Assignment Problem 项目项目投入资金投入资金ABC2万元万元89104万元万元1520286万元万元3035358万元万元384043表表8-5【解解】设设xk为第为第k个项目的投资，该问题的静态规划模型为个项目的投资，该问题的静态规划模型为112233123max()()()80,2,4,6,8jZv xv xv xxxxx阶段阶段k：每投资一个项目作为一个阶段，每投资一个项目作为一个阶段，k=1,2,3,4。k=4为虚设为虚设的阶段的阶段状态变量状态变量sk：投资第投

22、资第k个项目前的资金数个项目前的资金数决策变量决策变量xk：第：第k个项目的投资额个项目的投资额决策允许集合：决策允许集合：0 xksk状态转移方程：状态转移方程：sk+1=skxk阶段指标：阶段指标：vk(sk，xk)见表见表8-5中的数据中的数据 递推方程：递推方程：11()max(,)()kkkkkkkfxv sxfs终端条件：终端条件：f4(s4)=0数学模型为数学模型为 11144()max(,)(),3,2,1()00,2,4,6,8,1,2,3kkkkkkkkkkkfxvsxfskssxfxxk8.2 资源分配问题资源分配问题Resource Assignment Problem

23、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)最优决策最优决策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=3580

24、4343+0=43*8.2 资源分配问题资源分配问题Resource Assignment Problems2x2(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=45804004

25、0+0=40k=2，0 x2s2，s3=s2x2 8.2 资源分配问题资源分配问题Resource Assignment Problemk=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。投资的最优策略是，项目投资的最优策略是，项目A不投资，项目不投资

26、，项目B投资投资4万元，项目万元，项目C投投资资4万元，最大效益为万元，最大效益为48万元万元 8.2 资源分配问题资源分配问题Resource Assignment Problem商人过河商人过河v 设有三名商人，各带一个随从，欲乘一小船渡河，小船只设有三名商人，各带一个随从，欲乘一小船渡河，小船只能容纳两人，须由他们自己划行。随从们密约，在河的任能容纳两人，须由他们自己划行。随从们密约，在河的任何一岸，一旦随从的人数比商人多，就杀人越货。而如何何一岸，一旦随从的人数比商人多，就杀人越货。而如何乘船渡河的大权掌握在商人们的手中。商人们怎样才能安乘船渡河的大权掌握在商人们的手中。商人们怎样才能

27、安全渡河呢？全渡河呢？【例例8.3】某种设备可在高低两种不同的负荷下进行生产，设在某种设备可在高低两种不同的负荷下进行生产，设在高负荷下投入生产的设备数量为高负荷下投入生产的设备数量为x,产量为产量为g=10 x，设备年完好率设备年完好率为为a=0.75；在低负荷下投入生产的设备数量为在低负荷下投入生产的设备数量为y，产量为产量为h=8y，年完好率为年完好率为b=0.9。假定开始生产时完好的设备数量假定开始生产时完好的设备数量s1=100。制定一个五年计划，确定每年投入高、低两种负荷下生产的设制定一个五年计划，确定每年投入高、低两种负荷下生产的设备数量，使五年内产品的总产量达到最大。备数量，使

28、五年内产品的总产量达到最大。阶段阶段k：运行年份运行年份（k=1,2,3,4,5,6），），k=1表示第一年初，表示第一年初，k=6表示第五年末（即第六年初）；表示第五年末（即第六年初）；状态变量状态变量sk：第第k年初完好的机器数（年初完好的机器数（k=1,2,3,4,5,6），），也是第也是第k1年末完好的机器数，其中年末完好的机器数，其中s6表示第五年末（即第六年初）的表示第五年末（即第六年初）的完好机器数，完好机器数，s1100。决策变量决策变量xk：第第k年初投入高负荷运行的机器数；年初投入高负荷运行的机器数；状态转移方程：状态转移方程：sk+1=0.75xk+0.9(skxk)8.

29、2 资源分配问题资源分配问题Resource Assignment Problem决策允许集合：决策允许集合：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 资源分配问题资源分配问题

30、Resource Assignment Problem4444444444444550444504444440*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 sxsxfsxsxsxsxxsxxssx 时最优8.2 资源

31、分配问题资源分配问题Resource Assignment Problem2222222222222330222302222220*22220()max 108()()max 108()23.75max 108()23.75(0.750.9()max 1.562529.375 29.3750 xsxsxsxsfsxsxf sxsxsxsxxsxxssx 时最优1111111111111220111201111110*11110()max 108()()max 108()29.375max 108()29.375(0.750.9()max 2.40634.4375 34.43750 xsxsxs

32、xsf sxsxfsxsxsxsxxsxxssx 时最优8.2 资源分配问题资源分配问题Resource Assignment Problem因为因为s1=100，五年的最大总产量为五年的最大总产量为f1(s1)=25.75251003443.75。由由x1*=x2*=x3*=0，x4*s4，x5*s5，设备的最优分配策略是，设备的最优分配策略是，第一年至第三年将设备全部用于低负荷运行，第四年和第五年将第一年至第三年将设备全部用于低负荷运行，第四年和第五年将设备全部用于高负荷运行。每年投入高负荷运行的机器数以及每设备全部用于高负荷运行。每年投入高负荷运行的机器数以及每年初完好的机器数为：年初完

33、好的机器数为：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.9(s4x4)=55x5*=s5=55，s6=0.75x5+0.9(s5x5)=41第五年末还有41台完好设备。8.2 资源分配问题资源分配问题Resource Assignment Problem一般地，设一个周期为一般地，设一个周期为n年，高负荷生产时设备的完好率为年，高负荷生产时设备的完好率为a，单台产量为单台产量为g；低负荷完好率为低负荷完好率为b

34、，单台产量为单台产量为h。若有若有t满足满足100()n tn tiiiighaag 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年

35、低负年低负荷运行，荷运行，45年为高负荷运行年为高负荷运行 8.2 资源分配问题资源分配问题Resource Assignment Problem(8.7)作业：教材作业：教材P188 T1，6，8，98.2 资源分配问题资源分配问题Resource Assignment Problem下一节：生产与存储问题下一节：生产与存储问题8.3 生产与存储问题生产与存储问题Production and inventory problem8.3 生产与存储问题生产与存储问题Production and inventory problem【8.4】一个工厂生产某种产品，一个工厂生产某种产品，16月份生产成

36、本和产品需求量月份生产成本和产品需求量的变化情况见表的变化情况见表8-9 月份月份(k)123456需求量需求量(dk)203035402545单位产品成本单位产品成本(ck)151216191816表表8-9没有生产准备成本，单位产品一个月的存储费为没有生产准备成本，单位产品一个月的存储费为hk0.6元，元，月底交货。分别求下列两种情形月底交货。分别求下列两种情形6个月总成本最小的生产方案。个月总成本最小的生产方案。（1）1月初与月初与6月底存储量为零，不允许缺货，仓库容量为月底存储量为零，不允许缺货，仓库容量为S=50件，生产能力无限制；件，生产能力无限制；（2）其它条件不变，）其它条件不

37、变，1月初存量为月初存量为10 8.3 生产与存储问题生产与存储问题Production and inventory problem【解解】动态规划求解过程如下。动态规划求解过程如下。阶段阶段k：月份，月份，k=1,2,7状态变量状态变量sk：第：第k个月初的库存量个月初的库存量决策变量决策变量xk：第：第k个月的生产量个月的生产量状态转移方程：状态转移方程：sk+1=sk+xkdk 决策允许集合决策允许集合:500,0)(kkkkkkkdxsxxsD阶段指标：阶段指标：(,)0.6kkkkkkkkkkv sxc xh sc xs终端条件：终端条件：f7(s7)=0,s7=0递推方程：递推方程

38、：)(),(min)(),(min)(1)(11)(kkkkkkkkskDkxkkkkkkskDkxkkdxsfxsvsfxsvxf8.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的值取的

39、值取“0”，决策允许集合为，决策允许集合为 555555()max0,2570D sxsxs555555555555566()556()55655()*5555*555()min180.6()min180.615.4720min2.614.81105(25)17.41170252514.81105250 xDsxDsxDsf sxsfsxssxsssxssxsssx其中时,取下界：时,取下界：8.3 生产与存储问题生产与存储问题Production and inventory problemk=4时，5440254025,ssx，0有44465sxs40决策允许集合为决策允许集合为 44444

40、4()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.214.2169718.4197065xDsxDsxDsfsxsf sxssxs

41、sxs 取下界：8.3 生产与存储问题生产与存储问题Production and inventory problem显然该决策不可行，显然该决策不可行，x5=0，s4+x4=65d4+d5，s5=s6=0，x6=45，与与s525矛盾。因此有矛盾。因此有 k=3，当，当0s440时，时，*4444555*4444455518.41930 040,40025,25()16.81866 4050,0025,25ssxssxsf sssxsxs并且并且333540s+x0333333()max0,3575D sxsxs333333333333344()334()33()*333()min160.6(

42、)min160.618.41930min2.417.8257415.4239475xDsxDsxDsf sxsfsxssxssxs 取上界：8.3 生产与存储问题生产与存储问题Production and inventory problem当当40s450时，时，33403550s+x333333()7585D sxsxs333333333333344()334()33()*333()min160.6()min160.616.81866min0.816.2245415.4238685xDsxDsxDsf sxsfsxssxssxs 取上界：当当k=2时，由时，由 43224050,050305

43、0,sssx，0有22280sxs30 x2的决策允许集合为的决策允许集合为 222222()max0,3080D sxsxs22222222222223330652233065223065*222()min120.6()min120.615.42386min3.414.8284811.4257680sxssxssxsfsxsf sxssxssxs 取上界：8.3 生产与存储问题生产与存储问题Production and inventory problem当当k=1时，由时，由 211050 02050,ssx，1112070sxs只要期初存量只要期初存量s120，则，则x1的决策允许集合为的

44、决策允许集合为111111()2070D sxsxs111111111111122()112()11()*111()min150.6()min150.611.42584min3.610.8280414.4287620 xD sxD sxD sf sxsfsxssxssxs 取下界：(1)期初存储量期初存储量s1=0，由各阶段的最优决策由各阶段的最优决策xj*及状态转移方程，及状态转移方程，回朔可求出最优策略。回朔可求出最优策略。8.3 生产与存储问题生产与存储问题Production and inventory problemx1=20，s2=s1+x1d1=0+20200，x2=80，s3=

45、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所示。所示。8.3 生产与存储问题生产与存储问题Production and inventory problem表表8-10月份月份(k)123456合计合计需求量需求量(dk)20303

46、5402545195单位产品成本单位产品成本(ck)151216191816单位存储费单位存储费hk0.60.60.60.60.60.6产量产量xk20803501545195期初存量期初存量sk005050100110生产成本生产成本CK(xk)30096056002707202810存储成本存储成本Hk(sk)0030306066合计合计28768.3 生产与存储问题生产与存储问题Production and inventory problem 例，某工厂与用户签订了4个月的交货合同如表所示 该厂生产能力为每月该厂生产能力为每月5万件，该厂仓库的存货能力为万件，该厂仓库的存货能力为4万万件

47、。件。已知生产费用为已知生产费用为c=1千元千元/万件，在进行生产的月份，工万件，在进行生产的月份，工厂要支出固定费用厂要支出固定费用b=2千元，每月仓库保管费用千元，每月仓库保管费用h=0.2千元千元/万件万件/月。月。假定开始时及假定开始时及4月底交货后无存货，试问应在每月各生月底交货后无存货，试问应在每月各生产多少件产品，才能满足交货任务，又使总费用最小？产多少件产品，才能满足交货任务，又使总费用最小？月1234需求量dk(万件)32328.4 背包问题背包问题Knapsack Problem8.3 生产与存储问题生产与存储问题Production and inventory probl

48、em作业：教材作业：教材P189 T 7下一节：背包问题下一节：背包问题 8.4 背包问题背包问题Knapsack ProblemnixWxwxwxwxcxcxcZinnnn,10max22112211且为整数，8.4 背包问题背包问题Knapsack Problem背包问题数学模型为背包问题数学模型为式中：式中：ck为第为第k种物品的单位价值，种物品的单位价值，wk是第是第k种物品的单位重量或体积，种物品的单位重量或体积，W是背包的重量或体积限制。动态规划的有关要素如下。是背包的重量或体积限制。动态规划的有关要素如下。阶段阶段k：第：第k次装载第次装载第k种物品（种物品（k=1,2,n）状态

49、变量状态变量sk：第：第k次装载时背包还可以装载的重量次装载时背包还可以装载的重量(或体积或体积)决策变量决策变量xk：第：第k次装载第次装载第k种物品的件数种物品的件数决策允许集合：决策允许集合：Dk(sk)=dk|0 xk sk/wk，xk为整数为整数状态转移方程：状态转移方程：sk+1=skwkxk阶段指标：阶段指标：vk=ckxk8.4 背包问题背包问题Knapsack Problem递推方程：递推方程：)(max)(max)(111kkkkkkkkkkkkxwsfxcsfxcsf终端条件：终端条件：fn1(sn1)=0 123123123max60406032510,0Zxxxxxx

50、x x x且为整数【例例8.5】用动态规划方法求解下列整数规划用动态规划方法求解下列整数规划【解解】终端条件：终端条件：f4(x4)=0 k=3时，递推方程时，递推方程60max)(max)(35/04433/03333333xsfxcsfsxwsx8.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最优决策是；最优决策是；s3为为04时，时，