最优化技术基础PPT学习教案

1、会计学1 最优化技术基础最优化技术基础 第1页/共23页 第2页/共23页 通常多阶段决策过程的发展是通过状态的一系列变换来实通常多阶段决策过程的发展是通过状态的一系列变换来实 现的。一般情况下，系统在某个阶段的状态转移除与本阶段现的。一般情况下，系统在某个阶段的状态转移除与本阶段 的状态和决策有关外，还可能与系统过去经历的状态和决策的状态和决策有关外，还可能与系统过去经历的状态和决策 有关。因此，问题的求解就比较困难复杂。有关。因此，问题的求解就比较困难复杂。 适合于用动态规划方法求解的只是一类特殊的多阶段决策适合于用动态规划方法求解的只是一类特殊的多阶段决策 问题，即具有问题，即具有“无后

2、效性无后效性”( (马尔柯夫性马尔柯夫性) )的多阶段决策过程。的多阶段决策过程。 所谓无后效性，是指系统从某个阶段往后的发展，仅由本阶所谓无后效性，是指系统从某个阶段往后的发展，仅由本阶 段所处的状态及其往后的决策所决定，与系统以前经历的状段所处的状态及其往后的决策所决定，与系统以前经历的状 态和决策态和决策( (历史历史) )无关。无关。多阶段决策过程特点多阶段决策过程特点: 状态状态 x x1 1 阶段阶段1 1 T T1 1 决策决策u u1 1 状态状态 x x2 2 决策决策u u2 2 阶段阶段2 2 T T2 2 状态状态 x x3 3 .状态 状态 x xk k 决策决策u

3、uk k 阶段阶段k k T Tk k 状态状态 x xk k+1 +1 .状态 状态 x xn n 决策决策u un n 阶段阶段n n TnTn 状态状态 x xn n+1 +1 第3页/共23页 第4页/共23页 第5页/共23页 第6页/共23页 第7页/共23页 (1)(,( 1kkkkk susTs 第8页/共23页 )(,( kkkk spsR 第9页/共23页 nkspsRoptsf kkkk sPp kk kKk ,2, 1),(,()( )( nkuuup nkkk , 2 , 1, 1 )(,( kkkk spsR ,),()( 211111 n uusussp nkuu

4、up nkkk , 2 , 1, 1 第10页/共23页 （5） nk Uu Ss usTs ts usususRRoptf kk kk kkkk nn uu n ,2,1 ),( . ),( 1 2211 1 , 21 n uuu , 121 nn ssss 第11页/共23页 则对上述策略中所隐含的任一状态而言， 第k子过程上对应于该状态的最优策略必然 包含在上述全过程最优策略p1*中，即为 )(,),(),()( 11nnkkkkkk susususp )(),(,),(),()( 221111nnkk sususususp 第12页/共23页 贝尔曼最优化原理概念贝尔曼最优化原理概念:

5、 如图如图, 如果已经给出从点如果已经给出从点A到到 点点C的最优轨迹，那么从任一中间点的最优轨迹，那么从任一中间点B到点到点C的部分轨迹必须的部分轨迹必须 是从是从B到到C的最优轨迹。的最优轨迹。 设给出路线设给出路线-是从是从A到到C的最优路的最优路 线，根据贝尔曼原理，则路线线，根据贝尔曼原理，则路线 是从是从B到到C的最优路线。的最优路线。 证证:用反证法用反证法, 假设某假设某 条其它路线，例如条其它路线，例如 是是 从从B到到C的最优路线，那的最优路线，那 么，路线么，路线I-比路线比路线I- 有更小的费用。但这与有更小的费用。但这与I- 是从是从A到到C最优路线的最优路线的 前提

6、相矛盾，因此前提相矛盾，因此必是必是 从从B到到C的最优路线的最优路线 贝尔曼阐述贝尔曼阐述: “一个最优策略有这样的特性，不论初始状态和一个最优策略有这样的特性，不论初始状态和 初始决策如何，相对于第一个决策所形成的状态来说，余下初始决策如何，相对于第一个决策所形成的状态来说，余下 的决策必定构成一个最优策略的决策必定构成一个最优策略”。 第13页/共23页 第14页/共23页 n ki iiikk usgsR),()( ),( iii usg ),(),( 111 nkkkkkk ssRusgR 第15页/共23页 求最短路径 4.动态规划方法应用举例 第16页/共23页 D D2 2(

7、(x x2 2)=)=D D2 2( (B B3 3)=)=B B3 3C C1 1, ,B B3 3C C2 2, ,B B3 3 C C3 3 f f 5 5 ( x( x 5 5 ) = f) = f 5 5 ( E ) = 0( E ) = 0 其含义是从其含义是从E E到到E E的最短路径为的最短路径为0 0。 第17页/共23页 x4 D4(x4) x5 v4(x4,d4) v4(x4,d4)+f5(x5) f4(x4) 最优决策 d4* D1 D 1E E 5 5+0=5* 5 D1E D2 D 2E E 2 2+0=2* 2 D2E )(),(min)( 55444 )( 44

8、 444 xfdxvxf xDd 从从f f5 5(x(x5 5) )到到f f4 4(x(x4 4) )的递推过程用下表表示的递推过程用下表表示 ： 第四阶段的递推方程为：第四阶段的递推方程为： 在上表中，在上表中，*表示最优值，由于决策允许集合表示最优值，由于决策允许集合D4(x4) 中的决策是唯一的，因此这个值就是最优值。中的决策是唯一的，因此这个值就是最优值。 第18页/共23页 由此得到f4(x4)的表达式。由 于这是一个离散的函数，取值用 列表表示： f4(x4)的表达式的表达式 D15D1E x4f4(x4)最优决策 d4* D22D2E 第19页/共23页 x3 D3(x3)

9、x4 v3(x3,d3) v3(x3,d3)+f4(x4) f3(x3) 最优决策 d3* C1 C1D1 C1D2 D1 D2 3 9 3+5=8* 9+2=11 8 C1D1 C2 C2D1 C2D2 D1 D2 6 5 6+5=11 5+2=7* 7 C2D2 C3 C3D1 C3D2 D1 D2 8 10 8+5=13 10+2=12* 12 C3D2 从从f f4 4(x(x4 4) )到到f f3 3(x(x3 3) )的递推过程用表格表示如下：的递推过程用表格表示如下： )(),(min)( 44333 )( 33 333 xfdxvxf xDd 第三阶段的递推方程为：第三阶段的

10、递推方程为： 第20页/共23页 由此得到由此得到f f3 3( (x x3 3) )的表达式的表达式, ,取值用列表表示取值用列表表示： x3 f3(x3) 最优决策d3* C1 8 C1D1 C2 7 C2D2 C3 12 C3D2 第21页/共23页 x2 D2(x2) x3 v2(x2,d2) v2(x2,d2)+f3(x3) f2(x2) 最优决策 d2* B1 B1C1 B1C2 B1C3 C1 C2 C3 12 14 10 12+8=20* 14+7=21 10+12=22 20 B1C1 B2 B2C1 B2C2 B2C3 C1 C2 C3 6 10 4 6+8=14* 10+7=17 4+12=16 14 B2C1 B3 B3C1 B3C2 B3C3 C1 C2 C3 13 12 11 13+8=21 12+