第六章 动态规划

1、第六章 动态规划第六章 动态规划动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化的一种数学方法。大约产生于50年代。1951年美国数学家贝尔曼（r3bellman）等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列互相联系单阶段问题，然后逐个加以解决。与此同时，他提出了解决这类问题的“最优性原理”，研究了许多实际问题，从而创建了解决最优化问题的一种新的方法动态规划。他的名著“动态规划”于1957年出版，该书是动态规划的第一本著作。动态规划的方法，在工程技术、企业管理、工农业生产及军事等部门中都有广泛的应用，并且获得了显著的效果。在企业管理方面，动态规划可以用来解决最优路径

2、问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等等，所以它是现代企业管理中的一种重要的决策方法。许多问题用动态规划的方法去处理，常比线性规划或非线性规划更有成效。特别对于离散性的问题，由于解析数学无法施展其术，而动态规划的方法就成为非常有用的工具。应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，读者在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性

3、的技巧去求解。动态规划模型的分类，根据多阶段决策过程的时间参量是离散的还是连续的变量，过程分为离散决策过程和连续决策过程。根据决策过程的演变是确定性的还是随机性的，过程又可分为确定性决策过程和随机性决策过程。组合起来就有离散确定性、离散随机性、连续确定性、连续随机性四种决策过程模型。本部分主要研究离散决策过程，介绍动态规划的基本概念、理论和方法，并通过几个典型的问题来说明它的应用，这些都是整个动态规划的基本内容。 第一节 动态规划的基本原理一、引例 最短路问题例1 图5.1为一道路网，各路段的长度如图中所示，某人欲从a到j，试为他选择一条最短线。为解决这一问题，显然可用直接枚举法，即列出从a到

4、j（沿图中箭头方向前进）的所有路线，分别计算出这些路线的长度，经比较选出其中最短者。本问题从a到各个节点的路线数示于图5.1中各节点旁的小圆圈中，可知共有8条路线。为清楚起见，将这8条路线分离划出于图5.2中。由图5.2右侧标出的各条路线的总长度可知，abehj为最短路，其长度等于9。由于每条路线均由4段组成，故计算一条路线的长度要做3次加法运算，8条路线共需24次加法运算。此外，为决定最短路长还要进行7次比较。为减少计算工作量，我们考虑另一种算法。用表示从起点a到终点j的最短路长，类似地，用表示从某一节点k到j的最短路长，并用表示节点k到某节点y的路段长度。由于各路段长度已给，故知取决于和，

5、取决于和，取决于和，、和则仅取决于，而j为终点，可令=0。如此，可按以下顺序逐步进行计算。=+=3+0=3=5+0=5=6+0=6=2+3=5算出的最短路线长度等于9，与枚举法结果相同。由=9知b在最短路上线，由知e在最短路线上，如此追踪可找出最短路径（在有关数据下加有横线）为abehj。该算法仅需14次加法，5次比较，比枚举法计算量少；问题规模越大，计算量的节约越显著。可以认为，随问题规模的增加，枚举法的计算量按指数增加，而该方法则按线性增加。上述第二种算法采用了由后向前逐阶段递推的方法，它包含了动态规划的基本思想。二、动态规划的主要术语为便于下面讨论，先解释动态规划的主要术语，并说明一些有

6、关概念。1阶段（stage）多阶段决策过程包含若干个组成阶段，整个过程是由各个阶段按一定顺序联系起来的统一整体，它由开始阶段出发，按过程进行的方向，由前向后一个阶段一个阶段地推移，直至最后一个阶段结束为止。若决策者在某一阶段作出了一个决策，则系统此后的发展就要受到这一决策的影响，这个决策的好坏，将影响到此后的决策序列及其效果。因此，在作阶段决策时不能不考虑到对后面各阶段的影响而将它单独“最优化”。由于最后一个阶段对其它阶段不产生影响，因而可以把它看作是整个系统的一个子问题，而将它子最优化，从而得出这一阶段的相应决策。然后，把最后两个阶段看成第二个子问题，利用已得前一子问题子最优化的结果，对其进

