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

第6章动态规划动态规划的基本理论（2学时）确定型动态规划（2学时）随机型动态规划（1学时）动态规划的软件求解简介（1学时）一、离散随机性动态规划随机型的动态规划是指状态的转移律是不确定的，即对给定的状态和决策，下一阶段的到达状态是具有确定概率分布的随机变量，这个概率分布由本阶段的状态和决策完全确定。随机型动态规划的基本结构如下图：sk状态xk决策概率k阶段的收益p1p2pN….k+1阶段的状态sk+1c1c2cN12N第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-，故有状态转移方程为kx6.0kkxkxkspsp6.01)0(6.0)1(11kx6.0用C(xk)表示第k阶段的费用，第k阶段的费用包括制造成本和装配费用，故有根据状态转移方程以及C(xk)，可得到0002)(kkkkxxxxC)}1(6.0)0()6.01()({min)1(11kxkxkxkffxcfkkk)}1(6.0)({min1kxkxfxckk如果3个月后没有试制出一件合格品，则要承担2000元的罚金，因此有f4(1)=20。当k=3时，计算如下表：x3s3C(x3)+20×f3(s3)x3*012345600——————001201511.29.328.598.568.938.5650.63x当k=2时，计算如下表：x2s2C(x2)+8.56×f2(s2)x2*0123400————0018.568.147.086.857.116.8530.62x当k=1时，有x1s1C(x1)+6.85×f1(s1)x1*012300———0016.857.116.466.486.4620.61x上面三个表中并没有列出xk取更大数值的情况，因为可以证明以后的C(xk)+fk+1(1)的值是对xk单调增加的。因此得到的最优策略是，在第1个阶段试制2件产品；如果都不合格，在第2阶段试制3件产品；如果仍都不合格，则在第3个阶段试制5件产品。该策略得到的最小的期望费用6.46。0.6kx例2不确定性采购问题（类例教材1：例6-8）某厂生产上需要在近五周内必须采购一批原料,而估计在未来五周内原材料的价格是波动的，浮动价格和概率已知。如何采购使其采购价格的数学期望最小，并求出期望值。单价概率5000.36000.37000.4动态规划的数学模型–该问题分成五个阶段，k表示周，k＝1，2，3，4，5–设Sk表示为第k周的实际价格。–决策变量Uk,Uk＝1表示为第k周决定采购，Uk＝0表示为第k周决定等待。–XkE表示为第k周决定等待,而在以后采取最优决策时采购价格的期望值。–fk(Sk)表示第k周实际价格为Sk时，从第k周到第5周采取最优策略所得的最小期望值。递推关系式：fk(Sk)＝min{Sk，XkE}边界条件：f5(S5)＝S5其中：XkE=0.3fk+1(500)+0.3fk+1(600)+0.4fk+1(700)Sk∈{500,600,700}f5(S5)＝S5S5∈{500,600,700}f5(500)＝500f5(600)＝600f5(700)＝700即在第五周，不论原材料的市场价格如何，都必须购买。当k=5时f4(S4)＝min{S4，X4E}X4E=0.3f5(500)+0.3f5(600)+0.4f5(700)＝610f4(500)＝500f4(600)＝600f4(700)＝610当k=4时U4＝1，当S4＝500，600U4＝0，当S4＝700即在第四周时，当市场价格为500或600时，选择购买原材料。若市场价格为700时，则继续等待。当k=3时，f3(S3)＝min{S3，X3E}X3E=0.3f4(500)+0.3f4(600)+0.4f4(700)＝574f3(500)＝500f3(600)＝574f3(700)＝574U3＝1，当S3＝500U3＝0，当S3＝600，700即在第三周时，当市场价格为500时，选择购买原材料。若市场价格为600或700时，则继续等待。当k=2时，f2(S2)＝min{S2，X2E}X2E=0.3f3(500)+0.3f3(600)+0.4f3(700)＝551.8f3(500)＝500f3(600)＝551.8f3(700)＝551.8U2＝1，当S2＝500U2＝0，当S2＝600，700即在第二周时，当市场价格为500时，选择购买原材料。若市场价格为600或700时，则继续等待。当k=1时，f1(S1)＝min{S1，X1E}X1E=0.3f2(500)+0.3f2(600)+0.4f2(700)＝536.26f1(500)＝500f1(600)＝536.26f1(700)＝536.26U1＝1，当S1＝500U1＝0，当S1＝600，700即在第一周时，当市场价格为500时，选择购买原材料。若市场价格为600或700时，则继续等待。由上可知，在第1、2、3周时，当价格为500时，选择购买原材料，若价格为600或700，则继续等待。在第4周时，当价格为500或600时，选择购买原材料，若价格为700，则继续等待，在第5周，则无论时什么价格都购买。依照这样的最优策略，价格的数学期望值为：500×0.3+536.26×0.3+536.26×0.4=525.382二、动态规划软件求解简介1使用Lingo求解最短路例6-9求A到G的最短距离路线，各地间的距离如图6-3所示。图6-3例6-9的图二、动态规划软件求解简介2使用Matlab求解最短路【例6-10】用Matlab求解图6-7的最短路。A2B3B1B1C2C3C1D2DE24374632462363333434图6-7上海至灾区的公路网络图解:计算机求解在该题中首先用[1,2,3,4,5,6,7,8,9,10]来代表12312312[,,,,,,,,,]ABBBCCCDDE。三、动态规划应用案例分析(6.5)论文1:基于Matlab的0-1背包问题的动态规划方法求解论文2:基于MATLAB的动态规划常用算法的实现论文3:基于启发式动态规划方法的发电商最优竞价策略论文4:基于自适应动态规划的系统边际电价预测1电厂内部机组负荷的经济分配2电力企业购网电量分配案例分析四、动态规划文献阅读作业:习题66,7,8