教学材料《运筹学》-第7章

第7章动态规划学习目标理解动态规划的基本知识，掌握用动态规划的思想建立多阶段决策模型。能够用动态规划理论解决诸如最短路径问题、资源分配问题、设备更新等问题。上一页下一页返回第7章动态规划关键词汇动态规划(DynamicProgramming)多阶段决策过程(Multiple-stageDecisionProcessK-后部子过程(k-stepSub-process)贝尔曼最优性原理(BellmanPrincipleofOptimality)阶段(Stage)状态变量(StateVariable)可能状态集合(PossibleStateSet)决策变量(DecisionVariable)允许决策集合(PermissibleDecisionSet)上一页下一页返回第7章动态规划策略(Strategy)最优策略(OptimalStrategy)状态转移方程(StateTransitionEquation)阶段指标(StageIndicatorFunction)过程指标函数(ProcessIndicatorFunction)基本方程(FundamentalEquation)递推公式(RecurrenceEquation)边界条件(BoundaryCondition)离散型变量(DiscreteVariable)连续型变量(ContinuousVariable)上一页下一页返回第7章动态规划案例导引例一某运输公司拟将一大型设备从下列交通网络的A点运输到F点，试求从A到F的最短路径。例二某企业生产某种产品，每月月初按订货单发货，生产的产品随时入库，由于空间的限制，仓库最多能够贮存产品90000件。在上半年(1~6月)其生产成本(万元/千件)和产品订单的需求数量情况如表7-1所示。已知上一年底库存量为40千件，要求6月底库存量仍能够保持40千件。问:如何安排这6个月的生产量，既能满足各月的订单需求，同时使生产成本最低。上一页下一页返回第7章动态规划案例思考题:(1)分析上面例题的共同特点是什么?提炼问题特征。思考实际中有哪些类似的情况。

(2)对于这类问题，我们关心哪些事情?难点在哪里?在实践中，我们可以进一步做哪些有益的工作?上一页返回下一页7.1多阶段决策问题

动态规划是解决多阶段决策过程最优化问题的一种方法，由美国数学家R.Bellman等人在20世纪50年代提出。动态规划可以用于解决诸如最优路径、资源分配(包括投资)、生产计划与库存、装载、排序等现代企业决策问题。动态规划模型根据状态变量的数量和取值性质可分为:(1)离散确定型。

(2)离散随机型。

(3)连续确定型。

(4)连续随机型。

(5)低维—一维。

(6)高维。下一页返回上一页7.1多阶段决策问题

多阶段决策是一类特殊活动过程，它们可以按“时序”分解成若干相互联系的阶段—“时段”，在每一个时段均需作出决策，前级决策影响后级决策，构成决策序列，故属于序贯决策问题。多阶段决策过程最优化的目标是要使整个活动的总体效果最优，由于各决策阶段的有机结合，本阶段决策影响下一阶段决策以至影响总体效果，所以决策人在每阶段决策中不应该仅考虑本阶段实现最优决策，更应重点分析本阶段决策对全局的影响，从而作出全局最优决策。动态规划方法的“动态”体现在动态规划与“时序”关系的紧密相连上，所研究的问题随“时间”(或“空间”)发展而形成序贯决策，即为“动态”。上一页下一页返回7.1多阶段决策问题动态规划方法也可被用来处理与时间无直接关系的静态问题，即人为引入“时段”，把问题视为多阶段动态决策过程即可。例7.1投资问题。一公司有三个工厂，每个工厂均需扩建，公司用于扩建的资金共计700万元，各厂的投资方案及扩建后的预期收益如表7-2所示。现公司要确定对各厂的投资额度，以使公司总利润最大。分析此问题中，每个工厂均有几种不同的投资方案，所以要对每一个工厂作出一种决策，共需决策3次，同时在阶段决策时，必须遵循投资总额不超过700万元的约束，如把每个厂视为一个阶段，则此问题为一个多阶段决策问题。上一页下一页返回7.1多阶段决策问题例7.2背包问题。有四种货物准备装到一艘船上，第i(i=1,2,3,4)种货物的每箱重量为wi，其价值为vi，如表7-3所示。假定此船的载重量为10，现需确定四种货物各装几箱可使装载的总价值最大。分析此问题中，因为要对每一种货物确定装载的箱数，即作出一种决策，共需作出四次决策，同时货物的总重量不能超过10，如把每一种货物看成一个阶段，则可视此问题为多阶段决策问题。例7.3最优路径问题。设要从A到F铺设管道，有多种铺设路径方案，如图7-2所示。图中两点连线上的数字表示管道距离，问选择怎样的路径可使线路最短。上一页下一页返回7.1多阶段决策问题分析此问题中，从A到B1，B2中的哪一点需要作出决策，从B1，B2中的某点到C1，C2，C3，C4中的哪一点也要作出决策，依此类推。故从A=>F共需作出五次决策。可以把整个路线分成A=>B=>C=>D=>E=>F五个阶段，此问题为多阶段决策问题。思考题(1)可用动态规划求解的多阶段决策过程有什么特点?(2)求解多阶段决策问题时，动态规划方法的分析思路是怎样的?上一页返回下一页7.2动态规划的基本概念和基本原理7.2.1动态规划的基本概念

1)阶段对多阶段决策问题，按问题的特点可将其划分成若干互相联系的阶段，描述阶段的变量为阶段变量，用h表示。例3中，阶段为问题所处的地段，从A=>F共可划分五个阶段，故k=1，2，3，4，5。

