随机型动态规划及软件介绍.ppt

《随机型动态规划及软件介绍.ppt》由会员分享，可在线阅读，更多相关《随机型动态规划及软件介绍.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第6章章 动态规划动态规划动态规划的基本理论动态规划的基本理论 （2学时）学时）确定型动态规划确定型动态规划 （2学时）学时）随机型动态规划随机型动态规划 （1学时）学时）动态规划的软件求解简介动态规划的软件求解简介（1学时）学时）1第八章 动态规划一、离散随机性动态规划一、离散随机性动态规划 随机型的动态规划是指状态的转移律是不确定的，即对给定的状态和决策，下一阶段的到达状态是具有确定概率分布的随机变量，这个概率分布由本阶段的状态和决策完全确定。随机型动态规划的基本结构如下图：sk状态 xk决策概率k阶段的收益p1p2pN.k+1阶段的状态sk+1c1c2cN 1 2N第15讲 随机型动态

2、规划及软件介绍2第八章 动态规划 图图中中N N表表示示第第k+1k+1阶阶段段可可能能的的状状态态数数，p p1 1、p p2 2、ppN N为为给给定定状状态态s sk k和和决决策策x xk k的的前前提提下下，可可能能达达到到下下一一个个状状态态的的概概率率。c ci i为为从从k k阶阶段段状状态态s sk k转转移移到到k+1 k+1 阶阶段段状状态态为为i i时时的的指指标函数值。标函数值。在随机性的动态规划问题中，由于下一阶段到达的状在随机性的动态规划问题中，由于下一阶段到达的状态和阶段的效益值不确定，只能根据各阶段的期望效益值态和阶段的效益值不确定，只能根据各阶段的期望效益值

3、进行优化。进行优化。3第八章 动态规划 例例1 1 某公司承担一种新产品研制任务，合同要求三个月内交出一件合格的样品，否则将索赔2000元。根据有经验的技术人员估计，试制品合格的概率为0.4，每次试制一批的装配费为200元，每件产品的制造成本为100元。每次试制的周期为1个月。问该如何安排试制，每次生产多少件，才能使得期望费用最小？（类例教材（类例教材1：例：例6-7）4第八章 动态规划 解：把三次试制当作三个阶段（解：把三次试制当作三个阶段（k=1,2,3k=1,2,3）,决策变量决策变量x xk k表示第表示第k k次生产的产品的件数；状态变量次生产的产品的件数；状态变量s sk k表示第

