运筹学-6、动态规划

1、1,第五章 动态规划,所谓多阶段决策问题是有这样一类决策过程,它可以划分为若干个相互联系的阶段，在任一阶段都有若干种方案可供选择，选择哪一种方案需要作出决策，这样就形成一个决策序列，通常称为一种策略。不同的策略就产生不同的效果，在所有可能的策略当中，选择一个效果最好的最优策略，就是解决多阶段决策问题的主要目的。下面通过例子来说明。,第 一 节 多阶段决策过程及实例,2,例1：（最短路问题）设从A地到E地要铺设一条管道，其中要经过若干个中间点(如图)。图中两点之间连线上的数字表示两地间的距离。现在要选择一条铺设管道的路线，使总长度最短。,3,在这个问题中，从A到B1 ,B2 , B3中的哪一个点

2、要作出一项决策，从B1,B2 , B3某点到 C1,C2,C3 中的哪一个点又要作出一项决策等等。所以总共要作出四个决策。因此，我们可以把整个路程分为A,B ( 包括B1,B2 , B3), C (包括C1, C2 , C3),D(包括D1和D2),E四个阶段。这就是一个多阶段的决策问题。,用动态规划求解多阶段决策问题，是把整个问题划分为若干阶段后，依次地为每一个阶段作出最优决策，而每个阶段的最优决策应该是包含本阶段和以后所有各阶段在内的最优决策。因此，在确定了第一个阶段的决策之后，整个问题的最优决策序列也就随之产生。这就是用动态规划解多阶段决策问题的基本思想。,4,以上面的例1来说明动态规划

3、解决问题的思想。设：,Sk第k阶段的起点（状态变量）,d(x, y) 第k阶段的从状态x 到状态y 的“距离”；,fk(sk) 第k阶段从状态Sk出发到终点E的“最短路”。,最短路线的重要特征是：如果最短路线在第k阶段通过点Pk。则由点Pk出发到达终点的这条路线，对于从点Pk出发到达终点的所有可能选择的不同路线来说，必定也是最短路线。,5,例如在最短路问题中，如果找到了从A到E的最短路：,则C2D1E应该是由C2 出发到E点的所有可能不同线路中的最短路线。,最短路线这一特性，启发我们找最短路线的方法：那就是从最后一段开始，用由后向前逐步递推的方法，求出各点到E点的最短路线，最后求得由A点到E点

4、的最短路线。所以动态规划的常用的方法是从终点逐段向始点方向寻找“最短路线” 。如图所示：,行进方向,动态规划寻优途径,6,下面按上述思想，将例1从最后一段开始计算，由后向前逐步推移至A点。,设想有k= 5， f5(E)= 0 。,7,K=4时：,8,9,K=3时：,10,11,12,K=2时：,最优决策：,13,最优决策：,14,最优决策：,15,K=1时：,最优决策：,16,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A (A，B2) B2 (B2，C1) C1 (C1，D1) D1 (D1，E) E 从A到E的最短路径为19，路线为AB 2C1 D1 E,17,(

5、1) 阶段(stage) 把所研究的决策问题，按先后顺序划分为若干相互联系的决策步骤，以便按一定的次序进行求解。描述阶段的变量称阶段变量，常用k表示.,(2)状态(state)表示系统每个阶段开始时所处的自然状况或客观条件，它描述了影响决策的因素随决策进程的变化情况，它既是前面阶段所作决策的结果，又是本阶段作出决策的出发点和依据。描述状态的变量称为状态变量，第k阶段的状态变量常用sk表示。第一阶段状态变量s1是确定的，称初始状态。,第 二节 动态规划的基本概念,18,(3) 决策(decision)表示在某一阶段处于某种状态时， 决策者在若干种方案中作出的选择决定。描述决策的变量称决策变量，第

6、k阶段的决策变量常用uk表示。决策变量的取值范围称为决策集，用Dk(sk)表示。,多阶段决策过程如下：,19,(4)策略（policy）,把从第一阶段开始到最后阶段终止的整个决策过程，称为问题的全过程；而把从第k阶段开始到最后阶段终止的决策过程，称为k子过程。在全过程上，各阶段的决策按顺序排列组成的决策序列:,p1,nu1,u2,un 称为全过程策略，简称策略；而在k子过程上的决策序列 pk,nuk,uk+1,un 称为k子过程策略，也简称子策略。,20,(5)状态转移方程,(6)指标函数和最优值函数 指标函数分为阶段指标函数和过程指标函数。 阶段指标函数是对某一阶段的状态和决策产生的效益值的