2)状态状态为各阶段开始时问题的自然状况。描述各阶段状态的变量称为状态变量，通常用sk表示第k阶段的某一具体状态，而用sk表示第k阶段的状态集合。如例3中，第一阶段状态为A，第二阶段则有两个状态B1，B2，B3,…即下一页返回上一页7.2动态规划的基本概念和基本原理注意:对于动态规划问题，其状态参量必须满足两个条件:(1)能描述问题的过程。就是当各阶段的状态确定后，整个问题的过程即被确定。上一页下一页返回7.2动态规划的基本概念和基本原理(2)满足无后效性(马尔可夫性)。它是指如某阶段的状态给定后，则在此阶段以后过程的发展不受这一阶段以前各状态的影响，而只受当前状态的影响。即过程的历史只能通过当前状态去影响未来的发展，当前状态是以往历史的一个总结。

3)决策决策表示当过程处于某一阶段的某一状态时，为确定下一阶段的某一状态所作出的决定或选择。描述决策的变量称为决策变量。通常用uk(sk)表示第k阶段，当状态为sk时所作出的决策。用Dk(sk)表示第k阶段，当状态为sk时所有可行决策构成的决策集合，uk(sk)∈Dk(sk)。上一页下一页返回7.2动态规划的基本概念和基本原理如例3中，从第二阶段的状态B1出发，可选择的下一阶段的可行决策为C1,C2,C3

，故如选择具体的决策方案可表示为

4)策略对于n阶段决策问题，从初始状态出发到终段状态的全过程中，由每阶段的决策uk(sk)(k=1,2,…，n)，所构成的决策序列称为一个整体策略—策略，记为上一页下一页返回7.2动态规划的基本概念和基本原理称下式所描述的决策序列为后部k段子策略:称下式所描述的决策序列为前部k段子策略:

在实际问题中，可供选择的策略范围称为允许策略集合，用P(或P1，n)表示。策略集合中使问题达到最优效果的策略称为最优策略。例3中，任一一条从A=>F的可行线路均构成一个策略。如5)状态转移方程描述相邻两阶段状态与决策相互关系的方程为状态转移方程。对于不同的问题，方程的形式不同。上一页下一页返回7.2动态规划的基本概念和基本原理状态转移方程的一般形式为它描述了由第k阶段到k+1阶段的状态转移规律，Tk称为状态转移函数。注意:采用顺序计算时，状态转移方程一般描述为: 。采用逆序计算时，状态转移方程一般描述为: 。如例3:上一页下一页返回7.2动态规划的基本概念和基本原理6)指标函数用于衡量所选定策略优劣的数量指标称为指标函数。在衡量问题的优劣时必须有数量指标，而该数量指标是定义在问题策略或子策略上的函数，通常用Vk，n表示，即对于动态规划模型来说，指标函数应满足可分离性，即可描述成sk，uk(sk)，Vk+1，n的函数(具有涕推性)，记为:注意以下几个符号含义:(1)V1，n(p1,n(s1))—表示初始状态(第一阶段)为s1，采用策略p1,n(s1)时过程(全过程)的指标函数值。上一页下一页返回7.2动态规划的基本概念和基本原理(2)Vk，n(pk,n(sk))—表示在k阶段，状态为sk

