运筹学课件-第七章动态规划.ppt

《运筹学课件-第七章动态规划.ppt》由会员分享，可在线阅读，更多相关《运筹学课件-第七章动态规划.ppt（81页珍藏版）》请在三一办公上搜索。

1、第七章 动态规划,动态决策问题：决策过程具有阶段性和时序性(与时间有关)的决策问题。即决策过程可划分为明显的阶段。动态规划(D.P.Dynamic Program)：动态规划是解决多阶段决策过程最优化问题的一种方法。广泛应用于工业技术、生产管理、企业管理、经济、军事等领域。可用于解决最优路径问题、资源分配问题、生产计划与库存、投资、装载、排序等问题及生产过程的最优控制等。动态规划(D.P.)的起源：1951年,(美)数学家R.Bellman等提出最优化原理，从而建立动态规划，名著动态规划于1957年出版。动态决策问题分类：1、按数据给出的形式分为：离散型动态决策问题。连续型动态决策问题。2、按

2、决策过程演变的性质分为：确定型动态决策问题。随机型动态决策问题。其中离散确定型是最基本的，本章主要针对这种类型的问题，介绍动态规划的基本思想、原理和方法，这些对其它类型的问题也适用。,第七章 动态规划,一、多阶段决策过程的最优化二、基本概念和基本原理三、动态规划模型的建立与求解四、动态规划在经济管理中的应用,一、多阶段决策过程的最优化,多阶段决策过程：多阶段决策过程，本意是指这样一类特殊的活动过程，它们可以按时间顺序分解成若干相互联系的阶段，称为“时段”，在每一个时段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问题属序贯决策问题。动态的含义：动态规划方法与“时间”关系很密切，随着

3、时间过程的发展而决定各时段的决策，产生一个决策序列，这就是“动态”的意思。多阶段决策过程最优化的目标：达到整个活动过程的总体效果最优。,例1 生产与存贮问题 某工厂每月需供应市场一定数量的产品，并将所余产品存入仓库。一般某月适当增加产量可降低生产成本，但超产部分存入仓库会增加库存费用。要求确定一个逐月的生产计划，在满足需求条件下，使一年的生产与存贮费用之和最小。显然，可以把每个月作为一个阶段，全年分为12个阶段逐次决策。例2 投资决策问题 某公司现有资金Q万元，在今后5年内考虑给A，B，C，D 4个项目投资，这些项目投资的回收期限、回报率均不相同，问该公司应如何确定这些项目每年的投资额，使到第

4、5年末拥有资金的本利总额最大。这是一个5阶段决策问题。例3 设备更新问题 企业在使用设备时都要考虑设备的更新问题，因为设备越陈旧所需的维修费用越多，但购买新设备则要一次性支出较大的费用；现某企业要决定一台设备未来8年的更新计划，已预测了第j年购买设备的价格为Kj，设Gj为设备经过j年后的残值，Cj为设备连续使用j-1年后在第j年的维修费(j1，2，8)，问应在哪些年更新设备可使总费用最小。这是一个8阶段决策问题，每年年初要作出决策，是继续使用旧设备，还是购买新设备。,几个例子,几个例子,例4、(基建投资问题)一家公司有三个工厂，每个厂都需要进行扩建。公司用于扩建的资金总共为7万元。各个厂的投资

5、方案及扩建后预期可获得的利润如表所示(单位：万元)。,现在公司要确定时各厂投资多少才能使公司的总利润达到最大？解：在这个问题中，因为每个厂都有几种投资方案，所以要对每个厂作出一项决策，总共要作出三个决策。同时，这三个厂的总投资不能超过7万元。如果我们把每个厂看成是一个阶段，这就是一个多阶段的决策问题。,几个例子,例5、(货船装运问题)有四种货物准备装到一艘货船上。第i(i12，3，4)种货物的每一箱重量是wi(单位：吨)，其价值是vi(单位：干元)，如表所示。,假定这艘货船的总载重量是10吨，现在要确定这四种货物应各装几箱才能使装载货物的总价值达到最大。解：在这个问题中，因为对每一种货物要确定

