《动态规划》PPT课件.pptx

《《动态规划》PPT课件.pptx》由会员分享，可在线阅读，更多相关《《动态规划》PPT课件.pptx（48页珍藏版）》请在装配图网上搜索。

1、 Copyright Li Yuxin. All Rights Reserved 1 Copyright Li Yuxin. All Rights Reserved 2 动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个n 维决策问题变换为几个一维最优化问题，从而一个一个地去解决。 Copyright Li Yuxin. All Rights Reserved Copyright Li Yuxin. All Rights Reserved1 2 n状 态 决 策 状 态 决 策状 态 状 态 决 策 Copyright Li Yuxin. All Rights Re

2、served 5 年 、 月 、路 段一 个 数 、一 组 数 、一 个 向 量 Copyright Li Yuxin. All Rights Reserved 6 3、 决 策 ： 表 示 当 过 程 处 于 某 一 阶 段 的 某 个 状 态 时 ， 可以 作 出 不 同 的 决 定 ， 从 而 确 定 下 一 阶 段 的 状 态 ， 这 种决 定 称 为 决 策 。 描 述 决 策 的 变 量 ， 称 为 决 策 变 量 。 决 策 变 量 是 状 态变 量 的 函 数 。 可 用 一 个 数 、 一 组 数 或 一 向 量 （ 多 维 情形 ） 来 描 述 。 在 实 际 问 题 中

