数学方法动态规划

数学方法动态规划第1页，共163页，2023年，2月20日，星期六动态规划(D.P.–DynamicProgram)是解决多阶段决策过程最优化问题的一种方法。

动态的含义：动态规划方法与“时间”关系很密切，随着时间过程的发展而决定各时段的决策，产生一个决策序列，这就是“动态”的意思。一、多阶段决策问题的最优化第2页，共163页，2023年，2月20日，星期六动态规划的起源：

1951年,(美)数学家R.Bellman等人，根据多阶段序贯决策问题的特点，提出了著名的“最优性原理”。将多阶段决策问题转变为一系列的互相联系的单阶段决策问题，然后，逐个阶段予以解决，最后再形成总体解决。从而创建了求解优化问题的新方法——动态规划。1957年，他的名著《动态规划》出版。一、多阶段决策过程的最优化第3页，共163页，2023年，2月20日，星期六最优性原理:作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优子策略。简言之，最优策略的子策略总是最优的。一、多阶段决策过程的最优化第4页，共163页，2023年，2月20日，星期六动态决策问题分类：1、按数据给出的形式分为：离散型动态决策问题。连续型动态决策问题。2、按决策过程演变的性质分为：确定型动态决策问题。随机型动态决策问题。一、多阶段决策过程的最优化第5页，共163页，2023年，2月20日，星期六例1生产与存贮问题要求确定一个逐月的生产计划，在满足需求条件下，使一年的生产与存贮费用之和最小？

例2投资决策问题某公司现有资金Q万元，在今后5年内考虑给A，B，C，D4个项目投资？例3设备更新问题现企业要决定一台设备未来8年的更新计划，问应在哪些年更新设备可使总费用最小？一、多阶段决策过程的最优化第6页，共163页，2023年，2月20日，星期六例4基建投资问题一家公司有三个工厂，每个厂都需要进行扩建。公司用于扩建的资金总共为7万元。各个厂的投资方案及扩建后预期可获得的利润如表所示(单位：万元)。现在公司要确定各厂投资多少才能使公司的总利润达到最大？

厂名方案1方案2方案3方案4投资数利润投资数利润投资数利润投资数利润一厂001528510二厂001339411三厂0027311413一、多阶段决策过程的最优化第7页，共163页，2023年，2月20日，星期六例5货船装运问题有四种货物准备装到一艘货船上。第i(i＝1．2，3，4)种货物的每一箱重量是wi(单位：吨)，其价值是vi(单位：干元)，如表所示。假定这艘货船的总载重量是10吨，现在要确定这四种货物应各装几箱才能使装载货物的总价值达到最大？

货物i单位重量wi单位价值vi124212347435一、多阶段决策过程的最优化第8页，共163页，2023年，2月20日，星期六例6

最短路程问题假定从A地到E地要铺设一条管道，其中要经过若干个中间点(如图)。图中两点之间连线上的数字表示两地间的距离，现在要选择一条铺设管道的路线使总长度最短。AB1B2B3C1C2C3D1D2E367769523835436943一、多阶段决策过程的最优化第9页，共163页，2023年，2月20日，星期六

动态规划是解决多阶段决策问题的一种方法。所谓多阶段决策问题是指这样的决策问题：其过程可分为若干个相互联系的阶段，每一阶段都对应着一组可供选择的决策，每一决策的选定即依赖于当前面临的状态，又影响以后总体的效果。当每一阶段的决策选定以后，就构成一个决策序列，称为一个策略，它对应着一个确定的效果。多阶段决策问题就是寻找使此效果最好的策略。二、基本概念和基本原理第10页，共163页，2023年，2月20日，星期六二、基本概念和基本原理1、阶段：将所给问题的过程，按时间或空间特征分解成若干互相联系的阶段，以便按次序去求每阶段的解，常用字母k表示阶段变量。动态规划模型要用到的概念：(1)阶段;(2)状态;(3)决策和策略;(4)状态转移;(5)指标函数。第11页，共163页，2023年，2月20日，星期六2、状态：各阶段开始时的客观条件叫做状态。状态变量：描述各阶段状态的变量，用sk表示第k阶段的状态变量。状态集合：状态变量的取值集合，用Sk表示。一阶段：S1＝{A}二阶段：S2＝{B1,B2,B3}三阶段：S3＝{C1,C2,C3}四阶段：S4＝{D1,D2}AB1B2B3C1C2C3D1D2E367769523835436943二、基本概念和基本原理第12页，共163页，2023年，2月20日，星期六3、决策：当各段的状态取定以后，就可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策。决策变量：表示决策的变量，称为决策变量，常用uk(sk)表示第k阶段当状态为sk时的决策变量。允许决策集合：决策变量的取值往往限制在一定范围内，我们称此范围为允许决策集合，用Dk(sk)表示第k阶段从状态sk出发的允许决策集合。D2(B1)={C1,C2}D2(B2)={C1,C2,C3}如状态为B1时选择C2，可表示为：u2(B1)=C2二、基本概念和基本原理第13页，共163页，2023年，2月20日，星期六策略：各段决策确定后，整个问题的决策序列就构成一个策略，用p1,n{u1(s1),u2(s2),...un(sn)}表示。允许策略集合：对每个实际问题，可供选择的策略有一定范围，称为允许策略集合，记作P1,n，使整个问题达到最优效果的策略就是最优策略。AB1B2B3C1C2C3D1D2E367769523835436943p1,4{B1,C1,D1,E}二、基本概念和基本原理第14页，共163页，2023年，2月20日，星期六4、状态转移方程：动态规划中本阶段的状态往往是上一阶段状态和上一阶段的决策结果。第k段的状态sk，本阶段决策为uk(sk)，则第k+1段的状态sk+1也就完全确定，它们的关系可用公式表示：sk+1=Tk(sk,uk)sk+1=uk(sk)AB1B2B3C1C2C3D1D2E367769523835436943二、基本概念和基本原理第15页，共163页，2023年，2月20日，星期六