6、装载的箱数，也就是要作出一项决策，所以总共要作出四个决策。同时，各种货物的总重量不能超过10吨。如果我们把每一种货物看成是一个阶段，这也是一个多阶段的决策问题。,几个例子,例6、(最短路程问题)假定从A地到E地要铺设一条管道，其中要经过若干个中间点(如图)。,图中两点之间连线上的数字表示两地间的距离，现在要选择一条铺设管道的路线使总长度最短。解：在问题中，从A到B1，B2，B3中的哪一个点要作出一项决策，从B1，B2，B3中的某点到C1，C2，C3中的哪一个点又要作出一项决策等。所以总共要作出四个决策。因此可以把整个路程分为A，B(包括B1，B2，B3)，C(包括C1，C2，C3)和D(包括D

7、l，D2)四个阶段。这是个多阶段的决策问题。,二、动态规划的基本概念和基本原理,1、阶段：将所给问题的过程，按时间或空间特征分解成若干互相联系的阶段，以便按次序去求每阶段的解，常用字母k表示阶段变量。,动态规划模型要用到的概念：(1)阶段;(2)状态;(3)决策和策略;(4)状态转移;(5)指标函数。,2、状态：各阶段开始时的客观条件叫做状态。状态变量：描述各阶段状态的变量，用sk表示第k阶段的状态变量状态集合：状态变量的取值集合，用Sk表示。动态规划中的状态应具有如下性质：当某阶段状态给定以后，在这阶段以后过程的发展不受这段以前各段状态的影响。无后效性。,一阶段：S1A二阶段：S2B1,B2

8、,B3三阶段：S3C1,C2,C3四阶段：S4D1,D2,3、决策：当各段的状态取定以后，就可以作出不同的决策（或选择），从而确定下一阶段的状态，这种决定称为决策。决策变量：表示决策的变量，称为决策变量，常用uk(sk)表示第k阶段当状态为sk时的决策变量。允许决策集合：决策变量的取值往往限制在一定范围内，我们称此范围为允许决策集合，用Dk(sk)表示第k阶段从状态sk出发的允许决策集合。,D2(B1)=C1,C2D2(B2)=C1,C2,C3如状态为B1时选择C2，可表示为：u2(B1)=C2,策略：各段决策确定后，整个问题的决策序列就构成一个策略，用p1,nu1(s1),u2(s2),.u

9、n(sn)表示。对每个实际问题，可供选择的策略有一定范围，称为允许策略集合，记作P1,n，使整个问题达到最优效果的策略就是最优策略。,4、状态转移方程：动态规划中本阶段的状态往往是上一阶段状态和上一阶段的决策结果。第k段的状态sk，本阶段决策为uk(sk)，则第k+1段的状态sk+1也就完全确定，它们的关系可用公式表示：sk+1=Tk(sk,uk),sk+1=uk(sk),5、指标函数：用于衡量所选定策略优劣的数量指标。它分为阶段指标函数和过程指标函数。阶段指标函数是指第k段，从状态sk出发，采取决策uk时的效益，用d(sk,uk)表示。d(B1,C2)一个n段决策过程，从1到n叫作问题的原过

10、程，对于任意一个给定的k(1k n)，从第k段到第n段的过程称为原过程的一个后部子过程。V1,n(s1,p1,n)表示初始状态为s1采用策略p1,n时原过程的指标函数值;而Vk,n(sk,pk,n)表示在第k段，状态为sk采用策略pk,n时,后部子过程的指标函数值。最优指标函数记为fk(sk)表示从第k段状态sk采用最优策略到过程终止时的最佳效益值。,f2(B1),f1(A),动态规划的基本思想,最简单的方法穷举法。共有多少条路径，依次计算并比较。动态规划方法本方法是从过程的最后一段开始，用逆序递推方法求解，逐步求出各段各点到终点的最短路线，最后求得起始点到终点的最短路线。,动态规划的基本思想

11、,第一步：k=5状态s5：E1，E2,(4),(3),f5(E1)4,f5(E2)3,第二步：k=4 状态：D1 D2 D3,u4*(D1)=E1,u4*(D2)=E2,u4*(D3)=E1,(7),(5),(5),第三步：k=3 状态：C1 C2 C3 C4,u3*(C1)=D1,u3*(C2)=D2,u3*(C3)=D2,f3(C1)12,f3(C2)10,f3(C3)8,u3*(C4)=D3,f3(C4)9,(12),(10),(8),(9),第四步：k=2状态：B1 B2,u2*(B1)=C2,u2*(B2)=C3,f2(B1)13,f2(B2)15,(13),(15),第五步：k=1

12、状态：A,u1*(A)=B1,f1(A)17,(17),即从A到F的最短距离为17。最优路线为：AB1C2D2E2F,练习：,求从A到E的最短路径,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f5(E)=0,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D1)=5,f5(E)=0,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C

13、1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f4(D1)=5,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C1)=8,f4(D1)=5,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C2)=7,f4(D1)=5,f3(C1)=8,2,5,1,12,14,10,6

