运筹与优化动态规划课件.ppt

《运筹与优化动态规划课件.ppt》由会员分享，可在线阅读，更多相关《运筹与优化动态规划课件.ppt（76页珍藏版）》请在三一办公上搜索。

1、第八章 动态规划,最短路径问题资源分配问题背包问题机器负荷分配问题,动态规划是一种研究多阶段决策问题的理论和 方 法。动态规划又称为多阶段规划.多阶段决策问题:决策过程是一种在多个相互联 系的阶段分别作出决策以形成序列决策的过程，而这些决策都是根据总体最优化这一共同目标 来选取的。要点：阶段，状态，决策，状态转移方程，k-后部子过程。状态 决策 状态 决策 状态 状态 决策 状态,第一节 多阶段的决策问题,阶段1,阶段2,阶段n,例1 最短路径问题:求从A到E的最短路径.,如果用枚举法，则从A到E共有332 1=18条不同的路径，逐个计算每条路径的长度，总共需作418=72次加法计算；对18条

2、路径的长度做两两比较，找出其中最短的一条，总共要 进行181=17次比较.最短路径：AB2C1D1E，最短距离19。,第二节 动态 规划的基本概念和基本方程 2.1.动态 规划的基本概念,1.阶段与阶段变量 把所给问题的过程,恰当地分为若干个相互联系的阶段,以便能按一定的次序去求解.描述阶段的变量称为阶段变量,用k表示.(k=1,2,n),2.状态与状态变量 状态是系统在变化过程中某个阶段的初始形态表征.描述状态的变量称为状态变量,用sk表示第k阶段的初始状态.第k阶段所有可能状态构成的集合称为该阶段的(可达)状态集合,记为Sk.,最短路问题中，各个节点就是状态生产库存问题中，库存量是状态物资

3、分配问题中，剩余的物资量是状态,无后效性：如果某阶段状态给定后,则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响.,3.决策与决策变量 决策是指在某个阶段状态给定以后,从该状态演变至下一阶段某状态的选择.描述决策的变量称为决策变量,用uk(sk)表示第k阶段处于状态sk时的决策变量.用Dk(sk)表示第k阶段从状态sk出发的允许决策集合.uk(sk)Dk(sk),最短路问题中，走哪条路生产库存问题中，各阶段的产品生产量物资分配问题中，分配给每个地区的物资量,4.策略与(后部)子策略 策略是一个按顺序排列的决策组成的集合.由过程的第一阶段开始到终点为止的每阶段的决策所组成的决策序列称为全过

4、程策略,简称策略.记为 p1,n(s1)=u1(s1),u2(s2),un(sn),由过程的第k阶段开始到终止状态为止的过程,其相应的决策序列称为k子过程策略,简称子策略.记为 pk,n(sk)=uk(sk),uk+1(sk+1),un(sn)可供选择的策略范围称为允许策略集合,用P表示.从P中找出达到最优效果的策略称为最优策略.,5.状态转移与状态转移方程 过程由这一阶段的一个状态转变到下一阶段的另一个状态称为状态转移.描述状态转移关系的方程称为状态转移方程.由状态sk转移到sk+1的状态转移方程.记为 sk+1=Tk(sk,uk)Tk称为状态转移函数.,6.指标函数和最优值函数 用来衡量所

5、实现过程优劣的一种数量指标,称为指标函数.表示为 Vk,n=Vk,n(sk,uk,sk+1,uk+1,sn+1)，k=1,2,n,动态规划的指标函数应具有可分离性、递推关系，即 Vk,n(sk,uk,sk+1,uk+1,sn+1)=ksk,uk,Vk+1,n(sk+1,uk+1,sn+1)常见的指标函数的形式是:1).Vk,n(sk,uk,sn+1)=nj=k vj(sj,uj)=vk(sk,uk)+Vk+1,n(sk+1,uk+1,sn+1),2).Vk,n(sk,uk,sn+1)=nj=k vj(sj,uj)=vk(sk,uk)Vk+1,n(sk+1,uk+1,sn+1)其中vj(sj,u

6、j)表示第j阶段的指标.,指标函数1),2)可统一表示为:其中记号“*”可都表示为“+”或都表示为“”.指标函数的最优值,称为最优值函数,记为fk(sk).它表示从第k阶段的状态sk开始到第n阶段的终止状态的过程,采取最优策略所得到的指标函数值.即其中“opt”是最优化(optimization)的缩写,可依题意取min或max.,2.2.动态 规划的基本思想和基本方程,最短路线有一个重要特性：如果L是允许策略集合P中从始点A到终点E的最短路线,M是L中的一点,则从M沿L到E的路是从M到E的最短路线.寻找最短路线的方法,可以从最后一段开始,由后向前逐步递推,求出各点到后一点的最短路线,最后求得

