运筹学 第3版 课件 08 动态规划

第8章动态规划第8章动态规划§8-1多阶段决策问题

§8-2动态规划的最优性原理§8-3动态规划的应用分析动态规划概述※动态规划是运筹学的一个重要分支，也是规划论的一个重要组成部分。※动态规划是研究多阶段决策过程的最优化问题的方法。

※动态规划问题1951年由贝尔曼提出※动态规划问题必须具体问题具体对待，除了要对基本概念和方法正确理解之外，还要以丰富的想象力去建立模型，用创造性的技巧去求解。

※动态规划方法在许多领域都可应用，可以取得比线性规划更有效的效果。投资问题、库存问题、生产计划、资源分配、设备更新、最优搜索、马尔可夫决策过程，以及最优控制和自适应控制等问题，均可用动态规划方法来处理。§8-1多阶段决策问题例8-1最短路问题。图8-1中给出了从A铺设到E的石油管线网。图中A、B1、B2、B3、C1、C2、C3、D1、D2、D3、E都是途径的市镇的名称，路径上的数字则是该段路径的长度。现在的问题是要求出如何铺设石油管线使A到E的路线最短。

阶段1阶段2阶段3阶段4图8-12AB1B2B3C1C2C3D1D2E5756324515413633343例8-2机器负荷分配问题。

某种机器可以在高低两种不同的负荷下进行生产。设开始有完好的机器s台，要求制定一个五年计划，在每年开始决定如何重新分配完好机器在两种不同负荷下工作的数量，以使五年所生产的产品总产量最高。

机器数量年产量年完好率年终完好机器数高负荷u1g=g(u1)a低负荷u2h=h(u2)bau1bu2§8-1多阶段决策问题1决策状态……图8-22决策状态状态状态n决策状态前述例题在每一阶段都需要问（1）现在的条件是什么？ 状态（2）现在该怎么办？ 决策多阶段决策问题：这样一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。 动态规划方法就是一种从多种可能的过程活动路线中找出一条最优路线的方法。§8-1多阶段决策问题课下学习检测什么是多阶段决策问题？动态规划问题能解决具有阶段性决策特点的问题，可以是时间上的阶段性，也可以是空间上的阶段性。§8-2动态规划的最优性原理一、动态规划的基本概念二、动态规划最优性原理三、动态规划基本方程四、动态规划的基本思想五、构成动态规划模型的条件2、状态：表示每个阶段开始时所面临的自然状态或客观条件，既是该段某支路的始点，同时也是前一阶段某支路的终点。

状态变量：以sk表示在第k阶段的某个状态。可达状态集合：第k阶段所有状态的集合称之为可达状态集合，记之为Sk

其中：表示第k阶段的第i个状态。

例8-2中，Sk＝{0~ck

}，ck为第k阶段初可能拥有的完好机器数的最大值状态变量的选取必须满足无后效性无后效性：如果给定了某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。 状态的这个性质意味着过程的过去历史只能通过当前的状态去影响它的未来的发展。例8-1中，返回1、阶段：指一个问题需要作出决策的步数，一般根据时间或空间的特征划分阶段。阶段变量：以k表示假设阶段数为n，一般会将阶段表示为：k=n,n-1,…,1一、动态规划的基本概念允许决策集合：决策变量的取值范围，记为Dk(sk)，表示第k阶段初状态为sk时的允许决策集合。决策变量：以uk(sk)表示第k阶段初状态变量为sk时的决策变量，是状态变量的函数。例：例8-1中，k=2时，若s2=B2，则从B2出发有三种选择，如果选择了B2→C1，则例：例8-1中，如果s2=B2，则从B2出发有三种选择，即允许决策集合为3、决策：决策就是某阶段初从给定的状态出发，决策者从面临的若干种不同方案中作出的选择。

右边两个式子的区别？一、动态规划的基本概念子策略：由第k段开始到终点为止的过程称为原过程的后部子过程，简称k子过程。其决策函数序列称为k子过程策略，简称子策略。

允许策略集合：可供选择的策略范围，这个范围称为允许策略集合。用P表示。

最优策略：允许策略集合中达到最优效果的策略称为最优策略。

例：A→B1→C1→D1→E为一个策略，

C1→D1→E为一个子策略

例：允许决策集合为所有从A到E的路，

最优策略即为最短路。

例：即：A→B1→C1→D1→E4、策略：由过程的第1阶段开始到其终点为止的过程称为问题的全过程。在此全过程中由每一阶段的决策ui(si)（i=1,2,…,n）组成的决策函数序列就称为全过程策略，简称为策略，记为p1,n

