动态规划及其应用课件

《动态规划及其应用课件》由会员分享，可在线阅读，更多相关《动态规划及其应用课件（92页珍藏版）》请在装配图网上搜索。

1、广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用1 缪兴锋 教授/高级工程师联系方法：634378 E-mail:wuliuxitong 2013广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用2【学习目标】【学习目标】知识目标知识目标 1.了解动态规划的作用与意义以及在实际中的应用了解动态规划的作用与意义以及在实际中的应用 2.掌握动态规划的基本方法以及动态规划的建模掌握动态规划的基本方法以及动态规划的建模 3.掌握动态规划是规划论的一个重要分支，理解它与掌握动态规划是规划论的一个重要分支，理解它与传统的解题不同方法；传统的解题不同方法；4.掌握动态规划的顺序及逆序解法。掌握

2、动态规划的顺序及逆序解法。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用3 能力目标能力目标 1.能够结合实际情况建立动态规划模型能够结合实际情况建立动态规划模型，把一个复杂的，把一个复杂的问题，划分为一系列小问题，以便通过解这些小问题来问题，划分为一系列小问题，以便通过解这些小问题来求得全部问题的解决求得全部问题的解决 2.能够应用顺序及逆序解法求解简单的投资分配问题、能够应用顺序及逆序解法求解简单的投资分配问题、货物配装问题、最短路径问题以及生产与存储问题货物配装问题、最短路径问题以及生产与存储问题广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用4 机械挖掘金矿问题机械挖

3、掘金矿问题 两个金矿两个金矿A,B分别有存储量分别有存储量x，y，现有一部开矿机器。，现有一部开矿机器。如果开采金矿如果开采金矿A，则以概率，则以概率P1得储量得储量x的的r1倍（倍（0 r11），并且），并且机器没有损坏，可以继续再去开采金矿机器没有损坏，可以继续再去开采金矿A或或B。同时又以概率。同时又以概率1-P1宣告失败，机器报废，也得不到金子；宣告失败，机器报废，也得不到金子；如果把这部开矿机器用以开采金矿如果把这部开矿机器用以开采金矿B，则以概率，则以概率P2得到储量得到储量y的的r2倍（倍（0r21），并且机器没有损坏，可以继续再去开采金矿），并且机器没有损坏，可以继续再去开采金

4、矿A或或B，同时又以概率，同时又以概率1-P2宣告失败，机器报废，也得不到金子。宣告失败，机器报废，也得不到金子。把机器用于开采金矿把机器用于开采金矿A或者或者B，如果机器没有损坏，将继续把机，如果机器没有损坏，将继续把机器用于开采金矿器用于开采金矿A或者或者B，直到机器损坏，问应该如何选择开矿的，直到机器损坏，问应该如何选择开矿的序列使获得金子的期望值最大。序列使获得金子的期望值最大。讨论题：讨论题：1.运筹学的产生是不是属于偶然现象？运筹学的产生是不是属于偶然现象？2.运筹学与物流的结合应用中间有什么必然联系？运筹学与物流的结合应用中间有什么必然联系？广东轻工职业技术广东轻工职业技术学院学

5、院动态规划及其应用5动态规划是解决多阶段决策过程最优化问题的一种方法。动态规划是解决多阶段决策过程最优化问题的一种方法。该方法在工程技术、企业管理、物流规划与管理以及军事等部门都该方法在工程技术、企业管理、物流规划与管理以及军事等部门都有广泛的应用，并取得了显著的效果。有广泛的应用，并取得了显著的效果。在物流管理中，动态规划可以解决最优路径问题、生产计划与库存、在物流管理中，动态规划可以解决最优路径问题、生产计划与库存、资源分配问题、装载排序、投资及生产过程的最优控制等问题。资源分配问题、装载排序、投资及生产过程的最优控制等问题。它的独特解题思路，在处理某些优化问题时，比线性规划或非线性它的独

6、特解题思路，在处理某些优化问题时，比线性规划或非线性规划方法更有效。规划方法更有效。动态规划的优点是可把一个动态规划的优点是可把一个N维优化问题化成维优化问题化成N个一维优化问题求个一维优化问题求解；求得最优解以后，可得所有子问题的最优解。解；求得最优解以后，可得所有子问题的最优解。动态规划的缺点是没有统一的处理方法，不同的问题具有不同的模动态规划的缺点是没有统一的处理方法，不同的问题具有不同的模型，采用不同的求解方法，而且求解技巧要求比较高；状态变量维型，采用不同的求解方法，而且求解技巧要求比较高；状态变量维数不能太高，一般情况下变量维数小于数不能太高，一般情况下变量维数小于10。广东轻工职

7、业技术广东轻工职业技术学院学院动态规划及其应用6v动态规划是把多阶段决策问题作为研究对象。动态规划是把多阶段决策问题作为研究对象。v所谓多阶段决策是指可将问题求解的全过程划分所谓多阶段决策是指可将问题求解的全过程划分为若干个互相联系的阶段为若干个互相联系的阶段(即将问题划分为许多个即将问题划分为许多个互相联系的子问题互相联系的子问题)，在它的每一阶段都需要作出，在它的每一阶段都需要作出决策，并且在一个阶段的决策确定以后再转移到决策，并且在一个阶段的决策确定以后再转移到下一个阶段。下一个阶段。v在决策过程中，往往前一个阶段的决策要影响到在决策过程中，往往前一个阶段的决策要影响到后一阶段的决策，从

