资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章 动态规划,不要过河拆桥,动态规划,Dynamic programming,五十年代贝尔曼(,B.E.Bellman,),为代表的研究成果,属于现代控制理论的一部分,以长远利益为目标的一系列决策,最优化原理，可归结为一个递推公式,5.1,动态规划的最优化原理及其算法,5.1.1 求解多阶段决策过程的方法,例5.1.1 最短路问题,2,决策树法,可以枚举出20条路径，其中最短的路径长度为16,3,例,5.1.1,最短路问题,表现为明显的阶段性,一条从,A,到,B,的,最短路径中的任何一段都是最短的,最优性原理,“最优策略的一部分也是最优的,”,每步的决策只与相邻阶段状态有关，而与如何达到这一状态无关,因此我们可以从,B,向回搜索最短路,标记法,如何找出最短路径,4,5.1.2,动态规划的基本概念及递推公式,状态,(每阶段初始的出发点),最短路问题中，各个节点就是状态,生产库存问题中，库存量是状态,物资分配问题中，剩余的物资量是状态,控制变量,(决策变量),最短路问题中，走哪条路,生产库存问题中，各阶段的产品生产量,物资分配问题中，分配给每个地区的物资量,阶段的,编号,与递推的,方向,一般采用反向递推，所以阶段的编号也是逆向的,当然也可以正向递推,5,动态规划的步骤,1、确定问题的阶段和编号,2、确定状态变量,用,S,k,表示第,k,阶段的状态变量及其值,3、确定决策变量,用,x,k,表示第,k,阶段的决策变量，并以,x,k,*,表示该阶段的最优决策,4、状态转移方程,s,k,-1,=,g,(,s,k,x,k,),反向编号,s,k,+1,=,g,(,s,k,x,k,),正向编号,5、直接效果,直接一步转移的效果,d,k,(,s,k,x,k,),6、,总效果函数,指某阶段某状态下到终端状态的总效果，它是一个递推公式,6,动态规划的步骤,h,k,是一般表达形式，求当前阶段当前状态下的阶段最优总效果,(1)如最短路问题，是累加形式，此时有,终端的边际效果一般为,f,0,(,s,0,x,0,)=0,(2),如串联系统可靠性问题，是连乘形式，此时有,终端的边际效果一般为,f,0,(,s,0,x,0,)=1,从第1阶段开始，利用边际效果和边界条件，可以递推到最后阶段,7,5.2 动态规划模型举例,5.2.1 产品生产计划安排问题,例1,某工厂生产某种产品的月生产能力为10件，已知今后四个月的产品成本及销售量如表所示。如果本月产量超过销售量时，可以存储起来备以后各月销售，一件产品的月存储费为2元，试安排月生产计划并做到：,1、保证满足每月的销售量，并规定计划期初和期末库存为零；,2、在生产能力允许范围内，安排每月生产量计划使产品总成本(即生产费用加存储费)最低。,8,例1 产品生产计划安排,设,x,k,为第,k,阶段生产量，则有直接成本,d,k,(,s,k,x,k,)=,c,k,x,k,+2,s,k,状态转移公式为,s,k,-1,=,s,k,+,x,k,-,y,k,总成本递推公式,第一阶段,：(即第4月份),由边界条件和状态转移方程,s,0,=,s,1,+,x,1,y,1,=,s,1,+,x,1,6=0,得,s,1,+,x,1,=6,或,x,1,=6,s,1,0,估计,第一阶段，即第4月份初库存的可能,状态：,0,s,1,306712=5，,所以，,s,1,0,5,9,第一阶段最优决策表,第二阶段,：最大可能库存量 7 件,由状态转移方程：,s,1,=,s,2,+,x,2,12,0,及,x,2,10，,可知,s,2,2,7，min,x,2,=5,由阶段效果递推公式有：,f,2,(2,10)=,d,2,(2,10)+,f,1,*(0,6)=2,2+8010+456=1260,得第二,阶段最优决策表，如下,10,第二阶段最优决策表,第三阶段,：最大可能库存量 4 件,由状态转移方程：,s,2,=,s,3,+,x,3,7,2,及,x,3,10，,可知,s,3,0,4，min,x,3,=5,由阶段效果递推公式有：,f,3,(1,10)=,d,3,(1,10)+,f,2,*(4,8)=2,1+,7210+1104=1826,得第三,阶段最优决策表，如下,11,第三阶段最优决策表,第四阶段,：初始库存量,s,4,=0,由状态转移方程：,s,3,=,s,4,+,x,4,6,0,可知,x,4,6，,由阶段效果递推公式有：,f,4,(0,6)=,d,4,(0,6)+,f,3,*(0,10)=,706+1902=2322,得第四,阶段最优决策表，如下,回,溯,得,此,表,12,例,2,生产库存管理问题,(,连续变量,),设某厂计划全年生产某种产品,A。,其四个季度的订货量分别为600公斤，700公斤，500公斤和1200公斤。已知生产产品,A,的生产费用与产品的平方成正比，系数为0.005。厂内有仓库可存放产品，存储费为每公斤每季度1元。求最佳的生产安排使年总成本最小。,解,：四个季度为四个阶段，采用阶段编号与季度顺序一致。,设,s,k,为第,k,季初的库存量，则边界条件为,s,1,=,s,5,=0,设,x,k,为第,k,季的,生产,量，,设,y,k,为第,k,季的订货量；,s,k,，,x,k,，,y,k,都取实数，状态转移方程为,s,k,+1,=,s,k,+,x,k,-,y,k,仍采用反向递推，但注意阶段编号是正向的,目标函数为,13,例,2,生产库存管理问题,(,连续变量,),第一步,：(第四季度)总效果,f,4,(,s,4,x,4,)=0.005,x,4,2,+,s,4,由边界条件有：,s,5,=,s,4,+,x,4,y,4,=0，,解得：,x,4,*=1200,s,4,将,x,4,*,代入,f,4,(,s,4,x,4,),得：,f,4,*(,s,4,)=0.005(1200,s,4,),2,+,s,4,=7200 11,s,4,+0.005,s,4,2,第二步,：(第三、四季度)总效果,f,3,(,s,3,x,3,)=0.005,x,3,2,+,s,3,+,f,4,*(,s,4,),将,s,4,=,s,3,+,x,3,500,代入,f,3,(,s,3,x,3,),得：,14,例,2,生产库存管理问题,(,连续变量,),第三步,：(第二、三、四季度)总效果,f,2,(,s,2,x,2,)=0.005,x,2,2,+,s,2,+,f,3,*(,s,3,),将,s,3,=,s,2,+,x,2,700,代入,f,2,(,s,2,x,2,),得：,注意,：阶段最优总效果仅是当前状态的函数，与其后的决策无关,15,例,2,生产库存管理问题,(,连续变量,),第四步,：(第一、二、三、四季度)总效果,f,1,(,s,1,x,1,)=0.005,x,1,2,+,s,1,+,f,2,*(,s,2,),将,s,2,=,s,1,+,x,1,600=,x,1,600,代入,f,1,(,s,1,x,1,),得：,由此,回溯,：得最优生产库存方案,x,1,*=600，,s,2,*=0；,x,2,*=700，,s,3,*=0；,x,3,*=800，,s,4,*=300；,x,4,*=900。,16,5.2.2,资源分配问题,例3,某公司有9个推销员在全国三个不同市场推销货物，这三个市场里推销人员数与收益的关系如下表，试作出使总收益最大的分配方案。,解,：设分配人员的顺序为市场1,2,3，采用反向阶段编号。,设,s,k,为第,k,阶段尚未分配的人员数，边界条件为,s,3,=9,设,x,k,为第,k,阶段分配的推销人员数；,仍采用反向递推，,状态转移方程为,s,k,1,=,s,k,x,k,目标函数为,17,例3,第一阶段：给第三市场分配,s,1,有,09种可能，第一阶段最优决策表如下：,为什么与,例1,的第一阶段的表有差别？,因为不存在边界条件,s,0,=0,18,例3,第二阶段：给第二市场分配,s,2,有,09种可能，第二阶段最优决策表如下：,19,例3,第三阶段：给第一市场分配,由边界条件,s,3,=9，,第三阶段最优决策表如下：,得决策过程：,x,3,*=2,x,2,*=0,x,1,*=7,f,3,*=218,即 市场1 分配 2人，市场2 不分配，市场3 分配 7人,最优解与分配的顺序有关吗,？,20,5.2.2,资源分配问题,例4,项目选择问题,某工厂预计明年有,A,B,C,D,四个新建项目，每个项目的投资额,w,k,及其投资后的收益,v,k,如右表所示。投资总额为30万元，问如何选择项目才能使总收益最大。,上述问题的静态规划模型如下：,这是一类,0-1规划问题,该问题是经典的,旅行背包问题,(,Knapsack),该问题是,NP-complete,21,例,4,项目选择问题,解,：设项目选择的顺序为,A,B,C,D;,1、,阶段,k,=1,2,3,4,分别,对应,D,C,B,A,项目的选择过程,2、第,k,阶段的状态,s,k,，,代表第,k,阶段初尚未分配的投资额,3、第,k,阶段的决策变量,x,k,，,代表第,k,阶段分配的投资额,4、,状态转移方程为,s,k,1,=,s,k,w,k,x,k,5、,直接效益,d,k,(,s,k,x,k,)=,v,k,或,0,6、总效益递推公式,该问题的难点在于各阶段的状态的确定，当阶段增加时，状态数成指数增长。下面利用决策树来确定各阶段的可能状态。,22,23,例,4,第一阶段(项目,D,),的选择过程,s,1,8,时,，,x,1,只能取0；,w,1,=8,v,1,=5,24,例,4,第二阶段(项目,C,),的选择过程,25,例,4,第三阶段(项目,B,),的选择过程,第四阶段(项目,A,),的选择过程,26,5.2.3,串联系统可靠性问题,例5,有,A,B,C,三部机器串联生产某种产品，由于工艺技术问题，产品常出现次品。统计结果表明，机器,A,B,C,产生次品的概率分别为,p,A,=30%,P,B,=40%,P,C,=20%,而产品必须经过三部机器顺序加工才能完成。为了降低产品的次品率，决定拨款,5 万元进行技术改造，以便最大限度地提高产品的成品率指标。现提出如下四种改进方案：,方案1:不拨款，机器保持原状；,方案2:加装监视设备，每部机器需款 1 万元；,方案3:加装设备，每部机器需款 2 万元；,方案4:同时加装监视及控制设备，每部机器需款 3 万元；,采用各方案后，各部机器的次品率如下表。,27,例,5,串联机器可靠性问题,解,：为三台机器分配改造拨款，设拨款顺序为,A,B,C,，,阶段序号反向编号为,k,，,即第一阶段计算给机器,C,拨款的效果。,设,s,k,为第,k,阶段剩余款，则边界条件为,s,3,=5,；,设,x,k,为第,k,阶段的,拨款额,；,状态转移方程为,s,k,-1,=,s,k,-,x,k,；,目标函数为,max,R,=(1-,P,A,)(1-,P,B,)(1-,P,C,),仍采用反向递推,第一阶段,：对机器,C,拨款的效果,R,1,(,s,1,x,1,)=,d,1,(,s,1,x,1,),R,0,(,s,0,x,0,)=,d,1,(,s,1,x,1,),28,第二阶段最优决策表,第二阶段,：对机器,B,C,拨款的效果,由于机器,A,最多只需,3,万元，故,s,2,2,递推公式：,R,2,(,s,2,x,2,)=,d,2,(,s,2,x,2,),R,1,(,s,1,x,1,*),例：,R,2,(3,2)=,d,2,(3,2),R,1,(1,1)=(1-0.2),0.9=0.72,得,第二阶段最优决策表,29,第二阶段最优决策表,第三阶段,：对机器,A,B,C,拨款的效果,边界条件：,s,3,=5,递推公式：,R,3,(,s,3,x,3,)=,d,3,(,s,3,x,3,),R,2,(,s,2,x,2,*),例：,R,3,(5,3)=,d,3,(5,3),R,2,(2,2)=(1-0.05),0.64=0.
展开阅读全文