第10章动态规划方法

2019/12/201第10章动态规划方法2019/12/202动态规划（DynamicProgramming）同前面介绍过的线性规划方法不同，它不是一种算法，而是考察问题的一种途径。动态规划是一种求解多阶段决策问题的系统技术。由于动态规划不是一种特定的算法，因而它不像线性规划那样有一个标准的数学表达式和明确定义的一组规则，动态规划必须对具体问题进行具体的分析处理。动态规划在自然科学和社会科学等各个领域都有着广泛的应用，并且获得了显著的效果。2019/12/2031最短路径问题2贝尔曼最优化原理3WinQSB软件应用动态规划2019/12/204动态规划是解决多阶段决策问题的一种方法.1951年，美国数学家贝尔曼（R.Bellman，1920～1984）研究了一类多阶段决策问题的特征，提出了解决这类问题的基本原理。在研究、解决了某些实际问题的基础上，他于1957年出版了《动态规划》这一名著。本章将简要介绍动态规划的思想方法及其应用。2019/12/205——动态规划解决问题的基本思路是：把整体比较复杂的大问题划分成一系列较易于解决的小问题，通过逐个求解，最终取得整体最优解。这种“分而治之，逐步调整”的方法，在一些比较难以解决的复杂问题中已经显示出优越性。2019/12/206——所谓多阶段决策过程是指这样一类活动过程：一个决策过程可以分为若干个相互联系的阶段，每个阶段都需要作一定的决策，但是每个阶段最优决策的选择不能只是孤立地考虑本阶段所取得的效果如何，必须把整个过程中的各个阶段联系起来考虑，要求所选择的各个阶段决策的集合——策略，能使整个过程的总效果达到最优。2019/12/2071最短路径问题2019/12/2081最短路径问题【例1】设在E城的某公司要从S城运送一批货物，两城之间有公路相连（见图1(a)），其中是可以供选择的途经站点，各点连线上的数字表示相邻站点间的距离。现在的问题是选择一条由S到E的路径，使得所经过的路径最短。(1,2,3),(1,2),(1,2)ijlAiBjCl2019/12/2091最短路径问题(a)(b)2019/12/20101最短路径问题分析：如果用枚举法，将有12条不同的路径，每条路径对应一个由S到E的路径距离，其中最小值所对应的路径即为最短路径。本问题的最短路径有3条，路程均为21个单位：第1条：第2条：第3条：111SABCE311SABCE321SABCE2019/12/20111最短路径问题当段数很多时，枚举法的计算量将极其庞大。现在换个思路，寻找由S到E的最短路径。先把最短路径问题所考虑的过程分为4个阶段：由S到为第1阶段；(1,2,3)iAi由到为第2阶段；由到E为第4阶段。由到为第3阶段；(1,2,3)iAi(1,2)jBj(1,2)jBj(1,2)lCl(1,2)lCl2019/12/20121最短路径问题我们称由某点到终点的阶段数k为阶段变量，如由到E的阶段数为1（这时记由C到E的阶段数为1，它与第1阶段是不同的概念），由到E的阶段数为2（这时记由B到E的阶段数为2），等等。可见阶段变量的取值正好与实际进行的阶段相反（图（b））。(1,2)lCl(1,2)jBj(b)2019/12/20131最短路径问题在任一阶段开始时所处的位置称为状态变量，在阶段k的状态变量记为，例如为阶段3的状态变量，可以取为中任意一个。当某一个状态给定后，需要做出决策以确定下一步的状态，描述决策的变量称为决策变量，在阶段k的决策变量记为。例如在阶段2的状态取时的决策变量记为，可取为。若，则表示由到，从而决定了下一步的状态是。kS3S123,,AAAkX22SB22()XB22()XB12,CC222()XBC2B2C2C2019/12/20141最短路径问题为了寻找由起点S到E终点的最短路径，我们考察前面用枚举法找到的第1条最短路径：111SABCE容易看出：子路径“”也应是从出发到终点E的所有路径中最短的一条。111ABCE1A这个现象启发我们从阶段1开始，逐段逆向地求出各点到终点E的最短路径，最后求得由起点S到终点E的最短路径，这就是动态规划的基本思想。2019/12/20151最短路径问题以表示在阶段k的状态变量为、决策变量为时点与间的距离；记为在阶段k由点到终点E的最短路径的长度。本例中要求的是。()kkfS在阶段1：可以取中任意一个，对应的有在阶段2：可以取中任意一个，对应的有(,())kkkdSXSkS()kkXSkS()kkXSkS4()fS1S12,CC1112()5,()8fCfC2S12,BB1111211212(,)()65()minmin11(,)()58dBCfCfBdBCfC2111222212(,)()95()minmin14(,)()88dBCfCfBdBCfC2019/12/20161最短路径问题从出发到终点E最短路径为“”，决策变量；11BCE1B在阶段3：可以取中任意一个，对应的有*211()XBC从出发到终点E最短路径为“”，决策变量；2B21BCE*221()XBC3S123,,AAA1121311222(,)()611()minmin17;(,)()514dABfBfAdABfB2121322222(,)()811()minmin19;(,)()614dABfBfAdABfB3121333222(,)()711()minmin18(,)()414dABfBfAdABfB2019/12/20171最短路径问题从出发到终点E最短路径为“”，决策变量；1A111ABCE从出发到终点E最短路径为“”，决策变量；从出发到终点E最短路径为“”，决策变量或；最后，在阶段4：只可以取S，于是*311()XAB2A211ABCE*321()XAB3A311ABCE*331()XAB2B4S1314232333(,)()417()min(,)()min31921(,)()318dSAfAfSdSAfAdSAfA2019/12/20181最短路径问题因此，由起点S到终点E的最短路径为111311321.SABCESABCESABCE；；最短路径长度为21单位长度。2019/12/20191最短路径问题由上述计算过程可知，对有n个阶段的最短路径问题，可以逐段逆向地求出各点到终点的最短路径，且在求解的每一步都利用阶段k和阶段k-1间的递推关系：-1()11111111()min{(,())(())},2,3,...,,()min{(,())}(,()).kkkkkkkkXSfSdSXSfXSknfSdSXSdSXS此关系被称为求最短路径的动态规划基本方程。求解最短路径问题的过程，本质上是解上述基本方程的过程。2019/12/20202贝尔曼最优化原理2019/12/20212贝尔曼最优化原理将求解最短路径问题的思路推广到一般多阶段决策问题时，可以表述成：贝尔曼最优化原理：一个过程的最优策略具有这样的性质，即无论其初始状态和初始决策如何，今后的诸决策，对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优策略。这个原理是动态规划的理论基础。2019/12/20222贝尔曼最优化原理应用动态规划方法解决一般多阶段决策问题时，其求解过程如下：（1）把实际问题适当地划分成k个阶段，阶段变量为；（2）在每个阶段k，确定状态变量为及此阶段可能的状态集合；（3）确定决策变量及每个阶段k的允许决策集合；（4）列出递推关系即动态规划基本方程并计算：(1,2,...,)kknkS{}kS()kkXS(){()}kkkkxSXS-1()11111111()min{(,())(())},2,3,...,,()min{(,())}(,()).kkkkkkkkxSfSdSXSfXSknfSdSXSdSXS2019/12/20232贝尔曼最优化原理【例2】（石油输送管道铺设优选问题）某石油公司计划从A地到E地铺设一条石油输送管道，为此在A地与E地之间必须建立三个油泵加压站，如图2所示，其中分别为必须建站的地区，而分别为可供选择的各站点，各点连线上的数字表示相邻站点间铺设输送管道所需费用.问：如何铺设石油输送管道，能使总费用最少？,,BCD123123,,,,,,BBBCCC12,DD2019/12/20242贝尔曼最优化原理(a)(b)2019/12/20252贝尔曼最优化原理解划分成4个阶段：阶段变量依次为4，3，2，1，如图2所示.设阶段k的状态变量为。;;;.ABBCCDDE,1,2,3,4kSk在阶段1：1112()3,()4fDfD在阶段2：可以取中任意一个，对应的有2S123,,CCC1111211212(,)()13()minmin4(,)()44dCDfDfCdCDfD2111222212(,)()63()minmin7(,)()34dCDfDfCdCDfD3111233212(,)()33()minmin6(,)()34dCDfDfCdCDfD2019/12/20262贝尔曼最优化原理从出发到终点E最短路径为“”，决策变量；从出发到终点E最短路径为“”，决策变量；从出发到终点E最短路径为“”，决策变量；1C11CDE*211()XCD2C22CDE*222()XCD3C31CDE*231()XCD2019/12/20272贝尔曼最优化原理在阶段3：可以取中任意一个，于是3S123,,BBB1121122231132321212222322323(,)()74(,)()()minmin11;47(,)()66(,)()34(,)()()minmin7;27(,)()46dBCfCdBCfCfBdBCfCdBCfCdBCfCfBdBCfC31213222333323(,)()44(,)()()minmin8.17(,)()56dBCfCdBCfCfBdBCfC2019/12/20282贝尔曼最优化原理从出发到终点E最短路径为“”或决策变量或；1B111BCDE122BCDE*311()XBC2C从出发到终点E最短路径为“”，决策变量；2B211BCDE*321()XBC3B从出发到终点E最短路径为“”或决策变量或；311BCDE322BCDE*331()XBC2C在阶段4：1314232333(,)()211()min(,)()min4711(,)()38dABfBfAdABfBdABfB2019/12/20292贝尔曼最优化原理因此，由起点A到终点E的费用最少路径有3条：211311322.；；ABCDEABCDEABCDE此3条路径对应的总费用均为11单位金额。2019/12/20302贝尔曼最优化原理动态规划为我们提供了一种优秀的决策思想：战略上追求全局优化，战术上稳扎稳打、步步为营。这深刻地揭示了局部与全局的统一关系。动态规划在实际中得到广泛应用，如可应用于背包问题、资源分配问题、生产与存储问题、设备更新问题等。需要指出的是：动态规划是一种求解思路，注重决策过程，而不是一种算法，不同的问题模型各异。2019/12/203