7、行子最优化，并得出倒数第二个阶段的相应决策。如此继续，直至第一阶段，即可求出全过程的最优决策序列。用上述方法，通过由后向前逐阶段求解由后部各阶段（或称后部子过程）构成的子问题，就把求解原来的n阶段问题，简化成了求解n个单阶段子问题。图5.3表明了这种求解过程，并且虚线框代表由后部子过程构成的子问题。基于以上分析，在用动态规划的方法解决实际问题时，通常都先将原来的问题划分成若干个阶段，并从最后一个阶段开始，由后向前逆向递推寻优。求解例1时将整个过程划时代发为四个阶段，第一阶段包括路段ab和ac，第二阶段包括路段bd、be、ce和cf，第三阶段包括路段dg、eg、eh、ei和fi，第四阶段由路段g

8、j、hj和ij组成（图5.4）。求最短路时由第四阶段开始，沿与过程行进方向相反的方向逆向递推进行。 图5.32状态（state）状态表示过程（系统）的状况或所处的位置，进行到某一阶段的系统可处于若干个不同的状态。在例1中，可把某阶段所含路段的起点（也是前一阶段中路段的终点）定义为该阶段的状态，这样一来，其第一阶段有一个状态：a点；第二阶段有二个状态：b点和c点；。选择的状态构成该阶段的状态集合。在例1中，=a，=b，c，=d，e，f，=g，h，i。3决策（decision）对于处于某一状态的系统，决策者可以作出不同的决策，而使系统沿着不同的方向演变，结果达到下一阶段的某个状态。描述采取不同决策

9、的变量称为决策变量。在进行决策时，决策变量的选取要受到某些条件的影响而只能限于某种范围，这一范围构成允许决策集合。常用表示阶段的决策变量，表示阶段的允许决策集合，显然，它们都是状态变量的函数。若系统在阶段处于状态，则有从n阶段决策过程第一阶段的某一状态出发，逐阶段作出决策构成的策略，称为全过程策略，简称策略，记为 （5.1）而与阶段到最终阶段的后部子过程相对应的策略称为予策略，记为 （5.1）4指标函数和阶段收益（return）指标函数是用以衡量多阶段决策过程实现效果的一种数量指标，是定义在全过程和所有后部子过程上的数量函数，显然，它和起始状况以及以后各阶段的决策有关，可表示为=1，2，n阶段

10、收益是系统通过某一阶段对于指标函数的贡献，它与所处的状态和决策者的决策有关，若用表示阶段的阶段收益，则可写成 （5.3）在上述最短路问题中，阶段收益是旅行者通过该阶段中某一路段所走的距离，而指标函数则是他从某节点起到达终点所走的距离之和。对于阶段的某一状态来说，若从它出发并选定了一确定的策略（或后部子策略），则状态就得到了一确定的指标函数值，这个值也称为该状态的值。策略不同，得出的状态的值也不同。在最优策略下状态的值，是状态的最优值，记为（以后常简记为）。 在例1中，节点e的状态的值有三个：7、6、8；节点a的状况的值有八个，而其最优值为9。由以上讨论可知，指标函数由阶段收益构成，其间的关系主

11、要有以下两种：（1）指标函数为阶段收益之和 （5.4）（2）指标函数为阶段收益之积 （5.5）三、动态规划的基本原理1最优性原理（principle of optimality）现再看例1的最短路问题，已求出最短路线是abehj。我们指出：在最短路线上的任一点，它到终点的最短路也在这条路线上。例如点e到终点j的最短路线是ehj，而不会是别的，如若不然，abehj就不会是a到j的最短路线，也是其上任一点到终点的最短路线。根据以上说明，即可了解下面陈述的最优性原理：在多阶段决策过程中，最优决策序列具有这种性质，即不管该序列上某状态以前的状态和决策如何，余下的决策序列必构成该状态的最优决策序列。最优

