和灵活的技巧性,这就带来了应用上的局限性 (i)用数值方法求解时存在维数灾( curse of dimensionality)。若一维状态变量有m 个取值,那么对于n维问题,状态x就有m”个值,对于每个状态值都要计算、存储函 数f(x),对于n稍大(即使n=3)的实际问题的计算往往是不现实的。日前还没 有克服维数灾的有效的一般方法 §5若干典型问题的动态规划模型 5.1最短路线问题 寸于例1一类最短路线问题( shortest Path Problem),阶段按过程的演变划分,状 态由各段的初始位置确定,决策为从各个状态出发的走向,即有xk+1=u4(xk),阶段 指标为相邻两段状态间的距离d4(xk2u4(x),指标函数为阶段指标之和,最优值函数 f4(xk)是由x出发到终点的最短距离(或最小费用),基本方程为 f(xr=mn [d (k, u,(xr))+f, (xkDlk=n,, 1; fn+1(xn+1)=0 利用这个模型可以算出例1的最短路线为ABC2DE2F2G,相应的最短距离为 52生产计划问题 对于例2一类生产计划问题( Production planning problem),阶段按计划时间自然 划分,状态定义为每阶段开始时的储存量x,决策为每个阶段的产量u,记每个阶段 的需求量(已知量)为dk,则状态转移方程为 xk+1=xk+l4-dk,x≥0.k=1,2,…,n (5) 设每阶段开工的固定成本费为a,生产单位数量产品的成本费为b,每阶段单位数量产 品的储存费为C,阶段指标为阶段的生产成本和储存费之和,即 (4)=+{+,“4>0 指标函数V为v4之和。最优值函数f(x)为从第k段的状态x出发到过程终结的最 小费用,满足 f4(x)=m[v4(xk,uk)+fk+1(xk+1),k=n,…1 其中允许决策集合U由每阶段的最大生产能力决定。若设过程终结时允许存储量为 x21,则终端条件是 (7) (5)~(7)构成该问题的动态规划模型 53资源分配问题 种或几种资源(包括资金)分配给若干用户,或投资于几家企业,以获得最大的 效益。资源分配问题( resource allocating Problem)可以是多阶段决策过程,也可以是 静态规划问题,都能构造动态规划模型求解。下面举例说明。 例4机器可以在高、低两种负荷下生产。u台机器在高负荷下的年产量是g(u),-41- 和灵活的技巧性，这就带来了应用上的局限性。 （ii）用数值方法求解时存在维数灾（curse of dimensionality）。若一维状态变量有 m 个取值，那么对于 n 维问题，状态 k x 就有 n m 个值，对于每个状态值都要计算、存储函 数 ( ) k k f x ，对于 n 稍大（即使 n = 3 ）的实际问题的计算往往是不现实的。目前还没 有克服维数灾的有效的一般方法。 §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 dk xk uk xk f k xk k n  u x k k k k = + + + = ( ) 0. f n+1 xn+1 = 利用这个模型可以算出例 l 的最短路线为 AB1C2D1E2F2G ， 相应的最短距离为 18。 5.2 生产计划问题 对于例 2 一类生产计划问题（Production planning problem），阶段按计划时间自然 划分，状态定义为每阶段开始时的储存量 k x ，决策为每个阶段的产量 k u ，记每个阶段 的需求量（已知量）为 k d ，则状态转移方程为 , 0, 1,2, , . xk +1 = xk + uk − dk xk  k =  n (5) 设每阶段开工的固定成本费为 a ，生产单位数量产品的成本费为 b ，每阶段单位数量产 品的储存费为 c ，阶段指标为阶段的生产成本和储存费之和，即    +  = + 0 , 0 ( , ) k k k k k k a bu u v x u cx (6) 指标函数 Vkn 为 k v 之和。最优值函数 ( ) k k f x 为从第 k 段的状态 k x 出发到过程终结的最 小费用，满足 ( ) min [ ( , ) ( )], , ,1. f x vk xk uk f k 1 xk 1 k n  u U k k k k = + + + =  其中允许决策集合 Uk 由每阶段的最大生产能力决定。若设过程终结时允许存储量为 0 n+1 x ，则终端条件是 ( ) 0. 0 f n+1 xn+1 = （7） （5）~（7）构成该问题的动态规划模型。 5.3 资源分配问题 一种或几种资源（包括资金）分配给若干用户，或投资于几家企业，以获得最大的 效益。资源分配问题（resource allocating Problem）可以是多阶段决策过程，也可以是 静态规划问题，都能构造动态规划模型求解。下面举例说明。 例 4 机器可以在高、低两种负荷下生产。 u 台机器在高负荷下的年产量是 g(u)