随机型动态规划及软件介绍PPT课件

1、一、离散随机性动态规划一、离散随机性动态规划 随机型的动态规划是指状态的转移律是不确定的，即对给定的状态和决策，下一阶段的到达状态是具有确定概率分布的随机变量，这个概率分布由本阶段的状态和决策完全确定。随机型动态规划的基本结构如下图： sk状态 xk决策概率k阶段的收益p1p2pN.k+1阶段的状态sk+1c1c2cN 1 2N第第1515讲讲 随机型动态规划及软件介随机型动态规划及软件介绍绍第1页/共26页 图中图中N N表示第表示第k+1k+1阶段可能的状态数，阶段可能的状态数，p p1 1、p p2 2、p pN N为给定状态为给定状态s sk k和决策和决策x xk k的前提下，可能达

2、到下一个状态的前提下，可能达到下一个状态的概率。的概率。c ci i为从为从k k阶段状态阶段状态s sk k转移到转移到k+1 k+1 阶段状态为阶段状态为i i时时的指标函数值。的指标函数值。 在随机性的动态规划问题中，由于下一阶段到达在随机性的动态规划问题中，由于下一阶段到达的状态和阶段的效益值不确定，只能根据各阶段的期望的状态和阶段的效益值不确定，只能根据各阶段的期望效益值进行优化。效益值进行优化。第2页/共26页 例例1 1 某公司承担一种新产品研制任务，合同要求三个月内交出一件合格的样品，否则将索赔2000元。根据有经验的技术人员估计，试制品合格的概率为0.4，每次试制一批的装配费

3、为200元，每件产品的制造成本为100元。每次试制的周期为1个月。问该如何安排试制，每次生产多少件，才能使得期望费用最小？（类例教材（类例教材1：例：例6-7） 第3页/共26页 解：把三次试制当作三个阶段（解：把三次试制当作三个阶段（k=1,2,3k=1,2,3）, ,决策决策变量变量x xk k表示第表示第k k次生产的产品的件数；状态变量次生产的产品的件数；状态变量s sk k表示第表示第k k次试制前是否已经生产出合格品，如果有合格品，则次试制前是否已经生产出合格品，如果有合格品，则s sk k=0=0；如果没有合格品，记如果没有合格品，记s sk k=1=1。最优函数。最优函数f f

4、k 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- ，故有状态转移方程为，故有状态转移方程为 kx6 . 0kkxkxkspsp6 . 01)0(6 . 0) 1(11kx6.0第4页/共26页 用用C(xC(xk k) )表示第表示第k k阶段的费用，第阶段

5、的费用，第k k阶段的费用包阶段的费用包括制造成本和装配费用，故有括制造成本和装配费用，故有 根据状态转移方程以及根据状态转移方程以及C(xC(xk k) )，可得到，可得到 0002)(kkkkxxxxC)1 (6 . 0)0()6 . 01 ()(min) 1 (11kxkxkxkffxcfkkk)1 (6 . 0)(min1kxkxfxckk第5页/共26页 如果如果3 3个月后没有试制出一件合格品，则要承担个月后没有试制出一件合格品，则要承担20002000元的罚金，因此有元的罚金，因此有f f4 4(1)=20(1)=20。 当当k=3k=3时，计算如下表：时，计算如下表： x3 s

6、3 C(x3)+20f3(s3) x3* 0 1 2 3 4 5 6 0 0 0 0 1 20 1511.2 9.32 8.59 8.56 8.93 8.56 5 0.63x第6页/共26页 当当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 3 0.62x第7页/共26页 当当k=1k=1时，有时，有 x1 s1 C(x1)+6.85f1(s1) x1* 0 1 2 3 0 0 0 0 16.857.116.466.48 6.46 2 0.61x第8页

7、/共26页 上面三个表中并没有列出上面三个表中并没有列出x xk k取更大数值的情况，取更大数值的情况，因为可以证明以后的因为可以证明以后的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。 0.

8、6kx第9页/共26页例例2 不确定性采购问题（类例教材不确定性采购问题（类例教材1：例：例6-8）某厂生产上需要在近五周内必须采购一批原料,而估计在未来五周内原材料的价格是波动的，浮动价格和概率已知。如何采购使其采购价格的数学期望最小数学期望最小，并求出期望值。单价概率5000.36000.37000.4第10页/共26页动态规划的数学模型动态规划的数学模型 该问题分成五个该问题分成五个阶段阶段，k表示周，表示周，k1，2，3，4，5 设设Sk表示为第表示为第k周的实际价格。周的实际价格。 决策变量决策变量Uk, ,Uk1表示为第表示为第k周决定采购，周决定采购，Uk0表表示为第示为第k周决

9、定等待。周决定等待。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第11页/共26页f5(S5)S5 S5500,600,700f5(500)500 f5(600)600 f5(

10、700)700即在第五周，不论原材料的市场价格如何，都必须购买。当k=5时f4(S4)minS4，X4EX4E=0.3 f5(500)+0.3 f5(600)+ 0.4f5(700)610f4(500)500 f4(600)600 f4(700)610当k=4时U41 ，当S4500，600U40 ，当S4700即在第四周时，当市场价格为500或600时，选择购买原材料。若市场价格为700时，则继续等待。第12页/共26页当k=3时，f3(S3)minS3，X3EX3E=0.3 f4(500)+0.3 f4(600)+ 0.4f4(700)574f3(500)500 f3(600)574 f3

11、(700)574U31 ，当S3500U30 ，当S3600，700即在第三周时，当市场价格为500时，选择购买原材料。若市场价格为600或700时，则继续等待。 第13页/共26页当当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

12、.3 f2(500)+0.3 f2(600)+ 0.4f2(700)536.26f1(500)500 f1(600)536.26 f1(700)536.26第14页/共26页U11 ，当，当S1500U10 ，当，当S1600，700即在第一周时，当市场价格为500时，选择购买原材料。若市场价格为600或700时，则继续等待。由上可知，在第1、2、3周时，当价格为500时，选择购买原材料，若价格为600或700，则继续等待。在第4周时，当价格为500或600时，选择购买原材料，若价格为700，则继续等待，在第5周，则无论时什么价格都购买。依照这样的最优策略，价格的数学期望值为价格的数学期望值为

13、：5 0 0 0 . 3 + 5 3 6 . 2 6 0 . 3 + 536.260.4=525.382第15页/共26页二、动态规划软件求解简介 1 使用Lingo求解最短路第16页/共26页例6-9 求A到G的最短距离路线，各地间的距离如图6-3所示。 图6-3 例6-9的图第17页/共26页第18页/共26页第19页/共26页第20页/共26页二、动态规划软件求解简介 2 使用Matlab求解最短路第21页/共26页【例6-10】用Matlab求解图6-7的最短路。A2B3B1B1C2C3C1D2DE24374632462363333434图6-7 上海至灾区的公路网络图解: 计算机求解 在该题中首先用1,2,3,4,5,6,7,8,9,10来代表12312312 ,A B B B C C C D D E。第22页/共26页第23页/共26页第24页/共26页