动态规划方法.ppt

《动态规划方法.ppt》由会员分享，可在线阅读，更多相关《动态规划方法.ppt（39页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、动态规划方法动态规划方法2022-9-41现在学习的是第1页，共39页 动态规划动态规划（Dynamic ProgrammingDynamic Programming）同前面介）同前面介绍过的线性规划方法不同，它不是一种算法，而是考察问绍过的线性规划方法不同，它不是一种算法，而是考察问题的一种途径。动态规划是一种求解多阶段决策问题的系题的一种途径。动态规划是一种求解多阶段决策问题的系统技术。由于动态规划不是一种特定的算法，因而它不像统技术。由于动态规划不是一种特定的算法，因而它不像线性规划那样有一个标准的数学表达式和明确定义的一组线性规划那样有一个标准的数学表达式和明确定义的一组规则，动态规划

2、必须对具体问题进行具体的分析处理。动规则，动态规划必须对具体问题进行具体的分析处理。动态规划在自然科学和社会科学等各个领域都有着广泛的应态规划在自然科学和社会科学等各个领域都有着广泛的应用，并且获得了显著的效果。用，并且获得了显著的效果。2022-9-42现在学习的是第2页，共39页1 1 最短路径问题最短路径问题 2 2 贝尔曼最优化原理贝尔曼最优化原理 3 3 WinQSBinQSB软件应用软件应用动态规划动态规划2022-9-43现在学习的是第3页，共39页 动态规划是解决多阶段决策问题动态规划是解决多阶段决策问题的一种方法的一种方法. 1951. 1951年，美国数学年，美国数学家贝尔

3、曼（家贝尔曼（R.BellmanR.Bellman，1920192019841984）研究了一类多阶段决策）研究了一类多阶段决策问题的特征，提出了解决这类问问题的特征，提出了解决这类问题的基本原理。在研究、解决了题的基本原理。在研究、解决了某些实际问题的基础上，他于某些实际问题的基础上，他于19571957年出版了年出版了动态规划动态规划这一这一名著。本章将简要介绍动态规划名著。本章将简要介绍动态规划的思想方法及其应用。的思想方法及其应用。2022-9-44现在学习的是第4页，共39页 动态规划解决问题的基本思路是：把整体比较复杂的动态规划解决问题的基本思路是：把整体比较复杂的大问题划分成一系

4、列较易于解决的小问题，通过逐个求解大问题划分成一系列较易于解决的小问题，通过逐个求解，最终取得整体最优解。这种，最终取得整体最优解。这种“分而治之，逐步调整分而治之，逐步调整”的的方法，在一些比较难以解决的复杂问题中已经显示出优越方法，在一些比较难以解决的复杂问题中已经显示出优越性。性。2022-9-45现在学习的是第5页，共39页 所谓多阶段决策过程是指这样一类活所谓多阶段决策过程是指这样一类活动过程：一个决策过程可以分为若干个相动过程：一个决策过程可以分为若干个相互联系的阶段，每个阶段都需要作一定的互联系的阶段，每个阶段都需要作一定的决策，但是每个阶段最优决策的选择不能决策，但是每个阶段最

5、优决策的选择不能只是孤立地考虑本阶段所取得的效果如何只是孤立地考虑本阶段所取得的效果如何，必须把整个过程中的各个阶段联系起来，必须把整个过程中的各个阶段联系起来考虑，要求所选择的各个阶段决策的集合考虑，要求所选择的各个阶段决策的集合策略，能使整个过程的总效果达到最策略，能使整个过程的总效果达到最优。优。2022-9-46现在学习的是第6页，共39页1 最短路径问题最短路径问题 2022-9-47现在学习的是第7页，共39页1 最短路径问题最短路径问题 【例例1 1】设在设在E E城的某公司要从城的某公司要从S S城运送一批城运送一批货物，两城之间有公路相连（见图货物，两城之间有公路相连（见图

6、1(a)1(a)），），其中其中 是可以供选择的途经站点，各点连线上的数是可以供选择的途经站点，各点连线上的数字表示相邻站点间的距离。现在的问题是选择字表示相邻站点间的距离。现在的问题是选择一条由一条由S S到到E E的路径，使得所经过的路径最短的路径，使得所经过的路径最短。(1,2,3),(1,2),(1,2)ijlA iBjC l2022-9-48现在学习的是第8页，共39页1 最短路径问题最短路径问题(a)(b)2022-9-49现在学习的是第9页，共39页1 最短路径问题最短路径问题 分析：如果用枚举法，将有分析：如果用枚举法，将有1212条不同的路条不同的路径，每条路径对应一个由径，

