G信息工程大学 INFORMATION ENGINEERING UNIVERSITY 数学建模款学片 第十三章动态规划方法 设计制作:韩中庚 杜剑平 信息工程学院指挥管理系
■■■ cUneo 第十三章动态规划方法 ■■■■■ 主要内容 4动态规划的基本问题; 动态规划的基本概念与条件; 4动态规划的基本方程; 动态规划的求解方法; 4动态规划的应用案例分析。 信息大学申 2021年2月5日
第十三章 动态规划方法 3 2021年2月5日 动态规划的基本问题； 动态规划的基本概念与条件； 动态规划的基本方程； 动态规划的求解方法； 动态规划的应用案例分析
■■■ cUneo -,动态规划的一般问题 ■■■■■ 动态规划是一种用于处理多阶段决策问题 的数学方法。主要是先将一个复杂的问题分 解成相互联系的若干阶段,每个阶段即为 个小问题,然后逐个解决,当每个阶段的决 策确定之后,整个过程的决策也就确定了。 阶段一般用时间表示即与时间有关) 这就是“动态”的含义,把这种处理问题的 方法称为动态规划方法。 信息大学申 2021年2月5日
一、动态规划的一般问题 4 2021年2月5日 动态规划是一种用于处理多阶段决策问题 的数学方法。主要是先将一个复杂的问题分 解成相互联系的若干阶段，每个阶段即为一 个小问题，然后逐个解决，当每个阶段的决 策确定之后，整个过程的决策也就确定了。 阶段一般用时间段表示(即与时间有关)， 这就是“动态”的含义，把这种处理问题的 方法称为动态规划方法
■■■ cUneo 1.引例:最短路线问题 ■■■国■ (1)问题的提出 假设从A地到G地要铺设一条管道,如图 所示,中间经过5个中转站,第一个中转站可 以在{B,B2}中任一个,第二、三、四、五个中 转站分别在{C1,C2,C3,C4}、{D,D2,D3} {E1,E2,E}、{1,F2}中任选一个 接铺达5 直 求从 信息大喾唧度 2021年2月5日
5 2021年2月5日 1. 引例：最短路线问题 (1) 问题的提出 假设从 A 地到 G 地要铺设一条管道，如图 所示，中间经过 5 个中转站，第一个中转站可 以在{B1,B2 }中任一个，第二、三、四、五个中 转站分别在{C1 ,C2 ,C3 ,C4}、{D1,D2 ,D3 }、 {E1 ,E2 ,E3 }、{F1 ,F2 }中任选一个． 由于地理条件的限制，有些站点之间不可直 接铺设管道（图中无连线的站点），连线上的数 据表示相应管道的成本（距离、费用、时间等）．试 求从 A 到 G 使得成本最低的一条管道铺设线路．
■■■ cUneo 1.引例:最短路线问题 ■■■国■ (2)问题的分析 fE4人3 4 A)3 6 3 4 由题意可知,从A到G可分为6个阶段: A->B C D>E->F-G 共有48条路线,现在的问题是要求每一个阶段的最小值 (距离、费用,或时间)。 信瞿大学囀廣 2021年2月5日
6 2021年2月5日 (2) 问题的分析 1. 引例：最短路线问题 由题意可知，从 A 到 G 可分为 6 个阶段： A ⎯→B ⎯→C ⎯→D ⎯→E ⎯→F ⎯→G 1 2 3 4 5 6 ， 共有 48 条路线，现在的问题是要求每一个阶段的最小值 （距离、费用，或时间）
■■■ cUneo 1.引例:最短路线问题 ■■■国■ d.用动态规划的方法分步考虑 (1)求一个阶段最优 从F到G:d(F,G 为()=:0)=(的 以最短路线为F2→>G 3 368 }=7,E→F1→G 7 2021年2月5日
7 2021年2月5日 2 .用动态规划的方法分步考虑 1. 引例：最短路线问题 (1) 求一个阶段最优选择： 从 F 到 G： ( , ) 4, ( , ) 3 d F1 G = d F2 G = ，最优选择 为 ( ) ( , ) 4, ( ) ( , ) 3 f 6 F1 = d F1 G = f 6 F2 = d F2 G = ， 所 以最短路线为 F2 →G ； (2) 求两个阶段最优选择： 从 E 到 G，有三个出发点 1 2 3 E ,E ,E ： E F G d E F f F d E F f F f E = → → + + = + + = 1 1 1 2 6 2 1 1 6 1 5 1 7, 5 3 3 4 min ( , ) ( ) ( , ) ( ) ( ) min
A 2用动态规划的方法分步 迎2 人4 (2)求两个阶段最优选择 从E到G,有三个出发点E1,E2,E3 d(E1,F1)+f6(F1) 3+4 fs (e=min =7.E,→FG d(E1,F2)+f6(F2 5+3 f5(E2)=m d(E2, F)+6(ELms 5+ min 5,E,→F2→G (E2,F2)+f6(F2 2+3 d(E32F1)+f6(F1) 6+4 ∫5(E3)=mn mIn =9E,→F>G (3,F)+(FE) 6+3 所以最短路线为E,→>F,→>G; 信瞿大学囀廣 8 2021年2月5日
8 2021年2月5日 (2) 求两个阶段最优选择： 从 E 到 G，有三个出发点 1 2 3 E ,E ,E ： E F G d E F f F d E F f F f E = → → + + = + + = 1 1 1 2 6 2 1 1 6 1 5 1 7, 5 3 3 4 min ( , ) ( ) ( , ) ( ) ( ) min ， E F G d E F f F d E F f F f E = → → + + = + + = 2 2 2 2 6 2 2 1 6 1 5 2 5, 2 3 5 4 min ( , ) ( ) ( , ) ( ) ( ) min E F G d E F f F d E F f F f E = → → + + = + + = 3 2 3 2 6 2 3 1 6 1 5 3 9, 6 3 6 4 min ( , ) ( ) ( , ) ( ) ( ) min 所以最短路线为 E2 → F2 →G ； 2 .用动态规划的方法分步考虑
2用动态规划的方法分步考虑 ■■■ ■■■■■ (3)求三个阶段最优选择: 2+7 f4(D=min d(D,E)+(E) mIn =7D,→E→F→O d(D1,E2)+f5(E2) 2+5 d(D2,E2)+f(E2 1+5 f(D,)=min dD2,E)+(E) min =6,D,>E,→>F,>G 2+ f4(D3)=m D,E2)+(E2)3 +5 mIn 8.D,→E,→F→)G d(D3,E3)+f5(E3 3+ 所以最短路线为D2→E2→F→G 信息大学申
9 2021年2月5日 2 .用动态规划的方法分步考虑 (3)求三个阶段最优选择： D E F G d D E f E d D E f E f D = → → → + + = + + = 1 2 2 1 2 5 2 1 1 5 1 4 1 7, 2 5 2 7 min ( , ) ( ) ( , ) ( ) ( ) min D E F G d D E f E d D E f E f D = → → → + + = + + = 2 2 2 2 3 5 3 2 2 5 2 4 2 6, 2 9 1 5 min ( , ) ( ) ( , ) ( ) ( ) min ， D E F G d D E f E d D E f E f D = → → → + + = + + = 3 2 2 3 3 5 3 3 2 5 2 4 3 8, 3 9 3 5 min ( , ) ( ) ( , ) ( ) ( ) min 所以最短路线为D2 → E2 → F2 →G ；
2用动态规划的方法分步考虑 ■■■ ■■■■■ (4)求四个阶段最优选择: 从C到G有四个出发点C,C2C3C:最优选择为 d(C1,D1)+f(D) 6+7 f3(C1=mn min =13,C1→D1→>E,→>F2→G d(C,D2)+f4(D2 8+ Jd(, D)+f4(D, mIn min =10,C,→D→E,→F,→G ld(c, D))+SAD,) 信息大学申 2021年2月5日
10 2021年2月5日 2 .用动态规划的方法分步考虑 (4)求四个阶段最优选择： 从 C 到 G 有四个出发点 1 2 3 4 C ,C ,C ,C ：最优选择为 C D E F G d C D f D d C D f D f C = → → → → + + = + + = 1 1 2 2 1 2 4 2 1 1 4 1 3 1 13, 8 6 6 7 min ( , ) ( ) ( , ) ( ) ( ) min C D E F G d C D f D d C D f D f C = → → → → + + = + + = 2 1 2 2 2 2 4 2 2 1 4 1 3 2 10, 5 6 3 7 min ( , ) ( ) ( , ) ( ) ( ) min
2用动态规划的方法分步考虑 ■■■ ■■■国■ (4)求四个阶段最优选择: ) f3(C1)=13,C1→D1→>E2>F2→G f3(C2)=10,C2→D→E2→>F2→G d(C,D2)+f4(D2) f3(C3)=min min =9,C3→>D,→>E,→>F,→>G d(C,D3)+f4(D3) 3+8 d(C4,D2)+f(D2 ∫3(C4) mIn d(C4, D, )+A(D, ) min 12,C4→>D3→>E,→>F,→>G 所以最短路线为C3→D2→E2→F2→G; 信息大学申 11 2021年2月5日
11 2021年2月5日 2 .用动态规划的方法分步考虑 3 1 1 1 2 2 f C C D E F G ( ) 13, = → → → → 3 2 2 1 2 2 f C C D E F G ( ) 10, = → → → → C D E F G d C D f D d C D f D f C = → → → → + + = + + = 3 2 2 2 3 3 4 3 3 2 4 2 3 3 9, 3 8 3 6 min ( , ) ( ) ( , ) ( ) ( ) min C D E F G d C D f D d C D f D f C = → → → → + + = + + = 4 3 2 2 4 3 4 3 4 2 4 2 3 4 12, 4 8 8 6 min ( , ) ( ) ( , ) ( ) ( ) min 所以最短路线为 C3 → D2 → E2 → F2 → G ； （4)求四个阶段最优选择：