运筹学第六章

1、第第6章章 动态规划动态规划第第1节节 多阶段决策过程及实例多阶段决策过程及实例第第2节节 动态规划的基本概念和方程动态规划的基本概念和方程第第3节节 动态规划的最优性原理和最优性定理动态规划的最优性原理和最优性定理第第4节节 动态规划和静态规划的关系动态规划和静态规划的关系第第5节节 动态规划应用举例动态规划应用举例 第第1节节 多阶段决策过程及实例多阶段决策过程及实例 动态规划研究的对象是多阶段决策问题。动态规划研究的对象是多阶段决策问题。 所谓多阶段决策问题是指一类活动过程，它所谓多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都可以分为若干个相互联系的阶段，在

2、每个阶段都需要作出决策。这个决策不仅决定这一阶段的效需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。益，而且决定下一阶段的初始状态。 每个阶段的决策确定以后，就得到一个决策每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。略，使各阶段的效益的总和达到最优。多阶段决策问题的典型例子：多阶段决策问题的典型例子： 1 . 生产决策问题：企业在生产过程中，由于需生产决策问题：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳求是随时间变化的，因此企业为了

3、获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地生产效益，就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。根据库存和需求决定生产计划。 2. 机器负荷分配问题：某种机器可以在高低机器负荷分配问题：某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量时，产品的年产量g和投入生产的机器数量和投入生产的机器数量u1的关的关系为系为g=g(u1)12n状态状态决策决策状态状态决策决策状态状态状态状态决策决策 这时，机器的年完好率为这时，机器的年完好率为a，即如果年初完好机，即如果年初完好机器的数量为器的数量为

4、u，到年终完好的机器就为，到年终完好的机器就为au, 0a1。 在低负荷下生产时，产品的年产量在低负荷下生产时，产品的年产量h和投入生和投入生产的机器数量产的机器数量u2的关系为的关系为 h=h(u2) 假定开始生产时完好的机器数量为假定开始生产时完好的机器数量为s1。要求制。要求制定一个五年计划，在每年开始时，决定如何重新定一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。使在五年内产品的总产量达到最高。 相应的机器年完好率相应的机器年完好率b, 0 b0，故比较，故比较0,10的端

