§1多阶段决策过程最优化问题举例 第一阶段:只有1个始点A,终点有B1,B2B3,B4。对始点和终 点进行分析和讨论分别求A到B1B2,B3B4的最短路径问题: 表10-4 阶段1 本阶段始 本阶段各终点(决策) 到E的最本阶段最优终 点状态)B,B2B2B,短距离点最优决第 4+12=163+13=163+14=172+12=14 14 B 最后,可以得到:从A到E的最短路径为A→>B4→>C3>D1→ E 运莓
管 理 运 筹 学 6 第一阶段：只有1个始点A，终点有B1 ,B2 ,B3 ,B4。对始点和终 点进行分析和讨论分别求A到B1 ,B2 ,B3 ,B4的最短路径问题： 表10-4 最后，可以得到：从A到E的最短路径为A→ B4→ C3→ D1→ E §1 多阶段决策过程最优化问题举例 阶段1 本阶段始 点(状态) 本阶段各终点（决策） 到E的最 短距离 本阶段最优终 点(最优决策) B1 B2 B3 B4 A 4+12=16 3+13=16 3+14=17 2+12=14 14 B4
§1多阶段决策过程最优化问题举例 以上计算过程及结果,可用图2表示,可以看到,以上方法不仅 得到了从A到D的最短路径,同时,也得到了从图中任一点到E的最 短路径。 以上过程,仅用了22次加法,计算效率远高于穷举法。 运筹
管 理 运 筹 学 7 以上计算过程及结果，可用图2表示，可以看到，以上方法不仅 得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最 短路径。 以上过程，仅用了22次加法，计算效率远高于穷举法。 A B B C D B C D E C 4 1 2 3 1 2 3 1 2 3 3 2 1 6 4 7 2 4 8 3 8 6 7 5 1 6 10 6 0 10 6 12 11 11 12 13 14 14 B4 12 7 5 1 2 §1 多阶段决策过程最优化问题举例
§2基本概念、基本方程与最优化原理 基本概念: 1、阶段k:表示决策顺序的离散的量,阶段可以按时间或空间划 分。 2、状态s:能确定地表示决策过程当前特征的量。状态可以是 数量,也可以是字符,数量状态可以是连续的,也可以是离散 的 3、决策x:从某一状态向下一状态过渡时所做的选择。决策是 所在状态的函数,记为x1(s1) 决策允许集合D):在状态s下,允许取决策的全体。 4、策略PL(S):从第k阶段开始到最后第功阶段的决策序列,称k 子策略。P1n(S1)即为全过程策略。 5、状态转移方程S+1=T(s,x):某一状态以及该状态下的决策, 与下一状态之间的函数关系
管 理 运 筹 学 8 一、基本概念： 1、阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划 分。 2、状态sk：能确定地表示决策过程当前特征的量。状态可以是 数量，也可以是字符，数量状态可以是连续的，也可以是离散 的。 3、决策xk：从某一状态向下一状态过渡时所做的选择。决策是 所在状态的函数，记为xk (sk )。 决策允许集合Dk (sk )：在状态sk下，允许采取决策的全体。 4、策略Pk,n(sk )：从第k阶段开始到最后第n阶段的决策序列，称k 子策略。P1,n(s1 )即为全过程策略。 5、状态转移方程 sk+1=Tk (sk , xk )：某一状态以及该状态下的决策， 与下一状态之间的函数关系。 §2 基本概念、基本方程与最优化原理
§2基本概念、基本方程与最优化原理 6、阶段指标函数v(sx1):从状态s出发,选择决策x所产生的第 k阶段指标 过程指标函数vn(S1,x1,xk+1…,x):从状态s出发,选择决策 x,…,xn所产生的过程指标。动态规划要求过程指标具有可分离 性,即Ⅴkn(Ss,x,xk+1…,xn)=v(s,X)+Vk+1( k+19k+15 称指标具有可加性,或Ⅴn(S1,x2xk+1,…,xn)=v(sx)×V1(Sk+1, k,3…,xn)称指标具有可乘性。 基本方程 最优指标函数s):从状态s出发,对所有的策略Pn,过程 指 (Sk)=opt ilk,n(Sk, i, n)3 OK (sk) 标vn的最优值,即 管理筹学
管 理 运 筹 学 9 6、阶段指标函数vk (sk , xk )：从状态sk出发，选择决策xk所产生的第 k阶段指标。 过程指标函数Vk,n(sk , xk , xk+1 ,…, xn )：从状态sk出发，选择决策 xk , xk+1 , …, xn所产生的过程指标。动态规划要求过程指标具有可分离 性，即 Vk,n(sk , xk , xk+1 , …, xn ) = vk (sk , xk )+Vk+1 (sk+1 , xk+1 , …, xn ) 称指标具有可加性，或 Vk,n(sk , xk , xk+1 , …, xn ) = vk (sk , xk )×Vk+1 (sk+1 , xk+1 , …, xn )称指标具有可乘性。 二、基本方程： 最优指标函数fk (sk )：从状态sk出发，对所有的策略Pk,n，过程 指 标Vk,n的最优值，即 ( ) { , ( , , )} ( ) k n k k n x D s f k sk opt V s P k k k = §2 基本概念、基本方程与最优化原理
§2基本概念、基本方程与最优化原理 对于可加性指标函数,上式可以写为 f(sk)=opt iv(,xk)+f+(sk+1)) k=1,2,…,n xk∈Dk(Sk) 上式中“opt”表示“max”或“min”。对于可乘性指标函数,上 式可以 写为f(s)=Opt{(s,x)×1(S1) k=1,2,…,n xk∈Dk(Sk) 以上式子称为动态规划最优指标的递推方程,是动态规划的基本 方程。 终端条件:为了使以上的递推方程有递推的起点,必须要设定最 优指标的终端条件,一般最后一个状态n+1下最优指标fm(m1)=0。 10
管 理 运 筹 学 10 对于可加性指标函数，上式可以写为 上式中“opt”表示“max”或“min”。对于可乘性指标函数，上 式可以 写为 以上式子称为动态规划最优指标的递推方程，是动态规划的基本 方程。 终端条件：为了使以上的递推方程有递推的起点，必须要设定最 优指标的终端条件，一般最后一个状态n+1下最优指标fn+1 (sn+1 ) = 0。 f s vk sk xk f k sk k n x D s k k opt k k k ( ) { ( , ) ( )} 1,2, , 1 1 ( ) = + + + = f s v s x f s k n k k k k k x D s k k opt k k k ( ) { ( , ) ( )} 1,2, , 1 1 ( ) = + + = §2 基本概念、基本方程与最优化原理