7、每条路径对应一个由S S到到E E的路径距离的路径距离，其中最小值所对应的路径即为最短路径。，其中最小值所对应的路径即为最短路径。本问题的最短路径有本问题的最短路径有3 3条，路程均为条，路程均为2121个单个单位：位： 第1条： 第2条： 第3条： 111SABCE311SABCE321SABCE2022-9-410现在学习的是第10页，共39页1 最短路径问题最短路径问题 当段数很多时，枚举法的计算量将极其庞大。当段数很多时，枚举法的计算量将极其庞大。 现在换个思路，寻找由现在换个思路，寻找由S S到到E E的最短路径。先的最短路径。先把最短路径问题所考虑的过程分为把最短路径问题所考虑的过

8、程分为4 4个阶段：个阶段： 由S到 为第1阶段；(1,2,3)iA i 由 到 为第2阶段； 由 到E为第4阶段。 由 到 为第3阶段；(1,2,3)iA i (1,2)jBj (1,2)jBj (1,2)lC l (1,2)lC l 2022-9-411现在学习的是第11页，共39页1 最短路径问题最短路径问题 我们称由某点到终点的阶段数我们称由某点到终点的阶段数k k为为阶段变量阶段变量，如由如由 到到E E的阶段数为的阶段数为1 1（这时记由（这时记由C C到到E E的阶段数为的阶段数为1 1，它与第，它与第1 1阶段是不同的概念）阶段是不同的概念），由，由 到到E E的阶段数为的阶段

9、数为2 2（这时记由（这时记由B B到到E E的阶段数为的阶段数为2 2），等等。可见阶段变量的），等等。可见阶段变量的取值正好与实际进行的阶段相反（图（取值正好与实际进行的阶段相反（图（b b）。(1,2)lC l (1,2)jBj (b)2022-9-412现在学习的是第12页，共39页1 最短路径问题最短路径问题 在任一阶段开始时所处的位置称为在任一阶段开始时所处的位置称为状态变量状态变量，在阶段，在阶段k k的状态变量记为的状态变量记为 ，例如，例如 为为阶段阶段3 3的状态变量，可以取为的状态变量，可以取为 中中任意一个。任意一个。 当某一个状态给定后，需要做出决策以确定下一步的状态

10、，描述决策的变量称为决策变量，在阶段k的决策变量记为 。例如在阶段2的状态取 时的决策变量记为 ， 可取为 。若 ，则表示由 到 ，从而决定了下一步的状态是 。kS3S123,A A AkX22SB22()XB22()XB12,C C222()XBC2B2C2C2022-9-413现在学习的是第13页，共39页1 最短路径问题最短路径问题 为了寻找由起点为了寻找由起点S S到到E E终点的最短路径，我终点的最短路径，我们考察前面用枚举法找到的第们考察前面用枚举法找到的第1 1条最短路径条最短路径： 111SABCE 容易看出：子路径“ ” 也应是从 出发到终点E的所有路径中最短的一条。111A