12、性原理是动态规划理论的核心，它是由rbellman首先提出的。这个原理说明，最优策略的任一后部子策略也是最优的。根据这个原理，在用动态规划的方法求解多阶段决策问题时，各状态前面的状态和决策，对其后面的子问题来说，只不过相当于其初始条件而已，并不影响后面过程的最优决策。2动态规划的函数方程由以上说明可知，在用动态规划的方法逐阶段求解n阶段决策问题时，要利用第阶段与第+1阶段之间的如下关系：上述方程为动态规划的函数方程，或称为动态规划的基本方程。它反映了一种递推关系，动态规划就是借助于这种递推关系来求解的。根据问题的性质，opt可用max，也可用min。对应于式（5.4）和（5.5）这两种情况，有

13、若已知第阶段的状态，则当该阶段的决策确定之后，就完全确定了下一阶段（+1阶段）的状态，故和的函数，即 （5.9）上式称为状态转移方程，或变换方程。它给出了状态转移规律。四、建立动态规划的数学模型为了用动态规划的方法解决实际问题，首先必须建立动态规划的数学模型。这主要指的是解决好以下几个问题。1划分阶段划分阶段是用多阶段决策过程描述一个实际问题的第一步，通常可根据问题的性质，按照时间、空间、变量等进行划分。2确定状态变量及状态集合多阶段决策过程的进展，可用各阶段的状态演变来描述。因而，先取的状态变量应能反映过程的演变特征，并要满足无后效性的要求。所谓无后效性指的是：若已知过程已处于某阶段的某一状

14、态，则该阶段以后过程的演变，就不再受以前各阶段状态的影响。这就是说，过程的过去历史只能通过当前的状态去影响它未来的发展，当前状态是未来过程的初始状态。在建立实际问题的动态规划模型时，若选取的状态变量不能使它描述的过程具有无后效性，就不能把它作为动态规划模型中的状态变量。这时，需要适当改变状态的规定方法，以实现无后效性的要求。决定了状态变量之后，还需对实际问题的情况进行分析，以确定状态集合，即各个阶段状态变量的可能取值范围。确定决策变量及允许决策集合决策变量是决策者对系统实施控制的手段，它应能体现决策者对系统发展的能控作用。在确定允许决策集合时，应考虑到一切可能情况，它通常是由系统状态和最优化的

15、目的所决定的。4建立状态转移方程状态转移方程如式（5.9）所示，它给出了状态转移的规律。当阶段的状态变量和决策变量的数值取定时，如果第+1阶段的状态变量的值也随之确定，则称这种多阶段决策过程为确定性多阶段决策过程，；如果对于确定的和，相应的不确定，而是具有某种概论分布的随机变量，则这种多阶段决策过程就是随机性的。5确定各阶段的阶段收益通过对各阶段的分析，弄清（5.3）式的函数关系，以便计算系统各阶段对指标函数的“贡献”。6确定指标函数，建立动态规划的函数方程分析指标函数和阶段收益的关系，构造指标函数的结构。在动态规划中要求指标函数按阶段是可分的，同时随阶段的推移单调变化，以便将指标函数写成动态

16、规划函数方程所要求的递推关系。式（5.4）和（5.5）给出的这两种指标函数都满足上述第一项要求，在适当限制下（例如，对式（5.4），各阶段收益均非负（或非正）；对式（5.5），各阶段收益均不小于1（或均不大于1），也容易使它们满足第二项要求，因而易于建立相应的函数方程（见（5.7）（5.8）。7确定边界条件边界条件是指过程开始和结束时的状况。包括过程的初始状态、终止状态、起始时状态的值、终止时状态的值。初步建立了动态规划的模型之后，还要进一步综合检查一下，看它是否正确地表达了对原来问题的要求和各项限制条件。为了形象和有条理地表达出名阶段之间的关系，在分析多阶段决策过程时常运用图5.5所示的流向

