运筹学动态规划

第7章 动态规划动态规划是Bellman在1957年提出的解多阶决策问题的方法，在那个时期，线性规划很流行，它是研究静态问题的，而Bellman提出的解多阶决策问题的方法适用于动态问题，相对于线性规划研究静态问题，取名动态规划。动态规划方法应用范围非常广泛，方法也比较简单。动态规划是将一个多阶决策问题分解为一系列的互相嵌套的一步决策问题，序贯求解使问题得到简化。 动态规划问题按照问题的性质可以分为确定性的和随机性的，按决策变量的和状态变量的取值可以分为离散型的和连续型的。此外还有依据时间变量连续取值还是离散取值又分为连续时间动态规划问题和离散时间动态规划问题。本章重点讨论离散时间确定性动态规划问题，包括状态变量和决策变量连续取值和离散取值两种情况。7.1解多阶决策问题的动态规划法1.多阶决策问题的例(1)最优路径问题多阶决策问题的例为了直观，先从最优路径问题谈起，它可以看作一个多阶决策过程。通过最优路径问题的解可以看到用动态规划法解多阶决策问题的基本思想。图7-1最优路径问题 考虑图7-1所示的最优路径问题。一汽车由点出发到终点，和是一些可以通过的点。图中两点间标出的数字是汽车走这一段路所需的时间(单位为小时)。最优路径问题是确定一个路径，使汽车沿这条路径由点出发达到点所用时间最短。最优路径问题可以看作一个多阶决策问题，由到城市甲是第1个阶段，第1个结点或第2个结点做为第1阶段可以通过的两个站点，由城市甲到城市乙是第2阶段，这个阶段是从或到或，由城市乙到城市丙是第3阶段，这个阶段是从或到或，由城市丙的或到做为第四阶段。（2）最优路径问题的解对最优路径问题，存在一个非常明显的原理，即最优路径的一部分还是最优路径。换句话说，如果是所求的最优路径，那么，汽车从这一路径上的任何一点，例如，出发到的最优路径必为。这一原理称为最优性原理。根据这一原理可以由后向前递推求出最优路径。如果汽车已到，由直接到用3小时，如果汽车已到，由直接到用4小时，这两个数字分别标在图7-2中和旁的方括号内。再向前推一步，设汽车已在，经需2+4=6小时，经需2+3=5小时。这样从出发经到所需时间最短，需5小时。将5记在旁的括号内，经到达，将标在括号的下角。类似的可计算出汽车分别从，出发达到所需的最短时间及路径，见图7-2。图7-2最优路径问题的解解由图7-2可以看出，汽车从出发达到的最优路径是，需时13小时。不仅如此，由图7-2还可以看到汽车从任何一点出发到达点最短路径，及与它相应的最短时间。按构造图7-2的方法共需10次加法。如将所有的路径一一列出则需24次加法。上面的求最优路径的方法，是把一个四阶段的最优决策问题，化成四个互相嵌套的子问题逐一求解，从而使问题得到简化，这种方法称为动态规划法。为了说明动态规划方法的优点，我们将应用决策树法的情况画到图9.3中，可以看到用决策树法运算量比用动态规划法大得多。由图9.3可以看出决策树法是算出所有可能的路径所需的时间，最后从中选出最优路径，动态规划法则是从后面向前递推。每阶段计算过的结果不在重复计算，从而减少了计算量。41511431616424153614412131451832471732第二阶段第四阶段第三阶段第一阶段图 最短线路问题中的决策树2.应用动态规划解多阶决策问题的基本特征动态规划是解多阶决策问题的一种方法。它可以求解的问题有如下特征：决策问题可以分成若干个阶段，每个阶段有若干与该阶段有关的状态和需要做的决策，系统从一个阶段的状态按一定的规律转移到下一个阶段的状态，多阶决策问题是求一个由每个阶段的决策构成的最优策略使得按决策目标最好。应用动态规划解多阶决策问题有如下基本特征：（1）问题可以依时间顺序或空间的自然特征划分为几个阶段，每个阶段有一个决策变量需要作出决策。用表示阶段数，用表示第阶段的决策变量。（2）动态规划中本阶段状态往往是上一阶段的状态和上一阶段的决策进行综合的结果每个阶段作出决策后，使得当前的状态转移到下一阶段的状态 函数决定了这一转移过程，称它为转移函数。这个方程称为状态转移方程简称状态方程。状态方程是研究对象的内在规律的数学描述，也称为研究对象的数学模型。 （3）每个阶段的决策变量的集合构成多阶决策问题的一个策略按照决策的目标，引进一个用于衡量所选定策略优劣的数量指标称为指标函数一些决策过程的指标函数越大越好（例如指标函数是利润、产值等），另一些决策过程的指标函数越小越好（例如指标函数是成本、误差等）。使得指标函数最大（或最小）的策略称为最优策略。最优策略常记为 （4）以表示第阶段的指标函数，则阶决策过程的指标函数为 3.多阶段决策问题的一般提法设多阶决策问题状态方程为 （7-1）指标函数为 （7-2）其中为决策变量。多阶段决策问题是求一个策略:，使得指标函数最大(或最小)。使得指标函数最大(或最小)的策略称为最优策略，常记为为了讨论简单，假设函数和都不依赖于时间变量，设状态方程为 （7-3）指标函数为 （7-4）我们遇到的多数问题属于这种情况。假设系统的初始状态给定为，在指标函数中逐次应用状态方程，可得到N步决策的指标函数的值为经逐次代入可得到如果已经求出了使最大（或最小）的最优策略，那么，将它们代入上式，就得到控制步的指标函数的最大值(或最小值)。由于已确定，只依赖于，记为，即一般地，初始条件为时，步决策的指标函数为如果已经求出了使最大（或最小）的最优策略，那么，将它们代入上式，就得到控制步的指标函数的最大值(或最小值)。由于已确定，只依赖于，记为，即简记为是第阶段状态为指标函数的最优值，称为最优值函数。4.动态规划的基本方程Bellman方程(1)最优性原理在最短路径问题中讲的最优性原理，对于一般多阶段决策问题也成立。多阶段决策问题的最优性原理，可用一句话概括：最优策略序列的一部分也构成一个最优策略序列。更具体的可叙述为如下的定理。最优性原理：如果是最优策略序列，那么它的一部分也是一个最优策略序列，其初始状态为。(2)动态规划的基本方程下面导出动态规划的基本方程，它给出阶决策问题的指标函数最优值与它的子问题(一个阶决策问题)的指标函数最优值之间的递推关系式。这个基本方程是用动态规划解一切多阶段决策问题的基础。假设已求出，那么的问题构成一个初始条件为的阶决策问题。这一问题的指标函数最小值记作，则有方程 称为动态规划的基本方程，它给出了与之间的递推关系。类似于上面的推导，可以得到动态规划基本方程的如下一般形式： （7-5） 动态规划的基本方程，也称递推方程或Bellman方程，它给出了与之间的递推关系。通过它可以把一个多阶决策问题化为若干个子问题，而在决策的每一阶段，只需对一个变量进行最优化。5.动态规划的逆向递归求解法应用Bellman方程（7-5），可以对以上多阶决策问题从最后一步开始递推求解。这一方法称为逆向递归求解法。该方法首先考虑一步最优化问题：对变量求最小，这是一个静态最优化问题，解这个问题得到，代入上式可以求出。求出后，由Bellman方程 (7-6）式中。在此约束条件下对花括号中的函数关于求最小，由于已经求出，这又是一个静态最优化问题，解这个问题得到。这是通过解一阶必要条件 （7-7）求出的。由这个一阶条件求出后，将它代回式（7-6）得到。然后就可以进行下一次递推。一阶必要条件（7-7）的一般形式是 （7-8）这样逐次应用基本方程，就可以由后向前逐次求出所有的决策变量。这一求解过程是把原来的阶决策问题化成了一系列对单变量求最小的问题，从而使问题的求解得到了简化。最优性原理保证这种分步最优化的过程得到的结果与同时确定所有决策变量的结果相同。以上是终端状态为自由的情况，如果终端状态是给定的，即已给，则由状态方程有于是由方程可以直接解出唯一的，它就是(因为没有其他选择)。进而可以计算，由Bellman方程 再求，然后再继续递归。只到求出最优策略。以上推导假设了x和u都是标量，当x和u都是向量时以上结果仍然成立。【例7-1】将前面讨论的最优途径问题看作一个四阶段决策问题，可以看出前面的解法实质上是在逐次利用动态规划基本方程求解。从最后一个阶段开始，如果汽车已经在城市丙的站点，则到达终点的最短时间为，如果汽车已经在城市丙的站点，则到达终点的最短时间为。向前递推一步，考虑3，4两个阶段，即城市乙和丙联合考虑，利用动态规划基本方程，如果汽车已经在城市乙的站点，则到达终点的最短时间（选）如果汽车已经在城市乙的站点，则到达终点的最短时间（选）再递推一步，将城市甲、乙和丙联合考虑，如果汽车已经在城市甲的站点，则到达终点的最短时间（选）如果汽车已经在城市甲的站点，则到达终点的最短时间（选）最后，始点到达终点的最短时间（选）于是得到最优途径是。【例7-2】资源分配问题设某公司为了扩大生产能力拟购设备4-6套分配给3个分厂，各分厂得到设备后预期的利润见下表：预期利润表分厂0套1套2套3套4套5套6套1035676520467891030259887按1、2、3的顺序进行分配，以表示给厂分配时可分配的套数，分配给厂的套数是由上表给出的厂得到套设备所创的利润，状态转移方程为指标函数为问题是选取策略使满足并使最大。记 由后向前递推：第1步：，由利润表的最后一行得到下表123456123333259999第2步：，由利润表的第2行及递推公式得到下表0123456012345600+20+50+9=90+9=90+9=90+9=94+0=44+2=64+5=94+9=134+9=134+9=136+0=66+2=86+5=116+9=156+9=157+0=77+2=97+5=127+9=168+0=88+2=108+5=139+0=99+2=1110+0=100469131516011,20,1123第2步：，由利润表的第1行及递推公式得到下表，由于公司仅购买4-6套设备，所以01234564560+130+150+163+9=123+13=163+15=185+6=115+9=145+13=186+4=106+6=126+9=157+0=77+4=117+6=136+0=116+4=105121618111,2最后顺序递推得到最优策略：由上表，当时，3步决策的指标函数值最大为18，这时=1或2，于是这时对于，因此3；对于，因此3于是3，由第1步的表，。最优策略的两种可能：，最大利润18。，最大利润18。最优策略为1,2,3或2,1,3，两种策略均可获最大利润18。【例7-3】吃糕问题 吃糕问题是资源管理中很多问题的的基础，经济管理的教材都以它为例。吃糕只是形象的说法。已知有一块蛋糕其大小为（代表某种资源的初始存量），计划分天吃完（开采完），以记第天开始时剩余的蛋糕的大小（资源的存量），以记第天吃的蛋糕的量（开采量），则吃糕问题（资源开采问题）的状态方程为为了具体我们设，考虑问题解 由得到，即，于是 应用Bellman方程，有下面需要对花括号内的函数关于求导数，并令它等于零，解出，这一工作可以由MATLAB的符号微分运算和解方程来完成，程序如下： syms beta c1 w1eq=diff(beta*log(c1)+(beta)2*log(w1-c1),c1)eq =beta/c1-beta2/(w1-c1) c1=solve(eq,c1)c1 =w1/(1+beta)得到 于是 应用bellman方程再递推一步 其中，以上式代入花括号内，再对花括号内的函数关于求导数，并令它等于零，解出，这一工作仍然由MATLAB的符号微分运算和解方程来完成： syms beta c0 w0 bb=1+beta;eq=diff(log(c0)+beta*log(w0-c0)/b)+(beta)2*log(beta*(w0-c0)/b),c0)eq =1/c0-beta/(w0-c0)-beta2/(w0-c0) c0=solve(eq,c0)c0 =w0/(1+beta+beta2)得到 在解离散的多阶决策问题时，要考虑今天采取的行动会对未来产生影响。用动态规划的Bellman方程求解跨期最优化问题时，例如在决定当前的收入水平下今天的消费时，不仅要考虑今天的消费，还要考虑未来的消费。当决定今天消费多少时，必须考虑这一决策将影响明天的消费。在应用动态规划的Bellman方程多阶决策问题时，总是将决策分为两个时期，当前和未来。假设未来的行为已经最优化了，当前应该如何决策。本例中第一个必要条件可改写为左边是消费的边际效用的贴现值，即在这个周期每增加1个单位蛋糕的消费增加的效用的贴现值。右边是在未来增加1个单位蛋糕的消费增加的边际效用的贴现值，即在这个周期增加1个单位蛋糕的消费增加的效用的贴现值。这恰是这个周期每增加1个单位蛋糕的消费的机会成本。因此上面的必要条件的经济意义是：在这个周期每增加1个单位蛋糕的消费增加的效用的贴现值等于这个周期每增加1个单位蛋糕的消费的机会成本。通过例7-1，演示了如何借助于MATLAB的符号运算，通过Bellman方程解动态规划问题。但是多数动态规划问题不能像例12-1那样可以求出解析解。通过例7-1的求解过程我们再概括一下动态规划解多阶决策问题的思路：（1）将多阶段决策过程划分阶段，恰当地选择状态变量、决策变量以定义最优指标函数，从而把问题化成一族同类型的子问题，然后逐个求解。 （2）求解时从边界条件开始，逆序过程行进，逐段递推寻优在每一个子问题求解时，都要使用它前面已求出的子问题的最优结果最后一个子问题的最优解，就是整个问题的最优解。 （3)动态规划方法不是将每个阶段孤立地分开，而是既将当前一段与未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法，因此每段的最优决策选取是从全局考虑的，与仅考虑该阶段的最优选择一般是不同的。【例7-4】生产-库存-销售系统控制问题设某厂计划全部生产某种产品，四个季度的定货量分别为600件，700件，500件和1200件。已知该产品的生产费用与生产数量的平方成正比，比例系数为0.005。厂内有仓库可存放未销售掉的产品，其存储费用为每件每季度1元。设第季度该产品的生产数量为，第季度初的库存量为，第季度的销售量(这里假设完全按定货量销售)为。那么这三个变量之间的关系为：下季度初的库存量等于本季度的库存量加本季度的生产量减去本季度的销售量。因此该系统的状态方程为如果年初没有存货，则，如果要求年底将货销完，则有。该控制问题的目标是使总费用(包括生产费用和存储费用)最小。指标函数为生产库存系统的最优管理问题是求，使最小。下面用动态规划的基本方程求这一管理问题的最优策略。先由最后一个季度考虑起：由状态方程和条件得到由此得到代入得到第二步考虑第三、四两个季度。由动态规划的基本方程： 其中，代入上式得到对中的函数关于求最小，有解得为了保证，必须小于1600。将代入得到第三步考虑24三个季度，由基本方程其中，代入上式得到由解得代入得到最后对四个季度一起考虑，由基本方程有以代入上式得令得到即代入得到由于已设，得，。采用上策略时，总费用为元如果采用销多少生产多少的策略，则总费用为最优策略节省费用900元，约合。5.指标函数有贴现因子时的Bellman方程设系统的状态方程为指标函数为是贴现因子。Bellman方程为式中因此和都是贴现到时的值。上方程的两边同乘以得到式中记得到它是指标函数有贴现因子时的Bellman方程，为当期的指标函数的最优值，没有贴现到初始时刻。为了简化，以后仍把记为。将指标函数有贴现因子时的Bellman方程仍记为 （7-9）【例7-5】设某大学生的家长计划在四年内给该生M元，作为大学四年的花费。设效用函数为，贴现因子为，则效用最大化问题的状态方程是是该生第年开始时剩的钱，是该生第年的消费，指标函数是效用最大化问题是求消费策略使最大。这个问题可简记为由于效用函数是增函数，最后一年的最优消费策略必是于是初始条件为时指标函数的最大值为由指标函数有贴现因子时的Bellman方程，递推一步有其中,以代入上式得到下面需要对花括号内的函数关于求导数，并令它等于零，解出，这一工作可以由MATLAB的符号微分运算和解方程完成：(文件Li12_2_1)syms beta s2 c2eq=diff(sqrt(c2)-beta*sqrt(s2-c2),c2)c2=solve(eq,c2)运行这个文件得到： Li12_2_1eq =1/2/c2(1/2)+1/2*beta/(s2-c2)(1/2)c2 =s2/(1+beta2)即得到将代回得到应用指标函数有贴现因子时的Bellman方程再递推一步下面需要对花括号内的函数关于求导数，并令它等于零，解出，这一工作可以由MATLAB的符号微分运算和解方程完成：(文件Li12_2_2)syms beta s1 c1eq=diff(sqrt(c1)+beta*sqrt(1+beta2)*(s1-c1),c1)c1=solve(eq,c1)运行这个文件得到： Li12_2_2eq =1/2/c1(1/2)+1/2*beta/(1+beta2)*(s1-c1)(1/2)*(-1-beta2)c1 =s1/(beta4+beta2+1)即得到 将代回得到再递推一步有下面需要对花括号内的函数关于求导数，并令它等于零，解出，这一工作可以由MATLAB的符号微分运算和解方程完成：(文件Li12_2_3)syms beta s0 c0eq=diff(sqrt(c0)+beta*sqrt(1+beta2+beta4)*(s0-c0),c0)c0=solve(eq,c0)运行这个文件得到： Li12_2_3eq =1/2/c0(1/2)+1/2*beta/(beta4+beta2+1)*(s0-c0)(1/2)*(-beta4-beta2-1)c0 =s0/(beta6+beta4+beta2+1)即得到 贴现因子取值于0，1之间，当时，7.2随机动态规划1.随机动态规划的提法以上给出的动态规划算法都是确定型的，没有考虑有随机干扰的情况，本节给出有随机干扰的动态系统的跨期最优化问题的动态规划算法。设动态系统的状态方程为 （7-12）式中对动态系统的随机干扰这里用是因为在时刻它是未知的，假设它的概率分布不依赖于。指标函数为 （7-13）由于花括号中的函数是一个随机变量，因此指标函数表示为花括号中函数的期望值，是期望算子。2. 随机动态规划的Bellman方程对于这个随机跨期最优化问题，动态规划的Bellman方程应改为 （7-14）象前面一样，引进值函数Bellman方程又可以改写为或者简记为 问题的一阶条件是对于随机动态规划问题，方程（7-10）和（7-11）化为 （7-15） （7-16）这两个条件常称为Euler均衡条件。 最常见的一类随机跨期最优化问题是线性二次型高斯问题，这类问题的状态方程是线性差分方程组，指标函数是状态变量和决策变量的二次型，随机干扰是高斯白噪声。 ss,pi,xx=dpstst(model,h,nbin,s,x);这里用到的程序：qnwlogn ，fundefn ，funnode，lqapprox ，dpsolve ，dpsimul和dpsts都可以在参考文献18的作者网站的CompEcon Toolbox中找到。7.3 MATLAB在动态规划中的应用动态规划问题形式多种多样，MATLAB没有统一的解动态规划问题的函数，但对于自由始端和终端的动态规划,求指标函数最小值的逆序算法递归，有人写了函数dynprog,可以应用dyprog求解。（参见：宋来忠，王志明：数学建模与实验 科学出版社2005 p.182或周品、赵新芬：MATLAB数学建模与仿真 国防工业出版社 2009 p.340）函数dynprog的调用形式是：p_opt,fval=dynprog(x,DecisFun,ObjFun,TransFun) 输入 x是状态变量的矩阵，它的第k列是k阶段状态变量的可能取值，其他输入由3个函数给出：DecisFun(k,x)是由阶段k的状态变量，求出相应的允许决策变量的函数。函数ObjFun(k,x,u)用于由阶段k的状态变量x和阶段k的决策变量u计算阶段k指标函数。函数TransFun(k,x,u) 是状态转移函数,其中x是阶段k的状态变量，u是相应的决策变量。应用函数dyprog之前，需要写3个函数: DecisFun,ObjFun,TransFun分别给出状态变量x求出相应的允许决策变量、阶段指标函数和转移函数。 输出p_opt由4列构成，第1列是序号组，第2列是最优轨线，第3列是最优策略，第4列是阶段指标函数值；输出fval是一个列向量，它给出p_opt各最优策略组对应的最优值。下面通过实例说明如何应用函数dynpro求解动态规划问题。1.生产计划问题1 （参看宋来忠，王志明：数学建模与实验 科学出版社2005 p.179或周品、赵新芬：mATLAB数学建模与仿真 国防工业出版社 2009 p.343）设某工厂与用户订立合同，在4个月内出售一定数量的某产品，产量限制为10的倍数，工厂每月至多生产100件，产品可以存储，存储费用每件2元，最多可以存储130件，每个月的需求量及每件产品的 生产成本如表7-1月份 每件生产成本（元） 需要量（件）月份 每件生产成本（元） 需要量（件）1 70 602 72 70 3 80 120 4 76 60在一月初的存储量未知的情况下，确定每月的产量，要求既能满足每月的合同需求量，第4个月不剩产品，又使生产成本和存储费用的和最小。设是第月初的库存量，是第月的生产量，是第月的合同需求量，指标函数：总费用最小，即 为使用函数dynprog需要定义3个函数：eg13f1_2.m function u=DecisF_1(k,x) %在阶段k由状态变量x的值求出其相应的决策变量所有的取值 c=70,72,80,76;q=10*6,7,12,6; if q(k)-x x=nan*ones(14,4)x = NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN由于第1个月的需求量是60，第1个月的存储量考虑0、10、20、30、40、50、60几种情况： x(1:7,1)=10*(0:6)x = 0 NaN NaN NaN 10 NaN NaN NaN 20 NaN NaN NaN 30 NaN NaN NaN 40 NaN NaN NaN 50 NaN NaN NaN 60 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN当时，第1个月最多生产100件，第1个月需求是60，因此： x(1:11,2)=10*(0:10)x = 0 0 NaN NaN 10 10 NaN NaN 20 20 NaN NaN 30 30 NaN NaN 40 40 NaN NaN 50 50 NaN NaN 60 60 NaN NaN NaN 70 NaN NaN NaN 80 NaN NaN NaN 90 NaN NaN NaN 100 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN第2个月存储量最大100，生产最大100，第2个月需求量是70，因此，但是由于第4个月需求是120，而第4个月的产量最大100因此： x(1:12,3)=10*(2:13)x = 0 0 20 NaN 10 10 30 NaN 20 20 40 NaN 30 30 50 NaN 40 40 60 NaN 50 50 70 NaN 60 60 80 NaN NaN 70 90 NaN NaN 80 100 NaN NaN 90 110 NaN NaN 100 120 NaN NaN NaN 130 NaN NaN NaN NaN NaN NaN NaN NaN NaN第4个月不剩产品，第4个月的需求量是60，因此： x(1:7,4)=10*(0:6)x = 0 0 20 0 10 10 30 10 20 20 40 20 30 30 50 30 40 40 60 40 50 50 70 50 60 60 80 60 NaN 70 90 NaN NaN 80 100 NaN NaN 90 110 NaN NaN 100 120 NaN NaN NaN 130 NaN NaN NaN NaN NaN NaN NaN NaN NaN有了以上准备，就可以调用函数dynprog,解这个问题了，程序及运行结果如下： clear;x=nan*ones(14,4);% x是10的倍数，最大范围0x130, %因此x=0,1,.13，所以x初始化取14行，nan表示无意义元素 x(1:7,1)=10*(0:6); % 按月定义x的可能取值 x(1:11,2)=10*(0:10);x(1:12,3)=10*(2:13); x(1:7,4)=10*(0:6); p,f=dynprog(x,eg13f1_2,eg13f2_2,eg13f3_2)p = 1 0 100 7000 2 40 100 7280 3 70 50 4140 4 0 60 4560 1 10 100 7020 2 50 100 7300 3 80 40 3360 4 0 60 4560 1 20 100 7040 2 60 100 7320 3 90 30 2580 4 0 60 4560 1 30 100 7060 2 70 100 7340 3 100 20 1800 4 0 60 4560 1 40 100 7080 2 80 100 7360 3 110 10 1020 4 0 60 4560 1 50 100 7100 2 90 100 7380 3 120 0 240 4 0 60 4560 1 60 100 7120 2 100 100 7400 3 130 0 260 4 10 50 3820f = 22980 22240 21500 20760 20020 19280 18600以上结果中，p给出第1个月存储量为0,10,20,30,40,50,60时的最优策略以及相应的存储量和本月的费用的和：p = 月 1 0 100 7000 2 40 100 7280 3 70 50 4140 4 0 60 4560 1 10 100 7020 2 50 100 7300 3 80 40 3360 4 0 60 4560 1 20 100 7040 2 60 100 7320 3 90 30 2580 4 0 60 4560 1 30 100 7060 2 70 100 7340 3 100 20 1800 4 0 60 4560 1 40 100 7080 2 80 100 7360 3 110 10 1020 4 0 60 4560 1 50 100 7100 2 90 100 7380 3 120 0 240 4 0 60 4560 1 60 100 7120 2 100 100 7400 3 130 0 260 4 10 50 3820F给出，相应于第1个月存储量为0,10,20,30,40,50,60时的指标函数的最小值f = 22980（时） 22240（时） 21500（时） 20760（时） 20020（时） 19280（时） 18600（时）这样对于第1个月的初始存储量的6种情况都求出了最优解。生产计划问题2 （参看马莉：MATLAB数学实验与建模 清华大学出版社2010 p.258）工厂生产莫产品，每千件的成本为1千元每次开工的固定成本为3千元，每季度的最大生产能力为6千件。经调查该产品1-4季度的需求量分别为2、3、2、4千件存储费用每季度每千件0.5（千元）制定生产计划，使满足需求，年初、年终均无库存，并使一年的总费用最小。设是第季度初的库存量，是第季度的生产量，是第季度的需求量，指标函数：总费用最小，即 按题意 egF2_1p = 1.0000 0 5.0000 7.0000 2.0000 3.0000 0 1.5000 3.0000 0 6.0000 9.0000 4.0000 4.0000 0 2.0000f = 20.5000 NaN NaN NaN NaN2.资源最优配置问题 公司有新设备6台分配给所属甲乙丙丁四个企业，四个企业获得新设备后可获利的情况如下表： 设备企业 0 1 2 3 4 5 6 1 0 4 6 7 7 7 7 2 0 2 4 6 8 9 103 0 3 5 7 8 8 84 0 4 5 6 6 6 6求最优分配方案，使可以获得最大利润。（见马莉：MATLAB数学实验与建模 清华大学出版社 2010 p.259）设是分配到企业时可用于分配的设备数， 是分配给企业的设备数，状态方程为为分配台设备给企业获得的利润指标函数应用函数dynprog解这个问题，先构造3个函数：DecisF20_1:function u=DecisF20_1(k,x)if k=4 u=x;else u=0:x;endObjF20_1function v=ObjF20_1(k,x,u)w=0 0 0 0;4 2 3 4;6 4 5 5;7 6 7 6;7 8 8 6;7 9 8 6;7 10 8 6;w=-w;v=(0 1 2 3 4 5 6=u)*w(:,k);TransF20_1function y=TransF20_1(k,x,u)y=x-u;有了这3个函数，就可以利用函数dynprog解这的问题了。 clear all;x=0;1;2;3;4;5;6;x=x,x,x,x;p,f=dynprog(x,DecisF20_1,ObjF20_1,TransF20_1)p = 1 0 0 0 2 0 0 0 3 0 0 0 4 0 0 0 1 1 1 -4 2 0 0 0 3 0 0 0 4 0 0 0 1 2 1 -4 2 1 0 0 3 1 0 0 4 1 1 -4 1 3 1 -4 2 2 0 0 3 2 1 -3 4 1 1 -4 1 4 2 -6 2 2 0 0 3 2 1 -3 4 1 1 -4 1 5 2 -6 2 3 1 -2 3 2 1 -3 4 1 1 -4 1 6 2 -6 2 4 2 -4 3 2 1 -3 4 1 1 -4f = 0 -4 -8 -11 -13 -15 -17计算结果分析： 企 业 p = 1 0 0 0 2 0 0 0 3 0 0 0 4 0 0 0 1 1 1 -4 2 0 0 0 3 0 0 0 4 0 0 0 1 2 1 -4 2 1 0 0 3 1 0 0 4 1 1 -4 1 3 1 -4 2 2 0 0 3 2 1 -3 4 1 1 -4 1