1、动态规划动态规划（Dynamic Programming）同前面介绍过的）同前面介绍过的线性规划方法不同，它不是一种算法，而是考察问题线性规划方法不同，它不是一种算法，而是考察问题的一种途径。动态规划是一种求解多阶段决策问题的的一种途径。动态规划是一种求解多阶段决策问题的系统技术。由于动态规划不是一种特定的算法，因而系统技术。由于动态规划不是一种特定的算法，因而它不像线性规划那样有一个标准的数学表达式和明确它不像线性规划那样有一个标准的数学表达式和明确定义的一组规则，动态规划必须对具体问题进行具体定义的一组规则，动态规划必须对具体问题进行具体的分析处理。动态规划在工程技术、经济管理等各个的分析
2、处理。动态规划在工程技术、经济管理等各个领域都有着广泛的应用，并且获得了显著的效果。领域都有着广泛的应用，并且获得了显著的效果。3.1 3.1 最短路径问题最短路径问题 3.2 3.2 贝尔曼最优化原理贝尔曼最优化原理 3.3 3.3 WinQSBinQSB软件应用软件应用第三章第三章 动态规划动态规划动态规划是解决多阶段决策问题动态规划是解决多阶段决策问题的一种方法的一种方法.1951年，美国数学家年，美国数学家贝尔曼（贝尔曼（R.Bellman，19201984）研究了一类多阶段决策问题的特研究了一类多阶段决策问题的特征，提出了解决这类问题的基本征，提出了解决这类问题的基本原理。在研究、解
3、决了某些实际原理。在研究、解决了某些实际问题的基础上，他于问题的基础上，他于1957年出版年出版了了动态规划动态规划这一名著。本章这一名著。本章将简要介绍动态规划的思想方法将简要介绍动态规划的思想方法及其应用。及其应用。动态规划解决问题的基本思路是：把整体比较动态规划解决问题的基本思路是：把整体比较复杂的大问题划分成一系列较易于解决的小问复杂的大问题划分成一系列较易于解决的小问题，通过逐个求解，最终取得整体最优解。这题，通过逐个求解，最终取得整体最优解。这种种“分而治之，逐步调整分而治之，逐步调整”的方法，在一些比的方法，在一些比较难以解决的复杂问题中已经显示出优越性。较难以解决的复杂问题中已
4、经显示出优越性。经过半个世纪的发展，动态规划解决问题的方经过半个世纪的发展，动态规划解决问题的方法已经广泛应用于经济、管理、军事、生物、法已经广泛应用于经济、管理、军事、生物、工程等诸多领域，并取得了很好效果。工程等诸多领域，并取得了很好效果。所谓多阶段决策过程是指这样一类活动过程：所谓多阶段决策过程是指这样一类活动过程：一个决策过程可以分为若干个相互联系的阶段，一个决策过程可以分为若干个相互联系的阶段，每个阶段都需要作一定的决策，但是每个阶段每个阶段都需要作一定的决策，但是每个阶段最优决策的选择不能只是孤立地考虑本阶段所最优决策的选择不能只是孤立地考虑本阶段所取得的效果如何，必须把整个过程中
5、的各个阶取得的效果如何，必须把整个过程中的各个阶段联系起来考虑，要求所选择的各个阶段决策段联系起来考虑，要求所选择的各个阶段决策的集合的集合策略，能使整个过程的总效果达到策略，能使整个过程的总效果达到最优。最优。3.1 最短路径问题最短路径问题 3.1 最短路径问题最短路径问题【例例3.1】设在设在E城的某公司要从城的某公司要从S城运送一批城运送一批货物，两城之间有公路相连（见图货物，两城之间有公路相连（见图3.1(a)），），其中其中 是可以供选择的是可以供选择的途经站点，各点连线上的数字表示相邻站点间途经站点，各点连线上的数字表示相邻站点间的距离。现在的问题是选择一条由的距离。现在的问题是
6、选择一条由S到到E的路的路径，使得所经过的路径最短。径，使得所经过的路径最短。(1,2,3),(1,2),(1,2)ijlA iBjC l3.1 最短路径问题最短路径问题(a)(b)3.1 最短路径问题最短路径问题分析：如果用枚举法，将有分析：如果用枚举法，将有12条不同的路径，条不同的路径，每条路径对应一个由到的路径距离，其中最小每条路径对应一个由到的路径距离，其中最小值所对应的路径即为最短路径。本问题的最短值所对应的路径即为最短路径。本问题的最短路径有路径有3条，路程均为条，路程均为21个单位：个单位：第第1条：条：第第2条：条：第第3条：条：111SABCE311SABCE321SABC
7、E3.1 最短路径问题最短路径问题当段数很多时，枚举法的计算量将极其庞大。当段数很多时，枚举法的计算量将极其庞大。现在换个思路，寻找由现在换个思路，寻找由S到到E的最短路径。先的最短路径。先把最短路径问题所考虑的过程分为把最短路径问题所考虑的过程分为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 3.1 最短路径问题最短路径问题我们称由某点到终点的阶段数我们称由某点到终点的阶
8、段数k为阶段变量，为阶段变量，如由如由 到到E的阶段数为的阶段数为1（这时记由（这时记由C到到E的阶段数为的阶段数为1，它与第，它与第1阶段是不同的概念），阶段是不同的概念），到到E的阶段数为的阶段数为2（这时记由（这时记由B到到E的阶的阶段数为段数为2），等等。可见阶段变量的取值正好），等等。可见阶段变量的取值正好与实际进行的阶段相反（图（与实际进行的阶段相反（图（b）。）。(1,2)lC l(1,2)jBj 3.1 最短路径问题最短路径问题在任一阶段开始时所处的位置称为状态变量，在任一阶段开始时所处的位置称为状态变量，在阶段在阶段k的状态变量记为的状态变量记为 ，例如，例如 为阶段为阶段3
9、的状态变量，可以取为的状态变量，可以取为 中任意一个。中任意一个。kS3S123,A A A当某一个状态给定后，需要做出决策以确定下当某一个状态给定后，需要做出决策以确定下一步的状态，描述决策的变量称为决策变量，一步的状态，描述决策的变量称为决策变量，在阶段在阶段k的决策变量记为的决策变量记为 。例如在阶段。例如在阶段2的的状态取状态取 时的决策变量记为时的决策变量记为 ，可取为可取为 。若。若 ，则表示由，则表示由 到到 ，从而决定了下一步的状态是从而决定了下一步的状态是 。kX22SB22()XB22()XB12,C C222()XBC2B2C2C3.1 最短路径问题最短路径问题为了寻找由
10、起点为了寻找由起点S到到E终点的最短路径，我们终点的最短路径，我们考察前面用枚举法找到的第考察前面用枚举法找到的第1条最短路径：条最短路径：111SABCE容易看出：子路径容易看出：子路径“”也应也应是从是从 出发到终点出发到终点E的所有路径中最短的一条。的所有路径中最短的一条。111ABCE1A这个现象启发我们从阶段这个现象启发我们从阶段1开始，逐段逆向地开始，逐段逆向地求出各点到终点求出各点到终点E的最短路径，最后求得由起的最短路径，最后求得由起点点S到终点到终点E的最短路径，这就是动态规划的基的最短路径，这就是动态规划的基本思想。本思想。3.1 最短路径问题最短路径问题 以以 表示在阶段
11、表示在阶段k的状态变量为的状态变量为 、决策变、决策变量为量为 时点时点 与与 间的距离；记间的距离；记 为在为在阶段阶段k由点由点 到终点到终点E的最短路径的长度。本例中要的最短路径的长度。本例中要求的是求的是 。(,()kkkd SXSkS()kkXSkS()kkXS()kkfSkS4()fS在阶段在阶段1：可以取可以取 中任意一个，对应的有中任意一个，对应的有1S12,C C1112()5,()8f Cf C在阶段在阶段2：可以取可以取 中任意一个，对应的有中任意一个，对应的有2S12,B B1111211212(,)()65()minmin11(,)()58d B Cf CfBd B
12、Cf C2111222212(,)()9 5()minmin14(,)()8 8d B Cf Cf Bd B Cf C3.1 最短路径问题最短路径问题从从 出发到终点出发到终点E最短路径为最短路径为“”，决策变量决策变量 ；11BCE*211()XBC1B从从 出发到终点出发到终点E最短路径为最短路径为“”，决策变量决策变量 ；2B21BCE*221()XBC在阶段在阶段3：可以取可以取 中任意一个，对应中任意一个，对应的有的有3S123,A A A1121311222(,)()6 11()minmin17;(,)()5 14d A BfBfAd A BfB2121322222(,)()8 1
13、1()minmin19;(,)()6 14d A BfBfAd A BfB3121333222(,)()7 11()minmin18(,)()4 14d A BfBfAd A BfB3.1 最短路径问题最短路径问题从从 出发到终点出发到终点E最短路径为最短路径为“”，决策变量决策变量 ；1A111ABCE*311()XAB从从 出发到终点出发到终点E最短路径为最短路径为“”，决策变量决策变量 ；2A211ABCE*321()XAB从从 出发到终点出发到终点E最短路径为最短路径为“”，决策变量决策变量 或或 ；3A311ABCE*331()XAB2B最后，在阶段最后，在阶段4：只可以取只可以取S
14、，于是，于是 4S1314232333(,)()4 17()min(,)()min 3 1921(,)()3 18d S AfAfSd S AfAd S AfA3.1 最短路径问题最短路径问题因此，由起点因此，由起点S到终点到终点E的最短路径为的最短路径为111311321.SABCESABCESABCE；最短路径长度为最短路径长度为21单位长度。单位长度。3.1 最短路径问题最短路径问题由上述计算过程可知，对有由上述计算过程可知，对有n个阶段的最短路个阶段的最短路径问题，可以逐段逆向地求出各点到终点的最径问题，可以逐段逆向地求出各点到终点的最短路径，且在求解的每一步都利用阶段短路径，且在求解
15、的每一步都利用阶段k和阶和阶段段k-1间的递推关系：间的递推关系：-1()11111111()min(,()(),2,3,.,()min(,()(,().kkkkkkkkXSfSd SX SfX Sknf Sd S X Sd S X S此关系被称为求最短路径的动态规划基本方程。此关系被称为求最短路径的动态规划基本方程。求解最短路径问题的过程，本质上是解上述基求解最短路径问题的过程，本质上是解上述基本方程的过程。本方程的过程。3.1 最短路径问题最短路径问题本节学习要点本节学习要点1.通过实例，了解什么是动态规划，了解动态规划在管理中的几类应用例子2.动态规划数学模型的组成及其特征3.掌握求最短
16、路径的动态规划基本方程3.2 贝尔曼最优化原理贝尔曼最优化原理 3.2 贝尔曼最优化原理贝尔曼最优化原理 将求解最短路径问题的思路推广到一般多阶段将求解最短路径问题的思路推广到一般多阶段决策问题时，可以表述成：决策问题时，可以表述成：贝尔曼最优化原理：一个过程的最优策略具有贝尔曼最优化原理：一个过程的最优策略具有这样的性质，即无论其初始状态和初始决策如这样的性质，即无论其初始状态和初始决策如何，今后的诸决策，对以第一个决策所形成的何，今后的诸决策，对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优状态作为初始状态的过程而言，必须构成最优策略。策略。这个原理是动态规划的理论基础。这个
17、原理是动态规划的理论基础。3.2 贝尔曼最优化原理贝尔曼最优化原理应用动态规划方法解决一般多阶段决策问题时，其求应用动态规划方法解决一般多阶段决策问题时，其求解过程如下：解过程如下：（1）把实际问题适当地划分成）把实际问题适当地划分成k个阶段，阶段变量个阶段，阶段变量为为 ；（2）在每个阶段）在每个阶段k，确定状态变量，确定状态变量 为及此阶段可为及此阶段可能的状态集合能的状态集合 ；（3）确定决策变量）确定决策变量 及每个阶段及每个阶段k的允许决策集的允许决策集合合 ；（4）列出递推关系即动态规划基本方程并计算：）列出递推关系即动态规划基本方程并计算：(1,2,.,)k knkSkS()kk
18、XS()()kkkkx SXS-1()11111111()min(,()(),2,3,.,()min(,()(,().kkkkkkkkkkxSfSd SXSfXSknf Sd S X Sd S X S3.2 贝尔曼最优化原理贝尔曼最优化原理【例例3.2】（石油输送管道铺设优选问题）（石油输送管道铺设优选问题）某某石油公司计划从石油公司计划从A地到地到E地铺设一条石油输送地铺设一条石油输送管道，为此在管道，为此在A地与地与E地之间必须建立三个油地之间必须建立三个油泵加压站，如图泵加压站，如图3.2所示，所示，其中其中 分别为分别为必须建站的地区，而必须建站的地区，而 分别分别为可供选择的各站点，
19、各点连线上的数字表示为可供选择的各站点，各点连线上的数字表示相邻站点间铺设输送管道所需费用相邻站点间铺设输送管道所需费用.问：如何问：如何铺设石油输送管道，能使总费用最少？铺设石油输送管道，能使总费用最少？,B C D123123,B B B C C C12,D D3.2 贝尔曼最优化原理贝尔曼最优化原理(a)(b)3.2 贝尔曼最优化原理贝尔曼最优化原理解解 划分成划分成4个阶段：个阶段：阶段变量依次为阶段变量依次为4，3，2，1，如图，如图3.2所示所示.设设阶段阶段k的状态变量为的状态变量为 。;.AB BC CD DE,1,2,3,4kSk 在阶段在阶段1：1112()3,()4f D
20、f D在阶段在阶段2：可以取可以取 中任意一个，对中任意一个，对应的有应的有 2S123,C C C1111211212(,)()1 3()minmin4(,)()44d C Df Df Cd C Df D2111222212(,)()63()minmin7(,)()34d C Df Df Cd C Df D3111233212(,)()33()minmin6(,)()34d C Df Df Cd C Df D3.2 贝尔曼最优化原理贝尔曼最优化原理从从 出发到终点出发到终点E最短路径为最短路径为“”，决策变量决策变量 ；从从 出发到终点出发到终点E最短路径为最短路径为“”，决策变量决策变量
21、；从从 出发到终点出发到终点E最短路径为最短路径为“”，决策变量决策变量 ；1C11CDE*211()XCD2C22CDE*222()XCD3C31CDE*231()XCD3.2 贝尔曼最优化原理贝尔曼最优化原理在阶段在阶段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 C31213222
22、333323(,)()44(,)()()minmin8.17(,)()56d B Cf Cd B Cf CfBd B Cf C3.2 贝尔曼最优化原理贝尔曼最优化原理从从 出发到终点出发到终点E最短路径为最短路径为“”或或 决策变量决策变量 或或 ；1B111BCDE122BCDE*311()XBC2C从从 出发到终点出发到终点E最短路径为最短路径为“”，决策变量决策变量 ；2B211BCDE*321()XBC3B从从 出发到终点出发到终点E最短路径为最短路径为“”或或 决策变量决策变量 或或 ；311BCDE322BCDE*331()XBC2C在阶段在阶段4：1314232333(,)()2
23、 11()min(,)()min4711(,)()38d A BfBfAd A BfBd A BfB3.2 贝尔曼最优化原理贝尔曼最优化原理因此，由起点因此，由起点A到终点到终点E的费用最少路径有的费用最少路径有3条：条：211311322.；ABCDEABCDEABCDE此此3条路径对应的总费用均为条路径对应的总费用均为11单位金额。单位金额。3.2 贝尔曼最优化原理贝尔曼最优化原理动态规划为我们提供了一种优秀的决策思想：动态规划为我们提供了一种优秀的决策思想：战略上追求全局优化，战术上稳扎稳打、步步战略上追求全局优化，战术上稳扎稳打、步步为营。这深刻地揭示了局部与全局的统一关系。为营。这深
24、刻地揭示了局部与全局的统一关系。动态规划在实际中得到广泛应用，如可应用于动态规划在实际中得到广泛应用，如可应用于背包问题、资源分配问题、生产与存储问题、背包问题、资源分配问题、生产与存储问题、设备更新问题等。设备更新问题等。需要指出的是：动态规划是一种求解思路，注需要指出的是：动态规划是一种求解思路，注重决策过程，而不是一种算法，不同的问题模重决策过程，而不是一种算法，不同的问题模型各异。型各异。3.2 贝尔曼最优化原理贝尔曼最优化原理本节学习要点本节学习要点了解贝尔曼最优化原理.掌握动态规划的决策思想：战略上追求全局优化，战术上稳扎稳打、步步为营.注意动态规划是一种求解思路，注重决策过程，而
25、不是一种算法，不同的问题模型各异.3.3 WinQSB软件应用软件应用本节结合最短路径问题、背包问题介绍WinQSB软件的应用，其他问题的求解可参考本章参考文献.求解动态规划问题，需要调用WinQSB软件中的子程序“Dynamic Programming”.方法：点击“开始”“程序”“WinQSB”“Dynamic Programming”,屏幕显示如图3.3所示.该程序有3个子模块：最短路问题（Stagecoach Problem）,背包问题（Knapsack Problem）,生产与存储问题（Production and Inventory Scheduling）.3.3 WinQSB软件
26、应用软件应用 3.3 WinQSB软件应用软件应用点击1.最短路问题最短路问题【例3.3】用WinQSB软件求解例3.1.解解（1）调用WinQSB软件中的子程序“Dynamic Programming”，建立新问题.在图3.3中选择第一项，输入标题和站点数.（2）输入数据.按照图3.1从左到右将相邻站点间的距离输入表3.1中，其中 Node k表示图3.1中从左到右第k 个站点，k=1,2,9表3.1 3.3 WinQSB软件应用软件应用（3）求解）求解.点击菜单栏点击菜单栏“Solve and Analyze”“Solve the Problem”,得到图得到图3.4.再点击再点击“Sol
27、ve”键，得到计算结果，见表键，得到计算结果，见表3.2.可见由起点到终点的最短路径为可见由起点到终点的最短路径为 111SABCE 3.3 WinQSB软件应用软件应用表表 3.2 3.3 WinQSB软件应用软件应用2.背包问题背包问题背包问题的一般提法是：设有一位旅行者携带背包去登山，背包问题的一般提法是：设有一位旅行者携带背包去登山，已知他所能承受的背包质量为已知他所能承受的背包质量为a（单位：（单位：kg），），iiaixiic x(ici1,2,in种物品可供他选择装入背包，其中第种物品可供他选择装入背包，其中第种物品的重量为种物品的重量为（单位：（单位：kg），其价值（可以是表明
28、该物品对登山的重要性，其价值（可以是表明该物品对登山的重要性的函数的函数为第为第种物品单种物品单问：旅行者应如何选择携带各物品的件数，以使总价值最大？问：旅行者应如何选择携带各物品的件数，以使总价值最大？背包问题等同于车、船、飞机、潜艇、人造卫星等工具的最背包问题等同于车、船、飞机、潜艇、人造卫星等工具的最优装载问题，有广泛的实际意义优装载问题，有广泛的实际意义.现有现有n 的数量指标）是携带数量的数量指标）是携带数量位数量的价值，位数量的价值，).3.3 WinQSB软件应用软件应用【例例3.43.4】已知已知1T1T的集装箱最大载重量为的集装箱最大载重量为800kg.800kg.现有现有5
29、 5种物品种物品各各1010件可供选择装箱，其中单位物品重量、价值见表件可供选择装箱，其中单位物品重量、价值见表3.3.3.3.求求价值最大的装载方案价值最大的装载方案.表表3.33.3解解(1)调用调用WinQSB软件中子程序软件中子程序“Dynamic Programming”建立新问题：在图建立新问题：在图3.3中选择第二项，输入标题和物品品种数中选择第二项，输入标题和物品品种数5，见图，见图3.5.3.3 WinQSB软件应用软件应用（2）按表）按表3.4形式输入数形式输入数据：第据：第1列为物品名称，第列为物品名称，第2列为物品限量及集装箱最列为物品限量及集装箱最大载重量，第大载重量
30、，第3列为单位物列为单位物品重量，第品重量，第4列为物品价值列为物品价值函数函数.注：物品的数量仍用a,b,c,d,e表示.3.3 WinQSB软件应用软件应用 表表 3.4 3.3 WinQSB软件应用软件应用（3）求解）求解:点击菜单栏点击菜单栏“Solve and Analyze”“Solve the Problem”,得到表得到表3.5.由此表可见，由此表可见，价值最大的装载方案为：价值最大的装载方案为：物品物品a，b，c，d，e分别装载分别装载10，9，4，0，10件，总价值件，总价值1365元，集装箱还有元，集装箱还有5kg的剩余能的剩余能力力.3.3 WinQSB软件应用软件应用表表 3.5 3.3 WinQSB软件应用软件应用3.3 WinQSB软件应用软件应用本节学习要点本节学习要点1.了解WinQSB软件中子程序DynamicProgramming的功能.2.学会使用WinQSB软件求解：最短路问题；背包问题3.1 3.1 最短路径问题最短路径问题3.2 3.2 贝尔曼最优化原理贝尔曼最优化原理3.33.3 WinQSB软件应用软件应用