17、图。图中小方框表示阶段，其中的数字为阶段的编号，其它符号的意义与前述相同。下面通过两个简单的例子，说明用动态规划方法解决问题时的建模过程及求解技术。第一个例子是连续变量问题（变量连续取值），第二个例子是离散变量问题。例2 一个线性规划问题某工厂现有资金30万元，可用于生产两种产品。已知生产1吨第一种产品需要资金3万元，可获利1.5万元；生产1吨第二种产口需要资金5万元，可获利2万元。问应生产这两种产品各多少吨，才能使获得的利润最大。解 设生产第一、二种产品分别为吨和吨，则可写出其数学模型如下： embed equation.3 这是一个线性规划，现用动态规划的方法求解。将该问题划分为两个阶段：

18、以向第一种产品提供生产投资为第一阶段，向第二种产品提供投资为第二阶段。或者说以变量为第一阶段，变量为第二阶段。以可以提供的资金作为状态变量。从而，第一阶段的状态变量=30（这也是初始条件），第二阶段的状态变量=303，剩下的资金为=3035。显然，只取一个值（等于30），和可在030之间取值。以各阶段生产的产品数量作为本阶段的决策变量，这样就有：，。根据以上规定，可得状态转移议程如下： 在确定和的允许决策集合上界时，应注意不能使和小于零。阶段收益为各阶段提供的利润，即，。指标函数为=+=+，并要求极大化。以上各点集中反映在下面的流向图（图5.6）中。其函数方程是现进行递推计算。子问题1（阶段2

19、）： 图5.6或得到，子问题2（阶段2、1）或得到 ，这时，从而。最优决策序列为 ，即生产第一种产品10吨，不生产第二种产品，获得的利润是15万元。例3 某工厂正在进行a、b、c三种新产品的试制，估计其试制成功的概率分别为0.5、0.4、0.3。因急于推出新产品，厂领导决定再增拨3万元研制费，以期提高新产品试制成功的概率。根据专家估计，增加研制费后试制成功的概率如表5.1所示。试将研制费分配给各新产品试制项目（不分配，或分配给1万元、2万元、3万元），以使这三种新产品均试制成功的概率为最大。表5.1增加研制费数额（万元）新 产 品abc01230.50.60.750.850.40.50.70.

20、90.30.40.650.8解 首先构造动态规划模型，再进行数值计算。阶段：以向某一新产品的研制工作提供研制费作为一个阶段，如此，可分为三个阶段，在阶段1、2、3分别向a、b、c新产品试制工作增拨研制费。状态变量：以可能提供的研制费作为状态变量，其取值范围是0、1、2、3（万元）。决策变量：以给某项新产品试制工作提供的研制费额作为决策变量，它应满足的条件。状态转移方程：由对和的规定，应有阶段收益：以某种新产品试制成功的概率为阶段收益，其值已载于表5.1中。指标函数：由于各产品试制成功为独立事件，故可以各阶段收益的乘积作为指标函数，并要求极大化。如此，可写出函数方程如下： =3，2，1边界条件：

21、在开始时的可用金额为3万元，最后应将提供的费用全部用完，故有=3，=0；此外，=1。其流程图示于图5.7中。图5.7下面按逆向递推做数值计算，因是离散问题，宜列表进行。各步计算按次序示于表5.2、5.3和5.4中。 子问题1（阶段3，新产品c） 表5.2012301230.300.400.660.800.300.400.660.800123 子问题2（阶段3、2，新产品c、b） 表5.3012301230.30.3=0.120.40.4=0.160.40.66=0.2460.40.8=0.320.50.3=0.150.50.4=0.200.50.66=0.330.70.3=0.210.70.4

22、=0.280.9.03=0.270.120.160.2640.330001 子问题3（阶段3、2、1，新产品c、b、a） 表5.4012330.50.33=0.1650.60.264=0.15840.750.16=0.120.850.12=0.1020.1650 第二节 动态规划和静态规划的关系动态规划、线性规划和非线性规划都是属于数学规划的范围，所研究的对象本质上都是一个求极值的问题，都是利用迭代法去逐步求解的。不过，线性规划和非线性规划所研究的问题，通常是与时间无关的，故又称它们为静态规划。线性规划迭代中的每一步是就问题的整体加以改善的。而动态规划所研究的问题是与时间有关的，它是研究具有多