，采用策略pk,n(sk)时后部k段子过程的指标函数值。

(3)V1，k(p1,k(s1))—表示初始状态(第一阶段)为s1，采用策略p1,k(s1)时前部k段子过程的指标函数值。动态规划指标函数的形式一般有如下两种。1)阶段指标和形式。过程或子过程指标为各阶段指标之和其中， 表示第j阶段在状态为sj时作出决策uj的指标，即所谓的阶段指标。上一页下一页返回7.2动态规划的基本概念和基本原理例1、例2、例3中的指标函数均为阶段指标和形式，显然这种形式可以描述成即满足指标函数的可分离性。

(2)阶段指标积形式。此形式即过程或子过程的指标为各阶段指标的积:上一页下一页返回7.2动态规划的基本概念和基本原理亦满足可分离性:

由于指标函数是(子)策略的函数，当采取不同的(子)策略时，就会得到不同的指标函数值，因而必存在一个最优的指标函数值，通常用fk(sk)表示，可描述为注意以下符号含义。①fk(sk)—表示从第左段，状态为sk开始，采用最优后部子策略

pk，n*(sk)到过程终止时的最优指标函数值。上一页下一页返回7.2动态规划的基本概念和基本原理②特别地，当k=1时，f1(s1)—即为从初始状态s1，到全过程结束的整体最优指标函数值。需特别注意的是，当采用顺序计算时，fk(sk)表示的是前部k段最优子策略的最优指标函数值。上一页下一页返回7.2动态规划的基本概念和基本原理7.2.2动态规划的最优性原理

R.Bellman等人在20世纪50年代提出此原理:“作为整个过程的最优策略具有如下性质:无论过去的状态和决策如何，对以前的决策所形成的现在状态而言，余下的诸决策必须构成最优决策。”也就是说，一个最优决策的子策略总是最优的。上一页下一页返回7.2动态规划的基本概念和基本原理7.2.3动态规划的基本方程指标函数为阶段指标和形式的问题，其动态规划方程形式为指标函数为阶段指标积形式的问题，其动态规划方程形式为上一页下一页返回7.2动态规划的基本概念和基本原理7.2.4动态规划问题的基本思想和解题步骤多阶段决策问题的求解过程可以被看成是对若干相互联系的子问题逐个求解的递推过程。

1)动态规划的求解基本思想

(1)正确写出基本递推关系式(基本方程)

首先将问题的过程划分成若干相互联系的阶段，正确选择问题的状态变量和决策变量以及定义指标函数的具体形式。从问题的边界条件开始，逐段递推寻优，在每个子问题的求解中，均利用其前面的子问题的优化结果依次进行，最后一个子问题所得到的最优解就是整个问题的最优解。上一页下一页返回7.2动态规划的基本概念和基本原理(2)在多阶段决策过程中，每阶段决策的选取是从全局来考虑的，故全局最优决策与阶段的最优选择答案一般是不同的。

(3)在求整个问题的最优策略时，初始状态是已知的，而每阶段的决策均是阶段状态的函数，故最优策略所经过的各阶段状态可逐次变换得到，从而确定最优路径。

2)动态规划的解题步骤

(1)建立问题的动态规划模型。划分阶段，选择问题的状态变量、决策变量，列出状态转移方程，描述问题的指标函数，列出动态规划方程。上一页下一页返回7.2动态规划的基本概念和基本原理(2)递推计算:按(1)所列动态规划方程分阶段逐一计算。

(3)以(2)递推计算结果为基础，以状态转移方程为纽带，按与递推计算相反的方向寻找最优策略。思考题

(1)试述动态规划方法的墓本思想、动态规划的墓本方程的结构，并正确写出动态规划墓本方程的关键步骤。

