运筹学第06章动态规划

1、第六章 动态规划 (Dynamic programming)多阶段决策问题及其举例 动态规划的基本概念及基本方程 资源分配问题 生产与存储问题 背包问题 其他动态规划问题WinQSB软件应用 动态规划是解决多阶段决策问题最优化的一种数学方法，大约产生于50年代，1951年美国数学家数学家贝尔曼(R.Bellman)等人根据多阶段决策问题的特点，把多阶段决策问题变换为一系列相互联系的单阶段问题，然后逐个加以解决。与此同时他提出了解决这类问题的最优性原理，研究了许多实际问题，从而创立了解决最优化问题的一种新方法动态规划（Dynmamic Programming），他的名著动态规划于1957年出版。

2、 动态规划问世之初，受计算技术水平的限制，对人们所关心的许多复杂问题难以进行处理。以后,随着计算技术的进步,动态规划的思想方法,在工程技术、企业管理、工农业生产以及军事等部门都有广泛的应用。例如在企业管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等等。 第一节 多阶段决策问题及其举例 动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个n 维决策问题变换为几个一维最优化问题，从而一个一个地去解决。 需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。必

3、须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。 多阶段决策过程最优化的目标，就是要在所有可采取的策略中选取一个最优的策略，从而使整个过程在预定目标下达到最好的活动效果。 所谓多阶段决策问题是指这样一类活动过程：由于它的特殊性，可将整个过程按照时间划分为若干个互相联系的阶段，在它的每一个阶段都需要作出决策，当各个阶段决策确定后，就组成了一个决策序列，因而也就确定了整个过程的一条活动路线。如下图： 12n状态决策状态决策状态状态决策状态 2、即在系统发展的不同时刻（或阶段）根据系统所处的状态，不断地做出决策；一、动态决策问题的特点 1、系统所处的状

4、态和时刻是进行决策的重要因素；3、找到不同时刻的最优决策以及整个过程的最优策略。二、多阶段决策问题举例 如果由A点经过P点和H点而到达G点是一条最短线路，则由P点出发经过H点到达终点的这条子线路，相对于从P点出发到达终点的所有可选择的不同线路来说，PG为最短线路。 【例6-1】生产与存贮问题。某工厂每月需供应市场一定数量的产品，并将所余产品存入仓库。一般某月适当增加产量可降低生产成本，但超产部分存入仓库会增加库存费用。要求确定一个逐月的生产计划，在满足需求的条件下，使一年的生产与存贮费用之和最小。 本例中，我们可以把每个月作为一个阶段，全年分为12个阶段逐次决策。 【例6-2】设备更新问题。企

5、业在使用设备时都要考虑设备的更新问题，因为设备越陈旧所需的维修费用越多，但购买新设备则要一次性支出较大的费用。现某企业要决定一台设备未来8年的更新计划，已预测了第j 年购买设备的价格为Ki，设Gj为设备经过 j 年后的残值，Cj为设备连续使用j-1年后在第j 年的维修费(j =1，2，n)，问应在哪些年更新设备可使总费用最小。 【例6-3】投资决策问题。某公司现有资金Q万元，在今后5年内考虑给A、B、C、D四个项目投资，这些项目投资的回收期限、回报率均不相同，问该公司应如何确定这些项目每年的投资额，使到第5年年末拥有资金的本利总额最大。这是一个5阶段决策问题。 第二节 动态规划的基本概念及基本

6、方程一、动态规划的基本概念 【例6-4】最短路问题。今有如图6-2所示交通网络，顶点连接线段上的数字表示两地距离，求s至t距离最短的线路。 1、阶段 把一个问题的过程，恰当地分为若干个相互联系的阶段，以便于按一定的次序去求解。 描述阶段的变量称为阶段变量，通常用k表示。阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。8A1A2A3sB1B2B3C1C2t6473643562652744445 例6-4中，从s到t可以分成四个阶段：sA(A有三种选择，A1或A2或A3)，AB(B1或B2或B3)，BC(C1或C2)，Ct，因此k1，2，3，4。 表示每个阶段开始