23、阶段决策过程的一类问题，将问题的整体按时间或空间的特征而分成若干个前后衔接的时空阶段，把多阶段决策问题表示为前后有关联的一系列单阶段决策问题，然后逐个加以解决，从而求出了整个问题的最优决策序列。因此，对于某些静态的问题，也可以人为地引入时间因素，把它看作是按阶段进行的一个动态规划问题，这就使得动态规划成为求解一些线性、非线性规划的有效方法。由于动态规划方法有逆序解法和顺序解法之分，其关键在于正确写出动态规划的递推关系式，故递推方式有逆推和顺推两种形式。一般地说，当初始状态给定时，用逆推比较方便；当终止状态给定时，用顺推比较方便。考察如图8-6所示的n阶段决策过程。图8-6其中取状态变量为，；决

24、策变量为，。在第k阶段，决策使状态（输入）转移为状态（输出），设状态转移函数为 k=1，2，n假定过程的总效益（指标函数）与各阶段效益（阶段指标函数）的关系为其中记号*可都表示为“+”或者都表示为“”。问题为使达到最优化，即求opt 。为简单起见，不妨此处就求max 。一、逆推解法设已知初始状态为。并假定最优值函数表示第k阶段的初始状态为，从k阶段到n阶段所得到的最大效益。从第n阶段开始，则有其中是由状态所确定的第n阶段的允许决策集合。解此一维极值问题，就得到最优解和最优值。要注意的是，若只有一个决策，则就应写成。在第阶段，有 embed equation.3 其中。解此一维极值问题，得到最优

25、解和最优值在第k阶段，有其中。解得最优解和最优值。如此类推，直到第一阶段，有其中。解得最优解和最优值。由于初始状态已知，故和是确定的，从而也就可确定，于是和也就可确定。这样，按照上述递推过程相反的顺序推算下去，就可逐步确定出每阶段的决策及效益。例3 用逆推解法求解下面问题max z =解 按问题的变量个数划分阶段，把它看作为一个三阶段决策问题。设状态变量为、，并记= c；取问题中的变量、为决策变量；各阶段指标函数按乘积方式结合。令最优值函数表示为第k阶段的初始状态为，从k阶段到3阶段所得到的最大值。设 = += += c则有 = 0 0= c于是用逆推解法，从后向前依次有及最优解由 得和=0（

26、舍去）又 ，而0，故为极大值点。所以及最优解象前一样利用微分法易知 故 由于已知= c，因而按计算的顺序反推算，可得各阶段的最优决策和最优值。即，由所以，由，所以，。因此得到最优解为：，；最大值为：max z =。二、顺推解法设已知终止状态，并假定最优值函数表示第k阶段末的结束状态为，从1阶段到k阶段所得到的最大收益。已知终止状态用顺推解法与已知初始状态用逆推解法在本质上没有区别，它用当于把实际的起点视为终点，实际的终点视为起点，而按逆推解法进行的。换言之，只要把图8-6的箭头倒转过来即可，把输出看作输入，把输入看作输出，这样便得到顺推解法。但应注意，这里是在上述状态变量和决策变量的记法不变的

27、情况下考虑的。因而这时的状态变换是上面状态变换的逆变换，记为。从运算而言，即是由和而去确定的。从第一阶段开始，有其中解得最优解和最优值只有一个决策，则就写成。在第二阶段，有其中，解得最优解和最优值。如此类推，直到第n阶段，有其中。解得最优解和最优值。由于终止状态是已知的，故和是确定的。再按计算过程的相反顺序推算上去，就可逐步确定出每阶段的决策及效益。应指出的是，若将状态变量的记法改为、，决策变量记法不变，则按顺序解法，此时的最优值函数为。因而，这个符号与逆推解法的符号一样，但含义是不同的，这里的是表示k阶段末的结束状态。例4 将例3用顺推解法解之。解 设= c，令最优值函数表示第k阶段末的结束

