清华大学运筹学6动态规划

1、第七章第七章 动态规划动态规划第一节第一节 多阶段决策过程优化多阶段决策过程优化第二节第二节 基本概念和原理基本概念和原理第三节第三节 模型与求解模型与求解第四第四节节 在管理中应用在管理中应用1/151第七章第七章 动态规划动态规划n是是优化优化多阶段决策过程的多阶段决策过程的一种方法一种方法。1957年年，美国数学家贝尔曼美国数学家贝尔曼(R. Bellman) 发表发表了了该领域第一本专著该领域第一本专著动态规划动态规划(Dynamic Programming)。n用于用于解决最优解决最优路径、资源分配、生产与路径、资源分配、生产与库库存、投资、装载、排序存、投资、装载、排序等等以以及过

2、程最优控及过程最优控制等制等问题问题。思路独特，。思路独特，对于对于某些问题，某些问题，比比线性或线性或非线性规划非线性规划方法有效。方法有效。2/1513/151Born: 26 August 1920 in Brooklyn, New York CityDied: 19 March 1984 in Los Angeles Richard Ernest Bellman completed his doctoral studies in Princeton and remained there as Assistant Professor of Mathematics after the aw

3、ard of his doctorate but in 1948 he left to take up the position of Associate Professor of Mathematics at Stanford University. During the following summer he worked at RAND.n动态规划动态规划模型的分类模型的分类：n离散确定型离散确定型；n离散随机型离散随机型；n连续确定型连续确定型；n连续连续随机型。随机型。n本章主要本章主要介绍介绍离散确定型，思想离散确定型，思想、原理和、原理和方法方法，为解决为解决其他类型问题其他类型

4、问题打基础打基础。4/151第一节第一节 多阶段决策过程最优化多阶段决策过程最优化 有些有些过程，可按过程，可按先后先后分解分解成成若若干干相互相互联联系系的的“时段时段”，每一时段，每一时段都要都要做出做出的的决策，决策，构构成成一一个个决策决策序列序列，这就是这就是多多阶段决策阶段决策问题。问题。 多阶段决策多阶段决策要要达到整个过程总体效果达到整个过程总体效果最最优。优。某阶某阶段决策影响下段决策影响下阶阶段决策段决策及及总体效果总体效果。 每每一阶一阶段决策段决策，不仅不仅应谋取应谋取本本阶段最优阶段最优，还应，还应考虑考虑对对最终最终目目标标的影响，从而做出对的影响，从而做出对全全局

5、局来讲是最优的决策来讲是最优的决策。5/151 动态规划动态规划就是就是随着时间的随着时间的推移逐段做出推移逐段做出决策。决策。 如果研究对象可分离为若干部分，分别如果研究对象可分离为若干部分，分别考虑，就考虑，就可可视这若干部分为若干时段，用视这若干部分为若干时段，用动态动态规划方法规划方法处理处理之之。 现举例现举例如次如次。6/151例例1 生产与存贮问题生产与存贮问题 某厂某厂每月需供应市场一每月需供应市场一定量产品，余定量产品，余者者存存入入仓库。仓库。一般一般说来，各说来，各月月适当适当增加增加产量可降低产量可降低生产成本，生产成本，但存但存入入仓库仓库会增加库存费用会增加库存费用

6、。如何如何安排各安排各月产月产量量，才能既才能既满足满足市场市场需求，需求，又减少又减少全全年生产年生产与与存存储储费用费用总总和和呢？呢？ 可逐月可逐月考虑，但要顾及考虑，但要顾及全年全年生产与存生产与存储储费费用用总总和。和。7/151例例2 投资决策问题投资决策问题 某公司有某公司有资金资金Q万元万元，今后，今后5年年要投入要投入A、B、C和和D四四个项目个项目。各。各项项目目投资回收期投资回收期和收和收益率益率不同不同，问问：如何如何安排各安排各年投资额，年投资额，才能才能使使第第5年末年末的的资金总额资金总额最大。最大。 该问题可按该问题可按5阶段阶段决策决策问题问题处理处理。8/1

7、51例例3 设备更新问题设备更新问题 设备越设备越到后来，到后来，维修费越多维修费越多。但买但买新新设备设备一次性一次性支出支出较较多多。企业要。企业要制订制订一一台设备未来台设备未来8年的更新年的更新计划计划。经。经预测预测，第第j年的年的买买价为价为Kj，设设Gj为为用用过过j年后的残值年后的残值，Cj为连续用为连续用j-1年年后后第第j年的维修费年的维修费(j=1，2，8)，问问：哪哪一一年年更新总更新总费用费用最小最小？ 可视为可视为8阶段决策问题，每年年初要做出阶段决策问题，每年年初要做出决决定定，是是继续用，继续用，还是购买还是购买新新的的。9/151第二节第二节 动态规划基本概念

8、和原理动态规划基本概念和原理一一、基本、基本概念概念 用用动态规划模型动态规划模型表达和解决表达和解决实际问题实际问题，要要用用到以下概念：到以下概念：(1)阶段；阶段；(2)状态；状态；(3)决策和决策和策略策略。 下面下面以实例以实例说明说明之之。10/15111/151例例4 最短路线问题最短路线问题 要要从从A向向F铺铺输油管道，输油管道，问问管线如何走，管线如何走，总总长度才长度才最短最短？线线上的数字表示上的数字表示距离距离。(1)阶段阶段 将将过程或整体过程或整体，按时间或按时间或空间分解空间分解成若干成若干互相联系互相联系的的时时段段或部分或部分，以便，以便逐一逐一求解，用求解

