管理运筹学 第六章 动态规划

第6章 动态规划§1 多阶段决策过程最优化问题举例

§2 基本概念、基本方程与最优化原理§3 动态规划的应用(1)

管

理

运

筹

学

§1 多阶段决策过程最优化问题举例例1 最短路径问题 下图表示从起点A到终点E之间各点的距离。求A到E的最 短路径。B 2 1 1 6 4 A 3 2 3 B2 7 2 C2 7 5 D 2 6 C3 1 6 E

C 16

8 D 1

4

10

4B3 7 3

8

1

5

4管 理 运 筹 学2

§1 多阶段决策过程最优化问题举例用穷举法的计算量: 如果从A到E的站点有k个，除A、E之外每站有3个位置则

总共有3k-1×2条路径；计算各路径长度总共要进行 (k+1) 3k-1×2次加法以及3k1×2-1次比较。随着

k 的值增加时，需要进行的加法和比较的

次数将迅速增加；例如当 k=20时，加法次数为 4.2550833966227×1015 次， 比较 1.3726075472977×1014 次。若用1亿次/秒的计算机计算 需要约508天。

管

理

运

筹

学

§1 多阶段决策过程最优化问题举例讨论： 1、以上求从A到E的最短路径问题，可以转化为四个性质完全相

同，但规模较小的子问题，即分别从Di 、Ci、Bi、A到E的最短路径问题。 第四阶段：两个始点D1和D2,终点只有一个；表6-1 阶段4本阶段始点 (状态) D1 D2 本阶段各终点(决策) E 10* 6 10 6 到E的最短距离 本阶段最优终点 (最优决策) E E

分析得知：从D1和D2到E的最短路径唯一。管 理 运 筹 学4

§1 多阶段决策过程最优化问题举例第三阶段：有三个始点C1,C2,C3,终点有D1,D2,对始点 和终点进行分析和讨论分别求C1,C2,C3到D1,D2 的最短路 径问题：表6-2 阶段3

本阶段始点 (状态)C1 C2 C3

本阶段各终点(决策)D1 8+10=18 7+10=17 1+10=11 D2 6+6=12 5+6=11 6+6=12

本阶段最优终点 到E的最短距离 (最优决策)12 11 11 D2 D2 D1

分析得知：如果经过C1,则最短路为C1-D2-E; 如果经过C2,则最短路为C2-D2-E; 如果经过C3,则最短路为C3-D1-E。

管

理

运

筹

学

§1 多阶段决策过程最优化问题举例第二阶段：有4个始点B1,B2,B3,B4,终点有C1,C2,C3。对始点和终点进行分 析和讨论分别求B1,B2,B3,B4到C1,C2,C3 的最短路径问题：表6-3 阶段2 本阶段始点 (状态) B1 B2 B3 B4 本阶段各终点(决策)

C12+12=14 4+12=16 4+12=16 7+12=19

C21+11=12 7+11=18 8+11=19 5+11=16

C36+11=17 2+11=13 3+11=14 1+11=12

到E的最 短距离 12 13 14 12

本阶段最优终 点(最优决策) C2 C3 C3 C3

分析得知：如果经过B1,则走B1-C2-D2-E; 如果经过B2,则走B2-C3-D1-E; 如果经过B3,则走B3-C3-D1-E; 如果经过B4,则走B4-C3-D1-E。管 理 运 筹 学6

§1 多阶段决策过程最优化问题举例第一阶段：只有1个始点A,终点有B1,B2,B3,B4 。对始点和终 点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：表6-4 阶段1 本

阶段始 点(状态) A 本阶段各终点(决策) B1 B2 B3 3+14=17 B4 2+12=14 4+12=16 3+13=16 到E的最 短距离 14 本阶段最优终 点(最优决策) B4

最后，可以得到：从A到E的最短路径为A B4 C3 D1 E

管

理

运

筹

学

§1 多阶段决策过程最优化问题举例以上计算过程及结果，可用图2表示，可以看到，以上方法不仅 得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最 短路径。12 B1 14 A 3 2 4 3 2 6 1 12 C1 6 11 7 2 4 8 3 1 7 5 D2 6 6 6 8 10 D1 10

13 4 B2

0 E

C2

B3

C31 11

14 7 5B4

12

以上过程，仅用了22次加法，计算效率远高于穷举法。管 理 运 筹 学8

§2 基本概念、基本方程与最优化原理一、基本概念： 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):某一状态以及该状态下的决策， 与下一状态之间的函数关系。管 理 运 筹 学9

§2 基本概念、基本方程与最优化原理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的最优值，即f k (sk ) 管

optxk Dk ( s k )

{ Vk , n ( s k , P k , n )}筹 学10

理

运

§2 基本概念、基本方程与最优化原理对于可加性指标函数，上式可以写为f k ( sk )

optxk Dk ( sk )

{vk ( sk , xk ) f k 1 ( sk 1 )}

k 1,2, , n

上式中“opt”表示“max”或“min”。对于可乘性指标函数，上式 可以

写为

f k ( sk )

optxk Dk ( sk )

{vk ( sk , xk ) f k 1 ( sk 1 )}

k 1,2, , n

以上式子称为动态规划最优指标的递推方程 …… 此处隐藏：1802字，全部文档内容请下载后查看。喜欢就下载吧 ……