28、状态为，从1阶段到k的阶段的最大值。设 ，则有 ，0，0于是用顺推解法，从前向后依次有及最优解及最优解。及最优解。由于已知，故易得到最优解为，；相应的最大值为max z =。现在再考虑若是已知初始状态= c，将例3用顺推解法又如何进行呢？因这时的状态转移函数为，1，2，3。为了保证决策变量非负，必须有c。因此，设 ，则有 ，0， 0。于是用顺推解法，从前向后依次有 及最优解 及最优解 及最优解由于终止状态不知道，故须再对求一次极值，即显然，只有当=0时，才能达到最大值。然后按计算顺序反推算可求出各阶段的最优决策及最优值。最后得到最优解为，；最大值为max z =。注：若记状态变量为、，取= c

29、；决策变量记法不变；令最优值函数表示第k阶段末的结束状态为，从1阶段到k阶段的最大值。则按顺推解法，从前向后依次为例5 用动态规划方法解下面问题max f =解 按问题中变量的个数分为三个阶段，设状态变量为、，并记9；取、为各阶段的决策变量；各阶段指标函数按加法方式结合。令最优值函数表示第k阶段的结束状态为，从1阶段至k阶段的最大值。设 ，则有 ，于是用顺推方法，从前向后依次有 及最优解 由 解得 因该点不在允许决策集合内，故无须判别。因而的最大值必在两个端点上选取。而 ，所以的最大值在=0处，故得到及相应的最优解=0。由 解得 又 0，故该点为极小值点。而 ，故的最大值点在处。所以得及相应的

30、最优解由于不知道，故须再对求一次极值，即显然，当=9时才能达到最大值。所以为最大值。再按计算的顺序反推算可求得最优解为=0，=0，=9；最大值为max f =注：（1）若先作代换，令，。将原问题变为max f =再解此问题，然后换回也可以。（2）在计算的最大值中，若学习了凸函数的性质，也可利用凸函数的性质来确定最大值。三、动态规划的计算框图在实际问题中，函数序列往往不能表示为解析形式；再状态变量和决策变量即使是离散的，其集合也很大。这样，求和最优策略的数值解计算量就很大，一般要用计算机来解决。一面讨论逆序解法的迭代计算程序。由于始端可能是自由状态或固定状态两种情况，终端也可能是自由状态或固定状

31、态两种情况，因而组合起来就有四种情况。这里，仅讨论终端自由而且始端自由或固定的两种情况的计算框图。至于终端固定的情况框图类似，就不讨论了。为明确起见，假设：决策变量是连续实变数，允许决策集合是实数集合；状态变量也是连续实变数，各段可达状态集合的实数闭区间是，对于始端固定的状态变量，各段可达状态集合的实数闭区间是。在计算前，先要把离散化。为此，要选好适当的增量。在第k段，计算将在点列上进行，其中是满足的正整数。根据一般的逆序动态规划的基本方程：其中。且（1）当固定时，；（2）当自由时，。因而可得动态规划的逆序解法计算程序框图，如图8-7所示。这里对框图作几点说明：（1）图8-7中，左边部分是指标

32、函数序列的递推计算，它是逆序的，即k由n逐步减小到1；右边部分是最优决策序列的递推计算，它是顺序的，即k由1逐步增大到n。（2）若实际问题要求的不只是整个过程的最优解，而且要求出从各段出发的最优策略和最优值。则在程序中，对每一k段，计算完和后就可输出，如图中的虚线所示。如不需要输出，可把右边部分框图取消。（3）框图中包含（1）固定始端和（2）自由始端两种情况。它们的区别是，左边部分输入数据不同，右边部分在自由始端（2）情况下，还需多求一次最优值计算。因只在计算k段时有用，到k1段就没用了。故在计算k段时，都要存入内存，在计算k1段时，可用把替换掉。函数在左边部分计算出来后不要用，可送入外存。在

