随机动态规划

ChinaThreeGorgesUniversity随机动态规划建模实例三峡大学于林ChinaThreeGorgesUniversity运用随机动态规划的分析方法，求解随机动态规划模型的最优解是一种比较常见的数学建模问题。例如，在实际应用中，经常会遇到某些多阶段决策过程中出现随机因素的情况，而动态规划的方法也可以处理这种随机性问题。本节从一个实际建模案例出发，说明这一方法的应用。这一问题被称之为价格波动时的采购策略。ChinaThreeGorgesUniversity一、问题的提出ChinaThreeGorgesUniversity某工厂生产上需要在近5周内必须采购进一批原料，根据各方面的信息和资料，这种原料在未来5周内价格会有波动，其浮动价格和相应的概率已经估计测出如下表所示：单价（元）500600700概率0.30.40.4请建立一种模型，决定采购策略，使得厂家采购价格的数学期望值最小，并计算出此最小期望价格。ChinaThreeGorgesUniversity二、分析与假设ChinaThreeGorgesUniversity此问题中价格是一个随机变量，是按照某种已知的概率分布规律取值的。可以将采购期限内的5周看做5个阶段（即需要每周做一次决策，自然也可以每天做一次决策而将之更加细致地分为35个阶段），则问题便成了在每个阶段进行决策是否购进原料，以期使原料的采购价格的期望值达到最小。ChinaThreeGorgesUniversity在实际应用中，经常会遇到某些多阶段决策过程中出现随机因素的情况。用动态规划的方法也可以处理这种随机性问题。不过此时状态转移不能完全确定，而是按照某种已知的概率分布取值，具有这种性质的多阶段决策过程就称之为随机性的决策过程，此时运用的动态规划也就相应的被称为随机动态规划。ChinaThreeGorgesUniversity为此，对问题做出如下基本假设：（1）所需要的原料在购买期限内必须一次性购买，而不是可以分批购买（这一假设极大简化了决策过程）；（2）原料价格波动的概率规律在每周内都是一样的（这一假设与我们的阶段划分方式相一致）；（3）将每周原材料的实际价格看做个阶段的状态，并用kx)5,4,3,2,1(k表示；ChinaThreeGorgesUniversity（4）每一阶段的采购策略视为决策变量，并用ku)5,4,3,2,1(k表示，其中，.,0,1周决定等待观望表示第周决定采购，表示第kkuk（5）用kEx表示第k周时决定等待观望，而在以后采取最优决策时采购价格的期望值；（6）用)(kkxf表示第k周实际价格为kx时，从第k周至第5周采取最优策略所得的采购价格的最小期望值。ChinaThreeGorgesUniversity三、模型的建立与求解ChinaThreeGorgesUniversity根据上述对问题的分析和基本假设，显然应有这样的事实：当第k)5(k周原材料实际价格为kx时，若kExkx，即若第k周等待观望不采购，而在以后采取最优采购策略的采购价格的期望值低于现行价格，那么显然应在第k周采取等待观望态度。由)(kkxf的定义可知，此时应有)(kkxf=kEx。若kExkx，说明若再第k周等待观望不采购，则以后采购的价格期望值将高于现行价格，这时显然最优策略就应该是采购了，而这样显然就有)(kkxf=kx。ChinaThreeGorgesUniversity因此，可以建立模型为：,)(},,{min)(555xxfxxxfkEkSxkkkk（1）其中}700,600,500{kS，.5,4,3,2,1k由kEx和)(kkxf的含义可又下面的状态转移方程：kEx)(11kkxf)700(4.0)600(3.0)500(3.0111kkkfff（2）最优决策变量为：,)(,0,)(,1kEkkkkkkxxfxxfu（3）ChinaThreeGorgesUniversity从最后一周（第五周）开始逐步向前逆推对模型求解，过程如下。1.当5k时，因为555)(xxf，55Sx，故有500)500(5f，600)600(5f，.700)700(5f由（3）式可知此时有：15u，即在第5周时，应采取购买决策。显然，若在第5周时所需要的原料尚未买入，则无论市场价格如何，都必须采购不能再等待了，而且此时的采购价格期望值就是现行的实际价格。ChinaThreeGorgesUniversity2.当4k时，即此时意味着前3周都采取了等待观望的策略。首先计算一下若第4周仍然采取等待观望而在以后采取最优采购策略的采购价格的期望值。由（2）式可得)700(4.0)600(3.0)500(3.05554fffxE.6107004.06003.05003.0于是，由（1）式可得},{min)(444444ESxxxxf}610,{min444xSx,700,610,600,600,500,500444xxx若若若这样，由（3）可得第4周的最优策略为：.700,0600500,1444xxu若，或若ChinaThreeGorgesUniversity3.当3k时，仍然要首先计算Ex3得值，还是由公式（2）得到)700(4.0)600(3.0)500(3.04443fffxE.5746104.06003.05003.0由此可得出)(33xf的值为：},{min)(333333ESxxxxf}574,{min333xSx.700600,574,500,50033或若若xx由)(33xf的值和（3）式便可确定第3周的策略为：.700600,0500,1333或若，若xxuChinaThreeGorgesUniversity4.当2k时，仍然由公式（2）计算得到)700(4.0)600(3.0)500(3.03332fffxE.8.5515744.05743.05003.0将此代入（1）可得出)(22xf的值为：},{min)(222222ESxxxxf}8.551,{min222xSx.700600,8.551,500,50022或若若xx由)(22xf的值和（3）式便可确定第2周的策略为：.700600,0500,1222或若，若xxuChinaThreeGorgesUniversity5.当1k时，由公式（2）计算得到)700(4.0)600(3.0)500(3.02221fffxE.26.5368.5514.08.5513.05003.0将此代入（1）可得出)(11xf的值为：},{min)(111111ESxxxxf}26.536,{min111xSx.700600,26.536,500,50011或若若xx由)(11xf的值和（3）式便可确定第1周的策略为：.700600,0500,1111或若，若xxuChinaThreeGorgesUniversity四、结论与分析ChinaThreeGorgesUniversity由以上逆推计算得结果可知，最优的采购策略序列为},,,,{54321uuuuu。根据1u，2u，3u的表达式可知，在第1、2、3周时，若价格为500时，就应采购；而在价格为600或者700时则应采取等待观望的态度。由4u的表达式得，在第4周，若价格为500或者600时就应该采购，而在价格为700时则等待观望。若在前4周都采取了等待观望策略，则在第5周，无论什么价格都必须采购（15u）。ChinaThreeGorgesUniversity如果采取上述策略，采购价格的数学期望是多少呢？为此，我们仍然需要从第5周开始考虑。ChinaThreeGorgesUniversity若采购是在第5周进行的，那说明前4周均是采取的等待策略。根据最优策略可知，第1、2、3周原材料的价格不是500，且第4周的价格是700。根据乘法公式，这一事件发生的概率为：4.07.07.07.0此时购买价格的期望值（条件期望值）为：7004.06003.05003.0。若采购是在第4周进行的，那说明前3周均是采取的等待策略。根据最优策略可知，第1、2、3周原材料的价格不是500，这一事件发生的概率为：7.07.07.0此时购买价格的期望值（条件期望值）为：6003.05003.0。ChinaThreeGorgesUniversity若采购是在第3周进行的，那说明前2周均是采取的等待策略。根据最优策略可知，第1、2周原材料的价格不是500，这一情况发生的概率为：7.07.0据最优策略，第3周购买价格为500，所以此时的购买价格的期望值（条件期望值）为：5003.0。若采购是在第2周进行的，那说明第1周是采取的等待策略。根据最优策略可知，第1周原材料的价格不是500，这一情况发生的概率为7.0。据最优策略，第2周购买价格为500，所以此时的购买价格的期望值（条件期望值）为：5003.0。若采购是在第1周进行的，则说明第1周的价格为500，此情况发生的概率为3.0。据最优策略，第1周购买价格为500，所以此时的购买价格的期望值（条件期望值）为：5003.0。ChinaThreeGorgesUniversity根据上述分析，可知采取最优策略的购买价格的期望值应为：)6003.05003.0(7.0)7004.06003.05003.0(4.07.033E5003.05003.07.05003.07.0252682.525由此可见，采取有模型所确定的最优采购策略，采购价格的期望值仅比可能出现的最低价格500高出5%，因此效果明显。ChinaThreeGorgesUniversity