第七章动态规划学习教案

1、会计学1第七章动态第七章动态(dngti)规划规划第一页，共76页。动态规划的起源： 1951年,(美)数学家R.Bellman等人，根据多阶段序贯决策问题的特点，提出了著名的“最优性原理”。将多阶段决策问题转变为一系列的互相联系的单阶段决策问题，然后，逐个阶段予以解决，最后再形成总体解决。从而创建了求解优化问题的新方法动态规划。1957年，他的名著动态规划出版。最优性原理: 作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成(guchng)最优子策略。简言之，最优策略的子策略总是最优的。2第1页/共75页第二页，共76页。动态

2、决策(juc)问题： 决策(juc)过程具有阶段性和时序性(与时间有关)的决策(juc)问题。即决策(juc)过程可划分为明显的阶段。动态决策(juc)问题分类： 1、按数据给出的形式分为： 离散型动态决策(juc)问题。 连续型动态决策(juc)问题。 2、按决策(juc)过程演变的性质分为： 确定型动态决策(juc)问题。 随机型动态决策(juc)问题。 3第2页/共75页第三页，共76页。例1 生产与存贮问题要求确定一个逐月的生产计划，在满足需求条件下，使一年的生产与存贮费用之和最小？ 例2 投资决策问题某公司现有资金Q万元，在今后(jnhu)5年内考虑给A，B，C，D 4个项目投资？例

3、3 设备更新问题现企业要决定一台设备未来8年的更新计划，问应在哪些年更新设备可使总费用最小？ 4第3页/共75页第四页，共76页。例例4 基建投资基建投资(tu z)问题问题 一家公司有三个工厂，每个厂都需要进行扩建。公司用于扩一家公司有三个工厂，每个厂都需要进行扩建。公司用于扩建的资金总共为建的资金总共为7万元。各个厂的投资万元。各个厂的投资(tu z)方案及扩建后预期方案及扩建后预期可获得的利润如表所示可获得的利润如表所示(单位：万元单位：万元)。 现在公司(n s)要确定时各厂投资多少才能使公司(n s)的总利润达到最大？ 厂名厂名方案方案1方案方案2方案方案3方案方案4投资数投资数利润

4、利润投资数投资数利润利润投资数投资数利润利润投资数投资数利润利润一厂一厂001528510二厂二厂001339411三厂三厂00273114135第4页/共75页第五页，共76页。例例5 货船装运问题货船装运问题 有四种货物准备装到一艘货船上。第有四种货物准备装到一艘货船上。第i(i12，3，4)种种货物的每一箱重量是货物的每一箱重量是wi(单位：吨单位：吨)，其价值，其价值(jizh)是是vi(单位：单位：干元干元)，如表所示。，如表所示。 假定这艘货船(hu chun)的总载重量是10吨，现在要确定这四种货物应各装几箱才能使装载货物的总价值达到最大？ 货物i单位重量wi单位价值vi1242

5、123474356第5页/共75页第六页，共76页。例例6 最短路程问题最短路程问题(wnt) 假定从假定从A地到地到E地要铺设一条管道，其中要经过若干个中地要铺设一条管道，其中要经过若干个中间点间点(如图如图)。 图中两点之间连线上的数字(shz)表示两地间的距离，现在要选择一条铺设管道的路线使总长度最短。 AB1B2B3C1C2C3D1D2 E3677695238354369437第6页/共75页第七页，共76页。1、阶段：将所给问题(wnt)的过程，按时间或空间特征分解成若干互相联系的阶段，以便按次序去求每阶段的解，常用字母k表示阶段变量。动态(dngti)规划模型要用到的概念： (1)

6、阶段; (2)状态; (3)决策和策略; (4)状态转移; (5)指标函数。8第7页/共75页第八页，共76页。2、状态(zhungti)：各阶段开始时的客观条件叫做状态(zhungti)。状态(zhungti)变量：描述各阶段状态(zhungti)的变量，用sk表示第k阶段的状态(zhungti)变量。状态(zhungti)集合：状态(zhungti)变量的取值集合，用Sk表示。一阶段(jidun)：S1A二阶段(jidun)：S2B1,B2,B3三阶段(jidun)：S3C1,C2,C3四阶段(jidun)：S4D1,D2AB1B2B3C1C2C3D1D2 E367769523835436