33、右边部分求需用时，再依k的序列将由外存移入内存。（5）在计算时，在点列上取值，对于点(0j)，点不一定在的点列中，这时，必须选择适当的内插公式，由在点列上的值求它在点上的值。逆序解法计算程序框图：（1）固定始端；（2）自由始端。逆序求最优值 顺序求图8-7 动态规划逆序解法计算程序框图最后应指出的是，在这里运用递推关系逐步求出极值函数、及相应的决策函数、，这是一种通过函数值不断的迭代过程，而逐步达到最优值，通常称为函数空间迭代法。这种迭代方法，不仅对像例1那样阶段数为确定有限值的定期多阶段决策过程有效，而且，对在实际问题中，出现的动态规划基本方程，不是一个递推方程，而是为某函数的泛函方程，那种

34、阶段数为有限但不固定的不定期多阶段决策过程或阶段数为无限（或很大）的无期多阶段决策过程也是一种重要的求解方法。还有对解上述两类过程比函数空间迭代法的收敛速度要快些的策略空间迭代法。函数空间迭代法和策略空间迭代法都是动态规划求解不定期或无期的多阶段决策过程的两种重要方法。由于篇幅有限，这里就不介绍了。有兴趣的读者可参见参考资料1和2。第三节 动态规划应用举例一、背包问题一架货运飞机，有效载重量为24t，可运输物品的重量及运费收入见表8-7，问题是选哪几件物品使收入最多。这类问题称为背包问题（一个徒步旅行者在他容量有限的背包里放置哪些旅行必需品使总价值最大的问题）。问题可以按物品数划分为6个阶段（

35、k=1，2，6），假定实际过程是先决定是否运送物品因而求解时第k阶段的决策变量可取两个值：=0（不运）=1（运）。第1阶段可能的状态是=0，1，2，24，但可将0，1，2，7合并为一类，8，9，24合并为一类，因为为了运送物品1，至少需要8t表8-7 物品重量（t）收入物品重量（t）收入1238136852456987423剩余吨位，=0，1，2，7时能采取的决策是相同的，即=0。在这一阶段。，（当8）。计算结果如表8-8。一栏表示在相应状态下最优决策变量。如果状态在824范围内，最优决策是运送物品1：表8-8 =0=1078240080108=1（运）。第2阶段：=0，对一切，=5，13。状

36、态转移方程是：（为物品的重量）。对于本阶段：=。在列举本阶段可能的状态时，我们也希望将那些具有相同计算结果的状态加以合并，以减少计算次数，如果只孤立地考虑阶段2，则可将的可能值024和1324两个小区间，因为在012区间内只能决定不运物品2，而在1324区间内，都同样可以作运或不运两种决策，但是这样划分区间是不正确的，例如=7和=8时，不相等：所以在确定状态划分区间时需要同时考虑阶段1和阶段2。为此可以借助矩阵形式找出所谓隔开值。矩阵的第0列是只考虑阶段2决策的隔开值。然后将元素（i，0）与元素（0，j）相加，得元素（i，j），元素（i，j）就是阶段2隔开值，i=1，2，j =1，2，隔开值矩

37、阵如下：（k = 2）0 13 第0行0 0 13 第1行（k = 1）8 8 21 第2行第0列 第1列 第2列因此将区间024分成07，812，1320，2124四个小区间。第2阶段的决策过程如表8-9。表8-9 =0=1078121320212403335800110358举两个例子说明表8-9中数字的计算：当=812时，。当=2124时，。现在考虑第3阶段。首先列出求隔开值的矩阵：（k = 3）0 6 0 0 13 （k = 2）8 8 21 13 13 1921 21 27阶段3的小区间为05，67，812，13，1418，1920，2124。本阶段的决策如表8-10。表8-10 =

38、0=1056781213141819202124003555822257701000,1100235578如果可运输的物品只有1，2，3三种，那么计算到这个阶段就得到了最优解。最优策略是不运物品3（=24，表8-10中末行：=0），运物品2（=240=24，表8-9中末行：=1），运物品1（=2413=11，表8-8中末行：=1）。如果飞机吨位只有14t，则有两个最优策略。一个是不运物品3（表8-10中=14一行中有两个值，取=0），运物品2（=14，表8-9中=14一行：=1），不运物品1（=1413=1，表8-8中=1一行：=0）。另一个最优策略是运物品3（取表8-10中=14一行的另一个