14、,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f3(C1)=8,f3(C2)=7,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B1)=20,f3(C2)=7,f3(C1)=8,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,

15、2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B2)=14,f3(C2)=7,f3(C1)=8,f2(B1)=21,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f2(B1)=21,f2(B2)=14,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6

16、,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=2

17、1,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A（A，B2）B2,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A（A，B2）B2（B2，C1）C1,2,5,1,12,14,10,6,10,4,13,11,12

18、,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A（A，B2）B2（B2，C1）C1（C1，D1）D1,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3

19、)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A（A，B2）B2（B2，C1）C1（C1，D1）D1（D1，E）E从A到E的最短路径为19，路线为AB 2C1 D1 E,可以看出，在求解的各阶段，都利用了第k段和第k+1段的如下关系:,这种递推关系称为动态规划的基本方程，第二个式子称为边界条件。这种在图上直接计算的方法称为标号法。,动态规划标号法较之穷举法的优点:第一，容易算出;其次，动态规划的计算结果不仅得到了从起始点到最终点的

20、最短路线，而且得到了中间段任一点到最终点的最短路线。,动态规划方法的基本思想：(1)将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数从而把问题化成一族同类型的子问题，然后逐个求解。(2)求解时从边界条件开始，逆(或顺)过程行进方向，逐段递推寻优。在每一个子问题求解时，都要使用它前面已求出的子问题的最优结果，最后一个子问题的最优解，就是整个问题的最优解。(3)动态规划方法是既把当前一段与未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法，因此每段的最优决策选取是从全局考虑的，与该段的最优选择一般是不同的。,动态规划的基本方程：,依据原理：最优化原理 一个过程

21、的最优策略具有这样的性质：即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略。,三、动态规划模型的建立与求解,（一）动态规划模型的建立（二）逆序解法与顺序解法（三）基本方程分段求解时的几种常用算法,（一）动态规划模型的建立,建立动态规划的模型关键，在于识别问题的多阶段持征，将问题分解成为可用递推关系式联系起来的若干子问题，或者说正确地建立具体问题的基本方程。而正确建立基本递推关系方程的关键又在于正确选择状态变量，保证各阶段的状您变量具有递推的状态转移关系 sk+1=Tk(sk,uk)下面以资源分配问题为例介绍动态规划的建模条件及解法。资源分配问题是动态规