。一、动态规划的基本概念给定第k阶段状态变量sk的值后，如果这一阶段的决策变量uk的值一旦确定，则第k+1阶段的状态变量sk+1也就完全确定，即sk+1的值随sk和uk的值的变化而变化，可以把这一关系看成sk+1与(sk

,uk)的确定的对应关系，通常用sk+1=Tk(sk

,uk

)表示。例：对于最短路问题，sk+1=uk(sk

)

,如：s3=u2(B2

)

例如，在例8-2中，设sk是第k年初完好的机器数量，uk为该年度中分配到高负荷下生产的机器数量，这时分配在低负荷下生产的机器数量为sk－uk，所以在第k+1年初完好的机器数量为：

2阶段1AB1B2B3C1C2C3D1D2E575632451541363334阶段2阶段3阶段435、状态转移方程：从第k阶段到第k+1阶段的状态转移规律，称之为状态转移方程。一、动态规划的基本概念6、指标函数和最优值函数

（1）指标函数：用来衡量所实现过程优劣的一种数量指标，它是定义在全过程和所有后部子过程上的确定数量函数，常用Vk,n表示为：常见的指标函数的形式:

※过程和他的任意子过程的指标是它所包含的各阶段指标的和。

其中，vj(sj,uj)是阶段指标。例如：例8-2中阶段指标为每段路的路长，状态为B2，策略为B2→C1→D1→E，此时指标函数值为：3＋1＋3＝7（2）最优值函数：指标函数的最优值，记为fk(sk)。

※过程和他的任意子过程的指标是它所包含的各阶段指标的积。

一、动态规划的基本概念区分三个概念（1）指标函数（2）阶段指标：vj(sj,uj)

（3）最优值函数：指标函数的最优值，记为fk(sk)。

一、动态规划的基本概念二、动态规划的最优性原理——贝尔曼（R.Bellman）原理作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对于由前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。换句话说，一个最优策略的子策略总是最优的。

例如：A→B3→C2→D2→E是一个从A到E的最短路，则C2→D2→E必是C2到E的最短路。

另一方面，无论前面是如何到达C2的，则C2→D2→E必是C2到E的最短路。最优性原理与无后效性是一致的。

AB3C2D2ED1动态规划的基本方法是分级决策方法与最优性原理的综合应用

1、动态规划的基本方法：

（1）逆序解法：从过程的最后一个阶段开始逆向求解到第一个阶段为止。

123456始点终点动态规划的寻优途径行进方向图8-3（2）顺序解法：过程的第一阶段开始一直求解到最后一个阶段为止。

123456始点终点动态规划的寻优途径行进方向图8-4三、动态规划基本方程2阶段1AB1B2B3C1C2C3D1D2E575632451541363334阶段2阶段3阶段4图8-53034476117811逆序解法123456始点终点动态规划的寻优途径行进方向图8-3三、动态规划基本方程2阶段1AB1B2B3C1C2C3D1D2E575632451541363334阶段2阶段3阶段4图8-6311978482530顺序解法123456始点终点动态规划的寻优途径行进方向图8-4三、动态规划基本方程2、动态规划的基本方程

逆序解法的基本方程为：

顺序解法的基本方程为：

逆序解法：其初始条件必须是确定的。顺序解法：其终点条件必须是确定的。当两者均确定时可以任选一种解法。三、动态规划基本方程2AB1B2B3C1C2C3D1D2E57563245154136333431178113+04+0EED1D21+34+4C1C2C3D1D26+33+43+33+47+45+7B1B2B3C1C2C33+42+75+41+76+64+65+62+115+711B3AB1B2B33+8k=4:S4=｛D1,D2｝k=3:S3=｛C1,C2,C3｝k=2:S2=｛B1,B2,B3｝，最优值函数（略）k=1:S1=｛A｝，最优值函数（略）034476C1C1C2D1D2D11178476f5(S5)=0E341、动态规划方法的关键：

正确写出基本的递推关系式和恰当的边界条件。要做到这一点,首先必须将问题分成几个相互连系的阶段，正确选取状态变量和决策变量以及定义最优值函数。从而把一个大问题转化为一组相互联系的子问题，在每个子问题的求解过程中均要用到它的一个后部子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是原问题的最优解。

2阶段1AB1B2B3C1C2C3D1D2E575632451541363334阶段2阶段3阶段43四、动态规划的基本思想2、分析动态规划基本方程：

