运筹学5(动态规划).ppt

《运筹学5(动态规划).ppt》由会员分享，可在线阅读，更多相关《运筹学5(动态规划).ppt（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章第七章 动态规划动态规划.1.1动态规划动态规划问题问题和基本概念和基本概念.2.2 动态规划的基本原理动态规划的基本原理.3 .3 动态规划的应用动态规划的应用 引言引言 动态规划与多阶段决策：动态规划与多阶段决策：多阶段决策是指这样一类特殊的活动过程,它们可以按时间顺序分解成若干相互联系的阶段,每个阶段都要作出决策,全部过程的决策是一个决策序列,所以多阶段决策问题又称为序贯决策问题。多阶段决策的目标多阶段决策的目标是要达到整个活动过程的总体效果最优,所以多阶段决策又叫做过程最优化。所谓动态规划，动态规划，就是解决多阶段决策和过程最优化问题的一就是解决多阶段决策和过程最优化问题的一种规

2、划方法。种规划方法。例.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

3、),(A,B2)和(A,B3),第二阶段有9条路线，第3 阶段有6条路线,第4 阶段有2 条路线。12342 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)当各阶段的状态确定以后，就可以做出不同的决定或选择，从而确定下一阶段的状态，这种决定就是决策，表示决策的变量称为决策变量。常用kX

4、（ks）表示第K阶段当状态为ks时的决策变量，在例.1中第二阶段如决定从B1出发，即S2=B1，可选择走C1或C2，C3，如果我们选择，从C2走，则此时的决策变量可表示x2(B1)=C2。12344 4）、策略（）、策略（Policy）在各阶段决策确定以后，整个问题的决策序列就构成了一个策略,用P1n(s1)表示。如对于例.1总共可有18个策略，但最优策略只有一个。12345 5）、目标函数）、目标函数 用于衡量所选定策略优劣的数量指标称作目标函数。一个n阶段的决策过程，从1到n 叫作问题的原过程。目标函数的最优值称为最优目标函数，最优目标函数记为fk(sk)，它表示从第K阶段的状态Sk出发采

5、用的最优策略。当K=1时,f1(s1)就是从初始状态S1到全过程结束的整体最优目标函数。,在例.1中，目标函数就是距离。如在第2阶段，状态为B2时，f2(B2)则表示从B2到E的最短距离。本问题的总目标是求f 1(A),即从A到E的最短距离。12346 6）、）、状态转移方程状态转移方程在动态规划中，本阶段的状态往往是上阶段决策的结果。所以如果给定了第K阶段的状态ks和该阶段的决策kx(ks)，则第K+1段的状态1+ks由于K阶段决策的完成也就完全确定了,它们之间的关系可用如下公式表示：1+kskT（ks，kx）其中，kT表示从状态ks出发经过kx向下一阶段的转移(Transfer)，换言之，

6、即1+ks是从状态ks出发经过决策kx转移的结果。由于上式表示了由K段到第K+1段的状态转移规律，所以就称为状态转移方程。在例.1中,状态转移方程即1+kskx。为了求出例.1的最短路线,一个简单的方法是,可以求出所有从A到E的可能走法的路长并加以比较。不难知道,从A到E共有18条不同的路线,每条路线有四个阶段,要做3次加法,要求出最短路线需做54次加法运算和17次比较运算,这叫做穷穷举法举法。当问题的段数很多,各段的状态也很多时,这种方法的计算量会大大增加,甚至使得寻优成为不可能。下面应用动态规划方法求解例.1。运用逆序递推方法求解,即由最后一段到第一段逐步求出各点到终点的最短路线,最后求出