4、表示第k k次试制前次试制前是否已经生产出合格品，如果有合格品，则是否已经生产出合格品，如果有合格品，则s sk k=0=0；如果没有；如果没有合格品，记合格品，记s sk k=1=1。最优函数。最优函数f fk k(s(sk k)表示从状态表示从状态s sk k、决策、决策x xk k出发出发的第的第k k阶段以后的最小期望费用。故有阶段以后的最小期望费用。故有f fk k(0)(0)0 0。生产出一件合格品的概率为生产出一件合格品的概率为0.40.4，所以生产，所以生产x xk k件产品都不件产品都不合格的概率为合格的概率为 ，至少有一件合格品的概率为，至少有一件合格品的概率为1-1-，故

5、，故有状态转移方程为有状态转移方程为 5第八章 动态规划 用用C(xC(xk k)表示第表示第k k阶段的费用，第阶段的费用，第k k阶段的费用包阶段的费用包括制造成本和装配费用，故有括制造成本和装配费用，故有 根据状态转移方程以及根据状态转移方程以及C(xC(xk k)，可得到，可得到 6第八章 动态规划 如果如果3 3个月后没有试制出一件合格品，则要承担个月后没有试制出一件合格品，则要承担20002000元的罚金，因此有元的罚金，因此有f f4 4(1)=20(1)=20。当当k=3k=3时，计算如下表：时，计算如下表：x3 s3 C(x3)+20f3(s3)x3*0 1 2 3 4 5

6、6 0 0 0 0 1 20 1511.2 9.32 8.59 8.56 8.93 8.56 57第八章 动态规划 当当k=2k=2时，计算如下表：时，计算如下表：x2 s2 C(x2)+8.56f2(s2)x2*0 1 2 3 4 0 0 0 0 18.568.147.086.857.11 6.85 38第八章 动态规划 当当k=1k=1时，有时，有 x1 s1 C(x1)+6.85f1(s1)x1*0 1 2 3 0 0 0 0 16.85 7.11 6.46 6.48 6.46 29第八章 动态规划 上上面面三三个个表表中中并并没没有有列列出出x xk k取取更更大大数数值值的的情情况况

7、，因因为为可可以以证证明明以以后后的的C(xC(xk k)+)+f fk+1k+1(1)(1)的的值值是是对对x xk k单单调调增加的。增加的。因此得到的最优策略是，在第因此得到的最优策略是，在第1 1个阶段试制个阶段试制2 2件产件产品；如果都不合格，在第品；如果都不合格，在第2 2阶段试制阶段试制3 3件产品；如果仍都件产品；如果仍都不合格，则在第不合格，则在第3 3个阶段试制个阶段试制5 5件产品。该策略得到的最件产品。该策略得到的最小的期望费用小的期望费用6.466.46。10第八章 动态规划例例2 不确定性采购问题（类例教材不确定性采购问题（类例教材1：例：例6-8）某厂生产上需要

8、在近五周内必须采购一批原料,而估计在未来五周内原材料的价格是波动的，浮动价格和概率已知。如何采购使其采购价格的数数学学期期望最小望最小，并求出期望值。单价概率5000.36000.37000.411第八章 动态规划动态规划的数学模型动态规划的数学模型该问题分成五个该问题分成五个阶段阶段，k表示周，表示周，k1，2，3，4，5设设Sk表示为第表示为第k周的实际价格。周的实际价格。决决策策变变量量Uk,Uk1表表示示为为第第k周周决决定定采采购购，Uk0表表示示为为第第k周决定等待。周决定等待。XkE表表示示为为第第k周周决决定定等等待待,而而在在以以后后采采取取最最优优决决策策时时采采购购价格的

9、期望值。价格的期望值。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,70012第八章 动态规划f5(S5)S5 S5500,600,700f5(500)500 f5(600)600 f5(700)700即在第五周，不论原材料的市场价格如何，都必须购买。当当k=5k=5时时f4(S4)mi

10、nS4，X4EX4E=0.3 f5(500)+0.3 f5(600)+0.4f5(700)610f4(500)500 f4(600)600 f4(700)610当当k=4时时U U4 41 1，当，当S S4 4500500，600600U U4 40 0，当，当S S4 4700700即在第四周时，当市场价格为500或600时，选择购买原材料。若市场价格为700时，则继续等待。13第八章 动态规划当k=3时，f3(S3)minS3，X3EX3E=0.3 f4(500)+0.3 f4(600)+0.4f4(700)574f3(500)500 f3(600)574 f3(700)574U31，当

11、S3500U30，当S3600，700即在第三周时，当市场价格为500时，选择购买原材料。若市场价格为600或700时，则继续等待。14第八章 动态规划当当k=2时时，f2(S2)minS2，X2EX2E=0.3 f3(500)+0.3 f3(600)+0.4f3(700)551.8f3(500)500 f3(600)551.8 f3(700)551.8U21，当，当S2500U20，当，当S2600，700即在第二周时，当市场价格为500时，选择购买原材料。若市场价格为600或700时，则继续等待。当当k=1时，时，f1(S1)minS1，X1EX1E=0.3 f2(500)+0.3 f2(

12、600)+0.4f2(700)536.26f1(500)500 f1(600)536.26 f1(700)536.2615第八章 动态规划U11，当，当S1500U10，当，当S1600，700即在第一周时，当市场价格为500时，选择购买原材料。若市场价格为600或700时，则继续等待。由上可知，在第1、2、3周时，当价格为500时，选择购买原材料，若价格为600或700，则继续等待。在第4周时，当价格为500或600时，选择购买原材料，若价格为700，则继续等待，在第5周，则无论时什么价格都购买。依照这样的最优策略，价格的数学期望值为价格的数学期望值为：5000.3+536.260.3+53

13、6.260.4=525.38216第八章 动态规划二、动态规划软件求解简介二、动态规划软件求解简介 1 1 使用使用LingoLingo求解最短路求解最短路17第八章 动态规划例例6-9 6-9 求求A A到到G G的最短距离路线，各地间的距离如图的最短距离路线，各地间的距离如图6-36-3所示。所示。图图6-3 6-3 例例6-96-9的图的图18第八章 动态规划19第八章 动态规划20第八章 动态规划21第八章 动态规划二、动态规划软件求解简介二、动态规划软件求解简介 2 2 使用使用MatlabMatlab求解最短路求解最短路22第八章 动态规划【例【例6-106-10】用】用Matla

14、bMatlab求解图求解图6-76-7的最短路。的最短路。图图6-7 6-7 上海至灾区的公路网络图上海至灾区的公路网络图解解:计算机求解计算机求解 在该题中首先用在该题中首先用1,2,3,4,5,6,7,8,9,101,2,3,4,5,6,7,8,9,10来代表来代表。23第八章 动态规划24第八章 动态规划25第八章 动态规划三、动态规划应用案例分析三、动态规划应用案例分析(6.5)(6.5)论文论文1:1:基于基于MatlabMatlab的的0-1 0-1 背包问题的动态规划方法求解背包问题的动态规划方法求解论文论文2:2:基于基于MAT LAB MAT LAB 的动态规划常用算法的实现的动态规划常用算法的实现论文论文3:3:基于启发式动态规划方法的发电商最优竞价策略基于启发式动态规划方法的发电商最优竞价策略论文论文4:4:基于自适应动态规划的系统边际电价预测基于自适应动态规划的系统边际电价预测1 1 电厂内部机组负荷的经济分配电厂内部机组负荷的经济分配2 2 电力企业购网电量分配案例分析电力企业购网电量分配案例分析四、动态规划文献阅读四、动态规划文献阅读作业作业:习题习题6 6,7,86 6,7,826第八章 动态规划