7、度量,用vk(sk,uk)表示。,若第k阶段的状态变量值为sk，当决策变量uk的取值决定后，下一阶段状态变量sk+1的值也就完全确定。即sk+1的值对应于sk和uk的值。这种对应关系记为: sk+1= Tk(sk,uk) 称为状态转移方程。状态转移方程描述了由一个阶段的状态到下一阶段的状态的演变规律。,21,过程指标函数是指从第k阶段至第n阶段所包含的各阶段的状态和决策所产生的总的效益值，记为: Vk,nVk,n(sk,uk,sk+1,uk+1,sn,un),定义在全过程上的过程指标函数相当于目标函数,一般记为: V1,nV1,n(s1,u1, sk,uk ,sn,un)，或简记为V1,n,动

8、态规划所要求的过程指标函数应具有可分离性，即可表达为它所包含的各阶段指标函数的函数形式。常见的两种过程指标函数形式是：,22,把过程指标函数Vk,n对k子过程策略pk,n求最优，得到一个关于状态sk的函数，称为最优值函数或贝尔曼函数，记为fk(sk)。即,各阶段指标函数的和:,各阶段指标函数的积:,23,式中的“opt”（optimization）可根据具体问题的实际意义而取min或max（下面我们主要以加法形式讨论）。,或:,也就是说第k阶段从初始状态Sk出发，执行最优决策序列或策略，到达过程终点时，整个k子过程中的最优目标函数值。,24,一、动态规划最优化原理,动态规划最优化原理： “作为

9、整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的各决策必须构成最优策略。”,简单地说就是一个最优策略的子策略也是最优的。,第 三 节 动态规划的最优化原理及求解,25,二、动态规划基本方程,1) 加法型,逆序法:,26,其中：fk(sk)表示第k阶段初始状态为sk 时，k后部子过程的最优准则函数 。,状态转移方程：,（边界条件）,由此得加法型逆序算法的递归方程如下：,27,2) 乘法型,28,状态转移方程：,（边界条件）,动态规划方法的关键在于利用最优化原理给出最优值函数的递推关系式和边界条件，为此，必须先将问题的过程划分为几个相互联系的阶段，适

10、当选取状态变量、决策变量、状态转移方程及最优值函数。从而把一个大问题化成一系列同类型的子问题，然后逐个求解。,由此得乘法型逆序算法的递归方程如下：,29,动态规划建模有以下过程： 将问题划分成恰当的阶段； 正确选择状态变量，使它既能描述过程的演变，又要满足无后效性。 确定决策变量和决策允许集合。 确定状态转移方程。 明确阶段指标、过程指标和最优值函数。,三、动态规划的建模,30,k=n时，动态规划基本方程是,边界条件：,即 ：,逆序地求出最优目标函数值集合和最优决策集合。,仅就逆序法说明求解步骤：,四、动态规划问题求解的一般步骤,31,k = n1时，动态规划的基本方程是,因所有的fn(sn)

11、都已经求出，因此可以根据sn=Tn-1 (sn-1,un-1)就n-1阶段每个可能状态sn-1 ，求出最优决策及相应的最优目标函数值fn-1(sn-1) 。,k = n2时，动态规划的基本方程是,由于fn-1(sn-1)都已经求出，因此可以根据sn-1=Tn-2 (sn-2 ,un-2)就n-2阶段每个可能状态sn-2 ，求出最优决策及相应的最优目标函数值fn-2(sn-2) 。,32,k=1时，动态规划的基本方程是,由于所有的 f2(s2) 都已经求出，因此可以根据 s2=T1(s1,u1)，就阶段1每个可能状态S1 ,求最优决策及相应的最优目标函数值 f1(s1) .,依次下去 .,最后，

12、顺序地求出最优目标值、最优策略和最优路线。,33,解: 按问题的变量个数划分阶段,把它看作一个三阶段决策问题。令变量x1，x2，x3为决策变量。,例2：用逆推解法求解下面问题:,则有：x3=s3, 0 x2s2, 0 x1s1=c,令状态变量为： s3= x3, s2 = x2+x3, s1=c = x1+x2+x3,即 s3= x3, s2 = s3+ x2, s1=c = s2+ x1。,于是状态转移方程为： s3=s2-x2, s2 =s1-x1,34,各阶段指标按乘积方式结合。即令:,由逆推解法：,即最优解 x3*=s3 。,令最优值函数f k(sk)表示第k阶段从初始状态sk出发，从