7、始点到终点的最短路线.所以,动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法.如图所示:行进方向 始点 1 2 3 n 终点 寻优途径,例1、最短路径问题,求从A到E的最短路径,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f5(E)=0,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D1)=5,f5(E)=0,2,5,1,12,14,10,6,10,4,13,11,1

8、2,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f4(D1)=5,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C1)=8,f4(D1)=5,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C2)=7,f4(D1)=5,f3(C1

9、)=8,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f3(C1)=8,f3(C2)=7,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B1)=20,f3(C2)=7,f3(C1)=8,2,5,1,12,14,10,6,10,4,13,1

10、1,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B2)=14,f3(C2)=7,f3(C1)=8,f2(B1)=21,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f2(B1)=21,f2(B2)=14,2,5,1,12,14,10,6

11、,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=1

12、9,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A（A，B2）B2,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A（A，B2）B2（B2，C1）C1,2,5,1,12,1

13、4,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A（A，B2）B2（B2，C1）C1（C1，D1）D1,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4

14、(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A（A，B2）B2（B2，C1）C1（C1，D1）D1（D1，E）E从A到E的最短路径为19，最短路线为AB 2C1 D1 E,k阶段与k+1阶段之间的递推关系:称为动态规划的基本方程.例1中opt=min，vk(sk,uk(sk)=dk(sk,uk(sk).用动态规划解题的基本思路,是将一个n阶段的决策问题化为依次求解n个具有递推关系的单阶段决

15、策问题,从而简化计算过程.这一思路体现了动态规划方法的如下基本特征:多阶段性，无后效性，递归性，总体优化性.,逆序解法:从问题的最后一个阶段开始,逆多阶段决策的实际过程反向寻优.如图所示:行进方向 始点 1 2 3 n 终点 寻优途径 顺序解法:从问题的最初阶段开始,顺多阶段决策的实际过程同向寻优.如图所示:行进方向 始点 1 2 3 n 终点 寻优途径(两种解法可表示行进方向的不同或对始点终点看法的颠倒),给实际问题建立动态规划模型的基本步骤:(1).将问题的过程恰当地划分为若干个阶段;(2).正确选择状态变量sk(第k阶段的初始状态),使它既 能描述过程的演变,又能满足无后效性;(3).确

16、定决策变量uk及每阶段的允许决策集合Dk(sk);(4).正确写出状态转移方程;(5).正确写出指标函数Vk,n，它应满足下面三个性质:a)是定义在全过程和所有后部子过程上的函数;b)要具有可分离性,且满足递推关系,即,Vk,n(sk,uk,sn+1)=ksk,uk,Vk+1,n(sk+1,uk+1,sn+1),c)函数k(sk,uk,Vk+1,n)对于变量Vk+1,n 要严格单调.,指标函数:动态规划逆序解法的基本方程为:式中状态转移方程sk+1=Tk(sk,uk).(8.2)中通常“*”取“+”时=0；取“”时=1.,动态规划顺序解法的基本方程为:式中状态转移方程sk=Tk(sk+1,uk

17、).(8.3)中通常“*”取“+”时=0；取“”时=1.,附注：若将状态变量sk表示k阶段末的结束状态，则 动态规划顺序解法的基本方程为:,第三节 动态 规划的最优性原理和最优性定理,动态 规划的最优性原理:作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何,对前面决策所形成的状态而言,余下的诸决策必构成最优策略.(简言之,一个最优策略的子策略总是最优的)动态 规划的最优性定理:设阶段数为n的多阶段决策过程,其阶段编号为k=0,1,2,。允许策略 是最优策略的充要条件是对任一个k，0kn-1和s0S0有,式(8.4)中,它是由给定的初始状态s0和子策略p0，k-1所确定的k段状态.

