动态规划a课件

第八章动态规划8.1多阶段决策问题8.2动态规划的基本概念和基本方程8.3最优性定理8.4动态规划的建模与求解方法8.5动态规划应用举例1第八章动态规划8.1多阶段决策问题1动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistepdecisionprocess)的优化问题时，提出了著名的最优化原理(principleofoptimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著DynamicProgramming，这是该领域的第一本著作。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。2动态规划(dynamicprogramming)是运筹学的8.1多阶段决策问题多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。决策:在多个可行方案中选择或选定一个的过程或行为;策略:由一系列相互衔接的决策构成的决策序列;策略集合:有可供选择的策略构成的集合;最优策略:在预定标准下达到最好效果的策略.38.1多阶段决策问题多阶段决策过程，是指这样的一类特殊的活静态决策一次性决策动态决策多阶段决策决策s1s2vx输入决策输出决策效应第一阶段s1s2v1x1第二阶段s3v2x2第三阶段s4v3x34静态决策一次性决策动态决策多阶段决策例1（最短路线问题）给定一个线路网络图,两点之间联线上的数字表示两点间的距离(或运费),试求一条由s到t的铺管线路,使总距离最短.adbetcfs97578456465475例1（最短路线问题）adbetcfs975784564654例2（资源分配问题）某公司拟将50万元资金投放下属A、B、C三个部门，各部门在获得资金后的收益如表所示，求总收益最大的投资分配方案（投资数以10万元为单位）。投放资金(万元)01020304050收益（万元）

A01520252830B0010254570C010203040506例2（资源分配问题）某公司拟将50万元资金投放下属A、B、C例3（装载问题）已知货物的单位重量ωi，单位体积υi及价值pi如表所示，船的最大载重能力为W＝5，最大装载体积为V＝8，求最优装载方案。iωiυipi1123023480323657例3（装载问题）已知货物的单位重量ωi，单位体积υi及8.2动态规划的基本概念和基本方程(1)动态规划的基本概念阶段与阶段变量:将所要研究的问题,按时间或空间特征分成若干个互相联系的阶段.简称“阶段”我们就是要按阶段的顺序来求解.描述阶段的变量阶段变量,常用字母k来表示;88.2动态规划的基本概念和基本方程(1)动态规划的基本概状态、状态变量和状态集合各阶段开始时的客观条件叫做状态.描述各阶段状态的变量叫做状态变量,常用sk表示第ｋ阶段的状态变量；状态变量sk的取值集合称为状态集合,用Sk表示；动态规划中状态具有以下性质:某阶段状态一旦确定以后过程的状态变化不受这个状态以前的影响,也就是说某状态以后的过程和以前无关,只与当前状态有关,我们称这种特性为“无后效性.”9状态、状态变量和状态集合9决策、决策变量和策略当个阶段的状态取定以后,就可以做出关于下一步的选择,从而确定下一阶段的状态,这种决定称为决策；表示决策的变量叫做决策变量,常用xk(sk)表示.第k阶段当状态为sk时的决策变量；在实际问题中决策变量的取值往往限制在一定的范围内,我们称此范围为允许决策集,常用Dk(sk)表示第k阶段从状态sk出发的允许决策集,因此有xk(sk)∈Dk(sk).各段决策确定后,整个问题的决策序列就构成了一个策略,用p1,n{x1(s1),x2(s2),…,xn(sn)}表示；10决策、决策变量和策略10使整个问题达到最优效果的的策略就是最优策略.动态规划中本阶段的状态是上一阶段的决策结果.如果给定了第k阶段的状态sk,本阶段的决策就为xk(sk),则第k+1段的状态xk+1也就完全确定了,它的关系可表示为:sk+1=Tk(sk,xk).由于它表示了由k到k=1段的状态转移规律,所以称为状态转移方程.T1s1s2v1(s1,x1)x1(s1)T2s3v2(s2,x2)x2(s2)Tksksk+1vk(sk,xk)xk(sk)Tnsnsn+1……vn(sn,xn)xn(sn)11使整个问题达到最优效果的的策略就是最优策略.T1s1s2v1指标函数与最优值函数用于衡量所选定策略优劣的数量指标称为指标函数.阶段指标函数vk(sk,xk)一个n段决策过程,从1到n叫作问题的原过程,对于任意一个给定的k,从第k到n段的过程称为原过程的一个后部子过程.V1,n(s1,p1,n)表示初始状态s1采用策略p1,n.时原过程指标函数值.Vkn=(sk,xk,sk+1,xk+1,…,sn,xn)(k=1,2,…,n)V1n=(s1,x1,s2,x2,…,sn,xn)12指标函数与最优值函数12多段决策过程中从第k阶段到最终阶段的过程称为k-后部子过程，简称k-子过程。Tksksk+1vk(sk,xk)xk(xk)Tnsnsn+1…vn(sn,xn)xn(xn)13多段决策过程中从第k阶段到最终阶段的过程称为指标函数应具有三个条件1）指标函数在全过程和所有后部子过程上有定义；2）指标函数应具有可分离性，满足递推公式Vkn=Ψ(sk,xk,Vk+1,n(sk+1,xk+1,…,sn,xn))3）函数Ψ是一个关于变量Vk+1,n单调递增的函数。指标函数Vkn达到最优值，称为最优值函数。fk(sk)=optVkn(sk,xk,sk+1,xk+1,…,sn,xn)

(k=1,2,…,n)

使指标函数Vkn达到最优值的策略是从k开始的后部子过程的最优策略，记作pkn*={xk*,..xn*},p1n*又是全过程的最优策略，简称最优策略。

14指标函数应具有三个条件14指标函数的两种基本形式：Ⅰ全过程和它的任一后部子过程的指标函数等于各阶段指标函数之和Ⅱ全过程和它的任一后部子过程的指标函数等于各阶段指标函数之积15指标函数的两种基本形式：Ⅱ全过程和它的任一后部子过程的指(2)最优化原理Bellman最优化原理“最优策略具有的基本性质是：无论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，下余的决策序列必构成最优策略”。AMB16(2)最优化原理Bellman最优化原理AMB16最优性原理的含意最优策略的任何一部分子策略，也是相应初始状态的最优策略。每个最优策略只能由最优子策略构成。显然，对于具有无后效性的多段决策过程而言，如果按照k后部子过程最优的原则来求各阶段状态的最优决策，那么这样构成的最优决策序列或策略一定具有最优性原理所揭示的性质。17最优性原理的含意17(3)动态规划基本方程多段决策过程的特点每个阶段都要进行决策相继进行的阶段决策构成的决策序列前一阶段的终止状态又是后一阶段的初始状态阶段最优决策不能只从本阶段的效应出发，必须通盘考虑，整体规划。阶段k的最优决策不应该只是本阶段效应的最优，而必须是本阶段及其所有后续阶段的总体最优，即关于整个k后部子过程的最优决策。18(3)动态规划基本方程18多段决策过程中所要求解的是，从起始状态x1开始，进行一系列的决策，使目标V达到最优，最优目标值V*最优策略----使得目标达到最优的决策序列。最优路线----在采取最优策略时，系统从s1开始所经过的状态序列求解动态规划模型找到最优策略、最优路线和最优目标值。19多段决策过程中所要求解的是，从起始状态x1开始，进行一系列的对于Ⅰ类指标函数设在阶段k的状态xk执行了任意选定决策xk后的状态是sk+1=Tk(sk,xk)。这时k-后部子过程就缩小为k+1后部子过程。根据最优性原理，对k+1后部子过程应采取最优策略，由于无后效性，k后部子过程的目标函数值为20对于Ⅰ类指标函数20给出边界条件：合在一起即构成动态规划的基本方程。21给出边界条件：21Ⅰ类指标函数的基本方程（逆序）为II类指标函数的基本方程（逆序）为适用于初始状态给定22Ⅰ类指标函数的基本方程（逆序）为II类指标函数的基本方程（逆Ⅰ类指标函数的基本方程（顺序）为II类指标函数的基本方程（顺序）为同理适用于终止状态给定23Ⅰ类指标函数的基本方程（顺序）为II类指标函数的基本方程（顺8.3最优性定理248.3最优性定理24动态规划的最优性定理：设阶段数为n的多阶段决策过程，其阶段编号为k=0,1,...,n-1。允许策略是最优策略的充要条件是对任意一个k,0<k<n-1和s0S0，有它是由给定的初始状态s0和子策略p0,k-1所确定的k段状态。当V是效益函数时，opt取max;当V是损失函数时，opt取min.25动态规划的最优性定理：设阶段数为n的多阶段决策过程，其阶段编证明：必要性（）26证明：必要性（）26充分性（）设p0,n-1=(p0,k-1,pk,n-1)为任一策略，sk为由（s0，p0,k-1）所确定的k阶段的起始状态，则有（以最大化为例）27充分性（）设p0,n-1=(p0,k-1,推论：若允许策略p*0,n-1是最优策略，则对任意的k,0<k<n-1,它的子策略p*k,n-1对于以

s*k=Tk-1(s*k-1,u*k-1)为起点的k到n-1子过程来说，必是最优策略。（注意：k段状态s*k,是由s0和p*0,k+1所确定的）28推论：若允许策略p*0,n-1是最优策略，则对任意的k,0<8.4动态规划的求解方法(1)基本求解过程动态规划建模递推回溯(2)动态规划逆推解法(3)动态规划顺推解法298.4动态规划的求解方法(1)基本求解过程29(1)基本求解过程动态规划建模①确定阶段与阶段变量k②明确状态变量sk(无后效性)和状态可能集合Sk。③确定决策变量xk(sk)和决策允许集合Dk(sk)。④确定状态转移方程sk+1=Tk(sk,xk)。⑤明确阶段效应和目标，即写出指标函数Vkn(具有三个性质)。30(1)基本求解过程30①确定阶段与阶段变量阶段的划分一般是按照决策进行的时间或空间上的先后顺序划分的，阶段数等于多段决策过程中从开始到结束所需要作出决策的数目，阶段变量用k表示。②明确状态变量和状态可能集合状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。状态变量的确定决定了整个决策过程是不是具有无后效性，因而也决定着能不能用动态规划方法来求解。状态可能集是关于状态的约束条件，因此为了求解必须正确地确定状态可能集。31①确定阶段与阶段变量31③确定决策变量和决策允许集合。与静态问题相同，决策变量应能够反映对问题所作的决策，决策变量也应有其相应的约束条件，在建模时应明确决策允许集合Dk(sk)。④确定状态转移方程。系统k阶段从状态sk出发作了决策xk(sk)之后的结果之一是系统状态的转移，这一结果直接影响系统往后的决策过程，因此必须明确状态的转移过程，即根据问题的内在关系，明确sk+1=Tk(sk,xk)中的函数Tk(sk,xk)

。32③确定决策变量和决策允许集合。32递推运用基本方程的递推公式和边界条件，从k=n开始，由后向前逆推，从而逐步求得各阶段的最优决策和相应的最优值，最后求得f1(s1),将s1的值代入计算即得。回溯由s1和x1*，利用状态转移方程计算出s2，从而确定x2*，…，依此类推，最后确定xn*，于是获得最优策略33递推33(2)动态规划逆推解法例1某旅行者希望从s地起到t地，其间的道路系统如图所示，图上圆圈表示途径的地方，称为节点，连结两地的箭线表示道路，其上的数字表示该段道路长度，箭头表示通行的方向。试求s到t的最短路。adbetcfs975784564654734(2)动态规划逆推解法adbetcfs9757845646第一阶段第二阶段第三阶段划分阶段k=1,2,3代表三个阶段adbetcfs975784564654735第一阶段第二阶段状态变量sk取为k阶段所在地，则有：adbetcfs9757845646547边界条件f4(t)=036状态变量sk取为k阶段所在地，则有：adbetcfs975k阶段决策是决定下一步走到哪里，xk(sk)取为下一步的所在点。adbetcfs975784564654737k阶段决策是决定下一步走到哪里，xk(sk)取为下一步的所在

adbetcfs9757845646547指标函数：递推方程：38 adbetcfs9757845646547指标函数：由于第3阶段末已到达t，往后的距离自然是零，因此f4(t)=0对3阶段所有可能的状态S3={d,e,f}计算f3()如下39由于第3阶段末已到达t，往后的距离自然是零，因此f4(t)=也可以用表格方法计算如下t/tf3()x3()def5+07+04+0574tttv3(s3,x3)+f4(s4)f3(s3)x3(s3)adbetcfs975784564654740也可以用表格方法计算如下t/tf3()x3()d5+05tvadbetcfs975784564654747541adbetcfs975784564654747541对2阶段所有可能的状态s2={a,b,c}计算f2()如下42对2阶段所有可能的状态s2={a,b,c}计算f2()如下44343也可以用表格方法计算如下d/de/ef/ff2()x2()abc7+55+54+56+75+74+46+48109fddf2(s2)x2(s2)v2(s2,x2)+f3(s3)adbetcfs975784564654744也可以用表格方法计算如下d/de/ef/ff2()x2()aadbetcfs9757845646547475910845adbetcfs9757845646547475910845对1阶段所有可能的状态S1={s}计算f1()如下a/ab/bc/cf2()x2()s9+88+107+916c46对1阶段所有可能的状态S1={s}计算f1()如下a/a顺序回溯求最优策略、最优路线和最优目标函数值47顺序回溯求最优策略、最优路线和最优47adbetcfs975784564654747591081648adbetcfs9757845646547475910816例2某公司有资金10万元，若投资项目i（i=1,2,3）的投资额为时,其效益分别为:问应如何分配投资数额才能使总收益最大?可列出它的静态模型:

[分析]:这是一个表面与时间没有任何关系的问题,但要用动态规划的方法去解则必须把它划分为“时段”.本题可划分为3各时段,每段只决定对一个投资项目的投资额.这样把问题分解为3阶段决策问题.49例2某公司有资金10万元，若投资项目i（i=1,2,解:50解:50当k=2时,

这是一个函数求极值问题,利用微分方法可求得该函数有极小值.s0s2x251当k=2时,这是一个函数求极值问题,利用微分方法可求得该函要讨论的具体情况:52要讨论的具体情况:52减函数53减函数535454例3用动态规划方法求解下列规划问题：解:(1)建模阶段划分：k=1,2,3状态变量：阶段初始时刻可分配资源，用s1,s2,s3表示，其中s1=6决策变量：每阶段消耗资源量，用x1,x2,x3表示状态转移方程：指标函数：55例3用动态规划方法求解下列规划问题：解:(1)建模55(2)递推：56(2)递推：565757(3)回溯：58(3)回溯：58(3)动态规划顺推解法例1某旅行者希望从s地起到t地，其间的道路系统如图所示，图上圆圈表示途径的地方，称为节点，连结两地的箭线表示道路，其上的数字表示该段道路长度，箭头表示通行的方向。试求s到t的最短路。adbetcfs975784564654759(3)动态规划顺推解法adbetcfs9757845646第一阶段第二阶段第三阶段划分阶段k=1,2,3代表三个阶段adbetcfs975784564654760第一阶段第二阶段状态变量sk取为k阶段所在地，则有：adbetcfs9757845646547边界条件f0(s)=061状态变量sk取为k阶段所在地，则有：adbetcfs975k阶段决策是决定到达所在点的路线，uk(sk)取为到达的sk的路线。adbetcfs975784564654762k阶段决策是决定到达所在点的路线，uk(sk)取为到达的sk由于第0阶段末已到达s，往前的距离自然是零，因此f0(s)=0对1阶段所有可能的状态S1={a,b,c}计算f1()如下63由于第0阶段末已到达s，往前的距离自然是零，因此f0(s)=也可以用表格方法计算如下s/sf1()u1()abc9+08+07+0987sasbscv1(s1,u1)+f0(s)f1(s1)u1(s1)64也可以用表格方法计算如下s/sf1()u1()a9+09saadbetcfs9757845646547879065adbetcfs9757845646547879065对2阶段所有可能的状态s2={d,e,f}计算f2()如下66对2阶段所有可能的状态s2={d,e,f}计算f2()如下66767也可以用表格方法计算如下a/ab/bc/cf2()u2()def7+94+95+86+84+75+76+7111213cdceaf,cff2(s2)u2(s2)v2(s2,u2)+f1(s1)68也可以用表格方法计算如下a/ab/bc/cf2()u2()dadbetcfs9757845646547879131112069adbetcfs9757845646547879131112对3阶段所有可能的状态S3={t}计算f3(t)如下d/de/ef/ff3()u3()t5+117+124+1316ft70对3阶段所有可能的状态S3={t}计算f3(t)如下d/de逆序回溯求最优策略、最优路线和最优目标函数值71逆序回溯求最优策略、最优路线和最优71adbetcfs975784564654787913111216072adbetcfs9757845646547879131112动态规划的优点：可把一个N维优化问题化成N个一维优化问题求解。73动态规划的优点：73动态规划的优点：可把一个N维优化问题化成N个一维优化问题求解。DP方程中附加某些约束条件，可使求解更加容易。74动态规划的优点：74动态规划的优点：可把一个N维优化问题化成N个一维优化问题求解。DP方程中附加某些约束条件，可使求解更加容易。求得最优解以后，可得所有子问题的最优解。75动态规划的优点：75动态规划的缺点：“一个”问题，“一个”模型，“一个”求解方法。且求解技巧要求比较高，没有统一处理方法。76动态规划的缺点：768.5动态规划的其他应用举例（1）生产——库存问题（2）资源分配问题（3）串联系统可靠性问题（4）设备更新问题（5）二维背包问题778.5动态规划的其他应用举例（1）生产——库存问题77（1）生产－库存问题生产计划周期分为n个阶段，即k=1~n；已知最初库存量为s1；阶段需求量为dk；单位产品的消耗费用为Lk；单位产品的阶段库存费用为hk；仓库容量为Mk；阶段生产能力为Bk；生产的准备费用为：78（1）生产－库存问题生产计划周期分为n个阶段，即k=1~n问应如何安排各阶段产量，使计划期总费用最小。这里状态变量sk应选为阶段k的初始库存量，计划初期的库存量s1是已知的，末期的库存量通常也是给定的，为简单起见这里假定sn+1=0，于是问题是始端末端固定的问题。关于状态xk的约束条件是即阶段k的库存既不能超过库存容量，也不应超过阶段k至阶段n的需求总量(dk+dk+1+…+dn)，否则将与sn+1=0的假设相违背。79问应如何安排各阶段产量，使计划期总费用最小。这里状态变量sk库容量限制以后需求缺口本期需求缺口决策变量xk选为阶段k的生产量。阶段产量要在不超过生产能力Bk的条件下，充分满足该阶段的需求dk，同时还要满足计划末期的库存量为0的要求。因此关于决策变量的约束条件就是期末库存=期初库存+生产量-本期需求80库容量限制以后需求缺口本期需求缺口决策变量xk选为阶段k的生阶段k的生产费用是库存费用按阶段k末期的库存量sk+1计算81阶段k的生产费用是库存费用按阶段k末期的库存量sk+1计算例3求解生产－库存问题。已知其n=3，ck=8，Lk=2，hk=1.5，s1=1，Mk=4，s4=0(计划周期末期的库存量为0)，Bk＝6，d1=3，d2=4，d3=3。解：82例3求解生产－库存问题。已知其n=3，ck=8，Lk=2838384840123f3()x3’0141431121222101013000850123f3()x3’01414311212221010130123456f2()x2’016+1419.5+1223+10304114+1417.5+1221+1024.5+024.56212+1415.5+1219+1022.5+022.55310+1413.5+1217+1020.5+020.5440+1411.5+1215+1018.5+0140860123456f2()x2’016+1419.5+1223+23456f!()x1’112+3015.5+24.519+22.522.5+20.526+14403或68723456f!()x1’112+3015.5+24.519+23456f!()u1’112+3015.5+24.519+22.522.5+20.526+14403或68823456f!()u1’112+3015.5+24.519+(2)资源分配问题资源的多元分配

设有某种资源，总量为M，可以投入n种生产活动。已知用于活动k的资源为uk时的收益是gk(uk)，问应如何分配资源，使n种生产活动的总收益最大。这种问题就是资源的多元分配问题。89(2)资源分配问题资源的多元分配89资源的多元分配如果将n种活动作为一个互相衔接的整体，对一种活动的资源分配作为一个阶段，每个阶段确定对一种活动的资源投放量。则该问题成为一个多段决策问题。状态变量xk的选取原则是要能够据此确定决策uk，以及满足状态转移方程所要求的无后效性。在资源分配问题中，决策变量选为对活动k的资源投放量，因此状态变量可以选择为阶段k初所拥有的资源量，即将要在第k种到第n种活动间分配的资源量。90资源的多元分配90关于状态变量xk的约束条件是0≤xk≤M关于决策变量uk的约束条件是0≤uk≤xk状态转移方程为xk+1=xk-uk显然它满足无后效性要求。阶段效应为对活动k投放资源uk时的收益，vk(xk,uk)=gk(uk)目标函数是为n种活动投放资源后的总收益动态规划基本方程91关于状态变量xk的约束条件是0≤xk≤M91例4某公司拟将50万元资金投放下属A、B、C三个部门，各部门在获得资金后的收益如表所示，用动态规划方法求总收益最大的投资分配方案（投资数以10万元为单位）。投放资金（万元）01020304050收益（万元）A01520252830B0010254570C0102030405092例4某公司拟将50万元资金投放下属A、B、C三个部门，各部解:该问题可以作为三段决策过程。对A、B、C三个部门分配资金分别形成1，2，3三个阶段。xk表示给部门k分配资金时拥有的资金数。uk表示给部门k分配的资金数（以10万元为单位）。状态转移方程是xk+1=xk-uk。阶段效应如表所示。目标函数是阶段效应求和。首先逆序求最优目标函数值集合和最优决策集合。93解:该问题可以作为三段决策过程。对A、B、C三个部门分配资从表可知g3()是单调递增的函数，因此，当u3=x3时达到最大。即：94从表可知g3()是单调递增的函数，因此，当u3=x3时达x3g3f3U3’000011010122020233030344040455050595x3g3f3U3’000011010122020233030k=2时，0≤x2≤50≤u2≤x2

96k=2时，0≤x2≤50≤u2≤x296k=2时，0≤x2≤50≤u2≤x2

0/x21/x2-12/x2-23/x2-34/x2-45/x2-5f2()U2’00+00010+100+010020+200+1010+020030+300+2010+1025+030040+400+3010+2025+1045+045450+500+4010+3025+2045+1070+070597k=2时，0≤x2≤50≤u2≤x20/x21/当k=1时，有x1=5，0≤u1≤x1=598当k=1时，有x1=5，0≤u1≤x1=598当k=1时，有x1=5，0≤u1≤x1=50/51/42/33/24/15/0f1()U1’50+7015+4520+3025+2028+1030+070099当k=1时，有x1=5，0≤u1≤x1=50/51/42/顺序求最优目标函数值和最优策略、最优路线0/51/42/33/24/15/0f1()U1’50+7015+4520+3025+2028+1030+0700100顺序求最优目标函数值和最优策略、最优路线0/51/42/33资源的多段分配将一种有消耗性的资源，多阶段地在多种不同的生产活动中投放的问题称为资源的多段分配问题，下面讨论其中包含有两个生产活动的简单情况。设有某种资源，初始的拥有量是M。计划在A，B两个生产部门连续使用n个阶段。已知在部门A投入资源uA时的阶段收益是g(uA)，在部门B投入资源uB时的阶段收益是h(uB)。又资源在生产中将有部分消耗，已知每生产一个阶段后部门A，B中的资源完好率分别为a和b，0<(a,b)<1。求n阶段间总收益最大的资源分配计划。101资源的多段分配101n段决策过程状态变量xk为阶段k初拥有的资源量，0≤xk≤M，x1=M决策变量选为阶段k在部门A的资源投放量，即uA=uk，这里显然有uB=xk-uk，决策变量的约束条件是0≤uk≤xk即最多将所拥有的资源都投入部门A，其时uB=0阶段k末部站A的剩余资源auk，部门B中则为b(xk-uk)，因此状态转移方程xk+1=T(xk,uk)是xk+1=auk+b(xk-uk)满足无后效性阶段效应rk(xk,uk)即阶段收益rk(xk,uk)=g(uk)+h(xk-uk)目标函数是n个阶段的总收益，即阶段效应求和。102n段决策过程102例5今有1000台机床，要投放到A、B两个生产部门，计划连续使用3年。已知对A部门投入uA台机器时的年收益是g(uA)=4(uA)2（元），机器完好率a=0.5，相应的B部门的年收益是h(uB)=2(uB)2（元），完好率b=0.9。试求使3年间总收益最大的年度机器分配方案。解以每年作为一个阶段，设状态变量和决策变量都是连续取值的。K阶段状态变量xk取为该年度初完好的设备数，决策变量取为该年度投入A活动的设备数，则有

0≤xk≤1000，

0≤uk≤xk状态转移方程为：xk+1=0.5uk+0.9(xk-uk)103例5今有1000台机床，要投放到A、B两个生产部门，计解以每年作为一个阶段，设状态变量和决策变量都是连续取值的。K阶段状态变量xk取为该年度初完好的设备数，决策变量取为该年度投入A活动的设备数，则有

0≤xk≤1000，

0≤uk≤xk状态转移方程为：xk+1=0.5uk+0.9(xk-uk)动态规划基本方程104解以每年作为一个阶段，设状态变量和决策变量都是连续取值的逆序求条件最优目标函数值fk(xk)和条件最优决策k=3时，0≤u3≤x3，注意到f4(x4)=0，有k=2时，0≤u2≤x2，有105逆序求条件最优目标函数值fk(xk)和条件最优决策k=2时，k=1时，0≤u1≤x1，x2=0.5u1+0.9(x1-u1)，f2(x2)106k=1时，0≤u1≤x1，x2=0.5u1+0.9(x1-u(3)串联系统可靠性问题系统可靠性是指系统在规定的条件下能正常工作的概率，它是管理和工程技术设计中经常要研究的问题。这儿要研究的是串联系统可靠性问题。例如某种仪器设备由N个部件串联构成，凡其中有一个部件出现故障，则整个系统便不能正常工作。为了提高系统工作的可靠性，一种方法是可以在每个部件上装有主要元件的相同性能的备用件，并且带有备用元件自动投入装置。自然备用元件越多，系统的可靠性越高，但也会相应增加系统重量、体积和费用，有时也会降低工作精度。因此，在成本、重量、体积等一定的条件限制下，应如何选择各部件的备用元件数，使得整个系统的可靠性最大，就可以归结为一个动态规划问题。107(3)串联系统可靠性问题系统可靠性是指系统在规定的条件下例6某电气设备由三个部件串联而成，为提高该种设备在指定工作条件下正常工作的可靠性，需在每个部件上安装一个、两个或三个主要元件的相同备件。假设对部件i(i=1，2，3)配备j个备件后的可靠性Rij和所需费用cij均已知，如表所示，若可用的总资金数量为1万元，问如何配备各部件的备用元件数，才能使该设备在给定工作条件下的可靠性最大？备件数部件j=1j=2j=3Ci1（千元)vi1Ci2（千元）vi2Ci3（千元）vi3110.9030.9450.96230.7550.8860.97320.8030.9240.99108例6某电气设备由三个部件串联而成，为提高该种设备在指定解:以给不同的部件决定备件作为不同的阶段，则该问题是3阶段决策问题设状态变量xk表示从第k个部件到第3个部件允许使用的总费用（k=1,2,3）决策变量uk为第k部件配备的备用元件数（k=1，2，3）。则据题意有：x1=10千元，且每个部件都最少有一个备件，即uk≥1，若令sk表示为保障以后各部件均能获得一个备件所需的资金数，则应有：109解:以给不同的部件决定备件作为不同的阶段，则该问题是3阶且据此可得：s1=6，s2=5，s3=2。从而可知：对uk有即当期所耗资金加上k+1期往后所用资金sk+1不超过当前拥有资金数。根据上述分析可以写出各阶段的状态可能集合和决策允许集合如下：

x1=10X2＝{9，7，5}X3＝{2，3，4，5，6}U1＝{1，2，3}U2(9)＝{1，2，3}U2(7)＝{1，2}U2(5)＝{1}U3(2)＝{1}U3(3)＝{1，2}U3(4)＝{1，2，3}U3(5)＝{1，2，3}U3(6)＝{1，2，3}110且据此可得：s1=6，s2=5，s3=2。即当期所耗资金加上状态转移方程为：阶段效应为目标函数为是阶段效应乘积的形式若以fk(xk)表示在阶段k拥有资金xk时采用最优决策序列所得的k阶段往后的系统的可靠性，则动态规划基本方程为：111状态转移方程为：阶段效应为目标函数为是阶段效应乘积的形式1/x3-22/x3-33/x3-4f3()U3’20.8×10.8130.8×10.92×10.92240.8×10.92×10.99×10.99360.8×10.92×10.99×10.9931121/x3-22/x3-33/x3-4f3()U3’20.8×1/x2-32/x2-53/x2-6f2()U2’90.75×0.990.8×0.990.97×0.920.8924370.75×0.990.8×0.80.7425150.75×0.80.611/x3-22/x3-33/x3-4f3()U3’20.8×10.8130.8×10.92×10.92240.8×10.92×10.99×10.99360.8×10.92×10.99×10.9931131/x2-32/x2-53/x2-6f2()U2’90.751/x2-32/x2-53/x2-6f2()U2’90.75×0.990.8×0.990.97×0.920.8924370.75×0.990.8×0.80.7425150.75×0.80.611/92/73/5f1()U1’100.9×0.89240.94×0.74250.96×0.60.803161

1141/x2-32/x2-53/x2-6f2()U2’90.75(4)设备更新问题

设备更新问题的一般提法随着使用年限的增加，设备性能会变差，故障会增加，需要维修或更新。设备使用时间愈长，积累效益愈高，但随着设备陈旧，维修使用费用也会提高，而且，设备使用年限愈久，处理价格愈低，更新费用也要增加。因此，处于某个阶段的各种设备，总是面临着保留还是更新的问题，这个问题应该从整个计划期间的总回收额，而不应从局部的某个阶段的回收额来考虑。由于每个阶段都面临着保留还是更新的两种选择，因此，它是一个多阶段的决策过程，可以用动态规划方法求解。115(4)设备更新问题设备更新问题的一般提法115今有一设备更新问题如下：已知n为计算设备回收额的总期数；t为某个阶段的设备役龄；γ(t)为从役龄为t的设备得到的阶段收益；μ(t)为役龄为t的设备的阶段使用费用；s(t)是役龄为t的设备的处理价格；p为新设备的购置价格；求n期内使回收额最大的设备更新政策。116今有一设备更新问题如下：116状态变量选为设备的役龄t，即xk=t，决策只有两种可能，即保留或更新，记为K（保留）或P（更新）。状态转移方程相应的阶段效应即阶段的回收额也有两种可能117状态变量选为设备的役龄t，即xk=t，相应的阶段效应即阶段的例7假定n＝6年，新设备购买价格为10万元。役龄为t时的设备使用效益γ(t)，使用费用μ(t)和处理价格s(t)如下表所示T0123456γ(t)万元27262624222018μ(t)万元15151616171718s(t)万元6554432118例7假定n＝6年，新设备购买价格为10万元。T01234T0123456γ(t)万元27262624222018μ(t)万元15151616171718s(t)万元6554432γ(t)-μ(t)1211108530s(t)+28776654119T0123456γ(t)万元27262624222018μ(t0123456γ(t)-μ(t)1211108530s(t)+28776654t0123456f6(t)1211108654120t0123456γ(t)-μ(t)1211108530s(t0123456γ(t)-μ(t)1211108530s(t)+28776654t0123456f6(t)1211108654f5(t)23211817171615γ(t)-μ(t)+f6(t+1)23211814107s

(t)+2+1119181817171615121t0123456γ(t)-μ(t)1211108530s(t0123456γ(t)-μ(t)1211108530s(t)+28776654t0123456f6(t)1211108654f5(t)23211817171615γ(t)-μ(t)+f5(t+1)332927252118s

(t)+2+11292828272726