(2)试解释状态、决策、策略、最优策略、状态转移方程、指标函数、最优值函数、边界条件等概念。(3)试述动态规划的“最优化原理”及其与动态规划墓本方程的关系。上一页返回下一页7.3动态规划问题实例7.3.1最短线路问题考虑例7.3，要从A到F铺设管道，有多种铺设路径方案，如图7-1所示。图中两点连线上的数字表示管道距离，问选择怎样的路径可使线路最短。解逆序计算:(1)建立问题的动态规划模型。①阶段:由题意，按地段划分决策阶段，k=1,2,3,4,5。②状态:各阶段开始时问题的自然状态，此问题中为各阶段(地段)的起始位置，用sk表示。③决策:各地段在给定状态下(sk)铺设管路的路径选择，用uk(sk)表示。④状态转移方程:相邻两阶段状态与决策相互关系的方程sk+1=uk(sk)。下一页返回上一页7.3动态规划问题实例⑤指标函数:衡量决策优劣的数量指标，对该问题来说即是铺设管线的距离，指标函数的形式为各阶段管线长度之和—和函数形式。其中， 为各阶段的阶段指标，即路线的长度。⑥动态规划方程:目的是求:上一页下一页返回7.3动态规划问题实例(2)递推计算。当k=5时(第五阶段)，第五阶段的初始状态sk共有两个，即S5=E1，E2或S5={E1，E2}则有:同理上一页下一页返回7.3动态规划问题实例所以当k=4时(第四阶段):第四阶段的初始状态s4共有三个，即:s4=D1,D2，D3或s4={D1,D2，D3}，而每个状态的决策可行集各包含两个元素，即则有上一页下一页返回7.3动态规划问题实例所以同理所以上一页下一页返回7.3动态规划问题实例又所以上一页下一页返回7.3动态规划问题实例

当k=3时(第三阶段):第三阶段的初始状态s3共有四个，即s3=C1，C2，C3,C4或S4={C1，C2，C3,C4}，而每个状态的决策可行集各包含两个元素，即:则最优的后部三段子策略为:上一页下一页返回7.3动态规划问题实例所以 同理 所以上一页下一页返回7.3动态规划问题实例而 所以 上一页下一页返回7.3动态规划问题实例而 所以 上一页下一页返回7.3动态规划问题实例

当k=2时(第二阶段):第二阶段的初始状态s2共有两个，即:s2=B1，B2或s2={B1，B2}，而每个状态的决策可行集各包含三个元素，即则最优的后部四段子策略为上一页下一页返回7.3动态规划问题实例所以 同理 上一页下一页返回7.3动态规划问题实例所以当k=1时(第一阶段):第一阶段的初始状态s1共有一个，即:s1=A或s1={A}，决策可行集包含两个元素，即则最优的后部五段子策略(即全过程策略)为

上一页下一页返回7.3动态规划问题实例所以 (3)寻找最优策略(与计算方向相反)。上一页下一页返回7.3动态规划问题实例即最优策略为 则该问题的最短路径为(如图7-3所示)路径长度为: 。 上一页下一页返回7.3动态规划问题实例7.3.2投资分配问题投资分配问题的一般前提条件是:有数量为a的资金，计划分配给n个项目进行投资，假设

xi=分配给第i个项目的资金数(即为uk)gi(xi)=第i个项目得到数量为xi的资金后所创造的收益值，i=1,2,…,n问题:如何确定各项目的资金分配数额，使得所获得的总收益最大?

分析此类问题可以化为规划问题:上一页下一页返回7.3动态规划问题实例用动态规划思想求解上述问题(顺序计算方法):阶段划分:k=1,2,…，n，以工厂(或项目)为定义阶段的依据;决策变量:xk为投资于第k个项目的资金数(即为uk)状态变量:sk+1为投资于第1到第k个项目(前k个项目)的投资金额。则有上一页下一页返回7.3动态规划问题实例状态转移方程为 注意:

顺序计算时，状态转移方程一般描述为: ，即从第1到第k-1个项目的投资总额取决于第1到第k个项目的投资总额以及投资于第k个项目的投资额。逆序计算时，状态转移方程一般描述为: ，即从第1到第k个项目的投资总额取决于第1到第k-1个项目的投资总额以及投资于第k个项目的投资额。令最优目标函数关 为第k阶段，即从第1阶段(项目)到第k阶段(项目)投资总额为 所获得的最大收益。此时动态规划的基本方程为上一页下一页返回7.3动态规划问题实例故此投资问题就是求解 。注意:资金分配可视为一种连续的数值分布形式，即xk的取值在 之间是连续的，因为求解全过程的连续型最优策略并不容易，所以常把连续变量离散化求解数字解，即把 分成 的大小视具体情况而定。当然，这样处理可能丢失最优解，故一般得到的是原问题的近似解。动态规划的基本方程可写成上一页下一页返回7.3动态规划问题实例

