第9章多阶段动态规划决策

第九章多阶段决策动态规划的基本概念和方程9.2确定性多阶段决策:定价问题9.3随机性多阶段决策:采购问题9.4多阶段决策与动态规划9.1最短路线问题AB1B2B3C1C2C3D1D2D3E150170110150100160250300200180300200300170280200280200300400多阶段决策：决策过程分为若干个互相联系的阶段，在每一个阶段都需要作出决策，从而使整个过程达到最好的效果。多阶段决策过程的分类：离散确定性，连续确定性；离散随机性，连续随机性.多阶段决策与动态规划9.1决策1状态状态决策2状态决策n状态……动态规划：运筹学的一个分支，它是解决多阶段决策过程最优化的一种数学方法。1951年美国数学家贝尔曼（R.Bellman）等将多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以解决产生。基本思想：从最后一段开始，用由后向前逐步递推的方法，从终点逐段向始点方向寻找最优路经的方法.多阶段决策与动态规划9.1登山线路问题AB1B2B3C1C2C3D1D2D3E150170110150100160250300200180300200300170280200280200300400阶段：根据问题的时间和空间的自然特征进行划分，用k表示。状态：每个阶段开始所处的自然状况或客观条件，用Sk表示。决策：当过程处于某一阶段的某个状态时，可以作出的决定，用dk(Sk)表示。指标函数：当过程处于某一阶段某个状态的即时所得，用Rk(Sk,dk)表示。动态规划的基本概念和方程9.2最短路线问题—基本概念AB1B2B3C1C2C3D1D2D3E150170110150100160250300200180300200300170280200280200300400k=1k=2k=3k=4最优指标函数递推方程：fk(Sk)=min/max{Rk(Sk,dk)+fk+1(Sk+1)}k=n,n-1,……,1fn+1(Sn+1)=0动态规划的基本概念和方程9.2贝尔曼（R.Bellman）的最优性原理：“任何前一阶段决策结果所得的状态，应能使其同其余阶段的决策共同构成最优决策。”AB1B2B3C1C2C3D1D2E5211412610311104125296138519521419207128最短路线问题的求解：“标号法”最短路线:A→B2→C1→D1→E最短路线问题的性质：从最短路上的任一点到终点的部分道路也一定是从该点到终点的最短子路。AB1B2B3C1C2C3D1D2D3E150170110150100160250300200180300200300170280200280200300400确定性多阶段决策9.312131415161620201825241810121415151414165元6元7元8元k=1k=2k=3k=4k=5“新产品定价问题－Page214”12131415161620201825241810121415151414165元6元7元8元k=1k=2k=3k=4k=59276612545最优策略：如果第1年定价8元，第2年定价8元，第3年定价7元，第4年定价6元，第5年定价5元。总利润92万元。最优指标函数方程：fk(Sk)=min{Rk(Sk,dk)+fk+1(Sk+1)}k=n,n-1,……,1fn+1(Sn+1)=0随机性多阶段决策9.4最优指标期望值随机性多阶段决策9.4单价:X（万元/千克）303440概率0.220.400.38某厂为安排生产需要在月初五日内采购一批染料，根据市场调查，每天染料价格波动及概率如下表。试求每月在哪一天采购为宜？“原材料采购价格问题Page216”11110,11.kkkkkkkkxfxDxfxD采购期望价格(最优指标)函数方程：fk(xk)=min{Dk·xk+Dk+1·fk+1(xk+1)}k=n,n-1,……,1fn+1(xn+1)=0kD单价（万元/千克）303440概率0.220.400.38某厂为安排生产需要在月初五日内采购一批染料，根据市场调查，每天染料价格波动及概率如下表。试求每月在哪一天采购为宜？采购日期期望价格（万元/千克）535.4433.6532132.8532.2231.73最优策略：如果第1、2、3天价格为30则购进，否则等待；第4天价格为30或34则购进，否则第5天购买。某厂为安排生产需要在近五周内采购一批原材料，估计未来五周内原材料价格波动及概率如下表。试求在哪一周以什么价格采购可使采购价格的期望值最小，并求出期望值。单价（元/千克）500600700概率0.30.30.4随机性多阶段决策练习最优策略：如果第1、2、3周价格为500元/千克则购进，否则等待；第4周价格为500或600元/千克则购进，否则第5天购买。