7、所处的自然状况或客观条件。 状态变量的取值有一定的允许集合或范围，此集合称为状态允许集合，第k阶段的可能状态集用Sk 表示。2、状态 描述各阶段状态的变量称为状态变量，常用sk表示第k阶段的状态变量。 在例6-4中，第一阶段有一个状态s，则S1=s；第二阶段的状态有A1、A2、A3三个，则S2=A1,A2,A3；第三阶段的状态也有B1、B2和B3三个，则S3=B1,B2,B3；第四阶段的状态有两个，C1和C2，记为则S4=C1,C2。 3.决策和策略 当各阶段的状态确定以后，就可以做出不同的选择，从而确定下一阶段的状态，这种选择称为决策。 表示决策的变量称为决策变量，用uk(sk)表示第k阶段

8、状态为sk 时的决策变量。在实际问题中，决策变量的取值往往限制在一定范围内，我们称该范围为允许决策集合，用Dk(sk)表示第k阶段状态为 sk 时的允许决策集合，显然uk(sk)Dk(sk)。 在例6-4中，从第二阶段的状态A1出发，可选择下一阶段到达B1、B2或B3，即第二阶段状态为A1时的允许决策集合为D2(A1)=B1，B2，B3。如决定选B2，则可表示为u2(A1)=B2。4.状态转移方程 各阶段的决策确定后，整个问题的决策序列就构成一个策略。含n个阶段的动态规划问题的策略可表示为u1(s1)，u2(s2)，un(sn)。自第k 阶段开始到最后第 n 阶段的决策序列称为k子策略，记为u

9、k(sk)，uk+1(sk+1)，un(sn)。 动态规划中本阶段的状态往往是上一阶段状态和上一阶段的决策结果。如果给定了第k 阶段的状态sk，本阶段决策为uk(sk)，则第k+1阶段的状态sk+1也就完全确定，它们的关系可表示为： 由于它表示了由k 阶段到k+1阶段的状态转移规律，所以称为状态转移方程。 5.指标函数 阶段指标函数 阶段指标函数是指第k 阶段，从状态sk 出发，采取决策uk(sk)时的效益，用vk(sk，uk)表示。 过程指标函数 过程指标函数是指从第k阶段的状态sk(k1，2，n)出发，采取某种策略到第n阶段的终止状态时的效益，它与所选取的策略有关，因此常记作： 常用的指标

10、函数的形式有各阶段指标函数的和的形式和积的形式两种。 和的形式 积的形式 指标函数的最优值称为最优值函数，是指对某一确定状态选取最优策略后得到的指标函数值。对应于从状态sk 出发的最优子策略的最优值函数，记为fk(sk)，则有： 其中opt表示最优化，可根据具体问题取max(求最大)或min(求最小)。 二、动态规划的数学模型 动态规划的数学模型可以描述如下： 建立实际问题的动态规划模型一般可遵循以下步骤： 第一，按时间或空间顺序将多阶段决策问题划分为适当的阶段； 第二，恰当选择状态变量sk，使它既能确切地描述过程的演变，又满足过程的无后效性； 第三，确定决策变量uk 及每阶段的容许决策集Dk

11、(sk)。状态变量和决策变量可以是连续的，也可以是离散的； 第四，正确写出状态转移方程sk+1Tk(sk，uk)； 第五，正确写出指标函数Vk,n，它应具有可分离性，并满足递推关系。 三、动态规划的基本方程 在n阶段决策过程中，当指标函数满足 时，根据最优值函数的定义有：当指标函数满足 时，有：动态规划的求解有两种基本方法：逆序解法和顺序解法。 若寻优方向与实际行进方向相反，即从最后一阶段开始计算，逐段前推，求得全过程的最优解，则称为逆序解法。 若寻优方向与实际行进方向相同，计算时从第一阶段开始向后递推，计算后一阶段要用到前一阶段的结果，最后一阶段的结果就是全过程的最优结果，则称为顺序解法。