5、点的端点101002910332232112 sxxss,xxss*因为因为 最优投资方案是全部资金投最优投资方案是全部资金投于第于第3个项目，可得最大收益个项目，可得最大收益200万元。万元。S29/2)s(fxmax)s(fsx221011411 29100959994101121111100111100111 xss,xsxsmaxxsxmax)(f*xx0401010200100241011111211110011 *xx)(fx)(fx)xs(xmax)(f2229s)s(f 22222s)s(f 当当当当时时时时矛盾，舍去矛盾，舍去。（最优决策）（最优决策）S29/2 当阶段当阶段

6、k= =n时时逆推解法小结：逆推解法小结： 设已知初始状态设已知初始状态s s1 1，最优值函数，最优值函数fk k( (sk k) )表示从表示从k阶段到阶段到n阶段所得到的最大效益。以求最大化为例来阶段所得到的最大效益。以求最大化为例来说明。说明。nnnsDunnxsvsfnnn,max)(),(),(),(222111, 1nnnnxsvxsvxsvV即即其中其中s表示状态，表示状态，x表示决策（控制）。表示决策（控制）。可得最优决策可得最优决策xn n= =xn n( (sn n) )和最优值和最优值fn n( (sn n) )。若若D(D(s sn n) )只有一个决策只有一个决策,

7、 ,则可写成则可写成 xn n= =xn n( (sn n) )。具体方法如下：具体方法如下： 当阶段当阶段k=n-1时时 nnnnnsDunnsfxsvsfnnn111)(11,max111 111 nnnnx,sTs其中状态转移方程其中状态转移方程得到最优决策得到最优决策xn-1-1= = xn-1-1( (sn-1-1) )和最优值和最优值fn-1-1( (sn-1-1) )。 当阶段当阶段k=k时时 11)(,maxkkkkksDukksfxsvsfkkk kkkkx,sTs 1其中状态转移方程其中状态转移方程得最优决策得最优决策xk= = xk( (sk) )和最优值和最优值fk(

8、(sk) )。如此类推，直到第一阶段。如此类推，直到第一阶段。当阶段当阶段k=1时时 ,22111)(11max111sfxsvsfsDs其中状态转移方程其中状态转移方程.,1112xsTs 得得最优决策最优决策x1 1= = x1( (s1 1) )和最优值和最优值f1 1( (s1 1) )。 由于初始状态由于初始状态s s1 1已知已知, ,故故x1 1= =x1 1( (s1 1) )和和f1 1( (s1 1) )是确是确定的定的, ,根据状态转移方程按照上述递推过程相反顺根据状态转移方程按照上述递推过程相反顺序推算下去，就可逐步确定出每阶段的决策及效序推算下去，就可逐步确定出每阶段

9、的决策及效益。益。例例3 用顺推解法求解下面问题用顺推解法求解下面问题: 321003213212,i,x)c(cxxx. t . sxxxZmaxi设设s4=c, fk(sk+1)表示第表示第k阶段的结束状态为阶段的结束状态为 sk+1，从从1阶段到阶段到k阶阶 段的最大值。分三个阶段，即段的最大值。分三个阶段，即 k=1，2，3;解：解：设状态变量（因此可得状态转移方程）设状态变量（因此可得状态转移方程） ：csxsxsxcsxssxsxs433221433322120;0;确定决策变量：确定决策变量：x1, x2, x332213131xxx)x,s(vViiii, 指标函数指标函数 最

10、优指标函数：最优指标函数：fk(sk+1)1)(3 , 2 , 1)(),(max)(10101sfksfxsvsfkkkkksxkkkk 基本方程基本方程当阶段当阶段k=1时，有时，有2*12121)(max)(21sxsxsfsx当阶段当阶段k=2时，有时，有得最优决策得最优决策33323*232202122032274)(,32)(max)(max)(23232ssfsxxsxsfxsfsxsx最优目标函数最优目标函数当阶段当阶段k=3时，有时，有)(274max)(max)(334303230434343xsxsfxsfsxsx最优决策最优决策44434*3641)(,41ssfsx最

11、优目标函数最优目标函数因此最后可得：因此最后可得：443*33323*221*1641)(,41161)(,213241)(,41csfcxcsfcsxcsfcx例例4 用动态规划方法解下面问题用动态规划方法解下面问题解：设状态变量为解：设状态变量为s0、s1、 s2、s3)3,2, 1(,0923.1224max321232221ixxxxtsxxxFi 按问题中变量的个数分为三个阶段，即按问题中变量的个数分为三个阶段，即k=1，2，3 确定决策变量：确定决策变量：x1, x2, x3 fk(sk)表示第表示第k阶段的结束状态为阶段的结束状态为 sk，从，从1阶段到阶段到k阶阶 段的最大值。

12、段的最大值。 确定状态变量确定状态变量(因此可得状态转移方程因此可得状态转移方程)：332211332221110,20,39,2,3sxsxsxsxssxssx状态转移方程状态转移方程最优目标函数最优目标函数 f1(s1)=(4/9)s12 当阶段当阶段k=1时，有时，有 f1(s1)=max 4x12 X1s1/3最优决策为最优决策为x1*=s1/3当阶段当阶段k=2时，有时，有),(max294max)(max)(2222/0222222/011222/022222222xshxsxsfxsfsxsxsx因该点不在允许决策集合内，最大值点只能在因该点不在允许决策集合内，最大值点只能在0，

13、s2/2端点上取得，即端点上取得，即222222780916914sxsxdxdh解得由4)2(,94)0(2222222sshsh所以所以h2(s2,x2)的最大值点在的最大值点在x2=0处，故得到处，故得到f2(s2)=(4/9)s22及相应的最优解及相应的最优解x2*=0。当阶段当阶段k=3时，有时，有),(max94122max)(122max)(33302332302223033333333xshxsxsfxsfsxsxsx233333112098944sxsxdxdh解得由故该点为极小值点。又, 09442332dxhd122)(,1294)0(2333233sshsh而。及相应的

14、最优解处，所以的最大值点在故33233333322122)(),(sxsxfsxxsh由于由于s3不知道，故须再对不知道，故须再对s3求一次极值，即求一次极值，即122max)(max2390339033ssfxx为最大值。所以得才能达到最大值。时显然，当1741292)9()(921333fsfs174)9(max; 9, 0, 013*21fFxxx最大值为可求得最优解为再按计算的顺序反推算 当阶段当阶段k= =1时时顺推解法小结：顺推解法小结： 设已知初始状态设已知初始状态s sn+1n+1，最优值函数，最优值函数fk k( (s) )表示第表示第k阶段末的结束状态为阶段末的结束状态为s

15、 s，从，从1 1阶段到阶段到k阶段所得到的最阶段所得到的最大效益。以求最大化为例来说明。大效益。以求最大化为例来说明。),(,1211111)(21max111xsTsxsvsfsDs其中),(),(),(222111, 1nnnnxsvxsvxsvV即即其中其中s表示状态，表示状态，x表示决策（控制）。表示决策（控制）。可得最优决策可得最优决策x1 1= =x1 1( (s2 2) )和最优值和最优值f1 1( (s2 2) )。若若D D1 1( (s s1 1) )只有一个决策只有一个决策, ,则可写成则可写成 x1 1= =x1 1( (s2 2) )。具体方法如下：具体方法如下：

16、当阶段当阶段k=2时时21222)(32,max222sfxsvsfsDx2322, xsTs其中状态转移方程其中状态转移方程得到最优决策得到最优决策x2= = x2( (s3) )和最优值和最优值f2( (s3) )。 当阶段当阶段k=k时时 kkkkksDskksfxsvsfkkk1)(1,maxkkkkxsTs,1其中状态转移方程其中状态转移方程得最优决策得最优决策xk= = xk( (sk+1) )和最优值和最优值fk( (sk+1) )。如此类推，直到第如此类推，直到第n n阶段。阶段。 当阶段当阶段k=n时时,1)(1maxnnnnnsDxnnsfxsvsfnnn其中状态转移方程其

17、中状态转移方程.,1nnnnxsTs得得最优决策最优决策xn n= = xn( (sn+1n+1) )和最优值和最优值fn n( (sn+1n+1) )。 由于终止状态由于终止状态s sn+1n+1已知已知, ,故故xn n= =xn n( (sn+1n+1) )和和fn n( (sn+1n+1) )是确定的是确定的, ,根据状态转移方程按照上述递推过程相根据状态转移方程按照上述递推过程相反顺序推算下去，就可逐步确定出每阶段的决策反顺序推算下去，就可逐步确定出每阶段的决策及效益。及效益。动态规划的优缺点：动态规划的优缺点：优点优点: . 最优解是全局最优解。最优解是全局最优解。 . 能得到一系

18、列（包括子过程）的最优解。能得到一系列（包括子过程）的最优解。 . 不需要对系统状态转移方程、阶段效应函数不需要对系统状态转移方程、阶段效应函数等的解析性质作任何假设。等的解析性质作任何假设。缺点：缺点： .没有统一的标准模型和标准的算法可供使用。没有统一的标准模型和标准的算法可供使用。 .应用具有局限性，要求满足应用具有局限性，要求满足“无后效性无后效性”。 . 存在存在“维数灾难维数灾难”问题，变量的个数增加，问题，变量的个数增加，计算的难度成倍增加。计算的难度成倍增加。第第5节节 动态规划应用举例动态规划应用举例 5.1节节 一维资源分配问题一维资源分配问题 设有某种原料，总数量为设有某

19、种原料，总数量为a，用于生产，用于生产n种产品。种产品。若分配数量若分配数量xi用于生产第用于生产第i 种产品，其收益为种产品，其收益为g gi i(x(xi i) )问应如何分配，才能使生产问应如何分配，才能使生产n种产品的总收入最大？种产品的总收入最大？ 将数量一定的一种或若干种资源，恰当地分配将数量一定的一种或若干种资源，恰当地分配给若干个使用者，使效益函数为最优。给若干个使用者，使效益函数为最优。max z =g1(x1)+ g2(x2)+ + gn(xn)x1+x2+ xn=axi0 i=1,2, ,ns.t.决策集合：决策集合：D Dk( (sk)=)=uk|0|0 uk= =xk

20、 sk )(max)(1 , 1)()(max)(10nnsxnnkkkkksxkkxgsfnkxsfxgsfnnkkuk: :分配给生产第分配给生产第k种产品的原料数量，即种产品的原料数量，即uk= =xk；sk: :分配给用于生产第分配给用于生产第k种至第种至第n种产品的原料数量；种产品的原料数量；状态转移方程：状态转移方程： sk+1+1= =sk- -uk= =sk- -xk最优值函数最优值函数fk( (sk):):数量为数量为sk的原料分配给第的原料分配给第k种产品种产品至第至第n种产品所得到的最大总收益，动态规划的递推种产品所得到的最大总收益，动态规划的递推关系为：关系为：某工业部

21、门根据国家计划的安排，拟将某种高效某工业部门根据国家计划的安排，拟将某种高效率的设备率的设备5 5台分配给所属的甲、乙、丙三个工厂，台分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备，可以为公司提供的盈利各工厂若获得这种设备，可以为公司提供的盈利如表。如表。问：这五台设备如何分配给各工厂，才能使公司问：这五台设备如何分配给各工厂，才能使公司得到的盈利最大。得到的盈利最大。例例1 1 工工 厂厂盈利盈利 设备台数设备台数 甲甲 乙乙 丙丙 0 1 2 3 4 5 0 3 7 9 12 13 0 5 10 11 11 11 0 4 6 11 12 12 解：将问题按工厂分为解：将问题按工厂分为

22、三个阶段，甲、乙、丙三个阶段，甲、乙、丙分别编号为分别编号为1 1，2 2，3 3。 工工 厂厂盈盈利利 设设备备台台数数 甲甲 乙乙 丙丙 0 1 2 3 4 5 0 3 7 9 12 13 0 5 10 11 11 11 0 4 6 11 12 12 = g30=0=maxk=3时，时，0 s3 5， 0 x3 s3f3(s3)=maxg3x3 0 x3s3f4(s4)=0g3(0)g3(1) =4x3 *(1) =1S3=0, f3(0)=max g3x3+ f4(s4) 0 x3s3x3 *(0) =0 x3=0,1S3=1, f3(1)=max g3x3+ f4(s4) 0 x3s3

23、 工工厂厂盈盈 利利 设设 备备 台台 数数 甲甲 乙乙 丙丙 0 1 2 3 4 5 0 3 7 9 1 2 1 3 0 5 1 0 1 1 1 1 1 1 0 4 6 1 1 1 2 1 2 2) 2 (6) 2 () 1 () 0 (max)()(max) 2 (2*33332 , 1 , 04433033333xgggsfxgfxsxs3) 3 (11) 3 () 2 () 1 () 0 (max)()(max) 3 (3*333333 , 2 , 1 , 04433033333xggggsfxgfxsxs4) 4 (12) 4 () 3 () 2 () 1 () 0 (max)()(

24、max) 4 (4*3333334 , 3 , 2 , 1 , 04433033333xgggggsfxgfxsxs5) 5 (12) 5 () 4 () 3 () 2 () 1 () 0 (max)()(max) 5 (5*33333335 , 4 , 3 , 2 , 1 , 04433033333xggggggsfxgfxsxs 工工 厂厂盈盈 利利 设设 备备 台台 数数 甲甲 乙乙 丙丙 0 1 2 3 4 5 0 3 7 9 12 13 0 5 10 11 11 11 0 4 6 11 12 12 g3(x3) x3 s3 0 1 2 3 4 5 f3(s3) x*3 0 1 2 3

25、 4 5 0 4 6 11 12 12 0 4 6 11 12 12 0 1 2 3 4 5 当阶段当阶段k=2时，时， s3=s2-x2， 0 s2 5， 0 x2 s2，有有0) 0 (0) 0 ()()(max) 0 (0*22332202222xgsfxgfssx1) 1 (50540max) 0() 1 () 1 () 0(max)()(max) 1 (1*21 , 032321 , 033220222222xfgfgsfxgfxxsxs2) 2 (100104560max) 0 () 2 () 1 () 1 () 2 () 0 (max)()(max) 2 (2*22 , 1 ,

26、03232322 , 1 , 033220222222xfgfgfgsfxgfsxxsx2) 3 (1401141065110max) 0 () 3 () 1 () 2() 2() 1 () 3 () 0 (max)()(max) 3 (3*23 , 2 , 1 , 0323232323 , 2 , 1 , 033220222222xfgfgfgfgsfxgfsxxsx2 , 1) 4 (16011411610115120max) 0 () 4 () 1 () 3 () 2 () 2 () 3 () 1 () 4 () 0 (max)()(max) 4 (4*24 , 3 , 2 , 1 ,

27、032323232324 , 3 , 2 , 1 , 033220222222xfgfgfgfgfgsfxgfsxxsx2) 5 (210114116111110125120max) 0 () 5 () 1 () 4 () 2 () 3 () 3 () 2 () 4 () 1 () 5 () 0 (max)()(max) 5 (5*25 , 4 , 3 , 2 , 1 , 03232323232325 , 4 , 3 , 2 , 1 , 033220222222xfgfgfgfgfgfgsfxgfsxxsxg2(x2)+f3(s2-x2) x2 s2 0 1 2 3 4 5 f2(s2) x*

28、2 0 1 2 3 4 5 0 0+4 0+6 0+11 0+12 0+12 5+0 5+4 5+6 5+11 5+12 10+0 10+4 10+6 10+11 11+0 11+4 11+6 11+0 11+4 11+0 0 5 10 14 16 21 0 1 2 2 1,2 2 结果列于下表：结果列于下表：f3(1-0)=f3(1)g3(x3) x3 s3 0 1 2 3 4 5 f3(s3) x*3 0 1 2 3 4 5 0 4 6 11 12 12 0 4 6 11 12 12 0 1 2 3 4 5 =4 f3(5-3)=f3(2)=max =21g1(0)+f2(5)g1(1)+

29、f2(4)g1(2)+f2(3)g1(3)+f2(2)g1(4)+f2(1)g1(5)+f2(0) =max g1x1+ f2(s1- x1) x1=0,1,2,3,4,5当阶段当阶段k=1时，时， s2=s1-x1， s1=5， 0 x1 s1，有有S1=5, f1(S1 )=max g1x1+ f2(s2) 0 x1s1x1*(5)=0, 20+213+167+149+1012+513+0= maxg1(x1)+f2(s1-x1) x1 s1 0 1 2 3 4 5 f1(s1) x*1 5 0+21 3+16 7+14 9+10 12+5 13+0 21 0,2 结果可写成表格的形式结果

30、可写成表格的形式g2(x2)+f3(s2-x2) x2 s2 0 1 2 3 4 5 f2(s2) x*2 0 1 2 3 4 5 0 0+4 0+6 0+11 0+12 0+12 5+0 5+4 5+6 5+11 5+12 10+0 10+4 10+6 10+11 11+0 11+4 11+6 11+0 11+4 11+0 0 5 10 14 16 21 0 1 2 2 1,2 2 S2*=s1*-x1*=5-0=5S3*=s2*-x2*=5-2=3max逆推到第一张表逆推到第一张表g3(x3) x3 s3 0 1 2 3 4 5 f3(s3) x*3 0 1 2 3 4 5 0 4 6 1

31、1 12 12 0 4 6 11 12 12 0 1 2 3 4 5 g2(x2)+f3(s2-x2) x2 s2 0 1 2 3 4 5 f2(s2) x*2 0 1 2 3 4 5 0 0+4 0+6 0+11 0+12 0+12 5+0 5+4 5+6 5+11 5+12 10+0 10+4 10+6 10+11 11+0 11+4 11+6 11+0 11+4 11+0 0 5 10 14 16 21 0 1 2 2 1,2 2 S3*=s2*-x2*=5-2=3x3*=3x2*=2按计算表格的顺序逆推，可知最优分配方案有两个：按计算表格的顺序逆推，可知最优分配方案有两个：甲工厂分配甲

32、工厂分配0台，乙工厂分配台，乙工厂分配2台台,丙工厂分配丙工厂分配3台。台。甲工厂分配甲工厂分配2台，乙工厂分配台，乙工厂分配2台，丙工厂分配台，丙工厂分配1台。台。 以上两个分配方案所得到的总盈利均为以上两个分配方案所得到的总盈利均为21万元万元1.2 资源连续分配问题资源连续分配问题: 一般问题的提法是一般问题的提法是 A种生产种生产数量数量u1投入投入 收益收益g(u1) 年终资源回收率年终资源回收率a如此进行如此进行n年，如何确定投入年，如何确定投入A的资源量的资源量u1、un，使总收入最大？使总收入最大？ B种生产种生产数量数量s1-u1 收益收益h(s1-u1) 年终资源回收率年终

33、资源回收率b资源数量资源数量s1第一年第一年资源数量资源数量s2=au1+b(s1-u1)第二年第二年 A种生产种生产数量数量u2投入投入;收益收益g(u2);年终回收率年终回收率a B种生产种生产数量数量s2-u2;收益收益h(s2-u2);年终回收率年终回收率b到到n年年此问题的静态规划问题模型为此问题的静态规划问题模型为： nisuusbaususbaususbaustsushugZiinnnnniiii,2,1,0)()()(.)()(max1222311121动态规划的逆推关系方程为：动态规划的逆推关系方程为： 1 , 2 , 1)()()(max)()()(max)(100nkus

34、baufushugsfushugsfkkkkkkksukknnnsunnnnnn最后求得得最后求得得f1(s1)即为所求问题的最大收入。即为所求问题的最大收入。 高负荷高负荷: 产量函数产量函数 g=8u1, u1是投入生产的机器是投入生产的机器 数量，年完好率为数量，年完好率为 a=0.7， 低负荷低负荷: 产量函数产量函数 h=5y， y是投入生产的机器是投入生产的机器数量，数量， 年完好率为年完好率为b=0.9。 假定开始生产时完好机器的数量为假定开始生产时完好机器的数量为1000台。台。 机器机器 例例2 2 机器负荷分配问题机器负荷分配问题解：设阶段数解：设阶段数k表示年度。表示年度

35、。 试问每年如何安排机器在高低两种负荷下的生试问每年如何安排机器在高低两种负荷下的生产，可使产，可使5年内生产的产品总产量最高。年内生产的产品总产量最高。状态变量状态变量sk为第为第k年度初拥有的完好机器台数；年度初拥有的完好机器台数； 决策变量决策变量uk为第为第k年度中分配高负荷下生产的机年度中分配高负荷下生产的机 器器台数。台数。低负荷下生产的机器台数是低负荷下生产的机器台数是sk-uk。 状态转移方程状态转移方程5 , 2 , 1),( 9 . 07 . 0)(1kusuusbauskkkkkkk第第k年度产量为年度产量为)(58),(kkkkkkusuusv 递推方程为递推方程为 1

36、 , 2 , 5)( 9 . 07 . 0()( 58max)(0)(1066kusufususfsfkkkkkkksukkkk指标函数指标函数515 , 1),(kkkkusvV允许决策集合允许决策集合 0 uk sk当当k=5时时 , f5(s5)= max 8u5+5 s5 - u5 + f6(s6) 0u5 s5=max 3u5+5 s5 0u5 s5u5*= s5 , f5(s5)=8 s5当当k=4时时 , f4(s4)= max 8u4+5( s4 u4 ) + f5(0.7 u4+0.9(s4 u4 ) 0u4 s4= max 13.6u4+12.2( s4- u40u4 s4

37、= max 1.4u4+12.2 s40u4 s4u4*= s4 , f4(s4)=13.6s4依次类推可得依次类推可得， u3*=s3 f3(s3)=17.5 s3 u2*=0 f2(s2)=20.8 s2 u1*=0 f1(s1)=23.7 s1最高产量为最高产量为f1(s1) =23700(台台)。因此最优策略为因此最优策略为: u1*=0, u2*=0, u3*=s3, u4*= s4 u5*= s5, u5*= s5 , f5(s5)=8 s5u4*= s4 , f4(s4)=13.6s45.2 生产存贮问题生产存贮问题 一个生产部门，如何在已知生产成本、库存一个生产部门，如何在已知

38、生产成本、库存费用和各阶段市场需求条件下，决定各阶段产量，费用和各阶段市场需求条件下，决定各阶段产量，使计划内的费用总和为最小的问题。使计划内的费用总和为最小的问题。例例8. 某工厂要对一种产品制订今后四个时期的生某工厂要对一种产品制订今后四个时期的生产计划，据估计在今后四个时期内，市场对于该产计划，据估计在今后四个时期内，市场对于该产品的需求量如下表所示。假定该厂生产每批产产品的需求量如下表所示。假定该厂生产每批产品的固定成本品的固定成本3千元，若不生产就为千元，若不生产就为0；每单位产；每单位产品成本为品成本为1千元；每个时期生产能力所允许的最大千元；每个时期生产能力所允许的最大生产批量为

39、不超过生产批量为不超过6个单位；每个时期未售出的产个单位；每个时期未售出的产品，每单位需付存贮费品，每单位需付存贮费0.5千元。还假定在第一个千元。还假定在第一个时期的初始库存量为时期的初始库存量为0，第四个时期末的库存量也，第四个时期末的库存量也为为0。问该厂应如何安排各个时期的生产与库存，。问该厂应如何安排各个时期的生产与库存，才能在满足市场需求条件下，使总成本最小。才能在满足市场需求条件下，使总成本最小。时 期 (k) 1 2 3 4 需求量 (dk) 2 3 2 4 解：设解：设dk为第为第k阶段的需求量，阶段的需求量，xk为第为第k阶段的生产量阶段的生产量，vk为第为第k时期末库存量

40、。有时期末库存量。有vk= vk-1+ xk- dk把生产的四个时期作为四个阶段，把生产的四个时期作为四个阶段，k=1, 2, 3, 4。由题。由题意知，第意知，第k阶段的生产成本为阶段的生产成本为66, 2 , 1,1300)(kkkkkkxxxxxc当当当第第k时期末库存量为时期末库存量为vk时的存储费用为时的存储费用为hk(vk)=0.5vk第第k时期内的总成本为时期内的总成本为ck(xk)+hk(vk)动态规划的顺序递推关系式为动态规划的顺序递推关系式为)()(min)(6 , 5 , 4 , 3 , 2 , 1),6 ,min()()()(min)(1111)6,min(111011

41、1vhxcvfkdvxdvfvhxcvfdvxkkkkkkkkkkkxkkkk边界条件其中当当k=1时，由时，由f1(v1)=minc1(x1)+h1(v1) 对对v1在在0与与 之间之间的值分别进行计算的值分别进行计算即即v1=0, 1, 2, 3, 4，于是由，于是由x1=minv1+2,6知，知，x1可可取值为取值为2, 3, 4, 5, 6。分别计算如下：。分别计算如下：f1(0)=min3+ x1 +0.50=5所以所以x1=2426 , 9min6 ,min421jjddx1=min(v1+2,6)x1=2 f1(1)=min3+ x1 +0.51=6.5 所以所以x1=3f1(2

42、)=min3+ x1 +0.52=8 所以所以x1=4f1(3)=min3+ x1 +0.53=9.5 所以所以x1=5f1(4)=min3+ x1 +0.54=11 所以所以x1=6k=2，f2(v2)=minc2(x2)+h2(v2)+f1(v2+3-x2) 0 x2minv2+3, 6 x1=3x1=4x1=5x1=6v2可在可在0与与 之间取值。即之间取值。即v2可取可取值值0, 1, 2, 3。x2可在可在0与与minv2+3, 6之间取值。分别计算如下：之间取值。分别计算如下： 36 ,min432jjdd由由 有有x2=0。 5 . 9565 . 65845 . 90min) 0

43、() 0() 3 () 1 () 0() 2() 2() 0() 1 () 3 () 0() 0(min) 0(1221221221223022fhcfhcfhcfhcfx5 .1155 . 75 . 65 . 685 . 55 . 95 . 4115 . 0min)0() 1 ()4() 1 () 1 () 3()2() 1 ()2() 3() 1 () 1 ()4() 1 ()0(min) 1 (1221221221221224022fhcfhcfhcfhcfhcfx由由 有有x2=0。 用同样的方法计算用同样的方法计算f2(2)=minc2(x2)+h2(2)+f1(5x2)=14 ,

44、有有x2=5 0 x25 f2(3)=minc2(x2)+h2(3)+f1(6x2)=15.5，有，有x2=6 0 x26k=3，f3(v3)=minc3(x3)+h3(v3)+f2(v3+2x3) ，v3可在可在0与与min4, 62=4之间取值。之间取值。x3可在可在0与与minv3+2, 6之间取之间取值。值。 分别计算如下：分别计算如下： 有有x3=0。 145 . 955 .114140min)0()0()2() 1 ()0() 1 ()2()0()0(min)0(2332332333fhCfhCfhCf用同样的方法计算用同样的方法计算 f3(2)=minc3(x3)+h3(2)+f

45、2(4x3)=17.5，有，有x3=40 x34 f3(3)=minc3(x3)+h3(3)+f2(5x3)=19，有，有x3=50 x35 f3(4)=minc3(x3)+h3(4)+f2(6x3)=20.5，有，有x3=60 x36有有x3=0或或3。 16*5 . 95 . 65 .115 . 5145 . 4*55.155 . 0min) 0() 1 () 3 () 1 () 1 () 2() 2() 1 () 1 () 3 () 1 () 0(min) 1 (2332332332333fhcfhcfhcfhcfk=4，因要求第，因要求第4时期末的库存量为时期末的库存量为0，即，即v4

46、=0，故有，故有 f4(0)=minc4(x4)+h4(0)+f3(4x4) 0 x44 x4=0。5 .201471665 .175194*5 .200min)0()4() 1 ()3()2()2()3() 1 ()4()0(min3434343434fCfcfcfcfc按计算顺序反推算，可找出每个时期的最优生产按计算顺序反推算，可找出每个时期的最优生产决策为决策为:x1=5，x2=0，x3=6，x4=0其相应的最小总成本为其相应的最小总成本为20.5千元。千元。 例例10 某车间需要按月在月底都要供应一定数量的部件某车间需要按月在月底都要供应一定数量的部件总装车间，由于生产条件的变化，该车

47、间在各月中生总装车间，由于生产条件的变化，该车间在各月中生产每单位这种部件所耗费的工时不同，各月份的生产产每单位这种部件所耗费的工时不同，各月份的生产量于当月的月底前，全部要存入仓库以备后用。已知量于当月的月底前，全部要存入仓库以备后用。已知总装车间的各个月份的需求量以及在加工车间生产该总装车间的各个月份的需求量以及在加工车间生产该部件每单位数所需工时数如表部件每单位数所需工时数如表6-7所示。所示。 设库存容量设库存容量H=9，开始时库存量为，开始时库存量为2，期终库存量为，期终库存量为0。表表6-70 8 5 3 2 7 411 18 13 17 20 10月份需求量月份需求量 dk单位工

48、时单位工时 ak 0 1 2 3 4 5 6 月份月份 k 需要制定一个半年生产计划，使得既满足需要需要制定一个半年生产计划，使得既满足需要和库存容量的限制，又使得总耗费工时数最少。和库存容量的限制，又使得总耗费工时数最少。 解解 这是一个多阶段决策问题，采用逆序解法。这是一个多阶段决策问题，采用逆序解法。 按月份划分阶段，即阶段变量为按月份划分阶段，即阶段变量为k=0，1，2，6。 状态变量状态变量 第第k月的部件库存量（上月月的部件库存量（上月产品送入后，本月需求量送出前）。产品送入后，本月需求量送出前）。 决策变量决策变量 表示第表示第k月生产的部件数量。月生产的部件数量。 kuks 状

49、态转移方程为状态转移方程为阶段指标阶段指标最优值函数最优值函数 表示在表示在k月开始的库存量为月开始的库存量为sk，从第从第k月到月到6月末所生产部件的最小累计工时数。月末所生产部件的最小累计工时数。 递推关系式为递推关系式为kkua)(kksf0)(6 , 5 , 4 , 3 , 2 , 1 , 0),(min)(771)(sfkdusfuasfkkkkkksDvkkkkk, 0:)(6,.,1 , 011HdusduusDHsdkdusskkkkkkkkkkkkkk故允许决策集合为且 当当k=6时，因要求期终库存量为时，因要求期终库存量为0，即，即s7=0。因每月。因每月的生产是供应下月的

50、需要，故第的生产是供应下月的需要，故第6月不用生产，月不用生产，即即u6=0。因此。因此f6(s6)=0, s6=d6=4当当k=5时，由时，由s6=s5+u5-d5有有u5=11-s5 所以所以 f5(s5)=min(a5u5)=10(11-s5)=110-10s5最优解最优解u5*=11-s5当当k=4时，时，u5=11-s51301010min)2(1011020min)(min)(44444444544)(4444444suusudusfuasfuusDu4*4444444444444444444444592022013010)9(10)(119)(, 9119 , 0max, 011

51、9sussssfsussDssusususHdusd及最优解故得为所以又因而又有由3*3333333331217244)(125 , 0max)(sussfsussD及最优解故得为又280203min)3(2022017min)(min)(,333)(333)(333433)(33333333333suusudusfuasfksDusDusDu时当1*11111111111111211)(111318442)(1713)(337135min)(min)(,11111sussfsussDsudusfuasfkusDu及最优解故得为其中时当222222222222222322)(221413273

52、)(148 , 0max)(329174min)(min)(,22222sussfsussDsudusfuasfkusDu及最优解故得为其中时当。相应的最小总工时数为，月的最优生产计划为：月到所以从为：即得各阶段的最优决策再按计算顺序反推之，和所以因及最优解故得为其中时当357403947504, 0, 3, 9, 4, 77357, 2911379)(98)(442187min)(min)(,0*5*4*3*2*1*0*0000*00000000000000100)(000000uuuuuuufssussfsussDsudusfuasfkusDu 个人、单位等随时均有设备更新问题。自行车、个

53、人、单位等随时均有设备更新问题。自行车、彩电、设备随着使用年限的增加而设备陈旧，处理价彩电、设备随着使用年限的增加而设备陈旧，处理价格愈低，因此需要维修和更新的费用增加。处于各种格愈低，因此需要维修和更新的费用增加。处于各种阶段的设备总是面临保留还是更新问题。保留还是更阶段的设备总是面临保留还是更新问题。保留还是更新，应该从整个计划期间的总回收额来考虑，而不能新，应该从整个计划期间的总回收额来考虑，而不能从局部的某个阶段的回收额来考虑，是一个多阶段的从局部的某个阶段的回收额来考虑，是一个多阶段的决策问题。决策问题。 5.3 5.3 设备更新问题设备更新问题设备更新问题提法如下（以一台机器为例）

54、：设备更新问题提法如下（以一台机器为例）： n n为设备计划使用年数。为设备计划使用年数。 I Ik k(t)(t) 为第为第k k年（阶段）机器役龄为年（阶段）机器役龄为t t年的一台机年的一台机器运行（在使用一年）所得的收入。器运行（在使用一年）所得的收入。 O Ok k(t)(t) 为第为第k k年机器役龄为年机器役龄为t t年的一台机器运行年的一台机器运行（在使用一年）时所需运行的费用（或维修费用）（在使用一年）时所需运行的费用（或维修费用） 。 C Ck k(t)(t) 为第为第k k年机器役龄为年机器役龄为t t年的一台机器更新时年的一台机器更新时所需更新的净费用（处理一台役龄为所

55、需更新的净费用（处理一台役龄为t t的旧设备，买的旧设备，买进一台新设备的更新净费用）。进一台新设备的更新净费用）。 为折扣因子，表示一年以后的收入是上一年的为折扣因子，表示一年以后的收入是上一年的 单位。单位。 要求在要求在n n年内的每年年初作出决策，是继续使用年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使旧设备还是更换一台新的，使n n年内总效益最大？年内总效益最大？建立动态规划模型如下：建立动态规划模型如下： RxKxsskkkk111 阶段效益为：阶段效益为：RxKxscOIsOsIxsvkkkjjjkjkjkkj)() 0() 0()()(),( 阶段阶段k（k=1，

56、2，n）：表示计划使用该设备的）：表示计划使用该设备的年限数。年限数。 状态变量状态变量sk：第：第k年初，设备已使用过的年数，即役年初，设备已使用过的年数，即役龄。龄。 决策变量决策变量xk：是第：是第k年初更新，还是保留使用旧设年初更新，还是保留使用旧设备，分别用备，分别用R，K表示。表示。状态转移方程为：状态转移方程为： 最优指标函数最优指标函数fk(sk)：表示第：表示第k年初，使用一台已用了年初，使用一台已用了sk年的设备，到第年的设备，到第n年末的最大收益，动态规划的基本年末的最大收益，动态规划的基本方程为方程为0)()(),(max)(1111nnkkkkjRorKxkksfsfxsvsfk实际上实际上RxKxfscOIsfsOsIsfkkkkkkkkkkkkkkk) 1 ()() 0 () 0 () 1()()(max)(11例：设某台新设备的年效益及年均维修费用、更新净例：设某台新设备的年效益及年均维修