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