7、9439第8页/共75页第九页，共76页。3、决策：当各段的状态取定以后，就可以作出不同的决定(judng)（或选择），从而确定下一阶段的状态，这种决定(judng)称为决策。决策变量：表示决策的变量，称为决策变量，常用uk(sk)表示第k阶段当状态为sk时的决策变量。允许决策集合：决策变量的取值往往限制在一定范围内，我们称此范围为允许决策集合，用Dk(sk)表示第k阶段从状态sk出发的允许决策集合。D2( B1)=C1,C2 D2( B2)=C1,C2,C3如状态为B1时选择(xunz)C2，可表示为：u2(B1)=C210第9页/共75页第十页，共76页。策略：各段决策确定后，整个问题的决

8、策序列就构成一个策略，用p1,nu1(s1),u2(s2),.un(sn)表示。允许(ynx)策略集合：对每个实际问题，可供选择的策略有一定范围，称为允许(ynx)策略集合，记作P1,n，使整个问题达到最优效果的策略就是最优策略。AB1B2B3C1C2C3D1D2 E367769523835436943p1,4B1,C1, D1,E二、基本概念和基本原理11第10页/共75页第十一页，共76页。 4、状态转移方程：动态规划(guhu)中本阶段的状态往往是上一阶段状态和上一阶段的决策结果。第k段的状态sk，本阶段决策为uk(sk)，则第k+1段的状态sk+1也就完全确定，它们的关系可用公式表示：

9、sk+1=Tk(sk,uk)sk+1= uk(sk)AB1B2B3C1C2C3D1D2 E367769523835436943二、基本概念和基本原理12第11页/共75页第十二页，共76页。 5、指标函数：用于衡量所选定策略优劣的数量指标。 它分为阶段指标函数和过程指标函数。 阶段指标函数是指第k段，从状态sk出发，采取决策uk时的效益，用d(sk,uk)表示(biosh)。d(B1,C2) 一个n段决策过程，从1到n叫作问题的原过程，对于任意一个给定的k(1k n)，从第k段到第n段的过程称为原过程的一个后部子过程。 V1,n(s1,p1,n) 表示(biosh)初始状态为s1采用策略p1,

10、n时原过程的指标函数值;Vk,n(sk,pk,n)表示(biosh)在第k段，状态为sk采用策略pk,n时,后部子过程的指标函数值。 最优指标函数记为fk(sk)：表示(biosh)从第k段状态sk采用最优策略到过程终止时的最佳效益值。二、基本概念和基本原理13第12页/共75页第十三页，共76页。最简单的方法穷举法。共有多少条路径，依次计算并比较。动态(dngti)规划方法本方法是从过程的最后一段开始，用逆序递推方法求解，逐步求出各段各点到终点的最短路线，最后求得起始点到终点的最短路线。二、基本概念和基本原理14第13页/共75页第十四页，共76页。251121410610413111239

