动态规划可以看作求决策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-

则

fk(xk)?max{vk(xk,uk)?fk?1(xk?1)}

0?uk?xk?max{5uk?4(xk?uk)?fk?1(xk?1)}?max{uk?4xk?fk?1(xk?1)} （14）

0?uk?xk0?uk?xk（1）k?5时，由（13）、（14）式得

{u5?4x5} f5(x5)?max0?u5?x5知其导数大于零，所以u5?4x5在u5等于x5处取得最大值，u5?4x5关于u5求导，

即u5?x5时，f5(x5)?5x5。

（2）k?4时，由（12）、（14）式得 f4(x4)?max{u4?4x4?5x5}

0?u4?x4 ?max{u4?4x4?5(0.9x4?0.1u4)}?max{0.5u4?8.5x4}

0?u4?x40?u4?x4当u4?x4时，f4(x4)?9x4 （3）k?3时，

f3(x3)?max{u3?4x3?9x4}

0?u3?x3 ?max{u3?4x3?9(0.9x3?0.1u3)}?max{0.1u3?12.1x3}

0?u3?x30?u3?x3当u3?x3时，f3(x3)?12.2x3 （4）k?2时，

f2(x2)?max{u2?4x2?12.2x3}?max{?0.22u2?14.98x2}

0?u2?x20?u2?x2当u2?0时，f2(x2)?14.98x2。 （5）k?1时，

f1(x1)?max{u1?4x1?14.98x2}?max{?0.498u1?17.482x1}

0?u1?x10?u1?x1当u1?0时，f1(x1)?17.482x1。因为 x1?1000（台） 所以由（12）式，进行回代得

x2?0.9x1?0.1u1?900（台） x3?0.9x2?0.1u2?810（台） x4?0.9x3?0.1u3?648（台） x5?0.9x4?0.1u4?518.4（台）

注：x5?518.4台中的0.4台应理解为有一台机器只能使用0.4年将报废。

例6 求解下面问题 maxz?u1u2u3

2?u1?u2?u3?c(c?0) ??ui?0i?1,2,3

-48-

解： 按问题的变量个数划分阶段，把它看作为一个三阶段决策问题。设状态变量为x1,x2,x3,x4，并记x1?c；取问题中的变量u1,u2,u3为决策变量；各阶段指标函数按乘积方式结合。令最优值函数fk(xk)表示第k阶段的初始状态为xk，从k阶段到3阶段所得到的最大值。

设x3?u3， x3?u2?x2， x2?u1?x1?c 则有

u3?x3， 0?u2?x2， 0?u1?x1

用逆推解法，从后向前依次有

*f3(x3)?max{u3}?x3 及最优解 u3?x3

u3?x322f2(x2)?max{u2f3(x3)}?max{u2(x2?u2)}?maxh2(u2,x2)

0?u2?x20?u2?x20?u2?x2由

dh222?2u2x2?3u2?0，得u2?x2和u2?0（舍去）

3du22u2?x23d2h2d2h2又?2x2?6u2，而22du2du2所以f2(x2)???2x2?0，故u2?2x2为极大值点。 3432*x2 及最优解 u2?x2。 2734f1(x1)?max{u1f2(x2)}?max{u1(x1?u1)3}

0?u1?x10?u1?x127141x1，最优解u1*?x1。 同样利用微分法易知 f1(x1)?644由于x1已知，因而按计算的顺序反推算，可得各阶段的最优决策和最优值。即

114*u1?c，f1(x1)?c

464由

13*x2?x1?u1?c?c?c

44所以

*u2?211x2?c，f2(x2)?c3 3216311c?c?c 424由

*x3?x2?u2?所以

11c，f3(x3)?c 44111***因此得到最优解为：u1?c，u2?c，u3?c；

424*u3? -49-