3、决 策 变 量 的 取 值 往 往 在 某 一 范 围 之 内 ，此 范 围 称 为 允 许 决 策 集 合 。 系 统 在 某 一 阶 段 的 状 态 转 移 不 但 与 系 统 的 当 前 的 状 态和 决 策 有 关 ， 而 且 还 与 系 统 过 去 的 历 史 状 态 和 决 策 有 关 。4、 多 阶 段 决 策 过 程 可 以 在 各 个 阶 段 进 行 决 策 ， 去 控 制 过 程 发 展 的 多 段 过程 ； 其 发 展 是 通 过 一 系 列 的 状 态 转 移 来 实 现 的 ； Copyright Li Yuxin. All Rights Reserved 7 ),(

4、 ),( ),( 22111 221123 1112 kkkk usususTs ususTs usTs图 示 如 下 ： 状 态 转 移 方 程 是 确 定由 一 个 状 态 到 另 一 个状 态 的 演 变 过 程 。 如果 第 k阶 段 状 态 变 量 sk的 值 、 该 阶 段 的 决 策变 量 一 经 确 定 ， 第 k+1阶 段 状 态 变 量 sk+1的 值也 就 确 定 。其 状 态 转 移 方 程 如 下 （ 一 般 形 式 ）1 2 ks1 u1 s2 u2s3 sk uk sk+1 能 用 动 态 规 划 方 法 求 解 的 多 阶 段 决 策 过 程 是 一 类特 殊

5、的 多 阶 段 决 策 过 程 ， 即 具 有 无 后 效 性 的 多 阶 段决 策 过 程 。 Copyright Li Yuxin. All Rights Reserved 8),( ),( ),(1 2223 1112 kkkk usTs usTs usTs 状态变量要满足无后效性的要求； Copyright Li Yuxin. All Rights Reserved Copyright Li Yuxin. All Rights Reserved ),()( 1, susVoptsf nkknkkk uu nk ),(, 111,1 nkknkkkk susVus),(1 kkkk us

6、Ts ),( 111, nkkkknknk sususVV),( 111, nkkkknk sususV Copyright Li Yuxin. All Rights Reserved 1 1 , *2*1 nuuu, *2*1 nsss解 多 阶 段 决 策 过 程 问 题 ， 求 出 最 优 策 略 ， 即 最 优 决 策 序 列 susvoptsf nkknkkk uu nk 1, , f1(s1) 最 优 轨 线 ， 即 执 行 最 优 策 略 时 的 状 态 序 列 最 优 目 标 函 数 值 ),( *1*1*,1*,1 nnnn ususVV 从 k 到 终 点 最 优 策 略子

7、 策 略 的 最 优 目 标 函 数 值 Copyright Li Yuxin. All Rights Reserved 1 2 Copyright Li Yuxin. All Rights Reserved 1 3 Copyright Li Yuxin. All Rights Reserved 1 4 Copyright Li Yuxin. All Rights Reserved 1 5 Copyright Li Yuxin. All Rights Reserved 1 6A B1B2 C1C2C3 D24 333 32 11 141、最短路径问题 Copyright Li Yuxin. A

8、ll Rights Reserved 1 7 解 ： 整 个 计 算 过 程 分 三 个 阶 段 ， 从 最 后 一 个 阶 段 开 始 。 第 一 阶 段 （ C D） ： C 有 三 条 路 线 到 终 点 D 。 A B1B2 C1C2C3 D24 333 32 11 14显 然 有 f1 (C1 ) = 1 ； f1(C2 ) = 3 ； f1 (C3 ) = 4 Copyright Li Yuxin. All Rights Reserved 1 8 d( B1,C1 ) + f1 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f1 (C2 ) = mi

9、n 3+3 d( B1,C3 ) + f1 (C3 ) 1+4 4 = min 6 = 4 5第 二 阶 段 （ B C） ： B 到 C 有 六 条 路 线 。 A B1B2 C1C2C3 D24 333 32 11 14(最 短 路 线 为 B 1C1 D) Copyright Li Yuxin. All Rights Reserved 1 9 d( B2,C1 ) + f1 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f1 (C2 ) = min 3+3 d( B2,C3 ) + f1 (C3 ) 1+4 3 = min 6 = 3 5 A B1B2 C

10、1C2C3 D24 333 32 11 14(最 短 路 线 为 B 2C1 D) Copyright Li Yuxin. All Rights Reserved 2 0 第 三 阶 段 （ A B ） ： A 到 B 有 二 条 路 线 。 f3(A)1 = d(A, B1 ) f2 ( B1 ) 2 4 6 f3 (A)2 = d(A, B2 ) f2 ( B2 ) 4 3 7 f3 (A) = min = min 6,7 =6d(A, B1 ) f2 ( B1 )d(A, B2 ) f2 ( B2 )(最 短 路 线 为 AB1C1 D)A B1B2 C1C2C3 D24 333 32

11、11 14 Copyright Li Yuxin. All Rights Reserved 2 1 A B1B2 C1C2C3 D24 333 32 11 14最 短 路 线 为 A B1 C1 D 路 长 为 6 Copyright Li Yuxin. All Rights Reserved 2 2 nix ax xgZini i ni ii .2.1 0 )(max1 1 2、投资分配问题 Copyright Li Yuxin. All Rights Reserved Copyright Li Yuxin. All Rights Reserved nk yxfygxf kkxyk .3.2

12、 )()(m ax)( 10 其 中 )()(m ax)( 1,2,1,0 yxfygxf kkxyk Copyright Li Yuxin. All Rights Reserved 2 5 投资利 润 0 10 20 30 40 50 60g1(x) 0 20 50 65 80 85 85g2(x) 0 20 40 50 55 60 65g3(x) 0 25 60 85 100 110 115g4(x) 0 25 40 50 60 65 70 Copyright Li Yuxin. All Rights Reserved 2 6 投 资利 润 0 10 20 30 40 50 60f1(x)

13、 g1(x) 0 20 50 65 80 85 85最 优 策 略 0 10 20 30 40 50 60 )60()(m ax)60( 1260,10,02 yfygf y Copyright Li Yuxin. All Rights Reserved 2 7 120065 2060 5055 6550 8040 8520 850m ax)0()60( )10()50( )20()40( )30()30( )40()20( )50()10( )60()0(m ax 12 12 12 12 12 12 12 fg fg fg fg fg fg fg最 优 策 略 为 （ 40， 20） ， 此

14、 时 最 大 利 润 为 120万 元 。同 理 可 求 得 其 它 f2(x) 的 值 。 Copyright Li Yuxin. All Rights Reserved 2 8 105)0()50( )10()40( )20()30( )30()20( )40()10( )50()0( )50()(m ax)50( 12 12 12 12 12 12 1250,10,02 fg fg fg fg fg fg yfygf y最 优 策 略 为 （ 30， 20） ， 此 时 最 大 利 润 为 105万 元 。 Copyright Li Yuxin. All Rights Reserved

15、2 9 90 )40()(m ax)40( 1240,10,02 yfygf y最 优 策 略 为 （ 20， 20） ， 此 时 最 大 利 润 为 90万 元 。 70 )30()(m ax)30( 1230,20,10,02 yfygf y最 优 策 略 为 （ 20， 10） ， 此 时 最 大 利 润 为 70万 元 。 Copyright Li Yuxin. All Rights Reserved 3 0 50 )20()(max)20( 1220,10,02 yfygf y 20 )10()(max)10( 12,10,02 yfygf y最 优 策 略 为 （ 10， 0） 或

16、 （ 0 ， 10 ） ， 此 时 最 大 利 润为 20万 元 。 f 2(0) 0。 最 优 策 略 为 （ 0， 0） ， 最 大 利 润 为 0万 元 。 得 到 下 表最 优 策 略 为 （ 20， 0） ， 此 时 最 大 利 润 为 50万 元 。 Copyright Li Yuxin. All Rights Reserved 3 1 投资利 润 0 10 20 30 40 50 60f2(x) 0 20 50 70 90 105 120最 优 策 略 (0,0) (10,0)(0,10) (20,0) (20,10) (20,20) (30,20) (40,20)第 三 阶 段

17、 ： 求 f3(x)。 此 时 需 考 虑 第 一 、 第 二 及 第 三 个工 厂 如 何 进 行 投 资 分 配 ， 以 取 得 最 大 的 总 利 润 。 )60()(m ax)60( 2360,10,03 yfygf y Copyright Li Yuxin. All Rights Reserved 3 2 1550115 20110 50100 7085 9060 10525 1200m ax)0()60( )10()50( )20()40( )30()30( )40()20( )50()10( )60()0(m ax 23 23 23 23 23 23 23 fg fg fg fg

18、 fg fg fg最 优 策 略 为 （ 20， 10， 30） ， 最 大 利 润 为 155万 元 。同 理 可 求 得 其 它 f3(x) 的 值 。 得 到 下 表 Copyright Li Yuxin. All Rights Reserved 3 3 投资利 润 0 10 20 30 40 50 60f3(x) 0 25 60 85 110 135 155最 优策 略 (0,0,0) (0,0,10) (0,0,20) (0,0,30) (20,0,20) (20,0,30) (20,10,30)第 四 阶 段 ： 求 f4(60)。 即 问 题 的 最 优 策 略 。 )60()(

19、m ax)60( 3460,10,04 yfygf y Copyright Li Yuxin. All Rights Reserved 3 4 160070 2565 6060 8550 11040 13525 1550m ax)0()60( )10()50( )20()40( )30()30( )40()20( )50()10( )60()0(m ax 34 34 34 34 34 34 34 fg fg fg fg fg fg fg最 优 策 略 为 （ 20， 0， 30， 10） ， 最 大 利 润 为 160万 元 。 Copyright Li Yuxin. All Rights R

20、eserved 3 5 3、背包问题 Copyright Li Yuxin. All Rights Reserved 3 6 ).2.1(0max 1 njx axa xcZjnij jj nj jj 且 为 整 数 Copyright Li Yuxin. All Rights Reserved 3 7 其 递 推 关 系 式 为 ： nk xayfxcyf kkkkkayxk kk 2 )(max)( 10 其 中当 k=1 时 ， 有 ： 的 最 大 整 数表 示 不 超 过其 中 11 11111 , )( ayay ayxaycyf Copyright Li Yuxin. All Ri

21、ghts Reserved 3 8 且 为 整 数0, 5523 1258max 321 321 321xxx xxx xxxZ 物 品 1 2 3重 量 （ 公 斤 ） 3 2 5使 用 价 值 8 5 12解 ： a 5 ， 问 题 是 求 f3(5) )55(12max)5( 323503 3 33 xfxf x ax 整 数 Copyright Li Yuxin. All Rights Reserved 3 9 )1()0( 22 32310 323550 323503 333 3 33 3 3 )0(12),5(0max )55(12max )55(12max )55(12max)5