11、6581052C1C3D1AB1B3B2D2EC2练习(linx)：求从A到E的最短路径(ljng)。二、基本概念和基本原理15第14页/共75页第十五页，共76页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0二、基本概念和基本原理16第15页/共75页第十六页，共76页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0505)E(f)ED(d)D(f5114二、基本概念和基本原理17第16页/共75页第十七页，共76页。2511214106104131112

12、396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5202)E(f)ED(d)D(f5224二、基本概念和基本原理18第17页/共75页第十八页，共76页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=51124211411138118min2953min)(),()(),(min)(DCDfDCdDfDCdCf最优决策二、基本概念和基本原理19第18页/共75页第十九页，共76页。2511214106104131112396581052C1

13、C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=82224221412237711min2556min)(),()(),(min)(DCDfDCdDfDCdCf最优决策二、基本概念和基本原理20第19页/共75页第二十页，共76页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7232423141333121213min21058min)(),()(),(min)(DCDfDCdDfDCdCf最优

14、决策二、基本概念和基本原理21第20页/共75页第二十一页，共76页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=8113331232113111220222120min1210714812min)(),()(),()(),(min)(CBCfCBdCfCBdCfCBdBf最优决策二、基本概念和基本原理22第21页/共75页第二十二页，共76页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2

15、f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=21123332232213122214161714min12471086min)(),()(),()(),(min)(CBCfCBdCfCBdCfCBdBf最优决策二、基本概念和基本原理23第22页/共75页第二十三页，共76页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=1

16、4233333232313133219231921min1211712813min)(),()(),()(),(min)(CBCfCBdCfCBdCfCBdBf最优决策二、基本概念和基本原理24第23页/共75页第二十四页，共76页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=212323222121119201923min191145212min)(),()(),()(),(min)(

17、BABfBAdBfBAdBfBAdAf最优决策二、基本概念和基本原理25第24页/共75页第二十五页，共76页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态(zhungti) 最优决策 状态(zhungti) 最优决策 状态(zhungti) 最优决策 状态(zhungti) 最优决策 状态(zhungti)A （ A，B2） B2二、基本概念和基本原理26第25页/共75页第二

18、十六页，共76页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态(zhungti) 最优决策 状态(zhungti) 最优决策 状态(zhungti) 最优决策 状态(zhungti) 最优决策 状态(zhungti)A （ A，B2） B2 （B2，C1） C1二、基本概念和基本原理27第26页/共75页第二十七页，共76页。251121410610413111239658105

19、2C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态(zhungti) 最优决策 状态(zhungti) 最优决策 状态(zhungti) 最优决策 状态(zhungti) 最优决策 状态(zhungti)A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1二、基本概念和基本原理28第27页/共75页第二十八页，共76页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)

20、=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态(zhungti) 最优决策 状态(zhungti) 最优决策 状态(zhungti) 最优决策 状态(zhungti) 最优决策 状态(zhungti)A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1 （D1，E） E从A到E的最短路径(ljng)为19，路线为AB 2C1 D1 E 二、基本概念和基本原理29第28页/共75页第二十九页，共76页。可以看出(kn ch)，在求解的各阶段，都利用了第k段和第k+1段的

