资源预览内容
第1页 / 共26页
第2页 / 共26页
第3页 / 共26页
第4页 / 共26页
第5页 / 共26页
第6页 / 共26页
第7页 / 共26页
第8页 / 共26页
第9页 / 共26页
第10页 / 共26页
亲,该文档总共26页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第6章 动态规划,动态规划的基本理论 (2学时) 确定型动态规划 (2学时) 随机型动态规划 (1学时) 动态规划的软件求解简介 (1学时),一、离散随机性动态规划 随机型的动态规划是指状态的转移律是不确定的,即对给定的状态和决策,下一阶段的到达状态是具有确定概率分布的随机变量,这个概率分布由本阶段的状态和决策完全确定。随机型动态规划的基本结构如下图:,sk,状态,xk,决策,概率,k阶段的收益,p1,p2,pN,.,k+1阶段的状态sk+1,c1,c2,cN,1,2,N,第15讲 随机型动态规划及软件介绍,图中N表示第k+1阶段可能的状态数,p1、p2、pN为给定状态sk和决策xk的前提下,可能达到下一个状态的概率。ci为从k阶段状态sk转移到k+1 阶段状态为i时的指标函数值。 在随机性的动态规划问题中,由于下一阶段到达的状态和阶段的效益值不确定,只能根据各阶段的期望效益值进行优化。,例1 某公司承担一种新产品研制任务,合同要求三个月内交出一件合格的样品,否则将索赔2000元。根据有经验的技术人员估计,试制品合格的概率为0.4,每次试制一批的装配费为200元,每件产品的制造成本为100元。每次试制的周期为1个月。问该如何安排试制,每次生产多少件,才能使得期望费用最小?(类例教材1:例6-7),解:把三次试制当作三个阶段(k=1,2,3),决策变量xk表示第k次生产的产品的件数;状态变量sk表示第k次试制前是否已经生产出合格品,如果有合格品,则sk=0;如果没有合格品,记sk=1。最优函数fk(sk)表示从状态sk、决策xk出发的第k阶段以后的最小期望费用。故有fk(0)0。 生产出一件合格品的概率为0.4,所以生产xk件产品都不合格的概率为 ,至少有一件合格品的概率为1- ,故有状态转移方程为,用C(xk)表示第k阶段的费用,第k阶段的费用包 括制造成本和装配费用,故有 根据状态转移方程以及C(xk),可得到,如果3个月后没有试制出一件合格品,则要承担 2000元的罚金,因此有f4(1)=20。 当k=3时,计算如下表:,当k=2时,计算如下表:,当k=1时,有,上面三个表中并没有列出xk取更大数值的情况,因为可以证明以后的C(xk)+ fk+1(1)的值是对xk单调增加的。 因此得到的最优策略是,在第1个阶段试制2件产品;如果都不合格,在第2阶段试制3件产品;如果仍都不合格,则在第3个阶段试制5件产品。该策略得到的最小的期望费用6.46。,例2 不确定性采购问题(类例教材1:例6-8) 某厂生产上需要在近五周内必须采购一批原料,而估计在未来五周内原材料的价格是波动的,浮动价格和概率已知。如何采购使其采购价格的数学期望最小,并求出期望值。,动态规划的数学模型 该问题分成五个阶段,k表示周,k1,2,3,4,5 设Sk表示为第k周的实际价格。 决策变量Uk,Uk1表示为第k周决定采购,Uk0表示为第k周决定等待。 XkE表示为第k周决定等待,而在以后采取最优决策时采购价格的期望值。 fk(Sk)表示第k周实际价格为Sk时,从第k周到第5周采取最优策略所得的最小期望值。,递推关系式: fk(Sk)minSk,XkE 边界条件:f5(S5)S5 其中:XkE=0.3 fk+1(500)+0.3 fk+1(600)+ 0.4fk+1(700) Sk500,600,700,f5(S5)S5 S5500,600,700 f5(500)500 f5(600)600 f5(700)700 即在第五周,不论原材料的市场价格如何,都必须购买。,当k=5时,f4(S4)minS4,X4E X4E=0.3 f5(500)+0.3 f5(600)+ 0.4f5(700)610 f4(500)500 f4(600)600 f4(700)610,当k=4时,U41 ,当S4500,600 U40 ,当S4700 即在第四周时,当市场价格为500或600时,选择购买原材料。若市场价格为700时,则继续等待。,当k=3时, f3(S3)minS3,X3E X3E=0.3 f4(500)+0.3 f4(600)+ 0.4f4(700)574 f3(500)500 f3(600)574 f3(700)574 U31 ,当S3500 U30 ,当S3600,700 即在第三周时,当市场价格为500时,选择购买原材料。若市场价格为600或700时,则继续等待。,当k=2时, f2(S2)minS2,X2E X2E=0.3 f3(500)+0.3 f3(600)+ 0.4f3(700)551.8 f3(500)500 f3(600)551.8 f3(700)551.8 U21 ,当S2500 U20 ,当S2600,700 即在第二周时,当市场价格为500时,选择购买原材料。若市场价格为600或700时,则继续等待。 当k=1时, f1(S1)minS1,X1E X1E=0.3 f2(500)+0.3 f2(600)+ 0.4f2(700)536.26 f1(500)500 f1(600)536.26 f1(700)536.26,U11 ,当S1500 U10 ,当S1600,700 即在第一周时,当市场价格为500时,选择购买原材料。若市场价格为600或700时,则继续等待。 由上可知,在第1、2、3周时,当价格为500时,选择购买原材料,若价格为600或700,则继续等待。在第4周时,当价格为500或600时,选择购买原材料,若价格为700,则继续等待,在第5周,则无论时什么价格都购买。 依照这样的最优策略,价格的数学期望值为: 5000.3+536.260.3+ 536.260.4=525.382,二、动态规划软件求解简介,1 使用Lingo求解最短路,例6-9 求A到G的最短距离路线,各地间的距离如图6-3所示。,图6-3 例6-9的图,二、动态规划软件求解简介,2 使用Matlab求解最短路,【例6-10】用Matlab求解图6-7的最短路。,图6-7 上海至灾区的公路网络图,解: 计算机求解 在该题中首先用1,2,3,4,5,6,7,8,9,10来代表,。,三、动态规划应用案例分析(6.5),论文1:基于Matlab的0- 1 背包问题的动态规划方法求解 论文2:基于MAT LAB 的动态规划常用算法的实现 论文3:基于启发式动态规划方法的发电商最优竞价策略 论文4:基于自适应动态规划的系统边际电价预测,1 电厂内部机组负荷的经济分配 2 电力企业购网电量分配案例分析,四、动态规划文献阅读,作业:习题6 6,7,8,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号