8、而影响整个过程。后一阶段的决策，从而影响整个过程。v这类把一个问题划分成若干个相互联系的阶段并这类把一个问题划分成若干个相互联系的阶段并选取其最优策略的问题就是多阶段决策问题。选取其最优策略的问题就是多阶段决策问题。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用7 1951年，美国数学家贝尔曼（年，美国数学家贝尔曼（RBellman，19201984）研究了一类多阶段决策问题的特征，提出了解决这类问研究了一类多阶段决策问题的特征，提出了解决这类问题的基本原理。在研究、解决了某些实际问题的基础上，题的基本原理。在研究、解决了某些实际问题的基础上，他于他于1957年出版了年出版了动态规划

9、动态规划这一名著。本章将简要这一名著。本章将简要介绍动态规划的思想方法及其应用。介绍动态规划的思想方法及其应用。由于动态规划与由于动态规划与“时间时间”关系很密切，随着时间过程的关系很密切，随着时间过程的发展而决定各阶段的决策，产生一个决策序列，这就是发展而决定各阶段的决策，产生一个决策序列，这就是“动态动态”的意思。的意思。然而它也可以处理与时间无关的静态问题，只要在问题然而它也可以处理与时间无关的静态问题，只要在问题中人为地引入中人为地引入“时间时间”因素，将问题看成多阶段的决策因素，将问题看成多阶段的决策过程即可。过程即可。动态规划及其应用8 动态规划解决问题的基本思路：动态规划解决问题

10、的基本思路：把整体比较复杂的大问把整体比较复杂的大问题划分成一系列较易于解决的小问题，通过逐个求解，题划分成一系列较易于解决的小问题，通过逐个求解，最终取得整体最优解。最终取得整体最优解。这种这种“分而治之，逐步调整分而治之，逐步调整”的方法，在一些比较难以的方法，在一些比较难以解决的复杂问题中已经显示出优越性。解决的复杂问题中已经显示出优越性。在经济管理决策中，有些管理决策问题可以按时序或空在经济管理决策中，有些管理决策问题可以按时序或空间演变划分成多个阶段间演变划分成多个阶段，呈现出明显的阶段性；，呈现出明显的阶段性；于是可把这类决策问题分解成几个相互联系的阶段，每于是可把这类决策问题分解

11、成几个相互联系的阶段，每个阶段即为一个子问题；个阶段即为一个子问题；原有问题的求解就化为逐个求解几个简单的阶段子问题；原有问题的求解就化为逐个求解几个简单的阶段子问题；每个阶段的决策一旦确定，整个决策过程也随之确定，每个阶段的决策一旦确定，整个决策过程也随之确定，此类问题称为多阶段决策问题。此类问题称为多阶段决策问题。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用9 动态规划数学模型由阶段、状态、决策与策略、动态规划数学模型由阶段、状态、决策与策略、状态转移方程及指标函数等状态转移方程及指标函数等5个要素组成。个要素组成。为了理解动态规划的解题思路，为了理解动态规划的解题思路，广东轻

12、工职业技术广东轻工职业技术学院学院动态规划及其应用10q根据多阶段决策过程的时间参量是离散的还是连根据多阶段决策过程的时间参量是离散的还是连续的，动态规划过程可分为：续的，动态规划过程可分为：离散决策过程与连离散决策过程与连续决策过程；续决策过程；q根据决策过程的演变是确定性的还是随机性的，根据决策过程的演变是确定性的还是随机性的，可分为：可分为：确定性、随机性的决策过程。确定性、随机性的决策过程。q这样组合起来就有这样组合起来就有离散确定性、离散随机性、连离散确定性、离散随机性、连续确定性、连续随机性续确定性、连续随机性 四种决策过程模型。四种决策过程模型。q有些决策过程的阶段数是有些决策过

13、程的阶段数是固定的固定的，称为，称为定期的决定期的决策过程策过程，q有些决策过程的阶段数是有些决策过程的阶段数是不固定不固定的或可以有的或可以有无限无限多阶段多阶段数，分别称为数，分别称为不定期不定期或或无期的决策过程无期的决策过程。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用11 max f(X1,X2)8 X1 9 X2 s.t v 这个问题的求解很简单，直观处理便可以找出最这个这个问题的求解很简单，直观处理便可以找出最这个问题的求解很简单，直观处理便可以找出最优解，因为目问题的求解很简单，直观处理便可以找出最优解，因为目标函数为标函数为X1，X2的线性函数，且系数均为正值，的

14、线性函数，且系数均为正值，X2的系的系数比数比X1的系数大，所以最优解中的的系数大，所以最优解中的X2 的取值要尽量大，的取值要尽量大，X1 取值要相对较小，再分析约束条件，得：取值要相对较小，再分析约束条件，得：v X10，X2 6v 目标函数最优值为：目标函数最优值为：v Fmax f(X1，X2)54。4X12X2 12X10，X203.13.2广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用12q从形式上我们把问题分解为两个子问题，每次只考虑一从形式上我们把问题分解为两个子问题，每次只考虑一个变量。个变量。q第一阶段，从形式上考虑第一阶段，从形式上考虑X1，由约束条件（，由约束

15、条件（3.2）知）知,第一第一阶段的阶段的X1的取值范围应为：的取值范围应为：04X112，q其对目标函数的贡献为其对目标函数的贡献为R18X1。q当第一阶段当第一阶段X1形式取值确定后，在下一阶段形式取值确定后，在下一阶段X2的变化范的变化范围是：围是：02 X2 124X1q在此基础上，在形式上考虑在此基础上，在形式上考虑X2，它对目标函数的贡献为，它对目标函数的贡献为R29X2。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用13q上面只是形式上考虑上面只是形式上考虑X1和和X2，并没有说它们具体取何值，并没有说它们具体取何值，下面用回代过程来求解。下面用回代过程来求解。q 求解