18、推论：若允许策略p*0,n-1 是最优策略,则对任意的k，0kn-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所确定的)此推论就是动态规划的“最优性原理”,它仅仅是最优策略的必要性.,动态规划的四大要素、一个重点(方程)状态变量及其可达状态集合 sk Sk 决策变量及其允许决策集合 uk Dk 状态转移方程 sk+1=Tk(sk,uk)阶段指标函数 vk(sk,uk)动态规划基本方程(8.2)或(8.3),第四节 多阶段决策过程及实例,多阶段决策过程特点:要点：阶段，状态

19、，决策，状态转移方程，k子过程.,逆推解法:决策uk使状态sk(输入)转移为状态sk+1(输出).状态转移方程 sk+1=Tk(sk,uk)，k=n,n-1,1.顺推解法:决策uk使状态sk+1(输入)转移为状态sk(输出).状态转移方程 sk=Tk(sk+1,uk)，k=1,2,n.初始状态给定时,宜用逆推法;终止状态给定时,宜用顺推法.,例1、设备负荷分配问题,某种机器可在高低两种不同的负荷下进行生产.设机器在高负荷下生产的产量函数为g=cu=8u，其中u为投入生产的机器数量,年终机器的完好率为a=0.7；在低负荷下生产的产量函数为h=dx=5x，其中x为投入生产的机器数量,年终机器的完好

20、率为b=0.9.假定开始生产时完好的机器数量为s1=1000台.试问企业每年年初应如何分配机器在高、低两种负荷下的生产,使在第5年年末完好的机器数量为s6=500台,并且5年内生产的产品总产量最高.,例1、设备负荷分配问题,解.设阶段序号k表示年度.状态变量sk为第k年年初拥有的完好机器数量,同时也是第k-1年年末的完好机器数量.决策变量uk为第k年度投入高负荷下生产的机器数量,于是 xk=sk-uk 为该年度中分配在低负荷下生产的机器数量.状态转移方程为 sk+1=auk+bxk=0.7uk+0.9(sk-uk),第k年度的允许决策集合为 Dk(sk)=uk0uksk第k年度的产量为 vk=

21、8uk+5(sk-uk),k=1,2,5指标函数 V1,5=5k=1vk.,令最优值函数fk(sk)表示从第k年开始到第5年年末所生产的产品的最大总产量,则有逆推法的基本方程:从第5年度开始,向前递推计算.,最优策略为：u1*=u2*=u3*=u4*=0，u5*=4.5s5-2500452.这表明,从第1年到第4年应把年初全部完好的机器投入低负荷生产,则在第5年初完好机器数为656台,第5年分配452台机器高负荷生产,204 台机器低负荷生产,可以保证在第5年年末完好的机器数量为500台,且5年内生产的产品总产量最高,最高产量为21833单位.注1.sk=0.5表示一台机器在k年内只有半年正常

22、工作时间；uk=0.3表示一台机器在k年内只有3/10时间高负荷生产。,注2.如果第n年年末完好的机器数量没有限制，则可以确定从低负荷转为高负荷生产的第t年。由,知从1至t-1年在低负荷下生产，t至n年在高负荷下生产，使n年内生产的产品总产量最高。当g(x)、h(x)为凸函数，且g(0)=h(0)=0，则在每个阶段上的最优策略总是取其上限或下限。例1中，若第5年年末完好的机器数量没有限制，则t=5-1-1=3，即从第3年年初将完好的机器全部投入高负荷生产，5年内生产的产品总产量最高。,例2、生产与存储问题,某厂在未来3个月连续生产某种产品.每月初开始生产.月生产量为x,生产成本为x2,库存费为

23、每月每单位1元.假如3个月的需求量预测为 b1=100,b2=110，b3=120，且初始存货s0=0，第三个月的期末存货s3=0.问应如何安排生产,使总成本最小.解.以月为阶段.设uk为第k月的产量，sk为第k月末的库存量,vk(sk,uk)为第k月的成本，fk(sk)为从第1月到第k月按最优策略安排生产的总成本.状态转移方程为 sk-1=sk-uk+bk，sk0，uk0，k=1,2,3,建立顺推法的基本方程:,将b1,b2,b3代入上式,并依次回代,得 u3=110.5，s2=9.5，u2=110，s1=9.5,u1=109.5 全期的最小总成本为 f3(s3)=36319.5.,n个阶段

