《动态规划相关知识》由会员分享，可在线阅读，更多相关《动态规划相关知识（67页珍藏版）》请在金锄头文库上搜索。
1、动动 态态 规规 划划 (Dynamic programming)动态规划的基本思想动态规划的基本思想最短路径问题最短路径问题投资分配问题投资分配问题背包问题背包问题 动态规划是解决多阶段决策过动态规划是解决多阶段决策过程最优化问题的一种方法。由美国程最优化问题的一种方法。由美国数学家数学家贝尔曼贝尔曼（Ballman）等人在）等人在20世纪世纪50年代提出。他们针对多阶年代提出。他们针对多阶段决策问题的特点，提出了解决这段决策问题的特点，提出了解决这类问题的类问题的“最优化原理最优化原理”，并成功地，并成功地解决了生产管理解决了生产管理 、 工程技术等方工程技术等方面的许多实际问题。面的许多
2、实际问题。 动态规划是现代企业管理动态规划是现代企业管理中的一种重要决策方法，可用中的一种重要决策方法，可用于最优路径问题、资源分配问于最优路径问题、资源分配问题、生产计划和库存问题、投题、生产计划和库存问题、投资问题、装载问题、排序问题资问题、装载问题、排序问题及生产过程的最优控制等。及生产过程的最优控制等。动态规划模型的分类：动态规划模型的分类：以以“时间时间”角度可分成：角度可分成： 离散型离散型和连续型。和连续型。从信息确定与否可分成：从信息确定与否可分成： 确定型确定型和随机型。和随机型。从目标函数的个数可分成：从目标函数的个数可分成： 单目标型单目标型和多目标型。和多目标型。7-1
3、 动态规划的基本原理动态规划的基本原理多阶段决策过程最优化多阶段决策过程最优化 多阶段决策过程是指这样一类多阶段决策过程是指这样一类特殊的活动过程，他们可以按时间特殊的活动过程，他们可以按时间顺序分解成若干相互联系的阶段，顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问题。阶段决策问题也称为序贯决策问题。例例7-1 生产与存储问题生产与存储问题 某工厂每月需供应市场一定数某工厂每月需供应市场一定数量的产品。供应需求所剩余产品应量的产品。供应需求所剩余产品应存入仓库，
4、一般地说，某月适当增存入仓库，一般地说，某月适当增加产量可降低生产成本，但超产部加产量可降低生产成本，但超产部分存入仓库会增加库存费用，要确分存入仓库会增加库存费用，要确定一个每月的生产计划，在满足需定一个每月的生产计划，在满足需求条件下，使一年的生产与存储费求条件下，使一年的生产与存储费用之和最小。用之和最小。例例7-2 投资决策问题投资决策问题 某公司现有资金某公司现有资金Q亿元，在今亿元，在今后后5年内考虑给年内考虑给A、B、C、D四个项四个项目投资，这些项目的投资期限、回目投资，这些项目的投资期限、回报率均不相同，问应如何确定这些报率均不相同，问应如何确定这些项目每年的投资额，使到第五
5、年末项目每年的投资额，使到第五年末拥有资金的本利总额最大。拥有资金的本利总额最大。例例7-3 设备更新问题设备更新问题 企业在使用设备时都要考虑企业在使用设备时都要考虑设备的更新问题，因为设备越陈设备的更新问题，因为设备越陈旧所需的维修费用越多，但购买旧所需的维修费用越多，但购买新设备则要一次性支出较大的费新设备则要一次性支出较大的费用。用。现在某企业要决定一台设备未来现在某企业要决定一台设备未来8年的更新计划，已预测到第年的更新计划，已预测到第j年购年购买设备的价格为买设备的价格为Kj，Gj为设备经为设备经过过j年后的残值，年后的残值，Cj为设备连续使为设备连续使用用j-1年后在第年后在第j
6、年的维修费用年的维修费用(j=1,28)，问应在哪年更新设备，问应在哪年更新设备可使总费用最小。可使总费用最小。动态规划的基本概念动态规划的基本概念阶段；阶段；状态；状态；决策和策略；决策和策略；状态转移；状态转移；指标函数。指标函数。例例7-4（不定阶段最短路线问题）（不定阶段最短路线问题） 如图是一个五座城市的及其相如图是一个五座城市的及其相连道路的交通图，线连道路的交通图，线上的数字是对上的数字是对应的路长。问：应如何选择行驶路应的路长。问：应如何选择行驶路线，才能使从线，才能使从A、B、C、D各城市各城市到到E城市的行驶路程城市的行驶路程最短？最短？A AE ED DC CB B2 2
7、5 52 27 75 55 56 61 10.50.53 3从图中可以看出，任意两座城市从图中可以看出，任意两座城市之间都有道路相通。我们把从一之间都有道路相通。我们把从一座城市直达另一座城市作为一个座城市直达另一座城市作为一个阶段。例从阶段。例从A城市到城市到E城市的阶段城市的阶段数，少则一个（例从数，少则一个（例从A城市直达城市直达E城市），多则无限（例从城市），多则无限（例从A城市通城市通过其他过其他B、C、D三城市循环到三城市循环到E城城市）。为避免循环，加上约束条市）。为避免循环，加上约束条件：每个城市至多经过一次。件：每个城市至多经过一次。 于是从于是从A城市到达城市到达E城市的阶
8、城市的阶段数有下列四种情形：段数有下列四种情形：1.从从A城市直达城市直达E城市，一个阶段。城市，一个阶段。 于是从于是从A城市到达城市到达E城市的阶城市的阶段数有下列四种情形：段数有下列四种情形：1.从从A城市直达城市直达E城市，一个阶段。城市，一个阶段。2.从从A城市通过其他城市通过其他B、C、D三城三城市之一到市之一到E城市，二个阶段。城市，二个阶段。于是从于是从A城市到达城市到达E城市的阶段数城市的阶段数有下列四种情形：有下列四种情形：3.从从A城市通过其他城市通过其他B、C、D三城三城市之二到市之二到E城市，三个阶段。城市，三个阶段。于是从于是从A城市到达城市到达E城市的阶段数城市的
9、阶段数有下列四种情形：有下列四种情形：3.从从A城市通过其他城市通过其他B、C、D三城三城市之二到市之二到E城市，三个阶段。城市，三个阶段。4.从从A城市通过其他城市通过其他B、C、D三城三城市各一次到市各一次到E城市，四个阶段。城市，四个阶段。例例7-5（一定阶段最短路问题）（一定阶段最短路问题） W先生每天驾车去公司上班。如图，先生每天驾车去公司上班。如图，W先生的住所位于先生的住所位于A，公司位于，公司位于F，图中的直线段代表公路，交叉，图中的直线段代表公路，交叉点代表路口，直线段上的数字代点代表路口，直线段上的数字代表两路口之间的平均行驶时间。表两路口之间的平均行驶时间。现在现在W先生
10、的问题是要确定一条先生的问题是要确定一条最省时的上班路线。最省时的上班路线。A 3 B1 4 C1 3 D1A 3 B1 4 C1 3 D14 5 3 24 5 3 2B2 2 C2 3 D2 E1B2 2 C2 3 D2 E11 2 3 41 2 3 4C3 4 D3 5 E2 2 FC3 4 D3 5 E2 2 FA AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F41544445333332222A AB B C C D DE EF F1 阶段（阶段（Stage） 将所给问题的过程，按时间或将所给问题的过程，按时间或空间特征分解成若干个相互联系的空
11、间特征分解成若干个相互联系的阶段，以便按次序去求每阶段的解，阶段，以便按次序去求每阶段的解，常用常用k表示阶段变量。表示阶段变量。我们把从我们把从A到到F看成一个五阶段问看成一个五阶段问题。题。2 状态（状态（State） 各阶段开始时的客观条件各阶段开始时的客观条件叫做状态。描述各阶段状态的叫做状态。描述各阶段状态的变量称为状态变量，常用变量称为状态变量，常用sk表表示第示第k阶段的状态变量，状态阶段的状态变量，状态变量的取值集合称为状态集合，变量的取值集合称为状态集合，用用Sk表示。表示。 动态规划中的状态具有如下性质：动态规划中的状态具有如下性质： 当某阶段状态给定以后，在这当某阶段状态
12、给定以后，在这阶段以后的过程的发展不受这段以阶段以后的过程的发展不受这段以前各段状态的影响。即：过程的过前各段状态的影响。即：过程的过去历史只能通过当前状态去影响它去历史只能通过当前状态去影响它未来的发展，这称为无后效性。如未来的发展，这称为无后效性。如果所选定的变量不具备无后效性，果所选定的变量不具备无后效性，就不能作为状态变量来构造动态规就不能作为状态变量来构造动态规划模型。划模型。3 决策和策略决策和策略（Decision and Policy） 当各段的状态确定以后，就可当各段的状态确定以后，就可以做出不同的决定（或选择），从以做出不同的决定（或选择），从而确定下一阶段的状态，这种决定
13、而确定下一阶段的状态，这种决定称为决策。决策变量用称为决策。决策变量用dk(Sk)表示，表示，允许决策集合用允许决策集合用Dk(Sk)表示。表示。 各个阶段决策确定后，整个问各个阶段决策确定后，整个问题的决策序列就构成一个策略，用题的决策序列就构成一个策略，用p1,n(d1,d2,dn)表示。对每个实际表示。对每个实际问题，可供选择的策略有一定的范问题，可供选择的策略有一定的范围，称为允许策略集合，用围，称为允许策略集合，用P表示。表示。使整个问题达到最优效果的策略就使整个问题达到最优效果的策略就是最优策略。是最优策略。4 状态转移方程状态转移方程 动态规划中本阶段的状态往动态规划中本阶段的状
14、态往往是上一阶段的决策结果。如果往是上一阶段的决策结果。如果给定了第给定了第k段的状态段的状态Sk ，本阶段决，本阶段决策为策为dk(Sk) ，则第，则第k+1段的状态段的状态Sk+1由公式：由公式： Sk+1=Tk（ Sk， dk）确定，称为状态转移方程。确定，称为状态转移方程。5 指标函数指标函数 用于衡量所选定策略优用于衡量所选定策略优劣的数量指标称为指标函数。劣的数量指标称为指标函数。最优指标函数记为最优指标函数记为fk(Sk)。 动态规划的基本思想：动态规划的基本思想： 从过程的最后一段开始，从过程的最后一段开始，用逆序递推方法求解，逐步用逆序递推方法求解，逐步求出各段各点到终点求出
15、各段各点到终点E最短最短路线，最后求出路线，最后求出A点到点到E点的点的最短路线。最短路线。A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F41544445333332222A AB B C C D DE EF F当当K=5时，此时时，此时d5(S5)=F，其初始状态，其初始状态E1或或E2，故故f5(E1)=4, f5(E2)=2用用d5*(S5)表示最优决策。表示最优决策。A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F41544445333332222A AB B C C D DE EF F当当K=4
16、时，有两个阶段，初始状态时，有两个阶段，初始状态S4可可以是以是D1、D2或或D3。如果如果S4=D1，则下一步只能取，则下一步只能取E1，故，故 f4(D1)= r(D1,E1)+ f5(E1)=2+4=6最短路线：最短路线：D1E1F最优解：最优解： d4*(D1)= E1A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F41544445333332222A AB B C C D DE EF F如果如果S4=D2，则下一步能取，则下一步能取E1或或E2，故，故 f4(D2)=Min r(D2,E1)+ f5(E1) r(D2,E2)+ f5(E2)
17、 =Min（4+4，3+2）=5最短路线：最短路线：D2E2F最优解：最优解： d4*(D2)= E2A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F41544445333332222A AB B C C D DE EF F如果如果S4=D3，则下一步只能取，则下一步只能取E2，故，故 f4(D3)= r(D3,E2)+ f5(E2)=5+2=7最短路线：最短路线：D3E2F最优解：最优解： d4*(D3)= E2A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F41544445333332222A AB B
18、 C C D DE EF F当当K=3时，还有三个阶段，初始状态时，还有三个阶段，初始状态S3可可以是以是C1、C2或或C3。如果如果S3=C1，则下一步能取，则下一步能取D1或或D2，故，故 f3(C1)=Min r(C1,D1)+ f4(D1) r(C1,D2)+ f4(D2) =Min（3+6，3+5）=8最短路线：最短路线： C1D2E2F最优解：最优解： d3*(C1)= D2A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F41544445333332222A AB B C C D DE EF F如果如果S3=C2，则下一步能取，则下一步能
19、取D2或或D3，故，故 f3(C2)=Min r(C2,D2)+ f4(D2) r(C2,D3)+ f4(D3) =Min（3+5，2+7）=8最短路线：最短路线： C2D2E2F最优解：最优解： d3*(C2)= D2A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F41544445333332222A AB B C C D DE EF F如果如果S3=C3，则下一步只能取，则下一步只能取D3，故，故 f3(C3)= r(C3,D3)+ f4(D3) =（4+7）=11最短路线：最短路线： C3D3E2F最优解：最优解： d3*(C3)= D3A A
20、B1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F41544445333332222A AB B C C D DE EF F当当K=2时，还有四个阶段，初始状态时，还有四个阶段，初始状态S2可以可以是是B1或或B2。如果如果S2=B1，则下一步能取，则下一步能取C1或或C2，故，故 f2(B1)=Min r(B1,C1)+ f3(C1) r(B1,C2)+ f3(C2) =Min（4+8，5+8）=12最短路线：最短路线： B1 C1D2E2F最优解：最优解： d2*(B1)= C1A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E
21、1E2E2F F41544445333332222A AB B C C D DE EF F如果如果S2=B2，则下一步能取，则下一步能取C2或或C3，故，故 f2(B2)=Min r(B2,C2)+ f3(C2) r(B2,C3)+ f3(C3) =Min（2+8，1+11）=10最短路线：最短路线： B2 C2D2E2F最优解：最优解： d2*(B2)= C2A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F41544445333332222A AB B C C D DE EF F当当K=1时，五个阶段的原问题，初始状态时，五个阶段的原问题，初始状态
22、S1是是A。则下一步能取。则下一步能取B1或或B2，故，故 f1(A)=Min r(A,B1)+ f2(B1) r(A,B2)+ f2(B2) =Min（3+12，4+10）=14最短路线：最短路线：A B2 C2D2E2F最优解：最优解： d1*(A)= B2，最短用时最短用时14.A AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F41544445333332222A AB B C C D DE EF FA AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F41544445333332222A AB B C C
23、D DE EF FA AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F41544445333332222A AB B C C D DE EF FA AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F41544445333332222A AB B C C D DE EF FA AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E2F F41544445333332222A AB B C C D DE EF FA AB1B1B2B2C1C1C2C2C3C3D1D1D2D2D3D3E1E1E2E
24、2F F41544445333332222A AB B C C D DE EF F动态规划的函数方程（动态规划的函数方程（DP） 建立建立DP函数方程是指确定过函数方程是指确定过程的阶段及阶段数，规定状态变程的阶段及阶段数，规定状态变量和决策变量的取法，给出各阶量和决策变量的取法，给出各阶段的状态集合，允许决策集合，段的状态集合，允许决策集合，状态转移方程和指标函数等。状态转移方程和指标函数等。在上面的计算过程中，利用了第在上面的计算过程中，利用了第k阶段与第阶段与第k+1阶段的关系：阶段的关系：fk(Sk)= Min r(Sk,dk(Sk)+fk+1(Sk+1) d dk k(S(Sk k)
25、 ) k=1,2,3,4,5f6(S6)=0 这种递推关系称为这种递推关系称为动态规划动态规划的函数基本方程。的函数基本方程。贝尔曼贝尔曼(Ballman)最优化原理最优化原理 作为整个过程的最优策略具有作为整个过程的最优策略具有这样的性质，即无论过去的状态和这样的性质，即无论过去的状态和决策如何，对前面的决策所形成的决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成状态而言，余下的诸决策必须构成最优策略。这就是说，不管引导到最优策略。这就是说，不管引导到这个现时状态的头一个状态和决策这个现时状态的头一个状态和决策是什么，所有的未来决策应是最优是什么，所有的未来决策应是最优的。的。动
26、态规划的优点：动态规划的优点：可把一个可把一个N维优化问题化成维优化问题化成N个一个一维优化问题求解。维优化问题求解。动态规划的优点：动态规划的优点：可把一个可把一个N维优化问题化成维优化问题化成N个一个一维优化问题求解。维优化问题求解。DP方程中附加某些约束条件，可方程中附加某些约束条件，可使求解更加容易。使求解更加容易。动态规划的优点：动态规划的优点：可把一个可把一个N维优化问题化成维优化问题化成N个一个一维优化问题求解。维优化问题求解。DP方程中附加某些约束条件，可方程中附加某些约束条件，可使求解更加容易。使求解更加容易。求得最优解以后，可得所有子问题求得最优解以后，可得所有子问题的最优解。的最优解。动态规划的缺点：动态规划的缺点：“一个一个”问题，问题，“一个一个”模型，模型，“一个一个”求解方法。且求解技巧要求比较求解方法。且求解技巧要求比较高，没有统一处理方法。高，没有统一处理方法。动态规划的缺点：动态规划的缺点：“一个一个”问题，问题，“一个一个”模型，模型，“一个一个”求解方法。且求解技巧要求比较求解方法。且求解技巧要求比较高，没有统一处理方法。高，没有统一处理方法。状态变量维数不能太高，一般要状态变量维数不能太高，一般要求小于求小于6。