13、第k阶段到第3阶段所得到的效益最大值。,35,得 和 x2=0(舍去),故 为极大值点，也就是最大值点。,36,同上对h1(s1, x1)求导并令导数等于0可得：,由于s1=c，,37,由s2 =s1x1，,由s3 =s2x2，,因此最优解为：,最大值为：,38,解: 按问题的变量个数划分阶段,把它看作一个三阶段决策问题。令变量x1，x2，x3为决策变量。,例3：用顺推法求解下面问题:,则有：s2=x1 ,s2+x2=s3 ,s3+x3=s4=c x1=s2 ,0 x2s3 ,0 x3s4=c,状态转移方程为： s2=s3-x2, s3=s4-x3,设状态变量为：s2=x1 ,s3=x1+x2

14、 , s4=cx1+x2+x3,39,由顺推解法,最优解:,最优解x1*=s2。,最优值函数f k(sk+1)表示为第k阶段末的结束状态为sk+1，从第1阶段到第k阶段所得到的效益最大值。,40,最优解:,由于s4=c，,由于s3=s4x3*，,41,因此最优解为：,最大值为：,42,解: 按问题的变量个数划分阶段,把它看作一个三阶段决策问题。令变量x1，x2，x3为决策变量；,例4：用顺推法求解下面问题:,设状态变量为s0,3x1=s1, 3x1+2x2=s2, 3x1+2x2+ x3=s39,则: 3x1=s1, s1+2x2=s2, s2+x3=s39,则状态转移方程为：s1=s2-2x

15、2, s2=s3-x3,于是：x1 =s2/3 ,0 x2s2/2,0 x3s3.,43,由顺推解法,即最优解x1=s13。,(它不在决策集内),最优值函数f k(sk)表示为第k阶段的结束状态为sk，从第1阶段到第k阶段所得到的效益最大值。,44,则最大值在端点上，,最大值点为x2=0。故得到：,最优解x2=0。,45,而,最大值点为x3=s3，故得到：,最优解x3=s3 。,故该点为极小点.,46,由于s3不知道，故须再对s3求一次极值，即,反推回去即可得最优解为：由x1*=x2*=0，x3*=9。,最大值为：,47,假设有某种资源的总数量为a(例如原树料、能源、机器设备、劳动力、食品等)

16、，可用于生产n种产品，若生产第j种产品所使用的资源数为xj时，可获得利润为gj(xj)，问如何分配该种资源，使所获得的总利润达到最大。,一、资源分配问题,该问题的数学模型可表示为：,第四节 动态规划应用举例,48,当gj(xj)都是线性函数时，它是一个线性规划问题；当gj(xj)是非线性函数时,它是一个非线性规划问题。但当n比较大时，求解起来是非常麻烦的。由于该问题的特殊性，可以将它看成一个多阶段决策问题，并利用动态规划的方法来求解。,决策变量xk表示生产第k个产品所使用的资源数量，则:,我们将n个产品看作是n个阶段，设状态变量sk表示生产第k个产品至第n个产品所使用的资源数量。,显然状态转移

17、方程为：,49,第k阶段的阶段指标为：,则由动态规划最优化原理，可得动态规划的基本方程为：,最优值函数fk(sk)表示生产第k个产品至第n个产品所使用的资源数量为sk时获得的最大总利润。,50,例1: (投资分配问题)某公司拟将5百万元资金投放到A、B、C三个项目，各项目在获得资金后的收益如下表所示，用动态规划方法求总收益最大的投资分配方案。,51,解：该问题可以作为三阶段决策过程。对A、B、C三个项目分配资金分别形成1，2，3三个阶段。sk表示给项目k分配资金时拥有的资金数。uk表示给项目k分配的资金数（单位：百万元）。状态转移方程是 sk+1=sk-uk。,则递归方程为：,阶段指标gk(u

18、k)表示分配给第k个项目的资金为uk时所获得的收益，最优值函数fk(sk)表示分配给第k个至第3个项目的资金为sk时所获得的最大总收益。,52,（1）K=3时(第3阶段)注意到C的投资额不超过4百万元，,允许状态集合 1, 2, 3, 4 ,即用剩余额S31，2，3，4 投资项目C，得到的收益为：,（2） K=2时(第2阶段)注意到C的投资额至少是1百万元，,允许决策集合 D2(S2)0, 1, , S2-1 ,下面是各种可能方案的列表：,允许状态集合 1, 2, 3, 4，5 ,53,故：,54,（3）K=1时 （第1阶段） S1 5,允许决策集合 D1(S1) 0, 1, 2, 3, 4,