例7.4设共有600万元投资，应用于四个工厂，每个工厂投资后的利润与投资数相关，如表7-4所示。问如何进行投资分配以获取最大收益?解第一阶段(一个工厂)k=1：求f1(s2)，s2=600(投资总额600万元)，有同理，当s2=500，400，300，200，100，0时的最优解值亦可求出。显然，投资第一个工厂所得的利润如表7-5所示。上一页下一页返回7.3动态规划问题实例

第二阶段(两个工厂)k=2:

求f2(s3)，前两个工厂投资总额为600万元，即s3=600。此时需研究第一个和第二个工厂如何进行投资分配，以获取最大收益。由动态方程上一页下一页返回7.3动态规划问题实例最优决策为(400,200)，即对第一个工厂投资400万元，对第二个工厂投资200万元时获利最大为1200万元。类似地有:当前两个工厂共投资500万元时，即s3=500万元时有上一页下一页返回7.3动态规划问题实例最优决策为(300,200)，即对第一个工厂投资300万元，对第二个工厂投资200万元，此时获利最大为1050万元。当前两个工厂共投资400万元时，即s3=400万元时有上一页下一页返回7.3动态规划问题实例最优决策为(200,200)，即对第一个工厂投资200万元，对第二个工厂投资200万元，此时获利最大为900万元。当前两个工厂共投资300万元时，即s3=300万元时有上一页下一页返回7.3动态规划问题实例最优决策为(200,100)，即对第一个工厂投资200万元，对第二个工厂投资100万元，此时获利最大为700万元。当前两个工厂共投资200万元时，即s3=200万元时有上一页下一页返回7.3动态规划问题实例最优决策为(200,0)，即对第一个工厂投资200万元，对第二个工厂不投资，此时获利最大为500万元。当前两个工厂共投资100万元时，即s3=100万元时有上一页下一页返回7.3动态规划问题实例最优决策为(100,0)或(0,100)，即对第一个工厂投资100万元(或不投资)，对第二个工厂不投资(或投资100万元)，此时获利最大为200万元。当前两个工厂共投资0万元时，即s3=0万元时有最优决策为(0,0)，两个工厂均不投资，利润为0。对前两个工厂进行投资时的不同状态的最优决策如表7-6所示。上一页下一页返回7.3动态规划问题实例

第三阶段(三个工厂)k=3:

求关f3(s4)，前三个工厂投资总额为600万元，即s4=600。此时需研究前三个工厂如何进行投资分配，以获取最大收益。由动态方程上一页下一页返回7.3动态规划问题实例最优决策为(200,100,300)，即对第一个工厂投资为200万元，对第二个工厂投资100万元，对第三个工厂投资300万元，此时获利最大为1550万元。类似有:前三个工厂投资总额为500万元，即s4=500时有上一页下一页返回7.3动态规划问题实例最优决策为(200,0,300)，即对第一个工厂投资200万元，对第二个工厂不投资，对第三个工厂投资300万元，此时获利最大为1350万元。前三个工厂投资总额为400万元，即s4=400时有上一页下一页返回7.3动态规划问题实例最优决策为(200,0,200)，即对第一个工厂投资200万元，对第二个工厂不投资，对第三个工厂投资200万元，此时获利最大为1100万元。前三个工厂投资总额为300万元，即s4=300时有上一页下一页返回7.3动态规划问题实例最优决策为(o,o,300，即对第一个工厂、第二个工厂不投资，对第三个工厂投资300万元，此时获利最大为850万元。前三个工厂投资总额为200万元，即s4=200时有上一页下一页返回7.3动态规划问题实例最优决策为(0,0,200)即对第一个工厂、第二个工厂不投资，对第三个工厂投资200万元，此时获利最大为600万元。前三个工厂投资总额为100万元，即s4=100时有上一页下一页返回7.3动态规划问题实例最优决策为(0,0,100}，即对第一个工厂、第二个工厂不投资，对第三个工厂投资100万元，此时获利最大为250万元。前三个工厂投资总额为0万元，即s4=0时有最优决策为(0,0,0)，即对前三个工厂均不投资，此时获利为0万元。对前三个工厂进行投资时的不同状态的最优策略如表7-7所示。第四阶段(四个工厂)k=4:求f4(s5)，此即为题目所要求的解。由动态方程上一页下一页返回7.3动态规划问题实例最优决策为(200,0,300,100)，即对第一个工厂投资200万元，对第二个工厂不投资，对第三个工厂投资300万元，对第四个工厂投资100万元，此时获利最大为1600万元，此投资方案即是最优策略。上一页下一页返回7.3动态规划问题实例7.3.3背包问题背包问题的一般描述:

一位旅行者携带背包去旅行，已知他所能承受的背包重量限度为a，现有n种物品可供他选择携带，第j种物品的单位重量为aj，其效用值是携带物品数量二的函数cj(xj)(j=1,2,,…，n),如图7-8所示，问旅行者如何选择物品的携带可使总效用最大?列出规划模型上一页下一页返回7.3动态规划问题实例此问题可以用枚举法求解，但十分繁琐，故用动态规划思想求解(顺序法)。分析阶段划分:k=1,2,…,n;可供选择的物品按1,2,…,n排序，每段装一种物品，共划分为n段，成为n段决策问题。决策变量xk:为第k阶段装入第k种物品的件数。状态变量sk+1:为第1到第k阶段装入前k种物品的总重量，则上一页下一页返回7.3动态规划问题实例状态转移方程为最优指标函数fk(sk+1)为从第1一k阶段，在背包中装入前k种物品，且重量为sk+1

，时的最大效用—前部h段子策略。则此动态规划问题的基本方程(递推关系)为故此背包问题的最优策略为: 。上一页下一页返回7.3动态规划问题实例例7.5求如下问题的最优解。此问题可以看成是背包问题，旅行者所能承受的重量为5(见表7-9)，求其最优携物方案。解①当k=1，即只装第1种物品时:上一页下一页返回7.3动态规划问题实例注意:s2取离散值，s2=-0，1，2，3，4，5； 为重量不超过s2的第1种物品最多的件数。当s2=0时，最优策略为(o}，即第一种物品选。件。当s2=1时，上一页下一页返回7.3动态规划问题实例最优策略为(0)，即第一种物品选0件。当s2=2时，最优策略为(o}，即第一种物品选。件。当s2=3时，上一页下一页返回7.3动态规划问题实例最优策略为(1)，即第一种物品选1件。当s2=4时，最优策略为(1)，即第一种物品选1件。当s2=5时，上一页下一页返回7.3动态规划问题实例最优策略为(1)，即第一种物品选1件。第一阶段在承重约束下所有最优策略如表7-10所示。②当k=2，即装前2种物品时:s3可取值为0、1、2、3、4、5。则当s3=0时，上一页下一页返回7.3动态规划问题实例最优策略为(0,0)，即两种物品均不选。当s3=1时，上一页下一页返回7.3动态规划问题实例最优策略为(0,0)，即两种物品均不选。当s3=2时，上一页下一页返回7.3动态规划问题实例最优策略为(0,1)，即第一种物品不选，第二种物品选1件。当s3=3时，上一页下一页返回7.3动态规划问题实例最优策略为(1,0)，即选第一种物品1件，第二种物品不选。当s3=4时，上一页下一页返回7.3动态规划问题实例最优策略为(0,2)，即第一种物品不选，第二种物品选2件。当s3=5时，上一页下一页返回7.3动态规划问题实例最优策略为(1,1)，即第一种物品选1件，第二种物品选1件。在满足承重约束下，选前两种物品的最优策略如表7-11所示。③当k=3，即装前3种物品时:而 即为此背包问题的最优策略效用值。当s3=5时,上一页下一页返回7.3动态规划问题实例即该背包问题的最优策略为(1,1,0)，选一、二物品各一件，不选物品三，最大效用为13。上一页下一页返回7.3动态规划问题实例7.3.4设备更新问题设备更新问题的一般描述:

已知一台设备的效用函数r(t)、维修费用函数w(t)以及更新设备费用函数c(t)，要求在所考察的n年内每年初作出决策:是继续使用旧设备还是更新一台新设备，使n年总效用最佳。函数说明:rk(t):在第k年年初，已使用过t年(役龄)设备，再使用1年的效用。wk(t):在第k年年初，已使用过t年(役龄)设备，再使用1年的维修费用。ck(t):在第k年，更新一台役龄为t年的旧设备的净更新费用(注意:设备更新时尚余残值，所谓净更新费用是指已考虑残值以后所增加的费用)。上一页下一页返回7.3动态规划问题实例

α:为拆现因子，0≤α≤

1，进行计算时，我们对参数:r(t),w(t)均为年初时进行未来一年内效用及维修费用测算，由于费用的时效性，故需对此费用进行拆现，即把它们拆算到基年的年初，粗略计算时，此时间效应可忽略不计，取α=1。用动态规划方法解决此类问题，下面进行分析(逆序方法进行计算)。阶段k：k=n,n-1,…，1，以所考察的设备使用年限数n划分阶段。决策变量xk:第k年初是更新，还是继续使用旧设备，用R表示更新，用K表示继续使用该设备，即状态变量sk:第k年初，设备已使用的年限，即役龄。上一页下一页返回7.3动态规划问题实例则状态转移方程为: ，uk即为xk。两种状态:阶段指标:第k阶段到第k+1阶段的效用(一年的效用)为指标函数(和形式):上一页下一页返回7.3动态规划问题实例其中，Vk，n表示从第k阶段始到第/年(所考察的最后年限)，对该设备采用不同决策所获得的效用—后部k段子策略。fk(sk)表示第k年年初，设备已使用sk年，到第n年年末的最优后部k段子策略的最优效用。动态方程为注意:上一页下一页返回7.3动态规划问题实例例7.6设某台新设备的年效益及年均维护费用如表7-12所示，试决定今后5年的使用策略，以使其效用最大(忽略时效性)。解①当k=5时，即设备使用到第5年年初时的最优策略为即上一页下一页返回7.3动态规划问题实例注意:到第五年年初，该设备的役龄由于前几年采用不同策略，可以取值的范围为:s5=1，2，3，4。则当s5=1时，即该设备的役龄为1年时(设备在第四年初进行了更新):此时最优策略为s5=K，即不更新，继续使用该设备。当s5=2时，即该设备的役龄为2年时(设备在第三年初进行了更新，第四年继续使用):上一页下一页返回7.3动态规划问题实例此时最优策略为s5=K，即不更新，继续使用该设备。当s5=3时，即该设备的役龄为3年时(设备在第二年年初进行了更新，第三年、第四年继续使用):上一页下一页返回7.3动态规划问题实例此时最优策略为s5=R，即更新该设备。当s5=4时，即该设备的役龄为4年时(设备在第一年年初进行了更新，第二、第三、第四年继续使用):此时最优策略为s5=R，即更新该设备。在设备使用到第五年年初时的不同状态的最优决策如表7-13所示。上一页下一页返回7.3动态规划问题实例②当k=4时，即设备使用到第四年年初时的最优策略:注意:到第四年年初，由于前几年采用不同策略，该设备的役龄可以取值的范围为:s4=1，2，3。上一页下一页返回7.3动态规划问题实例则当s4=1时，即该设备的役龄为1年时:上一页下一页返回7.3动态规划问题实例此时最优策略为s4=R，即更新该设备。当s4=2时，即该设备的役龄为2年时:上一页下一页返回7.3动态规划问题实例此时最优策略为s4=R，即更新该设备。当s4=3时，即该设备的役龄为3年时:此时最优策略为x4=R，即更新该设备。在设备使用到第四年年初时的不同状态的最优决策如表7-14所示。上一页下一页返回7.3动态规划问题实例③当k=3时，即设备使用到第三年年初时的最优策略:注意:到第三年年初，由于前几年采用不同策略，该设备的役龄可以取值的范围为:s3=1，2。上一页下一页返回7.3动态规划问题实例则当s3=1时，即该设备的役龄为1年时:上一页下一页返回7.3动态规划问题实例此时最优策略为s3=R，即更新该设备。当s3=2时，即该设备的役龄为2年时:上一页下一页返回7.3动态规划问题实例此时最优策略为s3=R，即更新该设备。在设备使用到第三年年初时的不同状态的最优决策如表7-15所示。④当k=2时，即设备使用到第二年年初时的最优策略:注意:到第二年年初，由于前几年采用不同策略，该设备的役龄可以取值的范围为：s2=1。上一页下一页返