9、，用k表示阶段表示阶段(k=1, 2, , 5)。从。从A到到F可分可分5阶段阶段，每一阶段之初都有多个选择。每一阶段之初都有多个选择。 请注意，并不是所有的问题都能分解。请注意，并不是所有的问题都能分解。12/15113/151(2)状态状态 用用sk表示表示各各阶段阶段开始状态开始状态，称为状态变量称为状态变量。 sk取值取值全体全体称为称为状态集合，状态集合，用用Sk表示表示。 当当某某阶段阶段sk给给定后，以后定后，以后过程的过程的发发展不展不受受该阶段该阶段以前各以前各阶阶段段状态的影响状态的影响。当前状态。当前状态是过是过去历史的一个完整总结，去历史的一个完整总结，过程的历史过程的

10、历史只能通过只能通过当前当前状态影响未来状态影响未来的发展的发展，该性质该性质称为称为无后效无后效性性。不具备后效性的变量不能充当状态变量。不具备后效性的变量不能充当状态变量。14/151在在例例4中中， S1=A， S2=B1，B2 S3=C1, C2, C3, C4 S4=D1, D2, D3 S5=E1, E2当当某某段初始状态段初始状态已已选定时选定时，从这个点以后的铺，从这个点以后的铺管路线只与该点有关，不受管路线只与该点有关，不受以前以前的铺管路线影的铺管路线影响，所以满足状态的无后效性。响，所以满足状态的无后效性。15/15116/151整个决策序列构成策略整个决策序列构成策略，

11、用，用p1, nu1(s1), u2(s2), , un(sn)表示表示。可选策略可选策略全体全体称为称为允许策略允许策略集合，记作集合，记作P1, n，使使整整体体效果最优的效果最优的策略是策略是最最优策略优策略。 (4)状态转移方程状态转移方程 本阶段状态是本阶段状态是上上阶段阶段状态状态和决策和决策的的结果。结果。若已知若已知第第k段状态段状态sk和和uk(sk)，则，则第第k+1段状态段状态sk+1也就确定，可表示也就确定，可表示为为： sk+1=Tk(sk, uk) (7-1)，称为，称为状态状态转移方程转移方程。 例例4中，状态转移方程为中，状态转移方程为：sk+1=uk(sk)1

12、7/151(5)指标函数指标函数 衡量策略衡量策略优劣的优劣的数数值值称为称为指标函数指标函数。阶段阶段指标指标函数指第函数指第k段从状态段从状态sk出发出发，决策决策为为uk时时的的效效果果，用用d(sk, uk)表示表示。 从从1到到n叫做原叫做原过程过程，从第，从第k(1kn)段段到到第第n段段的过程称为原的过程称为原过程后部过程后部子过程子过程。 V1, n(s1, p1, n)表示表示初始状态为初始状态为s1，用用策略策略p1, n时时，原，原过程指标过程指标函数值函数值，Vk, n(sk, pk, n)表示表示k阶阶段段状态状态为为sk，用用策略策略pk, n时时，后部后部子子过程

13、指标过程指标函数值函数值。18/15119/151二、二、动态规划基本动态规划基本思想思想与原理与原理 求最短路线，求最短路线，可可求从求从A至至F的的所有所有可能可能铺铺设设的的长度，然后长度，然后比较。当段数比较。当段数和和各段状态各段状态都都很很多多时，穷举时，穷举法法效率低效率低。 动态规划方法动态规划方法，从过程最后从过程最后一段开始一段开始，逆，逆序递推，序递推，逐步求出各逐步求出各段段、各各点到终点点到终点F的最短的最短路线，路线，最后求得最后求得A到到F的的最短路线。最短路线。 第第1步，从步，从k=5开始开始，s5可取可取E1和和E2，到到F点点的的距离分别为距离分别为4，3

14、。即。即： f5(E1)=4， f5(E2)=320/151第第2步，步，k=4，s4可取可取D1，D2和和D3，从，从D1到到F点点有两条路线，取最短者有两条路线，取最短者： f4(D1)=min d(D1, E1)+f5(E1) = 3+4 =7 d(D1, E2)+f5(E2) 5+3 相应决策相应决策为为u*4(D1)=E1。 f4(D2)=min d(D2, E1)+f5(E1) = 6+4 =5 d(D2, E2)+f5(E2) 2+3u*4(D2)=E2。 f4(D3)=min d(D3, E1)+f5(E1) = 1+4 =5 d(D3, E2)+f5(E2) 3+3u*4(D

15、3)=E1。 21/151类似地类似地，k=3时时， f3(C1)=12，u*3(C1)=D1。 f3(C2)=10，u*3(C2)=D2。 f3(C3)=8， u*3(C3)=D2。 f3(C4)=9， u*3(C4)=D3。k=2时时，有有 f2(B1)=13，u*2(B1)=C2。 f2(B2)=15，u*2(B2)=C3。k=1时时，有有f1(A)=min d(A, B1)+f2(B1) = 4+13 =17 d(A, B2)+f2(B2) 5+15u*1(A)=B1。 22/151 再再按按计算计算顺序顺序反反求求最最优决策优决策序列，即序列，即u*1(A)=B1，u*2(B1)=C

