第十章动恋规期 §1多阶段决策过程最优化问题举例 §2基本概念、基本方程与最优化原理 §3动态规划的应用(1) §4动态规划的应用(2) 管理蓦
管 理 运 筹 学 1 第十章 动态规划 §1 多阶段决策过程最优化问题举例 §2 基本概念、基本方程与最优化原理 §3 动态规划的应用(1) §4 动态规划的应用(2)
§1多阶段决策过程最优化问题举例 例1最短路径问题 下图表示从起点A到终点E之间各点的距离。求A到E的最 短路径。 B 10 7 B 2 C 运莓
管 理 运 筹 学 2 §1 多阶段决策过程最优化问题举例 例1 最短路径问题 下图表示从起点A到终点E之间各点的距离。求A到E的最 短路径。 A B B C D B C D E C 4 1 2 3 1 2 3 1 2 3 2 2 1 6 4 7 2 4 8 3 8 6 7 5 6 1 10 6 4 3 7 5 1
§1多阶段决策过程最优化问题举例 讨论: 1、以上求从A到E的最短路径问题,可以转化为四个性质完全相 同,但规模较小的子问题,即分别从D;、C;、B;、A到E的最短路 径问题。 第四阶段:两个始点D1和D2,终点只有一个; 表 10-1 阶段4 本阶段始点|本阶段各终点(决策)」到E的最短距离本阶段最优终点 (状态) E (最优决策) 10* 10 D 6 6 EE 分析得知:从D和D2到E的最短路径唯一 管理蓦
管 理 运 筹 学 3 §1 多阶段决策过程最优化问题举例 讨论： 1、以上求从A到E的最短路径问题，可以转化为四个性质完全相 同，但规模较小的子问题，即分别从Di、Ci、Bi、A到E的最短路 径问题。 第四阶段：两个始点D1和D2，终点只有一个； 表10-1 分析得知：从D1和D2到E的最短路径唯一。 阶段4 本阶段始点 （状态） 本阶段各终点（决策） 到E的最短距离 本阶段最优终点 E （最优决策) D1 D2 10* 6 10 6 E E
§1多阶段决策过程最优化问题举例 第三阶段:有三个始点C1,C2,C3,终点有D1,D2,对始点 和终点进行分析和讨论分别求C1,C2,C3到D1,D2的最短路 径问题: 表10-2 阶段3 本阶段始点本阶段各终点(决策) 到E的最短距离本阶段最优终点 (状态) D D (最优决策) C 8+10=18 6+6=12 12 7+10=17 5+6=11 1+10=11 6+6=12 D 分析得知:如果经过C1,则最短路为C1-D2-E; 如果经过C2,则最短路为C2-D2E; 如果经过C3,则最短路为C3-D1-E。 管理蓦 4
管 理 运 筹 学 4 第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点 和终点进行分析和讨论分别求C1，C2，C3到D1，D2 的最短路 径问题： 表10-2 分析得知：如果经过C1，则最短路为C1 -D2 -E； 如果经过C2，则最短路为C2 -D2 -E； 如果经过C3，则最短路为C3 -D1 -E。 §1 多阶段决策过程最优化问题举例 阶段3 本阶段始点 （状态） 本阶段各终点（决策） 到E的最短距离 本阶段最优终点 D （最优决策) 1 D2 C1 C2 C3 8+10=18 7+10=17 1+10=11 6+6=12 5+6=11 6+6=12 12 11 11 D2 D2 D1
§1多阶段决策过程最优化问题举例 第二阶段:有4个始点B1,B2,B3,B4终点有C1C2C3。对始点和终点进行分 析和讨论分别求B1,B2B3,B到C1C2C3的最短路径问题: 表10-3 阶段2 本阶段始点 本阶段各终点(决策) 到E的最本阶段最优终 (状态) C C 短距离点(最优决策) 2+12=14 1+1=126+11-=17 12 BBBB 4+12=16 7+11=182+11=13 13 4+12=16 8+11=193+11=14 14 Cccc 4 7+12=195+11=161+1=12 12 分析得知:如果经过B1,则走B1-C2-D2-E; 如果经过B2,则走B2CxD1E; 如果经过B3,则走B3CxD1E 如果经过B,则走BrC3D1E
管 理 运 筹 学 5 第二阶段：有4个始点B1 ,B2 ,B3 ,B4，终点有C1 ,C2 ,C3。对始点和终点进行分 析和讨论分别求B1 ,B2 ,B3 ,B4到C1 ,C2 ,C3的最短路径问题： 表10-3 分析得知：如果经过B1，则走B1 -C2 -D2 -E； 如果经过B2，则走B2 -C3 -D1 -E； 如果经过B3，则走B3 -C3 -D1 -E； 如果经过B4，则走B4 -C3 -D1 -E。 §1 多阶段决策过程最优化问题举例 阶段2 本阶段始点 （状态） 本阶段各终点（决策） 到E的最 短距离 本阶段最优终 点（最优决策) C1 C2 C3 B1 B2 B3 B4 2+12=14 4+12=16 4+12=16 7+12=19 1+11=12 7+11=18 8+11=19 5+11=16 6+11=17 2+11=13 3+11=14 1+11=12 12 13 14 12 C2 C3 C3 C3
§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 基本概念、基本方程与最优化原理