运筹学OR1-Ch8-动态规划

1、第八章 动态规划Ch8 Dynamic Programming8-1 多阶段决策过程最优化8-2 动态规划基本概念8-3 动态规划基本原理8-4 动态规划的应用8-1 多阶段决策过程最优化一、多阶段决策问题动态规划是把多阶段决策问题作为研究对象。多阶段决策问题：根据问题本身的特点，可以将其求解的全过程划分为若干个相互联系的阶段(即将问题划分为许多个相互联系的子问题)，在它的每一阶段都需要作出决策，并且在一个阶段的决策确定以后再转移到下一个阶段。多阶段决策过程(Multi-Stagedecision process)： 前一个阶段的决策要影响到后一个阶段的决策，从而影响整个过程。各个阶段所确定的

2、决策就构成了一个决策序列，称为一个策略。一般来说，由于每一阶段可供选择的决策往往不止一个，因此，对于整个过程，就会有许多可供选择的策略。*Page 2 of 77 8-1 多阶段决策过程最优化最优策略：若对应于一个策略，可以由一个量化的指标来确定这个策略所对应的活动过程的效果，那么不同的策略就有各自的效果。在所有可供选择的策略中，对应效果最好的策略称为最优策略。把一个问题划分成若干个相互联系的阶段选取其最优策略，这类问题就是多阶段决策问题。多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最优。由于各段决策间有机地联系着，本段决策的执行将影响到下一段的决策，以至于影响总体效果，所以决策者

3、在每段决策时不应仅考虑本阶段最优，还应考虑对最终目标的影响，从而作出对全局来讲是最优的决策。动态规划就是符合这种要求的一种决策方法。*Page 3 of 77 8-1 多阶段决策过程最优化二、多阶段决策问题举例 1)工厂生产过程：由于市场需求是一随着时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根据库存和需求情况决定生产计划安排。2)设备更新问题：一般企业用于生产活动的设备，刚买来时故障少，经济效益高，即使进行转让，处理价值也高，随着使用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使用的年限越长

4、、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费因此就需要综合权衡决定设备的使用年限，使总的经济效益最好。*Page 4 of 77 8-1 多阶段决策过程最优化3)连续生产过程的控制问题：一般化工生产过程中，常包含一系列完成生产过程的设备，前一工序设备的输出则是后一工序设备的输入，因此，应该如何根据各工序的运行工况，控制生产过程中各设备的输入和输出，以使总产量最大。以上所举问题的发展过程都与时间因素有关，因此在这类多阶段决策问题中，阶段的划分常取时间区段来表示，并且各个阶段上的决策往往也与时间因素有关，这就使它具有了“动态”的含义，所以把处理这类动态问题的方法称为动态规划方法。不

5、过，实际中尚有许多不包含时间因素的一类“静态”决策问题，就其本质而言是一次决策问题，是非动态决策问题，但是也可以人为地引入阶段的概念当作多阶段决策问题，应用动态规划方法加以解决。*Page 5 of 77 8-1 多阶段决策过程最优化4）资源分配问题：属于这类静态问题。如：某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量，它与时间因素无关，不属动态决策，但是，我们可以人为地规定一个资源分配的阶段和顺序，从而使其变成一个多阶段决策问题(后面我们将详细讨论这个问题)。5）运输网络问题： 如下页图1所示的运输网络，

6、点间连线上的数字表示两地距离(也可是运费、时间等)，要求从v1 至v10的最短路线。 这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以把它分为4个阶段，而作为多阶段决策问题来研究。*Page 6 of 77 8-1 多阶段决策过程最优化图8-1 运输网络图示*Page 7 of 77 8-1 多阶段决策过程最优化三、动态规划求解的多阶段决策问题的特点 通常多阶段决策过程的发展是通过状态的一系列变换来实现的。一般情况下，系统在某个阶段的状态转移除与本阶段的状态和决策有关外，还可能与系统过去经历的状态和决策有关。因此，问题的求解就比较困难复杂。而适合于用动态规划方法求解的只是一类特