16、2，u*3(C2)=D2，u*4(D2)=E2，u*5(E2)=F。最短路线是最短路线是AB1C2D2E2F。 求解各阶段，都用了如下关系：求解各阶段，都用了如下关系： fk(sk)=min dk(sk, uk)+fk+1(sk+1) (7.3a) uk k=5, 4, 3, 2, 1 f6(s6)=0 (7.3b)23/151 (7.3a)称为称为动态规划基本方程动态规划基本方程，(7.3b)称为终称为终端条件。端条件。 各各结点结点上上方括号内数，方括号内数，是是该该点点到到F最最短距短距离离。连结各点到。连结各点到F的线的线是是最最短路径短路径。 在在图上直接图上直接计算计算，叫标号。叫

17、标号。比比穷举法易算穷举法易算，计算，计算量少量少。段数。段数越多，越越多，越复杂，复杂，越明显。越明显。不不仅仅算算得了得了从从A到到F的最短路线的最短路线，还还得到得到了了中间中间任任一点到一点到F的最的最短路线。短路线。24/15125/151图图7-226/1518838561310810131717若若d(E1, F)由由4改为改为8，标号过程如下。但，标号过程如下。但f(E1)应应当是当是7。请思考之。请思考之。动态规划方法基本动态规划方法基本思想思想总结：总结： (1)为为过程过程划分阶段，划分阶段，恰当选取状态恰当选取状态和和决策决策变量变量，定义定义最优指标最优指标函数，把函

18、数，把问题问题化化为若干为若干同同类型子类型子问题，然后逐个求解。问题，然后逐个求解。 (2)从从终终(始始)端端条件条件开始，逆开始，逆(或顺或顺)过程行进过程行进方向，逐方向，逐段寻段寻优。优。求解求解各各子子问题时，都问题时，都要用要用前前面子问题面子问题已得已得结果，结果，最最后后一个子问题的最优解一个子问题的最优解，就是整个就是整个问题的最优解。问题的最优解。 27/15128/151 动态规划方法动态规划方法的基础是的基础是贝尔曼等贝尔曼等人提出的人提出的最优化最优化原理：原理：“过程最过程最优优策略的性质策略的性质是是：无论：无论初始状态及初初始状态及初始决策如何，对于先前决策所

19、形成的状态而言始决策如何，对于先前决策所形成的状态而言，以后，以后的所有决策应构成最优策略的所有决策应构成最优策略”。 从从例例4（图图7-2）可可知知，无论从哪无论从哪一段一段哪一哪一状态出发状态出发，到终点到终点F的最短路线，只的最短路线，只与与该该状态状态有关，而有关，而与与其其以前状态以前状态、路线无关，、路线无关，即即与与从从A点到达这点到达这一一点点的路线无关的路线无关。 29/151第三节第三节 动态规划模型与求解动态规划模型与求解一一、动态规划模型的建立、动态规划模型的建立 建立基本方程建立基本方程，关键关键是划分是划分阶段，将阶段，将问问题题分解成分解成具有具有递递推推关系的

20、若关系的若干干子子问题，问题，而而查明查明递递推推关系的关系的关键又关键又在于选择在于选择状态变量状态变量，明确明确各各阶阶段状态转移关系段状态转移关系sk+1=Tk(sk, uk) 。 资源分配问题是动态规划典型应用资源分配问题是动态规划典型应用，可，可用于用于介绍动态规划建介绍动态规划建模模条件及解法。条件及解法。30/151例例5 现有现有10万万元元，第，第i个项目个项目投投入入xi时，收益为时，收益为g1(x1)=4x1；g2(x2)=9x2； g3(x3)=2x23。如何分如何分配配，总收益总收益才才最最多多? Max z=4x1+9x2+2x23 s.t. x1+x2+x3=10

21、， x1, x2, x3 0 按动态规划求解。按动态规划求解。先先在在项项目目1投资，投资，然后然后在在项目项目2，每每次次只只考虑一个考虑一个项目项目。 下面选择下面选择状态变量状态变量，找出找出各各后部子过程后部子过程之之间递间递推关系。推关系。31/151 可可以以原原NLP问题变量问题变量xk为决策变量为决策变量uk，即即设设 uk=xk (k=1，2，3) 状态和决策变量关系状态和决策变量关系密切密切，状态变量，状态变量一一般般为累计量或为累计量或随随着着递推变化递推变化。 可可以各以各阶段可用资金为状态变量阶段可用资金为状态变量sk，初始，初始状态状态s1=10。32/151 u1

22、为为项项目目1可用资金，第可用资金，第1阶段阶段(k=1)，有，有s1=10， u1=x1， 第第2阶段阶段(k=2)，s2为为余下可余下可投投入入其余其余两两个个项目的资金，即项目的资金，即 s2=s1-u1，u2=x2， 一般一般地地，第，第k阶段，有阶段，有sk=sk-1-uk-1，uk=xk， 于是，于是，阶段阶段k， k=1，2，3状态变量状态变量sk：第：第k阶段可投阶段可投入入第第k到第到第3个项目个项目的资金。的资金。决策决策变量变量xk：投入第：投入第k个个项目的资金。项目的资金。33/15134/151 一般一般地，建立动态规划模型的要点为：地，建立动态规划模型的要点为：

