十动态规划的应用---生产与存储,设备更新问题

1、 生产与存贮问题生产与存贮问题 生产周期分为生产周期分为 n 个阶段，已知个阶段，已知 最初库存量：最初库存量： x1 阶段市场的需求：阶段市场的需求：dk 生产的固定成本：生产的固定成本：K 单位产品的消耗费用：单位产品的消耗费用：L 单位产品的阶段库存费用：单位产品的阶段库存费用：h 仓库容量：仓库容量：M 阶段生产能力为阶段生产能力为B 一个生产部门，如何在已知生产成本、库存费用和一个生产部门，如何在已知生产成本、库存费用和各阶段市场需求条件下，决定各阶段产量，使计划内的各阶段市场需求条件下，决定各阶段产量，使计划内的费用总和为最小的问题。费用总和为最小的问题。 问如何安排各阶段产量，使

2、计划周期内的费用总和问如何安排各阶段产量，使计划周期内的费用总和最小。最小。Mxk不能超过阶段不能超过阶段 k 至阶段至阶段 n 的需求总量的需求总量xk dk+ dk+1+ dn，k =1, 2, , n阶段阶段 k 的的初始库存量初始库存量，x1已知，已知，xn+1 = 00 xk min M， dk+ dk+1+ dn，（k =1, 2, , n）状态变量状态变量 xk：不能超过库存容量不能超过库存容量M，决策变量决策变量 uk：不超过生产能力不超过生产能力Bukkkkuxd阶段阶段 k 的产量的产量uk dk+ dk + 1+ + dn- xk不小于该阶段的需求和库存量之差，不小于该阶

3、段的需求和库存量之差， 不超过不超过 kn 阶段的总需求减去第阶段的总需求减去第 k 阶段初的阶段初的库存量，库存量，dk- -xk uk minB，dk+ dk+1+ dn- -xk 状态转移方程状态转移方程kkkkduxx1为阶段生产费用和库存费用之和，即为阶段生产费用和库存费用之和，即)(),(kkkkkkkduxhLuKuxg阶段阶段 k 的生产费用的生产费用k 阶段末的库存费用阶段末的库存费用动态规划基本方程动态规划基本方程阶段效益阶段效益)()(min)(11)(kkkkkkxDukkxfduxhLuKxfkkkfn+1（xn+1）= 0，k = 1, 2, , ndk- -xk

4、uk minB，dk+ dk+1+ dn- -xk例5 已知 n = 3，K = 8，L = 2，h = 2，x1 = 1，M = 4，x4 = 0，B = 6，d1 = 3，d2 = 4，d3 = 3，求解生产与库存问题。 解：递推方程)()(min)(11)(kkkkkkxDukkxfduxhLuKxfkkkf 4 ( x4 ) = 0，k = 1, 2, 3 33 , 6min33333328min3xuxuxfk当当时时=8+2(3-x3)=14-2x3 3,min,min033dMdMxnkii仓库容量：仓库容量：4dk-xk uk minB，dk+ dk + 1+ dn-xk1kx

5、 若 x3 = 0, u*3 (0) = 3则 f3(0) =14若 x3 = 1, 则 f3 (1) = 12 u*3 (1) = 2若 x3 = 2, 则 f3 (2) = 10 u*3 (2) = 1 若 x3 = 3, 则 f3 (3) = 8 u*3 (0) = 0f3(x3)= 14-2x3 u3 =3-x3 x3：03 u3 x30123f3(x3)u*3(x3)0141431121222101013880kkkkduxx1k =22223duxx容量44+3uk dk-xk4-x2 u2 min6,7-x2 f2 (x2 )= min 8+2u2+2(x2 +u2-4)+ f3

6、 (x2 + u2-4)4-x2 u2 minB，d2+ d3-x2=min6,7-x20 x2 minM，d2+ d3 =min4,7=4u*2 (0) = 4x2 = 04-x2 u2 min6,7-x2 30104201221814016min)4()4(228min)0(23226, 5 , 422ufuufux2 = 1)3()3(228min) 1 (23226, 5 , 4, 322ufuufu288620104281221614014minu*2 (1) = 3 u3 x30123f3(x3)u*3(x3)01414311212221010138804-x2 u2 min6,7

7、-x2 x2 = 2u*2 (2) = 24-x2 u2 min6,7-x2 )2()2(228min)2(23225 , 4, 3 , 222ufuufu268618104161221414012minx2 = 3)1() 1(228min)3(23224, 3 , 2, 122ufuufu248616104141221214010minu*2 (3) = 1x2 = 4u*2(4)=04-x2 u2 min6,7-x2 )(228min)4(23223 , 2, 1 , 022ufuufu22861410412122101408min结果见下表： u1 x123456f1(x1) u*1(

8、x1)112+0+30 14+2+28 16+4+26 18+6+24 20+8+22422k =1f2=302 u1 6x2= x1+ u1-d1=1+ u1-3= u1- 2u*1 (1) = 2x1 =1)2()2(228min22116, 5 , 4, 3 , 21ufuuu)()(228min) 1 (2211116, 5 , 4, 3 , 211xfduxufu422282024618264162821430012min u2 x2 0 1 2 3 4 5 6 f2(x2) u*2(x2) 0 16+0+14 18+2+12 20+4+10 30 4 1 14+0+14 16+2+

9、12 18+4+10 20+6+8 28 3 2 12+0+14 14+2+12 16+4+10 18+6+8 26 2 3 10+0+14 12+2+12 14+4+10 16+6+8 24 1 4 8+0+14 10+2+12 12+4+10 14+6+8 22 0 f3=14 u3 x30123f3(x3)u*3(x3)01 41 4311 21 2221 01 013880最优决策为最优决策为 1，0，0，0 x2=u1-2=0 x3=x2+u2-d2=0+4-4=0最优路线为最优路线为最优目标函数值为最优目标函数值为42。（状态变量）（状态变量）u*1 (1) = 2，u*2 (0)

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

11、需的净费用（处理一台役龄为t的旧设备，买进一台新的旧设备，买进一台新设备的更新净费用）。设备的更新净费用）。 设备更新问题设备更新问题 为折扣因子，表示一年以后的收入是上一年的为折扣因子，表示一年以后的收入是上一年的 单单位。位。 要求在要求在n年内的每年年初作出决策，是继续使用旧年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使设备还是更换一台新的，使n年内总效益最大？年内总效益最大？建立动态规划模型如下：建立动态规划模型如下： 阶段阶段k（k=1，2，n）表示计划使用该设备的）表示计划使用该设备的年限数。年限数。 状态变量状态变量sk：第：第k年初，设备已使用过的年数，即年初，设

12、备已使用过的年数，即役龄。役龄。 决策变量决策变量xk：是第：是第k年初更新，还是保留使用旧设年初更新，还是保留使用旧设备，分别用备，分别用R ，K表示。表示。RxKxsskkkk111 阶段效益为：阶段效益为：RxKxscOIsOsIxsvkkkjjjkjkjkkj)() 0 () 0 ()()(),( 状态转移方程为：状态转移方程为： 最优指标函数最优指标函数fk(sk)：表示第：表示第k年初，使用一台已用了年初，使用一台已用了sk年的设备，到第年的设备，到第n年末的最大收益。年末的最大收益。0)()(),(max)(1111nnkkkkjRorKxkksfsfxsvsfk实际上实际上11

13、1( )( )()( )max(0)(0)( )(1)kkkkkkkkkkkkkkkI sO sfsxKf sIOc sfxR例例7：设某台新设备的年效益及年均维修费用、更新：设某台新设备的年效益及年均维修费用、更新净费用如下表，试确定今后五年内的更新策略，使总净费用如下表，试确定今后五年内的更新策略，使总效益最大。（设效益最大。（设 =1） 动态规划的基本方程为动态规划的基本方程为解：解：n=5RxKxscOIsOsIsfk555555555555)() 0() 0()()(max)(5状态变量状态变量s5可取可取1，2，3，4 役龄项目012345效益IK(t)54.543.7532.5运

14、行费OK(t) 0.511.522.53更新费CK(t) 0.51.5 2.22.533.5单位：万元单位：万元KxRxKxcOIOIf) 1 (5 . 35 . 15 . 0515 . 4max) 1 () 0() 0() 1 () 1 (max) 1 (555555555KxRxKxcOIOIf)2(5 . 22 . 25 . 055 . 15 . 4max)2()0()0()2()2(max)2(555555555卖掉役龄卖掉役龄2年的设年的设备，买入新设备备，买入新设备的更新费用的更新费用RxRxKxcOIOIf)3(25 . 25 . 05275. 3max)3()0()0()3()