7、殊的多阶段决策问题，即具有“无后效性”的多阶段决策过程。所谓无后效性，又称马尔柯夫性，是指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策(历史)无关。状态 x1阶段1T1决策u1状态 x2决策u2阶段2T2状态 x3.状态 xk决策uk阶段kTk状态 xk+1.状态 xn决策un阶段nTn状态 xn+1要点：阶段，状态，决策，状态转移方程，k-后部子过程多阶段决策过程特点:*Page 8 of 77 8-1 多阶段决策过程最优化四、动态规划方法导引：为了说明动态规划的基本思想方法和特点，下面以图8-1所示为例讨论的求最短路问题的方法。 第一种方法

8、称做全枚举法或穷举法。它的基本思想是列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。这里从v1到v10的路程可以分为4个阶段。第一段的走法有三种，第二三两段的走法各有两种，第四段的走法仅一种，因此共有322112条可能的路线，分别算出各条路线的距离，最后进行比较，可知最优路线是v1 v3 v7 v9 v10 ,最短距离是18显然，当组成交通网络的节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算 第二种方法即所谓“局部最优路径”法，是说某人从k出发，他并不顾及全线是否最短，只是选择当前最短途径，“逢近便走”，错误地以为局部最优会致整体最优，在

9、这种想法指导下，所取决策必是v1 v3 v5 v8 v10 ，全程长度是20；显然，这种方法的结果常是错误的*Page 9 of 77 8-1 多阶段决策过程最优化第三种方法是动态规划方法。动态规划方法寻求该最短路问题的基本思想是，首先将问题划分为4个阶段，每次的选择总是综合后继过程的一并最优进行考虑，在各段所有可能状态的最优后继过程都已求得的情况下，全程的最优路线便也随之得到。 为了找出所有可能状态的最优后继过程，动态规划方法总是从过程的最后阶段开始考虑，然后逆着实际过程发展的顺序，逐段向前递推计算直至始点。*Page 10 of 77 8-1 多阶段决策过程最优化具体说，此问题先从v10开

10、始，因为v10是终点。再无后继过程，故可以接着考虑第4阶段上所有可能状态v8 ,v9的最优后续过程因为从v8 ,v9 到v10的路线是唯一的，所以v8 ,v9 的最优决策和最优后继过程就是到v10 ，它们的最短距离分别是5和3。 接着考虑阶段3上可能的状态v5 ,v6 , v7 , 到v10的最优决策和最优后继过程在状态V5上，虽然到v8是8，到v9是9，但是综合考虑后继过程整体最优，取最优决策是到v9,最优后继过程是v5v9 v10 ，最短距离是12同理，状态v6的最优决策是至v8 ；v7的最优决策是到v9 。同样，当阶段3上所有可能状态的最优后继过程都已求得后，便可以开始考虑阶段2上所有可

11、能状态的最优决策和最优后继过程，如v2的最优决策是到v5,最优路线是v2v5v9v10 ，最短距离是15依此类推，最后可以得到从初始状态v1的最优决策是到v3最优路线是v1v3v7v9v10 ，全程的最短距离是18。图1中粗实线表示各点到的最优路线，每点上方括号内的数字表示该点到终点的最短路距离。*Page 11 of 77 8-1 多阶段决策过程最优化结论：全枚举法虽可找出最优方案，但不是个好算法；局部最优法则完全是个错误方法；动态规划方法属较科学有效的算法：它的基本思想是，把一个比较复杂的问题分解为一系列同类型的更易求解的子问题，便于应用计算机。整个求解过程分为两个阶段，先按整体最优的思想

12、逆序地求出各个子问题中所有可能状态的最优决策与最优路线值，然后再顺序地求出整个问题的最优策略和最优路线。计算过程中，系统地删去了所有中间非最优的方案组合，从而使计算工作量比穷举法大为减少。*Page 12 of 77 8-2 动态规划基本概念使用动态规划方法解决多阶段决策问题，首先要将实际问题写成动态规划模型，同时也为了今后叙述和讨论方便，这里需要对动态规划的下述一些基本术语进一步加以说明和定义： *Page 13 of 77 8-2 动态规划基本概念(一) 阶段和阶段变量 为了便于求解和表示决策及过程的发展顺序，而把所给问题恰当地划分为若干个相互联系又有区别的子问题，称之为多段决策问题的阶段

