随机动态规划.pptVIP

* 动态规划 Dynamic Programming（DP） 动态规划在经济管理中的应用 随机动态规划简介 随机动态规划不同于确定型动态规划之处在于其下一阶段的状态不是由当前阶段的状态以及决策完全确定。确切地说，下一阶段的状态是什么，服从一个概率分布。不过，这个概率分布仍由当前阶段的状态以及决策完全确定。由此，我们得到随机动态规划的基本结构。下图给出了这种结构的形象描绘： * 动态规划 Dynamic Programming（DP） 随机动态规划的基本结构图 sk uk s1k+1 sNk+1 s2k+1 opt k+1阶段 p1 fk（sk） k阶段 p2 pN … v1 v2 vN … … 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 =1 N fn（sn）= opt { ? pivi } un ? Dn（sn） i =1 N k = n-1，…，2，1 * 动态规划 Dynamic Programming（DP） 某公司相信对一个开发项目进行投资会取得成功。若投资成功的话，公司就可以获得与投资数额相同的利润，若投资失败的话，公司非但得不到利润，就连投资也完全不能收回。公司对有关资料详细分析后认为，每次投资成功的概率为 2/3，失败的概率为 1/3。目前公司对此项目进行投资的总资金有 3 百万元，为了有效控制投资风险，公司计划分三次投入资金（如果有资金的话）。公司需要作出的决策是每次应投入多少资金（以百万元为单位），才能使三次投资结束后公司最终获得 2 百万元利润（即最终拥有 5 百万元总资金）的概率最大。 下面我们通过一个例子来具体阐述如何求解动态规划问题。请看案例—— * 动态规划 Dynamic Programming（DP） 1、阶段 k ：第 k 次投资，k = 1，2，3 2、状态变量 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。 * 动态规划 Dynamic Programming（DP） 6、定义fk（ sk ）：第 k 次投资时拥有可用于投资的资金数量 sk ，并一直投资到第 3 次投资结束后公司获得 2 百万元利润的最大概率。我们应该注意到这样一个事实——即使前两次投资失败了，公司仍然有机会最终赢得 2 百万元的利润。 7、随机动态规划的基本结构图： sk uk sk- uk sk+ uk k+1阶段 fk（sk） k阶段 fk+1（ sk + uk ） 决策 uk =0，1，…，sk （ ? ） max fk+1（ sk - uk ） 成功，2/3 失败，1/3 * 动态规划 Dynamic Programming（DP） 8、随机动态方程： fk（sk）= max {（2/3） fk+1（ sk + uk ）+（1/3） fk+1（ sk - uk ）} uk =0，1，…，sk k = 3，2，1 f4（s4）= △ 0 s4 ? 5 1 s4 ≥ 5 * 动态规划 Dynamic Programming（DP） 9、逆序递推求解随机动态方程。 k = 3 s3 = 0，1，2，3，4，5，…，12 s3 0 1 2 3 4 ≥5 f3（s3） 0 0 0 2/3 2/3 1 u*3 … … … 2，3 1，2，3，4 0，≤ s3 - 5 fk（sk）= max {（2/3） fk+1（ sk + uk ）+（1/3） fk+1（ sk - uk ）} uk =0，1，…，sk k = 3，2，1 f4（s4）= △ 0 s4 ? 5 1 s4 ≥ 5 * 动态规划 Dynamic Programming（DP） k = 2 s2 = 0，1，2，3，4，5，6