第七章第七章 动态规划划.1.1动态规划问题和根本概念动态规划问题和根本概念.2 .2 动态规划的根本原理动态规划的根本原理.3 .3 动态规划的运用动态规划的运用 .引言引言 动态规动态规划与多划与多阶阶段决策：段决策：多阶段决策是指这样一类特殊的活动过程, 它们可以按时间顺序分解成假设干相互联络的阶段, 每个阶段都要作出决策, 全部过程的决策是一个决策序列, 所以多阶段决策问题又称为序贯决策问题。多阶段决策的目的多阶段决策的目的是要到达整个活动过程的总体效果最优, 所以多阶段决策又叫做过程最优化。所谓动态规划，动态规划， 就是处理多阶段决策和过程最优化问题的一就是处理多阶段决策和过程最优化问题的一种规划方法。种规划方法。 .例.1 最短路问题 设A地的某一企业要把一批货物由A地运到E城销售, 其间要经过八个城市,各城市间的交通道路及间隔如以下图所示, 问应选择什么道路才干使总的间隔最短? .1 .1 动态规划问题和根本概念动态规划问题和根本概念例中，道路图(共18条道路,3321=18).枚举法：例中，道路图(共18条道路,3321=18).为处理这个最短途径问题，首先给出几个定义。1 1、阶段、阶段(stage) 将所给问题的过程，按时间或空间特征分解成假设干相互联络的段落，以便按次序求解就构成了阶段 ,阶段变量常用字母K来表示。如例 .1有四个阶段，K就等于1,2,3,4。第一阶段共有3 条道路即(A,B1), (A,B2)和(A,B3),第二阶段有9条道路，第3 阶段有6条道路,第4 阶段有2 条道路。1234.2 2、 形状形状 ( state)各阶段开场时的出发点称作形状。 描画各阶段形状的变量，称作形状变量，用sk 表示。 在例.1 中，第一阶段的形状为 A，第二阶段的形状为城市 B1，B2和B3。 所以形状变量 S1的集合S1=A,S2的集合是S2=B1,B2,B3,依次有S3=C1,C2,C3, S4=D1,D2。1234. 3 3、 决策决策Decision ) Decision ) 当各阶段的形状确定以后，就可以做出不同的决议或选择，从而确定下一阶段的形状，这种决议就是决策，表示决策的变量称为决策变量。常用kXks表示第K阶段当形状为ks时的决策变量， 在例.1中第二阶段如决议从B1出发，即S2=B1，可选择走C1或C2，C3 ，假设我们选择，从C2走，那么此时的决策变量可表示x2(B1)=C2。1234.4 4、战略、战略 Policy Policy 在各阶段决策确定以后，整个问题的决策序列就构成了一个战略在各阶段决策确定以后，整个问题的决策序列就构成了一个战略, ,用用P1n(s1)P1n(s1)表示。表示。 如对于例.1总共可有18个战略，但最优战略只需一个。1234.5 5、目的函数、目的函数 用于衡量所选定战略优劣的数量目的称作目的函数。一个用于衡量所选定战略优劣的数量目的称作目的函数。一个n n阶阶段的决策过程，从段的决策过程，从1 1到到n n 叫作问题的原过程。叫作问题的原过程。 目的函数的最优值称为最优目的函数，最优目的函数记为目的函数的最优值称为最优目的函数，最优目的函数记为fk(sk)fk(sk)，它表示从第，它表示从第K K阶段的形状阶段的形状SkSk出发采用的最优战略。出发采用的最优战略。 当当K=1K=1时时, f1(s1 ), f1(s1 )就是从初始形状就是从初始形状S1S1到全过程终了的整体最优到全过程终了的整体最优目的函数。目的函数。 , .在例.1中，目的函数就是间隔。如在第2阶段，形状为B2时，f2 (B2)那么表示从B2到E的最短间隔。本问题的总目的是求f 1(A), 即从A到E的最短间隔。1234.6 6、 形状转移方程形状转移方程在动态规划中，本阶段的形状往往是上阶段决策的结果。所以假设给定了第K阶段的形状ks和该阶段的决策kx(ks)，那么第K+1段的形状1+ks由于K阶段决策的完成也就完全确定了 ,它们之间的关系可用如下公式表示： 1+kskTks，kx其中，kT表示从形状ks出发经过kx向下一阶段的转移(Transfer)，换言之，即1+ks是从形状ks出发经过决策kx转移的结果。由于上式表示了由K段到第K+1段的形状转移规律，所以就称为形状转移方程。在例 .1中,形状转移方程即1+kskx。 . 为了求出例.1的最短道路,一个简单的方法是,可以求出一切从A到E的能够走法的路长并加以比较。不难知道,从A到E共有18条不同的道路,每条道路有四个阶段,要做3次加法,要求出最短道路需做54次加法运算和17次比较运算,这叫做穷举法。 当问题的段数很多,各段的形状也很多时,这种方法的计算量会大大添加,甚至使得寻优成为不能够。 . 下面运用动态规划方法求解例.1。运用逆序递推方法求解,即由最后一段到第一段逐渐求出各点到终点的最短道路,最后求出A点到E点的最短道路。 运用逆序递推方法的益处是可以一直盯住目的,不致脱离最终目的。 例.1是一个四阶段决策问题,普通可分为四步：1234.第一步第一步,从从K=4开场开场 1234S1S2S3S4逆序法求解最短路问题形状变量S4可取两种形状D1, D2,它们到E点的间隔分别为4和3,这也就是由D1和D2到终点E 的最短间隔， 即 f4(D1)=4, f4(D2)=3.第二步第二步 ,K=3形状变量S3可取3个值即C1,C2和C3。为方便运用，规定用d(sk，sk+1)表示由形状sk出发，到达下一阶段sk+1时的两点间隔。 3f1Cmin+)(),()(),(24211411DfDCdDfDCd=min+3543=7这阐明,由1c到E 的最短间隔为7,其途径为以1C1DE,相应的决策为*3x1C=1D1234S1S2S3S4.+)(),()(),(24221412DfDCdDfDCd 3f2Cmin=min+3246=5即从C2到E的最短间隔为5,其途径为2C2DE,相应的决策为*3x2C=2D1234S1S2S3S4.即从C3到E的最短间隔为5,其途径为C3D1E,相应的决策为*3x3C=1D。 3f3Cmin+)(),()(),(24231413DfDCdDfDCd=min+3341=51234S1S2S3S4.第三步第三步, K=2, K=2由于第 3段各点C1,C2,C3到终点E的最短间隔f3(C1),f3(C2), f3(C3),知,所以要求城市B1到E的最短间隔,只需以它们为根底,分别加上B1到达C1,C2,C3的一段间隔,加以比较取其最短者即可。即B1到终点E的最短间隔为9,其途径为B1C2D2E,本段的相应决策为*2x1B=2C )(12Bf=min+)(),()(),()(),(333123211311CfCBdCfCBdCfCBd=min+555476=91234S1S2S3S4.同理有: )(22Bf=min+)(),()(),()(),(333223221312CfCBdCfCBdCfCBd=min+565778=11 即*2x2B3CB2C3 D1 E1234S1S2S3S4.+ )(32Bf=min+)(),()(),()(),(333323231313CfCBdCfCBdCfCBd=min+595877=13 即*2x3B2C1234S1S2S3S4B3C2 D2 E.第四步第四步, K=1, 只需一个形状点A,那么 )(1Af=min+)(),()(),()(),(333232121BfBAdBfBAdBfBAd=min+13511998=171234S1S2S3S4.从城市A到城市E的最短间隔为17。把各段的最优决策按计算顺序反推,即得到最优决策序列,即*1xA1B,*2 x1B=2C,*3 x2C2D，*4x2DE，所以最短道路为:AB1C2D2E.1234. 图例.1各点到终点的最短途径根据例 .1, 动态规划的根本思想可总结如下：一、 将多阶段决策过程划分阶段,恰当地选取形状变量,决策变量和定义最优目的函数,从而把问题化成一族同类型的子问题，然后逐个求解。二、 求解时从边境开场， 沿过程行进方向，逐段递推寻优。在每一个子问题求解时,都要利用它前边已求出的子问题的最优结果,最后一个子问题的最优解,就是整个问题的最优解。三、 动态规划方法是既把当前一段与未来各段分开,又把当前效益和未来效益结合起来思索的一种最优化方法,因此,每段的最优决策的选取都是从全局思索的,它与该段的最优选择是不同的。.在例.1的求解过程中 , 各段的计算都利用了第K段和第K+1段的如下关系：kfksminkdks，sk+1 )(11+kksf (k=4,3,2,1) (1)(55sf 0 (2)这种递推关系称为动态规划的根本方程动态规划的根本方程 ,(2)式称边境条件,容易算出,运用动态规划方法解例 .1 只进展了17次加法运算,11 次比较运算，就获得了最优解,比穷举法的计算量明显地要少,而且随着问题段数的添加和变量程度的提高,计算量将呈指数规律减少。其次,动态规划的计算结果不仅得到了A到E的最短道路,而且得到了恣意一点到E点的最优道路。这可由图 .2 来描画(用彩色线表示最优道路,各点上的数字表最短间隔).2.1 最优化原理最优化原理 动态规划方法是由美国数学家贝尔曼(R.Bellman)等人于本世纪50年 代提出的。他们针对多阶段决策问题的特点,提出理处理这类问题的 最优 化原理 ,并胜利地处理了消费管理、工程技术许多方面的实践问题。最优化 原理可以表述为：“一个过程的最优战略具有这样的性质 , 即无论初始形状 和初始决策如何,对于先前决策所构成的形状而言,其以后的一切决策必构成 最优战略。 .2 动态规划的根本原理划的根本原理简言之：最优战略的任一子战略都是最优的。. 假设把最优化原理用数学言语描画,就得到了动态规划的根本方程： kfks opt)(),(11+kkkkksfxsd (k=n,n-1,1) 1+kf1+ks0 其中,opt 可依题意取max或min.7.2.2 动态规划求解的根本步骤 求解动态规划 , 就是分析问题并建立问题的动态规划根本方程。 胜利地运用动态规划方法的关键 ;在于识别问题的多阶段特征 ,将问题 分解成可用递推关系式联络起来的假设干子问题 ,或者说是要正确地建立具 体问题的根本方程。而正确地建立关于递推关系根本方程的关键，又 在于正确地选择形状变量保证各阶段的形状变量具有递推的形状转移关系。 1+ks),(kkkxsT。 这是建立动态规划模型的两个要点。 1234S1S2S3S4.例P184 某公司有资金万元，拟投资于个工程，其收益分别为可建立以下模型：7.2.2 动态规划求解的根本步骤 . 2. 形状变量ks：表示第K段可用于剩余的n-k+1个工程的资金数, 显然有1s=10, 4s=0 。 3. 决策变量kx： 即应分配第K个工程上的投资额。 1.阶段：K=1，2，4. 形状转移方程：kkkxss-=+1 5. 最优目的函数kfks：表示当可投资金数为ks时,投资于剩余的 n-k+1个工程的最大收益。 6. 根本方程为： =+=+0)()()(max)(1111nnkkkkkksfsfxgsf k=3,2,1 (逆序解法).投资问题: 设总投资额为A万元, 拟投资于n个工程上，知对第i个工程投 资ix万元,收益函数为)(iixg,问应如何分配资金才可以使总收益最大 ? 这是一个与时间无明显关系的静态最优化问题 ,可先列出其静态模型为： 为了运用动态规划方法求解, 我们可以人为地赋予它“时段的概 念。方法是将投资工程排序, 假想对各个投资工程有先后顺序。 首先考 虑对项目1的投资, 然后思索对工程2的投资, 依次最后思索第n项 投资.这样就把原问题转化为n阶段的决策过程。接下来的问题，便是如 何选择正确的形状变量,并使各后部子过程间具有递推关系。 Max V=niiixg1)( s.t. Axnii=1 0ix (i=1,2,n) .2. 形状变量ks：表示第K段可用于剩余的n-k+1个工程的资金数, 显然有1s=A, 1+ns=0。 3. 决策变量kx： 即应分配第K个工程上的投资额。 1.阶段：K=1，2，n4. 形状转移方程：kkkxss-=+1 5. 最优目的函数kfks：表示当可投资金数为ks时,投资于剩余的 n-k+1个工程的最大收益。 6. 根本方程为： =+=+0)()()(max)(1111nnkkkkkksfsfxgsf k=n,n-1,2,1 假设运用逆序递推寻优, 那么)(1s1f就是所求的最大收益。 .7.2.3 动态规划求解时的几种常用算法离散变量的分段穷举法如最短路问题的解法, 离散型资源分配问题等延续变量的解法根据方程的详细情况灵敏选取求解方法a.逆序解法b.顺序解法如延续型资源分配问题等.例用动态规划方法求解以下问题解：采用逆序解法顺序解法的根本方程为： =+=+0)()()(max)(144k+1kkkkksfsfxgsf k=3,2,1.当3时，有可以看到,当 时, f3(s3)获得极大值.当时，有 求其极值点:这是一个极小点, 为什么?所以,极大值只能够在0,s2的端点获得, 那么有.当1时，有分两种情况: 讨论!当 x1=0时, f1(10)=200, 到达最大值.再由形状转移方程顺推,可求出: x2=0 x3=10.例用动态规划方法求解以下问题解：采用顺序解法顺序解法的根本方程为： =+=0)()()(max)(1kkkkkksfsfxgsf k=3,2,1.当时，有.当时，有.当3时，有记求导，得解得此点仅为极小点.极大值应在0，s4=0，10的端点获得当x3=0时，f3 (10)=90当x3=10时，f3 (10)=200再由形状转移方程逆推： 逆序解法的过程见书 P.3.1 资源分配问题 例 某企业共有设备5台,拟分给三个工厂,各工厂利用这些设备 为企业可提供的盈利 kk(x )g各不一样 ( 见表.4) ,问应如何分配这四台 设备才干使企业获得的盈利最大? .3 动态规划运用划运用举例例 表 .4 有关资料 单位：万元 设备分配数 )(11xg )(22xg )(33xg 0 1 2 3 45 0 3 7 9 1213 0 5 10 11 1111 0 4 6 11 1212 甲厂乙厂丙厂. Max z=3iiixg1)( s.t. 5xnii=1 0ix (i=1,2,n) 分析: 可建立如下模型.解： 1.将问题按工厂分为三个阶段，k=1,2,3 2.设 xk分配给第k个工厂的设备台数。S1S2S3S4甲厂x1乙厂x2丙厂x33.形状转移方程：Sk+1=Sk - xk知 s1=5 s2=s1-x1 s3=s2-x2. 4.目的函数为: fk(sk)=maxgk(xk)+fk+1(sk+1) k=3,2,1 f4(s4)=0 设备分配数 )(11xg )(22xg )(33xg 0 1 2 3 45 0 3 7 9 1213 0 5 10 11 1111 0 4 6 11 1212 甲厂乙厂丙厂.当K=3时形状变量3s的取值范围为3s0，1，2，3，4,53x的取值范围也是3D0，1，2，3，4, 5 ,33sx =0)(44=sf,K=3时的结果如下表: x3s3f3(s3)=g3(x3)+ f4(s4)f3(s3)x30123450123455.列表计算：046111212012345046111212.当K=2时223xss-=322ssx-= X2s2f2(s2)=g2(x2)+f3(s3)f2(s2)x20123450123450+00+40+60+110+120+125+05+45+65+115+1210+010+410+610+1111+011+411+611+011+411+00051102142 161,2212形状变量的取值范围为 s2=0,1,2,3,4,5,x2的取值范围也是2D0，1，2，3，4, 5 ,.当k=1时，s1=5, x1的可取值为0,1,2,3,4,5计算结果如下： x1s1f1(s1)=g1(x1)+f2(s2)f1(s1)x10123455最优分配方案有两个：x1=0, x2=2, x3=30+213+167+14 9+10 12+5 13+0210，2x1=2, x2=2, x3=1.例 7.5 一运输商拟用一10吨载分量的大卡车装载3种货物, 资料如下表,问应如何组织装载,可使总价值最大? 解： 设装载第三种货物的件数为ix，那么有： Max z=41x+52x+63x s.t. 31x+42x+53x10 0 xi 且为整数 货物编号1 2 3单位分量吨单位价值(百元)3 4 54 5 67.3.2背包问题.背包问题是动态规划的典型问题。一维背包问题的典型提法是：一位游览者能接受的背包最大分量是b千克，现有n种物品供他选择装入背包，第i种物品单件分量为ia千克，其价值(或重要性参数)为ci，总价值是携带数量ix的函数即iixc，问游览者应如何选择所携带物品的件数以使总价值最大? 模型可表述为：=niiixcz1max s.t. bxaniii=1 0ix 且为整数i=1,2,n.段。用动态规划方法来求解1. 阶段k：即需求装入的n种物品的次序,每段装入一种,共n2. 形状变量ks：即在第k段开场时,允许装入前k种物品的总重量，显然有1s=b 3. 决策变量kx：即装入第K种物品的件数4. 形状转移方程：kkkkxass-=+1允许的决策集合是：=kkkkkkasxxsD0|)(且为整数 5. 目的函数是:)=+=+nkSn+1fsfxcsfk+1kkkkk,.,2, 10)(max)(n+11.当K=3时，S3=0，1，2，10 ， f3(S3)=max6x3+0 x3s36x3+0f3(s3)x301201234567891000000666661200000666661200000111112. x2s25x2+ f3(S3)f2(s2)x2012012345678910当K=2时，S2=0，1，2，10， f2(S2)=max6x2+ f3(S3)000000+60+60+60+60+60+125+05+05+05+05+05+65+610+010+010+00000566610111100001000211.当K=1时，S1=10, f1(S1)=max4x1+ f2(S2) x1s14x1+ f2(S2)f1(s1)x1S2012310最优解为： X1*=2, X2*=1, X3*=0 Z*=130+114+68+512+01324.7.3.3 消费与存储问题 例 7.6 某厂消费的一种产品，以后四个月的订单如下表：月份1234订货量bk)3324合同规定在各月底前交货，消费每批产品的固定本钱为3千元，每批消费的产品件数不限。每件产品的可变本钱为1千元，每批产品的最大消费才干为5件。产品每件每月的存储费为500元。又知1月初有库存产品1件，4月底不再留下产品。试在满足需求的前提下，如何组织消费才干使总的本钱最低。.解：1.设阶段变量为K,那么每月为一个阶段,K=1,2,3,40xk5,4. 形状转移方程由下式确定： 1+ks kkkbxs-+ 其中 ,kd表示第K阶段的产品总本钱，即 ),(kkkxsd=+)0(0.5sk)50(3kkxxxk+0.5sk2.每月初的产品库存量作为形状变量，由知条件显然有S1=1，S5=03.决策变量是每月的产品消费量，由知条件知： 5. 建立根本方程即本钱最小化)(),(min)(11+=kkkkkUkksfxsdsfkk=4,3,2,10)(55=sf.当K=4时，S4的最小能够值为0，即4月初没有存货。S4的最大能够值=5313 3 2，4=4即 S4=0，1，2，3，4。 K=4s4本阶段费用s5f5(s5)d+ f5(s5)f4(s4)x4消费费用存储费d(s4,x4)043+4070077133+30.56.5006.56.5223+2160066313+11.55.5005.55.5400220022.当K=3时，S3的最小值=52+16，6=5即 S3=0,1,2,3,4,5 (k=3)s3本阶段费用s4f4(s4)d+ f4(s4)f3(s3)x3消费费用存储费d(s3,x3)023+20507.5121233+30616.512.543+407261353+50835.513.5113+10.54.50711.510.523+20.55.516.51233+30.56.52612.543+40.57.535.51353+50.58.54210.5.s3本阶段费用s4f4(s4)d+ f4(s4)f3(s3)x3消费费用存储费d(s3,x3)20011078813+11516.511.523+216261233+31735.512.243+41842103001.51.516.58813+11.55.52611.523+21.56.535.51233+31.57.5429.540022268813+12635.511.523+2274295002.52.535.58813+12.56.5428.5.s2本阶段费用s3f3(s3)d+ f3(s3)f2(s2)x2消费费用存储费d(s2,x2)033+306012181643+47110.517.553+582816123+20.55.501217.515.533+36.5110.51743+47.52815.553+58.53816.5213+115012171523+26110.516.533+37281543+48381653+594817 (K=2).s2本阶段费用s3f3(s3)d+ f3(s3)f2(s2)x2消费费用存储费d(s2,x2)3001.51.501213.513.513+15.5110.515.523+26.52814.533+37.53815.543+48.54816.553+59.55817.5.s1本阶段费用s2f2(s2)d+ f2(s2)f1(s1)x1消费费用存储费d(s1,x1)123+20.55.501621.521.533+36.5115.52243+47.521522.553+58.5313.522 (K=1)最优消费决策为： x1=2, x2=5, x3=0, x4=4 最优值为21.5.1234.