13、。一个阶段，就是需要作出一个决策的子问题，通常，阶段是按决策进行的时间或空间上先后顺序划分的。用以描述阶段的变量叫作阶段变量，一般以k表示阶段变量阶段数等于多段决策过程从开始到结束所需作出决策的数目，图51所示的最短路问题就是一个四阶段决策过程。（二）状态、状态变量和可能状态集 1.状态与状态变量。用以描述事物(或系统)在某特定的时间与空间域中所处位置及运动特征的量，称为状态。反映状态变化的量叫做状态变量。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。按照过程进行的先后，每个阶段的状态可分为初始状态和终止状态，或称输入状态和输出状态，阶段k的初始状态记作sk，终止状态记为sk+1

14、。但为了清楚起见，通常定义阶段的状态即指其初始状态。*Page 14 of 77 8-2 动态规划基本概念2可能状态集 一般状态变量的取值有一定的范围或允许集合，称为可能状态集，或可达状态集。可能状态集实际上是关于状态的约束条件。通常可能状态集用相应阶段状态sk的大写字母Sk表示，skSk，可能状态集可以是一离散取值的集合，也可以为一连续的取值区间，视具体问题而定在图51所示的最短路问题中，第一阶段状态为v1，状态变量s1的状态集合S1=v1；第二阶段则有三个状态：v2 ,v3 ,v4 ,状态变量s2的状态集合S2=v2 ,v3 ,v4 ；第三阶段也有三个状态:v5 ,v6 ,v7 ，状态变量

15、s3的状态集合S3=v5 ,v6 ,v7 ；第四阶段则有二个状态： v8 ,v9 , 状态变量s4的状态集合S4=v8 ,v9 ；*Page 15 of 77 8-2 动态规划基本概念（三）决策、决策变量和允许决策集合 所谓决策，就是确定系统过程发展的方案。决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。 用以描述决策变化的量称之决策变量和状态变量一样，决策变量可以用一个数，一组数或一向量来描述，也可以是状态变量的函数，记以uk= uk(sk)，表示于阶段k状态sk时的决策变量。 决策变量的取值往往也有一定的允许范围，称之允许决策集合。决策变量uk(sk)的允许

16、决策集用Uk(sk)表示, uk(sk) Uk(sk)允许决策集合实际是决策的约束条件。*Page 16 of 77 8-2 动态规划基本概念（四）、策略和允许策略集合 策略(Policy)也叫决策序列策略有全过程策略和k部子策略之分，全过程策略是指具有n个阶段的全部过程，由依次进行的n个阶段决策构成的决策序列，简称策略，表示为p1,nu1,u2,un。从k阶段到第n阶段，依次进行的阶段决策构成的决策序列称为k部子策略,表示为pk,nuk,uk+1,un ，显然当k=1时的k部子策略就是全过程策略。 在实际问题中，由于在各个阶段可供选择的决策有许多个，因此，它们的不同组合就构成了许多可供选择的

17、决策序列(策略)，由它们组成的集合，称之允许策略集合，记作P1,n ，从允许策略集中，找出具有最优效果的策略称为最优策略。*Page 17 of 77 8-2 动态规划基本概念（五）状态转移方程 系统在阶段k处于状态sk，执行决策uk(sk)的结果是系统状态的转移，即系统由阶段k的初始状态sk转移到终止状态sk+1 ，或者说，系统由k阶段的状态sk转移到了阶段k+1的状态sk+1 ，多阶段决策过程的发展就是用阶段状态的相继演变来描述的。 对于具有无后效性的多阶段决策过程,系统由阶段k到阶段k+1的状态转移完全由阶段k的状态sk和决策uk(sk)所确定，与系统过去的状态s1,s2, ,sk-1及