12、下面我们用例6-4来说明顺序解法。 将求s至t的最短路问题视为一个四阶段决策问题，设： sk 第k 阶段的初始状态。 sk+1 第k 阶段的终止状态。 uk 第k 阶段选择的路线。状态转移方程：skuk(sk+1) vk(sk+1，uk)第k 阶段选择路线uk 时增加的距离，即从初 始状态sk 到sk+1 的距离。 fk(sk+1)从起点s到第k阶段终止状态sk+1 的距离。 于是，可得下面的动态规划基本方程： k=0时，f0(s1)= f0(s)=0，这是边界条件。 k=1时，S2=A1，A2，A3 8A1A2A3s64k=2时，S3=B1，B2，B3 B1B2B38A1A2A3s64736

13、435626即从s到B1的最短路线为：sA2B1或sA3B1。 即从s到B2的最短路线为：sA3B2。 即从s到B3的最短路线为：sA3B3。 C1C2B1B2B38A1A2A3s64736435626527444k=3时，S4=C1，C2 即从s到C1的最短路线为：sA2B1C1 或sA3B1C1。 即从s到C2的最短路线为：sA3B2C2。 k=4时，S5=t 即从s到t的最短路线为：sA3B2C2t。 t4C1C2B1B2B38A1A2A3s647364356265274445即从s到t的最短距离为：4+2+4+5=15第三节 资源分配问题 资源分配问题就是将一定数量的一种或几种资源恰当

14、地分配给若干使用者，以获取最大效益。这里的资源可以是资金、设备、原材料、劳动力等。资源分配问题是动态规划的典型应用之一。本节和后面几节中我们都采用逆序解法来求解动态规划问题。 一、一维资源分配问题 假设某部门掌握总数为a的某种资源，现有n 个项目提出对这种资源的需求。若把数量为xk 的资源分配给第k 个项目，则其相应的收益为gk(xk)。问应如何分配这种资源，才能获得最大收益？ 这个问题可写成如下的规划模型： 把它看做一个多阶段决策问题，从而应用动态规划方法求解。确定一个项目的资源分配数量视为一个阶段，于是共有n个阶段。令： sk 分配给第k 个项目到第n 个项目的资源数量之和。 xk 分配给

15、第k 个项目的资源数量。 vk(sk，xk)从sk 中取出xk 数量的资源分配给第k 个项目 可获得的收益。即： fk(sk)将数量为sk 的资源分配给第k 个项目到第n 个项 目可获得的最大收益。 于是，可得到下面的状态转移方程和动态规划基本方程： 【例6-5】某公司有资金10万元，若投资于项目xi(i=1,2,3)的投资额为xi时，其收益分别为g(x1)=4x1, g(x2)=9x2, g(x3)=2x32,问应如何分配投资数额才能使总收益最大？ 解:该问题的静态模型为： 将投资项目排序时，首先考虑对项目1的投资，然后再考虑对项目2的投资，最后考虑对项目3的投资，这样可以把问题划分为3个阶

16、段，每个阶段只决定对一个项目应投资的金额。这样就把问题转化为一个3段决策过程。 通常可以把决策变量uk 定为原问题中的变量xk ，即设：uk=xk (k=1,2,3)把每个阶段可供使用的资金定为状态变量sk，初始状态s1=10。当第一阶段(k =1)时，有：当第二阶段(k =2)时，有：第k 阶段时，有：于是，有：阶段k=1,2,3； 状态变量sk ：第k段可以投资于第k 到第3个项目的资金；决策变量xk ：决定给第k 个项目投资的资金； 状态转移方程：sk+1 =sk - xk 最优目标函数fk(sk)：可投资金为sk 时，投资第k-3项所得的最大收益。 该问题的动态规划基本方程为： 指标函

17、数：下面用逆序解法求解例6-5：当k=3时： 显然，当x3=s3时，f3(s3)取得极大值，即：当k=2时：令： 由 所以 为极小值点。 而： 解得： 故极大值只可能在0,s2的端点处取得，则：f2(0)与f2(s2)的关系，有以下三种情况： f2(0)=f2(s2)，即：解得： f2(0)f2(s2)，即：解得： f2(0)f2(s2)，即：当k=1时： 当f2(s2)=9s2为最大时： 当f2(s2)=2s22为最大时：，与s29/2矛盾，所以舍去。 令： 解得：由 解得： 所以 为极小值点。 而： 故极大值只可能在0,s1的端点处取得。比较两个端点：再由状态转移方程顺推得： 因为 所以：