23、1. 分析分析题意，识别题意，识别问题问题各各阶段，按时空顺阶段，按时空顺序适当划分满足递序适当划分满足递推推关系关系的的若若干干阶段阶段或部分或部分。 2. 正确正确的的状态变量状态变量应有应有两个特征两个特征： (1)能能直直接或接或间接确定各阶段取值；间接确定各阶段取值； (2)能能反映反映过程演变且过程演变且无无无后效无后效性。即由性。即由第第k阶段状态阶段状态sk出发出发的的后部后部子过程，子过程，可可视为视为以以sk为为初始状态的独立过程初始状态的独立过程。35/151 这这一点一点并并非非每个每个问题问题都容易满足。都容易满足。 3. 写出写出状态状态转移方程转移方程 sk+1=

24、Tk(sk, uk)或转移或转移规则规则。 4. 明确明确指标指标函数函数Vk,n，最最优指标优指标函数函数fk(sk)以及阶段指标以及阶段指标vk(sk, uk)的含义的含义，列出，列出最优指标最优指标函数的递推关系函数的递推关系及及终端终端条件条件(即基本方程即基本方程)。 此外，此外，需经验与需经验与熟练熟练地地运用最优化原理。运用最优化原理。36/15137/151k012453二、逆序与顺序解法二、逆序与顺序解法 逆序逆序（顺序顺序）解法寻优方向与过程行进方解法寻优方向与过程行进方向向相反（相反（相同相同）。 例例4的的顺序解法计算顺序解法计算步骤如下步骤如下：k=0， f0(s0)

25、=f0(A)=0，这是初始条件。，这是初始条件。k=1， f1(s1) f1(B1)=4， u1(B1)=A f1(B2)=5， u1(B2)=A38/151k=2， f2(s2) f2(C1)=d(B1, C1)+f1(B1)=2+4=6 u2(C1)=B1 f2(C2)=min d(B1, C2)+f1(B1) = min 2+4 =6 d(B2, C2)+f1(B2) 8+5 u2(C2)=B1， f2(C3)=min d(B1, C3)+f1(B1) = min 6+4 =10 d(B2, C3)+f1(B2) 7+5 u2(C3)=B1，39/151 f2(C4)=d(B2, C4)

26、+f1(B2)=7+5=12 u2(C4)=B2k=3， f3(s3) f3(D1)=11，u3(D1)=C1或或C2f3(D2)=12，u3(D2)=C2f3(D3)=14，u3(D3)=C3k=4， f4(s4) f4(E1)=14，u4(E1)=D1f4(E2)=14，u4(E2)=D2k=5， f5(s5) f5(F)=17，u5(F)=E240/15141/151414141112146710124517042/15114141112146710124517按按定义定义知知f5(F)=17为为所求最短路长，而路径则所求最短路长，而路径则为为AB1C2D2E2F，与逆序解法相同。，与逆

27、序解法相同。计算计算过程过程如如图图7-3。图图中节点中节点上方括号内的上方括号内的数数是是该该点点到到A点的最短距离点的最短距离，黑粗线，黑粗线是是该该点到点到A点的点的路径。路径。上述上述解法写成解法写成如如下下递递推推方程方程：fk(sk)=minvk(sk, uk)+fk-1(sk-1)， (7.5a) k=1, 2, 3, 4, 5f0(s0)=0 (7.5b)这里这里，sk=Tk(sk+1, uk)43/151 一般地说一般地说，当给定初始状态时可用逆序解，当给定初始状态时可用逆序解法法，当给定当给定终止状态时终止状态时可用顺序解法可用顺序解法。 若给定了若给定了一一个个初始状态与

28、一个终止状态初始状态与一个终止状态，两种方法两种方法均均可用可用，如例，如例4。 但若虽但若虽已给定初始状态，终点状态有多个已给定初始状态，终点状态有多个，需比较到达不同，需比较到达不同终点的各路径终点的各路径及最优指标函及最优指标函数值，以选取总效益最佳的终点状态时数值，以选取总效益最佳的终点状态时，用顺，用顺序解法较简便。序解法较简便。 总之，总之，应应针对针对问题问题的特点的特点，灵活选用。灵活选用。44/151 上述上述两种两种方法，建模方法，建模时要注意以下区别：时要注意以下区别： 1. 状态状态转移方式不同转移方式不同 如如图图7-4所示，逆序所示，逆序解法第解法第k段段的输入的输

29、入状态状态sk和决策和决策uk确定了确定了sk+1，状态状态转移方程为：转移方程为： sk+1=Tk(sk, uk) (7.6)式式(7.6)称为称为状态状态sk到到sk+1的的顺序转移方程。顺序转移方程。45/15146/151 顺序解法第顺序解法第k段段sk由由sk+1和和uk决定决定，见见图图7-5，状态转移方程，状态转移方程为：为： sk=Tk(sk+1, uk) (7.7)式式(7.7)称逆序称逆序状态状态转移方程转移方程。 逆序逆序解法解法中阶段指标中阶段指标vk(sk, uk)在在顺序解法中顺序解法中应表应表为为vk(sk+1, uk)。 2. 指标指标函数的定义不同函数的定义不

