第15讲随机型动态规划及软件介绍

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

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

4、有合格品，则是否已经生产出合格品，如果有合格品，则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- ，故，故有状态转移方程为有状态转移方程为 kx6

5、 . 0kkxkxkspsp6 . 01)0(6 . 0) 1(11kx6.0 用用C(xC(xk k) )表示第表示第k k阶段的费用，第阶段的费用，第k k阶段的费用包阶段的费用包括制造成本和装配费用，故有括制造成本和装配费用，故有 根据状态转移方程以及根据状态转移方程以及C(xC(xk k) )，可得到，可得到 0002)(kkkkxxxxC)1 (6 . 0)0()6 . 01 ()(min) 1 (11kxkxkxkffxcfkkk)1 (6 . 0)(min1kxkxfxckk 如果如果3 3个月后没有试制出一件合格品，则要承担个月后没有试制出一件合格品，则要承担20002000元

6、的罚金，因此有元的罚金，因此有f f4 4(1)=20(1)=20。 当当k=3k=3时，计算如下表：时，计算如下表： x3 s3 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 当当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 当当k=1k=1时，有时，有 x1 s1 C(x1)+6.85f1(s1) x1* 0

7、 1 2 3 0 0 0 0 16.85 7.11 6.46 6.48 6.46 2 0.61x 上面三个表中并没有列出上面三个表中并没有列出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件产品

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

9、周决定采购，周决定采购，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,700f5(S5)S5 S5500

10、,600,700f5(500)500 f5(600)600 f5(700)700即在第五周，不论原材料的市场价格如何，都必须购买。当当k=5k=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时时U U4 41 1 ，当，当S S4 4500500，600600U U4 40 0 ，当，当S S4 4700700即在第四周时，当市场价格为500或600时，选择购买原材料。若市场价格为700时，则继续等待。当k=3时，f3(S3)minS3，X3EX3

11、E=0.3 f4(500)+0.3 f4(600)+ 0.4f4(700)574f3(500)500 f3(600)574 f3(700)574U31 ，当S3500U30 ，当S3600，700即在第三周时，当市场价格为500时，选择购买原材料。若市场价格为600或700时，则继续等待。 当当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时，选择购

12、买原材料。若市场价格为600或700时，则继续等待。当当k=1时，时，f1(S1)minS1，X1EX1E=0.3 f2(500)+0.3 f2(600)+ 0.4f2(700)536.26f1(500)500 f1(600)536.26 f1(700)536.26U11 ，当，当S1500U10 ，当，当S1600，700即在第一周时，当市场价格为500时，选择购买原材料。若市场价格为600或700时，则继续等待。由上可知，在第1、2、3周时，当价格为500时，选择购买原材料，若价格为600或700，则继续等待。在第4周时，当价格为500或600时，选择购买原材料，若价格为700，则继续等待

13、，在第5周，则无论时什么价格都购买。依照这样的最优策略，价格的数学期望值为价格的数学期望值为：5000.3+536.260.3+ 536.260.4=525.382二、动态规划软件求解简介二、动态规划软件求解简介 1 1 使用使用LingoLingo求解最短路求解最短路例例6-9 6-9 求求A A到到G G的最短距离路线，各地间的距离如图的最短距离路线，各地间的距离如图6-36-3所示。所示。 图图6-3 6-3 例例6-96-9的图的图二、动态规划软件求解简介二、动态规划软件求解简介 2 2 使用使用MatlabMatlab求解最短路求解最短路【例【例6-106-10】用】用MatlabM

14、atlab求解图求解图6-76-7的最短路。的最短路。A2B3B1B1C2C3C1D2DE24374632462363333434图图6-7 6-7 上海至灾区的公路网络图上海至灾区的公路网络图解解: 计算机求解计算机求解 在该题中首先用在该题中首先用1,2,3,4,5,6,7,8,9,101,2,3,4,5,6,7,8,9,10来代表来代表12312312 ,A B B B C C C D D E。三、动态规划应用案例分析三、动态规划应用案例分析(6.5)(6.5)论文论文1:1:基于基于MatlabMatlab的的0- 1 0- 1 背包问题的动态规划方法求解背包问题的动态规划方法求解论文论文2:2:基于基于MAT LAB MAT LAB 的动态