动态规划的解析法.doc

一维动态规划的求解法所谓一维动态规划问题是指：在一个多阶段决策过程中，每一个阶段只用一个状态变量sk就足以描述系统的状态演变，并且在每一个阶段，只需要选择一个决策变量xk就够了。前面讨论的问题都属于这一类。若每个阶段需要两个或多个状态变量才能描述系统的演变，或者每个阶段需要选择两个或多个决策变量时，这类问题都属于多维动态规划问题。求解一维动态规划问题，基本上有两类方法：一类是解析法；一类是数值法。所谓解析法是需要用到指标函数的数学公式表示式，并且能用经典求极值的方法得到最优解，即用解析的方法求得最优解。下面主要介绍解析法动态规划的解析法我们讨论仅有一个约束条件的数学规划问题 这里，当,j=1,2,n均为线性函数时，则为线性规划问题；当不全为线性函数时，则为线性规划问题；当xj有整数要求时，则为整数规划问题。虽然这一类问题可在线性规划、非线性规划及整数规划中讨论它。但是，用动态规划方法来解决这一类问题是有其特殊的优点和方便之处。用动态规划求解这一类问题，有一个统一的模式。即把问题划分为n个阶段，取xk为第k阶段的决策变量。第k阶段的效益为（k=1,2,n）。指标函数为各阶段效益之和，即 问题是如何选择状态变量sk。正如线性规划问题中可以将约束条件看成资源限制一样，这里也可以这样理解，即将现有数量为b个单位的某种资源用来生产n种产品，问如何分配使总利润最大。假设工厂的决策者份几个阶段来考虑这个问题，如果是用逆序递推法，决策者首先考虑的是第n 种产品生产几件，消耗资源多少；然后考虑第n-1种和第n种产品各生产多少，消耗资源多少；依次向前递推。在第k阶段时，就要考虑第k种、第k-1种、，第n种产品各生产多少，消耗资源多少。于是我们就可以这样来选择状态变量了，即令sk表示可供第k种产品至第n种产品消耗的资源数。显然由sk0,且sk满足无后效性。而第k阶段的资源消耗为akxk，于是得状态转移方程为再由sk+10及决策变量xk的非负性，可得允许决策集合为允许状态集合为且S1=b.设最优函数表示从第k阶段到第n阶段指标函数的最优值，则逆序递推方程为边界条件为。然后再依次逆序递推求解。下面看几个数学计算的例子。例1 用动态规划方法求解线性规划问题；解 利用上面的分析和有关符号，我们直接计算如下：当k=3时，有注意，这里=0为边界条件。再由函数6x3的单调性可知，它必在x3 = s3/5处取得极大值，故得。这时s3究竟等于多少还不知道，要等递推完成后，再用回代的方法确定。当k=2时，有再用状态转移方程s3=s2-4x2来替换上式中的s3，得 当k=1时，有 由于s110及关于s1是单调增函数，故应取s1=10。这时 这就是指标函数的最优值。再回代求最优决策：由于s1=10,所以即线性规划问题的最优解为最优值Z*=40/3.例2 用动态规划方法求解；解 这个问题可以理解为将一个数6（或某种资源数）分成三部分，使目标函数 达到最大。取阶段变量k=1,2,3共分三个阶段。决策变量xk表示第k阶段分配的数量，状态变量sk表示从第k阶段至第3阶段可供分配的总数量，则状态转移方程为允许决策集合，允许状态集合。递推方程为 当k=3时，有 当k=2时，有 令，则再由得x2=s2或，又由直接验证可知，故为的极大值点。这时当k=1时，有令，则再令得又由直接验证可知，故。为的极大值点。这时但s1=6，故又 所以最优解为 。目标函数的最优值为Z*=108。例3 用动态规划方法求解；解 用顺序递推法求解。设阶段变量k=1,2,3共分3个阶段，决策变量为xk(k=1,2,3).状态变量sk表示从第1阶段到第k阶段可供分配的数，则状态转移方程为并取s0=0，相当于将一个不大于20的量作三阶段进行分配。其中a1,a2,a3 分别为约束条件中x1,x2,x3的系数。最优值函数表示从第1阶段到第k阶段指标函数的最优值。则当k=1时，有当k=2时，有令，则。由得。但由于，所以为最小值点。故极大值点必在区间0，s2的端点，计算两端点的函数值并比较其大小可知极大值点为x2=s2。这时；当k=3时，有 但s320，所以取s3=20，得由直接验证可知，在x3=0为极大值点。故又，即最优解为目标函数最优值为1600。例4 设某厂生产A、B两种产品，由于该厂仓库及其他设备条件的限制，对两种产品的不同日产量x1及x2（以千件为单位），日生产成本分别为设两种产品的销售价分别为10千元/千件及15千元/千件。工时消耗定额为1小时/千件。若在每天总生产时间不超过 8小时的条件下，问两种产品各生产多少件，才能使总利润最大？解 设 为两种产品的利润函数，则有；设两种产品的日生产时间分别为y1,y2，则有又因日产量 x1=y1,x2=y2,于是问题的数学模型为这时变量x1，x2虽为产品A，B的生产件数，但我们对它不加整数限制，仍作为连续变量看待。上面的问题是一个非线性规划问题。现在我们用动态规划方法来解。取k=1,2共分两个阶段，决策变量xk表示第k种产品的产量，状态变量sk表示从第k阶段至第2阶段可供消耗的总工时。状态方程sk+1 = sk - xk，允许决策集合为 。允许状态集合为。边界条件下面进行递推求解：当k=2时，有令，则由得。又因为，故为极大值点。但是这时s2究竟等于多少还不知道，只知道0s28，因此。为了求出，还必须作如下分析。我们已经求出 x2=11/4为的极大值点。即当时，单调上升；当时，单调下降（如图6-4所示）。图6-4于是得从而，有当k=1时，有S1=8。所以 令 则 直接验证可知，当时，当，因此当时，达到极大值。这时，最优解为目标函数最优值。由0s39, 且关于s3是单调增函数