21、如下关系:0)(1 , 2 , 3 , 4 , 5)(),(min)(6611sfksfusdsfkkkkkkk这种递推关系称为动态规划的基本方程(fngchng)，第二个式子称为边界条件。这种在图上直接计算的方法称为标号法。二、基本概念和基本原理30第29页/共75页第三十页，共76页。动态规划标号法较之穷举法的优点: 第一，容易算出; 其次，动态规划的计算结果不仅得到了从起始点到最终点的最短路线，而且得到了中间(zhngjin)段任一点到最终点的最短路线 。二、基本概念和基本原理31第30页/共75页第三十一页，共76页。动态规划(guhu)方法的基本思想： (1)将多阶段决策过程划分阶段

22、，恰当地选取状态变量、决策变量及定义最优指标函数从而把问题化成一族同类型的子问题，然后逐个求解。 (2)求解时从边界条件开始，逆(或顺)过程行进方向，逐段递推寻优。在每一个子问题求解时，都要使用它前面已求出的子问题的最优结果，最后一个子问题的最优解，就是整个问题的最优解。 (3)动态规划(guhu)方法是既把当前一段与未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法，因此每段的最优决策选取是从全局考虑的，与该段的最优选择一般是不同的。二、基本概念和基本原理32第31页/共75页第三十二页，共76页。（一）动态规划模型的建立（一）动态规划模型的建立（二）逆序解法与顺序解法（二）逆

23、序解法与顺序解法（三）基本方程（三）基本方程(fngchng)分段求解时的几种常用算法分段求解时的几种常用算法33第32页/共75页第三十三页，共76页。 （一）动态规划模型的建立建立动态规划的模型关键，在于识别问题的多阶段持征，将问题分解成为可用递推关系式联系起来的若干子问题，或者说正确地建立具体问题的基本方程。而正确建立基本递推关系方程的关键又在于正确选择状态变量，保证各阶段的状您变量具有递推的状态转移(zhuny)关系 sk+1=Tk(sk,uk)下面以资源分配问题为例介绍动态规划的建模条件及解法。34第33页/共75页第三十四页，共76页。 例5 某公司有资金10万元若投资于项目i(i

24、1，2，3）的投资额为xi时，其收益分别为g1(x1)4x1，g2(x2)9x2，g3(x3)2x32，问应如何(rh)分配投资数额才能使总收益最大?可以人为地赋予时段，把问题转化为一个3段决策过程。关键问题是如何正确选择(xunz)状态变量，使各后部子过程之间具有递进关系。)3 , 2 , 1(010. .294max3212321ixxxxtsxxxzi35第34页/共75页第三十五页，共76页。22112xuussK=1K=2第k段时所以，建立动态规划模型(mxng)：阶段k：本例中取1，2，3状态变量sk：第k段可以投资于第k项到第3个项目的资金数决策变量xk：决定给第k个项目投资的资

25、金数。状态转移方程：sk+1sk-xk最优指标函数fk(sk)：当可投资金数为sk时，投资第k-3项所得的最大收益(shuy)数。基本方程为：11110 xuskkkkkxuuss1133 ,)( 函数 指标kiiikxgV0)(1 , 2, 3)()(max)(44110sfksfxgsfkkkksxkkk36第35页/共75页第三十六页，共76页。 建立(jinl)动态规划模型的要点1、分析题意，识别问题的多阶段特性，按时间或空间的先后顺序适当地划分为满足递推关系的若干阶段。2、正确地选择状态变量，使其具备两个必要待征： (1)可知性； (2)能够确切地描述过程的演变且满足无后效性。3、根

26、据状态变量与决策变量的含义，正确写出状态转移方程sk+1=Tk(sk,uk)或转移规则。4、根据题意明确指标函数vk,n最优指标函数fk(sk)以及k阶段指标vk(sk,uk)的含义，并正确列出最优指标函数的递推关系及边界条件(即基本方程)。37第36页/共75页第三十七页，共76页。（二）逆序解法与顺序解法如果寻优的方向与多阶段决策过程的实际行进(xngjn)方向相反，从最后一段开始计算逐段前推，求得全过程的最优策略，称为逆序解法。顺序解法的寻优方向同于过程的行进(xngjn)方向，计算时从第一段开始逐段向后递推，计算后一阶段要用到前一阶段的求优结果，最后一段计算的结果就是全过程的最优结果。

27、38第37页/共75页第三十八页，共76页。第一步：k=0状态(zhungti)：s1Af0(A)0求解(qi ji)步骤39第38页/共75页第三十九页，共76页。第二步：k=1 状态(zhungti)：B1 B2 u1*(B1)=Au1*(B2)=Af1(B1)4f2(B2)5(4)(5)40第39页/共75页第四十页，共76页。第三步：k=2 状态(zhungti)：C1 C2 C3 C4u2*(C1)=B1u2*(C2)=B1u2*(C3)=B1f2(C1)6f2(C2)7f2(C3)10u2*(C4)=B2f2(C4)12(4)(5)(6)(7)(10)(12)41第40页/共75页

28、第四十一页，共76页。(4)(5)(6)(7)(10)(12)第四步：k=3 状态(zhungti)：D1 D2 D3u3*(D1)=C1或C2u3*(D2)=C2u3*(D3)=C3f3(D1)11f3(D2)12f3(D3)14(11)(12)(14)42第41页/共75页第四十二页，共76页。第五步：k=4 状态(zhungti)：E1 E2 u4*(E1)=D1u4*(E2)=D2f4(E1)14f4(E2)14(4)(5)(6)(7)(10)(12)(11)(12)(14)(14)(14)43第42页/共75页第四十三页，共76页。第六步：k=5 状态(zhungti)：F u5*(

29、F)=E2f5(F)17(6)(4)(5)(7)(10)(12)(11)(12)(14)(14)(14)(17)即从A到F的最短距离为17。最优路线(lxin)为：AB1C2D2E2F44第43页/共75页第四十四页，共76页。逆序解法逆序解法(ji f)与顺序解法与顺序解法(ji f)建模的不同点建模的不同点1状态转移(zhuny)方式不同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

30、+1nsnunvn(sn+1,un)Sn+145第44页/共75页第四十五页，共76页。2指标函数的定义不同 逆序解法中，我们定义最优指标函数fk(sk)表示第k段从状态sk出发，到终点后部子过程(guchng)最优效益值，f1(s1)是整体最优函数值。 顺序解法中，定义最优指标函数fk(sk+1)表示第k段时从起点到状态sk+1的前部子过程(guchng)最优效益值。fn(sn+1)是整体最优函数值。46第45页/共75页第四十六页，共76页。3，基本(jbn)方程形式不同(1)当指标函数为阶段指标和形式逆序解法则基本(jbn)方程为：则基本(jbn)方程为：顺序解法nkjjjjnkusvV

31、),( ,kjjjjkusvV11, 1),( 0)(1 , 2,.,1,)(),()(1111nnkkkkkDukksfnnksfusvoptsfkk0)(,.,2 , 1)(),()(10111sfnksfusvoptsfkkkkkDukkkk47第46页/共75页第四十七页，共76页。(2)当指标(zhbio)函数为阶段指标(zhbio)积形式逆序解法基本(jbn)方程为：基本(jbn)方程为：顺序解法nkjjjjnkusvV),( ,kjjjjkusvV11, 1),( 1)(1 , 2,.,1,)(),()(1111nnkkkkkDukksfnnksfusvoptsfkk1)(,.,

32、2 , 1)(),()(10111sfnksfusvoptsfkkkkkDukkkk48第47页/共75页第四十八页，共76页。1离散变量(binling)的分段穷举算法 动态规划模型中的状态变量(binling)与决策变量(binling)若被限定只能取离散值，则可采用分段穷举法。如前面例4的求解方法就是分段穷举算法，由于每段的状态变量(binling)和决策变量(binling)离散取值个数较少，所以动态规划的穷举法要比一般的穷举法有效。用分段穷举法求最优指标函数值时，最重要的是正确确定每段状态变量(binling)取值范围和允许决策集合的范围。（三）基本方程(fngchng)分段求解时的

33、几种常用算法49第48页/共75页第四十九页，共76页。2连续变量的解法 当动态规划模型中状态变量与决策变量为连续变量，就要根据方程的具体情况灵活选取求解方法，如经典解析方法、线性规划方法、非线性规划法或其它数值计算方法等。如在例5中，状态变量与决策变量均可取连续值而不是(b shi)离散值，所以每阶段求优时不能用穷举方法处理。下面分别用逆序解法求解。三、动态(dngti)规划模型的建立与求解50第49页/共75页第五十页，共76页。 例5： 某公司有资金10万元若投资(tu z)于项目i(i1，2，3）的投资(tu z)额为xi时，其收益分别为g1(x1)4x1,g2(x2)9x2,g3(x

34、3)2x32，问应如何分配投资(tu z)数额才能使总收益最大?)3 , 2 , 1(010. .294max3212321ixxxxtsxxxzi三、动态规划(guhu)模型的建立与求解51第50页/共75页第五十一页，共76页。其动态规划模型已建立如下：阶段(jidun)k：本例中取1，2，3状态变量sk：第k段可以投资于第k项到第3个项目的资金数决策变量xk：决定给第k个项目投资的资金数。状态转移方程：sk+1sk-xk最优指标函数fk(sk)：当可投资金数为sk时，投资第k-3项所得(su d)的最大收益数。基本方程为：33 ,)( 函数 指标kiiikxgV0)(1 , 2, 3)(

35、)(max)(44110sfksfxgsfkkkksxkkk52第51页/共75页第五十二页，共76页。k3时2max)(2303333xsfsx 233*32s，sx取得极大值时当232303322max)(33sxsfsx233*32s，sx取得极大值时当53第52页/共75页第五十三页，共76页。k2时)(29max29max )(9max)(222202320332022222222xsxsxsfxsfsxsxsx2222222)(29),(xsxxsh令是极小值点9422 sx22222229)(2)0(0ssfsf。，s端点取得极大值只可能在2/9)()0(2222ssff得当2*

36、22222*22222),()0(2/90),()0(2/9sxsf，fsxsf，fs时当时当54第53页/共75页第五十四页，共76页。k1时 )(4max)(22101111sfxsfsx2222*29)(ss，fsx时当111100111100195-9max9-94max)10(11sxsxsxfxx2*22222*22222),()0(2/90),()0(2/9sxsf，fsxsf，fs时当时当10010112xss。，s舍去矛盾与2/9255第54页/共75页第五十五页，共76页。k1时 )(4max)(22101111sfxsfsx2222*22)(0ss，fx 时当)-(24m

37、ax)10(211110011xsxfx)-(24),(2111111xsxxsh令是极小点111 sx40)10(200)0(10011ff。，端点取得极大值只可能在10010*112xss0*1x所以2/92s满足条件1010010, 03*3*223*2s；xxssx所以最优投资方案为全部资金投于第3个项目(xingm)，可得最大收益200万元。56第55页/共75页第五十六页，共76页。四、在经济四、在经济(jngj)管理中的应用管理中的应用（一）背包(bibo)问题 背包问题的一般提法是：一位旅行者携带背包去登山、已知他所能承受的背包重量限度为a千克，现有(xin yu)n种物品可供

38、他选择装入背包。第i种物品的单件重量为ai干克、其价值(可以是表明本物品对登山的重要性的数量指标)是携带数量xi的函数ci(xi) (i1，2，n)，问旅行者应如何选择携带各种物品的件数，以使总价值最大？ 其他如车、船、飞机、潜艇、人造卫星等工具的最优装载问题，机床加工中零件最优加工、下料问题、投资决策问题，均等同于背包问题。57第56页/共75页第五十七页，共76页。背包问题背包问题(wnt)的动态规划模的动态规划模型型1阶段k：将可装入物品按1，2，.，n排序，共划分为n个阶段，即k1，2，.，n。2状态变量sk+1：在第k段开始时，背包中允许装入前k种物品的总重量。3决策变量xk：装入第

39、k种物品的件数。4状态转移方程：sk=sk+1-akxk5允许决策集合为： Dk(sk+1)xk|oxk sk+1/ak，xk为整数6最优指标函数 fk(sk+1)表示在背包中允许装入物品的总重量不超过sk+1千克，采用最优策略只装前k种物品时的最大使用(shyng)价值。7顺序递推方程：0)(n1,2,.,k )()(max)(1011/,.,1 , 01sfxasfxcsfkkkkkkasrkkkkk四、在经济管理四、在经济管理(gunl)中的应用中的应用58第57页/共75页第五十八页，共76页。例: 有一辆最大货运量为10吨的卡车(kch)，用以装载3种货物每种货物的单位重量及相应单位

40、价值如表所示。应如何装载可使总价值最大?设第i种货物装载的件数(jin sh)为xi(i1，2，3)，则问题可表为货物编号I123单位重量（t）345单位价值ci456) 3 , 2 , 1(为整数010543. .654max321321ixxxxtsxxxzi四、在经济四、在经济(jngj)管理中的应用管理中的应用59第58页/共75页第五十九页，共76页。K=1 3/ 44max)(213/021121sxsfxsx为整数s2012345678910f1(s2)0004448881212x1*00011122233s2f1(s2)x1*0)(n1,2,.,k )()(max)(1011/

41、,.,1 , 01sfxasfxcsfkkkkkkasxkkkkk建立动态(dngti)规划模型，用列表法求解四、在经济管理四、在经济管理(gunl)中的应中的应用用60第59页/共75页第六十页，共76页。K=2)4(5max)(23124/032232xsfxsfxsx为整数s30123 45678910 x200000 10 10 10 10 1 20 1 20 1 2c2+f200044 54 58 58 98 9 1012 9 1012 13 10f2(s3)0004 5 58 9 1012 13x2*0000 1 10 1 20 1s3x2c2+f2f2(s3)x2*四、在经济四、

42、在经济(jngj)管理中的应管理中的应用用61第60页/共75页第六十一页，共76页。K=3)510(6max)10(3232, 1 , 033xfxfx)0(12),5(6),10(max222fff012, 56 ,13max13所以(suy)x3*=0s3=s4-5x3=10-5*0=10所以(suy)x2*=1s2=s3-4x2=10-4*1=6所以(suy)x1*=2全部策略为：x1*=2 x2*=1 x3*=0，最大价值为13。四、在经济管理中的应用四、在经济管理中的应用62第61页/共75页第六十二页，共76页。（二）生产经营(jngyng)问题生产与存贮问题 在生产和经营管理中

43、经常遇到如何合理地安排生产计划、采购计划以及仓库(cngk)的存货计划和销售计划，使总效益最高的问题。四、在经济管理四、在经济管理(gunl)中的应中的应用用63第62页/共75页第六十三页，共76页。 例：某工厂生产并销售某种产品，已知今后四个月市场需求预测如表，又每月生产单位(dnwi)产品费用为： 每月库存j单位产品的费用为E(j)0.5j(干元)，该厂最大库存容量为3单位，每月最大生产能力为6单位，计划开始和计划期末库存量都是零。试制定(zhdng)四个月的生产计划，在满足用户需求条件下总费用最小。假设第j+1个月的库存量是第j个月可销售量与该月用户需求量之差；而第i个月的可销售量是本

44、月初库存量与产量之和。 i（月）1234gi（需求）2324 )6,.,2 , 1(3)0(0 )(jjjjC四、在经济四、在经济(jngj)管理中的应用管理中的应用64第63页/共75页第六十四页，共76页。0)(1,2,3,4k )()()(min)(551sfgusfsEucsfkkkkkkkk(1)阶段：每个月为一个阶段，k1，2，3，4。(2)状态变量:sk为第k个月初的库存量。(3)决策变量:uk为第k个月的生产(shngchn)量。(4)状态转移方程：sk+1=sk+uk-gk(5)最优指标函数：fk(sk)表示第k月状态为sk时，采用最佳策略生产(shngchn)，从本月到计划

45、结束（第4个月末）的生产(shngchn)与存贮最低费用。(6)基本方程：解：建立动态规划(guhu)模型四、在经济四、在经济(jngj)管理中的应用管理中的应用65第64页/共75页第六十五页，共76页。K=4 u4=4-s4s40123f4(s4)76.565.5u4(s4)4321 )()(min)(4444sEucsfs4f4(s4)u4(s4)四、在经济四、在经济(jngj)管理中的应管理中的应用用66第65页/共75页第六十六页，共76页。s30123u3(s3)2 3 4 51 2 3 40 1 2 3 0 1 2C+E+f412 12.5 13 13.511.5 12 12.5

46、 138 11.5 12 12.58 11.5 12f3(s3)1211.588u3 *(s3)2100K=3 s3=0,1,2,3 )()()(min)(33343333gusfsEucsf且为整数)6 ,5 , 6min(2 , 0max3333ssuss3u3(s3)C+E+f4f3(s3)u3 *(s3)四、在经济四、在经济(jngj)管理中的应用管理中的应用67第66页/共75页第六十七页，共76页。s20123u2(s2)3 4 5 62 3 4 51 2 3 40 1 2 3C+E+f318 18.5 16 1717.5 18 15.5 16.517 17.5 15 1613.5

47、 17 14.5 15.5f2(s2)1615.51513.5u2 *(s2)5430K=2 s2=0,1,2,3 )()()(min)(22232222gusfsEucsf且为整数)9 ,6 , 6min(3 , 0max2233ssuss2u2(s2)C+E+f3f2(s2)u2 *(s2)四、在经济四、在经济(jngj)管理中的应用管理中的应用68第67页/共75页第六十八页，共76页。s10u1(s1)2345C+f22121.52221.5f1(s1)21u1 *(s1)2K=1 s1=0 )()()(min)(11121111gusfsEucsf且为整数521us1u1(s1)C+

48、f2f1(s1)u1 *(s1) 可得最佳(zu ji)生产计划为：第一个月生产2单位，第二个月生产5单位，第三个月不生产，第四个月生产4单位。四、在经济四、在经济(jngj)管理中的应用管理中的应用69第68页/共75页第六十九页，共76页。采购采购(cigu)与销售问题与销售问题 某商店在未来的某商店在未来的4个月里个月里,准备用它的一个仓库来专门经销某种商准备用它的一个仓库来专门经销某种商品品,仓库最大容量能贮存这种商品仓库最大容量能贮存这种商品1000单位单位.假定该商店每月只能出卖假定该商店每月只能出卖仓库现有的货仓库现有的货,当商店在某月购货时当商店在某月购货时,下月初才能到货下月初才能到货.预测该商品未来预测该商品未来四个月的买卖价格如表四个月的买卖价格如表7-12所示所示,假定商店在假定商店在1月开