16、过程与分析过程相反，即把第二阶段作为计算的第求解过程与分析过程相反，即把第二阶段作为计算的第一步。一步。S.t第一步：把第一步：把X1的取值作为参数，考虑子问题的取值作为参数，考虑子问题 max f19X2 2X2124X1 X20v这个问题当这个问题当X2取最大值时目标函数达到极大，因此最优解取最大值时目标函数达到极大，因此最优解 为为:X262X1v目标函数值为：目标函数值为：F1Maxf19（62X1）广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用14qMaxf28X1 F1 8X19（62X1）5410X1 4X112 X10 S.t.v这个问题当这个问题当X1取最小值时目标

17、函数达到极大，因此最优取最小值时目标函数达到极大，因此最优解为：解为：X10v目标函数值为：目标函数值为：F2Max f254。v把把X10 代入第一步中的代入第一步中的 X2的表达式的表达式,得：得：X26v这个结果与前面直观处理计算是一致的。这个结果与前面直观处理计算是一致的。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用15 1）阶段）阶段 (stage)为能应用动态规划方法，首先必须根据实际问题所处的为能应用动态规划方法，首先必须根据实际问题所处的时间、空间或其他条件，把所研究的问题恰当地划分成时间、空间或其他条件，把所研究的问题恰当地划分成若干个相互联系的阶段。若干个相互联

18、系的阶段。用用k1，2，n，表示阶段序号，把，表示阶段序号，把k 称为阶段变称为阶段变量。如例量。如例1分为二个阶段，则分为二个阶段，则n2，k1，2。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用16v各阶段开始的客观条件叫做各阶段开始的客观条件叫做状态状态。描述各阶段状态的变。描述各阶段状态的变量称为量称为状态变量状态变量，常用，常用Yk表示第表示第k阶段的阶段的状态变量状态变量。v上例中记约束条件的右端的上例中记约束条件的右端的12为初始状态为初始状态,即即Y0 12.v它是第一阶段的输入状态。它是第一阶段的输入状态。vY1Y04X1v为第一阶段的输出状态，也是第二阶段的输入状

19、态为第一阶段的输出状态，也是第二阶段的输入状态。vY2Y12X1v为第二阶段的输出状态。为第二阶段的输出状态。Y2实际上相当于一般规划中的实际上相当于一般规划中的松弛变量松弛变量。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用17v在一个阶段中，可以有若干个状态，第在一个阶段中，可以有若干个状态，第k 段所有状态段所有状态构成的集合，称为构成的集合，称为第第k段段状态集，记为状态集，记为Yk y k 。v当某阶段状态给定以后，在这阶段以后的过程的发展当某阶段状态给定以后，在这阶段以后的过程的发展不受这段以前各段状态的影响。不受这段以前各段状态的影响。v即：即：过程的过去历史只能通过当

20、前状态去影响它未来过程的过去历史只能通过当前状态去影响它未来的发展，这称为的发展，这称为无后效性无后效性。v如果所选定的变量不具备无后效性，就不能作为状态如果所选定的变量不具备无后效性，就不能作为状态变量来构造动态规划模型。变量来构造动态规划模型。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用18v所谓决策所谓决策，是指对某一阶段活动初从给定的状态出发，决，是指对某一阶段活动初从给定的状态出发，决策者面临若干个不同的行为方案或途径作出的一种选择。策者面临若干个不同的行为方案或途径作出的一种选择。v 由于实际问题千变万化，因而决策可以有形形色色的不同含由于实际问题千变万化，因而决策可以

21、有形形色色的不同含义，很难言简而概全。义，很难言简而概全。v 但无论如何，有一点则是肯定的，就是每段的决策都取决于但无论如何，有一点则是肯定的，就是每段的决策都取决于该段的状态，它要随状态的变化而变化。该段的状态，它要随状态的变化而变化。v 用用xk 表示第表示第 k 段的决策，称之为段的决策，称之为第第 k 段决策变量段决策变量；由于决策；由于决策随状态而变，所以决策变量随状态而变，所以决策变量 xk是状态变量是状态变量Yk的函数，的函数，记为记为xkxk(Yk)。v 决策变量的取值一般都要受到一定条件的限制，我们把第决策变量的取值一般都要受到一定条件的限制，我们把第k段段决策变量的允许取值

22、范围称为第决策变量的允许取值范围称为第k 段允许决策集合，段允许决策集合，记为记为Xk(Yk)，于是，于是xk(Yk)Xk(Yk).广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用19 能否成功地应用动态规划方法，重要条件之一，就是所设能否成功地应用动态规划方法，重要条件之一，就是所设状态变量和决策变量必须满足：状态变量和决策变量必须满足：Yk和和Xk，的取值一经确定，则下一段状态变量，的取值一经确定，则下一段状态变量Yk+1的取值的取值规律也能随之确定，规律也能随之确定，就是说，就是说，Yk+1与与Yk和和Xk之间必须能够建立一种明确的数量之间必须能够建立一种明确的数量对应关系。对应

23、关系。在动态规划中本阶段的状态往往是上一阶段的决策结果。在动态规划中本阶段的状态往往是上一阶段的决策结果。如果给定了第如果给定了第k段的状态段的状态Yk，则第，则第k+1段的状态段的状态Yk+1由公式：由公式：Yk+1=Tk（YK，Xk+1）确定确定 这种明确的数量关系称为状态转移方程。这种明确的数量关系称为状态转移方程。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用20v 在多阶段决策过程中，每一阶段均有一个决策，依序组合成在多阶段决策过程中，每一阶段均有一个决策，依序组合成一个全过程的决策序列，称为一个全过程的决策序列，称为全过程策略全过程策略，简称，简称策略策略，记为，记为p