18、 例 设有500万元资金用于扩建三个工厂A、B、C，各厂获得资金后的利润增长额与投资数有关，详细数据如下表所示： 543210C742100B333220A利润增长额543210投资数(百万元)解：将问题视为三个阶段决策问题。sk 表示k 阶段初可用的投资数； uk 为分配给第k 个工厂的资金数； 状态转移方程为sk+1sk - uk fk(sk)表示sk资金被分配给工厂k - n 后，所得利润增长额。 问应如何确定这三个工厂的投资数，使总的利润增长额为最大？ 则该问题的动态规划基本方程为： 当k=3时，s3的可能取值为0、1、2、3、4、5，这些投资全部分配给C工厂，即u3=s3。因此有以下

19、关系式：若s3=0，则：若s3=1，则：若s3=2，则：若s3=3，则：若s3=4，则：543210C742100B333220A利润增长额543210投资数(百万元)若s3=5，则：用表格表示为：543210543210 u3s3012345012345012345 当k=2时，s2的可能取值为0、1、2、3、4、5，这些投资全部分配给B工厂和C工厂，即u2s2。因此有以下关系式：若x2=0，则u2=x2=0 若s2=1，则u2的取值可以为0、1，利用状态转移方程知s3的取值为1、0。 若s2=2，则u2的取值可以为0、1、2，利用状态转移方程知s3的取值为2、1、0。543210C7421

20、00B333220A利润增长额543210投资数(百万元) 若s2=3，则u2的取值可以为0、1、2、3，利用状态转移方程知s3的取值为3、2、1、0。 若s2=4，则u2的取值可以为0、1、2、3、4，利用状态转移方程知s3的取值为4、3、2、1、0。 若s2=5，则u2的取值可以为0、1、2、3、4、5，利用状态转移方程知s3的取值为5、4、3、2、1、0。用表格表示为：543210543210 u2s20+00+10+20+30+40+50+00+10+20+30+41+01+11+21+32+02+12+24+04+17+001234700000/45543210C742100B333

21、220A利润增长额543210投资数(百万元) 当k=1时，s1的可能取值为5，这些投资全部分配给A工厂、B工厂和C工厂，即u1s1。因此有以下关系式：用表格表示为：5543210 u1s10+72+42+33+23+13+070543210C742100B333220A利润增长额543210投资数(百万元)543210543210 u2s20+00+10+20+30+40+50+00+10+20+30+41+01+11+21+32+02+12+24+04+17+00123470123455543210 u1s10+72+42+33+23+13+070543210543210 u2s20+00

22、+10+20+30+40+50+00+10+20+30+41+01+11+21+32+02+12+24+04+17+0012347012345543210543210 u3s3012345012345012345 【例】某企业根据计划安排，拟将某种高效率的设备五台，分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为企业提供的盈利如下表所示。 问：这五台设备如何分配给各工厂，才能使企业得到的盈利最大。 121113512111241111936107245310000丙乙甲 工厂 盈利设备台数 解：将问题按工厂分为三个阶段，即k=1、2、3。 设sk 表示为分配给第k 个工厂至第n

23、 个工厂的设备台数。 状态转移方程为： 表示 sk 台设备分配给第k个工厂至第n个工厂时所得到的最大盈利值。 因而可写出逆推关系式为：表示 uk 台设备分配到第k个工厂所得的盈利值。 下面从最后一个阶段开始向前逆推计算。uk 表示为分配给第k 个工厂的设备台数。121113512111241111936107245310000丙乙甲 543210543210u3*f3(s3)g3(u3)u3s3406111212406111212102345 第三阶段： 设将s3台设备(s3=0,1,2,3,4,5)全部分配给工厂丙时，则最大盈利为：其中x3=s3=0,1,2,3,4,5 因为此时只有一个工厂

24、，有多少台设备就全部分配给工厂丙，故它的盈利值就是该段的最大盈利值，如下表：543210543210 第二阶段： 设把s2台设备(s2=0,1,2,3,4,5)分配给工厂乙和工厂丙时，则对每个s2值，有一种最优分配方案，使最大盈利值为：121113512111241111936107245310000丙乙甲 其数值计算如下表所示：00+40+60+110+120+1255+45+65+115+121010+410+610+111111+411+61111+411501014162110221,22其中121113512111241111936107245310000丙乙甲 第一阶段： 设把s1

