运筹学——动态规划.ppt

1,Yunchouxue,第七章 动态规划,2,以最短路问题为例，来说明动态规划的概念,3,一、动态规划基本概念：,1、阶段: 将所要研究的问题,按时间或空间特征分成若干个互相联系的阶段.简称“阶段”。 阶段就是作出决策的若干轮次。描述阶段的变量叫阶段变量，常用k表示阶段变量.上例中k1，2，3，4，5。,4,2、状态及性质,各阶段开始时的客观条件叫做状态.描述各阶段状态的变量叫做状态变量,常用sk表示第阶段的状态变量, sk的取值集合称为状态集合,用Sk表示。 阶段的出发位置，即阶段的起点。 上例中，第二阶段有两个状态，即Sk= B1,B2 动态规划中状态具有以下性质:某阶段状态一旦确定,以后过程的状态变化不受这个状态以前的影响,也就是说某状态以后的过程和以前无关,只与当前状态有关,我们称这种特性为“无后效性.”(即马尔科夫性。）P194,5,3、决策和策略,指从一个阶段某状态演变到下一阶段某状态的选择（决定）称为决策。 表示决策的变量叫做决策变量,常用uk(sk)表示.第k阶段当状态为sk时的决策变量. 在实际问题中决策变量的取值往往限制在一定的范围内,我们称此范围为允许决策集,常用Dk(sk)表示第k阶段从状态sk出发的允许决策集,因此有uk(sk) Dk(sk). 在例1中D2(B1)=C1,C2,C3 .,6,策略,在例1中 D2(B1)=C1,C2,C3.表示什么？ 表示从第二阶段的状态B1出发，可选择下一阶段的C1 ,C2,C3。即允许决策集是D2(B1).如果我们决策选择了C3,则u2(B1)=C3. 全过程中各个阶段的决策组成的有序总体称为策略。 上例中每一条路线都被称为一个策略。 使整个问题达到最优效果的策略就是最优策略.即上例中，路最短的策略就是最优策略。,7,状态转移方程,动态规划中本阶段的状态是上一阶段的决策结果.如果给定了第k阶段的状态sk,本阶段的决策就为uk(sk),则第k+1段的状态uk+1也就完全确定了,它们的关系可表示为:sk+1=Tk(sk,uk).由于它表示了由k到k1段的状态转移规律,所以称为状态转移方程. 即前一阶段的终点（决策）是后一阶段的起点（状态）。 例1的转移方程为:sk+1 =Tk(sk,uk) =uk(sk).,8,指标函数,用于衡量所选定策略优劣的数量指标称为指标函数. 一个n段决策过程,从1到n叫作问题的全过程,对于任意一个给定的k ,从第k 到n段的过程称为全过程的一个后部子过程.指标函数是定义在全过程和后部子过程上确定的数量函数。常用Vk,n表示， 即Vk,n Vk,n(sk, uk, sk+1, sn+1),k=1,2,n 指标函数的最优值称为最优指标函数，记为fk(sk),它表示从第k阶段状态sk开始到第n阶段的终止状态的过程，采取最优策略所得到的指标函数值。即fk(sk)=optVk,n(sk,pk,n), fk(sk)可能是最大值，也可能是最小值，依题意而定。 当k=1时F1(s1)就是从初始状态到全过程的整体最优函数.,9,指标函数的常见形式：,（1）过程和它的任一子过程的指标是它所包含的各阶段的指标的和。 （2）过程和它的任一子过程的指标是它所包含的各阶段的指标的乘积。 指标函数应具有可分离性，并满足递推关系。vj(sj,uj)表示第j阶段的指标，则1，2式分别写为： Vk,n(sk, uk, sk+1, sn+1) vk(sk,uk)+ Vk+1,n(sk+1, uk+1, sk+2, sn+1) Vk,n(sk, uk, sk+1, sn+1) vk(sk,uk) Vk+1,n(sk+1, uk+1, sk+2, sn+1),Vk,n(sk, uk, sk+1, sn+1),Vk,n(sk, uk, sk+1, sn+1),1,2,1,2,10,回到例1,在例1中 指标函数是距离.如第2阶段,状态为B1时,V2,5(B1)表示从B1到F的距离,而f2(B1)则表示从B1到 F的最短距离. 该问题总目标是求f1(A),即从A到终点F的最短距离.,11,阶段 从网络图中可看到问题可分为k=5段. 状态 由A-F分为5段,存在6种状态允许集:S1-S6 S1=A,S2=B1,B2, S3=C1,C2,C3,C4, S4=D1,D2,D3, S5=E1,E2, S6=F,12,例1中的决策允许集 D1(A)=B1,B2 D2(B1)=C1,C2,C3 D2(B2)=C2,C3,C4 D3(C1)=D1,D2, D3(C4)=? D4(D1)=E1,E2,D4(D2)= E1,E2 D5(E1)=F, D5(E2)=F,13,状态转移方程 例1中的状态转移方程sk+1=uk(sk) 如: s3=u2(B1)=C2. 指标函数 例1中的指标函数是距离,(是数值) V2,5(B1)=13 最优值函数fk(sk), 例1中f5(E2)=3.,14,二、动态规划的基本思想和基本方程,最短路线有一个重要特性：如果由起点A经P点和H点最终到达F点是一条最短路线，则由P点出发经过H点最终到达F点的这条路线必定也是从P点到F点的最短路。 根据这一特性，寻找最短路的方法，就是从最后一段开始，用由后向前逐步递推的方法，求出各点到F点的最短路，最后求得A点到F点的最短路。所以动态规划的方法是从终点逐段向始点方向寻找最短路的一种方法。,15,动态规划的寻优途径：是从终点逐段向始点方向寻找最短路线。 解例1： 从例1得出动态规划的基本方程。,16,17,动态规划的基本方程（一）,从上面的计算过程中可以看出，在求解的各个阶段，我们利用了k阶段与k+1阶段的递推关系：,18,动态规划的基本方程（二）,一般情况，k阶段与k+1阶段的递推关系式可写为： 上式称为动态规划的基本方程。,19,动态规划方法的基本思想P197,(1)动态规划方法的关键在于正确的 写出基本的递推关系式和恰当的边界条件(简言之为基本方程)。 (2)在多阶段决策过程中,动态规划方法是既把当前一段和未来各段分开,又把当前效应和未来效应结合起来考虑的一种最优化方法.因此每段决策的选取是从全局考虑的,与该段的最优选择答案一般是不同的。 (3)在求整个问题的最优策略时,由于初始状态是已知的,而每段的决策都是该段的状态函数,故最优策略所经过的各段状态便可逐次变换得到,从而确定了最优路线。,20,最短路问题的图上作业法标号法,4,3,7,5,5,12,10,8,9,13,15,17,0,逆序解法,21,最短路问题的图上作业法标号法,0,4,5,6,7,9,12,11,12,13,14,14,17,顺序解法,22,动态规划的最优性定理,作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略，也就是说最优策略的任一子策略都是最优的。,23,三、动态规划与静态规划的关系,将与时间无关的线性规划问题或非线性规划问题称为静态规划。而动态规划所研究的问题是与时间有关的，它是研究具有多阶段决策过程的一类问题，将问题的整体按时间或空间的特征而分成若干个前后衔接的时空阶段，从而求出了整个问题的最优决策序列。因此，对于某些静态的问题，也可以人为的引入时间因素，把它看作按阶段进行的一个动态规划问题，这就使得动态规划成为求解某些线性、非线性规划的有效方法。（P203）,24,1、动态规划模型的建立,建立动态模型的6个要素： 1）阶段k 2）状态SK 3)决策uk(sk) 4）状态转移方程 5）阶段指标函数 6）指标递推方程,25,动态规划的求解方法有两种： 逆序解法与顺序解法,2、动态规划模型的解法,2、在已知终止状态Sn下，采用顺序解法（正向递归）,1、在已知初始状态S1下，采用逆序解法：（反向递归）,26,3、两种解法在建模时的区别如下表所示,27,顺序解法解例1：,28,29,四、资源分配问题,所谓资源分配问题就是将一定数量的一种或多种资源恰当地分配给若干个使用者,而使目标函数为最优。如：东江流域水资源分配问题，出台东江流域水资源首个分配方案。公共资源、教育资源、卫生资源等等都涉及到资源分配问题。,30,1、一维资源分配问题,有某种资源总量为a ，用于生产n种产品。设分配数量Xi用于生产第i种产品，第i种产品的收益为gi(Xi) 。问：如何分配才使总收益最大？,该问题的静态规划模型为： Maxz=g1(x1)+ g2(x2)+ gn(xn) X1+ x2+ xn=a xi0(i=1,2,n),31,建立动态模型的6个要素：（提问）,1）阶段 2）状态变量 3)决策变量 4）状态转移方程 5）阶段指标函数 6）指标递推方程,32,分析：,如果将生产n种产品作为一个互相衔接的整体，对一种产品的资源分配作为一个阶段，每个阶段确定对一种产品的资源投放量。则该问题成为一个多阶段决策问题。 状态变量sk的选取原则是要能够据此确定决策变量uk，以及满足状态转移方程所要求的无后效性。 在资源分配问题中，决策变量选为对产品k的资源投放量，因此状态变量可以选择为阶段k初所拥有的资源量，即将要在第k种到第n种产品间分配的资源量。,该问题的静态规划模型为： Maxz=g1(x1)+ g2(x2)+ gn(xn) X1+ x2+ xn=a xi0(i=1,2,n),33,一维资源分配问题动态规划模型为：,阶段变量k1、2n 状态变量sk表示分配给用于生产第k种至第n种产品的资源数量。取值范围是 0ska 决策变量uk表示分配给第k种产品的资源数量。取值范围是： 0uksk。 状态转移方程为 sk+1=sk-uk 阶段指标函数为分配资源uk用于生产第k种产品时的收益，有Vk(sk, uk)=gk(uk)= gk(xk) 指标递推方程为：,34,例2：某有色金属公司拟拨出50万元对所属三家冶炼厂进行技术改造。若以10万元为最小分割单位，各厂收益与投资的关系如下： 公司经理从定量决策的需要出发，要求公司的系统分析组求出：对三个工厂如何分配这50万元，才能使总收益达到最大？,35,解：首先工厂1进行分配，余下的工厂2进行分配，最后余下的分配给工厂3。建立动态规划数学模型过程如下：,1）阶段变量k=1,2,3,2)状态变量sk表示分配给第k个工厂至第n个工厂的资金数。,3）决策变量xk表示为分配给第k个工厂的资金数。,4）状态转移方程sk+1=sk-xk为分配给第k+1个工厂至第n个 工厂的资金数。,5）阶段指标函数gk(xk)表示为资金xk分配给第k个工厂 所得的收益。,6）指标递推方程为：,36,最大盈利：f3(s3)=g3(x3)+f4(s4).,s3,x3,g3(x3),0,1,2,3,4,5,0,1,2,3,4,5,f3(s3),x3*,0,5,7,8,10,13,0,0,5,1,7,2,8,3,10,4,13,5,K=3时，设将s3万元全部分配给工厂3,计算如下：,37,最大盈利为： f2(s2)=,s2,x2,f2(s2)=,g2(x2)+f3(s3),0,1,2,3,4,5,0,1,2,3,4,5,0+0,0+5,2+0,0+7,2+5,4.5+0,0+8,2+7,4.5+5,7.5+0,0+10,2+8,4.5+7,7.5+5,11+0,0+13,2+10,4.5+8,7.5+7,11+5,15+0,f2(s2),x2*,0,0,5,0,7,0,1,9.5,2,12.5,3,16,4,K=2时，设将s2万元全部分配 给工厂2和3；,x2=0,1,2,3,4,5,计算如下：,38,最大盈利为： f1(s1)=,016 16,4.5+12.5 =17,7+9.5 =16.5,7+9 =16,10.5+5 =15.5,12+0 =12,0,1,2,3,4,5,17,1,由此可知， s1=5,此时， x1*1， s2= s1- x1*=5-1=4,此时， x2*3 s3= s2- x2*=431，此时， x3*1 Z*=17,最优策略为P*x1*， x2*， x3*1，3，1 即，1，2，3工厂分别分配10万，30万，10万元。,K=1时，设将s1万元全部分配 给工厂1、2和3；,x1=0，1，2，3，4，5,计算如下：,39,例3.某公司有资金10万元，若投资项目i（i=1,2,3）的投资额为 时,其效益分别为: 问应如何分配投资数额才能使总收益最大? 可列出它的静态模型:,分析:这是一个表面与时间没有任何关系的问题,但要用动态规划的方法去解则必须把它划分为“时段”.本题可划分为3个时段,每段只决定对一个投资项目的投资额.这样把问题分解为3阶段决策问题.,40,解：,1、阶段变量k1、2、3,2、状态变量为sk,41,42,当k=2时,这是一个函数求极值问题,利用微分方法可求得该函数有极小值.,43,要讨论 的具体情况:,44,45,46,2、资源连续分配问题,将一种有消耗性的资源，多阶段地在多种不同的生产活动中投放的问题称为资源的多段分配问题，下面讨论其中包含有两个生产活动的简单情况。,47,一般提法：设有某种资源，初始的拥有量是M。计划在A，B两个生产部门连续使用n个阶段。已知在部门A投入资源uA时的阶段收益是g(uA)，在部门B投入资源uB时的阶段收益是h(uB)。又资源在生产中将有部分消耗，已知每生产一个阶段后部门A、B中的资源完好率分别为a和b，0a、 b1。求n阶段间总收益最大的资源分配计划。,48,阶段变量k1、2n 状态变量sk为阶段k初拥有的资源量0skM，s1=M 决策变量选uk,为阶段k在部门A的资源投放量，即uA=uk，显然有uB=sk- uk， 0uksk 状态转移方程sk+1=auk+b(sk-uk) 阶段指标函数 rk(sk,uk)=g(uk)+h(sk-uk) 指标递推方程：目标函数是n个阶段的总收益，即阶段指标函数求和。,49,例4 今有1000台机床，要投放到A、B两个生产部门，计划连续使用3年。已知对A部门投入uA台机器时的年收益是g(uA)=4(uA)2元，机器完好率a=0.5，相应的B部门的年收益是h(uB)=2(uB)2 元，完好率b= 0.9。试求使3年间总收益最大的年度机器分配方案。,50,解 ： 阶段变量K=1、2、3 状态变量sk，为该年度初完好的设备数， 决策变量uk，为该年度投入A活动的设备数，则有0sk1000， 0uksk 状态转移方程为：sk+1=0.5uk+0.9(sk-uk) 阶段指标函数： g(uA) h(uB) 递推指标函数：,51,k=3时，0u3s3，有,k=2时，0u2s2，有,52,k=1时，0u1s1， s2=0.5u1+0.9(s1-u1)，,53,例4：用动态规划解下列规划问题：p204 Maxz=x1.x22.x3 x1+x2+x3=c (c0) x1,x2,x30 解：按问题变量的个数划分阶段， 阶段k1，2，3；状态变量为s1,s2,s3;且s1c； 决策变量为x1,x2,x3；状态转移方程为sk+1 xk =sk, 阶段指标函数gk(xk)表示为x1,x22,x3 设， s3 x3， s3 x2 s2， s2 x1 s1 c 则有 x3 s3，0 x2 s2， 0 x1 s1 c 则，递推方程为,s.t.,54,例5：用动态规划解下面问题P207 Maxz=4x12-x22+2x32+12 3x1+2x2+x39 xi0,(i=1,2,3) 解：按问题变量的个数划分阶段，阶段k1,2,3； 状态变量为s1,s2,s3,s4;且s19 ； 决策变量为x1,x2,x3；状态转移方程为sk+1 axk =sk,具体为：s3=x3,s3+2x2=s2,s2+3x1=s1 则有： x3 = s3,0 x2 s2/2, 0 x1 s1/3 阶段指标函数gk(xk)表示为4x12,-x22,2x32 递推关系式：,55,五、生产与存贮问题,一般提法：设某公司对某种产品要制定一项n个阶段的生产（或购买）计划。已知它的初始库存量为零，每阶段生产（或购买）该产品的数量有上限的限制；每阶段社会对该产品的需求量是已知的，公司保证供应，在n阶段末的终结库存量为零。问该公司如何制定每个阶段的生产（或采购）计划，从而使总成本最小。,56,模型的建立：,1、阶段变量：k=1、2、n； 2、决策变量xk，为第k阶段该产品的生产量（或采购量）；dk为第k阶段对产品的需求量。 3、状态变量vk，为第k阶段结束时的产品库存量。 4、状态转移方程：vk=vk-1+xk-dk 5、阶段指标函数：ck(xk)表示第k阶段生产产品xk时的成本费用， hk(vk)表示在第k阶段结束时的产品库存量vk所需的存储费用。 第k阶段的成本费用ck(xk)+ hk(vk),57,6、指标递推方程：,58,例题6：某工厂与购货单位签订的供货合同如下表。该厂每月最大产量为4百件，仓库的存货能力为3百件。已知每一百件货物的生产费为一万元。在生产的月份，每批产品的生产准备费为4千元，仓库保管费为每一百件货物每月一千元。假定1月初开始时及6月底交货后仓库中都无存货。问该厂应该如何安排每月的生产与库存，才能既满足交货合同的要求，又使总费用最小？,59,（4）状态转移方程：,（5）第k月的总费用包括生产费和库存费,（6）基本递推方程,解：1、建立动态规划模型 （1）阶段划分：k=1，2，3，4，5，6 （2）状态变量sk表示第k月初的库存量，s1=0 （3）决策变量dk表示第k月的计划生产量 表示第K月的合同交货量,60,2、用逆序算法求解 当k=6时，s6+d6-1=s7=0, 所以 s6+d6=1，f6(s6)=minv6(s6,d6) 当s6=0,d6=1, f6(s6)=14，当s6=1,d6=0, f6(s6)=1,当k=5时，s5+d5-2=s6, 所以,61,当k=4时，s4+d4-3=s5, 所以,62,所求最优决策结果如下表：,63,再生产点性质p227,很多库存问题有如下特征： （1）对于每个i，有vi-1xi=0,其中，v00.即前一阶段的库存量乘以本阶段的生产量等于零，前提是第一阶段初的库存为0. （2）对最优生产决策来说，它被裂解为多个子问题：分别是第一至第二阶段，第三至第四阶段，第五至第六阶段等，每个子问题的最优生产决策为：它们的最小总成本之和就等于原问题的最小总成本。符合以上规律的问题可以大大减少计算。,64,再生产点,如果对每个i，都有vi-1xi=0，则称该点的生产决策具有再生产点性质（又称重生性质）。如果vi=0,则称阶段i为再生产点。 由假设v0=0和vn=0，故阶段0和n是再生产点，运用再生产点性质可以求库存问题为凹函数的解。公式如下：,65,66,举例：p225,固定成本3千元，单位可变成本1千元，每期 最大生产能为6个单位，每期末未售出的产品每 单位存贮费为0.5千元，第一时期初与第六时期末 的库存均为0，求总成本最小的生产计划。,67,（背包问题）某工厂生产三种产品，各种产品重量与利润的关系下表所示。现将此三种产品运往市场出售，运输能力总重量不超过6吨，问如何安排使运输总利润最大,68,1、建立动态规划模型（在此用的是逆序算法求解，与课本不同） （1）阶段划分：k=1,2,3，把装载一种产品看成一个阶段（2）状态变量sk表示第k阶段初可用于装载产品的总容量量，s1=6 （3）决策变量dk表示第k阶段装载第k种货物的件数。,