22、( xxxx xx ax ff xfx xfx xfxf ， 整 数整 数 Copyright Li Yuxin. All Rights Reserved 4 0 5 5 )( 2)1()0( 111 2122,10 212250 212502 2222 2 22 2 2 )1(10),3(5),5(0max )25(max )25(max )25(5max)5( xxxxx xx ax fff xfx xfx xfxf ， 整 数整 数 Copyright Li Yuxin. All Rights Reserved 4 1 )0()0(0max )20(max )20(max )20(5ma

23、x)0( 1)0( 1 2120 212200 212002 22 2 22 2 2 ff xfx xfx xfxf xxx xx ax 5 5 整 数整 数 Copyright Li Yuxin. All Rights Reserved 4 2)0(0308)0( )0(0318)1( )1(8338)3( )1(8358)5( 1111 1111 1111 1111 xxcf xxcf xxcf xxcf )1,1(1310,85,8max )1(10),3(5),5(0max)5( 21 2)1()0( 1112 222 xx ffff xxx )( Copyright Li Yuxin

24、. All Rights Reserved 4 3 )0,0(0)0()0(0max)0( 211)0( 12 2 xxfff x )0,1,1(13 012,130max )0(12),5(0max)5( 321 )1()0( 223 33 xxx fff xx所 以 ， 最 优 解 为 X （ 1 , 1 , 0） ， 最 优 值 为 Z = 13。 Copyright Li Yuxin. All Rights Reserved 小 组1 2 30 0.40 0.60 0.801 0.20 0.40 0.502 0.15 0.20 0.30 4 4 4、系统可靠性问题 Copyright

25、Li Yuxin. All Rights Reserved 阶 段 1 2 3小 组 1 2 3 4 5 Copyright Li Yuxin. All Rights Reserved 4 6 s3 f3*(s3) x3*0 0 80 01 0 50 12 0 30 2 x2s 2 f2(s2,x2)=P2(x2) f3*(s2-x2) f2*(s2) x2*0 1 20 0 48 0 48 01 0 30 0 32 0 30 02 0 18 0 20 0 16 0 16 2 Copyright Li Yuxin. All Rights Reserved 4 7 x1s1 f1(s1,x1)=P1(x1) f2*(s1-x1) f2*(s2) x2*0 1 22 0 064 0 060 0 072 0 060 1 Copyright Li Yuxin. All Rights Reserved