运筹学5(动态规划).ppt
第七章 动态规划,.1动态规划问题和基本概念.2 动态规划的基本原理.3 动态规划的应用,引言,动态规划与多阶段决策：,多阶段决策是指这样一类特殊的活动过程,它们可以按时间顺序分,解成若干相互联系的阶段,每个阶段都要作出决策,全部过程的决策是,一个决策序列,所以多阶段决策问题又称为序贯决策问题。,例.1 最短路问题 设A地的某一企业要把一批货物由A地运到E城销售,其间要经过八个城市,各城市间的交通路线及距离如下图所示,问应选择什么路线才能使总的距离最短?,.1 动态规划问题和基本概念,例中，路线图(共18条路线,3321=18),枚举法：,例中，路线图(共18条路线,3321=18),为解决这个最短路径问题，首先给出几个定义。,1）、阶段,(stage),将所给问题的过程，按时间或空间特征分解成若干相互联系的段落，,以便按次序求解就形成了阶段,阶段变量常用字母,K,来表示,。如例,.1,有四个阶段，,K,就等于,1,2,3,4,。第一阶段共有,3,条路线即,(A,B1),(A,B2),和,(A,B3),第二阶段有,9,条路线，第,3,阶段有,6,条路线,第,4,阶段有,2,条,路线。,2）、,状态,(,state),各阶段开始时的出发点称作状态。,描述各阶段状态的变量，称作状态变量，用sk 表示。,和,B3。,3）、,决策（Decision),当各阶段的状态确定以后，就可以做出不同的决定或选择，从而确,定下一阶段的状态，这种决定就是决策，表示决策的变量称为决策变量。,常,用,k,X,（,k,s,）,表示第,K,阶段当状态为,k,s,时的决策变量,，,在例.1中第二阶段如决定从B1出发，即S2=B1，可选择走C1或C2，C3，如果我们选择，从C2走，则此时的决策变量可表示x2(B1)=C2。,4）、策略（Policy）在各阶段决策确定以后，整个问题的决策序列就构成了一个策略,用P1n(s1)表示。,如对于例.1总共可有18个策略，但最优策略只有一个。,5）、目标函数 用于衡量所选定策略优劣的数量指标称作目标函数。一个n阶段的决策过程，从1到n 叫作问题的原过程。目标函数的最优值称为最优目标函数，最优目标函数记为fk(sk)，它表示从第K阶段的状态Sk出发采用的最优策略。当K=1时,f1(s1)就是从初始状态S1到全过程结束的整体最优目标函数。,在例.1中，目标函数就是距离。如在第2阶段，状态为B2时，f2(B2)则表示从B2到E的最短距离。本问题的总目标是求f 1(A),即从A到E的最短距离。,6）、,状态转移方程,在动态规划中，本阶段的状态往往是上阶段决策的结果。所以如果给,定了第,K,阶段的状态,和该阶段的决策,(,),，则第,K+1,段的状态,由于,K,阶段决策的完成也就完全确定了,它们之间的关系可用如下公式表示：,（,，,）,其中，,表示从状态,出发经过,向下一阶段的转移,(,Transfer),，换,言之，,即,是从状态,出发经过决策,转移的结果。,由于上式表示了由,K,段到第,K+1,段的状态转移规律，所以就称为状态,转移方程。在例,.1,中,状态转移方程即,。,为了求出例.1的最短路线,一个简单的方法是,可以求出所有从A到E的可能走法的路长并加以比较。不难知道,从A到E共有18条不同的路线,每条路线有四个阶段,要做3次加法,要求出最短路线需做54次加法运算和17次比较运算,这叫做穷举法。当问题的段数很多,各段的状态也很多时,这种方法的计算量会大大增加,甚至使得寻优成为不可能。,下面应用动态规划方法求解例.1。运用逆序递推方法求解,即由最后一段到第一段逐步求出各点到终点的最短路线,最后求出A点到E点的最短路线。运用逆序递推方法的好处是可以始终盯住目标,不致脱离最终目标。例.1是一个四阶段决策问题,一般可分为四步：,第一步,从K=4开始,逆序法求解最短路问题,状态变量S4可取两种状态D1,D2,它们到E点的距离分别为4和3,这也就是由D1和D2到终点E 的最短距离，即 f4(D1)=4,f4(D2)=3.,为方便应用，规定用d(sk，sk+1)表示由状态sk出发，到达下一阶段sk+1时的两点距离。,同理有,:,B2C3 D1 E,B3C2 D2 E,第四步,K=1,只有一个状态点,A,则,图,例,.1,各点,到终点,的最短路径,根据例,.1,动态规划的基本思想可总结如下：,在例.1的求解过程中,各段的计算都利用了第,K,段和第,K+1,段的如下,关系：,（,）,min,（,，sk+1,）,(k=4,3,2,1),(1),0,(2),.2.1,最优化原理,动态规划方法是由美国数学家贝尔曼,(R.Bellman),等人于本世纪,50,年,代提出的。他们针对多阶段决策问题的特点,提出了解决这类问题的,”,最优,化原理,”,并成功地解决了生产管理、工程技术许多方面的实际问题。,最优化,原理可以表述为：“一个过程的最优策略具有这样的性质,即无论初始状态,和初始决策如何,对于先前决策所形成的状态而言,其以后的所有决策必构成,最优策略,。”,.2 动态规划的基本原理,简言之：最优策略的任一子策略都是最优的。,如果把最优化原理用数学语言描述,就得到了动态规划的基本方程：,求解动态规划,就是分析问题并建立问题的动态规划基本方程。,成功地应用动态规划方法的关键,;,在于识别问题的多阶段特征,将问题,分解成可用递推关系式联系起来的若干子问题,或者说是要正确地建立具,体问题的基本方程,。,而正确地建立关于递推关系基本方程的关键，又,在于正确地选择状态变量,保证各阶段的状态变,量具有递推的状态转移关系。,。,这是建立动态规划模型的两个要点。,例P184 某公司有资金万元，拟投资于个项目，其收益分别为,可建立以下模型：,1.阶段：K=1，2，,(逆序解法),投资问题:,设总投资额为,A,万元,拟投资于n个项目上，已知对第,i,个,项目投,资,万元,收益函数为,问应如何分配资金才可以使总收益最大,?,这是一个与时间无明显关系的静态最优化问题,可先列出其静态模型为：,1.阶段：K=1，2，n,7.2.3 动态规划求解时的几种常用算法,离散变量的分段穷举法如最短路问题的解法,离散型资源分配问题等,连续变量的解法,根据方程的具体情况灵活选取求解方法a.逆序解法b.顺序解法如连续型资源分配问题等,例用动态规划方法求解下列问题,解：采用逆序解法,顺序解法的基本方程为：,=,+,=,+,0,),(,),(,),(,max,),(,1,4,4,k+1,k,k,k,k,k,s,f,s,f,x,g,s,f,k=3,2,1,当3时，有,当时，有,求其极值点:,这是一个极小点,为什么?,所以,极大值只可能在0,s2的端点取得,则有,当1时，有,分两种情况:讨论!,当 x1=0时,f1(10)=200,达到最大值.,再由状态转移方程顺推,可求出:x2=0 x3=10,例用动态规划方法求解下列问题,解：采用顺序解法,顺序解法的基本方程为：,当时，有,当时，有,当3时，有,记,求导，得,解得,此点仅为极小点,极大值应在0，s4=0，10的端点取得,当x3=0时，f3(10)=90当x3=10时，f3(10)=200,再由状态转移方程逆推：,逆序解法的过程见书 P,.3.1,资源分配问题,例,为企业可提供的盈利,各不相同,(,见表,.4),问应如何分配这四台,设备才能使企业获得的盈利最大,?,.3 动态规划应用举例,分析:可建立如下模型,解：1.将问题按工厂分为三个阶段，k=1,2,3 2.设 xk分配给第k个工厂的设备台数。,3.状态转移方程：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,5.列表计算：,046111212,012345,0,4,6,11,12,12,当K=2时,0+00+40+60+110+120+12,5+05+45+65+115+12,10+010+410+610+11,11+011+411+6,11+011+4,11+0,0051,102142 161,2212,状态变量的取值范围为 s2=0,1,2,3,4,5,当k=1时，s1=5,x1的可取值为0,1,2,3,4,5计算结果如下：,最优分配方案有两个：x1=0,x2=2,x3=3,0+21,3+167+14 9+10 12+5 13+0,21,0，2,x1=2,x2=2,x3=1,背包问题,背包问题是动态规划的典型问题。一维背包问题的典型提法是：一,位旅行者能承受的背包最大重量是,b,千克，现有,n,种物品供他选择装入,背包，第,i,种物品单件重量为,千克，其价值,(,或重要性参数,),为,c,i,，总价,值是携带数量,的函数即,，问旅行者应如何选择所携带物品的件数,以使总价值最大,?,当K=3时，S3=0，1，2，10，f3(S3)=max6x3+0,00000,66666,12,00000,6666612,00000111112,当K=2时，S2=0，1，2，10，f2(S2)=max6x2+f3(S3),00000,0+60+60+60+60+6,0+12,5+05+05+05+05+0,5+65+6,10+010+010+0,0000,5666,101111,00001000211,当K=1时，S1=10,f1(S1)=max4x1+f2(S2),最优解为：X1*=2,X2*=1,X3*=0 Z*=13,0+11,4+6,8+5,12+0,13,2,4,7.3.3 生产与存储问题,例 7.6 某厂生产的一种产品，以后四个月的订单如下表：,合同规定在各月底前交货，生产每批产品的固定成本为3千元，每批生产的产品件数不限。每件产品的可变成本为1千元，每批产品的最大生产能力为5件。产品每件每月的存储费为500元。又知1月初有库存产品1件，4月底不再留下产品。试在满足需要的前提下，如何组织生产才能使总的成本最低。,解：1.设阶段变量为K,则每月为一个阶段,K=1,2,3,4,2.每月初的产品库存量作为状态变量，由已知条件显然有S1=1，S5=0,3.决策变量是每月的产品生产量，由已知条件知：,当K=4时，S4的最小可能值为0，即4月初没有存货。S4的最大可能值=531（3 3 2），4=4即 S4=0，1，2，3，4。（K=4）,当K=3时，S3的最小值=52+16，6=5即 S3=0,1,2,3,4,5(k=3),(K=2),(K=1),最优生产决策为：x1=2,x2=5,x3=0,x4=4 最优值为21.5,
