运筹学-第6章动态规划.ppt

2020/5/23,1,第六章动态规划DynamicProgramming，DP,美国数学家贝尔曼（Richard.Bellman,(19201984),创始时间,上个世纪50年代,创始人,动态规划是运筹学的一个主要分支,同时也是现代企业管理中的一种重要决策方法,它是解决多阶段决策过程的最优化的一种方法。,2020/5/23,2,动态规划模型分类,离散确定型,离散随机型,连续确定型,连续随机型,动态规划解决问题的思路独特,在处理某些优化问题时,有时比线性规划或者非线性规划更有效.需要丰富的想象力去建立模型，并能用创造性的技巧去求解。,其中离散确定性是最基本的,本章主要介绍这种类型的问题,介绍动态规划的基本思想、原理和方法.,2020/5/23,3,本章主要内容,多阶段决策过程及其问题举例最短路问题动态规划的基本概念和基本方程动态规划应用举例资源分配问题背包问题生产库存问题,2020/5/23,4,6.1多阶段决策过程及其问题举例,动态规划研究的问题-多阶段决策问题（顺序决策问题）研究的问题可以在时间或空间上划分为若干个相互联系阶段，称为”时段”。在每一个时段都需要做出决策,每时段的决策将影响到下一时段的决策,因此决策者每段决策时,不仅要考虑本阶段目标最优,还应考虑最终目标的最优,最终达到整个决策活动的总体目标最优.,2020/5/23,5,动态规划方法与“时间”关系很密切，随着时间过程的发展而决定各时段的决策，产生一个决策序列，这就是“动态”的意思。然而，它也可以处理与时间无关的静态问题，只要在问题中人为地引入“时段”因素，就可以将其转化为一个多阶段决策问题。,2020/5/23,6,例1最短路径问题,求从A到E的最短路径。显然，这种运输网络问题是静态决策问题。但是，按照网络中点的分布，可以把它分为4个阶段，而作为多阶段决策问题来研究。,2020/5/23,7,第一种方法称做全枚举法或穷举法。它的基本思想是列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。这里从A到E的路程共有332118条可能的路线，分别算出各条路线的距离，最后进行比较，可知最优路线。显然，当组成交通网络的节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算第二种方法贪心算法，即所谓“局部最优路径”法，是说某人从k出发，他并不顾及全线是否最短，只是选择当前最短途径，“逢近便走”，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是AB3C3D1E.距离为：1+11+8+5=25,2020/5/23,8,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,第1阶段,第4阶段,第3阶段,第2阶段,状态,第三种方法是动态规划方法。,2020/5/23,9,基本思想：如果起点A经过B1,C1,D1而到终点E，则由C1出发经D1到E点这条子路线，是从C1到E的最短路线。所以，寻找最短路线，应该从最后一段开始找，然后往前递推.设sk：第k阶段初的状态（所处的结点）;xk(sk)：在sk状态时第k阶段所作的决策,决定下一个状态的位置；d(sk,xk)：第k阶段，采取策略xk所发生的距离;fk(sk)：在第k阶段，由sk状态开始到终点E的最短距离.,2020/5/23,10,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f5(E)=0,2020/5/23,11,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D1)=5,f5(E)=0,2020/5/23,12,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f4(D1)=5,2020/5/23,13,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C1)=8,f4(D1)=5,2020/5/23,14,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C2)=7,f4(D1)=5,f3(C1)=8,2020/5/23,15,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f3(C1)=8,f3(C2)=7,2020/5/23,16,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B1)=20,f3(C2)=7,f3(C1)=8,2020/5/23,17,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B2)=14,f3(C2)=7,f3(C1)=8,f2(B1)=20,2020/5/23,18,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f2(B1)=20,f2(B2)=14,2020/5/23,19,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=20,2020/5/23,20,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=20,状态最优决策状态最优决策状态最优决策状态最优决策状态,A（A，B2）B2（B2，C1）C1（C1，D1）D1（D1，E）E从A到E的最短路径为19，路线为AB2C1D1E,2020/5/23,21,多阶段决策过程及实例-标号法,4,3,7,5,9,7,6,8,13,10,9,12,13,16,18,该点到G点的最短距离,从G到A的解法称为逆序解法。,注：因为从A到G的最短路与从G到A的最短路是一样的，因此也可以从A出发来找。从A到G的解法称为顺序解法。,2020/5/23,22,综上所述可见，全枚举法虽可找出最优方案，但不是个好算法，局部最优法则完全是个错误方法，只有动态规划方法属较科学有效的算法。它的基本思想是，把一个比较复杂的问题分解为一系列同类型的更易求解的子问题，便于应用计算机。,2020/5/23,23,6.2动态规划的基本概念和基本方程,(一)基本概念和基本方程,(1)阶段：k=1,，n,(2)状态变量sk：第k阶段的状态.状态变量取值的集合成为状态集合，用Sk表示。状态集合可以是一离散取值的集合，也可以为一连续的取值区间，视具体问题而定,(3)决策变量uk(sk)：第k阶段的决定，Dk(sk)为决策变量的取值范围.状态转移方程sk1T(sk,uk)：描述第k阶段与第k+1阶段的状态变量的关系,2020/5/23,24,(5)指标v(sk,uk)：第k阶段状态sk情况下采取决策uk得到的结果（距离、得益、成本等）指标函数是指各阶段指标的累计。即V(sk,uk,sn,un,sn+1)=vk(sk,uk)*vk+1(sk+1,uk+1)*vn(sn,un)它表示从第k阶段的状态sk开始到第n阶段的终止状态的指标累计。式中*表示某种运算符，一般为加法运算或者乘积运算。,(6)最优指标函数fk(sk)：它表示从第k阶段的状态sk开始到第n阶段的终止状态的过程，采取最优策略得到的指标函数值,阶段函数,2020/5/23,25,逆推公式,或,多阶段决策问题中，常见的目标函数形式之一是取各阶段效益之和的形式.有些问题，如系统可靠性问题，其目标函数是取各阶段效益的连乘积形式.总之，具体问题的目标函数表达形式需要视具体问题而定。,Max或者min,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,第1阶段,第4阶段,第3阶段,第2阶段,对例1,(1)阶段：k1，2，4,(2)状态变量：sk第k阶段初所处的位置,状态集合Sk如S2:=B1,B2,B3.,2020/5/23,27,(3)决策变量uk：在第k段sk状态时决定选取的下一段的某点.,(4)状态转移方程：sk1uk(sk),(5)阶段效益：d(sk,uk)为第k段，采取决策uk到下一状态的距离.,(6)最优指标函数：fk(sk)：第k段，在sk状态时到终点E的最短距离.,逆推公式：,2020/5/23,28,（二）贝尔曼最优化原理：一个最优策略具有这样的性质，即不论初始状态与初始策略如何，对于先前决策所造成的状态而言，余下所有决策必构成最优决策。也即：一个最优策略的子策略也是最优的。,2020/5/23,29,（三）解法步骤反向条件优化正向求最优解,2020/5/23,30,6.3应用举例,例2资源分配问题-1例3资源分配问题-2例4背包问题例5生产库存问题例6可靠性问题例7机器负荷分配问题等等,2020/5/23,31,例2资源分配问题-1,某公司准备将5台设备分配给所属的三个子工厂，各工厂获得设备后的可盈利情况如表所示。问：如何分配这五台设备，才能使公司获得的收益最大？,2020/5/23,32,分析,(1)阶段：k=1,2,3.,(3)决策变量uk：对第k个企业的分配数.,(2)状态变量sk：对第k至3个企业可分配的设备数或：第k阶段初可分配的设备数.,(4)状态转移方程：sk1skuk.,(5)最优指标函数fk(sk)：第k至3个企业采取最优分配策略可产生的最大收益.,设分配给第k个工厂的机器数为uk,工厂1,工厂2,工厂3,2020/5/23,33,其中，gk(uk)是阶段函数,逆推公式：,sk+1,2020/5/23,34,k=3,S3=0,1,2,3,4,5,f3(s3)maxg3(u3)+0,2020/5/23,35,k=2,S2=0,1,2,3,4,5,f2(s2)maxg2(u2)+f3(s3),S3=S2-u3,2020/5/23,36,k=1,S1=5,f1(s1)maxg1(u1)+f2(s2),得到两种方案：u1*0，u2*2，u3*3:工厂1分配0台，工厂2分配2台，工厂3分配3台;u1*2，u2*2，u3*1:工厂1分配2台，工厂2分配2台，工厂3分配1台。总盈利均为21万元。,同理得到另一组最优解,2020/5/23,37,一般分配问题,某种资源，总量为a，分配于n种生产。若分配ui用于第i种生产，收益为gi(ui)。问：应如何分配才能使总收入最大？容易建立其数学模型：,2020/5/23,38,逆推公式：,sk:第k阶段初可分配的资源数。uk:对第k个企业的分配资源数.状态转移方程:sk+1=sk-uk,例3资源分配问题-2,某工厂要进行A,B,C三种新产品的试制，为提高三种产品研制成功的概率，决定调拨经费2百万，并要求资金集中使用，也即以百万为单位进行分配，其增加研发费与新产品不成功概率的关系如表所示。问如何分配资金，可使三种产品都研制不成功的概率最小。,分析,(1)阶段：k=1，2，3,(3)决策变量uk：对第k阶段分配金额,(2)状态变量sk：第k阶段初的可用金额,(4)状态转移方程：sk1sk-uk,产品A,产品B,产品C,逆推公式：,其中，gk(uk)是阶段指标函数,(5)最优指标函数fk(sk)：第k至3阶段采取最优分配策略，得到不成功概率最小,k=3,S3=0,1,2,f3(s3)ming3(u3)*1,k=2,S2=0,1,2,f2(s2)ming2(u2)*f2(s2),k=1,S1=2,f1(s1)maxg1(u1)*f2(s2),得到方案：u1*1，u2*0，u3*1:产品A分配1百万，产品B分配0，产品C分配1百万f*=0.06,2020/5/23,45,例4背包问题某卡车载重能力为10吨，现要装三种产品，已知每件产品的重量和利润如表：又规定产品3至多装2件。问如何安排运输可使总利润最大？,设u1,u2,u3分别为1、2、3货物的装载件数，得到数学模型：,阶段k=1,2,3，状态变量sk第k阶段初的可装载能力，决策变量uk第k阶段的装载件数，状态转移方程:（tk为k产品的单件重量）递推公式:f4(s4)=0,k=3,2,1,动态规划方法求解,产品A,产品B,产品C,物品A,物品B,物品C,k=1,k=2,k=3,k=4,s1=10,s2,s3,s4,阶段k,状态变量：装载前背包的容量,决策变量：装载的件数,u1,u2,u3,决策允许集合：装载件数的范围,0u1s1/t1u1为整数,状态转移方程：背包容量和装载件数的关系,阶段指标：vk(sk,uk)=rkuk在背包中第k种物品的价值,最优指标：fk(sk)=maxrkuk+fk+1(sk+1),终端条件：,f4(s4)=0,s2s1-t1x1,s3=s2-t2x2,s4=s3-t3x3,0u2s2/t2u2为整数,0u3s3/t3,2u3为整数,k=3,C的单件重量为2,限制最多装2件,k=2,装载物品B，f2(s2),B的单件重量为3,k=1，装载物品A，f1(u1),最优解为：物品A装0件，物品B装2件，物品C装2件。最大价值为400元。,A的单件重量为4,2020/5/23,52,例5生产库存问题某厂在年末估计，下年4个季度市场对该厂某产品的需求量均为dk=3(k=1,2,3,4)，该厂每季度生产此产品的能力为bk=5(k=1,2,3,4,)。每季度生产这种产品的固定成本为F=13（不生产时为0），每一产品的单位变动成本为C=2。本季度产品如不能售出，则需发生库存费用g=1/件，仓库能贮存产品的最大数量Ek=4。年初年末库存为0，试问如何安排4个季度的生产，以保证在满足市场需求的前提下，使生产和库存总费用最小?,2020/5/23,53,假设：第k季度可以销售的产品是本季度初的库存及本季度的产量,(1)阶段：k=1,2,3,4n=4.,(2)状态变量sk：第k季度初的库存量.,(3)决策变量uk：第k个季度的产量.,(4)转移方程：sk1sk+uk-dk.,(5)最优指标函数fk(sk)：第k季度至第4个季度采取最优策略时的最小总费用.,2020/5/23,54,逆推公式：,k=4,k=3,K=2,k=1,2020/5/23,60,例5可靠性问题,某机器工作系统由n个部件组成，这些部件正常工作关系为串联，每个部件都装有主要元件的备用件，并可自动投入工作。显然备用件越多，可靠性越大，但系统的成本、重量、体积会变大。若已知备用件总费用为C，总重量为W.ck为第k个部件装配一个备用件的费用,问：在这两个限制条件下，应如何选用部件的备用件个数，使得正常工作的可靠性最大？,wk为第k个部件装配一个备用件的重量,Pk第k个部件的故障概率,设uk为第k个部件装配备用件个数,dk(sk,uk)为第k个部件装配uk个备用件时，机器正常工作的概率,动态规划模型：,(1)阶段：k=1,2,n,(2)决策变量：uk：第k个部件上装备用件个数,(4)状态转移：sk+1=sk-ckuktk+1=tk-wkuk,(5)fk(sk，tk)：第k-n个部件，采取最优策略时机器正常工作的概率。,某复合系统由A,B,C三个部分串联而成，已知：A、B、C相互独立；各部分的单件故障率分别为：P1=0.4，P2=0.2，P3=0.5；每个部分的单件价格为：A部分单价c1=1万元；B部分单价c2=2万元；C部分单价c3=3万元；可投资购置部件金额为10万元。求A、B、C三部分各应购置多少部件才能使系统的总可靠率最大？,令A、B、C分别为阶段1、2、3。sk第k阶段及以后可用来购买部件总额uk第k环节配备的件数状态转移方程：sk+1=skckuk第k环节本身的可靠率为：令：fk(sk)表示k阶段尚有资金sk时，可能获得k段及以后各段组成系统的最高可靠率。递推方程为：fk(sk)=maxdk(sk，uk)fk+1(skckuk)，f4(s4)=1,采用后向动态规划法，从第3阶段算起。,阶段2，此时考虑当把钱用于购置B和C部件时，各应购置多少个部件为最优。显然，此时B、C应至少各配制1个部件，故s2c2+c3=2+3=5；同时，