39、值，即=1），不运物品2（=146=8，表8-9中=8一行=0），运物品1（=80=8，表8-8中=8一行，=1）。现在回到原来的问题上来，第4阶段到第6阶段的决策，请读者自己完成。这里需要指出，对于已计算机完毕的第1，2，3三个阶段，实际是最后三个决策阶段，由于前面各实际决策阶段的决策组合是多种多样的，因而每个阶段可能的状态就很多，甚至不妨认为有024共25种状态。但是前面的实际决策阶段，可能的状态并不多。例如第6阶段的状态只能是24，第5阶段的可能状态只能是24（如果=0）和17（如果=1），因而不必求出隔开值，将024区间划分为小区间。第二节 生产计划问题某工厂与一个顾主订立合同，在4个

40、月内出售一定数量的某种产品。工厂每月最多生产100单位，产品可以存贮，存贮费用为每单位每月2元，各月的需要数量及单位产品的生产成本如表8-11所示。表8-11 月份单位生产成本（元）需要量月份单位生产成本（元）需要量127072807034807612060现在来确定每月的生产量，要求既能满足各月的合同需求量，又使生产成本和存贮费用之和达到最小。这是一个4阶段的动态规划问题，实际决策的第1阶段是1月份，逆序解题第1阶段是4月份。状态变量和决策变量的含义：第k阶段开始时的产品数；第k阶段的产量（为简化计算，限制为10的倍数）。还规定：第k阶段的单位生产成本；第k阶段的需求量。直接指标的函数式为：

41、 （8-5）状态转移方程为： （8-6）指标递推方程为： （8-7） 。 （8-8）现在逐阶段进行递推计算。在解题过程中，需根据约束条件确定各个阶段可能的状态和决策。在第1阶段（4月份），由于头3个月的最大产量为300单位，需求量为250单位，所以4月初的最大存贮量等于50单位（300-250=50）。产量又限为10的倍数，所以4月初可能的存贮量是0，10，20，30，40，50。每一状态只能有一种决策，因为月初存量加产量应恰好为4月份的需求量60单位。第1阶段的决策见表8-12。表8-12 0102060504045603820308030405030201023401600360表中数字计

42、算举例：，。在阶段2，月初最大存贮量为70，又因为100，120，所以应有20，即月初最低存贮量为20。各种状态下决策的计算见表8-13。=50=60=70=80=90=100203040506070870094808760102609540882011040103209600888011820111001033096608940125001188011160104409720900010090807060501260011320110401026094808700表中数字计算示例：在阶段3，月初的最大存贮量是40。因为后3个月的需求量为250，而生产能力为300，所以本阶段初的最低存贮量是0

43、。上面说过，阶段2的月初存贮量（即阶段3的月末存贮量）应不小于20，即应有20，不满足此式的决策为不可能的决策。本阶段每一种状态下不同决策的费用计算和最优决策见表8-14。表8-14 =50=60=70=80=90=10001020304016280169801622017680176201616018380176201686016100190801832017560168001604019020182601750016740159801001001001001001902018260175001674015980举两个计算例子：在阶段4，假定初始状态为0（即1月初的存贮量为0），需求量为60

44、，所以决策变量应不小于60，计算结果见表8-15。表8-15 =60=70=80=90=1000232202316023100230402298010022980至此，即可制定出4个月的最优生产计划，如表8-16所示。最优生产计划表8-16 月 份月初存贮量产 量销售量生产成本存贮费总费用12340407001001005060607012060700072004000456008014007000728041404560注意每个阶段在计算时，无论为何值，都是随的增大而增大（如第2阶段），或随的增大而减小（如第3阶段），呈线性关系；同样，显然也是的线性性函数。这就使我们有可能在计算时不必列举各种可能的状态变量值和决策变量值，而以和的函数式表示，最终找到最优策略。这种做法，实质上是考虑了一切可能的状态和决策（状态变量和决策变量可以连续取值），而计算却大大简化。下面介绍这种解法。这一解法，其阶段的划分，状态和决策的定义，状态转移方程