7、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时的两点距离。3f（1C）min+)(),()(),(24211411DfDCdDfDCd=min+

8、3543=7这说明,由1c到E 的最短距离为7,其路径为以1C1DE,相应的决策为*3x（1C）=1D1234S1S2S3S4+)(),()(),(24221412DfDCdDfDCd 3f（2C）min=min+3246=5即从C2到E的最短距离为5,其路径为2C2DE,相应的决策为*3x（2C）=2D1234S1S2S3S4即从C3到E的最短距离为5,其路径为C3D1E,相应的决策为*3x（3C）=1D。3f（3C）min+)(),()(),(24231413DfDCdDfDCd=min+3341=51234S1S2S3S4第三步第三步,K=2由于第 3段各点C1,C2,C3到终点E的最短

9、距离f3(C1),f3(C2),f3(C3),已知,所以要求城市B1到E的最短距离,只需以它们为基础,分别加上B1到达C1,C2,C3的一段距离,加以比较取其最短者即可。即B1到终点E的最短距离为9,其路径为B1C2D2E,本段的相应决策为*2x（1B）=2C )(12Bf=min+)(),()(),()(),(333123211311CfCBdCfCBdCfCBd=min+555476=91234S1S2S3S4同理有:)(22Bf=min+)(),()(),()(),(333223221312CfCBdCfCBdCfCBd=min+565778=11 即*2x（2B）3CB2C3 D1 E

10、1234S1S2S3S4+)(32Bf=min+)(),()(),()(),(333323231313CfCBdCfCBdCfCBd=min+595877=13 即*2x（3B）2C1234S1S2S3S4B3C2 D2 E第四步第四步,K=1,只有一个状态点A,则 )(1Af=min+)(),()(),()(),(333232121BfBAdBfBAdBfBAd=min+13511998=171234S1S2S3S4从城市A到城市E的最短距离为17。把各段的最优决策按计算顺序反推,即得到最优决策序列,即*1x（A）1B,*2 x（1B）=2C,*3 x（2C）2D，*4x（2D）E，所以最短

11、路线为:AB1C2D2E.1234 图例.1各点到终点的最短路径根据例.1,动态规划的基本思想可总结如下：一、将多阶段决策过程划分阶段,恰当地选取状态变量,决策变量和定义最优目标函数,从而把问题化成一族同类型的子问题，然后逐个求解。二、求解时从边界开始，沿过程行进方向，逐段递推寻优。在每一个子问题求解时,都要利用它前边已求出的子问题的最优结果,最后一个子问题的最优解,就是整个问题的最优解。三、动态规划方法是既把当前一段与未来各段分开,又把当前效益和未来效益结合起来考虑的一种最优化方法,因此,每段的最优决策的选取都是从全局考虑的,它与该段的最优选择是不同的。在例.1的求解过程中,各段的计算都利用

12、了第K段和第K+1段的如下关系：kf（ks）minkd（ks，sk+1）)(11+kksf (k=4,3,2,1)(1)(55sf 0 (2)这种递推关系称为动态规划的基本方程动态规划的基本方程,(2)式称边界条件,容易算出,运用动态规划方法解例.1 只进行了17次加法运算,11 次比较运算，就获得了最优解,比穷举法的计算量明显地要少,而且随着问题段数的增加和变量程度的提高,计算量将呈指数规律减少。其次,动态规划的计算结果不仅得到了A到E的最短路线,而且得到了任意一点到E点的最优路线。这可由图.2 来描述(用彩色线表示最优路线,各点上的数字表最短距离).2.1 最优化原理最优化原理 动态规划方

13、法是由美国数学家贝尔曼(R.Bellman)等人于本世纪50年 代提出的。他们针对多阶段决策问题的特点,提出了解决这类问题的”最优 化原理”,并成功地解决了生产管理、工程技术许多方面的实际问题。最优化 原理可以表述为：“一个过程的最优策略具有这样的性质,即无论初始状态 和初始决策如何,对于先前决策所形成的状态而言,其以后的所有决策必构成 最优策略。”.2 动态规划的基本原理动态规划的基本原理简言之：最优策略的任一子策略都是最优的。如果把最优化原理用数学语言描述,就得到了动态规划的基本方程：kf（ks）opt)(),(11+kkkkksfxsd (k=n,n-1,1)1+kf（1+ks）0 其中

14、,opt 可依题意取max或min7.2.2 动态规划求解的基本步骤 求解动态规划,就是分析问题并建立问题的动态规划基本方程。成功地应用动态规划方法的关键;在于识别问题的多阶段特征,将问题 分解成可用递推关系式联系起来的若干子问题,或者说是要正确地建立具 体问题的基本方程。而正确地建立关于递推关系基本方程的关键，又 在于正确地选择状态变量保证各阶段的状态变量具有递推的状态转移关系。1+ks),(kkkxsT。这是建立动态规划模型的两个要点。1234S1S2S3S4例P184 某公司有资金万元，拟投资于个项目，其收益分别为可建立以下模型：7.2.2 动态规划求解的基本步骤 2.状态变量ks：表示

15、第K段可用于剩余的n-k+1个项目的资金数,显然有1s=10,4s=0。3.决策变量kx：即应分配第K个项目上的投资额。1.阶段：K=1，2，4.状态转移方程：kkkxss-=+1 5.最优目标函数kf（ks）：表示当可投资金数为ks时,投资于剩余的 n-k+1个项目的最大收益。6.基本方程为：=+=+0)()()(max)(1111nnkkkkkksfsfxgsf k=3,2,1 (逆序解法)投资问题:设总投资额为A万元,拟投资于n个项目上，已知对第i个项目投 资ix万元,收益函数为)(iixg,问应如何分配资金才可以使总收益最大?这是一个与时间无明显关系的静态最优化问题,可先列出其静态模型

16、为：为了应用动态规划方法求解,我们可以人为地赋予它“时段”的概 念。方法是将投资项目排序,假想对各个投资项目有先后顺序。首先考 虑对项目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

17、.最优目标函数kf（ks）：表示当可投资金数为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

18、=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再由状态转移方程逆

19、推：逆序解法的过程见书 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,

20、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时的结果如下表:

21、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

22、的可取值为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背包问题背包问题是动

23、态规划的典型问题。一维背包问题的典型提法是：一位旅行者能承受的背包最大重量是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

24、-=+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+0

25、5+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+013247.3.3 生产与存储问题 例 7.6 某厂生产的一种产品，以后四个月的订单如下表：月份1234订货量（bk)3324合同规定在各月底前交货，生产每批产品的固定成本为3千元，每批生产的产品件数不限。每件产品的可变成本为1千元，每批产品的最大生产能力为5件。产品每件每月的存储费为500元。又知

26、1月初有库存产品1件，4月底不再留下产品。试在满足需要的前提下，如何组织生产才能使总的成本最低。解：1.设阶段变量为K,则每月为一个阶段,K=1,2,3,40 xk5,4.状态转移方程由下式确定：1+ks kkkbxs-+其中,kd表示第K阶段的产品总成本，即),(kkkxsd=+)0(0.5sk)50(3kkxxxk+0.5sk2.每月初的产品库存量作为状态变量，由已知条件显然有S1=1，S5=03.决策变量是每月的产品生产量，由已知条件知：5.建立基本方程（即成本最小化）)(),(min)(11+=kkkkkUkksfxsdsfk（k=4,3,2,1）0)(55=sf当K=4时，S4的最小

27、可能值为0，即4月初没有存货。S4的最大可能值=531（3 3 2），4=4即 S4=0，1，2，3，4。（K=4）s4本阶段费用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+40726

28、1353+50835.513.5113+10.54.50711.510.523+20.55.516.51233+30.56.52612.543+40.57.535.51353+50.58.54210.5s3本阶段费用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+22742950

29、02.52.535.58813+12.56.5428.5s2本阶段费用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.5s1本阶段费用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.51234