18、其决策u1(s1), u2(s2)uk-1(sk-1)无关。系统状态的这种转移，用数学公式描述即有：通常称式(1)为多阶段决策过程的状态转移方程。有些问题的状态转移方程不一定存在数学表达式，但是它们的状态转移，还是有一定规律可循的。(1)*Page 18 of 77 8-2 动态规划基本概念(六) 指标函数 用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用，等等。例如：图10-1的指标就是运费。 (1)阶段指标函数（也称阶段效应）。用gk(sk,

19、uk)表示第k段处于sk状态且所作决策为uk(sk)时的指标，则它就是第k段指标函数，简记为gk 。图1的gk值就是从状态sk到状态sk+1的距离。譬如，gk(v2,v5)=3,即v2到v5的距离为3。 (2)过程指标函数（也称目标函数）。用Rk(sk,uk)表示第k子过程的指标函数。如图10-1的Rk(sk,uk)表示处于第k段sk状态且所作决策为uk时，从sk点到终点v10的距离。由此可见，Rk(sk,uk)不仅跟当前状态sk有关，还跟该子过程策略pk(sk)有关，因此它是sk和pk(sk)的函数，严格说来，应表示为:*Page 19 of 77 8-2 动态规划基本概念不过实际应用中往往

20、表示为Rk(sk,uk)或Rk(sk)。还跟第k子过程上各段指标函数有关，过程指标函数Rk(sk)通常是描述所实现的全过程或k后部子过程效果优劣的数量指标，它是由各阶段的阶段指标函数gk(sk,uk)累积形成的，适于用动态规划求解的问题的过程指标函数（即目标函数），必须具有关于阶段指标的可分离形式对于部子过程的指标函数可以表示为： 式中，表示某种运算，可以是加、减、乘、除、开方等。多阶段决策问题中，常见的目标函数形式之一是取各阶段效应之和的形式，即:总之，具体问题的目标函数表达形式需要视具体问题而定。 (2)（3）(4)*Page 20 of 77 8-2 动态规划基本概念(七) 最优解 用f

21、k(sk)表示第k子过程指标函数 在状态sk下的最优值,即 称fk(sk)为第k子过程上的最优指标函数；与它相应的子策略称为sk状态下的最优子策略，记为pk*(sk) ；而构成该子策赂的各段决策称为该过程上的最优决策，记为 : 简记为*Page 21 of 77 8-2 动态规划基本概念特别当k=1且s1取值唯一时，f1(s1)就是问题的最优值，而p1*就是最优策略。如例10-1只有唯一始点v1即s1取值唯一,故f1(s1)=18就是例10-1的最优值，而: 就是例10-1的最优策略。 但若取值不唯一,则问题的最优值记为f0有 最优策略即为s1=s1*状态下的最优策略： 我们把最优策略和最优值

22、统称为问题的最优解。*Page 22 of 77 8-2 动态规划基本概念按上述定义，所谓最优决策 是指它们在全过程上整体最优(即所构成的全过程策略为最优)，而不一定在各阶段上单独最优。(八) 多阶段决策问题的数学模型 综上所述，适于应用动态规划方法求解的一类多阶段决策问题，亦即具有无后效性的多阶段决策问题的数学模型呈以下形式:（5）*Page 23 of 77 8-2 动态规划基本概念式中“OPT”表示最优化，视具体问题取max或min。 上述数学模型说明了对于给定的多阶段决策过程，求取一个(或多个)最优策略或最优决策序列，使之既满足式(5)给出的全部约束条件，又使式(5)所示的目标函数取得

23、极值，并且同时指出执行该最优策略时，过程状态演变序列即最优路线*Page 24 of 77 8-3 动态规划基本原理一。最优化原理 （贝尔曼最优化原理） 作为一个全过程的最优策略具有这样的性质：对于最优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个最优子策略。该原理的具体解释是，若某一全过程最优策略为：则对上述策略中所隐含的任一状态而言，第k子过程上对应于该状态的最优策略必然 包含在上述全过程最优策略p1*中，即为：*Page 25 of 77 8-3 动态规划基本原理二。动态规划方法的基本步骤应将实际问题恰当地分割成n个子问题(n个阶段)。通常是根据时间或空间而

24、划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数n，即k=n。 正确地定义状态变量sk，使它既能正确地描述过程的状态，又能满足无后效性动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的，动态规划中的状态变量必须具备以下三个特征： (1)要能够正确地描述受控过程的变化特征。 (2)要满足无后效性。即如果在某个阶段状态已经给定，那么在该阶段以后，过程的发展不受前面各段状态的影响，如果所选的变量不具备无后效性，就不能作为状态变量来构造动态规划的模型。 (3)要满足可知性。即所规定的各段状态变量的值，可以直接或间接地测算得到。一般在动态规划模型中，状态

