随机动态规划

1动态规划DynamicProgramming（DP）动态规划在经济管理中的应用随机动态规划简介随机动态规划不同于确定型动态规划之处在于其下一阶段的状态不是由当前阶段的状态以及决策完全确定。确切地说，下一阶段的状态是什么，服从一个概率分布。不过，这个概率分布仍由当前阶段的状态以及决策完全确定。由此，我们得到随机动态规划的基本结构。下图给出了这种结构的形象描绘：2动态规划DynamicProgramming（DP）随机动态规划的基本结构图skuks1k+1sNk+1s2k+1optk+1阶段p1fk（sk）k阶段p2pN…v1v2vN……fk+1（s1k+1）fk+1（s2k+1）fk+1（sNk+1）决策ukDk（sk）随机动态规划的基本方程：fk（sk）=opt{pi（vi+fk+1（sik+1））}ukDk（sk）i=1Nfn（sn）=opt{pivi}unDn（sn）i=1Nk=n-1，…，2，13动态规划DynamicProgramming（DP）某公司相信对一个开发项目进行投资会取得成功。若投资成功的话，公司就可以获得与投资数额相同的利润，若投资失败的话，公司非但得不到利润，就连投资也完全不能收回。公司对有关资料详细分析后认为，每次投资成功的概率为2/3，失败的概率为1/3。目前公司对此项目进行投资的总资金有3百万元，为了有效控制投资风险，公司计划分三次投入资金（如果有资金的话）。公司需要作出的决策是每次应投入多少资金（以百万元为单位），才能使三次投资结束后公司最终获得2百万元利润（即最终拥有5百万元总资金）的概率最大。下面我们通过一个例子来具体阐述如何求解动态规划问题。请看案例——4动态规划DynamicProgramming（DP）1、阶段k：第k次投资，k=1，2，32、状态变量sk：第k次投资时拥有可用于投资的资金数量。3、决策变量uk：第k次投资的资金数量。决策集合Dk（sk）={uk|uk=0，1，2，…，sk}4、状态转移方程：sk+1=sk+uk第k次投资确实成功。sk-uk第k次投资确实失败。5、定义阶段指标值（函数）：成功的概率为2/3，失败的概率为1/3。5动态规划DynamicProgramming（DP）6、定义fk（sk）：第k次投资时拥有可用于投资的资金数量sk，并一直投资到第3次投资结束后公司获得2百万元利润的最大概率。我们应该注意到这样一个事实——即使前两次投资失败了，公司仍然有机会最终赢得2百万元的利润。7、随机动态规划的基本结构图：skuksk-uksk+ukk+1阶段fk（sk）k阶段fk+1（sk+uk）决策uk=0，1，…，sk（）maxfk+1（sk-uk）6动态规划DynamicProgramming（DP）8、随机动态方程：fk（sk）=max{（2/3）fk+1（sk+uk）+（1/3）fk+1（sk-uk）}uk=0，1，…，skk=3，2，1f4（s4）=△0s451s4≥57动态规划DynamicProgramming（DP）9、逆序递推求解随机动态方程。k=3s3=0，1，2，3，4，5，…，12s301234≥5f3（s3）0002/32/31u*3………2，31，2，3，40，≤s3-5fk（sk）=max{（2/3）fk+1（sk+uk）+（1/3）fk+1（sk-uk）}uk=0，1，…，skk=3，2，1f4（s4）=△0s451s4≥58动态规划DynamicProgramming（DP）k=2s2=0，1，2，3，4，5，6u2s2（2/3）f3（s2+u2）+（1/3）f3（s2-u2）f2（s2）u*201234000…1000…204/94/94/91，232/34/92/32/32/30，2，342/38/92/32/32/38/91≥5110，≤s3-5s301234≥5f3（s3）0002/32/31u*3………2，31，2，3，40，≤s3-59动态规划DynamicProgramming（DP）k=1s1=3u2s2（2/3）f2（s1+u1）+（1/3）f2（s1–u1）f1（s1）u*1012332/320/272/32/320/271u2s2（2/3）f3（s2+u2）+（1/3）f3（s2-u2）f2（s2）u*201234000…1000…204/94/94/91，232/34/92/32/32/30，2，342/38/92/32/32/38/91≥5110，≤s3-510动态规划DynamicProgramming（DP）u2s2（2/3）f2（s1+u1）+（1/3）f2（s1–u1）f1（s1）u*1012332/320/272/32/320/271于是，我们有最优策略：s1=3，u*1=1成功s2=4，u*2=1失败s2=2，u*2=1u*2=2成功s3=5，u*3=0失败s3=3，u*3=2or3成功s3=3or4，u*3=2，3or1，…，4失败s3=1or0，投资失败。