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

1、第九章 多阶段决策 动态规划的根本概念和方程9.2确定性多阶段决策:定价问题9.3随机性多阶段决策:采购问题9.4 多阶段决策与动态规划9.1.最短道路问题AB1B2B3C1C2C3D1D2D3E150170110150100160250300200180300200300170280200280200300400.多阶段决策：决策过程分为假设干个相互联络的阶段，在每一个阶段都需求作出决策，从而使整个过程到达最好的效果。多阶段决策过程的分类： 离散确定性，延续确定性；离散随机性，延续随机性. 多阶段决策与动态规划9.1决策1形状形状决策2形状决策n形状.动态规划： 运筹学的一个分支，它是处理多

2、阶段决策过程最优化的一种数学方法。1951年美国数学家贝尔曼R.Bellman等将多阶段决策问题变换为一系列相互联络的单阶段问题，然后逐个加以处理产生。根本思想： 从最后一段开场，用由后向前逐渐递推的方法，从终点逐段向始点方向寻觅最优路经的方法. 多阶段决策与动态规划9.1.登山线路问题AB1B2B3C1C2C3D1D2D3E150170110150100160250300200180300200300170280200280200300400.阶段：根据问题的时间和空间的自然特征进展划分，用 k 表示。形状：每个阶段开场所处的自然情况或客观条件，用 Sk 表示。决策：当过程处于某一阶段的某个

3、形状时，可以作出的决议，用 dk (Sk )表示。目的函数：当过程处于某一阶段某个形状的即时所得，用 Rk (Sk ,dk )表示。 动态规划的根本概念和方程9.2.最短道路问题根本概念AB1B2B3C1C2C3D1D2D3E150170110150100160250300200180300200300170280200280200300400k=1k=2k=3k=4.最优目的函数递推方程：f k(Sk )= min/maxRk(Sk, dk )+ f k+1(Sk+1 ) k = n, n-1, , 1f n+1(Sn+1 )=0 动态规划的根本概念和方程9.2贝尔曼R.Bellman的最优

4、性原理：“任何前一阶段决策结果所得的形状，应能使其同其他阶段的决策共同构成最优决策。.AB1B2B3C1C2C3D1D2E5211412610311104125296138519521419207128最短道路问题的求解：“标号法最短道路:AB2 C1 D1 E.最短道路问题的性质：从最短路上的任一点到终点的部分道路也一定是从该点到终点的最短子路。AB1B2B3C1C2C3D1D2D3E150170110150100160250300200180300200300170280200280200300400. 确定性多阶段决策9.312131415161620201825241810121415

5、151414165 元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万元。.最优目的函数方程： f k(Sk )= minRk(Sk, dk )+ f k+1(Sk+1 ) k = n, n-1, , 1f n+1(Sn+1 )=0 随机性多阶段决策9.4最优目的期望值. 随机性多阶段决策9.4单价:X（万元/

6、千克）303440概率0.220.400.38某厂为安排消费需求在月初五日内采购一批染料，根据市场调查，每天染料价钱动摇及概率如下表。试求每月在哪一天采购为宜？“原资料采购价钱问题Page216采购期望价钱(最优目的)函数方程： f k(xk )= min Dkxk+ Dk+1f k+1(xk+1 ) k = n, n-1, , 1 f n+1(xn+1 )=0.单价（万元/千克）303440概率0.220.400.38某厂为安排消费需求在月初五日内采购一批染料，根据市场调查，每天染料价钱动摇及概率如下表。试求每月在哪一天采购为宜？采购日期期望价格（万元/千克）535.4433.6532132.8532.2231.73最优战略：假设第1、2、3天价钱为30那么购进，否那么等待；第4天价钱为30或34那么购进，否那么第5天购买。. 某厂为安排消费需求在近五周内采购一批原资料，估计未来五周内原资料价钱动摇及概率如下表。试求在哪一周以什么价钱采购可使采购价钱的期望值最小，并求出期望值。单价（