22、划的典型应用之一，资源可以是资金、原材料、设备、劳力等，资源分配就是将一定数量的一种或几种资源恰当地分配给若干使用者，以获取最大效益。,（一）动态规划模型的建立,例5 某公司有资金10万元若投资于项目i(i1，2，3）的投资额为xi时，其收益分别为g1(x1)4x1，g2(x2)9x2，g3(x3)2x32，问应如何分配投资数额才能使总收益最大?这是一个与时间无明显关系的静态最优化问题，可列出其静态模型。,也可以人为地赋予时段概念，把问题转化为一个3段决策过程。关键问题是如何正确选择状态变量，使各后部子过程之间具有递进关系。,（一）动态规划模型的建立,例5 某公司有资金10万元若投资于项目i(

23、i1，2，3的投资额为xi时，其收益分别为g1(x1)4x1，g2(x2)9x2，g3(x3)2x32，问应如何分配投资数额才能使总收益最大?,K=1,K=2,第k段时,所以，建立动态规划模型：阶段k：本例中取1，2，3状态变量sk：第k段可以投资于第k项到第3个项目的资金数决策变量xk：决定给第k个项目投资的资金数。状态转移方程：sk+1sk-xk,最优指标函数fk(sk)：当可投资金数为sk时，投资第k-3项所得的最大收益数。基本方程为：,模型,建立动态规划模型的要点 1、分析题意，识别问题的多阶段特性，按时间或空间的先后顺序适当地划分为满足递推关系的若干阶段，对非时序的静态问题要人为地赋

24、予“时段”概念。2、正确地选择状态变量，使其具备两个必要待征：(1)可知性：即过程演变的各阶段状态变量的取值，能直接或间接地确定；(2)能够确切地描述过程的演变且满足无后效性。即由第k阶段的状态sk出发的后部子过程，可以看作是一个以sk为初始状态的独立过程。3、根据状态变量与决策变量的含义，正确写出状态转移方程sk+1=Tk(sk,uk)或转移规则。4、根据题意明确指标函数vk,n最优指标函数fk(sk)以及k阶段指标vk(sk,uk)的含义，并正确列出最优指标函数的递推关系及边界条件(即基本方程)。,（二）逆序解法与顺序解法,如果寻优的方向与多阶段决策过程的实际行进方向相反，从最后一段开始计

25、算逐段前推，求得全过程的最优策略，称为逆序解法。顺序解法的寻优方向同于过程的行进方向，计算时从第一段开始逐段向后递推，计算后一阶段要用到前一阶段的求优结果，最后一段计算的结果就是全过程的最优结果。,求解步骤,第一步：k=0状态：s1A,f0(A)0,第二步：k=1 状态：B1 B2,u1*(B1)=A,u1*(B2)=A,f1(B1)4,f2(B2)5,(4),(5),第三步：k=2 状态：C1 C2 C3,u2*(C1)=B1,u2*(C2)=B1,u2*(C3)=B1,f2(C1)6,f2(C2)7,f2(C3)10,u2*(C4)=B2,f2(C4)12,(6),(7),(10),(12

26、),第四步：k=3 状态：D1 D2 D3,u3*(D1)=C1或C2,u3*(D2)=C2,u3*(D3)=C3,f3(D1)11,f3(D2)12,f3(D3)14,(11),(12),(14),第五步：k=4 状态：E1 E2,u4*(E1)=D1,u4*(E2)=D2,f4(E1)14,f4(E2)14,(14),(14),第六步：k=5 状态：F,u5*(F)=E2,f5(F)17,(17),即从A到F的最短距离为17。最优路线为：AB1C2D2E2F,顺序解法的基本方程：,逆序解法与顺序解法建模的不同点,1状态转移方式不同sk+1=Tk(sk,uk)sk=Tk(sk+1,uk),2

27、指标函数的定义不同 逆序解法中，我们定义最优指标函数fk(sk)表示第k段从状态sk出发，到终点后部子过程最优效益值，f1(s1)是整体最优函数值。顺序解法中，定义最优指标函数fk(sk+1)表示第k段时从起点到状态sk+1的前部子过程最优效益值。fn(sn+1)是整体最优函数值。,3，基本方程形式不同(1)当指标函数为阶段指标和形式逆序解法,则基本方程为：,则基本方程为：,顺序解法,(2)当指标函数为阶段指标积形式逆序解法,则基本方程为：,则基本方程为：,顺序解法,(最短路程问题)假定从A地到E地要铺设一条管道，其中要经过若干个中间点(如图)。,图中两点之间连线上的数字表示两地间的距离，现在

28、要选择一条铺设管道的路线使总长度最短。,练 习,AB1C2D2E,（三）基本方程分段求解时的几种常用算法,1离散变量的分段穷举算法 动态规划模型中的状态变量与决策变量若被限定只能取离散值，则可采用分段穷举法。如例4的求解方法就是分段穷举算法，由于每段的状态变量和决策变量离散取值个数较少，所以动态规划的穷举法要比一般的穷举法有效。用分段穷举法求最优指标函数值时，最重要的是正确确定每段状态变量取值范围和允许决策集合的范围。,例5：某公司有资金10万元若投资于项目i(i1，2，3）的投资额为xi时，其收益分别为g1(x1)4x1,g2(x2)9x2,g3(x3)2x32，问应如何分配投资数额才能使总

29、收益最大?,2连续变量的解法 当动态规划模型中状态变量与决策变量为连续变量，就要根据方程的具体情况灵活选取求解方法，如经典解析方法、线性规划方法、非线性规划法或其它数值计算方法等。如在例5中，状态变量与决策变量均可取连续值而不是离散值，所以每阶段求优时不能用穷举方法处理。下面分别用逆序解法求解。,其动态规划模型已建立如下：阶段k：本例中取1，2，3状态变量sk：第k段可以投资于第k项到第3个项目的资金数决策变量xk：决定给第k个项目投资的资金数。状态转移方程：sk+1sk-xk,最优指标函数fk(sk)：当可投资金数为sk时，投资第k-3项所得的最大收益数。基本方程为：,状态转移方程：sk+1

30、sk-xk,k3时,k2时,状态转移方程：sk+1sk-xk,k1时,状态转移方程：sk+1sk-xk,状态转移方程：sk+1sk-xk,k1时,最优投资方案为全部资金投于第3个项目，可得最大收益200万元。,连续变量的解法-顺序解法,建立动态规划模型：阶段k：本例中取1，2，3决策变量xk：决定给第k个项目投资的资金数状态变量sk+1：表示可用于第1到第k个项目投资的金额，则有：s4=10 s3=s4-x3 s2=s3-x2 s1=s2-x1状态转移方程：sksk+1-xk最优指标函数fk(sk+1)：表示第k段投资额为sk+1时第1到第k项目所获的最大收益。基本方程为：,动态规划在经济管理

31、中应用,一、背包问题,背包问题的一般提法是：一位旅行者携带背包去登山、已知他所能承受的背包重量限度为a千克，现有n种物品可供他选择装入背包。第i种物品的单件重量为ai干克、其价值(可以是表明本物品对登山的重要性的数量指标)是携带数量xi的函数ci(xi)(i1，2，n)，问旅行者应如何选择携带各种物品的件数，以使总价值最大？其他如车、胎、飞机、潜艇、人造卫星等工具的最优装载问题，机床加工中零件最优加工、下料问题、投资决策问题，均等同于背包问题。,背包问题的整数规划模型,背包问题的动态规划模型,1阶段k：将可装入物品按1，2，.，n排序，每段装 一种物品、共划分为n个阶段，即k1，2，.，n。2

32、状态变量sk+1：在第k段开始时，背包中允许装入前k种物品的总重量。3决策变量xk：装入第k种物品的件数。4状态转移方程：sk=sk+1-akxk5允许决策集合为：Dk(sk+1)xk|oxk sk+1/ak，xk为整数 其中sk+1/ak表示不超过sk+1/ak的最大整数。6最优指标函数 fk(sk+1)表示在背包中允许装入物品的总重量不超过sk+1千克，采用最优策略只装前k种物品时的最大使用价值。7则可得到动态规划的顺序递推方程为：,注：当xi仅表示装入(取1)和不装(取0)第i种物品，则本模型就是0-1背包问题。,例:有一辆最大货运量为10吨的卡车，用以装载3种货物每种货物的单位重量及相

33、应单位价值如表所示。应如何装载可使总价值最大?,设第i种货物装载的件数为xi(i1，2，3)，则问题可表为,建立动态规划模型，用列表法求解,K=1,K=2,K=3,所以x3*=0,s3=s4-5x3=10-5*0=10,所以x2*=1,s2=s3-4x2=10-4*1=6,所以x1*=2,全部策略为：x1*=2 x2*=1 x3*=0，最大价值为13。,练 习 题,某公司打算在三个不同的地区设置4个销售点，根据市场预测部门估计，在不同的地区设置不同数星的销售店，每月可得到的利润如表所示。试问在各个地区应如何设置销售点，才能使每月获得的总利润最大?其值是多少？,1阶段k：将设点地区划分为3个阶段

34、，即k1，2，3。2状态变量sk+1：在第k段开始时，允许设点个数。3决策变量xk：K段设点个数。4状态转移方程：sk=sk+1-xk5允许决策集合为：Dk(sk+1)xk|oxk sk+1，xk为整数6最优指标函数 fk(sk+1)表示在前k段时销售点的总收效益。7动态规划的顺序递推方程为：,解：建立动态规划模型,K=1,K=2,K=2,K=3,全部策略为：x1*=2 x2*=1 x3*=1，最大价值为47。,动态规划在经济管理中应用,二、生产经营问题生产与存贮问题,在生产和经营管理中经常遇到如何合理地安排生产计划、采购计划以及仓库的存货计划和销售计划，使总效益最高的问题。,例：某工厂生产并

35、销售某种产品，已知今后四个月市场需求预测如表，又每月生产单位产品费用为：,每月库存j单位产品的费用为E(j)0.5j(干元)，该厂最大库存容量为3单位，每月最大生产能力为6单位，计划开始和计划期末库存量都是零。试制定四个月的生产计划，在满足用户需求条件下总费用最小。假设第j+1个月的库存量是第j个月可销售量与该月用户需求量之差；而第i个月的可销售量是本月初库存量与产量之和。,(1)阶段：每个月为一个阶段，k1，2，3，4。(2)状态变量:sk为第k个月初的库存量。(3)决策变量:uk为第k个月的生产量。(4)状态转移方程：sk+1=sk+uk-gk(5)最优指标函数：fk(sk)表示第k月状态为sk时，采用最佳策略生产，从本月到计划结束（第4个月末）的生产与存贮最低费用。(6)基本方程：,解：建立动态规划模型,K=4 u4=4-s4,K=3 s3=0,1,2,3,K=3 s3=0,1,2,3,K=2 s2=0,1,2,3,K=2 s2=0,1,2,3,K=1 s1=0,可得最佳生产计划为：第一个月生产2单位，第二个月生产5单位，第三个月不生产，第四个月生产4单位。,练习题：,用动态规划方法求解下列问题,