5、指标函数：用于衡量所选定策略优劣的数量指标。它分为阶段指标函数和过程指标函数。

阶段指标函数是指第k段，从状态sk出发，采取决策uk时的效益，用d(sk,uk)表示。d(B1,C2)一个n段决策过程，从1到n叫作问题的原过程，对于任意一个给定的k(1≤k≤n)，从第k段到第n段的过程称为原过程的一个后部子过程。V1,n(s1,p1,n)表示初始状态为s1采用策略p1,n时原过程的指标函数值;Vk,n(sk,pk,n)表示在第k段，状态为sk采用策略pk,n时,后部子过程的指标函数值。

最优指标函数记为fk(sk)：表示从第k段状态sk采用最优策略到过程终止时的最佳效益值。二、基本概念和基本原理第16页，共163页，2023年，2月20日，星期六最简单的方法－－穷举法。共有多少条路径，依次计算并比较。动态规划方法－－本方法是从过程的最后一段开始，用逆序递推方法求解，逐步求出各段各点到终点的最短路线，最后求得起始点到终点的最短路线。二、基本概念和基本原理第17页，共163页，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2练习：求从A到E的最短路径。二、基本概念和基本原理第18页，共163页，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0二、基本概念和基本原理第19页，共163页，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0二、基本概念和基本原理第20页，共163页，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5二、基本概念和基本原理第21页，共163页，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5二、基本概念和基本原理第22页，共163页，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8二、基本概念和基本原理第23页，共163页，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7二、基本概念和基本原理第24页，共163页，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=8二、基本概念和基本原理第25页，共163页，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=21二、基本概念和基本原理第26页，共163页，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=14二、基本概念和基本原理第27页，共163页，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21二、基本概念和基本原理第28页，共163页，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态最优决策状态最优决策状态最优决策状态最优决策状态A（A，B2）B2二、基本概念和基本原理第29页，共163页，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态最优决策状态最优决策状态最优决策状态最优决策状态A（A，B2）B2（B2，C1）C1二、基本概念和基本原理第30页，共163页，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态最优决策状态最优决策状态最优决策状态最优决策状态A（A，B2）B2（B2，C1）C1（C1，D1）D1二、基本概念和基本原理第31页，共163页，2023年，2月20日，星期六2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态最优决策状态最优决策状态最优决策状态最优决策状态A（A，B2）B2（B2，C1）C1（C1，D1）D1（D1，E）E从A到E的最短路径为19，路线为A→B2→C1→D1→E二、基本概念和基本原理第32页，共163页，2023年，2月20日，星期六可以看出，在求解的各阶段，都利用了第k段和第k+1段的如下关系:这种递推关系称为动态规划的基本方程，第二个式子称为边界条件。这种在图上直接计算的方法称为标号法。二、基本概念和基本原理第33页，共163页，2023年，2月20日，星期六动态规划标号法较之穷举法的优点:第一，容易算出;其次，动态规划的计算结果不仅得到了从起始点到最终点的最短路线，而且得到了中间段任一点到最终点的最短路线。二、基本概念和基本原理第34页，共163页，2023年，2月20日，星期六动态规划方法的基本思想：(1)将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数．从而把问题化成一族同类型的子问题，然后逐个求解。(2)求解时从边界条件开始，逆(或顺)过程行进方向，逐段递推寻优。在每一个子问题求解时，都要使用它前面已求出的子问题的最优结果，最后一个子问题的最优解，就是整个问题的最优解。(3)动态规划方法是既把当前一段与未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法，因此每段的最优决策选取是从全局考虑的，与该段的最优选择一般是不同的。二、基本概念和基本原理第35页，共163页，2023年，2月20日，星期六三、动态规划模型的建立与求解（一）动态规划模型的建立（二）逆序解法与顺序解法（三）基本方程分段求解时的几种常用算法第36页，共163页，2023年，2月20日，星期六（一）动态规划模型的建立建立动态规划的模型关键，在于识别问题的多阶段特征，将问题分解成为可用递推关系式联系起来的若干子问题，或者说正确地建立具体问题的基本方程。而正确建立基本递推关系方程的关键又在于正确选择状态变量，保证各阶段的状态变量具有递推的状态转移关系sk+1=Tk(sk,uk)下面以资源分配问题为例介绍动态规划的建模条件及解法。三、动态规划模型的建立与求解第37页，共163页，2023年，2月20日，星期六例5某公司有资金10万元．若投资于项目i(i＝1，2，3）的投资额为xi时，其收益分别为g1(x1)＝4x1，g2(x2)＝9x2，g3(x3)＝2x32，问应如何分配投资数额才能使总收益最大?可以人为地赋予时段，把问题转化为一个3段决策过程。关键问题是如何正确选择状态变量，使各后部子过程之间具有递进关系。三、动态规划模型的建立与求解第38页，共163页，2023年，2月20日，星期六K=1K=2第k段时所以，建立动态规划模型：阶段k：本例中取1，2，3状态变量sk：第k段可以投资于第k项到第3个项目的资金数决策变量xk：决定给第k个项目投资的资金数。状态转移方程：sk+1＝sk-xk最优指标函数fk(sk)：当可投资金额数为sk时，投资第k-3项所得的最大收益数。基本方程为：三、动态规划模型的建立与求解第39页，共163页，2023年，2月20日，星期六建立动态规划模型的要点1、分析题意，识别问题的多阶段特性，按时间或空间的先后顺序适当地划分为满足递推关系的若干阶段。2、正确地选择状态变量，使其具备两个必要待征：(1)可知性；(2)能够确切地描述过程的演变且满足无后效性。3、根据状态变量与决策变量的含义，正确写出状态转移方程sk+1=Tk(sk,uk)或转移规则。4、根据题意明确指标函数vk,n最优指标函数fk(sk)以及k阶段指标vk(sk,uk)的含义，并正确列出最优指标函数的递推关系及边界条件(即基本方程)。三、动态规划模型的建立与求解第40页，共163页，2023年，2月20日，星期六（二）逆序解法与顺序解法如果寻优的方向与多阶段决策过程的实际行进方向相反，从最后一段开始计算逐段前推，求得全过程的最优策略，称为逆序解法。顺序解法的寻优方向同于过程的行进方向，计算时从第一段开始逐段向后递推，计算后一阶段要用到前一阶段的求优结果，最后一段计算的结果就是全过程的最优结果。三、动态规划模型的建立与求解第41页，共163页，2023年，2月20日，星期六第一步：k=0状态：s1＝Af0(A)＝0求解步骤三、动态规划模型的建立与求解第42页，共163页，2023年，2月20日，星期六第二步：k=1状态：B1B2u1*(B1)=Au1*(B2)=Af1(B1)＝4f2(B2)＝5(4)(5)三、动态规划模型的建立与求解第43页，共163页，2023年，2月20日，星期六第三步：k=2状态：C1C2C3C4u2*(C1)=B1u2*(C2)=B1u2*(C3)=B1f2(C1)＝6f2(C2)＝7f2(C3)＝10u2*(C4)=B2f2(C4)＝12(4)(5)(6)(7)(10)(12)三、动态规划模型的建立与求解第44页，共163页，2023年，2月20日，星期六(4)(5)(6)(7)(10)(12)第四步：k=3状态：D1D2D3u3*(D1)=C1或C2u3*(D2)=C2u3*(D3)=C3f3(D1)＝11f3(D2)＝12f3(D3)＝14(11)(12)(14)三、动态规划模型的建立与求解第45页，共163页，2023年，2月20日，星期六第五步：k=4状态：E1E2u4*(E1)=D1u4*(E2)=D2f4(E1)＝14f4(E2)＝14(4)(5)(6)(7)(10)(12)(11)(12)(14)(14)(14)三、动态规划模型的建立与求解第46页，共163页，2023年，2月20日，星期六第六步：k=5状态：Fu5*(F)=E2f5(F)＝17(6)(4)(5)(7)(10)(12)(11)(12)(14)(14)(14)(17)即从A到F的最短距离为17。最优路线为：A－B1－C2－D2－E2－F三、动态规划模型的建立与求解第47页，共163页，2023年，2月20日，星期六逆序解法与顺序解法建模的不同点1．状态转移方式不同sk+1=Tk(sk,uk)sk=Tk(sk+1,uk)1状态s1决策u1效益v1(s1,u1)s2kskukvk(sk,uk)Sk+1nsnunvn(sn,un)Sn+11状态s1决策u1效益v1(s2,u1)s2kskukvk(sk+1,uk)Sk+1nsnunvn(sn+1,un)Sn+1三、动态规划模型的建立与求解第48页，共163页，2023年，2月20日，星期六2．指标函数的定义不同逆序解法中，我们定义最优指标函数fk(sk)表示第k段从状态sk出发，到终点后部子过程最优效益值，f1(s1)是整体最优函数值。顺序解法中，定义最优指标函数fk(sk+1)表示第k段时从起点到状态sk+1的前部子过程最优效益值。fn(sn+1)是整体最优函数值。三、动态规划模型的建立与求解第49页，共163页，2023年，2月20日，星期六3，基本方程形式不同(1)当指标函数为阶段指标和形式逆序解法则基本方程为：则基本方程为：顺序解法三、动态规划模型的建立与求解第50页，共163页，2023年，2月20日，星期六(2)当指标函数为阶段指标积形式逆序解法基本方程为：基本方程为：顺序解法三、动态规划模型的建立与求解第51页，共163页，2023年，2月20日，星期六B1C1D1235843三、动态规划模型的建立与求解第52页，共163页，2023年，2月20日，星期六逆序递推方程：（1）k=5时，状态它们到F点的距离即为最短路。第53页，共163页，2023年，2月20日，星期六AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（2）k=4时，状态它们到F点需经过中途点E，需一一分析从E到F的最短路：先说从D1到F的最短路有两种选择：经过E1,E2,比较最短。第54页，共163页，2023年，2月20日，星期六AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143这说明由D1到F的最短距离为7，其路径为相应的决策为：第55页，共163页，2023年，2月20日，星期六这说明由D2到F的最短距离为5，其路径为相应的决策为：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第56页，共163页，2023年，2月20日，星期六AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即D3到F的最短距离为5，其路径为相应的决策为：第57页，共163页，2023年，2月20日，星期六（3）k=3时，状态这说明由C1到F的最短距离为12，相应的决策为AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第58页，共163页，2023年，2月20日，星期六AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即由C2到F的最短距离为10，相应的决策为第59页，共163页，2023年，2月20日，星期六即由C3到F的最短距离为8，相应的决策为即由C4到F的最短距离为9，相应的决策为AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第60页，共163页，2023年，2月20日，星期六AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（4）k=2时，状态这说明由B1到F的最短距离为13，相应的决策为第61页，共163页，2023年，2月20日，星期六即由B2到F的最短距离为15，相应的决策为AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第62页，共163页，2023年，2月20日，星期六AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（1）k=1时，只有一个状态点A,则即由A到F的最短距离为17，相应的决策为第63页，共163页，2023年，2月20日，星期六所以最优路线为：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143再按计算顺序反推可得最优决策序列：第64页，共163页，2023年，2月20日，星期六顺序递推方程：AB1B2C1C2C3C4D1D2D3E1E2F4523687758453484356231431阶段2阶段3阶段4阶段5阶段行走方向第65页，共163页，2023年，2月20日，星期六最短路径：最短路长：注：顺序解法与逆序解法无本质区别，一般来说，当初始状态给定时用逆序解法，当终止状态给定时用顺序解法。若问题给定了一个初始状态与一个终止状态，则两种方法均可使用。第66页，共163页，2023年，2月20日，星期六1．离散变量的分段穷举算法

动态规划模型中的状态变量与决策变量若被限定只能取离散值，则可采用分段穷举法。如前面例4的求解方法就是分段穷举算法，由于每段的状态变量和决策变量离散取值个数较少，所以动态规划的穷举法要比一般的穷举法有效。用分段穷举法求最优指标函数值时，最重要的是正确确定每段状态变量取值范围和允许决策集合的范围。（三）基本方程分段求解时的几种常用算法三、动态规划模型的建立与求解第67页，共163页，2023年，2月20日，星期六2．连续变量的解法当动态规划模型中状态变量与决策变量为连续变量，就要根据方程的具体情况灵活选取求解方法，如经典解析方法、线性规划方法、非线性规划法或其它数值计算方法等。如在例5中，状态变量与决策变量均可取连续值而不是离散值，所以每阶段求优时不能用穷举方法处理。下面分别用逆序解法求解。三、动态规划模型的建立与求解第68页，共163页，2023年，2月20日，星期六例5：某公司有资金10万元．若投资于项目i(i＝1，2，3）的投资额为xi时，其收益分别为g1(x1)＝4x1,g2(x2)＝9x2,g3(x3)＝2x32，问应如何分配投资数额才能使总收益最大?三、动态规划模型的建立与求解第69页，共163页，2023年，2月20日，星期六其动态规划模型已建立如下：阶段k：本例中取1，2，3状态变量sk：第k段可以投资于第k项到第3个项目的资金数决策变量xk：决定给第k个项目投资的资金数。状态转移方程：sk+1＝sk-xk最优指标函数fk(sk)：当可投资金数为sk时，投资第k-3项所得的最大收益数。基本方程为：三、动态规划模型的建立与求解第70页，共163页，2023年，2月20日，星期六k＝3时三、动态规划模型的建立与求解第71页，共163页，2023年，2月20日，星期六k＝2时三、动态规划模型的建立与求解第72页，共163页，2023年，2月20日，星期六k＝1时三、动态规划模型的建立与求解第73页，共163页，2023年，2月20日，星期六k＝1时最优投资方案为全部资金投于第3个项目，可得最大收益200万元。三、动态规划模型的建立与求解第74页，共163页，2023年，2月20日，星期六例用动态规划解决下面问题解：此问题分三个阶段；取第k阶段决策变量为xk；状态变量sk表示从第k阶段到第3阶段“消耗”的数:指标函数为目标第k项之后部分的和式:三、动态规划模型的建立与求解第75页，共163页，2023年，2月20日，星期六状态转移方程：允许决策集合为允许状态集合最优值函数和边界条件三、动态规划模型的建立与求解第76页，共163页，2023年，2月20日，星期六逆向递归求解：三、动态规划模型的建立与求解第77页，共163页，2023年，2月20日，星期六最优函数值最优解是（指标函数最优值）回代求最优决策三、动态规划模型的建立与求解第78页，共163页，2023年，2月20日，星期六四、在经济管理中的应用（一）背包问题背包问题的一般提法是：一位旅行者携带背包去登山,已知他所能承受的背包重量限度为a千克，现有n种物品可供他选择装入背包。第i种物品的单件重量为ai干克、其价值(可以是表明本物品对登山的重要性的数量指标)是携带数量xi的函数ci(xi)(i＝1，2，…n)，问旅行者应如何选择携带各种物品的件数，以使总价值最大？其他如车、船、飞机、潜艇、人造卫星等工具的最优装载问题，机床加工中零件最优加工、下料问题、投资决策问题，均等同于背包问题。第79页，共163页，2023年，2月20日，星期六背包问题的动态规划模型1阶段k：将可装入物品按1，2，...，n排序，共划分为n个阶段，即k＝1，2，...，n。2状态变量sk+1：在第k段开始时，背包中允许装入前k种物品的总重量。3决策变量xk：装入第k种物品的件数。4状态转移方程：sk=sk+1-akxk5允许决策集合为：Dk(sk+1)＝{xk|o≤xk≤[sk+1/ak]，xk为整数}6最优指标函数fk(sk+1)表示在背包中允许装入物品的总重量不超过sk+1千克，采用最优策略只装前k种物品时的最大使用价值。7顺序递推方程：四、在经济管理中的应用第80页，共163页，2023年，2月20日，星期六例:有一辆最大货运量为10吨的卡车，用以装载3种货物．每种货物的单位重量及相应单位价值如表所示。应如何装载可使总价值最大?设第i种货物装载的件数为xi(i＝1，2，3)，则问题可表为货物编号I123单位重量（t）345单位价值ci456四、在经济管理中的应用第81页，共163页，2023年，2月20日，星期六K=1s2012345678910f1(s2)0004448881212x1*00011122233s2f1(s2)x1*建立动态规划模型，用列表法求解四、在经济管理中的应用第82页，共163页，2023年，2月20日，星期六K=2s3012345678910x2000001010101012012012c2+f2000445458589891012910121310f2(s3)00045589101213x2*00001101201s3x2c2+f2f2(s3)x2*四、在经济管理中的应用第83页，共163页，2023年，2月20日，星期六K=3所以x3*=0s3=s4-5x3=10-5*0=10所以x2*=1s2=s3-4x2=10-4*1=6所以x1*=2全部策略为：x1*=2x2*=1x3*=0，最大价值为13。四、在经济管理中的应用第84页，共163页，2023年，2月20日，星期六（二）生产经营问题—生产与存贮问题

在生产和经营管理中．经常遇到如何合理地安排生产计划、采购计划以及仓库的存货计划和销售计划，使总效益最高的问题。四、在经济管理中的应用第85页，共163页，2023年，2月20日，星期六例：某工厂生产并销售某种产品，已知今后四个月市场需求预测如表，又每月生产单位产品费用为：每月库存j单位产品的费用为E(j)＝0.5j(干元)，该厂最大库存容量为3单位，每月最大生产能力为6单位，计划开始和计划期末库存量都是零。试制定四个月的生产计划，在满足用户需求条件下总费用最小。假设第j+1个月的库存量是第j个月可销售量与该月用户需求量之差；而第i个月的可销售量是本月初库存量与产量之和。i（月）1234gi（需求）2324四、在经济管理中的应用第86页，共163页，2023年，2月20日，星期六(1)阶段：每个月为一个阶段，k＝1，2，3，4。(2)状态变量:sk为第k个月初的库存量。(3)决策变量:uk为第k个月的生产量。(4)状态转移方程：sk+1=sk+uk-gk(5)最优指标函数：fk(sk)表示第k月状态为sk时，采用最佳策略生产，从本月到计划结束（第4个月末）的生产与存贮最低费用。(6)基本方程：解：建立动态规划模型四、在经济管理中的应用第87页，共163页，2023年，2月20日，星期六K=4u4=4-s4s40123f4(s4)76.565.5u4(s4)4321s4f4(s4)u4(s4)四、在经济管理中的应用第88页，共163页，2023年，2月20日，星期六s30123u3(s3)234512340123012C+E+f41212.51313.511.51212.513811.51212.5811.512f3(s3)1211.588u3*(s3)2100K=3s3={0,1,2,3}s3u3(s3)C+E+f4f3(s3)u3*(s3)四、在经济管理中的应用第89页，共163页，2023年，2月20日，星期六s20123u2(s2)3456234512340123C+E+f31818.5161717.51815.516.51717.5151613.51714.515.5f2(s2)1615.51513.5u2*(s2)5430K=2s2={0,1,2,3}s2u2(s2)C+E+f3f2(s2)u2*(s2)四、在经济管理中的应用第90页，共163页，2023年，2月20日，星期六s10u1(s1)2345C+f22121.52221.5f1(s1)21u1*(s1)2K=1s1={0}s1u1(s1)C+f2f1(s1)u1*(s1)可得最佳生产计划为：第一个月生产2单位，第二个月生产5单位，第三个月不生产，第四个月生产4单位。四、在经济管理中的应用第91页，共163页，2023年，2月20日，星期六（三）设备更新问题企业中经常会遇到一台设备应该使用多少年更新最合算的问题。一般来说，一台设备在比较新时，年运转量大，经济收入高，故障少，维修费用少，但随着使用年限的增加，年运转量减少因而收入减少，故障变多，维修费用增加。如果更新可提高年净收入，但是当年要支出一笔数额较大的购买费。设备更新的一般提法为：在已知一台设备的效益函数，维修费用函数及更新费用函数条件下，要求在n年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使使n年总效益最大。四、在经济管理中的应用第92页，共163页，2023年，2月20日，星期六例11某台新设备的年效益及年均维修费、更新净费用如表7-15所示。试确定今后5年内的更新策略，使总收益最大。表7-15单位：万元

役龄项目012345效益54.543.7532.5维修费0.511.522.53更新费0.51.52.22.533.5第93页，共163页，2023年，2月20日，星期六解：以年限划分阶段k：1，2，3，4，512345决策变量:第k年初保留使用(keep)第k年初更新(replacement)状态变量:第k年初，设备已使用过的年数，称役龄。状态转移方程：第94页，共163页，2023年，2月20日，星期六在第k年设备已使用过t年（或役龄为t年），再使用1年时的效益。在第k年设备已使用过t年（或役龄为t年），再使用1年时的维修费用。在第k年卖掉一台役龄为t年的设备，买进一台新的设备的更新净费用。

役龄项目012345效益54.543.7532.5维修费0.511.522.53更新费0.51.52.22.533.5第95页，共163页，2023年，2月20日，星期六

役龄项目012345效益54.543.7532.5维修费0.511.522.53更新费0.51.52.22.533.5即：“买一部新机器的费用”－“卖一部t年役龄的旧机器的收益”。阶段指标函数：第96页，共163页，2023年，2月20日，星期六最优指标函数：第k年初，使用一台已用了年的设备，到第5年末的最大效益，有按逆序建立递推式：下面用逆序法求解：第97页，共163页，2023年，2月20日，星期六K=5时：此时，的所有可能取值为：1，2，3，4。下分别求最优指标函数值：12345第98页，共163页，2023年，2月20日，星期六

役龄项目012345效益54.543.7532.5维修费0.511.522.53更新费0.51.52.22.533.5此时，第99页，共163页，2023年，2月20日，星期六

役龄项目012345效益54.543.7532.5维修费0.511.522.53更新费0.51.52.22.533.5此时，第100页，共163页，2023年，2月20日，星期六

役龄项目012345效益54.543.7532.5维修费0.511.522.53更新费0.51.52.22.533.5此时，第101页，共163页，2023年，2月20日，星期六

役龄项目012345效益54.543.7532.5维修费0.511.522.53更新费0.51.52.22.533.5此时，第102页，共163页，2023年，2月20日，星期六

12343.532.52.31.7520.51.53.52.521.5第103页，共163页，2023年，2月20日，星期六12343.52.521.5K=5时最优值表第104页，共163页，2023年，2月20日，星期六K=4时：此时，的所有可能取值为：1，2，3。下分别求最优指标函数值：12345第105页，共163页，2023年，2月20日，星期六12343.52.521.5K=5时最优值表

役龄项目012345效益54.543.7532.5维修费0.511.522.53更新费0.51.52.22.533.5此时，第106页，共163页，2023年，2月20日，星期六12343.52.521.5K=5时最优值表

役龄项目012345效益54.543.7532.5维修费0.511.522.53更新费0.51.52.22.533.5此时，第107页，共163页，2023年，2月20日，星期六12343.52.521.5K=5时最优值表

役龄项目012345效益54.543.7532.5维修费0.511.522.53更新费0.51.52.22.533.5此时，第108页，共163页，2023年，2月20日，星期六1236.55.85.5K=4时最优值表第109页，共163页，2023年，2月20日，星期六K=3时：此时，的所有可能取值为：1，2。下分别求最优指标函数值：12345第110页，共163页，2023年，2月20日，星期六

役龄项目012345效益54.543.7532.5维修费0.511.522.53更新费0.51.52.22.533.5此时，1236.55.85.5K=4时最优值表第111页，共163页，2023年，2月20日，星期六

役龄项目012345效益54.543.7532.5维修费0.511.522.53更新费0.51.52.22.533.5此时，1236.55.85.5K=4时最优值表第112页，共163页，2023年，2月20日，星期六129.58.8K=3时最优值表第113页，共163页，2023年，2月20日，星期六K=2时：此时，只能取1。所以12345第114页，共163页，2023年，2月20日，星期六

役龄项目012345效益54.543.7532.5维修费0.511.522.53更新费0.51.52.22.533.5此时，129.58.8K=3时最优值表第115页，共163页，2023年，2月20日，星期六K=1时：此时，只能取0。所以12345第116页，共163页，2023年，2月20日，星期六

役龄项目012345效益54.543.7532.5维修费0.511.522.53更新费0.51.52.22.533.5此时，第117页，共163页，2023年，2月20日，星期六12345状态转移方程：上述计算递推回去，当时，由状态转移方程：知查得第118页，共163页，2023年，2月20日，星期六12345状态转移方程：有知129.58.8K=3时最优值表查知第119页，共163页，2023年，2月20日，星期六12345状态转移方程：查知1236.55.85.5K=4时最优值表第120页，共163页，2023年，2月20日，星期六12345状态转移方程：查12343.52.521.5K=5时最优值表第121页，共163页，2023年，2月20日，星期六故本题最优策略为，即第一年初购买的设备到第二、三、四、年初各更新一次，用到第5年末，其总效益为17万元。第122页，共163页，2023年，2月20日，星期六例2资源分配问题（离散型）例：设有6万元资金用于4个工厂的扩建，已知每个工厂的利润增长额同投资额的大小有关，见下表。问应如何确定对这四个工厂的投资额，使总利润增长额最大？投资额(j)工厂(i)010020030040050060010204260758590202545576570733018396178909540284765748085

表1利润增长额

（百元）第123页，共163页，2023年，2月20日，星期六解：把对四个工厂的投资依次看成4个阶段的决策过程，确定对第k个工厂的投资额看成第k个阶段的决策，k=1,2,3,4。图示如下：工厂1工厂2工厂3工厂4投资x1投资x2投资x3投资x4状态状态状态状态变量：可用于第k,k+1,…n个工厂的投资额。决策变量：第k阶段对第k个工厂的投资额。允许决策集：第124页，共163页，2023年，2月20日，星期六状态转移方程：其中阶段指标函数：第k阶段投资元时所产生的利润。（见上表）最优指标函数：第k阶段状态为且采取最佳投资策略，从第k个工厂以及以后的最大总利润。逆序法基本递推方程：第125页，共163页，2023年，2月20日，星期六工厂1工厂2工厂3工厂4投资x1投资x2投资x3投资x4状态状态状态投资额(j)工厂(i)010020030040050060040284765748085

表1利润增长额

（百元）解：（1）k=4时考虑：若到最后一个，第4个工厂投资时，还有资金，若投资于第4个工厂的资金为，则最大利润为第126页，共163页，2023年，2月20日，星期六工厂1工厂2工厂3工厂4投资x1投资x2投资x3投资x4状态状态状态投资额(j)工厂(i)010020030040050060040284765748085

表1利润增长额

（百元）（注意到此时=0）第127页，共163页，2023年，2月20日，星期六自然问：现在还有多少钱？即=？=0，100，200，300，400，500，600都有可能。下面分情况讨论：工厂1工厂2工厂3工厂4投资x1投资x2投资x3投资x4状态状态状态投资额(j)工厂(i)010020030040050060040284765748085

表1利润增长额

（百元）第128页，共163页，2023年，2月20日，星期六时，时，其他种情况类似讨论，我们把所有的结果汇总成一个表2。投资额(j)工厂(i)010020030040050060040284765748085

表1利润增长额

（百元）第129页，共163页，2023年，2月20日，星期六01002003004005006000100200300400500600002802847028476502847657402847657480028476574808502847657480850100200300400500600表2

k=4时决策表投资额(j)工厂(i)010020030040050060010204260758590202545576570733018396178909540284765748085

表1利润增长额

（百元）第130页，共163页，2023年，2月20日，星期六（2）k=3时到第三个工厂投资时，可利用的资金还有，若向第三个工厂投资（万元），则自此即以后最大利润为：

表1利润增长额

（百元）投资额(j)工厂(i)010020030040050060030183961789095同样问：=？，即现在还有多少钱？它是允许决策集上界。同理第131页，共163页，2023年，2月20日，星期六仅举一例：投资额(j)工厂(i)010020030040050060030183961789095

表1利润增长额

（百元）第132页，共163页，2023年，2月20日，星期六01002003004005006000100200300400500600002802847028476502847657402847657480028476574808502847657480850100200300400500600表2

k=4时决策表投资额(j)工厂(i)010020030040050060030183961789095表1利润增长额（百元）第133页，共163页，2023年，2月20日，星期六所有情况讨论结果汇总成下表：010020030040050060001002003004005006000+00+2818+00+4718+2839+00+6518+4739+2861+00+7418+6539+4761+2878+00+8018+7439+6561+7478+2890+00+8518+8039+7461+6578+4790+2895+0028476789108126000200300300300表3

k=3时决策表第134页，共163页，2023年，2月20日，星期六（3）k=2时仅举一例：第135页，共163页，2023年，2月20日，星期六投资额(j)工厂(i)010020030040050060020254557657073表1利润增长额（百元）第136页，共163页，2023年，2月20日，星期六010020030040050060001002003004005006000+00+2818+00+4718+2839+00+6518+4739+2861+00+7418+6539+4761+2878+00+8018+7439+6561+7478+2890+00+8518+8039+7461+6578+4790+2895+0028476789108126000200300300300表3

k=3时决策表第137页，共163页，2023年，2月20日，星期六关于的其它取值情况及相应的最优决策列于下表010020030040050060001002003004005006000+00+2825+00+4725+2845+00+6725+4745+2857+00+8925+6745+4757+2865+00+10825+8945+6757+4765+2870+00+12625+10845+8957+6765+4770+2873+002853739211413400100200100或200100200

表4k=2时决策表第138页，共163页，2023年，2月20日，星期六（4）k=1时，此时第139页，共163页，2023年，2月20日，星期六投资额(j)工厂(i)010020030040050060010204260758590表1利润增长额（百元）第140页，共163页，2023年，2月20日，星期六010020030040050060001002003004005006000+00+2825+00+4725+2845+00+6725+4745+2857+00+89