11、BCE1A 这个现象启发我们从阶段1开始，逐段逆向地求出各点到终点E的最短路径，最后求得由起点S到终点E的最短路径，这就是动态规划的基本思想。2022-9-414现在学习的是第14页，共39页1 最短路径问题最短路径问题 以以 表示在阶段表示在阶段k k的状态变量为的状态变量为 、决策变量为、决策变量为 时点时点 与与 间的距离；记间的距离；记 为在阶段为在阶段k k由点由点 到到终点终点E E的最短路径的长度。本例中要求的是的最短路径的长度。本例中要求的是 。()kkfS 在阶段1： 可以取 中任意一个，对应的有 在阶段2： 可以取 中任意一个，对应的有(,()kkkd SXSkS()kkX

12、SkS()kkXSkS4( )fS1S12,C C1112()5,()8f Cf C2S12,B B1111211212(,)()65()minmin11(,)()58d B Cf CfBd B Cf C2111222212(,)()9 5()minmin14(,)()8 8d B Cf Cf Bd B Cf C2022-9-415现在学习的是第15页，共39页1 最短路径问题最短路径问题 从从 出发到终点出发到终点E E最短路径为最短路径为“ ”，决策变量，决策变量 ；11BCE1B 在阶段3： 可以取 中任意一个，对应的有*211()XBC 从 出发到终点E最短路径为“ ”，决策变量 ；2

13、B21BCE*221()XBC3S123,A A A1121311222(,)()6 11()minmin17;(,)()5 14d A BfBfAd A BfB2121322222(,)()8 11()minmin19;(,)()6 14d A BfBfAd A BfB3121333222(,)()7 11()minmin18(,)()4 14d A BfBfAd A BfB2022-9-416现在学习的是第16页，共39页1 最短路径问题最短路径问题 从从 出发到终点出发到终点E E最短路径为最短路径为“ ”，决策变量，决策变量 ； 1A111ABCE 从 出发到终点E最短路径为“ ”，决

14、策变量 ； 从 出发到终点E最短路径为“ ”，决策变量 或 ； 最后，在阶段4： 只可以取S，于是 *311()XAB2A211ABCE*321()XAB3A311ABCE*331()XAB2B4S1314232333( ,)()4 17( )min( ,)()min 3 1921( ,)()3 18d S AfAfSd S AfAd S AfA2022-9-417现在学习的是第17页，共39页1 最短路径问题最短路径问题 因此，由起点因此，由起点S S到终点到终点E E的最短路径为的最短路径为111311321.SABCESABCESABCE； 最短路径长度为21单位长度。2022-9-41

15、8现在学习的是第18页，共39页1 最短路径问题最短路径问题 由上述计算过程可知，对有由上述计算过程可知，对有n n个阶段的最短个阶段的最短路径问题，可以逐段逆向地求出各点到终路径问题，可以逐段逆向地求出各点到终点的最短路径，且在求解的每一步都利用点的最短路径，且在求解的每一步都利用阶段阶段k k和阶段和阶段k-1k-1间的递推关系：间的递推关系：-1()11111111()min (,()(),2,3,., ,()min (,()(,().kkkkkkkkXSfSd SX SfX Sknf Sd S X Sd S X S 此关系被称为求最短路径的动态规划基本方程。求解最短路径问题的过程，本质

16、上是解上述基本方程的过程。2022-9-419现在学习的是第19页，共39页2 贝尔曼最优化原理贝尔曼最优化原理 2022-9-420现在学习的是第20页，共39页2 贝尔曼最优化原理贝尔曼最优化原理 将求解最短路径问题的思路推广到一般多将求解最短路径问题的思路推广到一般多阶段决策问题时，可以表述成：阶段决策问题时，可以表述成： 贝尔曼最优化原理：一个过程的最优策略贝尔曼最优化原理：一个过程的最优策略具有这样的性质，即无论其初始状态和初具有这样的性质，即无论其初始状态和初始决策如何，今后的诸决策，对以第一个始决策如何，今后的诸决策，对以第一个决策所形成的状态作为初始状态的过程而决策所形成的状态

17、作为初始状态的过程而言，必须构成最优策略。言，必须构成最优策略。 这个原理是动态规划的理论基础。这个原理是动态规划的理论基础。2022-9-421现在学习的是第21页，共39页2 贝尔曼最优化原理贝尔曼最优化原理 应用动态规划方法解决一般多阶段决策问题时，其求解过应用动态规划方法解决一般多阶段决策问题时，其求解过程如下：程如下： （1 1）把实际问题适当地划分成）把实际问题适当地划分成k k个阶段，阶段变量为个阶段，阶段变量为 ； （2 2）在每个阶段）在每个阶段k k，确定状态变量，确定状态变量 为及此阶段可能的为及此阶段可能的状态集合状态集合 ； （3 3）确定决策变量）确定决策变量 及每

18、个阶段及每个阶段k k的允许决策集合的允许决策集合 ； （4 4）列出递推关系即动态规划基本方程并计算：）列出递推关系即动态规划基本方程并计算： (1,2,., )k knkSkS()kkXS()()kkkkx SXS-1()11111111()min (,()(),2,3,., ,()min (,()(,().kkkkkkkkxSfSd SX SfX Sknf Sd S X Sd S X S2022-9-422现在学习的是第22页，共39页2 贝尔曼最优化原理贝尔曼最优化原理 【例例2 2】（石油输送管道铺设优选问题）（石油输送管道铺设优选问题）某石某石油公司计划从油公司计划从A A地到地到

19、E E地铺设一条石油输送管地铺设一条石油输送管道，为此在道，为此在A A地与地与E E地之间必须建立三个油泵地之间必须建立三个油泵加压站，如图加压站，如图2 2所示，所示， 其中其中 分别为必分别为必须建站的地区，而须建站的地区，而 分别为可供选择的各站点，各点连线上的数字分别为可供选择的各站点，各点连线上的数字表示相邻站点间铺设输送管道所需费用表示相邻站点间铺设输送管道所需费用. . 问：问：如何铺设石油输送管道，能使总费用最少？如何铺设石油输送管道，能使总费用最少？ ,B C D123123,B B B C C C12,D D2022-9-423现在学习的是第23页，共39页2 贝尔曼最优

20、化原理贝尔曼最优化原理(a)(b)2022-9-424现在学习的是第24页，共39页2 贝尔曼最优化原理贝尔曼最优化原理 解解 划分成划分成4 4个阶段：个阶段： 阶段变量依次为阶段变量依次为4 4，3 3，2 2，1 1，如图，如图2 2所示所示. . 设设阶段阶段k k的状态变量为的状态变量为 。;.AB BC CD DE,1,2,3,4kSk 在阶段1： 1112()3,()4f Df D 在阶段2： 可以取 中任意一个，对应的有 2S123,C C C1111211212(,)()1 3()minmin4(,)()44d C Df Df Cd C Df D2111222212(,)()

21、63()minmin7(,)()34d C Df Df Cd C Df D3111233212(,)()33()minmin6(,)()34d C Df Df Cd C Df D2022-9-425现在学习的是第25页，共39页2 贝尔曼最优化原理贝尔曼最优化原理 从从 出发到终点出发到终点E E最短路径为最短路径为“ ”，决策变量，决策变量 ； 从 出发到终点E最短路径为“ ”，决策变量 ； 从 出发到终点E最短路径为“ ”，决策变量 ； 1C11CDE*211()XCD2C22CDE*222()XCD3C31CDE*231()XCD2022-9-426现在学习的是第26页，共39页2 贝尔

22、曼最优化原理贝尔曼最优化原理 在阶段在阶段3 3： 可以取可以取 中任意一个中任意一个 ，于是，于是 3S123,B B B1121122231132321212222322323(,)()74(,)()()minmin11;47(,)()66(,)()34(,)()()minmin7;27(,)()46d B Cf Cd B Cf CfBd B Cf Cd B Cf Cd B Cf CfBd B Cf C31213222333323(,)()44(,)()()minmin8.17(,)()56d B Cf Cd B Cf CfBd B Cf C2022-9-427现在学习的是第27页，共39

23、页2 贝尔曼最优化原理贝尔曼最优化原理 从从 出发到终点出发到终点E E最短路径为最短路径为“ ”或或 决策变量决策变量 或或 ； 1B111BCDE122BCDE*311()XBC2C 从 出发到终点E最短路径为“ ”，决策变量 ； 2B211BCDE*321()XBC3B 从 出发到终点E最短路径为“ ”或 决策变量 或 ； 311BCDE322BCDE*331()XBC2C 在阶段4：1314232333( ,)()2 11( )min( ,)()min4711( ,)()38d A Bf BfAd A Bf Bd A Bf B2022-9-428现在学习的是第28页，共39页2 贝尔曼

24、最优化原理贝尔曼最优化原理 因此，由起点因此，由起点A A到终点到终点E E的费用最少路径有的费用最少路径有3 3条：条：211311322.；ABCDEABCDEABCDE 此3条路径对应的总费用均为11单位金额。2022-9-429现在学习的是第29页，共39页2 贝尔曼最优化原理贝尔曼最优化原理 动态规划为我们提供了一种优秀的决策思动态规划为我们提供了一种优秀的决策思想：想：战略上追求全局优化，战术上稳扎稳战略上追求全局优化，战术上稳扎稳打、步步为营。这深刻地揭示了局部与全打、步步为营。这深刻地揭示了局部与全局的统一关系。局的统一关系。动态规划在实际中得到广动态规划在实际中得到广泛应用，

25、如可应用于背包问题、资源分配泛应用，如可应用于背包问题、资源分配问题、生产与存储问题、设备更新问题等问题、生产与存储问题、设备更新问题等。 需要指出的是：动态规划是一种求解思路需要指出的是：动态规划是一种求解思路，注重决策过程，而不是一种算法，不同，注重决策过程，而不是一种算法，不同的问题模型各异。的问题模型各异。2022-9-430现在学习的是第30页，共39页3 WinQSB软件应用软件应用2022-9-431现在学习的是第31页，共39页 本节结合最短路径问题、背包问题介绍WinQSB软件的应用，其他问题的求解可参考本章参考文献. 求解动态规划问题，需要调用WinQSB软件中的子程序“D

26、ynamic Programming”. 方法：点击“开始”“程序”“WinQSB”“Dynamic Programming”,屏幕显示如图3.3所示. 该程序有3个子模块：最短路问题（Stagecoach Problem）,背包问题（Knapsack Problem）,生产与存储问题（Production and Inventory Scheduling）. 3 WinQSB软件应用软件应用2022-9-432现在学习的是第32页，共39页 3 WinQSB软件应用软件应用2022-9-433现在学习的是第33页，共39页1.最短路问题最短路问题【例3】用WinQSB软件求解例1. 解解（1

27、）调用WinQSB软件中的子程序“Dynamic Programming”，建立新问题. 在图3.3中选择第一项，输入标题和站点数. （2）输入数据. 按照图3.1从左到右将相邻站点间的距离输入表3.1中，其中 Nodek表示图3.1中从左到右的第k 个站点，k=1,2,9表3.1 3 WinQSB软件应用软件应用2022-9-434现在学习的是第34页，共39页（3 3）求解）求解. .点击菜单栏点击菜单栏“Solve and Analyze” “Solve the Solve and Analyze” “Solve the Problem”,Problem”,得到图得到图3.4. 3.4.

28、 再点击再点击“Solve”Solve”键，得到计算结果，见键，得到计算结果，见表表3.2. 3.2. 可见由起点到终点的最短路径为可见由起点到终点的最短路径为 111SABCE 3 WinQSB软件应用软件应用2022-9-435现在学习的是第35页，共39页表表 2 2 3 WinQSB软件应用软件应用2022-9-436现在学习的是第36页，共39页 2. 2. 背包问题背包问题 背包问题的一般提法是：设有一位旅行者携带背包去登山，已背包问题的一般提法是：设有一位旅行者携带背包去登山，已知他所能承受的背包质量为知他所能承受的背包质量为a a （单位：（单位：kg），），iiaixiic

29、x(ici1,2,in种物品可供他选择装入背包，其中第种物品可供他选择装入背包，其中第 种物品的重量为种物品的重量为（单位：（单位：kg），其价值（可以是表明该物品对登山的重要性，其价值（可以是表明该物品对登山的重要性的函数的函数 为第为第种物品单位种物品单位问：旅行者应如何选择携带各物品的件数，以使总价值最大？问：旅行者应如何选择携带各物品的件数，以使总价值最大？ 背包问题等同于车、船、飞机、潜艇、人造卫星等工具的最背包问题等同于车、船、飞机、潜艇、人造卫星等工具的最优装载问题，有广泛的实际意义优装载问题，有广泛的实际意义. . 现有现有n 的数量指标）是携带数量的数量指标）是携带数量数量的

30、价值，数量的价值， ). 3 WinQSB软件应用软件应用2022-9-437现在学习的是第37页，共39页 【例例4 4】已知已知1T1T的集装箱最大载重量为的集装箱最大载重量为800kg.800kg.现有现有5 5种物品各种物品各1010件件可供选择装箱，其中单位物品重量、价值见表可供选择装箱，其中单位物品重量、价值见表3. 3. 求价值最大的装求价值最大的装载方案载方案. . 表表3 3解解 (1)调用调用WinQSB软件中子程序软件中子程序“Dynamic Programming”建立新问题：在图建立新问题：在图3.3中选择第二项，输入标题和物品品种数中选择第二项，输入标题和物品品种数5，见图，见图5. 3 WinQSB软件应用软件应用2022-9-438现在学习的是第38页，共39页（2）按表）按表4形式输入数据：第形式输入数据：第1列为物品名称，第列为物品名称，第2列为物品列为物品限量及集装箱最大载重量，限量及集装箱最大载重量，第第3列为单位物品重量，第列为单位物品重量，第4列列为物品价值函数为物品价值函数. 注：物品的数量仍用a,b,c,d,e表示. 3 WinQSB软件应用软件应用2022-9-439现在学习的是第39页，共39页