数学建模-动态规划

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

联系客服:779662525#qq.com(#替换为@)