24、的生产与存储问题,设第k阶段对产品的需求量dk，生产量uk，库存费hk(uk)。初始库存量s0=0，第n阶段末存货sn=0。在保证供应下，问如何安排生产,使总成本最小.sk为第k阶段末的库存量，则有sk-1=sk-uk+bk，ck(uk)为第k阶段生产产品uk时的成本，即,其中K为生产准备成本，a为单位产品成本，m为每阶段最多能生产该产品的上限.,fk(sk)表示从第1阶段到第k阶段按最优策略安排生产的最小总成本.则顺序递推式为:,注1.若每阶段生产产品的数量无上限的限制，则只要改变ck(uk)，即,例3.书P225例3.,注2.如果对每个i，都有si-1ui=0，则称该点的生产决策(或称一个

25、策略u=u1,u2un)具有再生产点性质。如果si=0，则称阶段i为再生产点。若库存问题的目标函数g(x)在凸集S上是凹（或凸）函数，则g(x)在S的顶点上具有再生产点性质的最优策略。设c(j,i)(ji)为阶段j到阶段i的总成本，给定j-1和i是再生产点，并且阶段j和阶段i期间的产品全部由阶段j供给。则,设最优值函数fi表示在阶段i末库存量si=0时，从阶段1到阶段i的最小成本.则递推式为:,设j(n)为计算fn时，使（8.6）式右边最小的j 值，即,则从阶段j(n)到阶段n的最优生产决策为:,故j(n)-1为再生产点。记 m=j(n)-1，而j(m)是在计算fm时，使（8.6）式右边最小的

26、j 值，则从阶段j(m)到阶段j(n)的最优生产决策为：,故j(m)-1为再生产点,其余依此类推。,例4.利用再生产点性质解例3。,例5、设备更新问题,某企业在今后4年内需使用一辆卡车.现有一辆已使用2年的旧车,根据统计资料分析,预计卡车的年收入、年维修费(包括油料等费)、一次更新重置费及4年后残值如下表所示，表中k=1,2,3,4.试确定4年中的最优更新计划,以使总利润最大.,解.设状态变量sk表示第k年初机器的役龄;决策变量uk表示第k年初对役龄sk的机器采用的决策,则 ukDk=(更新)R，(继续使用)K.状态转移方程：,t5(s5)表示第5年初役龄为s5的机器残值;rk(sk)为第k年

27、初役龄为sk的机器继续使用一年的年收入;yk(sk)表示第k年初役龄为sk的机器继续使用一年的年维修费(包括因维修而减少生产所引起的损失);,ck(sk)表示第k年初对役龄为sk的机器进行更新时一次性以旧换新的费用(购买和安装新机器费用与旧机器残值之差).第k年的年利润为:设fk(sk)表示第k年至第4年内,期初有一台役龄为sk的机器,采用最优更新策略所能获得的最大利润,则有,计算结果:表1 表2(k=4),表3(k=3)表4(k=2),k=1时f1(s1=2)=28,u*1=s1.最优策略为 K,R,K,K,最大年利润28个单位.,例6、资源分配问题,设有某种原料,总数量为a,用于生产n种产

28、品.若分配数量xi用于生产第i种产品.其收益为gi(xi).问应如何分配,才能使生产n种产品总收益最大?此问题可写成静态规划,对某些静态问题可用动态规划来求解,把依次决定各个变量的取值看成是一个多阶段的决策过程,因而模型中有多少个变量,求解就分多少个阶段.约束条件的右端项表明可分配的资源量,用状态变量表示,而约束条件的个数则是状态变量的维数.,解.设状态变量sk表示分配用于生产第k种产品至第n种产品的原料数量;决策变量uk表示分配给生产第k种产品的原料数，即uk=xk.允许决策集合为Dk：0uksk.状态转移方程为 sk+1=sk-uk=sk-xk，s1=a,k=1,2,n.,令fk(sk)表

29、示以sk的原料分配给第k种产品至第n种产品所得的最大总收益.则动态规划的逆推关系式为：,利用此逆推式逐段计算,求得f1(a)即为所求最大总收益.例如：g1(x1)=4x12，g2(x2)=-x22，g3(x3)=2x32+12，a=10，n=3，其中生产第2种产品实际上不盈利.问应如何分配,才能使生产n种产品总收益最大?最优解：x3=x2=0，x1=10，zmax=f1(10)=412.,例7、一般数学规划模型的动态规划解法,分别用动态规划的逆序解法和顺序解法求解下述非线性规划问题:,解.按(MP)中变量的个数分为三个阶段,xk为第k阶段的决策变量.设状态变量为sk.各阶段指标函数按乘积方式结