25、变量大都选取那种可以进行累计的量。此外，在与静态规划模型的对应关系上，通常根据经验，线性与非线性规划中约束条件的个数，相当于动态规划中状态变量sk的维数而前者约束条件所表示的内容，常常就是状态变量sk所代表的内容。*Page 26 of 77 8-3 动态规划基本原理3正确地定义决策变量及各阶段的允许决策集合Uk(sk)，根据经验，一般将问题中待求的量，选作动态规划模型中的决策变量。或者在把静态规划模型(如线性与非线性规划)转换为动态规划模型时，常取前者的变量xj为后者的决策变量uk。4. 能够正确地写出状态转移方程，至少要能正确反映状态转移规律。如果给定第k阶段状态变量sk的值，则该段的决策

26、变量uk一经确定，第k+1段的状态变量sk+1的值也就完全确定，即有sk+1=Tk(sk ,uk)5根据题意,正确地构造出目标与变量的函数关系目标函数，目标函数应满足下列性质： (1)可分性，即对于所有k后部子过程，其目标函数仅取决于状态sk及其以后的决策 uk ,uk+1,un,就是说它是定义在全过程和所有后部子过程上的数量函数。 (2)要满足递推关系，即 (3)函数 对其变元Rk+1来说要严格单调。*Page 27 of 77 8-3 动态规划基本原理6写出动态规划函数基本方程例如常见的指标函数是取各段指标和的形式 其中 表示第i阶段的指标，它显然是满足上述三个性质的。所以上式可以写成 ：

27、*Page 28 of 77 8-4 动态规划的应用最短路问题一.求最短路径问题例8-2*Page 29 of 77 8-4 动态规划的应用最短路问题将问题分成五个阶段，第k阶段到达的具体地点用状态变量xk表示，例如：x2=B3表示第二阶段到达位置B3，等等。这里状态变量取字符值而不是数值。将决策定义为到达下一站所选择的路径，例如目前的状态是x2=B3，这时决策允许集合包含三个决策，它们是D2(x2)=D2(B3)=B3C1,B3C2,B3C3最优指标函数fk(xk)表示从目前状态到E的最短路径。终端条件为 f5(x5)=f5(E)=0其含义是从E到E的最短路径为0。第四阶段的递推方程为:*P

28、age 30 of 77 8-4 动态规划的应用最短路问题其中*表示最优值，在上表中，由于决策允许集合D4(x4)中的决策是唯一的，因此这个值就是最优值。由此得到f4(x4)的表达式。由于这是一个离散的函数，取值用列表表示：*Page 31 of 77 8-4 动态规划的应用最短路问题第三阶段的递推方程为：*Page 32 of 77 8-4 动态规划的应用最短路问题由此得到f3(x3)的表达式：从f3(x3)到f2(x2)的递推过程用表格表示如下： *Page 33 of 77 8-4 动态规划的应用最短路问题*Page 34 of 77 8-4 动态规划的应用最短路问题由此得到f2(x2)

29、的表达式：第一阶段的递推方程为：*Page 35 of 77 8-4 动态规划的应用最短路问题从f2(x2)到f1(x1)的递推过程用表格表示如下： 由此得到f1(x1)的表达式从表达式f1(x1)可以看出，从A到E的最短路径长度为19。由f1(x1)向f4(x4)回朔，得到最短路径为：A B2 C1 D1 E *Page 36 of 77 8-4 动态规划的应用资源分配问题二.资源分配问题所谓资源分配问题，就是将供应量有限的一种或若干种资源（例如原材料、资金、机器设备、劳动、食品等），分配给若干个使用者，而使目标函数为最优。 问题的提出：设有某种原材料，总量为a，用于生产n种产品。若分配数量