15、3(max)3(555555555RxRxKxcOIOIf)4(5 . 135 . 055 . 23max)4()0()0()4()4(max)4(555555555RxKxfscOIsfsOsIsfk445444445444444) 1 ()() 0 () 0 () 1()()(max)(4状态变量状态变量s4可取可取1，2，3RxRxKxfscOIsfsOsIfs) 1 (5 . 65 . 35 . 15 . 055 . 215 . 4max) 1 ()() 0() 0() 1()()(max) 1 (44454444454444144RxRxKxfscOIsfsOsIfs)2(8 . 5

16、5 . 32 . 25 . 0525 . 14max) 1 ()()0()0() 1()()(max)2(44454444454444244RxRxKxfscOIsfsOsIfs) 3(5 . 55 . 35 . 25 . 055 . 1275. 3max) 1 ()()0()0() 1()()(max) 3(44454444454444344RxKxfscOIsfsOsIsfk334333334333333) 1 ()() 0 () 0 () 1()()(max)(3此时此时s3可取可取1或或2RxRxKxfscOIsfsOsIfs) 1 (5 . 95 . 65 . 15 . 058 .

17、515 . 4max) 1 ()() 0() 0() 1()()(max) 1 (33343333343333133RxRxKxfscOIsfsOsIfs)2(8 . 85 . 62 . 25 . 055 . 55 . 14max) 1 ()()0()0() 1()()(max)2(33343333343333233RxKxfscOIsfsOsIsfk223222223222222) 1 ()() 0() 0() 1()()(max)(2由于状态由于状态s2只能取只能取1，所以有，所以有RxRxKxfscOIsfsOsIfs) 1 (5 .125 . 95 . 15 . 058 . 815 .

18、 4max) 1 ()()0()0() 1()()(max) 1 (22232222232222122RxKxfscOIsfsOsIsfk112111112111111) 1 ()() 0 () 0 () 1()()(max)(1由于状态由于状态s1只能取只能取0，所以有，所以有KxRxKxfscOIsfsOsIfs) 0(175 .125 . 05 . 055 .125 . 05max) 1 ()() 0() 0() 1()()(max) 0(11121111121111011寻找最优解，上述过程递推回去。寻找最优解，上述过程递推回去。当当x*1(0)=K，由状态转移方程，由状态转移方程 本例的最优策略是本例的最优策略是K，R，R，R，K，即第一，即第一年初购买的设备到第二、三、四年初各更换一次，用年初购买的设备到第二、三、四年初各更换一次，用到第五年年末，总效益为到第五年年末，总效益为17万元。万元。RxKxss111211s2=1，查，查f2(1)得得x*2=RRxKxss222311s3=1，查，查f3(1)得得x*3=Rs4=1，查，查f4(1)得得x*4=Rs5=1，查，查f5(1)得得x*5=K 练习