设备更新问题.doc

设备更新问题许多公司和顾客面临决定在他们应该使用现有设备多长时间才更换一台新设备。这类问题被称做“设备更新问题”而且常常利用动态规划求解这个问题。举例1某家汽车修理厂总要用到一台发动机分析仪。新分析仪的成本为1000元。分析仪使用第i年的维修费如下，分析仪可以使用1，2，或3年，在使用i年之后可以更换一台新的分析仪。如果更换使用了i年的分析仪，可以得到残值， 。已知必须在现在购买新分析仪(时间0)，修理厂决定极小化在今后5年内的更新交换策略。举例2一家汽车公司有一种型号的汽车，每辆汽车的年均利润函数与年均维修费用，购买同种型号汽车每辆购价为20万元。如果出售不同使用年龄汽车的价格如表。该公司年初有一辆新汽车，试计划今后4年盈利最大的更新计划。解：l 阶段数n = 4l 状态：以汽车的役龄为状态变量，表示在第k阶段汽车使用年限为t。l 决策变量：继续使用，更新汽车l 状态转移方程式ll 设=在第k年开始使用役龄为t年的汽车，从第k年到第n年的最佳收入役龄(年)0123利润函数(万元) 201817.515维修费用(万元) 22.546出售价格(万元) 171615.515购买价格(万元)20202020k = 4更新续用120-2+16-20=1418-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 = 3更新续用120-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 = 2更新续用120-2+16-20+29.5=43.518-2.5+29=44.5*44.502k = 1更新续用020-2+44.5=62.5*62.501应用动态规划的难点l 状态空间大到利用动态规划求解要求大量的计算时间。l 不可加的递推：不代表在当前阶段到将来的成本或利润之和。举例： 王先生要从城市1开车到城市10去，他关心的不是最短距离，而是极小化在开车过程中的海拔高度(用高出海平面的千英尺)。是从城市i到城市j所遇到的最大高度。定义代表从城市出发所遇到最小的最大高度，有如下递推公式最优路线是，旅行中所遇到的最大高度是8000英尺 马氏决策规则随机系统的多阶段决策：马尔柯夫决策规则确定型：随机型：一、马尔柯夫过程动态随机系统的特征，系统的状态转移规律具有无后效性：l 已知当前状态，采取的决策后，下一阶段的状态的概率分布是已知的。l 与系统以前的发展历史无关。称具有这种系统状态的转移规律具有马尔科夫特征状态和时间都是离散的马氏过程l 时间间隔为1个单位l 系统的状态为有限个Ntt +1状态转移矩阵ij二、赋值马氏过程1. 具有N个状态的马氏过程2. 任意时刻从ij获得相应的收益记作，报酬矩阵 3. 经过一定阶段运行后的总报酬l =从i出发作一次转移的期望报酬 一次转移的期望报酬向量。l =从i出发作n次转移的期望报酬已知，定义乘法 举例：马氏决策规则在赋值马氏过程中，若在某个状态选用不同的决策能够改变相应的状态转移矩阵和赋值矩阵，则产生动态随机系统求解最优问题。有限阶段的模型的求解方法值迭代法，总期望报酬值最大化举例： 1. 决策1不登广告 2. 决策2登广告 问题在若干月内采用什么决策才能使其总期望报酬为最大？设n表示系统的阶段数=当前状态为i，下一步采用决策d转移到状态j的概率=表示系统初始状态为，经过个阶段采用最