25、台(这里只有s1=5的情况)设备分配给甲、乙、丙三个工厂时，则最大盈利值为：其中 因为给甲工厂u1台，其盈利为g1(u1) ，剩下的5u1台就分给乙和丙两个工厂，则它的盈利最大值为f2(5u1) 。其数值计算如下表所示：55432100+2113+09+1012+5210,23+167+1455432100+2113+09+1012+5210,23+167+1454321054321000+40+60+110+120+1255+45+65+115+121010+410+610+111111+411+61111+411501014162110221,22 即得甲工厂分配0台，乙工厂分配2台，丙工

26、厂分配3台。 或：甲工厂分配2台，乙工厂分配2台，丙工厂分配1台。 以上两个分配方案所得到的总盈利均为21万元。 例 现有1000台机床，要投入到A、B两个生产部门，计划连续使用5年。在A部门的收益函数为g(uA)=7uA，其中uA为投入生产的机床数，年末机床完好率为a=0.4；在B部门的收益函数为h(uB)=3uB，其中uB为投入生产的机床数，年末机床完好率为b=0.8求5年间总收益最大的年度机床分配计划方案。 解：这是一个5阶段决策过程，一个年度为一个阶段。利用上述假设，状态转移方程为： sk+1auk+b(sk-uk)=0.8sk-0.4uk (k=1，2，3，4)相应的动态规划基本方程

27、: k=5时，0u5s5，因f6(s6)=0，有： 资源连续分配问题k=4时，0u4s4，由动态规划基本方程得： k=3时，0u3s3，由动态规划基本方程得： k=2时，0u2s2，由动态规划基本方程得： k=1时，0u1s1，由状态转移方程知： 由于阶段1的初始状态s1是唯一给定的，s1=1000，因此，问题的最大总收益为f1(1000)12388.8 。 按计算顺序反向推算，可求出最优策略以及执行最优策略时各阶段初的完好机床数： 二、二维资源分配问题 此问题可写成如下数学模型： 在资源分配问题中，若考虑的资源有两种时，便是二维资源分配问题。一般的二维资源分配问题可叙述如下：某部门具有总数分

28、别为 a 和 b 的两种资源，现有 n 个项目提出对这两种资源的需求。若把数量为 xk 的资源A和数量为 yk 的资源B分配给项目k ，可获得收益vk(xk，yk)。问应如何分配这两种资源，使总收益最大？ 用动态规划方法来求解，状态变量和决策变量要取二维的。 设： (sk，tk)sk 和tk 分别为分配给第k 至第n 个项目的资源A和资源B的总量。 (xk，yk)xk 和yk 分别为分配给第k 个项目的资源A和资源B的总量。 vk(sk，tk，xk，yk)从sk 中取出数量为xk 的资源A，从tk 中取出数量为yk 的资源B分配给项目k 可获得的收益。即： fk(sk，tk)将数量为sk 的资

29、源A和数量为tk 的资源B分配给第k至第n个项目可获得的最大收益。 于是可得下面的状态转移方程和基本方程： 第四节 生产与存储问题 【例6-7】某工厂生产并销售某种产品，已知今后4个月的市场需求预测如表6-8，又每月生产j 单位产品的费用为： 每月库存j 单位产品的费用为E(j)=0.5j(千元)，该厂最大库存容量为3单位，每月最大生产能力为6单位，计划开始和计划期末库存量都是零。试制定4个月的生产计划，在满足用户需求条件下总费用最小。 假设第i+1个月的库存量是第i 个月可销售量与该月用户需求量之差；而第i 个月的可销售量是本月初库存量与产量之和。 4232gi(需求量)4321i(月)解：

