第13讲 确定型动态规划

1、运筹学运筹学 第八、九章第八、九章 动态规划动态规划第八章 动态规划1建立动态规划模型的步骤建立动态规划模型的步骤 1 1、划分阶段、划分阶段划分阶段是运用动态规划求解多阶段决策问题的第一划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予人为地赋予“时间时间”概念，以便划分阶段。概念，以便划分阶段。 2 2、正确选择状态变量、正确选择状态变量Sk选择变量既要能确切描述过程演变又要满足无后效性，选择变量既要能

2、确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。一般地，状态而且各阶段状态变量的取值能够确定。一般地，状态变量的选择是从过程演变的特点中寻找。变量的选择是从过程演变的特点中寻找。 3 3、确定决策变量、确定决策变量Uk及允许决策集合及允许决策集合Dk通常选择所求解问题的关键变量作为决策变量，同时通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。要给出决策变量的取值范围，即确定允许决策集合。运筹学运筹学 第八、九章第八、九章 动态规划动态规划第八章 动态规划2 4 4、确定状态转移方程、确定状态转移方程Sk+1=Tk(Sk,Uk) 根

3、据根据k 阶段状态变量和决策变量，写出阶段状态变量和决策变量，写出k+1阶段状态变量，阶段状态变量，状态转移方程应当具有递推关系。状态转移方程应当具有递推关系。 5 5、正确写出指标函数、正确写出指标函数V Vk,n的关系，它应满足下面三个的关系，它应满足下面三个性质：性质：V Vk,n是定义在全过程和所有后部子过程上的数量函数是定义在全过程和所有后部子过程上的数量函数具有可分离性，并满足递推关系，即具有可分离性，并满足递推关系，即Vk,n(Sk,Uk ,Sk1,Sn+1)=k(Sk,Uk ,Vk1,n(Sk1,Uk1,Sn+1)函数函数k（Sk，Uk ，Vk1,n）对于变量对于变量Vk1,n

4、要严格单调。要严格单调。6 6、恰当地定义最优指标函数、恰当地定义最优指标函数 阶段指标函数是指第阶段指标函数是指第k 阶段的收益，最优指标函数是阶段的收益，最优指标函数是指从第指从第k 阶段状态出发到第阶段状态出发到第n 阶段末所获得收益的最优值。阶段末所获得收益的最优值。 运筹学运筹学 第八、九章第八、九章 动态规划动态规划第八章 动态规划3 动态规划模型分类 过程过程变量变量确定确定随机随机离散离散连续连续离散确定型离散确定型离散随机型离散随机型连续确定型连续确定型连续随机型连续随机型7、写出恰当的边界条件、写出恰当的边界条件 ，从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均用

5、了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优结果，就是这个问题的最优解，并找到相应的最优策略最优策略。第第6章章 动态规划动态规划动态规划的基本理论动态规划的基本理论 （2学时）学时）确定型动态规划确定型动态规划 （2学时）学时）随机型动态规划随机型动态规划 （1学时）学时） 动态规划的软件计算动态规划的软件计算 （1学时）学时）第14讲 确定型性动态规划 (6.2)最短路问题最短路问题资源分配问题资源分配问题生产与存储问题生产与存储问题动态规划和静态规划的关系动态规划和静态规划的关系自学背包问题、排序问题、货郎担问题自学背包问题、排序问题、货郎担问题 资源分配问题：资源分

6、配问题：把有限的资源把有限的资源( (如资金、材料、设备、人力等如资金、材料、设备、人力等) )分分配给若干使用者，而使某一指标为最优的问题即配给若干使用者，而使某一指标为最优的问题即为资源分配问题。为资源分配问题。资源可以有一种或若干种，资源可以有一种或若干种，只有一种资源可供分配的问题称之为一维资源分只有一种资源可供分配的问题称之为一维资源分配问题。配问题。资源分配问题 (6.2.2)例例1：某工业部门按国家计划的安排，拟将某高效率某工业部门按国家计划的安排，拟将某高效率的设备五台，分配给所属的甲、乙、丙三个工厂，各工的设备五台，分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可

7、以为国家提供的盈利如下表厂若获得这种设备之后，可以为国家提供的盈利如下表所示。问：这五台设备如何分配给各工厂，才能使国家所示。问：这五台设备如何分配给各工厂，才能使国家得到的盈利最大。得到的盈利最大。1、一维资源分配问题、一维资源分配问题 动态规划的数学模型动态规划的数学模型将三个分厂看作是三个阶段，即阶段变量将三个分厂看作是三个阶段，即阶段变量 k=1,2,3k=1,2,3; ;状态变量状态变量s sk k 表示表示第第k k 阶段初可分配的设备台数阶段初可分配的设备台数, ,0s0sk k 55; ;决策变量决策变量x xk k 表示表示第第k k 阶段分配给分厂阶段分配给分厂k k 的设

8、备台数，的设备台数， 允许决策集合允许决策集合X Xk k ( (s sk k)= )= x xk k 00 x xk k ssk k;状态转移方程为状态转移方程为 s sk+1k+1 = = s sk k - - x xk k ; ;阶段指标阶段指标P Pk k( (s sk k, , x xk k) ) 表示第表示第k k 阶段从阶段从s sk k台设备中分配给台设备中分配给k k 分厂分厂x xk k 台设备的阶段效益台设备的阶段效益; ; 最优指数函数最优指数函数f fk k( (s sk k) )表示第表示第k k阶段从阶段从s sk k 开始到最后阶段采开始到最后阶段采用最优分配策

9、略取得的最大的效益值用最优分配策略取得的最大的效益值; ;递推方程函数式递推方程函数式 0)()(),()(4411)(maxsfsfxsPsfkkkkkSXxkkkkk边界条件：基本方程：第三阶段第三阶段：设将S3台设备（S30,1,2,3,4,5）全部分配给丙厂时，最大盈利值为： f3(S3)maxP3(X3) 其中X3S30,1,2,3,4,5 X3*表示使得表示使得f3(S3)为最大值时的最优决策。为最大值时的最优决策。X3S3 P3(X3) f3(S3) X3* 01234500 0014 4126 62311 113412 124512125逆序求解逆序求解表表91第二阶段第二阶段

10、：设将设将S2台设备（台设备（S20,1,2,3,4,5）分配给乙厂和）分配给乙厂和丙厂时，对每一个丙厂时，对每一个S2值，都有一种最优分配方案，使得最大盈值，都有一种最优分配方案，使得最大盈利值为：利值为：f2(S2)max P2(X2)+ f3(S2X2) ，X20,1,2,3,4,5X2S2P2(X2)f3(S2X2) f2(S2) X2* 01234500 0010450 5120654100 102301156104110 1424012511106114110 161,250125121011116114110212表表92第一阶段第一阶段：设将S1台设备（S15）分配给甲厂、乙厂

11、和丙厂时，则最大盈利值为：f1(S1)max P1(X1)+ f2(5X1) 其中，X10,1,2,3,4,5X1S1P1(X1)f2(5X1) f1(5) X1* 0123455021 316 714 910 125 130210,2按计算表格的顺序反推，可知最优分配方案有两个：按计算表格的顺序反推，可知最优分配方案有两个：1）由）由X1*0，S2S1X1*505。再由。再由表表92，可知，可知X2*2。S3S2X2*523，故，故X3*S33。即得甲。即得甲厂分得厂分得0台，乙厂分得台，乙厂分得2台，丙厂分得台，丙厂分得3台。台。2）由）由X1*2，S2S1X1*523。再由表。再由表92

12、，可知，可知X2*2。S3S2X2*321，故，故X3*S31。即得甲。即得甲厂分得厂分得2台，乙厂分得台，乙厂分得2台，丙厂分得台，丙厂分得1台。台。以上两种最优方案的总盈利均为以上两种最优方案的总盈利均为21万元。万元。 例例2 2 机器负荷问题机器负荷问题某种机器可在高低两种不同的某种机器可在高低两种不同的负荷下进行生产，设机器在高负荷下生产的产量函数为负荷下进行生产，设机器在高负荷下生产的产量函数为g=8u1，其中，其中u u1 1为投入生产的机器数量，年完好率为为投入生产的机器数量，年完好率为a=0.7=0.7；在低负荷下生产的产量函数为在低负荷下生产的产量函数为h=5y，其中，其中

13、y y为投入生产的为投入生产的机器数量，年完好率为机器数量，年完好率为b=0.9。假定开始生产时完好的机。假定开始生产时完好的机器数量器数量S S1 110001000台，试问每年如何安排机器在高低负荷下台，试问每年如何安排机器在高低负荷下的生产，使在五年内生产的产品总产量最高。的生产，使在五年内生产的产品总产量最高。2、资源连续分配问题、资源连续分配问题 动态规划的数学模型动态规划的数学模型每年为一个阶段，每年为一个阶段，即阶段变量即阶段变量 k=1,2,3,4,k=1,2,3,4,5;5;状态变量状态变量s sk k 表示表示第第k k年初所拥有的完好机器台数，年初所拥有的完好机器台数，s

14、 s1 1 =1000=1000; ;决策变量决策变量u uk k 表示表示第第k k年投入高负荷生产的机器数年投入高负荷生产的机器数 ， 允许决策集合允许决策集合U Uk k ( (s sk k)= )= u uk k 00 u uk k s sk k; skuk表示为第表示为第k年初分配在低负荷下生产的机器数量。年初分配在低负荷下生产的机器数量。状态转移方程为状态转移方程为 s sk+1k+1 = =au uk k + +b b( (s sk ku uk k ) =) =0.7u0.7uk k+ +0.90.9( (s sk ku uk k) ) = =0.9s0.9sk k 0.2 0.

15、2u uk k; ;阶段指标阶段指标v vk k( (s sk k, , x xk k) ) 表示表示第第k k年的产量年的产量 ：v vk k( (s sk k, ,u uk k) = ) = 8u8uk k + +5 5( (s sk ku uk k ) )= =5s5sk k + +3u3uk k ; ;最优指数函数最优指数函数f fk k( (s sk k) )表示第表示第k k阶段从阶段从s sk k 开始到最后阶段采用最优开始到最后阶段采用最优分配策略实现的最大产量分配策略实现的最大产量; ;0)(5 , 4 , 3 , 2 , 1)2 . 09 . 0(35)(),()(6610

16、11)(maxmaxsfkusfussfusvsfkkkkkSukkkkkSUukkkkkkk边界条件：基本方程：解：解： K=5从第5阶段开始，向前逆推计算55)(),()(35maxmax5555066555055usSuSusfusvsff5(s5)是关于是关于u5 的单增函数，故的单增函数，故u*5 =s5 时，时，f5(s5)最大，最大， f5(s5)=8 s5 K=4440444405440554440444.12.12)2.09.0(835835)(),()(maxmaxmaxmax44444444ususussussfusvsfsusususuf4(s4)是关于是关于u4 的单

17、增函数，故的单增函数，故u*4 =s4 时，时， f4(s4)=13.6 s4 K=33303333043304433303328. 024.17)2 . 09 . 0(6 .13356 .1335)(),()(maxmaxmaxmax33333333ususussussfusvsfsusususuf f3 3( (s s3 3) )是关于是关于u u3 3 的单增函数，故的单增函数，故u*3 =s3 时，时， f3(s3)=17.52 s3 K=222022220322033222022504.08 .20)2 .09 .0(52.173552.1735)(),()(maxmaxmaxmax

18、22222222ususussussfusvsfsusususuf2(s2)是关于是关于u2 的的单调减函数单调减函数，故，故u*2 =0 时，时， f2(s2)=20.8 s2依次类推，可求得：u1*0，f1(s1)23.7 s1 最优生产策略：u*1 =0 ， u*2 =0 ， u*3 =s3 ，u*4 =s4 ，u*5 =s5 各阶段状态： s1 =1000， u*1 =0， s2 = 0.9s1 0.2u1 = 0.9s1 =900， u*2=0， s3 = 0.9s2 0.2u2 = 0.9s2 =810， u*3= s3 ， s4 = 0.9s3 0.2u3 = 0.7s3 =57

19、6， u*4= s4 s5 = 0.9s4 0.2u4 = 0.7s4=397 ， u*5= s5 s6 = 0.9s5 0.2u5 = 0.7s5=278即前两年应把年初全部完好的机器投入低负荷下即前两年应把年初全部完好的机器投入低负荷下生产，后三年应把年初全部完好的机器投入高负荷生产，后三年应把年初全部完好的机器投入高负荷下生产。这样最高产量为下生产。这样最高产量为23700台。台。 企业一年中的产品生产往往是分期分批生产的。企业一年中的产品生产往往是分期分批生产的。 组织每批产品的生产，都要花费一些生产准备组织每批产品的生产，都要花费一些生产准备费和存贮费用。费和存贮费用。 若某一时期增

20、大生产批量则可减少生产批次，若某一时期增大生产批量则可减少生产批次，从而降低生产成本。从而降低生产成本。 与此同时，批量大了，必然增加库存而使存与此同时，批量大了，必然增加库存而使存贮费用增加。贮费用增加。 在企业产品的生产成本、存贮费用、市场需求在企业产品的生产成本、存贮费用、市场需求量确定的情况下，正确计划各时期的生产量，量确定的情况下，正确计划各时期的生产量，既满足市场需求，又使总支出最少，这是一个既满足市场需求，又使总支出最少，这是一个多阶段决策问题。多阶段决策问题。生产存储问题 (6.2.3)1、生产计划问题：、生产计划问题：例例3 某工厂要对一种产品制订今后四个时期的生产某工厂要对

21、一种产品制订今后四个时期的生产计划，据估计在今后四个时期内，市场对于该产品的计划，据估计在今后四个时期内，市场对于该产品的需求量如下表所示。假定该厂生产每批产品的固定成需求量如下表所示。假定该厂生产每批产品的固定成本为本为3千元，若不生产就为千元，若不生产就为0，每单位产品成本为，每单位产品成本为1千千元，每个时期生产能力所允许的最大生产批量为不超元，每个时期生产能力所允许的最大生产批量为不超过过6个单位，每个时期末未售出的产品，每单位需付个单位，每个时期末未售出的产品，每单位需付存货费存货费0.5千元。还假定在第一个时期的初始库存量为千元。还假定在第一个时期的初始库存量为0，第四个时期之末的

22、库存量也为，第四个时期之末的库存量也为0。试问：该厂应如。试问：该厂应如何安排各个时期的生产与库存，才能在满足市场需求何安排各个时期的生产与库存，才能在满足市场需求的条件下，总成本最小。的条件下，总成本最小。 动态规划的数学模型动态规划的数学模型该问题分成四个阶段，该问题分成四个阶段，k k表示年度，表示年度，k k1 1，2 2，3 3，4 4; ;状态变量状态变量s sk-1k-1表示为第表示为第k年初的库存量，第年初的库存量，第k1年末的年末的库存量。库存量。决策变量决策变量u uk k 表示表示为第为第k k年的生产量，年的生产量，d dk k表示为第表示为第k k年的年的需求量。需求

23、量。 允许决策集合允许决策集合D Dk k( (s sk k)= )= u uk k 00 u uk k 66 状态转移方程为状态转移方程为 s sk k = =s sk-1k-1+ +u uk kdk; ;s s0 00; s40 第第k k年的生产成本为：年的生产成本为：66211300)(kkkkkkuuuuuc当，当当解：解：第第k期末库存量为期末库存量为sk的存贮费用为的存贮费用为: hk(sk)=0.5 sk总成本为总成本为:ck(uk)hk(sk)fk(sk)表示由第表示由第1年的初始库存为年的初始库存为0到第到第k年末的库存为年末的库存为Sk的最小总的最小总成本。成本。fk(s

24、k)min ck(uk)hk(sk)fk-1(sk-1) min ck(uk)hk(sk)fk-1(skdkuk) k=1,2,3,4边界条件边界条件f0(s0)0写出写出顺序递推关系式顺序递推关系式：由于由于库存量必须非负库存量必须非负, sk-1 skdkuk , ukskdkuk6 , 所以所以ukmin skdk，6sk 即使以后各期不再生产，须满足最后的库存即使以后各期不再生产，须满足最后的库存为为0。在。在0和和min ，6- dk 之间取值之间取值nkjjd1nkjjd1f1(s1)min c1(u1)h1(s1) f0(s0)s1 s0 +u1d1 d1=2s10，u12，f1

25、(0)5s11，u13，f1(1)6.5s12，u14，f1(2)842jjd对s1 9 之间的值分别进行计算。k1s13，u15，f1(3)9.5s14，u16，f1(4)11f2(s2)min c2(u2)h2(s2)f1(s2d2u2)k2其中，u2min s23，6s21，f2(1)min c2(u2)h2(1)f1(4u2)5 . 9565 . 65845 . 90min(0)f0(3)C(1)f0(2)C(2)f0(1)C(3)f0(0)Cmin121212125 .1155 . 075 . 65 . 0685 . 055 . 95 . 04115 . 00min(0)f5 . 0

26、(4)C(1)f5 . 0(3)C(2)f5 . 0(2)C(3)f5 . 0(1)C(4)f5 . 0(0)Cmin121212121243jjd对对s2 6 之间的值分别进行计算。之间的值分别进行计算。s20，f2(0)min c2(u2)h2(0)f1(3u2)u2=0 f2(0)9.5 u2=0u2=0f2(1)11.5，u2=0s22，f2(2)min c2(u2)h2(2)f1(5u2) 14，u2=5s23，f2(3)min c2(u2)h2(3)f1(6u2) 15.5，u2=6s24，f2(4)min c2(u2)h2(4)f1(7u2) 17.5，u2=6s25，f2(5)

27、min c2(u2)h2(5)f1(8u2) 19.5，u2=6s26，f2(6)min c2(u2)h2(6)f1(9u2) 21.5，u2=6145 . 955 .114140min(0)f0(2)C(1)f0(1)C(2)f0(0)Cmin232323f3(s3)min c3(u3)h3(s3)f2(s3d3u3)其中，其中，u3min s32，6 s3在在0至至d44之间之间k3s30，f3(0)minc3(u3)h3(0)f2(2u3)u3=0s31，f3(1)min c3(u3)h3(1)f2(3u3) 16 u3=0,3s32，f3(2)min c3(u3)h3(2)f2(4u3

28、) 17.5 u3=4f3(0)14 u3=0； f3(1) 16 u3=0,3； f3(2)17.5 u3=4f3(3)19 u3=55 .20140716065 .170519045 .2000min(0)f0(4)C(1)f0(3)C(2)f0(2)C(3)f0(1)C(4)f0(0)Cmin3434343434所以，所以，u4=0，u3=6，u2=0，u1=5, 最小总成本为最小总成本为20.5千元千元f4(s4)min c4(u4)h4(s4)f3(s4d4u4)其中，其中，u4min s44，6 s40k4f4(0)min c4(u4)h4(0)f3(4u4)u4=0f3(4)20

29、.5 u3=6例例4：某车间需要按月在月底供应一定数量的某种部件给总装：某车间需要按月在月底供应一定数量的某种部件给总装车间，由于生产条件的变化，该车间在各月份中生产每单位这种车间，由于生产条件的变化，该车间在各月份中生产每单位这种部件所需耗费的工时不同，各月份的生产量于当月的月底前，全部件所需耗费的工时不同，各月份的生产量于当月的月底前，全部要存入仓库以备后用。已知总装车间的各个月份的需求量以及部要存入仓库以备后用。已知总装车间的各个月份的需求量以及在加工车间生产该部件每单位数量所需工时数如下表所示。在加工车间生产该部件每单位数量所需工时数如下表所示。设仓库容量限制为设仓库容量限制为H=9，

30、开始库存量为，开始库存量为2，期终库存量为，期终库存量为0，要，要求制定一个半年的逐月生产计划，既使得满足需要和库容量的限求制定一个半年的逐月生产计划，既使得满足需要和库容量的限制，又使得生产这种部件的总耗费工时数为最少。制，又使得生产这种部件的总耗费工时数为最少。月份月份(k)6需求量需求量(dk)0单位工时单位工时(ak)201011181317458532740123动态规划的数学模型动态规划的数学模型 该问题分成六个阶段阶段，k表示月份，k1,2,3,4,5,6 设sk表示为第k月初的库存量，第k1月末的库存量。 uk表示为第k月的生产量，dk表示为第k月的需求量。 状态转移方程：状态

31、转移方程：sk+1skukdk ; dkskH 允许决策集合：允许决策集合：D k(sk) uk : uk 0, dk+1skukdkH s12 s70 fk(Sk)表示在第k月的库存为sk时，从第k月到第6月所生产部件的最小累计工时数。写出递推关系式：递推关系式：fk(Sk)minak(uk)fk+1(sk1) min ak(uk)fk+1(skukdk) k=0,1,2,3,4,5,6边界条件边界条件: f7(S7)0解：解：s7s6u6d6s70，u60 s6d64 f6(s6)0k6s6s5u5d5 s5u511f5(s5)mina5(u5)f6(s6) 10(11s5)11010s5

32、 u5*11 s5k5f4(s4)mina4(u4)f5(s5)min20 u4+11010 (s4u42) = min10 u410 s4130dk+1skukdkH ，dk+1dkskukHdk sk 9s4 u411s4又又uk0 ;max0, 9S4 u411s4f4(s4)10(9s4) 10 s4130=22020 s4 ; u4*9s4k4s5s4u4d4 s4u42s5s4s3u3d3 s3u33s4k3f2(s2)mina2(u2)f3(s3)min13 u2+24417 (s2u25) = min4u217 s23298s2 u214s2又又uk0 max0, 8s2 u2

33、14s2f2(s2)4(14s2) 17 s2329=27313 s2 u2*14s25s3 u312s3;又又uk0 max0, 5s3 u312s3f3(s3)3(12s3) 20 s3280=24417 S3 u3*12s3f3(s3)mina3(u3)f4(s4)min17 u3+22020 (s3 u33) = min3u320 s3280k2s3s2u2d2 ,s2u25s3f1(s1)mina1(u1)f2(s2)min18u1+27313(s1u18) =min5u113 s137713s1 u117s1;又又uk0 max0, 13s1 u117s1f1(S1)5(13s1)

34、 13s1377=44218s1 U1*13s1k1f0(s0)mina0(u0)f1(s1)min11u0+44218u018 s0= min7u018s04428s0 u09s0又又uk0 max0, 8s0 u09S0f0(s0)7(9s0) 18s0442 s0=2，f0(s0)357 u0*9s07k0s2s1u1d1 s1u18s2s1s0u0d0 , s0u0s1u0*7, u1*4，u2*9，u3*3，u4*0，u5*4 最小工时数为最小工时数为357。3 3 动态规划和静态规划关系动态规划和静态规划关系 对于某些静态规划问题对于某些静态规划问题, ,可以人为引入时间因素可以人

35、为引入时间因素, ,适当引入阶段变量、状态、决策变量可把它看作适当引入阶段变量、状态、决策变量可把它看作是按阶段进行的动态规划问题。是按阶段进行的动态规划问题。线性规划和非线性规划所研究的问题，通常都线性规划和非线性规划所研究的问题，通常都是与时间无关的，故又可以称为静态规划。是与时间无关的，故又可以称为静态规划。 静态规划模型静态规划模型njxaxxxxgxgxgzjnnn, 2 , 1 0 )()()( max212211其动态规划方程：其动态规划方程：0)(1 , 1, )()(max)(1111)(nnkkkksDxkksfnnksfxgsfkkk状态转移方程为状态转移方程为sk+1=

36、skxks1=a（1）逆推解法：）逆推解法： 设已知初始状态为s1，并假定最优值函数fk(sk)为表示第k阶段的初始状态为sk，从k阶段到n阶段得到最大效益。),x(sv)(sfnnn)(sDxnnnnn max 在第n阶段;111),x(sTsnnnn)(sfsxxnnnnn最优值最优解),( 在第n-1阶段max11111111)(sf),x(sv)(sfnnnnn)(sDxnnnnn)(sfsxxnnnnn11111),(最优值得最优解;1),x(sTskkkkmax2211111111)(sf),x(sv)(sf)(sDx;1112),x(sTs 在第1阶段)(sfsxxkkkkk最优

37、值最优解),( 在第k阶段max11)(sf),x(sv)(sfkkkkk)(sDxkkkkk)(sfsxx11111),(最优值得最优解 由于初始状态s1已知，)(sfsxx11111)(和可确定 按递推过程的相反顺序推算可得所要求结果例例5 用动态规划逆推解法求解用动态规划逆推解法求解csxssxsxsxxxcxssxcxsscs1122233332122311121,或设3,2, 1,0)0(max3213221ixccxxxxxxzi 按变量个数划分为3个阶段，设状态变量为s1, s2 s3, s4 ，s1c。取x1,x2,x3为决策变量；指标函数按乘积方式结合。最优值函数fk(sk)

38、表示为第k阶段的初始状态为sk，从k阶段到3阶段所得的最大值。csxsxsx1122330 ,0 ,则有解：解：33333333maxsxs)(x)(sfsx及最优解为极大值点，而22232222222222232,026222sxsdxhdxsdxhdsx22322232274sxs)(sf及最优解)(032032222222222舍去和得由xsxxsxdxdh),(max)(maxmax2220222203322022222222xshxsx)(sfx)(sfsxsxsx),(max)(274maxmax111031110221011111111xshxsx)(sfx)(sfsxsxsx4

39、1641maxc(c)fzcs 1c)(sfcx41;4133332222161;2132c)(sfcsxcccxss4341112cxcxcx41;21;41321411641;41c(c)fcxcccxss412143223411111641;41s)(sfsx最优解为：最优解为：（2）顺推解法：）顺推解法： 设已知终止状态为设已知终止状态为sn+1，并假定最优值函数，并假定最优值函数fk(s)为表示第为表示第k阶段的结束状态为阶段的结束状态为s，从，从1阶段到阶段到k阶阶段得到最大效益。段得到最大效益。),(,max121111121111xsTs),x(sv)(sf)(sDx其中 在第

40、在第1阶段阶段;2322),x(sTs)(sfsxx21211),(最优值最优解 在第在第2阶段阶段max2122232222)(sf),x(sv)(sf)(sDx )(sfsxx32322),(最优值得最优解 状态转移方程为：状态转移方程为：),(1kkkkxsTs12ks1u1s2u2s3skuksk+1;1),x(sTsnnnn)(sfsxxnnnnn11),(最优值最优解 在第在第k阶段阶段max11)(sf),x(sv)(sfnnnnn)(sDxnnnnn 由于终止状态由于终止状态sn+1已知，已知，)(sfsxxnnnnn11)(和可确定 按计算过程的相反顺序推算可得所要求结果按计

41、算过程的相反顺序推算可得所要求结果例例6csxssxsxsxxxcxxsxssxcxsscs 4333221212323423233434,或或设设3,2, 1,0)0(max3213221ixccxxxxxxzi 按变量个数划分为按变量个数划分为3个阶段，设状态变量为个阶段，设状态变量为s1, s2 s3, s4 ，s4c。取。取x1,x2,x3为决策变量；指标函为决策变量；指标函数按乘积方式结合。最优值函数数按乘积方式结合。最优值函数fk(sk+1)表示为第表示为第k阶段末的结束状态为阶段末的结束状态为sk+1，从，从1阶段到阶段到k阶段所阶段所得的最大值。得的最大值。csxsxsx433

42、2210 ,0 ,则有用顺推解法求解用顺推解法求解解：解：21212121maxsxs)(x)(sfsx及最优解为极大值点，而32332222223222232,026232sxsdxhdxsdxhdsx32332232274sxs)(sf及最优解)(032032232223222舍去和得由xsxxsxdxdh),(max)(maxmaxmax2320232202220212203232323232xshxsxsx)(sfx)(sfsxsxsxsx ),(max)(274max274maxmax343033430333032304343434343xshxsxsx)(sfx)(sfsxsxsx

43、sx443641maxc)(sfzcs 4c)(sfcx41;4121133232161;2132c)(sfcsxcccxss4341343cxcxcx41;21;413214433641;41c)(sfcxcccxss412143232444343641;41s)(sfsx最优解为：最优解为：例7 用动态规划方法解下面问题9,2,333222111sxssxssx设3 , 2 , 1, 09231224max321232221ixxxxxxxFi 按变量个数划分为按变量个数划分为3个阶段，设状态变量为个阶段，设状态变量为s0, s1 s2, s3 ，记，记s39。取。取x1,x2,x3为决策

44、变量；指标函数按加为决策变量；指标函数按加法方式结合。最优值函数法方式结合。最优值函数fk(sk)表示为第表示为第k阶段末的阶段末的结束状态为结束状态为sk，从，从1阶段到阶段到k阶段所得的最大值。阶段所得的最大值。3322110,20,3sxsxsx则有解：解：3944max11223111111sxs)x()(sfsx及最优解42,9402222222s)s(hs)(h222222780916914sxsxdxdh得由),(max)2(94max94maxmax2322022222202222011222022222212222xshxsxsx)(sfx)(sfsxsxsxsx094222

45、22xs)(sf及相应的最优解 该点不在允许决策集合内，因而最大值必在两端上选取该点不在允许决策集合内，因而最大值必在两端上选取),(max)(94122max122max33302332022203333333333xshxsx)(sfx)(sfsxsxsx122,129402332233s)(shs)(h174max,9;0;0321Fxxx最优解为：最优解为：233333112098944sxsxdxdh得由，该点为极小值点09442332dxhd332333122sxs)(sf及相应的最优解 由于s3未知，须对s3求极值122maxmax239033034s)(sfscs 当s39时，

46、 f3(s3)取最大。 f3(s3)292+12174 按计算过程的相反顺序推算可得所要求结果判断题判断题 1.1.动态规划模型中动态规划模型中, ,问题的阶段数目等于问题中子问问题的阶段数目等于问题中子问题的数目题的数目; ; 2.2.动态规划中动态规划中, ,定义状态时应保证在各个阶段中所做定义状态时应保证在各个阶段中所做决策的相互独立性决策的相互独立性; ; 3.3.动态规划的最优性原理保证了从某一状态开始的动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已作出的决策未来决策独立于先前已作出的决策; ; 4.4.对于一个动态规划问题对于一个动态规划问题, ,应用顺推或逆推解法

47、可能应用顺推或逆推解法可能会得到不同的结果；会得到不同的结果； 5.5.假如一个线性规划问题含有假如一个线性规划问题含有5 5个变量和个变量和3 3个约束条个约束条件，则用动态规划求解时将划分为件，则用动态规划求解时将划分为3 3个阶段，每个阶个阶段，每个阶段的状态将由一个五维的向量组成；段的状态将由一个五维的向量组成； 6.6.动态规划问题的基本方程是将一个多阶段的决策动态规划问题的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的决策问问题转化为一系列具有递推关系的单阶段的决策问题。题。作业：习题6 1，2，4 有一个徒步旅行者，其可携带物品重量的限度为有一个徒步旅行者，其

48、可携带物品重量的限度为a 公公斤，设有斤，设有n 种物品可供他选择装入包中。已知每种物品种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？的物品（各几件），使所起作用（使用价值）最大？物品物品 1 2 j n重量（公斤重量（公斤/ /件）件） a1 a2 aj an每件使用价值每件使用价值 c1 c2 cj cn 这就是背包问题。类似的还有工厂里的下料问题、运这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。输中的货物装载问题

49、、人造卫星内的物品装载问题等。背包问题 (选学)设设xj 为第为第j 种物品的装件数（非负整数）则问题的数学种物品的装件数（非负整数）则问题的数学模型如下：模型如下： ). 2 . 1(0max1njxaxaxcZjnijjjnjjj 且且为为整整数数动态规划的数学模型动态规划的数学模型 按照装入物品的种类划分阶段，按照装入物品的种类划分阶段，k=1，2，n； 状态变量状态变量sk表示装入第表示装入第k种至第种至第n种物品的总重量种物品的总重量 决策变量决策变量xk表示装入第表示装入第k种物品的件数；。种物品的件数；。 状态转移方程为：状态转移方程为：sk+1=skakxk 允许决策集合为：允

50、许决策集合为： 阶段指标函数阶段指标函数ck（xk）表示第表示第k阶段装入第阶段装入第k种商品种商品xk件时件时的价值的价值 fk(sk)表示第表示第k阶段装入物品总重量为阶段装入物品总重量为sk时的最大价值时的最大价值为整数kkkkkkkxasxxsD,0)(kkaskkas其中 表示不超过 的最大整数；动态规划基本方程为：动态规划基本方程为：nkxasfxcsfkkkkkkasxkkkkk2 )(max)(10其中当当 k=1 时，有：时，有：的最大整数表示不超过其中1111111 , )(asasasxascsfkkkkk例题：求下面背包问题的最优解例题：求下面背包问题的最优解且为整数0

51、,55231258max321321321xxxxxxxxxZ物品物品 1 2 3重量（公斤）重量（公斤） 3 2 5使用价值使用价值 8 5 12解：解：a5 ，问题是求，问题是求 f3(5) )55(12max)5(323503333xfxfxax 整整数数 )1()0(223231032355032350333333333)0(12),5(0max)55(12max)55(12max)55(12max)5(xxxxxxaxffxfxxfxxfxf ，整整数数整整数数 5 5 )( 2)1()0(1112122, 10212250212502222222222)1(10),3(5),5(0

52、max)25(max)25(max)25(5max)5(xxxxxxxaxfffxfxxfxxfxf，整数整数整数整数 )0()0(0max)20(max)20(max)20(5max)0(1)0(121202122002120022222222ffxfxxfxxfxfxxxxxax 5 5 整数整数整数整数)0(0308)0()0(0318)1()1(8338)3()1(8358)5(1111111111111111 xxcfxxcfxxcfxxcf ) 1, 1(1310, 85, 8max) 1 (10),3(5),5(0max)5(212)1()0(1112222 xxffffxxx

53、)( )0, 0(0)0()0(0max)0(211)0(122 xxfffx )0,1,1(13012,130max)0(12),5(0max)5(321)1()0(22333 xxxfffxx所以，最优解为所以，最优解为 X（1 . 1 . 0），），最优值为最优值为 Z = 13。 排序问题指排序问题指n 种零件经过不同设备加工是的顺序问题。种零件经过不同设备加工是的顺序问题。其目的是使加工周期为最短。其目的是使加工周期为最短。 1、n 1 排序问题排序问题 即即n 种零件经过种零件经过1 种设备进行加工，如何安排？种设备进行加工，如何安排？14682023交货日期（交货日期（d）451

54、73加工时间（加工时间（t）零件代号零件代号2j1j3j4j5j例、例、排序问题 (选学) （1）平均通过设备的时间最小）平均通过设备的时间最小 按零件加工时间非负次序排列顺序，其时间最小。（即按零件加工时间非负次序排列顺序，其时间最小。（即将加工时间由小到大排列即可）将加工时间由小到大排列即可）1j2j3j4j5j零件加工顺序零件加工顺序 工序时间工序时间13457 实际通过时间实际通过时间1481320 交货时间交货时间82314620 平均通过时间平均通过时间2 .9)1481320(51 x延迟时间延迟时间 = 13 6 = 7 （2）按时交货排列顺序）按时交货排列顺序1j2j3j4j

55、5j零件加工顺序零件加工顺序 工序时间工序时间13457 实际通过时间实际通过时间56101720 交货时间交货时间82314620 平均通过时间平均通过时间6 .11)56101720(51 x延迟时间延迟时间 = 0 （3）既满足交货时间，又使平均通过时间最小）既满足交货时间，又使平均通过时间最小1j2j3j4j5j零件加工顺序零件加工顺序 工序时间工序时间13457 实际通过时间实际通过时间1691320 交货时间交货时间82314620延迟时间延迟时间 = 0 平均通过时间平均通过时间8 .9)1691320(51 x 2、n 2 排序问题排序问题 即即n 种零件经过种零件经过2 种设备进行加工，如何安