发布时间 : 星期六 文章4第四章 动态规划更新完毕开始阅读67ec16bcf021dd36a32d7375a417866fb84ac09d
(j)(j)fk(j)(xki)?vk(xki,uki)?fk?1(Tk(xki,uki)),fk(xki)?optfk(j)(xki),j （4）
j?1,2,?,nki,i?1,2,?,nk,k?n,?,2,1.*按照（3），（4）逆向计算出f1(x1)，为全过程的最优值。记状态xki的最优决策为****和uki。并得到相应的uki(xki)，由x1(xki)按照状态转移方程计算出最优状态，记作xk********最优决策，记作uk(xk)。于是最优策略为{u1(x1),u2(x2),?,un(xn)}。
算法程序的框图如下。
*图的左边部分是函数序列的递推计算，可输出全过程最优值f1(x1)，如果需要还
*可以输出后部子过程最优值函数序列fk(xki)和最优决策序列uk(xki)。计算过程中存*fk(xki)是备计算fk?1之用，在fk?1算完后可用fk?1将fk替换掉；存uk(xki)是备右边
部分读uk(xk)之用。
图的右边部分是最优状态和最优决策序列的正向计算，可输出最优策略
*********{u1(x1),u2(x2),?,un(xn)}和最优轨线{x1,x2,?,xn}。
** §4 动态规划与静态规划的关系
动态规划与静态规划（线性和非线性规划等）研究的对象本质上都是在若干约束条
-44-
件下的函数极值问题。两种规划在很多情况下原则上可以相互转换。
动态规划可以看作求决策u1,u2,?,un使指标函数V1n(x1,u1，u2,?,un)达到最优（最大或最小）的极值问题，状态转移方程、端点条件以及允许状态集、允许决策集等是约束条件，原则上可以用非线性规划方法求解。
一些静态规划只要适当引入阶段变量、状态、决策等就可以用动态规划方法求解。下面用例子说明。
例3 用动态规划解下列非线性规划
maxn?gk?1knk(uk)；
s.t.
?uk?1?a,uk?0.
其中gk(uk)为任意的已知函数。
解 按变量uk的序号划分阶段，看作n段决策过程。设状态为x1,x2,?,xn?1，取问题中的变量u1,u2,?,un为决策。状态转移方程为
x1?a,xk?1?xk?uk,k?1,2,?,n.
取gk(uk)为阶段指标，最优值函数的基本方程为（注意到xn?1?0）
fk(xk)?max[gk(xk)?fk?1(xk?1)]；
0?uk?xk0?xk?a,k?n,n?1,?,2,1；
fn?1(0)?0.
*按照逆序解法求出对应于xk每个取值的最优决策uk(xk)，计算至f1(a)后即可利***用状态转移方程得到最优状态序列{xk}和最优决策序列{uk(xk)}。
与静态规划相比，动态规划的优越性在于：
（i）能够得到全局最优解。由于约束条件确定的约束集合往往很复杂，即使指标函数较简单，用非线性规划方法也很难求出全局最优解。而动态规划方法把全过程化为一系列结构相似的子问题，每个子问题的变量个数大大减少，约束集合也简单得多，易于得到全局最优解。特别是对于约束集合、状态转移和指标函数不能用分析形式给出的优化问题，可以对每个子过程用枚举法求解，而约束条件越多，决策的搜索范围越小，求解也越容易。对于这类问题，动态规划通常是求全局最优解的唯一方法。
（ii）可以得到一族最优解。与非线性规划只能得到全过程的一个最优解不同，动态规划得到的是全过程及所有后部子过程的各个状态的一族最优解。有些实际问题需要这样的解族，即使不需要，它们在分析最优策略和最优值对于状态的稳定性时也是很有用的。当最优策略由于某些原因不能实现时，这样的解族可以用来寻找次优策略。
（iii）能够利用经验提高求解效率。如果实际问题本身就是动态的，由于动态规划方法反映了过程逐段演变的前后联系和动态特征，在计算中可以利用实际知识和经验提高求解效率。如在策略迭代法中，实际经验能够帮助选择较好的初始策略，提高收敛速度。
动态规划的主要缺点是：
（i）没有统一的标准模型，也没有构造模型的通用方法，甚至还没有判断一个问题能否构造动态规划模型的准则。这样就只能对每类问题进行具体分析，构造具体的模
-45-
型。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力和灵活的技巧性，这就带来了应用上的局限性。 （ii）用数值方法求解时存在维数灾（curse of dimensionality）。若一维状态变量有m个取值，那么对于n维问题，状态xk就有m个值，对于每个状态值都要计算、存储函数fk(xk)，对于n稍大（即使n?3）的实际问题的计算往往是不现实的。目前还没有克服维数灾的有效的一般方法。 §5 若干典型问题的动态规划模型
5.1 最短路线问题
对于例1一类最短路线问题（shortest Path Problem），阶段按过程的演变划分，状态由各段的初始位置确定，决策为从各个状态出发的走向，即有xk?1?uk(xk)，阶段指标为相邻两段状态间的距离dk(xk,uk(xk))，指标函数为阶段指标之和，最优值函数，基本方程为 fk(xk)是由xk出发到终点的最短距离（或最小费用）
fk(xk)?min[dk(xk,uk(xk))?fk?1(xk?1)],k?n,?,1;
uk(xk)nfn?1(xn?1)?0.
利用这个模型可以算出例l的最短路线为AB1C2D1E2F2G， 相应的最短距离为18。
5.2 生产计划问题
对于例 2一类生产计划问题（Production planning problem），阶段按计划时间自然划分，状态定义为每阶段开始时的储存量xk，决策为每个阶段的产量uk，记每个阶段的需求量（已知量）为dk，则状态转移方程为
xk?1?xk?uk?dk,xk?0,k?1,2,?,n. (5)
设每阶段开工的固定成本费为a，生产单位数量产品的成本费为b，每阶段单位数量产品的储存费为c，阶段指标为阶段的生产成本和储存费之和，即
?a?buk,uk?0 (6) vk(xk,uk)?cxk???0指标函数Vkn为vk之和。最优值函数fk(xk)为从第k段的状态xk出发到过程终结的最
小费用，满足
fk(xk)?min[vk(xk,uk)?fk?1(xk?1)],k?n,?,1.
uk?Uk其中允许决策集合Uk由每阶段的最大生产能力决定。若设过程终结时允许存储量为
0xn?1，则终端条件是
0 fn?1(xn?1)?0. （7）
（5）~（7）构成该问题的动态规划模型。
5.3 资源分配问题
一种或几种资源（包括资金）分配给若干用户，或投资于几家企业，以获得最大的效益。资源分配问题（resource allocating Problem）可以是多阶段决策过程，也可以是静态规划问题，都能构造动态规划模型求解。下面举例说明。
例4 机器可以在高、低两种负荷下生产。u台机器在高负荷下的年产量是g(u)，
-46-
在低负荷下的年产量是h(u)，高、低负荷下机器的年损耗率分别是a1和b1（0?b1?a1?1）。现有m台机器，要安排一个n年的负荷分配计划，即 每年初决定多少台机器投入高、低负荷运行，使n年的总产量最大。如果进一步假设g(u)??u，，即高、低负荷下每台机器的年产量分别为?和?，结果将h(u)??u（????0）
有什么特点。
解 年度为阶段变量k?1,2,?,n。状态xk为第k年初完好的机器数，决策uk为第k年投入高负荷运行的台数。当xk或uk不是整数时，将小数部分理解为一年中正常工作时间或投入高负荷运行时间的比例。
机器在高、低负荷下的年完好率分别记为a和b，则a?1?a1，b?1?b1，有
a?b。因为第k年投入低负荷运行的机器台数为xk?uk，所以状态转移方程是
xk?1?auk?b(xk?uk) （8） 阶段指标vk是第k年的产量，有
vk(xk,uk)?g(uk)?h(xk?uk) （9） 指标函数是阶段指标之和，最优值函数fk(xk)满足
fk(xk)?max[vk(xk,uk)?fk?1(xk?1)],0?uk?xk 0?xk?m,k?n,?,2,1. (10)
及自由终端条件
fn?1(xn?1)?0,0?xn?1?m. （11） 当vk中的g,h用较简单的函数表达式给出时，对于每个k可以用解析方法求解极值问题。特别，若g(u)??u，h(u)??u，（10）中的[vk(xk,uk)?fk?1(xk)] 将是uk的线性函数，最大值点必在区间0?uk?xk的左端点uk?0或右端点uk?xk取得，即每年初将完好的机器全部投入低负荷或高负荷运行。 §6 具体的应用实例
例5 设某工厂有1000台机器，生产两种产品A、B，若投入y台机器生产A产品，则纯收入为5y，若投入y台机器生产B种产品，则纯收入为4y，又知：生产A种产品机器的年折损率为20%，生产B产品机器的年折损率为10%，问在5年内如何安排各年度的生产计划，才能使总收入最高？
解 年度为阶段变量k?1,2,3,4,5。
令xk表示第k年初完好机器数，uk表示第k年安排生产A种产品的机器数，则
xk?uk为第k年安排生产B种产品的机器数，且0?uk?xk。
则第k?1年初完好的机器数
xk?1?(1?0.2)uk?(1?0.1)(xk?uk)?0.9xk?0.1uk （12） 令vk(xk,uk)表示第k年的纯收入，fk(xk)表示第k年初往后各年的最大利润之
和。
显然
f6(x6)?0 （13）
-47-