30、为yi的原材料生产第i种产品，其效益为g(yi)。问应如何分配，才能使生产n种产品的总收入最大?问题的求解：在应用动态规划方法求解资源分配问题时，通常以把资源分配给一个或几个使用者的过程作为一个阶段；把规划问题中的变量取为决策变量；把累计的量或随递推过程变化的量选为状态变量。 *Page 37 of 77 8-4 动态规划的应用资源分配问题例8-3: 有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（万吨）和投入资金（万元）关系见下表：求对三个项目的最优投资分配，使总投资效益最大。阶段k：每投资一个项目作为一个阶段；状态变量xk：投资

31、第k个项目前的资金数；决策变量dk：第k个项目的投资；决策允许集合：0dkxk状态转移方程：xk+1=xk-dk阶段指标：vk(xk ,dk)见表中所示；递推方程：fk(xk)=maxvk(xk ,dk)+fk+1(xk+1)终端条件：f4(x4)=0*Page 38 of 77 8-4 动态规划的应用资源分配问题k=4，f4(x4)=0k=3，0d3x3，x4=x3-d3*Page 39 of 77 8-4 动态规划的应用资源分配问题K=2:*Page 40 of 77 8-4 动态规划的应用资源分配问题k=1，0d1x1，x2=x1-d1最优解为x1=4, d1*=1, x2=x1-d1=

32、3, d2*=0, x3=x2-d2*=3, d3=3, x4=x3-d3=0，即项目A投资1万元，项目B投资0万元，项目C投资3万元，最大效益为60万吨。 *Page 41 of 77 8-4 动态规划的应用生产与库存问题三. 生产与库存问题问题的提出：一个生产项目，在生产批量、生产成本费用、存储费用以及市场对产品的要求情况都是确定数值的条件下，为了根据需要制订计划，必须正确决定不同时期的生产量和库存量，以期在满足市场需求的条件下使生产与库存的费用最低。 一般的解决方法：以计划的不同时期为不同的阶段 k；状态变量 xk 取为第k阶段开始时的库存量；决策变量k为第k阶段（时期）的生产量； 状态

33、转移方程为： 为第k阶段的阶段指标，代表这一时期的成本。则此问题的动态规划递推关系式为： *Page 42 of 77 8-4 动态规划的应用生产与库存问题例8-4:一个工厂生产某种产品,1- 7月份生产成本和产品需求量的变化情 况如下表：为了调节生产生产和需求，工厂设有一个产品仓库，库容量H=9。已知期初库存量为2，要求期末（七月低）库存量为0。每个月生产的产品在月末入库，月初根据当月需求发货。求七个月的生产量，能满足各月的需求，并使生产成本最低。 *Page 43 of 77 8-4 动态规划的应用生产与库存问题阶段k：月份，k=1,2,7,8；状态变量xk：第k个月初（发货以前）的库存量

34、；决策变量dk：第k个月的生产量；状态转移方程：xk+1=xk-rk+dk；决策允许集合：Dk(xk)=dk | dk0, rk+1xk+1H =dk | dk0, rk+1xk-rk+dkH ；阶段指标：vk(xk ,dk)=ckdk；终端条件：f8(x8)=0,x8=0；递推方程：fk(xk)=minvk(xk ,dk)+fk+1(xk+1) dkDk(xk) =minckdk+fk+1(xk-rk+dk) dkDk(xk)*Page 44 of 77 8-4 动态规划的应用生产与库存问题对于k=7因为 x8=0 有: d7=0递推方程为: f7(x7)=minc7d7+f8(x8)=0