24、p1 1(y(y1 1)，有：，有：p p1 1(y(y1 1)=x=x1 1(y(y1 1)，x x2 2(y(y2 2)，,x,xn n(y(yn n)，简记简记p p1 1=x=x1 1，x x2 2，,x,xn n v 从过程的从过程的某个阶段开始某个阶段开始到到最终阶段最终阶段结束称为结束称为后部子过程后部子过程。从。从第第k k阶段开始的后部子策略称为第阶段开始的后部子策略称为第k k子过程策略。子过程策略。p pk k(y(yk k)=x)=xk k(y(yk k)，x xk+1k+1(y(yk+1k+1),),，x xn n(y(yn n)，简记简记p pk k=x=xk k，

25、x xk+1k+1，,x,xn n v 每一阶段有若干状态，每个状态又有若干个不同的决策，即每一阶段有若干状态，每个状态又有若干个不同的决策，即有许多策略可供选择。全体策略构成允许策略集合有许多策略可供选择。全体策略构成允许策略集合P Pk k(y(yk k)。v 能使预期目标达到最优效果的策略称为最优策略能使预期目标达到最优效果的策略称为最优策略P P*k k，v 构成最优策略的各决策称为相应阶段的最优决策构成最优策略的各决策称为相应阶段的最优决策x x*k k。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用21 指标函数有指标函数有阶段的指标函数阶段的指标函数和和过程的指标函数过

26、程的指标函数之分。之分。阶段的指标函数阶段的指标函数是对应某一阶段状态和从该状态出发的一个是对应某一阶段状态和从该状态出发的一个阶段的决策效果的优劣的数量指标，称为阶段指标函数阶段的决策效果的优劣的数量指标，称为阶段指标函数Vk，阶段指标是状态变量和相应决策变量的函数，阶段指标是状态变量和相应决策变量的函数，即即 Vk=Vk(Yk,xk)。过程的指标函数过程的指标函数是指从第是指从第k阶段的状态阶段的状态Yk出发到最后阶段出发到最后阶段结束，各阶段绩效综合起来反映这个后部子过程的绩效，称结束，各阶段绩效综合起来反映这个后部子过程的绩效，称为过程指标函数，记为为过程指标函数，记为Vk,n。Vk,

27、n的大小取决于从第的大小取决于从第k阶段到最后阶段所采取的子策略。阶段到最后阶段所采取的子策略。即即 Vk,n=Vk,n(yk，xk,yk+1，xk+1,yn)广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用22 根据实际问题的性质，指标函数根据实际问题的性质，指标函数Vk,n 可以是各个阶段可以是各个阶段指标的指标的和或积。和或积。最优指数函数最优指数函数是指对从是指对从状态状态yk出发某一确定状态选取最出发某一确定状态选取最优策略后得到的优策略后得到的指标函数值指标函数值，是对应某一最优子策略的，是对应某一最优子策略的某种某种效益度量。效益度量。（这个度量值可以是产量、成本、距离等

28、）。（这个度量值可以是产量、成本、距离等）。对应于从对应于从状态状态Yk 出发的出发的最优子策略最优子策略的效益值记作的效益值记作fk(Yk),于是有于是有 fk(Yk)=optVk,n =opt vk(yk,xk)+fk+1(yk+1)其中，其中，opt 表示最优化，根据具体含义表示最优化，根据具体含义 可以求最大（可以求最大（max）或求最小（）或求最小（min）。）。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用23 设计一个标准的动态规划算法设计一个标准的动态规划算法,通常可按以下几个步骤进通常可按以下几个步骤进行：行：1划分阶段：按照问题的时间或空间特征划分阶段：按照问题的

29、时间或空间特征,把问题分为把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的可排序的(即无后向性即无后向性)，否则问题就无法用动态规划求，否则问题就无法用动态规划求解。解。2选择状态：将问题发展到各个阶段时所处于的各种客选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。足无后效性。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用24 3确定决策并写出状态转移方程：之所以把这两步放在确定决策并写出状态转移方程：之所以把这两

30、步放在一起，因为决策和状态转移有着天然的联系，状态转移一起，因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。就是根据上一阶段的状态和决策来导出本阶段的状态。所以所以,如果我们确定了决策如果我们确定了决策,状态转移方程也就写出来了。状态转移方程也就写出来了。但事实上但事实上,我们常常是反过来做我们常常是反过来做,根据相邻两段的各状态根据相邻两段的各状态之间的关系来确定决策。之间的关系来确定决策。4写出规划方程写出规划方程(包括边界条件包括边界条件)，动态规划的基本方程，动态规划的基本方程是规划方程的通用形式化表达式。一般说来，只要阶段、是规划方程的通用形

31、式化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。状态、决策和状态转移确定了，这一步还是比较简单的。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用25 将多阶段决策过程划分阶段，恰当地选取状态将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量，定义最优指标函数，从而把问题变量、决策变量，定义最优指标函数，从而把问题化成一簇同类型的子问题，然后逐个求解。化成一簇同类型的子问题，然后逐个求解。求解时从边界条件开始，逆过程方向行进，逐求解时从边界条件开始，逆过程方向行进，逐段递推寻优。在每一个子问题求解时，都要使用它段递推寻优。在每一个子问题求解时，都要

32、使用它前面已求出的子问题的最优结果，最后一个子问题前面已求出的子问题的最优结果，最后一个子问题的最优解，就是整个问题的最优解。的最优解，就是整个问题的最优解。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用26 动态规划是将最初的问题分解为许多更容易解决的子问动态规划是将最初的问题分解为许多更容易解决的子问题。题。在【例题在【例题4.2】图】图4-1中的最短路问题中，我们把要建立的中的最短路问题中，我们把要建立的这些子问题定义为一个这些子问题定义为一个4阶段的动态规划问题。阶段的动态规划问题。在解决这个问题之前，我们先给出一条重要的原理在解决这个问题之前，我们先给出一条重要的原理贝尔曼

33、最优化原理。贝尔曼最优化原理。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用27 若某一点在最优路径上，那么从这一点到若某一点在最优路径上，那么从这一点到终点的最短路径也在最优路径上。解决最终点的最短路径也在最优路径上。解决最短路径问题的动态规划方法主要是将每一短路径问题的动态规划方法主要是将每一个节点看成是在最优路径上，然后做出相个节点看成是在最优路径上，然后做出相应的计算。应的计算。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用28 一个过程的最优策略具有这样的性质，即无论其初始状一个过程的最优策略具有这样的性质，即无论其初始状态和初始决策如何，今后诸决策对以第一个决策

34、所形成态和初始决策如何，今后诸决策对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优策略。的状态作为初始状态的过程而言，必须构成最优策略。这个原理是动态规划的理论基础。这个原理是动态规划的理论基础。应用动态规划思想方法解决一般多阶段决策问题时，其应用动态规划思想方法解决一般多阶段决策问题时，其求解过程如下：求解过程如下：把实际问题适当地划分成把实际问题适当地划分成n 个阶段，阶段变量为个阶段，阶段变量为k(k=1,2,n)；在每个阶段在每个阶段k 确定状态变量确定状态变量Sk及此阶段可能的状态集及此阶段可能的状态集合合Sk；广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用2

35、9广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用30 【例【例4.2】各城市间的交通线及距离如下图各城市间的交通线及距离如下图4-1所示，某所示，某物流公司进行货物配送要从城市物流公司进行货物配送要从城市1 到城市到城市10，问应选择，问应选择什么路线，可使运输成本最低？什么路线，可使运输成本最低？广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用31v解：解：这是一个典型的多阶段决策问题，由于所选运货路这是一个典型的多阶段决策问题，由于所选运货路线会有若干个不同选法，配送运输成本就不同，这就将线会有若干个不同选法，配送运输成本就不同，这就将物流求运输成本问题转化为求最短路径问

36、题。物流求运输成本问题转化为求最短路径问题。v第一种求解方法：穷举法第一种求解方法：穷举法v 从城市从城市1 到城市到城市10共有共有 C31 C31 C21 C11=18条不同条不同路径；路径；v 每条路径做每条路径做3次加法，要求出最短路线需要作次加法，要求出最短路线需要作54次加法，次加法，17次比较运算，次比较运算，v 当问题的段数很多，各段的状态也很多时，这种方法当问题的段数很多，各段的状态也很多时，这种方法的计算量会大大增加，甚至使得求优成为不可能。的计算量会大大增加，甚至使得求优成为不可能。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用32 这种方法是从过程的最后一段开

37、始，用这种方法是从过程的最后一段开始，用逆序递推算方法逆序递推算方法求解。求解。逐步求出各段各点到终点城市逐步求出各段各点到终点城市10的最短路线，最后求得的最短路线，最后求得城市城市1到城市到城市10的最短路线。的最短路线。用用d（Yk，uk）表示由状态）表示由状态Yk点出发，采用决策点出发，采用决策uk到达到达下一阶段下一阶段Yk+1点时的两点距离。点时的两点距离。本案例从城市本案例从城市1到城市到城市10 共分共分4个状态。个状态。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用33v 第第1步，步，从从k=4开始，状态变量开始，状态变量Y4取两种状态取两种状态8，9，到点，到点

38、10的路长分别为的路长分别为4，3，即，即f4（8）=4，f4（9）=3。第第2 2步，步，k=3k=3，状态变量，状态变量Y Y3 3取三个值取三个值5 5，6 6，7 7，是经过一个中，是经过一个中途点到达终点途点到达终点1010的两级决策问题，从城市的两级决策问题，从城市5 5到到1010有两条路线，取有两条路线，取其中最短的即：其中最短的即：f3（5）=min d(5,8)+d(5,8)+f4（8）d(5,9)+d(5,9)+f4（9）=min3+3+45+5+3=7v 则由城市则由城市5到终点到终点10最短距离为最短距离为7，路径为：，路径为：5810，v 相应决策为相应决策为 u*

39、3(5)=8。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用34v则由城市则由城市6到终点到终点10最短距离为最短距离为5，路径为：，路径为：6910，v相应决策为相应决策为u*3(6)=9。f3（6）=min d(6,8)+d(6,8)+f4（8）d(6,9)+d(6,9)+f4（9）=min6+6+42+2+3=5f3（7）=min d(7,8)+d(7,8)+f4（8）d(7,9)+d(7,9)+f4（9）=min1+1+43+3+3=5v则由城市则由城市7到终点到终点10最短距离为最短距离为5，路径为：，路径为：7810，v相应决策为相应决策为u*3(7)=8。广东轻工职业技

40、术广东轻工职业技术学院学院动态规划及其应用35 第第3步，步，k=2，是具有三个初始状态，是具有三个初始状态2，3，4，要经过两个中，要经过两个中途站才能到达终点的三级决策问题。途站才能到达终点的三级决策问题。由于第由于第3段各点段各点5，6，7，到终点，到终点10的最段距离的最段距离f3（5），），f3（6），），f3（7）已知，）已知，所以，若求城市所以，若求城市2到到10的最短距离，只需以此为基础，分别加的最短距离，只需以此为基础，分别加上城市上城市2与与5，6，7的一段距离，取其短者即可。的一段距离，取其短者即可。f2（2）=min d(2,5)+d(2,5)+f3（5）d(2,6)+

41、d(2,6)+f3（6）d(2,7)+d(2,7)+f3（7）=min6+6+74+4+55+5=9v 则 由 城 市则 由 城 市 2 到 终 点到 终 点 1 0 最 短 距 离 为最 短 距 离 为 6，路 径 为：，路 径 为：26910，v 相应决策为相应决策为u*2(2)=6。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用36 相应决策为相应决策为：u*2(3)=7。f2（3）=min d(3,5)+d(3,5)+f3（5）d(3,6)+d(3,6)+f3（6）d(3,7)+d(3,7)+f3（7）=min8+8+77+7+56+5=11f2（4）=min d(4,5)+

42、d(4,5)+f3（5）d(4,6)+d(4,6)+f3（6）d(4,7)+d(4,7)+f3（7）=min7+7+78+8+59+5=11 相应决策为相应决策为：u*2(4)=6。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用37v则由城市则由城市1到终点到终点10最短距离为最短距离为17，决策为，决策为u*1(1)=2。f1（1）=min d(1,2)+d(1,2)+f2（5）d(1,3)+d(1,3)+f2（3）d(1,4)+d(1,4)+f2（4）=min8+8+99+9+115+13=17v 再按计算顺序反推可得最优决策序列再按计算顺序反推可得最优决策序列 uk，即，即u*

43、1(1)=2，u*2(2)=6，u*3(6)=9，u*4(9)=10v 货物运输最优路线为：货物运输最优路线为：城市城市1城市城市2 城市城市6 城市城市9城市城市10。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用38第一步：打开第一步：打开“动态规划动态规划-DP.EXE”软件界面，点击软件界面，点击(Stagecoach,最短路径）输入标题，城市数目，如下图。最短路径）输入标题，城市数目，如下图。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用39广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用40广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用41 【

44、例例4.3】某厂要确定某厂要确定一种新产品在今后五年一种新产品在今后五年内的价格，并已拟定只内的价格，并已拟定只在在5，6，7，8元这四种元这四种单价中进行选择。据预单价中进行选择。据预测，今后五年不同价格测，今后五年不同价格下每年盈利（万元）如下每年盈利（万元）如表表1所示，但是各相邻年所示，但是各相邻年度价格增减不得超过度价格增减不得超过1元。元。问今后五年内每年定价问今后五年内每年定价各为多少，可预期五年各为多少，可预期五年总利润最大？总利润最大？广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用42（1）求最长路线，最后结果如图。）求最长路线，最后结果如图。广东轻工职业技术广东轻

45、工职业技术学院学院动态规划及其应用43动态规划及其应用44（1）定价问题是求最长路线问题，因而函数基本方程为）定价问题是求最长路线问题，因而函数基本方程为取最大值而非最小值；取最大值而非最小值；（2）最短路线问题，始点和终点均为固定，而定价问题）最短路线问题，始点和终点均为固定，而定价问题则始点和终点均不固定，因此最后在始端还要再决策一则始点和终点均不固定，因此最后在始端还要再决策一次。由次。由3838,36,35,37max 确定第一年定价为确定第一年定价为8元，从而最优定价策略为：元，从而最优定价策略为：5,6,7,8,80p广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用45 即

46、：前两年定价为即：前两年定价为8元，以后逐年降低元，以后逐年降低1元，这样能使今元，这样能使今后五年预期盈利最大，为后五年预期盈利最大，为38万元；万元；最短路线问题每个点到下面相邻几个点的距离一般不等；最短路线问题每个点到下面相邻几个点的距离一般不等；定价问题则均相等（即某年、某价格下的预计盈利额）；定价问题则均相等（即某年、某价格下的预计盈利额）；这里的定价问题实际上是一种特殊的最优路线问题。这里的定价问题实际上是一种特殊的最优路线问题。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用46 某厂估计某一种新产品未来四年内每年在不同价格下某厂估计某一种新产品未来四年内每年在不同价格下

47、的期望利润（万元的期望利润（万元)如下表所示。如果相邻两年间价格调如下表所示。如果相邻两年间价格调整幅度：整幅度：（1）不超过）不超过2元；元；（2）不超过）不超过4元；元；（3）无任何限制；）无任何限制；试就这三种情况分别确定各年最优定价？试就这三种情况分别确定各年最优定价？广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用47广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用48最优定价策略为最优定价策略为：元元，元，元，162016220p万元250f广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用49最优定价策略为最优定价策略为：元元，元，元，162016220p元

48、元，元，元，162016200p万元310f广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用50最优定价策略为：最优定价策略为：元元，元，元，162016220p万元330f广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用51 动态规划提供了一种优秀的决策思想：战略上追求全动态规划提供了一种优秀的决策思想：战略上追求全局优化，战术上稳扎稳打、步步为营。局优化，战术上稳扎稳打、步步为营。深刻地揭示了局部与全局的统一关系。深刻地揭示了局部与全局的统一关系。动态规划在实际中得到广泛应用，如何应用于背包问动态规划在实际中得到广泛应用，如何应用于背包问题，资源分配问题、生产与存储问题、设

49、备更新问题等。题，资源分配问题、生产与存储问题、设备更新问题等。另外，需要指出的是：动态规划是一种求解思路，注另外，需要指出的是：动态规划是一种求解思路，注重决策过程，而不是一种算法，不同的问题模型各异，重决策过程，而不是一种算法，不同的问题模型各异，需要具体问题，具体分析求解。需要具体问题，具体分析求解。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用52 旅游背包问题在物流方面表现为货物配装问题，如旅游背包问题在物流方面表现为货物配装问题，如储运仓库（或货运车站）整装零担车内装有多种货储运仓库（或货运车站）整装零担车内装有多种货物，要把各个客户所需要的零担货物组成整车，通物，要把各

50、个客户所需要的零担货物组成整车，通过铁路运往各地，货车装载能力一定，如何配装实过铁路运往各地，货车装载能力一定，如何配装实现价值最大化。现价值最大化。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用53 背包问题背包问题用动态规划方法求解只有一个约束条件（一维背用动态规划方法求解只有一个约束条件（一维背包问题）的整数规划最优解，即背包只有重量或体积限制。包问题）的整数规划最优解，即背包只有重量或体积限制。设数学模型为：设数学模型为：nnxcxcxcMaxZ2211nixWxwxwxwnn,2,102211且为整数，S.t.动态规划及其应用54广东轻工职业技术广东轻工职业技术学院学院动态

51、规划及其应用55【例【例4-3】假设有假设有4种货物种货物A、B、C、D，其中，其中A有有2件，件，每件重每件重6t，B有有1件，每件重件，每件重20t，C有有3件，每件重件，每件重11t，D有有2件，每件件，每件19t，如表，如表4-3所示。货车车厢的载重量上限所示。货车车厢的载重量上限为为50t。如何配装，才能充分利用车辆的装载能力。如何配装，才能充分利用车辆的装载能力。表表4-3 四种货物资料四种货物资料货物种类货物种类ABCD件数件数/件件2132每件重量每件重量/t6201119广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用56 1、阶段的划分和计算、阶段的划分和计算 货物

52、配装可以设定：装入一种货物看做一个阶货物配装可以设定：装入一种货物看做一个阶段，把货物配装问题化为动态规划问题。本例段，把货物配装问题化为动态规划问题。本例题题4种货物配装过程划分为四个阶段。种货物配装过程划分为四个阶段。采用逆推法采用逆推法，第，第1阶段分析装入货物阶段分析装入货物D的数量。的数量。把货物把货物D的件数折算成重量，用的件数折算成重量，用G1表示，共表示，共2件，件，每件重量为每件重量为19t。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用57 第第1阶段阶段的状态有三种：的状态有三种：0、19和和38。输入状态。输入状态为车辆可能的载重能力，此时状态为为车辆可能的载

53、重能力，此时状态为W=50。对于对于3种决策：种决策：G1=0、19、38，有，有3个余量：个余量：W-G1=50、31、12。见表见表4-4。本阶段的余量将作为第本阶段的余量将作为第2阶段的阶段的“输入状态输入状态”。表表4-4 第第1阶段计算表阶段计算表阶段阶段1输输入状态入状态决策：装入货物决策：装入货物D的重的重量（按件折算）量（按件折算）最优方案最优方案01938余量余量状态状态505031121238广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用58 第第2阶段阶段决策时分析装入货物决策时分析装入货物C的数量，用的数量，用G2表示。表示。此阶段的输入状态时第此阶段的输入状

54、态时第1阶段的阶段的3个余量，即个余量，即W=50、31、12。因为每件货物因为每件货物C重量为重量为11，共，共3件，所以决策有件，所以决策有4种状态可供分种状态可供分析，即析，即G2=0、11、22、33。本阶段的余量为本阶段的余量为WG2=50、39、28、17、31，见表见表4-5。表表4-5 第第2阶段计算表阶段计算表阶段阶段2输入输入状态状态 决策：装入货物决策：装入货物C的重量的重量（按件折算）（按件折算）最优方案最优方案0112233余量余量状态状态505039281717333131209-92212121-111广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用59

55、第第2阶段的余量作为第阶段的余量作为第3阶段的输入状态，继续分析，结果阶段的输入状态，继续分析，结果见表见表4-6。表表4-6 第第3阶段计算表阶段计算表阶段阶段3输入状态输入状态 决策：装入货物决策：装入货物B的重量的重量（按件折算）（按件折算）最优方案最优方案020余量余量状态状态50503030203939191920282888201717-17031311111202020002099-901212-120广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用60阶段阶段1输入状态输入状态决策：装入货物决策：装入货物A的重量（按件折算）的重量（按件折算）最优方案最优方案0612余量

56、余量状态状态5050443838123030241818123939332727131919137712282822161612882-26171711551231312519191211115562020148812993-3612 12 60012广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用61在第在第4阶段计算中，余量阶段计算中，余量WG4最小值为最小值为0，G4=12对应的对应的W值为值为12；第；第4阶段阶段W只对应于第只对应于第3阶段的余量阶段的余量WG3，对应余项，对应余项WG3=12的的G3=0，它们对应的，它们对应的W值分别为值分别为12；查第；查第2阶段计算表，

57、余阶段计算表，余项为项为12时，时，G2=0，W=12；再查第；再查第1阶段计算表，余项为阶段计算表，余项为12 时，时，G1=38。寻找过程表述为：。寻找过程表述为：G4=12 G3=0 G2=0 G1=38即把即把A货物货物12t（2件）和件）和D货物货物38t（2件）配装成一车。这就是所件）配装成一车。这就是所求的最优解。配装重量是求的最优解。配装重量是50t，达到满载，充分利用了货车的装载，达到满载，充分利用了货车的装载能力能力 广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用62 另外，在第另外，在第3阶段计算表中，也出现了一个余量为阶段计算表中，也出现了一个余量为0的项，的

58、项，对应的对应的G3=20，W=20；再查第；再查第2阶段计算表，余量为阶段计算表，余量为20，对应的对应的G2=11，W=31；再查第；再查第1阶段计算表，余项阶段计算表，余项31，对应对应G1=19。这样，也得出另一组最优解为这样，也得出另一组最优解为 G3=20 G2=11 G1=19 对于两组最优解，可根据实际情况进行选择，例如可以对于两组最优解，可根据实际情况进行选择，例如可以优先选用第一组最优解，因为它使优先选用第一组最优解，因为它使A，D两种货物全部配两种货物全部配装。装。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用63 【例【例5】已知已知1吨集装箱最大载重量吨集装

59、箱最大载重量800kg，有，有5种物品各种物品各10件，件，单位物品重量和价值见表单位物品重量和价值见表4-8，求如何装载价值最大？，求如何装载价值最大？表表4-8 单位物品重量和价值单位物品重量和价值物品物品12345物品限量（件）物品限量（件）1010101010单位物品重量（单位物品重量（kg）2015406030单位物品价值（元）单位物品价值（元）4025607050广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用64 用用WinQSB软件求解步骤如下：软件求解步骤如下：调用子程序调用子程序DP，新建问题。在图，新建问题。在图4-3中选择第二项，输入中选择第二项，输入标题和物品

60、数。标题和物品数。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用65 输入数据。按照表输入数据。按照表4-9的形式输入数据，第的形式输入数据，第1列为物品名称，列为物品名称，第第2列为物品限量和集装箱限量，第列为物品限量和集装箱限量，第3列为单位物品重量，第列为单位物品重量，第4列为物品价值函数。列为物品价值函数。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用66 求解。点击菜单栏求解。点击菜单栏 Solve and Analyze Solve the Problem，得到表得到表4-10的结果。的结果。由表由表4-10可以看出，表示可以看出，表示5种物品分别装载种物品分别

61、装载10、9、4、0及及10件，总价值件，总价值1365（元），集装箱还有（元），集装箱还有5kg的剩余能力。的剩余能力。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用67 企业一年中的产品生产往往是分期分批生产的。企业一年中的产品生产往往是分期分批生产的。企业组织每批产品的生产，都要花费一些生产准备费和企业组织每批产品的生产，都要花费一些生产准备费和存贮费用。若某一时期增大生产批量则可减少生产批次，存贮费用。若某一时期增大生产批量则可减少生产批次，从而降低生产成本。从而降低生产成本。与此同时，批量大了，必然增加库存而使存贮费用增加。与此同时，批量大了，必然增加库存而使存贮费用增加。

62、在企业产品的生产成本、存贮费用、市场需求量确定的在企业产品的生产成本、存贮费用、市场需求量确定的情况下，正确计划各时期的生产量，既满足市场需求，情况下，正确计划各时期的生产量，既满足市场需求，又使总支出最少，这是一个多阶段决策问题，也是物流又使总支出最少，这是一个多阶段决策问题，也是物流中的生产与存储问题。中的生产与存储问题。广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用68动态规划及其应用69广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用70广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用71 例例6 某工厂与用户签订了某工厂与用户签订了4个月的交货合同如表所示个

63、月的交货合同如表所示 该厂生产能力为每月该厂生产能力为每月5万件，该厂仓库的存货能力为万件，该厂仓库的存货能力为4万件。万件。已知生产费用为已知生产费用为c=1千元千元/万件，在进行生产的月份，工厂万件，在进行生产的月份，工厂要支出固定费用要支出固定费用b=2千元，每月仓库保管费用千元，每月仓库保管费用h=0.2千元千元/万万件件/月。月。假定开始时及假定开始时及4月底交货后无存货，试问应在每月各生产月底交货后无存货，试问应在每月各生产多少件产品，才能满足交货任务，又使总费用最小？多少件产品，才能满足交货任务，又使总费用最小？月月1234需求量需求量dk(万件万件)3232广东轻工职业技术广东

64、轻工职业技术学院学院动态规划及其应用72 每个月为一个阶段，即阶段变量每个月为一个阶段，即阶段变量 k=1,2,3,4k=1,2,3,4分别表示这四个月分别表示这四个月;状态变量状态变量y yk k 表示第表示第k k 月初的产品库存量，月初的产品库存量，0 y0 yk k 4;4;决策变量决策变量x xk k 表示第表示第k k月的生产量月的生产量 ，允许决策集合允许决策集合X Xk k(y(yk k)=x)=xk k 0 x0 xk k 5;5;状态转移方程为状态转移方程为 y yk+1k+1=y=yk k+x+xk k d dk k;阶段指标阶段指标v vk k(y(yk k,x,xk

65、k)表示第表示第k k 月的费用月的费用 ：本月若不安排生产，则仅：本月若不安排生产，则仅需支出保管费；本月若安排生产，则需支出生产费用和固定费，同时需支出保管费；本月若安排生产，则需支出生产费用和固定费，同时还需交付保管费。还需交付保管费。当当x xk k=0=0时，时，v vk k(y(yk k,x,xk k)=h y)=h yk k=0.2y=0.2yk k当当x xk k 0 0时，时，v vk k(y(yk k,x,xk k)=b+cx)=b+cxk k+hy+hyk k=2+x=2+xk k+0.2y+0.2yk k 最优指数函数最优指数函数f fk k(y(yk k)表示第表示第

66、k k阶段从阶段从y yk k 开始到最后阶段采用最优生产开始到最后阶段采用最优生产策略实现的最低生产费用策略实现的最低生产费用;0)()(),()(5511)(minyfyfxyvyfkkkkkyXxkkkkk边界条件：基本方程：广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用73x4y4v4(y4,x4)=0.2 y4v4(y4,x4)=2+x4+0.2 y4f3(y3)x3*012012-4-3.2-0.4-43.20.4210d4=2，4月末无库存则月末无库存则y5=0，状态转移方程状态转移方程 y5=y4+x4 d4，则则 y4=d4 x4=2 x4x40,则则y4=2 x4=0,1,2y40,则则x4=2 y4=0,1,2广东轻工职业技术广东轻工职业技术学院学院动态规划及其应用74x3y30.2 y3+f4(y4)v3(y3,x3)+f4(y4)=2+x3+0.2 y3+f4(y4)f3(y3)x3*012340123457.46.65.84.64.254300-9.09.27.4-8.28.46.6-7.47.65.8-4.66.85.0-44.2-d3=3，0y