30、同 逆序解法，最逆序解法，最优指标优指标函数函数fk(sk)表示第表示第k段段从从状态状态sk出发出发到终点后部到终点后部子子过程最优效益值过程最优效益值， f1(s1)是是整整体体最优函数值最优函数值。47/15148/15149/15150/15151/151三三、基本方程分段、基本方程分段求解几种求解几种常用算法常用算法 基本基本方程分段求解方程分段求解，须，须视视具体特点，灵活具体特点，灵活求解求解。大体大体有有以下方法以下方法。 1. 离散变量分段离散变量分段穷举算法穷举算法 状态与状态与决策变量决策变量若只取若只取离散值离散值，可用，可用分段分段穷举法穷举法，如，如例例4。求最。求

31、最优优指标函数值指标函数值时时，应应正确正确确定确定各各段段状态变量状态变量取值和取值和允许决策允许决策集合范围集合范围。52/151 2. 连续变量连续变量的解法的解法 状态与决策变量状态与决策变量若若连续，连续，可用可用解析法解析法、线线性性和和非线性规划非线性规划法或其他数值计算方法等。法或其他数值计算方法等。 例例5，状态与，状态与决策变量决策变量均连续，每均连续，每阶段求优阶段求优时不能时不能用穷举法。用穷举法。 (1)逆序逆序解法解法 例例5状态变量状态变量sk为第为第k段初可分配给第段初可分配给第k到到第第3个项目的资金；决策变量个项目的资金；决策变量xk为投为投入入第第k个个项

32、目的项目的资金；状态转移方程资金；状态转移方程为为sk+1=sk-xk，53/151 最最优指标优指标函数函数fk(sk)表示第表示第k阶段，状态为阶段，状态为sk时时，从，从第第k到到第第3个个项目项目的的最大最大收益收益， f1(s1)即即为为所所求总求总收益。递推收益。递推方程方程为：为： fk(sk)= max gk(xk)+fk+1(sk+1) k=3, 2, 1 0 xk sk f4(s4)=0k=3 f3(s3)= max 2x23= 2s23 0 x3 s3k=2 f2(s2)= max 9x2+f3(s3) 0 x2 s2 = max 9x2+2(s2-x2)2 0 x2 s

33、254/151令令h2=9x2+2(s2-x2)2，由，由dh2/dx2=9-4(s2-x2)=0，得，得x2=s2-9/4，而，而d2h2/dx22=40，所以，所以x2=s2-9/4是极是极小点。极大值只能在小点。极大值只能在x2=0或或x2=s2处取得。处取得。 f2(s2)|x2=s2 = 9s2 f2(s2)|x2=0 = 2s22当当f2(s2)|x2=s2 = f2(s2)|x2=0时，时，s2=9/2当当s29/2时时， f2(s2)|x2=s2 f2(s2)|x2=0，x*2=0当当s2 f2(s2)|x2=0，x*2=s255/151 k=1 f1(s1)= max 4x1

34、+f2(s2) 0 x1s1当当f2(s2)=9s2时，时， f1(10)= max 4x1+9s1-9x1 0 x110= max 9s1-5x1=9s1 ， x*1=0 0 x110但此时，但此时，s2=s1-x1=10-0=109/2，与，与s20，故，故x1=s1-1是是极小点。极大值只极小点。极大值只能在能在x1=0或或x1=s1=10处处取得。取得。 f1(s1)|x1=0 =2s21=200， f1(s1)|x1=10 = 40所以，所以， x*1=0，s2=s1-x*1=s1=10，因，因s29/2，所以，所以 x*2=0；s3=s2-x*2=s2=10，所以，所以， x*3=

35、s3=10全部全部资金投于第资金投于第3个项目个项目，收益，收益为为200万元。万元。57/151(2)顺序解法顺序解法 令可令可投入投入第第1到第到第k个个项目的金额项目的金额为为sk，则则状态转移方程为：状态转移方程为： s3=10，s2=s3-x3，s1=s2-x2， s0=s1-x1即即 sk=sk+1-xk+1， 令令投入投入第第1到到第第k个个项目项目的总的总额为额为sk时的时的最最大大总收益为总收益为fk(sk) 。基本基本方程为方程为： fk(sk)= max gk(xk)+fk-1(sk-1) k=1, 2, 3 0 xksk f0(s0)=0表示未投资时的最大收益。表示未投

36、资时的最大收益。58/151k=1 f1(s1)= max g1(x1)+f0(s0) 0 x1s1 = max 4x1= 4s1， x*1=s1 0 x1s1 k=2 f2(s2)= max 9x2+f1(s1) 0 x2s2 = max 9x2+4(s2-x2) 0 x2s2 = max 5x2+4s2=9s2， x*2=s2 0 x2s259/151k=3 f3(s3)= max 2x23+f2(s2) 0 x3s3 = max 2x23+9(s3-x3) 0 x3s3令令h(s3, x3)=2x23+9(s3-x3)dh(s3, x3)/dx3 =4x3-9=0，x3=9/4d2h(s

37、3, x3)/dx23 =40，x3=9/4为极小点，极大值为极小点，极大值应当在应当在x3=0或或x3=10处取得。处取得。f3(s3)|x3=0= 9s3，f3(s3)|x3=10=200， x*3=10， s2=s3 -x*3=10-10=0， s2=s3-x*3=s3-s3=0， s1=s2-x*1=s2-s2=0，60/151最最优投资方案与逆序解法结果相同，只投资于优投资方案与逆序解法结果相同，只投资于项项目目3，最大收益为，最大收益为200万元万元 对本对本例例而言而言，顺序解法比逆序解法简单。，顺序解法比逆序解法简单。61/15162/151状态转移方程：状态转移方程： sk+

