第1章动态规划方法课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第10章 动态规划方法,11/14/2024,1,第10章 动态规划方法8/7/20231,动态规划,（Dynamic Programming）同前面介绍过的线性规划方法不同，它不是一种算法，而是考察问题的一种途径。动态规划是一种求解多阶段决策问题的系统技术。由于动态规划不是一种特定的算法，因而它不像线性规划那样有一个标准的数学表达式和明确定义的一组规则，动态规划必须对具体问题进行具体的分析处理。动态规划在自然科学和社会科学等各个领域都有着广泛的应用，并且获得了显著的效果。,11/14/2024,2,动态规划（Dynamic Programming,1 最短路径问题,2 贝尔曼最优化原理,3,W,inQSB软件应用,动态规划,11/14/2024,3,1 最短路径问题 2 贝尔曼最优化原理 3 WinQSB,动态规划是解决多阶段决策问题的一种方法.1951年，美国数学家贝尔曼（R.Bellman，19201984）研究了一类多阶段决策问题的特征，提出了解决这类问题的基本原理。在研究、解决了某些实际问题的基础上，他于1957年出版了动态规划这一名著。本章将简要介绍动态规划的思想方法及其应用。,11/14/2024,4,动态规划是解决多阶段决策问题的一种方法.1951年，美国数,动态规划解决问题的基本思路是：把整体比较复杂的大问题划分成一系列较易于解决的小问题，通过逐个求解，最终取得整体最优解。这种“分而治之，逐步调整”的方法，在一些比较难以解决的复杂问题中已经显示出优越性。,11/14/2024,5,动态规划解决问题的基本思路是：把整体比较复杂的大问题划分,所谓多阶段决策过程是指这样一类活动过程：一个决策过程可以分为若干个相互联系的阶段，每个阶段都需要作一定的决策，但是每个阶段最优决策的选择不能只是孤立地考虑本阶段所取得的效果如何，必须把整个过程中的各个阶段联系起来考虑，要求所选择的各个阶段决策的集合策略，能使整个过程的总效果达到最优。,11/14/2024,6,所谓多阶段决策过程是指这样一类活动过程：一个决策过程可以,1 最短路径问题,11/14/2024,7,1 最短路径问题 8/7/20237,1 最短路径问题,【例1】,设在E城的某公司要从,S,城运送一批货物，两城之间有公路相连（见图 1(a)），其中,是可以供选择的途经站点，各点连线上的数字表示相邻站点间的距离。现在的问题是选择一条由,S,到,E,的路径，使得所经过的路径最短。,11/14/2024,8,1 最短路径问题【例1】设在E城的某公司要从S城运送一批货,1 最短路径问题,(a),(b),11/14/2024,9,1 最短路径问题(a)(b)8/7/20239,1 最短路径问题,分析：如果用枚举法，将有12条不同的路径，每条路径对应一个由,S,到,E,的路径距离，其中最小值所对应的路径即为最短路径。本问题的最短路径有3条，路程均为21个单位：,第1条：,第2条：,第3条：,11/14/2024,10,1 最短路径问题分析：如果用枚举法，将有12条不同的路径，每,1 最短路径问题,当段数很多时，枚举法的计算量将极其庞大。,现在换个思路，寻找由,S,到,E,的最短路径。先把最短路径问题所考虑的过程分为4个阶段：,由,S,到 为第1阶段；,由,到 为第2阶段；,由,到,E,为第4阶段。,由,到 为第3阶段；,11/14/2024,11,1 最短路径问题当段数很多时，枚举法的计算量将极其庞大。由S,1 最短路径问题,我们称由某点到终点的阶段数,k,为,阶段变量,，如由 到,E,的阶段数为1（这时记由,C,到,E,的阶段数为1，它与第1阶段是不同的概念），由 到,E,的阶段数为2（这时记由,B,到,E,的阶段数为2），等等。可见阶段变量的取值正好与实际进行的阶段相反（图（b）。,(b),11/14/2024,12,1 最短路径问题我们称由某点到终点的阶段数k为阶段变量，如由,1 最短路径问题,在任一阶段开始时所处的位置称为,状态变量,，在阶段,k,的状态变量记为 ，例如 为阶段3的状态变量，可以取为 中任意一个。,当某一个状态给定后，需要做出决策以确定下一步的状态，描述决策的变量称为决策变量，在阶段,k,的决策变量记为 。例如在阶段2的状态取 时的决策变量记为 ，可取为 。若 ，则表示由 到 ，从而决定了下一步的状态是 。,11/14/2024,13,1 最短路径问题在任一阶段开始时所处的位置称为状态变量，在阶,1 最短路径问题,为了寻找由起点,S,到,E,终点的最短路径，我们考察前面用枚举法找到的第1条最短路径：,容易看出：子路径“”也应是从 出发到终点,E,的所有路径中最短的一条。,这个现象启发我们从阶段1开始，逐段逆向地求出各点到终点,E,的最短路径，最后求得由起点,S,到终点,E,的最短路径，这就是动态规划的基本思想。,11/14/2024,14,1 最短路径问题为了寻找由起点S到E终点的最短路径，我们考察,1 最短路径问题,以 表示在阶段,k,的状态变量为 、决策变量为 时点 与 间的距离；记 为在阶段,k,由点 到终点,E,的最短路径的长度。本例中要求的是 。,在,阶段1,：可以取 中任意一个，对应的有,在,阶段2,：可以取 中任意一个，对应的有,11/14/2024,15,1 最短路径问题 以 表示在,1 最短路径问题,从 出发到终点,E,最短路径为“”，决策变量 ；,在,阶段3,：可以取 中任意一个，对应的有,从 出发到终点,E,最短路径为“”，决策变量 ；,11/14/2024,16,1 最短路径问题从 出发到终点E最短路径为“,1 最短路径问题,从 出发到终点,E,最短路径为“”，决策变量 ；,从 出发到终点,E,最短路径为“”，决策变量 ；,从 出发到终点,E,最短路径为“”，决策变量 或 ；,最后，,在阶段4,：只可以取,S,，于是,11/14/2024,17,1 最短路径问题从 出发到终点E最短路径为“,1 最短路径问题,因此，由起点,S,到终点,E,的最短路径为,最短路径长度为21单位长度。,11/14/2024,18,1 最短路径问题因此，由起点S到终点E的最短路径为最短路径长,1 最短路径问题,由上述计算过程可知，对有,n,个阶段的最短路径问题，可以逐段逆向地求出各点到终点的最短路径，且在求解的每一步都利用阶段,k,和阶段,k-1,间的递推关系：,此关系被称为,求最短路径的动态规划基本方程,。求解最短路径问题的过程，本质上是解上述基本方程的过程。,11/14/2024,19,1 最短路径问题由上述计算过程可知，对有n个阶段的最短路径问,2 贝尔曼最优化原理,11/14/2024,20,2 贝尔曼最优化原理 8/7/202320,2 贝尔曼最优化原理,将求解最短路径问题的思路推广到一般多阶段决策问题时，可以表述成：,贝尔曼最优化原理：一个过程的最优策略具有这样的性质，即无论其初始状态和初始决策如何，今后的诸决策，对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优策略。,这个原理是动态规划的理论基础。,11/14/2024,21,2 贝尔曼最优化原理 将求解最短路径问题的思路推广到一般多阶,2 贝尔曼最优化原理,应用动态规划方法解决一般多阶段决策问题时，其求解过程如下：,（1）把实际问题适当地划分成,k,个阶段，阶段变量为 ；,（2）在每个阶段,k,，确定状态变量 为及此阶段可能的状态集合 ；,（3）确定决策变量 及每个阶段,k,的允许决策集合 ；,（4）列出递推关系即动态规划基本方程并计算：,11/14/2024,22,2 贝尔曼最优化原理应用动态规划方法解决一般多阶段决策问题时,2 贝尔曼最优化原理,【例2】（石油输送管道铺设优选问题）,某石油公司计划从,A,地到,E,地铺设一条石油输送管道，为此在,A,地与,E,地之间必须建立三个油泵加压站，如图2所示，其中 分别为必须建站的地区，而 分别为可供选择的各站点，各点连线上的数字表示相邻站点间铺设输送管道所需费用.问：如何铺设石油输送管道，能使总费用最少？,11/14/2024,23,2 贝尔曼最优化原理【例2】（石油输送管道铺设优选问题）某石,2 贝尔曼最优化原理,(a),(b),11/14/2024,24,2 贝尔曼最优化原理(a)(b)8/7/202324,2 贝尔曼最优化原理,解 划分成4个阶段：阶段变量依次为4，3，2，1，如图2所示.设阶段,k,的状态变量为 。,在阶段1：,在阶段2：可以取 中任意一个，对应的有,11/14/2024,25,2 贝尔曼最优化原理解 划分成4个阶段：,2 贝尔曼最优化原理,从 出发到终点,E,最短路径为“”，决策变量 ；,从 出发到终点,E,最短路径为“”，决策变量 ；,从 出发到终点,E,最短路径为“”，决策变量 ；,11/14/2024,26,2 贝尔曼最优化原理从 出发到终点E最短路径为“,2 贝尔曼最优化原理,在阶段3：可以取 中任意一个，于是,11/14/2024,27,2 贝尔曼最优化原理在阶段3：可以取,2 贝尔曼最优化原理,从 出发到终点,E,最短路径为“”或,决策变量 或 ；,从 出发到终点,E,最短路径为“”，决策变量 ；,从 出发到终点,E,最短路径为“”或,决策变量 或 ；,在阶段4：,11/14/2024,28,2 贝尔曼最优化原理从 出发到终点E最短路径为“,2 贝尔曼最优化原理,因此，由起点,A,到终点,E,的费用最少路径有3条：,此3条路径对应的总费用均为11单位金额。,11/14/2024,29,2 贝尔曼最优化原理因此，由起点A到终点E的费用最少路径有3,2 贝尔曼最优化原理,动态规划为我们提供了一种优秀的决策思想：,战略上追求全局优化，战术上稳扎稳打、步步为营。这深刻地揭示了局部与全局的统一关系。,动态规划在实际中得到广泛应用，如可应用于背包问题、资源分配问题、生产与存储问题、设备更新问题等。,需要指出的是：动态规划是一种求解思路，注重决策过程，而不是一种算法，不同的问题模型各异。,11/14/2024,30,2 贝尔曼最优化原理动态规划为我们提供了一种优秀的决策思想：,3 WinQSB软件应用,11/14/2024,31,3 WinQSB软件应用8/7/202331,本节结合最短路径问题、背包问题介绍WinQSB软件的应用，其他问题的求解可参考本章参考文献.,求解动态规划问题，需要调用WinQSB软件中的子程序“Dynamic Programming”.方法：点击“开始”“程序”“WinQSB”“Dynamic Programming”,屏幕显示如图3.3所示.,该程序有3个子模块：最短路问题（Stagecoach Problem）,背包问题（Knapsack Problem）,生产与存储问题（Production and Inventory Scheduling）.,3 WinQSB软件应用,11/14/2024,32,本节结合最短路径问题、背包问题介绍WinQSB软件的应用，其,3 WinQSB软件应用,11/14/2024,33,3 WinQSB软件应用8/7/202333,1.最短路问题,【,例3,】,用WinQSB软件求解例1.,解,（1）调用WinQSB软件中的子程序“Dynamic Programming”，,建立新问题.在图3.3中选择第一项，输入标题和站点数.,（2）输入数据.按照图3.1从左到右将相邻站点间的距离输入表,3.1中，其中,表示图3.1中从左到右的第,k,个站点，,k=1,2,9,表3.1,3 WinQSB软件应用,11/14/2024,34,1.最短路问题表示图3.1中从左到右的第k 个站点，k=1,（3）求解.点击菜单栏“Solve and Analyze”“Solve the Problem”,得到图3.4.再点击“Solve”键，得到计算结果，见表3