当一个决策确定以后，它有两方面的影响：（1）直接影响这个阶段的阶段指标vk

(sk,

uk)。（2）影响后面第k+1阶段的初始状态，因而也影响到后面第k+1阶段到终点的最优值函数。故最优策略的选取则是综合这两方面统一考虑的结果而决定的。∴在多阶段决策过程中，动态规划方法是既把当前一阶段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。四、动态规划的基本思想2阶段1AB1B2B3C1C2C3D1D2E575632451541363334阶段2阶段3阶段4图8-530344761178113、每阶段的最优值函数都是该阶段状态变量的函数，因此只要初始状态是已知的，就可以通过逐次变换得到最优策略。四、动态规划的基本思想五、构成动态规划模型的条件1.正确划分阶段：将实际问题恰当划分为若干个阶段。2.正确选择状态变量sk及可达状态集合Sk，使状态变量既能描述过程的状态，又要满足无后效性。3.确定决策变量uk及每段的允许决策集合Dk

(sk)={uk}4.写出状态转移方程：sk＋1=Tk(sk,uk)

5.写出指标函数在很多情况下需要先写出阶段指标6.写出动态规划基本方程

若以fk(sk)表示k子策略的最优指标函数值，则动态规划逆序解法的基本方程§8-3动态规划的应用分析（Ⅰ）资源分配问题（Ⅱ）系统可靠性问题（Ⅲ）生产与存储问题（Ⅳ）机器负荷分配问题（Ⅴ）一般规划的动态规划解法（Ⅵ）设备更新问题（Ⅰ）资源分配问题1.问题的提出：设有某种原材料，总量为a，用于生产n种产品。若分配数量为xi的原材料生产第i

种产品，其效益为gi(xi)。问应如何分配，才能使生产n种产品的总收入最大?2.用动态规划方法求解

（1）阶段：通常以把资源分配给一个或几个使用者的过程作为一个阶段；

（2）状态变量sk：表示当前可用于分配的资源总量，即用于生产第k种产品至第n种产品的原材料数量；

（3）决策变量uk：表示分配给第k种产品的原材料数量uk

=xk

；

（4）状态转移方程为：

（5）允许决策集合：

（6）最优值函数：fk(sk)表示以数量为sk的原材料分配给第k种产品至第n种产品所得的最大总收入。

则动态规划基本方程为：

（Ⅰ）资源分配问题aksknxk（Ⅰ）资源分配问题例8-3某公司打算在甲、乙、丙三个地区建立5个产品分销点，根据各地区的地理位置和人文环境，在不同地区建立不同数目的分销点，会取得不同的盈利，其预测数据见表8-1，试决策在三个地区分别建立的分销点的个数，以使公司盈利最大。表8-1地区分销点数甲乙丙000013542710639111141211125131112解：（1）阶段变量k表示不同的地区甲、乙、丙，k=1，2，3（2）状态变量sk

表示从第k地区到最后一个地区还可以建立的分销点数；（3）决策变量uk

表示在第k地区建立的分销点数；（4）状态转移方程为：允许决策集合：（5）fk

(sk

)表示在第k地区到最后一个地区建sk个分销点所能获得的最大盈利。则动态规划基本方程为：其中，vk