38、1=sk-xksk与与xk是连续变量是连续变量。gk(xk)若若较复杂，较难求出较复杂，较难求出fk(sk)。常把连续变量离散化常把连续变量离散化，求数值解求数值解。具体。具体做法如下：做法如下：(1)令令sk=0，2，m=a， 大大小可小可依据依据要求的精度定。要求的精度定。(2)规定规定状态变量状态变量sk及决策变量及决策变量xk只只取取离散离散值值，递递推方程就推方程就变为变为： fk(sk)= max gk(p)+fk+1(sk-p) p=0, 1, , q fn+1(sn+1)=0其中，其中，q=sk, xk=p。63/151(3)按按逆序逆序解解法法，逐步递，逐步递推求推求fn(s

39、n)，fn-1(sn-1) ， f1(s1)，最后求最后求出出最优最优资金资金分配方案。分配方案。 现举例说明。现举例说明。 Max z=4x1+9x2+2x23 s.t. x1+x2+x3=10， x1, x2, x3 0解解 令令=2，则状态空间，则状态空间Sk=0, 2, 4, 6, 8, 10，决策集合为决策集合为0 xksk，64/151递递推推方程为方程为： fk(sk)= max gk(xk)+fk+1(sk-xk) 0 xksk f4(s4)=0k=3，f3(s3)= max 2x23，计算结果见表，计算结果见表7-1。 0 x3s3表表7-165/151s30246810f3

40、(s3)083272128200 x*30246810k=2，f2(s2)= max 9x2+f3(s2-x2) 0 x2s2表表7-266/151s20246x20 0 2 0 2 4 0 2 4 6g2+f30 8 18 32 26 3672 50 44 54f2(s2)0 18 3672x*20 2 4 0s30246810f3(s3)083272128200 x*30246810s2 810 x20 2 4 6 8 0 2 4 6 8 10g2+f3128 90 68 62 72 200 146 108 86 80 90f2(s2)128200 x*2 0 0s30246810f3(s

41、3)083272128200 x*30246810s2 810 x20 2 4 6 8 0 2 4 6 8 10g2+f3128 90 68 62 72 200 146 108 86 80 90f2(s2)128200 x*2 0 0k=1，f1(s1)= max 4x1+f2(s1-x1) 0 x110表表7-367/151s20246x20 0 2 0 2 4 0 2 4 6g2+f30 8 18 32 26 3672 50 44 54f2(s2)0 18 3672x*20 2 4 0s110 x10246810g1+f220013688605040f1(s1)200 x*10最最优决策为

42、优决策为：x*1=0， x*2=0， x*3=10，最最大大收收益益为为f1(s1)= 200，与例，与例5结论相同结论相同。 该该法法会会丢失丢失最优解，最优解，一般一般只是只是近似解近似解。68/15169/151设状态变量为：设状态变量为：sk=(Xk, Yk)，Xk：用于生产第：用于生产第k至至n种产品的第种产品的第1种资源量；种资源量；Yk：用于生产第用于生产第k至至n种产品的种产品的第第2种种资源量资源量；设决策变量设决策变量为为：uk=(xk, yk)，xk：用于生产第：用于生产第k种种产品的第产品的第1种资源量；种资源量；yk：用于生产第：用于生产第k种种产品的第产品的第2种资

43、源量；种资源量；状态转移方程为：状态转移方程为：Xk+1= Xk - xkYk+1= Yk - yk70/151允许决策集合为：允许决策集合为：Dk(Xk, Yk)=(xk, yk)|0 xkXk，0ykYk 最优指标函数最优指标函数fk(Xk, Yk)表示表示分配分配于于第第k种种产品至产品至第第n种种产品产品的两种资源分别为的两种资源分别为Xk和和Yk时的最大收时的最大收益。益。基本基本递推方程为递推方程为：fk(Xk, Yk)= max gk(xk, yk)+fk+1(Xk+1-xk, Yk-yk) 0 xkXk 0ykYk k=n, n-1, , 2, 1 fn+1(Xn+1, Yn+

44、1)=071/15172/15173/151第四节第四节 动态规划动态规划在管理在管理中中应用应用 本节本节介绍介绍一些例子。一些例子。一一、背包、背包问问题题 登山背包有登山背包有n种种物品物品要要装，装，但最多但最多装装a公公斤斤，第，第i种单种单件件重重ai公斤公斤，价值，价值ci(xi)(表明表明本物本物品对品对登山重要性登山重要性)是是件件数数xi的函数的函数 (i=1, 2, , n)，问如何选问如何选装装各种物品件各种物品件数数，使，使总价值最大总价值最大?74/15175/151允许决策集合为：允许决策集合为：Dk(sk)=xk|0 xksk/ak, xk为整数为整数 最优指标