19、55,应用顺序追踪可知，最优方案有两个：,方案 1：,方案 2：,最大收益都为21百万元。,56,二、可回收利用的资源分配问题,设有某种资源，初始的拥有量是s1。计划在A、B两个生产车间连续使用n个阶段。巳知在A车间投入资源x时的阶段收益是g(x)，在B车间投入资源y时的阶段收益是h(y)。投入的资源在生产过程中有部分消耗,已知，每生产一个阶段后，车间A、B的资源回收率分别为a和b，0a，b1。回收的资源下一阶段可继续使用，求使用n个阶段后总收益最大的资源分配方案。,设sj为第j阶段投入A、B两个车间使用的资源数，j=1、2、n。,57,该模型可用动态规划的方法来处理。,设xj为第j阶段投入A

20、车间使用的资源数，投入B车间使用的资源数为yj=sj-xj，j=1、2、n。此问题的静态规划模型为：,58,最优值函数fk(sk)表示第k阶段拥有资源数为sk时，从第k阶段至第n阶段采取最优分配方案进行生产时所获得的最大总收益。,令sk为状态变量，表示在第k阶段投入A、B两个车间使用的资源数，k=1、2、n。,xk为决策变量，表示在第k阶段投入A车间使用的资源数，则yk=sk-xk表示第k阶段投入B车间使用的资源数，k=1、2、n。,状态转移方程为：sk+1=axk+b(sk-xk),59,下面我们对一个具体问题，用此方法求解。,则动态规划的递推公式：,60,例2：(机器负荷分配问题)某公司新

21、购进1000台机床，每台机床都可在高、低两种不同的负荷下进行生产，设在高负荷下生产的产量函数为g(x)=10 x(单位：百件)，其中x为投入生产的机床数量，年完好率为a=0.7；在低负荷下生产的产量函数为h(y)=6y(单位：百件)，其中y为投人生产的机床数量，年完好率为b=0.9。计划连续使用5年，试问每年如何安排机床在高、低负荷下的生产计划，使在五年内生产的产品总产量达到最高。,解：该问题可看作一个5阶段决策问题，一个年度就是一个阶段。,决策变量xk为在第k阶段投入高负荷下生产的机床数。,61,状态转移方方程为：sk+1=axk+b(sk-xk)=0.7xk+0.9(sk-xk),第k年度

22、的产量为：vk(sk,xk)=10 xk+6(sk-xk),则动态规划的基本方程为：,最优值函数 fk(sk) 表示拥有机床数为sk时，从第k年度至第五年度采取最优分配方案进行生产时所获得的最大总产量。,状态变量sk取为第k年度初拥有的完好机床台数。,62,下面第5年度开始，用逆推归纳法进行计算。,因为 是x5的单调增加函数，故最大解为：,1）k=5时，有,相应有,63,2) k=4时，有,因为 是 x4 的单调增加函数，故最大解为：,相应有,64,3) k=3时，有,因为 是 x3 的单调增加函数，故最大解为：,相应有,65,4）k=2时，有,因为 是 x2 的单调减少函数，故最大解为：,相

23、应有,66,5）k=1时，有,因为 是 x1 的单调减少函数，故的最大解为：,相应有,67,即前两年应把年初全部完好机床投入低负荷生产，后三年应把年初全部完好机床投入高负荷生产。这样所得的产量最高，其最高产量为29139百件产品。同时，从求解过程还可反过来确定每年年初的状态，即每年年初所拥有的完好机器台数。已知s1=1000，于是可得：,由于第l阶段的初始状态s1是给定的，即s1=1000， 因此最优目标函数值为 =29139（百件）。,计算结果表明，最优策略为：,68,69,假设有一个企业，要制定某种产品n个时期(例如年、月、周)的生产(或购买)计划，已知初始的存贮量为零，第k个时期市场需求

24、量为dk，每个时期企业的最大产量为M，单位产品的生产成本为a，每次生产的生产准备成本为K。,设xk为第k个时期(阶段)该产品的生产量。,sk为第k个时期(阶段)末该产品的库存量，则有sk=sk-1+xk-dk。,三、 生产与存贮问题,70,ck(xk)表示第k个时期(阶段)该产品产量为xk时的生产成本，它包括生产准备成本K和产品成本axk两项费用，即：,hk(xk)表示在第k个时期(阶段)结束时库存量为sk时所需的存贮费用。,故第k个阶段的总成本费用为：,问如何安排生产(或购买)计划使得n个时期总成本费用最低？,71,上述问题的数学模型为：,72,现在我们用动态规划的顺推归纳法来讨论，把它看作