(sk

,

uk

)表示在第k地区建uk个分销点所能获得的盈利。（Ⅰ）资源分配问题表8-3：k=2表8-1地区分销点数甲乙丙000013542710639111141211125131112表8-2：k=304611121204611121201234500+4=40+6=60+11=110+12=120+12=125+0=55+4=95+6=115+11=165+12=1710+0=1010+4=1410+6=1610+11=2111+0=1111+4=1511+6=1711+0=1111+4=1511+0=11005110214216211,22012345012345012345012345表8-4：k=1表8-3：k=2000151210231424161,25212然后按计算表格的顺序反推算，可知最优的分销点分配建设方案有两个：000141262311341245125表8-2：k=3表8-1地区分销点数甲乙丙000013542710639111141211125131112（1）即甲—0；乙—2；丙—3（2）即甲—2；乙—2；丙—10+21=213+16=197+14=219+10=1912+5=1713+0=13210,20123455最大盈利：f1（s1）=21增拨经费/万元小组12300.400.600.8010.200.400.5020.150.200.30(II）系统可靠性问题例8-4

某科研项目由三个小组用不同的手段分别研究，他们失败的概率分别为0.40，0.60，0.80。为了减少三个小组都失败的可能性，现决定给三个小组增拨2万元经费，各小组增拨经费后失败的概率如下表所示。问如何分配新增的科研费用才能使三个小组都失败的概率最小？解：（1）阶段变量k，每个小组为一个阶段，k=1，2，3（2）状态变量sk

表示可以分配给第k个小组到3个小组的经费数；（3）决策变量uk

表示分配给第k小组的经费数；（4）状态转移方程为：允许决策集合：（5）fk

(sk

)表示当第k阶段状态为sk时从k阶段到3阶段都失败的概率最小。则动态规划基本方程为：其中，vk

(sk

,

uk

)表示阶段k分配经费uk后失败的概率。表8-11表8-14：k=2表8-12表8-13：k=30.80.500.300.6×0.80.4800.3000.162012012012012增拨经费/万元小组12300.400.600.8010.200.400.5020.150.200.300.800.500.300120.6×0.50.6×0.30.4×0.80.4×0.50.2×0.8表8-15：k=10.06101220.4×0.160.2×0.30.15×0.48然后按计算表格的顺序反推算，可知最优解为：u*=（1，0，1），最小失败概率为f1(s1)=0.06

例8-5某工厂要对某种产品制订今后四个时期的生产计划，根据市场预测，在今后四个时期内，该种产品的市场需求量如表8-5所示。每批固定成本为3千元，不生产为0，每单位成本为1千元。每个时期生产批量不超过6，最大库存量为5。时期末未售出的产品，每单位需要支付存贮费用0.5千元，初始库存为0，计划期末库存为0，问应如何安排生产，使得在满足市场需求的前提下，该厂四个时期的总成本最小。

（Ⅲ）生产与存储问题时期(k)IIIIIIIV需求量(dk)2324表8-5时期(k)IIIIIIIV需求量(dk)2324（2）状态变量sk

：第k阶段开始时的库存量；（3）决策变量uk

：第k阶段（时期）的生产量；（4）状态转移方程为：dk为第k阶段（时期）的市场需求量。已知：s1=0，s5=0，可达状态集合储存量不能超过第k期至期末的所有需求量之和储存量不能超过从第一期开始到第k-1期的最大产量减去所有需求量之和解：（1）阶段：划分为为4个阶段，k=1，2，3，4最大存储量为5，不会有负库存（Ⅲ）生产与存储问题时期(k)IIIIIIIV需求量(dk)2324（2）状态变量sk

：第k阶段开始时的库存量；（3）决策变量uk

：第k阶段（时期）的生产量；（4）状态转移方程为：dk为第k阶段（时期）的市场需求量。因为库存量大于等于0，所以：又因为解：（1）阶段：划分为为4个阶段，k=1，2，3，4允许决策集合因为：s5=0，所以（Ⅲ）生产与存储问题（6）fk(sk)为当第k阶段的库存量为sk时，从k段到第n段（最后一个时期）最低的生产与存储费用。则此问题的动态规划递推关系式为：

逆序法迭代求解过程如下：

（5）ck(

sk,uk)+hk(sk+uk

－dk

)为第k

阶段的阶段指标，代表这一时期的生产与库存费用，它是sk

、uk的函数。

生产费用存储费用（Ⅲ）生产与存储问题表8-6：k=4S4={0,1,2,3,4}f4(s4)=min{c4(

s4,u4)+h4(s4+u4

－d4

)+f5(s5)}u4s4c4(

s4,u4)+h4(s4+u4

－d4

)+f5(s5)f4(s4)0123401234表8-5时期(k)需求量(dk)I2II3III2IV47+0+06+0+05+0+04+0+00+0+07654043210第39页第40页（Ⅲ）生产与存储问题u3s3c3(

s3,u3)+h3(s3+u3

－d3)+f4(s4)f3(s3)0123456012345表8-5时期(k)需求量(dk)I2II3III2IV40+0+70+0.5+60+1+50+1.5+44+0+74+0.5+64+1+54+1.5+44+2+05+0+75+0.5+65+1+55+1.5+45+2+06+0.5+66+1+56+1.5+46+2+07+1+57+1.5+47+2+08+1.5+48+2+09+2+0111076.565.5650000074163252341400表8-7：k=3S3={0,1,2,3,4,5}f3(s3)=min{c3(

s3,u3)+h3(s3+u3

－d3

)+f4(s4)}（Ⅲ）生产与存储问题第39页第40页u2s2c2(

s2,u2)+h2(s2+u2

－d2

)+f3(s3)f2(s2)012345601234表8-7：k=30116110527036.5046055.50表8-5时期(k)需求量(dk)I2II3III2IV40+0+110+0.5+104+0+114+0.5+104+1+75+0+115+0.5+105+1+75+1.5+6.56+0+116+0.5+106+1+76+1.5+6.56+2+67+0.5+107+1+77+1.5+6.57+2+67+2.5+5.58+1+78+1.5+6.58+2+68+2.5+5.59+1.5+6.59+2+69+2.5+5.51615141110.554300表8-8：k=2S2={0,1,2,3,4}f2(s2)=min{c2(

s2,u2)+h2(s2+u2－d2

)+f3(s3)}（Ⅲ）生产与存储问题第39页第40页表8-8：k=20165115421433110410.50u1s1c1(

s1,u1)+h1(s1+u1

－d1

)+f2(s2)f1(s1)234560表8-5时期(k)需求量(dk)I2II3III2IV45+0+166+0.5+157+1+148+1.5+119+2+10.520.55表8-9：k=1S1={0}f1(s1)=min{c1(

s1,u1)+h1(s1+u1－d1

)+f2(s2)}（Ⅲ）生产与存储问题第39页第40页表8-8：k=20165115421433110410.50表8-9：k=1020.55表8-7：k=30116110527036.5046055.50然后按计算表格的顺序反推算：

表8-6：k=4074163252341400表8-5时期(k)需求量(dk)I2II3III2IV4最优决策为：最低成本为：解：（1）设阶段数为k，k表示年度，k=1,2,3,4,5。（2）状态变量sk

：第k年初拥有的完好机器数量。（3）决策变量uk

：第k年度中分配在高负荷下生产的设备数量，于是sk－uk为该年中在低负荷下生产的机器数量。（注：sk和uk均取为连续变量）（4）状态转移方程为：k段允许决策集合为（5）设vk

(sk，uk

)为第k年度的产量（阶段指标），则（6）fk

(sk

)表示第k年状态为sk时，从第k年开始到第5年结束时所生产的产品总产量的最大值。则有递推关系式：例8-6机器负荷分配问题，高负荷下的完好率a=0.7，低负荷下的完好率b=0.9，高负荷下的产量8件/台，低负荷下的产量5件/台，年限n=5。且初始完好机器数s1=1000台，要求安排好这5年的生产计划，使产品总产量最高。（IV）机器负荷分配问题从第5年开始，逆序计算如下：

k=5时因f5是u5的线性单调增函数，故得最大解u5*=s5，相应的有f5(s5)=8s5。

k=4时

故得最大解u4*=s4，相应的有f4(s4)=13.6s4。

（IV）机器负荷分配问题故得最大解u3*=s3，相应的有f3(s3)=17.5s3。

k＝3时（IV）机器负荷分配问题故得最大解u2*=0，相应的有f2(s2)=20.8s2。

故得最大解u1*=0。

最优值为f1(s1)=23720∴最优策略为u1*=0，u2*=0，u3*=s3，u4*=s4，u5*=s5。

k＝2时k＝1时（IV）机器负荷分配问题最优策略为u1*=0，u2*=0，u3*=s3，u4*=s4，u5*=s5。

u1*=0s1=1000u2*=0u3*=810u4*=567u5*=397最优策略为u1*=0，u2*=0，u3*=810，u4*=567，u5*=397最优值为f1(s1)=23720（IV）机器负荷分配问题这里说的一般数学规划包括线性规划、非线性规划（整数规划类同地可以用离散动态规划方法求解）等，尽管这些规划模型各自的求解方法有很大差别，但用动态规划的方法求解时，方法和步骤基本上一致，都可以看作为一般的资源分配问题来处理。

一般资源分配问题静态规划方程为：

（1）通常把决定每一个变量的取值的过程看作为一个阶段，变量的个数就是阶段数；（2）约束条件的右端项表明可分配的资源数，用状态变量来描述；（3）而约束条件的个数则表明状态的维数；（4）状态转移方程为sk+1=sk－uk，其中sk为状态变量，uk为决策变量。（5）每个变量的取值对目标函数的影响取作为阶段指标，V一般规划的动态规划解法例8-7求下列非线性规划的最优值。

解：（1）阶段：有三个变量，划分为三个阶段，k=1，2，3（2）状态变量sk：表示自k阶段至3阶段还可以分配的数值，其中s1

=c

（3）决策变量为xk（4）状态转移方程:sk+1=sk

－xk

（5）fk

(

sk

)表示第k阶段的初始状态为sk，从k阶段到第三阶段的最大值。则有递推方程为：V一般规划的动态规划解法k=3：k=2：

得到：

为极大值点

V一般规划的动态规划解法当

时,

所以：当

时，

又因为

，所以

V一般规划的动态规划解法V一般规划的动态规划解法k=1：k=2：

k=3：

所以最优解为:

最大值为:

V一般规划的动态规划解法补充作业V一般规划的动态规划解法一台设备在使用过程中要创造收益，支付维修费用，设备更新时还要支付新旧设备的价值差额部分的费用。那么一台设备在某一年更新，还是继续使用，就要从上面三方面的因素综合考虑，并且要从若干年总的收益效果来决定。

1、变量说明：

sk：表示设备已经使用过的年数或役龄；

Ik(sk)：表示在第k年已经使用了sk年的设备再使用一年的收入，它随sk而减少；

Ok(sk)：表示在第k年已经使用了sk年的设备每使用一年的运行费用（维修费用），它随sk而增加；

Ck(sk)：表示在第k年已经使用了sk年的设备更新时所需支付的新旧设备的价额差值，它随sk而增加；

T：表示在第一年开始时，正在使用的设备的役龄；n：表示计划的年限总数；

α：折扣因子（0≤α≤1），表示1年以后的单位收入的价值视为现年的α单位。VI设备更新问题2、用动态规划方法求解：

规定某一年为第一年，一直到n年为止，考虑这n年内的总的情况。（1）阶段k：表示计划年限；（2）状态变量sk：第k年设备的役龄；=1，2，3，……，k-1，k+T-1（3）决策变量uk：（5）fk(sk)：表示在第k年役龄为sk的设备，从第k年演变到n年为止所获得的最佳收入。若在第k年更换设备，要满足递推式：若在第k年不更新，继续使用，则有递推关系：（4）状态转移方程：T=5第五年初设备可能的使用年限为：1，2，3，4，9VI设备更新问题例8-8

设n=5，α＝1，T=0，有关数据如下表，试制定五年中的设备更新策略，使在五年中的总收入最大。

表8-10役龄项目012345收入Ik(t)：54.543.7532.5运行费用Ok(t)：0.511.522.53更新费用Ck(t)：0.51.52.22.533.5k=5时：状态sk=1，2，3，4（由s5=1，2，3，…k-1，k+T－1得到）u5s5I5(

s5

)－O5(s5)+f6(s6)I5(

0

)－O5(0)－C(s5)+f6(s6)f5(s5)u5(s5)继续使用(K)更新(R)14.5－1+0=3.55－0.5－1.5+0=33.5K24－1.5+0=2.55－0.5－2.2+0=2.32.5K33.75－2+0=1.755－0.5－2.5+0=22R43－2.5+0=0.55－0.5－3+0=1.51.5R返回k=4时：

状态：s4=1，2，3（由s4=1，2，3，…k-1，k+T－1得到）

役龄项目012345收入Ik(t)：54.543.7532.5运行费用Ok(t)：0.511.522.53更新费用Ck(t)：0.51.52.22.533.5u4s4I4(

s4

)－O4(s4)+f5(s5)I4(

0

)－O4(0)－C(s4)+f5(s5)f4(s4)u4(s4)继续使用(K)更新(R)14.5－1+2.5=65－0.5－1.5+3.5=6.56.5R24－1.5+2=4.55－0.5－2.2+3.5=5.85.8R33.75－2+1.5=3.255－0.5－2.5+3.5=5.55.5RVI设备更新问题u5s5f5(s5)u5(s5)13.5K22.5K32R41.5Rk=3时：

状态：s3=1，2（由s3=1，2，3，…k-1，k+T－1得到）

u3s3I3(

s3

)－O3(s3)+f4(s4)I3(

0

)－O3(0)－C(s3)+f4(s4)f3(s3)u3(s3)继续使用(K)更新(R)14.5－1+5.8=9.35－0.5－1.5+6.5=9.59.5R24－1.5+5.5=85－0.5－2.2+6.5=8.88.8RVI设备更新问题役龄项目012345收入Ik(t)：54.543.7532.5运行费用Ok(t)：0.511.522.53更新费用Ck(t)：0.51.52.22.533.5u4s4f4(s4)u4(s4)16.5R25.8R35.5Rk=1时：

状态：s1=0（由题知第一年初购买一个新设备）

u1s1I1(

s1

)－O1