35、d7=0对于k=6 因为d7=0，所以x7=r7=4 而x6-r6+d6=x7=4 因此有d6=x7+r6-x6=4+7-x6=11-x6也是唯一的决策。因此递推方程为：f6(x6)=minc6d6+f7(x7) d6=11-x6=10d6=10(11-x6)=110-10 x6*Page 45 of 77 8-4 动态规划的应用生产与库存问题对于k=5f5(x5)=minc5d5+f6(x6) =min20d5+110-10 x6 =min20d5+110-10(x5-r5+d5) =min20d5+110-10(x5-2+d5) =min10d5-10 x5+130 d5D5(x5)D5(

36、x5) =d5| d50, r6x5-r5+d5H =d5|d50, r6+r5-x5d5H+r5-x5 =d5| d50, 9-x5d511-x5因为x5H=9，因此9-x50，决策允许集合可以简化为 D5(x5)=d5| 9-x5d511-x5递推方程成为f5(x5)=min10d5-10 x5+130 9-x5d511-x5 =10(9-x5)-10 x5+130 =220-20 x5 d5*=9-x5*Page 46 of 77 8-4 动态规划的应用生产与库存问题对于k=4f4(x4)=minc4d4+f5(x5)=min17d4+220-20 x5 =min17d4+220-20(

37、x4-r4+d4) =min17d4+220-20(x4-3+d4) =min-3d4-20 x4+280 d4D4(x4) D4(x4)=d4| d40, r5x4-r4+d4H=d4| d40, r5+r4-x4d4H+r4-x4=d4| d40, 5-x4d412-x4=d4| max0,5-x4d412-x4 由于 在f4(x4)的表达式中d4的系数是-3，因此d4在决策允许集合中应取集合中的最大值，即d4=12-x4由此 f4(x4)=-3(12-x4)-20 x4+280 =-17x4+244*Page 47 of 77 8-4 动态规划的应用生产与库存问题对于k=3f3(x3)=

38、min c3d3+f4(x4) =min 13d3+244-17x4 =min 13d3+244-17(x3-r3+d3) =min -4d3-17x3+329 其中d3D3(x3) D3(x3)=d3| d30,r4x3-r3+d3H=d3| d30,r4+r3-x3d3H+r3-x3=d3| d30,8-x3d314-x3=d3| max0,8-x3d314-x3 d3*=14-x3由此 f3(x3)=-4(14-x3)-17x3+329 =-13x3+273, *Page 48 of 77 8-4 动态规划的应用生产与库存问题对于k=2f2(x2)=minc2d2+f3(x3) =min

39、18d2+273-13x3 =min18d2+273-13(x2-r2+d2) =min18d2+273-13(x2-8+d2) =min5d2-13x2+377 其中 d2D2(x2) D2(x2)=d2|d20,r3x2-r2+d2H =d2|d20,r3+r2-x2d2H+r2-x2 =d2|d20,13-x2d217-x2因为 13-x20所以 d2(x2)=d2|13-x2d217-x2由此 f2(x2)=5(13-x2)-13x2+377 =-18x2+442, d2*=13-x2*Page 49 of 77 8-4 动态规划的应用生产与库存问题对于k=1f1(x1)=minc1d

40、1+f2(x2) =min11d1+442-18x2 =min11d1+442-18(x1-r1+d1) =min11d1+442-18(x1-0+d1) =min-7d1-18x1+442 d1D1(x1) D1(x1)=d1|d10,r2x1-r1+d1H =d1|d10,r2+r1-x1d1H+r1-x1 =d1|d10,8-x1d19-x1根据题意 x1=2所以 D1(x1)=d1| 6d17由此 d1=7f1(x1)=-7d1-18x1+442 =-77182442 =357*Page 50 of 77 8-4 动态规划的应用生产与库存问题将以上结果总结成下表：*Page 51 of

41、 77 8-4 动态规划的应用背包问题四. 背包问题 设有n种物品，每一种物品数量无限。第i种物品每件重量为wi，每件价值ci。现有一只可装载重量为W的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。这个问题可以用整数规划模型来描述。设第i种物品取xi件（i=1,2,n，xi为非负整数），背包中物品的价值为z，则 则 Max z=c1x1+c2x2+cnxn s.t. w1x1+w2x2+wnxnW x1,x2,xn为正整数*Page 52 of 77 8-4 动态规划的应用背包问题1.阶段k：第k次装载第k种物品（k=1,2,n）2.状态变量xk：第k次装载时背包还可以装载的重

42、量；3.决策变量dk：第k次装载第k种物品的件数；4. 决策允许集合：Dk(xk)=dk|0 dkxk/wk，dk为整数；5. 状态转移方程：xk+1=xk-wkdk6. 阶段指标：vk=ckdk7. 递推方程 fk(xk)=maxckdk+fk+1(xk+1) =maxckdk+fk+1(xk-wkdk)8. 终端条件：fn+1(xn+1)=0*Page 53 of 77 8-4 动态规划的应用背包问题 例8.7:对于一个具体问题c1=65，c2=80，c3=30；w1=2，w2=3，w3=1；以及W=5【解】用动态规划求解边界条件： f4(x4)=0 对于k=3列出f3(x3)的数值表如下