30、合.,法1.逆序解法.设s112，s2=s1-x1，s3=s2-3x2，s4=s3-2x3，则各决策变量的取值为0 x1s1，0 x2s2/3，0 x3s3/2.,令最优值函数fk(sk)表示第k阶段的初始状态为sk,从第k阶段到n=3阶段的最大值，则有逆推法的基本方程:,从第3阶段开始,向前递推计算.,法2.顺序解法.,设s412，s3=s4-2x3，s2=s3-3x2，s1=s2-x1，则各决策变量的取值为0 x1s2，0 x2s2/3，0 x3s4/2.,令最优值函数fk(sk+1)表示第k+1阶段的初始状态为sk+1，从第1阶段至k阶段的最大值，则有顺推式:,从第1阶段开始,向后递推计

31、算.,若设s1=x1，s1+3x2=s2，s2+2x3=s312，则各决策变量的取值为x1=s1，0 x2s2/3，0 x3s3/2.,例8、随机性的动态规划问题,某公司承担一种新产品试制任务,合同要求三个月内交出一台合格的样品,否则将负担1500元的赔偿费.据专家估计，试制时每投产一台合格的概率为1/3，投产一批的准备结束费用为250元，每台试制费用为100元.若投产一批后全部不合格，可再投一批试制，但每投一批的周期需一个月.要求确定每批投产多少台，使总的试制费用(包括可能发生的赔偿费)的期望值最小.解.投产一批的周期为一个月,作为一个阶段.设状态变量sk.假定尚没有一台合格品时sk=1,已

32、得到一台以上合格品时sk=0.故签定合同时有s1=1.决策变量uk为每个阶段的投产试制台数.,允许决策集合为Dk(sk)=1,2,N(当sk=1),Dk(sk)=0(当sk=0).状态转移方程为:,第k阶段的费用支出为:,设fk(sk)为从状态sk、决策uk出发的k阶段以后的最小期望费用.因有fk(0)=0，故有,计算过程如下：,表 1(k=3),表 2(k=2),最优决策：第一批投产3台；若无合格品,第二批再生产3台；若仍然全部不合格,第三批投产4台.这样使总的期望研制费用(包括三批不合格时的赔偿费)为最小,共计796元.,表 3(k=1),例9、背包问题,某工厂生产三种产品,各种产品的重量

33、(吨/件)与利润(元/件)如下表所示.现将此三种产品运往市场出售,运输能力总重量不超过6吨.问应如何安排运输使总利润最大.解.以装运第k种产品为 第k阶段(k=1,2,3).设状态变量sk为表示可用于装载前k种货物的载重量;决策变量uk表示装载第k种货物的件数;ak为第k种货物的单件重量;,ck为每装一件第k种货物所得的利润;vk(sk,uk)表示装载uk件第k种货物所得的利润;,fk(sk)表示装载能力为sk时,采取最优策略装载前k种货物所得的最大利润.Dk(sk)=0,1,sk/ak,k=1,2,3.,状态转移方程为 sk=sk-1+akuk，s0=0，k=1,2,3 建立顺推法的基本方程

34、:,计算结果:表 1(k=1),表 2(k=2),s2=0,1,2,3时,D2(s2)=0;s2=4,5,6时,D2(s2)=0,1,表 3(k=3),最优解:(1).u1=u2=0,u3=2；(2).u1=u2=1,u3=0.fmax=260(元),k=3:s3=0,1,2时,D3(s3)=0;s3=3,4,5时,D3(s3)=0,1;s3=时,D3(s3)=0,1,2,例如：某工业部门拟将某种高效率的设备五台，分配给所属的甲、乙、丙三个工厂.预测各工厂使用这种设备的盈利预测值如表1所示.问应如何将设备分配给各工厂,才能总盈利最大?,解.按甲、乙、丙工厂分为三个阶段，编号为k=1,2,3.设sk表示分配给第k个工厂至第n个工厂的设备台数；xk表示分配给第k个工厂的设备台数，则 sk+1=sk-xk；,表1,表1,fk(sk)表示sk台设备分配给第k个工厂至第n个工厂时所得的最大盈利值.因而动态规划的逆推关系式为：,下面从最后一个阶段开始向前逆推计算.(教材P213),gk(sk)表示xk台设备分配到第k个工厂所得盈利值.,