运筹学第章动态规划.ppt

2019/7/9,1,第六章 动态规划 Dynamic Programming，DP,美国数学家贝尔曼 （Richard. Bellman, (19201984) ),创始时间,上个世纪50年代,创始人,动态规划是运筹学的一个主要分支, 同时也是现代企业管理中的一种重要决策方法, 它是解决多阶段决策过程的最优化的一种方法。,2019/7/9,2,动态规划 模型分类,离散确定型,离散随机型,连续确定型,连续随机型,动态规划解决问题的思路独特,在处理某些优化问题时, 有时比线性规划或者非线性规划更有效.需要丰富的想象力去建立模型，并能用创造性的技巧去求解。,其中离散确定性是最基本的, 本章主要介绍这种类型的问题,介绍动态规划的基本思想、原理和方法.,2019/7/9,3,本章主要内容,多阶段决策过程及其问题举例 最短路问题 动态规划的基本概念和基本方程 动态规划应用举例 资源分配问题 背包问题 生产库存问题 ,2019/7/9,4,6.1 多阶段决策过程及其问题举例,动态规划研究的问题-多阶段决策问题（顺序决策问题） 研究的问题可以在时间或空间上划分为若干个相互联系阶段，称为”时段”。 在每一个时段都需要做出决策,每时段的决策将影响到下一时段的决策, 因此决策者每段决策时, 不仅要考虑本阶段目标最优,还应考虑最终目标的最优, 最终达到整个决策活动的总体目标最优.,2019/7/9,5,动态规划方法与“时间”关系很密切，随着时间过程的发展而决定各时段的决策，产生一个决策序列，这就是“动态”的意思。 然而，它也可以处理与时间无关的静态问题，只要在问题中人为地引入“时段”因素，就可以将其转化为一个多阶段决策问题。,2019/7/9,6,例1 最短路径问题,求从A到E的最短路径。 显然，这种运输网络问题是静态决策问题。但是，按照网络中点的分布，可以把它分为4个阶段，而作为多阶段决策问题来研究。,2019/7/9,7,第一种方法称做全枚举法或穷举法。它的基本思想是列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。这里从A到E的路程共有332118条可能的路线，分别算出各条路线的距离，最后进行比较，可知最优路线。显然，当组成交通网络的节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算 第二种方法贪心算法，即所谓“局部最优路径”法，是说某人从k出发，他并不顾及全线是否最短，只是选择当前最短途径，“逢近便走”，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是 A B3 C3 D1 E. 距离为：1+11+8+5=25,2019/7/9,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阶段,状态,第三种方法是动态规划方法。,2019/7/9,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的最短距离.,2019/7/9,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,2019/7/9,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,2019/7/9,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,2019/7/9,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,2019/7/9,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,2019/7/9,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,2019/7/9,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,2019/7/9,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,2019/7/9,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,2019/7/9,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,2019/7/9,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，路线为AB 2C1 D1 E,2019/7/9,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的解法称为顺序解法。,2019/7/9,22,综上所述可见，全枚举法虽可找出最优方案，但不是个好算法，局部最优法则完全是个错误方法，只有动态规划方法属较科学有效的算法。它的基本思想是，把一个比较复杂的问题分解为一系列同类型的更易求解的子问题，便于应用计算机。,2019/7/9,23,6.2 动态规划的基本概念和基本方程,(一) 基本概念和基本方程,(1) 阶段：k=1,，n,(2) 状态变量sk ：第k阶段的状态. 状态变量取值的集合成为状态集合，用Sk表示。状态集合可以是一离散取值的集合，也可以为一连续的取值区间，视具体问题而定,(3) 决策变量uk(sk) ：第k阶段的决定，Dk(sk)为决策变量的取值范围. 状态转移方程sk1 T (sk,uk)：描述第k阶段与第k+1阶段的状态变量的关系,2019/7/9,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阶段的终止状态的过程，采取最优策略得到的指标函数值,阶段函数,2019/7/9,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.,2019/7/9,27,(3) 决策变量uk ：在第k段sk状态时决定选取的下一段的某点.,(4) 状态转移方程 ：sk1 uk ( sk),(5) 阶段效益： d(sk,uk)为第k段，采取决策uk 到下一状态的距离.,(6) 最优指标函数： fk (sk)：第k段，在sk状态时到终点E的最短距离.,逆推公式：,2019/7/9,28,（二）贝尔曼最优化原理： 一个最优策略具有这样的性质，即不论初始状态与初始策略如何，对于先前决策所造成的状态而言，余下所有决策必构成最优决策。 也即：一个最优策略的子策略也是最优的。,2019/7/9,29,（三）解法步骤 反向条件优化 正向求最优解,2019/7/9,30,6.3 应用举例,例2 资源分配问题-1 例3 资源分配问题-2 例4 背包问题 例5 生产库存问题 例6 可靠性问题 例7 机器负荷分配问题 等等,2019/7/9,31,例 2 资源分配问题-1,某公司准备将5台设备分配给所属的三个子工厂，各工厂获得设备后的可盈利情况如表所示。问：如何分配这五台设备，才能使公司获得的收益最大？,2019/7/9,32,分析,(1) 阶段：k=1,2,3.,(3) 决策变量uk ：对第k个企业的分配数.,(2) 状态变量sk ：对第k至3个企业可分配的设备数 或：第k阶段初可分配的设备数.,(4) 状态转移方程： sk1 sk uk.,(5) 最优指标函数fk (sk) ：第k至3个企业采取最优分配策略可产生的最大收益.,设分配给第k个工厂的机器数为uk,工厂1,工厂2,工厂3,2019/7/9,33,其中，gk (uk)是阶段函数,逆推公式：,sk+1,2019/7/9,34,k=3 ,S3 = 0,1,2,3,4,5 , f3(s3) maxg3(u3)+0,2019/7/9,35,k=2 ,S2 = 0,1,2,3,4,5 , f2(s2) maxg2(u2)+ f3(s3),S3=S2-u3,2019/7/9,36,k=1 ,S1 = 5, f1(s1) max g1(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万元。,同理得到另一组最优解,2019/7/9,37,一般分配问题,某种资源，总量为a，分配于n种生产。若分配 ui 用于第 i 种生产，收益为gi (ui ) 。 问：应如何分配才能使总收入最大？ 容易建立其数学模型：,2019/7/9,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) 状态转移方程： sk1 sk - 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) max g1(u1)* f2(s2),得到方案： u1*1，u2*0，u3*1: 产品 A分配1百万，产品 B分配0，产品 C分配1百万 f*=0.06,2019/7/9,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/t1 u1为整数,状态转移方程：背包容量和装载件数的关系,阶段指标： vk(sk,uk)=rkuk 在背包中第k种物品的价值,最优指标： fk(sk)=maxrkuk+fk+1(sk+1),终端条件：,f4(s4)=0,s2s1-t1x1,s3=s2-t2x2,s4=s3-t3x3,0u2s2/t2 u2为整数,0u3s3/t3, 2 u3为整数,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,2019/7/9,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个季度的生产，以保证在满足市场需求的前提下，使生产和库存总费用最小?,2019/7/9,53,假设：第 k季度可以销售的产品是本季度初的库存及本季度的产量,(1) 阶段：k=1,2,3,4 n=4.,(2)状态变量sk ：第k季度初的库存量.,(3)决策变量uk ：第k 个季度的产量.,(4) 转移方程： sk1 sk +uk- dk.,(5) 最优指标函数 fk (sk) ：第k季度至第4个季度采取最优策略时的最小总费用.,2019/7/9,54,逆推公式：,k=4,k=3,K=2,k=1,2019/7/9,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 - ck uk tk+1 =tk - wk uk,(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)= max dk(sk，uk)fk+1(skckuk)， f4(s4)=1,采用后向动态规划法，从第3阶段算起。,阶段2，此时考虑当把钱用于购置B和C部件时，各应购置多少个部件为最优。 显然，此时B、C应至少各配制1个部件，故s2c2+c3=2+3=5；同时，A部件亦至少配备1