管理运筹学-动态规划.ppt

,第 7 章,Dynamic Programming,DP,动 态 规 划,第7章 动态规划,2,7.1 引言 7.2 基本概念 7.3 离散确定型典例 7.4 其他典例,第7章 动态规划,第7章 动态规划,3,Sk+1,S2,7.1. 1 多阶段决策问题 阶段、决策、策略 7.1. 2 动态规划的基本特性 一、多阶段决策问题的基本特性,7.1 引言,Sk,Sk+1,Sn,T,Sn,Q = S1,反证法容易得证。,若 S2 , , Sk , Sk+1 , , Sn , T 全程最优,则 Sk+1 , , Sn , T 子程最优,第7章 动态规划,4,7.1 引言,二、 动态规划方法的基本思路,例1 最短路问题,1,2,3,4,3,4,0,4,7,6,11,7,8,11,阶段, 标号法,第7章 动态规划,5,三、决策 是指人们对某一阶段活动中各种不同的行为或方案或途径等的 一种选择。 用xk表示第k段的决策，称为第k段决策变量。由于决策随状态 而变,所以决策变量xk是状态变量sk的函数,记为 xk= xk(sk),7.2 基本概念,7.2.1 动态规划的基本概念 一、阶段 把所研究的问题恰当的划分成若干个相互联系的阶段。用 k = 1，2，n 表示阶段序号，称为阶段变量。 二、状态 状态表示某段的初始条件。用sk表示第k段的状态，称为第k段 状态变量。,skSk,Xk,第7章 动态规划,6,7.2 基本概念,四、状态转移方程 sk+1与sk,xk之间必须能够建立一种明确的数量对应关系，记为 Tk(sk,xk), 即有 sk+1 = Tk(sk,xk) 这种明确的数量关系称为状态转移方程。,五、策略 由各阶段决策xk构成的决策序列,称为全过程策略,简称策略,记为 p1(s1),有 p1(s1) = x1(s1),x2(s2), ,xn(sn) pk(sk) = xk(sk),xk+1(sk+1), ,xn(sn) Pk 称为第k子过程策略，简称子策略。,P1,而,第7章 动态规划,7,7.2 基本概念,六、指标函数 (1) 阶段指标函数 用vk(sk,xk)表示第k段处于sk状态且所作决策为xk 时的指标，则它就是第k段指标函数，简记为vk。,P1,(2) 过程指标函数 用fk(sk,xk)表示第k子过程的指标函数。 它是各vk的累积效应。 常用函数：,积函数,和函数,第7章 动态规划,8,七、最优解 (1) 最优指标函数 fk*(sk) = opt fk(sk, pk(sk), k=1,2,n pkPk (2) 最优策略 能使上式成立的子策略pk*称为最优子策略，记为 pk* (sk) = xk*(sk), ,xn*(sn) 特别当k=1时,称为最优策略，记为 p1* (s1) = x1*(s1), ,xk*(sk), ,xn*(sn) (3) 最优决策 构成最优策略的决策称为最优决策，记为xk*。 (4) 最优值：最优策略对应的最优指标 f *1,7.2 基本概念,第7章 动态规划,9,7.2 基本概念,7.2.2 动态规划的基本方程 一、最优化原理 作为一个全过程最优策略具有这样的性质： 无论过去的状态和决策如何，对前面所形成的状态而言， 余下的诸决策必构成最优策略。 二、函数基本方程 f*n+1(sn+1) = 0 f*k(sk) = opt vk(sk,xk)+fk+1*(sk+1) xkXk f*n+1(sn+1) = 1 f*k(sk) = opt vk(sk,xk) fk+1*(sk+1) xkXk,和,积,k = n, n-1, , 2, 1,k = n, n-1, , 2, 1,第7章 动态规划,10,7.2 基本概念,7.2. 3 动态规划的基本方法 1建立模型 (1) 划分阶段，设定 k (2) 设定状态变量 sk (3) 设定决策变量 xk (4) 建立状态转移方程 (5) 确定指标函数 vk，fk* (6) 建立函数基本方程 2递推(逆推)求解 3得出(顺推)结论,第7章 动态规划,11,7.2 基本概念,7.2. 4 动态规划的基本类型 一、按阶段变量k划分 (1) 定期型: k = 1, 2, , n (2) 不定期型: k = 1, 2, , n (解前未知) (3) 无期型: k = 1, 2, , n , 二、按状态变量sk划分,确定型,随机型,离散型,连续型,第7章 动态规划,12,7.3 离散确定型典例,7.3.1 定价问题 例2 某厂要确定一种新产品在今后五年内的价格，并已拟定只在 5、6、7、8 元这四种单价中进行选择。 据预测， 今后五年不同价格下每年盈利如表所示, 但是各相邻年度价格增减不超过 1 元。问今后五年内每年定价各为多少,可预期五年总利润最大？,盈利：万元,第7章 动态规划,13,7.3 离散确定型典例,13,14,11,10,18,22,23,17,24,28,28,30,37,35,36,38,p1* = 8, 8 , 7, 6 , 5 (元),f *1 = 38 万元,第7章 动态规划,14,7.3 离散确定型典例,7.3. 2 资源分配问题,例3 某厂为扩大生产能力，拟定购某种成套设备46套,以分配给 其所辖三个分厂使用。预计各分厂分得不同套数的设备后每年创造的 利润如下表所示。该厂应订购几套设备并如何分配，才能使每年预计 创利总额最大？,盈利：万元,第7章 动态规划,15,7.3 离散确定型典例,解 1. 建立DP模型 以 k = 1，2，3 表示给三个分厂分配的顺序。 设 sk = 在给k分厂分配时尚余的套数； xk = 分给k分厂的套数； 可知状态方程为 sk+1 = sk - xk vk ( sk, xk ) = 从现有sk套设备中分给k分厂xk套 设备后的预计创利额； fk ( sk, xk ) = 将现有sk套设备从 k - 3 分配后 (其中k分厂分得xk套)的预计创利额之和；,第7章 动态规划,16,7.3 离散确定型典例,函数基本方程为 f4*(s4) = 0,还有 fk(sk ,xk) = vk(sk, xk) + fk+1*(sk+1) 2 . 按逆序递推法逐段求解 (1) k=3 此时，1，2厂已分完，而目前所剩设备套数为 s3= 0，1，2，3，4，5，6 允许决策为 x3= 0，1，2，3，4，5，6 得下表。,第7章 动态规划,17,7.3 离散确定型典例,0 0 0 0 0 0,0,2,5,9,8,8,7,8,8 8,9 9 9,5 5 5 5,2 2 2 2 2,9 9 9 9,0,2,5,3 3 3 3,0,1,2,(1) k=3,第7章 动态规划,18,7.3 离散确定型典例,(2) k=2,s3 = s2 - x2,0 0 0 0 0 0,0,4,6,7,8,9,10,9,8 8,7 7 7,6 6 6 6,4 4 4 4 4,+0 +2 +5 +9 +9 +9 +9,+9,+0 +2 +5 +9 +9 +9,+0 +2 +5 +9,+0 +2 +5 +9,+0 +2 +5,+0 +2,+0,9,0,4,6,0,1,1,2,0,1,13,1,15,2,16,3,第7章 动态规划,19,7.3 离散确定型典例,(3) k=1,s2 = s1 x1,0 0,0,3,5,6,6,5,6,+13 +15 +16,+0 +4,+0,3 3,7,5 5,6 6,7 7,+9 +13 +15,+6 +9 +13,+4 +6 +9,+0 +4 +6,13,0,16,1,18,1, 2,p1*(6) = 1, , 或2, , (套),2,3,1,3,f1*(6) = 18 (万元),第7章 动态规划,20,7.3 离散确定型典例,3. 顺序递推，得出结论 按 k = 1，2，3的顺序，依次查看各表的sk列与xk*列， 并按 sk+1= sk - xk* 的转移规律将最优决策衔接为最优策略。 表7-5中s1 = 6时 f *1(s1) =18，值最大，故s1* = 6。顺次查 看 k = 1，2，3 时的表格，可知最优策略为： p1*(s1* = 6) = 1, 2, 3 或 2, 1, 3 即该厂应订购6套该设备，可分给1，2，3分厂 1，2，3 套 或 2，1，3 套。这样预计每年创利最大，为18万元。,第7章 动态规划,21,7.3 离散确定型典例,7.3. 3 生产调度问题 例4 某厂根据市场预测，确认今后四个月该厂的一种主要 产品每月需求量如下表所示。已知每月生产固定费用b=2 千元，但若当月不生产则b=0；产品成本为c=1千元/万件； 存贮费用为h=0.2千元/万件/月；每月最大生产能力为a=5 万件,最大存贮能力为=4万件。若第1月初无库存产品， 第4月末也不留库存，则该厂应如何安排生产，才能使今后 四个月的总费用最少？,第7章 动态规划,22,7.3 离散确定型典例,解：1 . 建立模型 令 k = 1，2，3，4 表示今后4个月的序号。 设 sk = 第k月初 (或第k-1月末) 的库存量； xk = 第k月的产量； 令以dk表示第k月的需求量，则状态转移方程为 sk+1 = sk+ xk- dk 设：vk( sk,xk ) = 第k月生产费用； fk(sk,xk ) = 第k月初到第4月末的生产费用； fk*(sk) = 第k月初到第4月末的最低生产费用；,第7章 动态规划,23,7.3 离散确定型典例,由题意知:,vk (sk,xk) =,=,fk(sk, xk ) = fk+1* ( sk+1 ) +,xk = xk| 0xk 5 ,上式中的允许决策集合为,fk*(sk) = min fk(sk,xk )， k = 4, 3, 2, 1,f5*(s5 ) = 0,函数基本方程为,2+xk+0.25sk， 当 xk 0 0.2sk， 当 xk = 0,0.2sk 当 xk = 0,2+xk+0.2sk 当 xk 0,hsk 当 xk = 0,b+cxk+hsk， 当 xk 0,第7章 动态规划,24,7.3 离散确定型典例,2 . 逆序递推求解,k=4,(1) k = 4,已知 d4= 2，s5= 0，由 s5 = s4 +x4 -2 得 s4= 2 - x4 2 故s4= 0，1，2，则 x4 的值也随之确定了。,4,3.2,0.4,2,1,0,第7章 动态规划,25,7.3 离散确定型典例,(2) k = 3 d3 = 3，由上知 0 s4 2，由 s4 = s3 + x3 -3 得 0 s3 + x3 -3 2， 即 3 s3 + x3 5 又 s3 = 4， 故 s3 = 0, 1，2，3，4 则有 X3 = x3 | 3 s3 + x3 5，s3 = 0,1 ,2 ,3 ,4 ,第7章 动态规划,26,7.3 离散确定型典例,k=3,4.6,4,9.0,8.2,7.4,9.2,7.4,8.4,7.6,6.8,6.6,5.8,5.0,4.2,7.4,5,6.6,5.8,4.6,4.0,4,3,0,0,s4= s3+x3- 3,第7章 动态规划,27,7.3 离散确定型典例,(3) k = 2 d2 = 2，由 0 s3 4，又 s3 = s2 + x2 -2, 可得 0 s2 +x2 -2 4 或 2 s2+x2 6 又由假设条件可知 s1 = 0，则 s2 = s1 + x1 - d1 = x1 - 3 因 x1 5，故 s2 = x1 - 3 5 - 3 = 2 即 s2 = 0，1，2； 则 x2 的取值也相应确定了。,第7章 动态规划,28,7.3 离散确定型典例,k=2,s3 = s2 + x2 - 2,11.4,11.4,11.6,11.8,11.6,11.2,10.6,10.8,11.0,10.8,10.0,10.2,10.0,10.4,7.8,10.6,7.8,2,1,0,第7章 动态规划,29,7.3 离散确定型典例,由上已知 s1 = 0， s2 = x1 -3 因s2 0，故 x1 3，但x1 5，则 x1 = 3, 4, 5;可得：,k=1,s2= x1- 3,3. 顺推结论 按例3的方法，可以推知最优解： p1* = 5，0，5，0 (万件) 最优值： f1* = 14.8 (千元) 即第1, 3月分别生产5万件，第2, 4月不生产。,5,14.8,第7章 动态规划,30,7.4 其他典例,7.4.1 机器负荷分配问题(连续确定型典例) 例5 设有100台同一规格的完好自动机床，每台机床 全年在高负荷下工作可创利9万元，折损率为0.75；在低负 荷下工作可创利6万元， 折损率为0.96。 试拟订连续四年的分配计划，使总利润最大。 解 设以 k = 1，2，3，4 表示年度； sk = 第k年初（第k-1年末）拥有的机床当量台数 (有效台年) ； xk = 第k年度分配于高负荷下工作的机床当量台数；,第7章 动态规划,31,Sk+1 = 0.75xk+0.96(sk-xk) = 0.96sk -0.21xk vk(sk,xk) = 9xk+6(sk-xk) = 3xk +6sk f5*(s5) = 0 fk*(sk) = max3xk+6sk+f*k+1(0.96sk-0.21xk), k = 4,3,2,1,7.4 其他典例,0xk sk,(1) k = 4 f4*(s4) = max 3x4+6s4 0x4 s4 由于 f4(s4, x4)=3x4+6s4 为关于x4 的线性单增函数,故有 x4* = s4， f4*（s4）= 9s4,第7章 动态规划,32,(2) k = 3 由于 f3*(s3) = max3x3+6s3+9(0.96s3-0.21x3) = max1.11x3+14.64s3 ， 故有 x3* = s3 ， f3*（s3）= 15.75s3 (3) k = 2 由于 f2*(s2) = max3x2+6s2+15.75(0.96s2-0.21x2) = max21.12s2 -0.3075x2， 故有 x2* = 0 ， f2 *(s2) = 21.12s2,7.4 其他典例,0x3 s3,0x2 s2,第7章 动态规划,33,7.4 其他典例,(4) k = 1 类似 k=2 情形，可得 x1* = 0, f1*(s1) = 26.2752s1 因s1 = 100，故 f1* = 2627.52 (万元) 最优策略为 x1* = x2* = 0， x3* = s3， x4* = s4 机床当量台数： s2 = 0.96s1-0.21x1* = 0.96s1 = 96 s3 = 0.96s2-0.21x2* = 0.96s2 = 92.16 s4 = 0.96s3-0.21x3* = 0.75s3 = 69.12 s5 = 0.96s4-0.21x4* = 0.75s4 = 51.84,第7章 动态规划,34,7.4 其他典例,四年内机床负荷分配最优计划,第7章 动态规划,35,7.4 其他典例,7.4.2 采购问题(离散随机型典例) 例6 某厂供应科必须在今后5周内购买一原料， 以保证第六周生产之用。 根据过去的统计资料， 预计该原料今后每周的 价格如右表所示。 应如何拟订采购策 略，才能期望原料价格 最低？,第7章 动态规划,36,解 用 k = 1, 2, 3, 4, 5 表示今后每周的序号； 设：sk = 第k周的原料价格； xk = 第k周的决策；xk = 1（采购）或 0（等待）； fk*(sk) = 源于sk状态的第k周以后的最低期望价格； 第k段状态集 sk = 500，550，600 ；状态概率分布为 p sk = 500 = 0.3， p sk = 550 = 0.3， p sk = 600 = 0.4 令 E (sk+1) = p(sk+1) fk+1*(sk+1) = 0.3 fk+1*(500) + 0.3 fk+1*(550) + 0.4 fk+1*(600) 则函数方程为 fk*(sk) = min sk，E(sk+1)， k = 4，3，2，1 又因第五周只得采购，即 x5* = 1， 故有 f5*(s5) = s5 此即函数的边界条件。而第k子过程指标函数为 sk 当 xk = 1 E (sk+1) 当 xk = 0,7.4 其他典例,fk (sk, xk) =,第7章 动态规划,37,7.4 其他典例,fk+1* (500),fk+1* (550),fk+1* (600),sk,xk,500,550,600,阶段k,指标,阶段k+1,状态,指标,0.3,0.3,0.4,f k (sk,xk) = sk,xk= 0（等待）,fk(sk,xk) = E(sk+1),xk=1(采购),状态,决策,其基本结构可表示为下图：,第7章 动态规划,38,(1) k = 5 最后一周，只有唯一决策：按该周价格采购，有,7.4 其他典例,(2) k = 4 第4周，有两种决策：采购或等待。按函数方程有 f4*(s4) = min s4 ，E(s5) 而 E (s5) = 0.3 f5*(500) + 0.3 f5*(550) + 0.4 f5*(600) = 0.3 500 + 0.3 550 + 0.4 600 = 555 故有,f5*(s5) = s5,500， 当s5 = 500 550， 当s5 = 550 600， 当s5 = 600,=,第7章 动态规划,39,7.4 其他典例,f4*(s4) = min s4 , 555 500，当s4 = 500 (x4* = 1 ) 550，当s4 = 550 (x4* = 1 ) 555，当s4 = 600 (x4* = 0 ),=,x4*= 1,x4* = 0,第7章 动态规划,40,类似可求得 500， 当s3 = 500， (x3* = 1) 537， 当s3 = 550 或 600 (x3* = 0) 500， 当s2 = 500 (x2* = 1) 526, 当s2 = 550 或 600 (x2* = 0) 500， 当s1= 500 (x1* = 1) 518， 当s1= 550 或 600 (x1* = 0),7.4 其他典例,f3* (s3) = min s3 , 537 ,f2*(s2) =,f1*(s1) =,=,第7章 动态规划,41,根据以上结果，可得最优采购策略为： 若前三周原料价格为500元，则应立即采购，否则 等待以后再采购； 第四周当原材料价格为500或550元时，都应立即 采购，否则等待到第五周再采购； 若前四周均未采购，则第五周无论原料价格如何， 都应立即按价采购； 这样，原料期望价格最低为： f0* = 0.3 500 + (0.3 + 0.4) 518 = 513 (元),7.4 其他典例,第7章 动态规划,42,7.4 其他典例,7.4.3 试制品批量问题 (离散随机型典例) 例7 某厂按合同要为用户制造一台特殊设备，据估计一台该设 备的制造费用为100元，而其合格品的概率为0.4，每制造一批的 准备费用为300元。若一批试制品全不合格，可再试制一批，但 在规定期限内最多试制三批。若三批未得到一台合格品，则要赔 偿用户2000元。该厂每批试制几台能使总