45、函数最优指标函数fk(sk)表示背包允许装入物品总重表示背包允许装入物品总重量不超过量不超过sk公斤，按最优策略装前公斤，按最优策略装前k种种物物品品时时的的最大价值。顺序最大价值。顺序递递推方程为：推方程为：fk(sk) = max ck(xk)+fk-1(sk-akxk) xk=0,1,sk/ak k=1,2,nf0(s0)=0，表示未装入物品时最大价值。，表示未装入物品时最大价值。76/151用用顺序解顺序解法逐步算出法逐步算出f1(s1)， f2(s2)， fn(sn)及相应的决策及相应的决策x1(s1)，x2(s2)， ， xn(sn)，最后最后得到得到的的fn(a)即为所求最大价值

46、。最优策略即为所求最大价值。最优策略反反向向推出推出。 当当xi仅仅表示装入表示装入(取取1)和不装和不装(取取0)第第i种物品种物品，则本模型，则本模型就是就是0-1背包问题。背包问题。77/151例例7 货运量货运量10t的卡车的卡车，可可装装3种货物，每种货物，每种单种单位位重量重量及价值如及价值如下下表。如何装载总表。如何装载总价值最大价值最大? 设第设第i种种货物装载的件数货物装载的件数为为xi(i=1, 2, 3)，则问题，则问题可表为：可表为： Max z =4x1+5x2+6x3 s.t. 3x1+4x2+5x3 10 xi 为为非负非负整数整数 (i=1, 2, 3)78/1

47、51货物编号货物编号123单件重单件重t345单位价值单位价值456是是离散决策变量，离散决策变量，可列表求解可列表求解当当k=1时，时，f1(s1) = max 4x1+f0(s0)或或 03x1s1取整数取整数 f1(s1) = max 4x1+f0(s0)=4s1/3 0 x1s1/3取整数取整数79/151s1012345678910f1(s1)0004448881212x*100011122233当当k=2时，时，f2(s2) = max 5x2+ f1(s2-4x2) 0 x2s2/4整数整数80/151s2012345x200000 10 1c2+f100044545f2(s2)

48、0004 5 5x*20000 1 1s1012345678910f1(s1)0004448881212x*100011122233s2678910 x20 10 10 1 20 1 20 1 2c2+f18 58 98 9 1012 9 1012 13 10f2(s2)8 9 1012 13x*20 1 2 0 1s2012345x200000 10 1c2+f100044545f2(s2)0004 5 5x*20000 1 1s2678910 x20 10 10 1 20 1 20 1 2c2+f18 58 98 9 1012 9 1012 13 10f2(s2)8 9 1012 13x*

49、20 1 2 0 1k=3，f3(s3) = max 6x3+ f2(s3-5x3) x3=0,1,2 = max f2(10), 6+f2(5), 12+f2(0) = max 13, 11, 12=13， x*3=0逆推逆推，可得全部策略为可得全部策略为：x*3=0， x*2=1， x*1=2。 当当约束条件两个以上时约束条件两个以上时，就是多维背包问就是多维背包问题题，解法与本例相似解法与本例相似，但状态变量是多维的。但状态变量是多维的。81/151二、生产经营问题二、生产经营问题例例8 生产与存储问题生产与存储问题某厂生产并销售某种产品某厂生产并销售某种产品，今后今后四个月需求量四个月

50、需求量预测如表预测如表7-7。每月生产每月生产j单位产品的单位产品的费用费用为：为： C(j)=0 j=0 =3+j (千元千元) j=1, 2, 3, 4, 5, 682/151i(月月)1234gi232 4月库存费月库存费E(j)=0.5j(千元千元)，最大，最大库容库容3单位单位，月，月最多最多产产6单位单位，期初期初和期末库存都是和期末库存都是零。零。试试订订四四个月计划，个月计划，既既满足需求满足需求，总费用总费用又又最小。设最小。设第第i+1月库存是第月库存是第i月月可可售售量量与需求量与需求量gk之之差；而差；而第第i月月可可售量是月初库存量售量是月初库存量sk与产量与产量uk

51、之之和。和。(1)阶段：阶段：每月每月为为一阶段，一阶段，k=1, 2, 3, 4。(2)状态变状态变量：量：sk为第为第k月初库存量月初库存量。(3)决策变决策变量量： uk为第为第k 月产量月产量。(4)状态转移方程状态转移方程：sk+1=sk+uk-gk83/151(5)最最优优指标指标函数函数fk(sk)表示第表示第k月月初库存初库存sk时，按时，按最佳策略生产，从该月到第最佳策略生产，从该月到第4月末月末最低最低生产生产与与存存贮贮费费用。用。考虑考虑k=4，因因4月月末末库存库存应应为为零零，该该月需求月需求4，故故u4=4-s4，最大库，最大库容容为为3，s4只能取只能取0, 1

52、, 2, 3。f4(s4)=minC(u4)+E(s4)，f4(s4)与与u4(s4)如如下下表。表。表表7-884/151s40123f4(s4)76.565.5u4(s4)4321k=3， s3与与库库容、产能和容、产能和需求需求有关有关，在此，由在此，由库库容容量决定：量决定：s3=0, 1, 2, 3。u3至少为至少为g3-s3=2-s3，若，若s3大大于于2，则则u3应取应取0。为。为保证期末保证期末库存库存为为0，u3不能超过不能超过g3+g4-s3=6-s3，另外，另外，u3不能超不能超库库容容量量3，即不能超过即不能超过g3+3-s3=5-s3，也不能超产能，也不能超产能6，总

