设备更新问题

1、设备更新问题许多公司和顾客面临决定在他们应该使用现有设备多长时间才更换一台新设备。这类 问题被称做“设备更新问题”而且常常利用动态规划求解这个问题。举例1某家汽车修理厂总要用到一台发动机分析仪。新分析仪的成本为1000元。分析仪使用第i年的维修费mi如下，mi=60元，m2=80元，m3= 120元，分析仪可以使用1, 2,或3年，在使用i年之后可以更换一台新的分析仪。如果更换使用了i年的分析仪，可以得到残值® ,Si =800元，S2二600元，S3 =500元。已知必须在现在购买新分析仪（时间0）,修理厂决定极 小化在今后5年内净成本二维修费用更新费用-残值的更新交换策略。第】年

2、 第2年 第3年 第4年 第5年9时间时间时间时间时间时间012345举例2一家汽车公司有一种型号的汽车，每辆汽车的年均利润函数 rt与年均维修费用mt , 购买同种型号汽车每辆购价为 20万元。如果出售不同使用年龄汽车的价格 pt如表。该公 司年初有一辆新汽车，试计划今后 4年盈利最大的更新计划。解：阶段数状态：以汽车的役龄为状态变量， Sk =t，表示在第k阶段汽车使用年限为t决策变量：继续使用xk t = 0，更新汽车xk t = 1状态转移方程式Skv设fk t =在第k年开始使用役龄为t年的汽车，从第k年到第n年的最佳收入役龄（年）0123利润函数（万元）r（t ）r 201817.

3、515维修费用（万元）m（t）P 22.546 :出售价格（万元）P（t）171615.515购买价格（万元）20202020|更新R: 4（0）-mk（O）+ p（t）-20+ fk+i（1）fk t 二 maxl续用 K: s（t）-mk（t）+ f（t + 1）k = 4S4更新x = 1续用x = 0f4（S4 ）£（S4 ）S5120-2+16-20=14）18-2.5=15.5*15.502220-2+15.5-20=13.5*17.5-4=13.5*13.50,11,3320-2+15-20=1315-6=91301k = 3S3更新续用f3（SO*怡（S3 ）S412

4、0-2+16-20+15.5=29.518-2.5+13.5=2929.511220-2+15.5-20+15.5=29*17.5-4+13=16.52911k = 2S2更新续用f2（S2 ）*X2（S2 ）S3120-2+16-20+29.5=43.518-2.5+29=44.5*44.502k = 1§更新续用X1（0）S2020-2+44.5=62.5*62.501X = Xi = 0, x?二 0, X3 = 1, X4 = 0：, z* 二 62.5应用动态规划的难点状态空间大到利用动态规划求解要求大量的计算时间。不可加的递推：fk（Uk不代表在当前阶段到将来的成本或利润

5、之和。 举例：王先生要从城市1开车到城市10去，他关心的不是最短距离，而是极小化在开车过程 中的海拔高度（用高出海平面的千英尺）。cj是从城市i到城市j所遇到的最大高度。 定义fk i代表从城市出发所遇到最小的最大高度，有如下递推公式f4 i 二 Ci,10f4 7 =13 7 > 10f4 8 =8 8 > 10f4 99 > 10max如=8, f4 (7)= 13 = 13 f3 (5) = min J maxg8 = 7, f4(8)= 8 = 8J (5t 8)| max a® = 10, f4 (9)= 9 = 10”maxc6,7, f4(7 ) =

6、13f3(6)= min Jmaxc6,8, f4(8) = 8J (6t 8)max%, f4(9 ) = 9f2(2)= maxc2,5 = 9, f3(5)= 8 = 9*= (2t 5)f2(3)= maxlc3,5 = 7, f3(5) = 8 = 8*今(3t 5)I max c4,5 = 11, f3 (5) = 8 = 11f2 4i；=minlmaxc4,6 = 7, f3(6 )= 8= 8J (4t 6)maxq,2 = 10, f2(2 )= 9 TOt (1 )= min < max'% = 7, f23)= 8=(1t 3)maxq,4 = 6, f2

7、(4)= 8 = 8*= (1- 4)(3t 518000英尺最优路线是1； f； - 8 > 10，旅行中所遇到的最大高度是14 t 6J马氏决策规则 随机系统的多阶段决策：马尔柯夫决策规则 确定型：X Ui ,X2,Xn?随机型：X U1 ,X2 z2 ,X n 召 I、马尔柯夫过程动态随机系统的特征，系统的状态转移规律具有无后效性：已知当前状态，采取的决策后，下一阶段的状态的概率分布是已知的 与系统以前的发展历史无关。称具有这种系统状态的转移规律具有马尔科夫特征状态和时间都是离散的马氏过程 时间间隔为1个单位 系统的状态为有限个Ntt +1"P=PijhN状态转移 矩阵

8、ijPiJ(1)(2)销路好(1)P11P12 10.50.51销路差(2) L p21P22 -o.40.6 一、赋值马氏过程1. 具有N个状态的马氏过程2. 任意时刻从ij获得相应的收益记作rij , R =报酬矩阵jiJ nxN_r11 r 1293 IR= |12= |2 1 r 2 2 -3 7 _3. 经过一定阶段运行后的总报酬q i =从i出发作一次转移的期望报酬Nq i 八Pj rj 1, 2, Nj勻Q= q1),q 2： q NT 一次转移的期望报酬向量。Vn i =从i出发作n次转移的期望报酬NVn i 八 Pj rjVn_i j乂 二 Vn 1 M 2 ,Vn N T已

9、知Pf N定义乘法oP12ri1P22 IJ2112P11GP12L q 1=1丄1=1122-lp2121 + p2222 丿 lq（2）丿N、PNj rNjjT（Np R二 ' 吋门Vn 二 Q PVn_1V1 二 Q举例：6_PnP120.50.51114 1_93 11=R =|-P21P22 _0.40.6 一丿2122 一3-7一0.50.51一93 16 10.40.6 一3_7 一1-3 一PQ60.5 0.567.5-30.4 0.6匸-3一-24马氏决策规则在赋值马氏过程中，若在某个状态选用不同的决策能够改变相应的状态转移矩阵和赋值矩 阵，则产生动态随机系统求解最优

10、问题。有限阶段的模型的求解方法一一值迭代法，总期望报酬值最大化举例:1.决策1不登广告,0. 5P1 二0. 42. 决策2登广告2P. 8P2 二0. 70J5r1930.一 63-7一0. 2 R0. 344“-19.问题在若干月内采用什么决策才能使其总期望报酬为最大？设n表示系统的阶段数pd =当前状态为i,下一步采用决策d转移到状态j的概率fn i =表示系统初始状态为，经过个阶段采用最优策略的总期望报酬最大， 则有如下方程式：r nfn i 二 m.ax qd i ： pj fn_1 j , n=2,3,f1i = max,：qd i由于1 0. 50. 5936Q - |e-0. 4 0.一6 3 一 7- 一 32 0. 8 0. 2444Q = |e |=|0. 7 0.一3 1-1 7- 一 5因而f1 1 = max' q11 ,q2 1 二 max6, 46d11 = 1f1 2 = max' q12 ,q2 2 ：二 max-3,-5： =-3 d1 2= 1dn i =第n阶段系统处于状态i的最优决策f2 121 1(1) +送 P1jf1( J),j22 2 q 1'Pij fi jj= j一 6 - 6 11 = max<6+0.5 0.5】|, 4 +0.8 0.2】|>I'