43、： *Page 54 of 77 *Page 55 of 77 8-4 动态规划的应用背包问题对于k=2 列出f2(x2)的数值表 *Page 56 of 77 8-4 动态规划的应用背包问题对于k=1*Page 57 of 77 8-4 动态规划的应用背包问题由题意知，x1=5，由表f1(x1)、f2(x2)、f3(x3)，经回朔可得：d1*=2，x2=x1-2d1=1，d2*=0，x3=x2-3d2=1，d3*=1，x4=x3-d3=0即应取第一种物品2件,第三种物品1件,最高价值为160元,背包没有余量。由f1(x1)得列表可以看出，如果背包得容量为W=4，W=3，W=2和W=1时，相应

44、的最优解立即可以得到。 *Page 58 of 77 8-4 动态规划的应用机器负荷分配问题五。机器负荷分配问题 最短路径问题和背包问题的状态变量和决策变量都只能取离散的整数值。当状态变量和决策变量的取值范围很大，或者这些变量是连续的，用列举的方法就比较困难或者根本不可能了。这就需要用连续变量的处理方法。例8.8:某种机器可以在高、低两种负荷下生产。高负荷生产条件下机器完好率为0.7，即如果年初有u台完好机器投入生产，则年末完好的机器数量为0.7u台。系数0.7称为完好率。年初投入高负荷运行的u台机器的年产量为8u吨。系数8称为单台产量。低负荷运行时，机器完好率为0.9，单台产量为5吨。设开始

45、时有1000台完好机器，要制订五年计划，每年年初将完好的机器一部分分配到高负荷生产，剩下的机器分配到低负荷生产，使五年的总产量为最高。 *Page 59 of 77 8-4 动态规划的应用机器负荷分配问题 构造动态规划模型如下： 阶段k：运行年份（k=1,2,3,4,5,6），其中k=1表示第一年初，依次类推；k=6表示第五年末（即第六年初）。 状态变量xk：第k年初完好的机器数（k=1,2,3,4,5,6），其中x6表示第五年末（即第六年初）的完好机器数。 决策变量dk：第k年投入高负荷运行的机器数； 状态转移方程：xk+1=0.7dk+0.9(xk-dk) 决策允许集合：Dk(xk)=dk

46、|0dkxk 阶段指标：vk(xk ,dk)=8dk+5(xk-dk) 终端条件：f6(x6)=0递推方程：fk(xk)=maxvk(xk,dk)+fk+1(xk+1) = max8dk+5(xk- dk)+fk+10.7dk+0.9(xk-dk) 0dkxkdkDk(xk)*Page 60 of 77 8-4 动态规划的应用机器负荷分配问题 根据题意，本题的决策允许集合应该是一个整数集合，但由于决策允许集合中可取的决策数量很大，一一列举计算量很大，不妨认为状态变量和决策变量都是连续的，得到最优解后，再作取整处理。f5(x5)=max8d5+5(x5-d5)+f6(x6) 0d5x5 =max

47、3d5+5x5=8x5, d5*=x5 0d5x5f4(x4)=max8d4+5(x4-d4)+f5(x5) 0d4x4 =max8d4+5(x4-d4)+8x5 0d4x4 =max8d4+5(x4-d4)+80.7d4+0.9(x4-d4) 0d4x4 =max1.4d4+12.3x4=13.7x4, d4*=x4*Page 61 of 77 8-4 动态规划的应用机器负荷分配问题f3(x3)=max8d3+5(x3-d3)+f4(x4) 0d3x3=max8d3+5(x3-d3)+13.7x4 0d3x3=max8d3+5(x3-d3)+13.70.7d3+0.9(x3-d3) 0d3x3=max0.28d3+17.24x3=17.52x3, d3*=x3 0d3x3f2(x2)=max8d2+5(x2-d2)+f3(x3) 0d2x2 =max8d2+5(x2-d2)+17.52x3 0d2x2 =ma