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 条路线，现在的问题是要求每一个阶段的最小值 （距离、费用，或时间）