30、将每个月视为一个阶段，因此k=1，2，3，4。设 状态变量sk：第k 个月月初的库存量。 决策变量uk：第k 个月的产量。 一、生产瞬时完成 状态转移方程：sk+1skukgk 指标函数：vk(sk，uk)第k 个月的生产和存储费用。即 最优值函数fk(sk)：当第k 个月月初的库存量为sk 时，采取最佳策略生产，从本月到计划结束(第4月末)的最低生产与存储费用。 则动态规划基本方程为： 当k=4时 因为s5=0，故本月产量应为u4g4s44s4，又因为最大库存量为3，故s4只能取0，1，2，3。 则u4 取值4，3，2，3。 列出 与u4(s4)，如表6-9所示：f4(s4)1234u4(s

31、4)3210s4当k=3时 状态变量s3的取值范围，取决于库存能力、产量和需求量。因为最大库存量为3，故s3只能在0，1，2，3中取。 变量u3的允许决策集合，受最大生产能力、最大库存量、需求量和计划期末库存量为0这几个方面的限制，应满足： 76.565.5u3下限u3上限062-s35-s36-s3故有： 对s3=0，1，2，3分别求出f3(s3)的值。 计算过程如表6-10所示。 且取整数 u3*(s3)f3(s3)C+E+f4u3(s3)3210s323451212.51313.5122123411.51212.51311.510123811.51212.580012811.51280当

32、k=2时 类似地，有s2只能取0，1，2，3。 决策变量u2的允许决策集合，它同样受最大生产能力、最大库存量、需求量和计划期末库存量为0这几个方面的限制，应满足： 15.53234u4*(s4)66.57f4(s4)210s4即：且取整数 根据基本方程： 对s2=0，1，2，3分别求出f2(s2)的值。 u2下限u2上限063-s26-s29-s2 u2*(s2) f2(s2)C+E+f3u2(s2)3210s234561818.51616165234517.51815.516.515.5412341717.51516153012313.51714.515.5013.5083012u3*(s3

33、)811.512f3(s3)210s3当k=1时，由于s1=0，故u1的允许决策集合为 ：u1下限u1上限g263+g111即：根据基本方程： 可以列出f1(s1)与u1(s1)，如表6-12所示： 可知，4个月的最低费用为f1(0)=21千元，第一个月的最优产量为2单位。再由计算过程表6-11、表6-10、表6-9可推得最优生产与存储计划为： u1*(s1)f1(s1)Cf25432u1(s1)0s1013.53345u2*(s2)1515.516f2(s2)210s22121.52221.5212083012u3*(s3)811.512f3(s3)210s315.53234u4*(s4)6

34、6.57f4(s4)210s4 即：第一个月生产2单位，第二个月库存为0，生产5单位，第三个月库存为2，不生产，第四个月库存为0，生产4单位。 二、生产需要一定的时间 【例6-8】某工厂生产并销售某种产品，有一个仓库专门存放该产品，仓库最大容量为1000单位。预计未来4个月该产品的需求将有极大的增长，存放的所有产品都能够销售出去。已知第k个月的单位成本为ck，销售单价为pk，如表6-13所示。 1713812销售单价（pk）1511910单位生产成本（ck）4321月份(k) 第一个月初该产品的库存为500单位。由于产品生产周期较长，当月开始生产的产品只能在下个月初入库，因此工厂只能销售仓库现

35、有的货。若不计库存费用，试确定未来4个月的生产与销售计划，使预期获利最大。 解：将每个月视为一个阶段，因此k=1，2，3，4。设： 状态变量sk：第k个月月初仓库的库存量。 决策变量xk：第k个月的销售量。 yk：第k个月开始生产的产量。 状态转移方程：sk+1sk-xkyk 指标函数：vk(sk，xk，yk)第k个月的利润。即： 最优值函数fk(sk)：当第k个月月初的库存量为sk时，从本月到计划结束(第4月末)的最大利润。 则动态规划基本方程为： 当k=4时 显然，当x4*=s4，y4*=0时，f4(s4)取得最大值f4(s4)=17s4。 当k=3时 这个阶段需要求解一个线性规划问题：

36、当x3*=s3，y3*=1000-s3x3=1000时，f3(s3)取得最大值f3(s3)=6000+13s3。 当k=2时 此阶段也需要求解一个线性规划问题： 解得：x2*=0， y2*=1000s2 故当x2*=0， y2*=1000s2 时，f2(s2)取得最大值f2(s2)=10000+9s2。当k=1时，由于s1=500，根据基本方程： 解线性规划问题： 得：x1*=500， y1*=0，f1(500)=16000。 由上述过程逆推可得最优生产与销售计划为： 第一个月月初库存500单位，销售500单位，不生产，第二个月月初库存为0，销售量为0，生产1000单位，第三个月月初库存为10