25、一个n阶段决策问题。令:,最优值函数fk(sk)表示从第1阶段初始库存量为0到第k阶段末库存量为sk时的最小总成本费用。,sk为状态变量，表示第k个阶段末该产品的库存量。,xk为决策变量，它表示第k阶段的生产量。,则状态转移方程为：sk-1=sk-xk+dk。,则其顺序递推关系式：,73,其中k=mindk+sk,M，这是因为一方面在每个阶段企业的最大产量为M；另一方面由于满足每个阶段市场的需求量，因此第k-1阶段末库存量sk-1必须非负，即: sk-1=dk+sk-xk0 , xkdk+sk。,边界条件为 f0(S0)=0.,从边界条件出发，利用上面顺序递推关系式，最后求出的 fn(0) 即

26、为所要求的最小总成本费用。,下面通过一个实际例子计算。,74,例3：某企业通过市场调查，估计今后四个时期市场对某种产品的需要量如下表：,假定不论在任何时期，生产每批产品的生产准备成本为3(千元)，若不生产，则为零；生产单位产品成本费为1(千元)；每个时期生产能力所允许的最大生产量不超过6个单位。则任何时期生产x个单位产品的生产成本为：,若 0 x6 ，则生产成本3十1x 若 x0 ， 则生产成本0,75,又设每个时期末未销售出去的产品，在一个时期内单位产品的库存费用为0.5(千元)，同时还假定第1时期开始之初和在第4个时期之末，均无产品库存。现在我们的问题是：在满足上述给定的条件下，该厂如何安

27、排各个时期的生产与库存，使得n个时期的总成本费用最低？,解：我们将四个时期分为4个阶段，设k为阶段变量， k1，2，3，4。,状态变量为sk表示第k个阶段末该产品的库存量。,决策变量为xk 表示第k阶段的生产量。,则状态转移方程为：sk-1=dk+sk-xk。,76,第k个阶段生产成本为：,第k个阶段结束时库存量为sk所需的存贮费用：,故第k个阶段的总成本费用为：,则其顺序递推关系式：,77,其中k=mindk+sk,6，边界条件为 f0(s0)=0。,1）当k=1时，由于,对s1的可能取值在0至,的值分别进行计算。,78,79,80,2）当k=2时，由于,对s2的可能取值在0至,( s1最大

28、可取到4)的值分别进行计算。,81,82,83,84,85,86,87,3）当k=3时，由于,对s3的可能取值在0至,( s2最大可取到6)的值分别进行计算。,88,89,90,91,92,4）当k=4时，由于要求的第4个阶段结束时的库存量为0，即s4=0，因此只须计算：,93,再按计算的顺序反推回去，可得到每个时期的最优生产决策为：,其相应的最小总成本费用为20.5千元。,94,解：设xi为第i种物品的装入件数，则问题的数学模型为：,有一个徒步旅行者带一背包，它可容纳物品重量的限度为a公斤。设有n种物品可供他选择装入背包中。这n种物品编号为1，2，n。已知第i种物品每件重量为wi公斤，使用价

29、值是携带数量xi的函数ci(xi)。问该旅行者应如何选择携带这些物品的件数,使得总使用价值最大?,四、 背包问题,95,将n种物品划分为n个阶段，,最优值函数fk(sk)表示当总重量不超过sk公斤，背包中只装前k种物品的最大使用价值。,最后得到的fn(a)就是所求的最大价值。,状态变量sk表示装入第1种物品至第k种物品的总重量。,决策变量xk表示装入第k种物品的件数。,则状态转移方程为：sk-1=sk-wkxk,则动态规划的基本方程为：,96,例4：,解: 用动态规划方法来解，问题变为求 f3(10) 。,为此必须先算出f2(10),f2(5),f2(0) 。而,97,98,为此必须先算出f1

30、(10)，f1(6)，f1(5)，f1(2)，f1(1)，f1(0) 。而,99,相应的最优策略为 ，于是得到,100,从而,101,最后得到：,所以最优装入方案为：,最大使用价值为13。,102,某人在退休时可拿到总数为x0的养老金，他估计自己还可活T年，如何利用这笔钱，使得他在T年内消费总效用最大？由于年龄大，不愿意冒险，他打算把钱存入银行(年利率为r ) ，试建立该问题的数学模型。,1、消费模型,设第t年的消费为ct，所获得的效用为U(ct)，xt为第t年所拥有的资金，则可建立该问题的数学模型如下：,五、 宏观经济学中应用模型,103,我们用动态规划来讨论它的求解。 设状态变量xt表示在第t年拥有的资金数。,决策变量ct表示在第t年的消费。,则状态转移方程为：,第t阶段的阶段指标为：,104,最优值函数Vt(xt)表示第t年拥有的资金数为xt时按最优方案消费所获得的最大总效用。,则由动态规划最优化原理，可得动态规划的基本方程为：,105,初始条件x0，边界条件xT+1=0，V(xT+1)