53、之，有，总之，有max0, 2-s3u3 min6, 5-s3, 6-s3的整数的整数f3(s3)=minC(u3)+E(s3)+f4(s3+u3-g3)85/151对对s3=0, 1, 2, 3求出求出f3(s3)，当，当s3=0时，时，f3(0)=min(3+u3)+0.50+f4(u3-2)， 2u35 u3=2: 5+7 = min u3=3: 6+6.5 = 12， u*3(0)=2, u3=4: 7+6 u3=5: 8+5.5这就是说，若这就是说，若第第3月初月初库存为零，库存为零，则则3、4二二月月最最低低费用费用为为12（千元），（千元），第第3月最月最优产量为优产量为2单位单

54、位。见见表表7-9。86/151s40123f4(s4)76.565.5u4(s4)4321当当s3=1时，时，f3(1)=min(3+u3)+0.51+f4(u3-1)， 1u34 u3=1: 4+0.5+7 = min u3=2: 5+0.5+6.5 = 11.5， u*3(1)=1, u3=3: 6+0.5+6 u3=4: 7+0.5+5.5这就是说，若这就是说，若第第3月初月初库存库存为为1，则，则3、4二二月月最最低低费用费用为为11.5（千元），（千元），第第3月最月最优产量优产量为为1单单位。位。87/151s40123f4(s4)76.565.5u4(s4)4321当当s3=2

55、时，时，f3(2)=minC(u3)+0.52+f4(u3)， 0u33 u3=0: 0+1+7 = min u3=1: 4+1+6.5 = 8， u*3(2)=0, u3=2: 5+1+6 u3=3: 6+1+5.5这就是说，若这就是说，若第第3月初月初库存库存为为2，则，则3、4二二月月最最低低费用费用为为8（千元），（千元），第第3月最月最优产量优产量为为0单位。单位。88/151s40123f4(s4)76.565.5u4(s4)4321当当s3=3时，时，f3(2)=minC(u3)+0.53+f4(u3+1)， 0u32 u3=0: 0+1.5+6.5 = min u3=1: 4+

56、1.5+6 = 8， u*3(3)=0, u3=2: 5+1.5+5.5 这就是说，若这就是说，若第第3月初月初库存库存为为3，则，则3、4二二月月最最低低费用费用为为8（千元），（千元），第第3月最月最优产量优产量为为0单位。单位。89/151s40123f4(s4)76.565.5u4(s4)432190/151s301u3(s3)23451234C+E+f41212.51313.511.51212.513f3(s3)1211.5u*3(s3)21s323u3(s3)0123012C+E+f4811.51212.5811.512f3(s3)88u*3(s3)00表表7-9s4=s3+u3-

57、g3=s3+u3-2k=2f2(s2)=minC(u2)+E(s2)+f3(s2+u2-g2)s2=0, 1, 2, 3决策变量决策变量u2为：为：max0, g2-s2u2min6, g2+3-s2, g2+g3+g4-s2的的整数，即整数，即max0, 3-s2u2min6, 6-s2, 9-s2的的整数整数本段计算结果见表本段计算结果见表7-10。91/15192/151s201u2(s2)34562345C+E+f31818.5161717.51815.516.5f2(s2)1615.5u*2(s2)54s323u3(s3)12340123C+E+f41717.5151613.5171

58、4.515.5f3(s3)1513.5u*3(s3)30表表7-10s3=s2+u2-g2=s2+u2-3k=1f1(s1)=minC(u1)+E(s1)+f2(s1+u1-g1)s1=0决策变量决策变量u1受本月需求量、库存容量和生产能受本月需求量、库存容量和生产能力限制，应为力限制，应为2u15的整数，的整数，f1(0)= min C(u1)+f2(u1-2) 2u15的的整数整数本本段计算结果见表段计算结果见表7-11。93/151表表7-11f1(s1)从表从表7-11可知，最低总费用为可知，最低总费用为f1(0)=21(千元千元)，第第1月最佳产量为月最佳产量为2单位，而需求为单位，

59、而需求为2单位，所以单位，所以，第，第2月初库存为月初库存为0，再由表，再由表7-10查查s2=0列，可列，可得，第得，第2月月最佳产量最佳产量为为5单位，同理查得，第单位，同理查得，第3月月最佳产量最佳产量为为0单位，第单位，第4月月最佳产量最佳产量为为4单位。单位。94/151s10u1(s1)2345C+f22121.52221.5f1(s1)21u*1(s1)2s2=s1+u1-g1=s1+u1-295/151例例9 采购与销售问题采购与销售问题 某商店未来某商店未来4个个月，准备用月，准备用一一个仓库专销个仓库专销某某种商品种商品，最，最多多贮存贮存1000单位。假定每月只能卖单位。

60、假定每月只能卖存存货。货。定定货下月初货下月初才能才能到。未来四个月买卖价到。未来四个月买卖价格格预测预测如如表表7-12。1月月初初库库存存500单位单位。若。若不计不计库存库存费，该店费，该店应如何应如何制订制订1至至4月购销计划月购销计划，使，使预期获利最大预期获利最大。 表表7-1296/151月份月份购价购价(ck) 售价售价(pk)110122983111341517解解 按按月划月划分分4阶段阶段，k=1, 2, 3, 4状态变量状态变量sk：第：第k月初库存量月初库存量。决策变量决策变量xk：第第k 月月卖卖出量出量。 yk：第：第k月订购量月订购量。状态转移方程状态转移方程：