37、00单位，销售1000单位，生产1000，第四个月月初库存为1000单位，销售1000单位，不生产。 第五节 背包问题 背包问题的一般提法是：一位旅行者携带背包去登山，已知背包最大承重量为a 公斤，现有n 种物品可供他选择装入背包，第i 种物品的单件重量为ai 公斤，其价值(重要性系数)是携带数量xi 的函数ci(xi)(i= 1，2，n)，问旅行者应如何选择携带各种物品的数量，使总价值最大？ 设xi 为第i 种物品的携带数量，则背包问题可归结为如下形式的整数规划模型： 下面用动态规划的逆序解法求解背包问题： 阶段k：将问题划分为n 个阶段，每阶段装入一种物品， k=1，2，n。 状态变量sk

38、：第k 阶段开始时背包中可装入的第k 种到第n 种物品的重量。 决策变量xk：第k 种物品的携带数量。 状态转移方程：sk+1skakxk 指标函数：vk(sk，xk)装入的第k种物品的总价值。即 ： 最优值函数fk(sk)：当背包中可装入的第k 种到第n 种物品的重量为sk 时，采用最优策略所装入的第k 种到第n 种物品的最大总价值。 则动态规划基本方程为： 用动态规划逆序解法逐步计算出最优值及相应的决策函数： 【例6-9】有一辆最大载重量为10吨的卡车，用以装载3种货物，每种货物的单位重量及相应的单位价值如表6-14所示。应如何装载可使总价值最大？ 654单位价值(ci)543单位重量(吨

39、)321货物编号解：设第i种物品的携带数量为xi。则问题模型为： 按上述方法建立动态规划模型，由于决策变量为离散值，故可用列表法求解。 当k=3时： 状态变量s3的可能取值范围为0到10的整数，允许决策集为满足05x3s3的整数。 由基本方程 可计算得如下结果： 00000 x3*(s3)00000f3(s3)210101010101000000 x3(s3)109876543210s 3当k=2时： 状态变量s2的可能取值范围为0到10的整数，允许决策集为满足04x2s2的整数。 由基本方程 可得如下结果： 01 2000 10000 x2*(s2)1211 10666 50000f2(s2

40、)101112101161056565656500000c2f 321021021010101010 0000 x2109876543210s206060606061206111112当k=1时： 状态变量s110，允许决策集为满足03x110的整数，即x10，1，2，3。 由基本方程 可计算得如下结果： 2x1*(s1) 13f1(s1)1208546012c1f 23210 x1因此，f1(10)13，x1*2。再用逆向追踪法求得最优策略为： 即最优策略是装载第一种货物2件，第二种货物1件，不装第三种货物，可装入的3种物品的最大价值为13。 第六节 其他动态规划问题 设： 设备更新问题的一

41、般提法是：在已知一台设备的收益函数r(t)，维修费用函数u(t)及更新费用函数c(t)的条件下，要求在n年内的每年年初做出决策，是继续使用旧设备还是更新设备，使n年总收益最大。 rk(t)：在第k年设备已使用过t 年(或称役龄为t 年)，再使用1年时的收益。 uk(t)：在第k 年设备役龄为t 年，再使用一年的维修费用。 ck(t)：在第k 年卖掉一台役龄为t 年的设备，买进一台新设备的更新净费用。 为折扣因子(01)，表示一年以后的单位收入价值相当于现年的单位。 用动态规划方法求解如下： 阶段k：将问题划分为n 个阶段，每年为一个阶段， k=1，2，n。 状态变量sk：第k年初，设备已使用过的年数，即役龄。 决策变量xk：第k年初更新设备还是继续使用旧设备，分别用R或K表示。 状态转移方程： 阶段指标函数： 最优值函数fk(sk)：第k年初设备役龄为sk 年时，采用最优策略到第n 年末的最大收益。 则动态规划基本方程为： 实际上 【例6-10】某台新设备的年效益及年均维修费、更新净费用如表