当前位置:首页 >> 理学 >>

动态规划










数学建模培训 2012.07

动 态 规 划
(Dynamic programming)

1.动态规划的基本方法
2.动态规划应用举例 3.马氏决策规划简介

动态规划是用来解决多阶段决策过程最优 化的一种数量方法。其特点在于,它可以把一 个n 维决策问题变换为几个一维最优化问题,从 而一个一个地去解决。

需指出:动态规划是求解某类问题的一种 方法,是考察问题的一种途径,而不是一种算 法。必须对具体问题进行具体分析,运用动态 规划的原理和方法,建立相应的模型,然后再 用动态规划方法去求解。

动态决策问题的特点: 系统所处的状态和时刻是进行决策的重要因素; 即在系统发展的不同时刻(或阶段)根据系统 所处的状态,不断地做出决策; 找到不同时刻的最优决策以及整个过程的最优策略。
多阶段决策问题: 是动态决策问题的一种特殊形式; 在多阶段决策过程中,系统的动态过程可以按照时间 进程分为状态相互联系而又相互区别的各个阶段; 每个阶段都要进行决策,目的是使整个过程的决策 达到最优效果。

决策 状态 状态 1

决策 决策 状态 ? 状态 2 n

多阶段决策问题的典型例子:
1 . 生产决策问题:企业在生产过程中,由于需 求是随时间变化的,因此企业为了获得全年的最佳 生产效益,就要在整个生产过程中逐月或逐季度地 根据库存和需求决定生产计划。 2. 机器负荷分配问题:某种机器可以在高低两 种不同的负荷下进行生产。在高负荷下进行生产时, 产品的年产量g和投入生产的机器数量u1的关系为 g=g(u1)

这时,机器的年完好率为a,即如果年初完好机 器的数量为u,到年终完好的机器就为au, 0<a<1。
在低负荷下生产时,产品的年产量h和投入生产 的机器数量u2的关系为 h=h(u2)

相应的机器年完好率b, 0< b<1。
假定开始生产时完好的机器数量为s1。要求制 定一个五年计划,在每年开始时,决定如何重新 分配完好的机器在两种不同的负荷下生产的数量, 使在五年内产品的总产量达到最高。

3. 航天飞机飞行控制问题:由于航天飞机的 运动的环境是不断变化的,因此就要根据航天飞机 飞行在不同环境中的情况,不断地决定航天飞机的 飞行方向和速度(状态),使之能最省燃料和实现 目的(如软着落问题)。
不包含时间因素的静态决策问题(本质上是一 次决策问题)也可以适当地引入阶段的概念,作为 多阶段的决策问题用动态规划方法来解决。 4 . 线性规划、非线性规划等静态的规划问题也 可以通过适当地引入阶段的概念,应用动态规划方 法加以解决。

5 . 最短路径问题:给定一个交通网络图如下, 其中两点之间的数字表示距离(或花费),试求从A 点到G点的最短距离(总费用最小)。
1 C1 3 6 8 3 D1 1 2 2 2 5 E2 2 D2 E1 3

5
A 3

B1

6
8 B2 7 6

C2

5
3

5

F1
3

4
G

C3 8 C4

3
4 D3

3
3 4 E3

6
6

F2

1

2

3

5

6

一、动态规划的基本思想
(一)、基本概念
1、阶段: 把一个问题的过程,恰当地分为若干个相互联系的 阶段,以便于按一定的次序去求解。

描述阶段的变量称为阶段变量k 。阶段的划分,一般 是根据时间和空间的自然特征来进行的,但要便于问题 一个数、 年、月、 转化为多阶段决策。 一组数、
路段 一个向 2、状态:表示每个阶段开始所处的自然状况或客观 量 条件。通常一个阶段有若干个状态,描述过程状态的

变量称为状态变量sk 。 状态变量的取值有一定的允许集合或范围,此集合 称为状态允许集合。

3、决策:表示当过程处于某一阶段的某个状态时, 可以作出不同的决定,从而确定下一阶段的状态,这 种决定称为决策。

描述决策的变量,称为决策变量uk。决策变量是状 态变量的函数。可用一个数、一组数或一向量(多维 情形)来描述。 在实际问题中决策变量的取值往往在某一范围之内, 此范围称为允许决策集合。 4、多阶段决策过程 可以在各个阶段进行决策,去控制过程发展的多段过 其发展是通过一系列的状态转移来实现的; 程; 系统在某一阶段的状态转移不但与系统的当前的状态 和决策有关,而且还与系统过去的历史状态和决策有 关。

其状态转移方程如下(一般形式)

s2 ? T1 ( s1 , u1 ) s3 ? T2 ( s1 , u1 , s2 , u2 ) ?? sk ?1 ? Tk ( s1 , u1 , s2 , u2 ,? , sk , uk )
图示如下: u1 1 u2 2

状态转移方程是确定 过程由一个状态到另 一个状态的演变过程。 如果第k阶段状态变量 sk的值、该阶段的决策 变量一经确定,第k+1 阶段状态变量sk+1的值 也就确定。

s1

s2

s3

?

sk

uk k

sk+1

能用动态规划方法求解的多阶段决策过程是一类 特殊的多阶段决策过程,即具有无后效性的多阶段 决策过程。

无后效性(马尔可夫性) 如果某阶段状态给定后,则在这个阶段以后 过程的发展不受这个阶段以前各段状态的影响; 过程的过去历史只能通过当前的状态去影响 它未来的发展; 构造动态规划模型时,要充分注意 是否满足无后效性的要求; 状态变量要满足无后效性的要求; 如果状态变量不能满足无后效性的要求,应 适当地改变状态的定义或规定方法。 状态具有无后效性的多阶段决策过程的状 态转移方程如下 动态规划中能 s2 ? T1 ( s1 , u1 ) 处理的状态转移 s3 ? T2 ( s2 , u2 ) 方程的形式。 ?? sk ?1 ? Tk ( sk , uk )

5、策略:是一个按顺序排列的决策组成的集合。 k 子过程策略 p ?s ? ? ?u ?s ?, u ?s ?,....,u ?s ?? 当 k ? 1时,得策略 p ?s ? ? ?u ?s ?, u ?s ?,....,u ?s ?? 在实际问题中,可供选择的策略有一定的范围,称 为允许策略集合P。从允许策略集合中找出达到最优效 果的策略称为最优策略。
k ,n k k k k ?1
1

k ?1

n

n

1, n

1

1

2

2

n

n

6、指标函数和最优值函数:用来衡量所实现过程优 劣的一种数量指标,为指标函数。
Vk , n ? Vk ,n (sk , uk , sk ?1 , uk ?1 ,?, sn ?1 )

指标函数应具有可分离性,并满足递推关系。即 指标函数的最优值,称为最优值函数。

Vk ,n (sk , uk , sk ?1 , uk ?1 ,?, sn?1 ) ? ?k [ sk , uk ,Vk ?1,n ( sk ?1 , uk ?1 ,?, sn?1 )]

f k ( s k ) ? opt V k ,n ( s k , u k ,?, s n?1)
?u k ,?,u n?

指标函数常见的形式 (1)各段指标的和的形式 n Vk ,n ?sk , u k ,..., sn?1 ? ? ? v j ?s j , u j ? ? vk ?sk , u k ? ? Vk ?1,n ?sk ?1 , u k ?1 ,..., sn?1 ?
j ?k

(2)各段指标的积的形式
Vk ,n ?sk , u k ,..., sn?1 ? ? ? v j ?s j , u j ? ? vk ?sk , u k ?Vk ?1,n ?sk ?1 , u k ?1 ,..., sn?1 ?
n

其中v j ?s j , u j ?表示第 j 阶段的阶段指标

j ?k

小结: 无后效性 动态规划本质上是多阶段决策过程;
概念 : 阶段变量k﹑状态变量sk﹑决策变量uk; 方程 :状态转移方程 sk ?1 ? Tk ( sk , uk ) 指标: Vk ,n ? Vk ,n ( sk , uk , sk ?1 , uk ?1 ,?, sn?1 )
效益

f k ( s k ) ? opt V k ,n ( s k , u k ,?, s n ?1)
?u k ,?,u n?
Vk ,n ( sk , uk , sk ?1 , uk ?1 ,?, sn ?1 )
可递推

? ?k [ sk , uk , Vk ?1, n ( sk ?1 , uk ?1 , ?, sn ?1 )]
指标函数形式: 和、 积

解多阶段决策过程问题,求出
最优策略,即最优决策序列

{u , u ,? , u }
最优轨线,即执行最优策略时的状态序列
* * * { s1 , s2 , ? , sn }

* 1

* 2

* n

f1(s1)

最优目标函数值
* V1,n * * * * * ? V1,n ( s1 , u1 ,?, sn , un )

f ?s ? ? opt v ?s , u
k k

从 k 到终点最优策略 子策略的最优目标函数值
k k

?u

k

,?,

un ?

k ,n

,? , sn?1

?

(二)、动态规划的基本思想
最短路径有一个重要特性: 如果由起点A经过P点和H点而到达终点G是 一条最短路线,则由点P出发经过H点到达 终点G的这条子路线,对于从点P出发到达 终点的所有可能选择的不同路线来说,必定 也是最短路线。如图
A P H G

H1

下面将例五从最后一段开始计算,由后向前逐步推移至A点 当k ? 6 时,由F1 到终点 G只有一条路线,故 f 6 ( F1 ) ? 4 。
同理 f 6 ( F2 ) ? 3。

E E 当k ? 5时,出发点有E1、 2 、 3 三个。若从 E1 出发, 则有两个选择,一是至 F1 ,一是至 F2 ,则
?d 5 ( E1 , F1 ) ? f 6 ( F1 ) ? ?3 ? 4? f 5 ( E1 ) ? min ? ? ? min ? ??7 ?5 ? 3 ? ?d 5 ( E1 , F2 ) ? f 6 ( F2 )?

其相应的决策为 u5 ( E1 ) ? F1 。这说明,由 E1 至终点G 的最短 距离为7,其最短路线是 E1 ? F1 ? G 。 同理,从 E2 和 E 3 出发,则有

?d 5 ( E 2 , F1 ) ? f 6 ( F1 ) ? ?5 ? 4? f 5 ( E 2 ) ? min ? ? ? min ? ??5 ? 2 ? 3? ?d 5 ( E 2 , F2 ) ? f 6 ( F2 )?

其相应的决策为 u5 ( E2 ) ? F2 。
?d 5 ( E3 , F1 ) ? f 6 ( F1 ) ? ?6 ? 4? f 5 ( E3 ) ? min ? ? ? min ? ??9 ?6 ? 3 ? ?d 5 ( E3 , F2 ) ? f 6 ( F2 )?

且 u5 ( E3 ) ? F2 。 类似地,可算得 当 k ? 4 时,有

f 4 ( D1 ) ? 7
f 4 ( D2 ) ? 6
f 4 ( D3 ) ? 8

u 4 ( D1 ) ? E2
u 4 ( D2 ) ? E2
u 4 ( D3 ) ? E2

当 k ? 3 时,有
f 3 (C1 ) ? 13
f 3 (C 2 ) ? 10

u3 (C1 ) ? D1
u3 (C 2 ) ? D1

f 3 (C3 ) ? 9
f 3 (C 4 ) ? 12

u3 (C3 ) ? D2

u3 (C 4 ) ? D3

当k ? 2时,有
f 2 (B1 ) ? 13
f 2 (B 2 ) ? 16
u 2 (B1 ) ? C 2
u 2 (B 2 ) ? C 3

当 k ? 1时,出发点只有一个 A 点,则
?d1 ( A, B1 ) ? f 2 ( B1 ) ? ?5 ? 13 ? f 1 ( A) ? min ? ? min ? ? ? ? 18 ?3 ? 16 ? ?d1 ( A, B2 ) ? f 2 ( B2 )?

且 u1 (A) ? B1。于是得到从起点 A 到终点G 的最短距离为18 为了找出最短路线,再按计算的顺序反推之,可求 出最优决策函数序列 ?u k ? ,即由

u1 (A) ? B1

u 2 (B1 ) ? C 2

u3 (C 2 ) ? D1

u5 ( E2 ) ? F2

u 6 ( F2 ) ? G

组成一个最优策略。因而,找出相应的最优路线为

A ? B1 ? C2 ? D1 ? E2 ? F2 ? G

基本思想:

1、动态规划方法的关键在于正确地写出基本的递推
关系式和恰当的边界条件(简称基本方程)。要做

到这一点,就必须将问题的过程分成几个相互联系
的阶段,恰当的选取状态变量和决策变量及定义最 优值函数,从而把一个大问题转化成一组同类型的 子问题,然后逐个求解。即从边界条件开始,逐段 递推寻优,在每一个子问题的求解中,均利用了它 前面的子问题的最优化结果,依次进行,最后一个 子问题所得的最优解,就是整个问题的最优解。

2、在多阶段决策过程中,动态规划方法是既把当前 一段和未来一段分开,又把当前效益和未来效益结合 起来考虑的一种最优化方法。因此,每段决策的选取 是从全局来考虑的,与该段的最优选择答案一般是不 同的. 3、在求整个问题的最优策略时,由于初始状态是 已知的,而每段的决策都是该段状态的函数,故最优 策略所经过的各段状态便可逐段变换得到,从而确定 了最优路线。 最优化原理:作为整个过程的最优策略具有这样的 性质:无论过去的状态和决策如何,相对于前面的决 策所形成的状态而言,余下的决策序列必然构成最优 子策略。”也就是说,一个最优策略的子策略也是最 优的。

(三)、建立动态规划模型的步骤 1、划分阶段 划分阶段是运用动态规划求解多阶段决策问题的第一 步,在确定多阶段特性后,按时间或空间先后顺序, 将过程划分为若干相互联系的阶段。对于静态问题要 人为地赋予“时间”概念,以便划分阶段。

2、正确选择状态变量 选择变量既要能确切描述过程演变又要满足无后效性, 而且各阶段状态变量的取值能够确定。一般地,状态变 量的选择是从过程演变的特点中寻找。
3、确定决策变量及允许决策集合 通常选择所求解问题的关键变量作为决策变量,同时要 给出决策变量的取值范围,即确定允许决策集合。

4、确定状态转移方程
根据k 阶段状态变量和决策变量,写出k+1阶段状态变 量,状态转移方程应当具有递推关系。

5、确定阶段指标函数和最优指标函数,建立动态规 划基本方程
阶段指标函数是指第k 阶段的收益,最优指标函数 是指从第k 阶段状态出发到第n 阶段末所获得收益的最 优值,最后写出动态规划基本方程。 以上五步是建立动态规划数学模型的一般步骤。由于 动态规划模型与线性规划模型不同,动态规划模型没有统 一的模式,建模时必须根据具体问题具体分析,只有通过 不断实践总结,才能较好掌握建模方法与技巧。

最短路径问题
例一、从A 地到D 地要铺设一条煤气管道,其中需经过 两级中间站,两点之间的连线上的数字表示距离,如 图所示。问应该选择什么路线,使总距离最短?
3
2 A 4 B2 B1 1 2 3

C1
C2 4 C3 3

1 D

3 1

3
2 A 4 B2 B1 1 2 3

C1
C2 4 C3 3

1 D

3 1

解:整个计算过程分三个阶段,从最后一个阶段开始。

第一阶段(C →D): C 有三条路线到终点D 。
显然有 f1 (C1 ) = 1 ; f1(C2 ) = 3 ; f1 (C3 ) = 4

3
2 A 4 B2 B1 1 2 3

C1
C2 4 C3 3

1 D

3 1

第二阶段(B →C): B 到C 有六条路线。
d( B1,C1 ) + f1 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f1 (C2 ) = min 3+3 d( B1,C3 ) + f1 (C3 ) 1+4 4 = min 6 = 4 (最短路线为B1→C1 →D) 5

3
2 A 4 B2 B1 1 2 3

C1
C2 4 C3 3

1 D

3 1

d( B2,C1 ) + f1 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f1 (C2 ) = min 3+3 d( B2,C3 ) + f1 (C3 ) 1+4 3 = min 6 = 3 (最短路线为B2→C1 →D) 5

3
2 A 4 B2 B1 1 2 3

C1
C2 4 C3 3

1 D

3 1

第三阶段( A → B ): A 到B 有二条路线。
f3(A)1 = d(A, B1 )+ f2 ( B1 ) =2+4=6 f3 (A)2 = d(A, B2 )+ f2 ( B2 ) =4+3=7 ∴ f3 (A) = min d(A, B1 )+ f2 ( B1 ) = min{6,7}=6 d(A, B2 )+ f2 ( B2 ) (最短路线为A→B1→C1 →D)

3 2 A 4 B2 B1 2 3 1 3 1

C1 C2 4 3

1 D

C3

最短路线为

A→B1→C1 →D

路长为 6

REMARK: 1.例1中寻求最优策略的方向是由D点到A点为逆行 方向, 这种以A为始端,D为终端,从D到A的解法称 为逆序解法。 2.如果从A到D的解法称为顺序解法。此解法与逆序 解法的求解方向相反。 3.动态规划的方法比穷举法有以下优点: (1)减少计算量 (2)丰富了计算结果 4.动态规划基本方程的表述: 设V ? ? v ?s , u ? ,则可将此式写成
n k ,n j ?k j j j

Vk ,n ?sk , u k ,..., sn?1 ? ? vk ?sk , u k ? ? Vk ?1,n ?sk ?1 , u k ?1 ,..., sn?1 ?

当初始状态给定时,指标函数是初始状态和 策略的函数,则指标函数可写成
Vk ,n ?sk , pk ,n ? ? vk ?sk , u k ? ? Vk ?1,n ?sk ?1 , pk ?1,n ?

其中子策略 pk ,n ? ? k ?s k ?, pk ?1,n ?s k ?1 ?? u 如果用 p ?s ? 表示初始状态为 s k 的后部子过程 所有子策略中的最优子策略,则最优值函数为
* k ,n k

* f k ?sk ? ? Vk ,n sk , pk ,n ?sk ? ? optVk ,n sk , pk ,n ?sk ? pk , n

?

?

?

?

而 optVk ,n ?sk , pk ,n ?sk ?? ? ?u opt ??vk ?sk , uk ? ? Vk ?1,n ?sk ?1 , pk ?1,n ?? p ,p
k ,n k k ?1, n

? ? opt?v k ?s k , u k uk ?

? ? ? opt Vk ?1,n ? pk ?1, n ?

但是

f k ?1 ?sk ?1 ? ? opt Vk ?1, n ?sk ?1 , pk ?1, n ?
p k ?1,n

所以

f k ?s k ? ? opt ?v k ?s k , u k ? ? f k ?1 ?s k ?1 ??
u k ?Dk ? sk ?

k ? n, n ? 1,...., 1

f n ?1 ?s n ?1 ? ? 0 边界条件 以上即为动态规划逆序解法的基本方程, 最后求出 f1 ?s1 ? 即为最优解。 类似可得动态规划顺序解法的基本方程

f k ?s k ?1 ? ?

r u k ?Dk ? sk ?1 ?

opt

?vk ?sk ?1 , u k ? ? f k ?1 ?sk ??
f 0 ?s1 ? ? 0

k ? 1,2,...,n

边界条件为

其中状态转移方程为 第k 阶段的允许决策集合为

s k ? Tkr ?s k ?1 , u k ?

Dkr ?s k ?1 ?

最后求出 f ?s ?即为整个问题的最优解。
n n ?1

练习1: 求从A到G的最短路径
1 5 A 3 B2 C1 6 8 C2 2 2 D2 3 8 4 D3 3 3 E3 1 5

B1
6 8 7

3

3
5 3

D1

E1

3 5 F1 4 G

2

E2 6

2 6 F2

3

6

C3

C4

最优路线为:A → B1 → C2 → D1 → E2 → F2 → G

路长=18

C1 6 1 D1 2 E1 3 8 k=6, F1 G f6(F1)=4 B1 3 5 F1 4 5 2 C2 3 6 A 5 D2 1 E25 G F2 G ,f6(F2)=3 3 2 2 B2 87 C3 3 3 E36 F2 3 3 D3 6 6 C4 8 3 k=5,出发点E1、E2、E3 4

3? 4 ?d5 ?E1 , F1 ? ? f 6 ?F1 ? ? f 5( E1) ? min ?d 5 ?E , F ? ? f ?F ? ? ? min{5 ? 3} ? 7 1 2 6 2 ? ?

u5(E1)=F1
E1 F1 G

? d5 ?E2 , F1 ? ? f 6 ?F1 ? f 5 ?E 2 ? ? min ? ?d5 ?E2 , F2 ? ? f 6 ?F2 ?
? d 5 ?E3 , F1 ? ? f 6 ?F1 ? f 5 ?E 3? ? min ? ?d 5 ?E3 , F2 ? ? f 6 ?F2 ?

5?4 ? }?5 ? ? min{ 2?3 ?
6?4 ? }?9 ? ? min{ 6?3 ?

u5(E2)=F2
E2 F2 G

u5(E3)=F2
E3 F2 G

k=4, 4(D1)=7 u4(D1)=E2 f

k=3,

f3(C1)=13 u3(C1)=D1

f4(D2)=6 u4(D2)=E2 f4(D3)=8 u4(D3)=E2
k=2, f2(B1)=13 u2(B1)=C2

f3(C2)=10 u3(C2)=D1
f3(C3)=9 u3(C3)=D1

f3(C4)=12 u3(C4)=D3

f2(B2)=16 u2(B2)=C3
k=1,

f1(A)= min

d1(A,B1)+ f2(B1)
d1(A,B2)+ f2(B2)

5+13

= min

3+16

=18

u1(A)=B1

u2(B1)=C2

u3(C2)=D1

u4(D1)=E2

u1(A)=B1
E1 F1 G

u2(B1)=C2
E2 F2 G

u3(C2)=D1

u4(D1)=E2 u5(E2)=F2

u5(E1)=F1 u5(E2)=F2

u5(E3)=F2
E3 F2 G

7
1 5 A 3 B2 B1 6 3

5
C1 C2 3 5 6

9
8 D1
1 2 3 D3 2 2 5 E2 6 D2

u6(F2)=G
最优策略
E1
3 5 F1 3 F2 4 G

8
7 6 C3

3
3

2
6

8 4
C4

3

E3

练习2: 求从A到E的最短路径
B1
2 10

12
14 10

C1
9

3

D1
6

5 2

A

5
1

B2 B3

6

C2
8

4 13

5 12 11

E

D2
10

C3

路线为A→B2→C1 →D1 →E ,最短路径为19

动态规划的最优性定理 设阶段数 n 的多阶段决策过程,其阶段编号 为 为 k ? 0,1,..., n ? 1


p0*,n?1 ? u0* , u1* ,....,u n*?1 是最有策略的充要条件是对 允许策略

?

?

任一个 k



0 ? k ? n ? 1和 s0 ? S 0 有

* V0,n ?1 s 0 , p 0,n ?1

?

?

? ? ? ?~ ?? ? opt V0,k ?1 , 0 , p 0,k ?1 ? s opt Vk ,n ?1 ? s k , p k ,n ?1 ?? ? p0 , k ?1?P0 , k ?1 ? x0 ? ?~ ? ? ?? ? pk , n ?1?Pk , n ?1 ? s k ? ? ? ? ? ? ?

?

?

式中 它是由给定的初始状态s 和子策略 p 所确定的 k 段状态 当V是效益函数时,opt 取max; 当V 是损失函数时,opt取min。
0 , k ?1

p0,n?1 ? ( p0,k ?1 , pk ,n?1 ) ,s k ? T ?s , u ? k ?1 k ?1 k ?1
~

0



推论
若允许策略

p0*,n?1是最优策略,则对任意的 k,0 ? k ? n ? 1

p k*,n?1 对于以sk* ? Tk ?1 ?sk*?1 , uk*?1 ?为起点的 k 到 n ?1 子过 它的子策略

程来说,必是最优策略。 Remark:

k 段状态 s 是由 s 0 和

* k

* p 0 ,k ?1 所确定的。

动态规划与静态规划的关系
静态规划:研究的问题与时间无关的数学规划 Remark:(非)线性规划利用迭代法,每一步都 是就问题的整体加以改善,最终求得最优解。 动态规划:所研究问题与时间有关。 Remark: 动态规划研究的是一类多阶段决策过程问 题,将问题整体按时间或空间特征分成若干个前 后衔接的时空阶段,将问题表示为前后相关联的 一系列单阶段决策问题,然后逐个加以解决,从 而求出最优策略序列。

Remark: 对于动态规划来说,关键在于正确写出动 态规划的递推关系式。当初始状态给定时,用 逆推比较方便;当终止状态给定时,用顺推比 较方便。 考察n 阶段决策过程:
xk 决策 x1 sk ?1 s2 s 状态 s1 k ? 1 k vk ( s k , xk ) 效益v (s , x )
1 1 1

xn sn

n
vn ( s n , xn )

sn?1

逆推解法
设已知初始状态为s1 ,并假定最优值函数 f (s ) 表示第k 阶段的初始状态为s k ,从k 阶段到n 阶段所得到的最大效益。 从第n阶段开始,则有
k k

f n ( s n ) ? max vn ( s n , xn )
xn ?Dn ( sn )

解此一维极值问题,可得到最优解x 优值 f (s ) 。 在第n-1阶段,有
n n

n

? xn ( s n )

和最

f n ?1 ( s n ?1 ) ?

xn ?1?Dn ( sn ?1 )

max [v n ?1 ( s n ?1 , x n ?1 ) * f n ( s n )]

解此一维极值问题,可得到最优解 x ? x (s )和最优值 f n?1 (sn?1 )。 在第k阶段,有 f ( s ) ? max [v ( s , x ) * f ( s )]
n ?1 n ?1 n ?1

k

k

xk ?Dk ( sk )

k

k

k

k ?1

k ?1

解得最优解 x ? x (s ) 和最优值 f k (sk ) 。 如此类推,直到第一阶段,有 f1 ( s1 ) ? max [v1 ( s1 , x1 ) * f 2 ( s 2 )]
k k k

x1?D1 ( s1 )

解得最优解 x1 ? x1 (s1 ) 和最优值 f1 (s1 ) 。 例 用逆推解法求解下面问题
2 max z ? x1 ? x2 ? x3

? x1 ? x 2 ? x3 ? c, (c ? 0) ? ? xi ? 0, i ? 1,2,3

解:按问题的变量个数划分阶段,把它看作为一个 三阶段决策问题。设状态变量为s , s , s , s ,并 s ? c 。 取问题中的变量 x , x , x 为决策变量;各阶段指标 函数按乘积方式结合。令最优值函数 f (s ) 表示为 第k阶段的初始状态为 s k ,从k阶段到3阶段所得 到的最大值。 s ?x ?s s2 ? x1 ? s1 ? c 设 s 3 ? x3 则有 x ? s 0 ? x2 ? s 2 0? x ?s ?c
1 2 3 4

1

1

2

3

k

k

3

2

2

3

3

1

1

于是用逆推解法,从后向前依次有
f 3 ( s3 ) ? max( x3 ) ? s3
x3 ? s3

及最优解

* x3 ? s 3

2 2 f 2 ( s 2 ) ? max x 2 ? f 3 ?s3 ? ? max x 2 ? ?s 2 ? x 2 ? ? max h2 ( s 2 , x 2 ) 0 ? x2 ? s2 0 ? x2 ? s 2 0 ? x2 ? s 2

?

?

?

?




dh2 2 ? 2 x 2 s 2 ? 3x 2 ? 0 dx2




x2 ? 2 s 2 3



x2 ? 0(舍去)

d 2 h2 ? 2s 2 ? 6 x 2 2 dx2

d 2 h2 ? ?2s 2 ? 0 2 2 dx2 x 2 ? 3 s 2





x2 ? 2 s 2 3

为极大值点。
* x2 ? 2 s 2 3

4 所以 f 2 (s2 ) ? 27 s23 及最优解

4 ? 3? f1 ( s1 ) ? max x1 ? f 2 ?s 2 ? ? max ? x1 ? ?s1 ? x1 ? ? ? max h1 ( s1 , x1 ) 0? x1 ? s1 0? x1 ? s1 27 ? ? 0? x1 ? s1

?

?

象前面一样利用微分法易知
f1 (s1 ) ? 1 4 s1 64

* x1 ?

1 s1 4

故 由于已知 s1 ? c,因而按计算的顺序反推算,可得各阶段 的最优决策和最优值。即

x

* 1

1 ? c 4

f1 (c) ?

1 4 c 64



* s 2 ? s1 ? x1 ? c ?

1 3 c ? c 4 4
f 2 ?s 2 ? ? 1 3 c 16

所以 由 所以

* x2 ?

2 1 s 2 ? c, 3 2

* s3 ? s 2 ? x 2 ?

3 1 1 c? c ? c 4 2 4

1 x ? c, 4
* 3

?s3 ? ? 1 c f3
4
1 x ? c 2
* 2

因此得到最优解为
* x1 ?

1 c 4

1 x ? c, 4
* 3

最大值为

1 4 max z ? f1 (c) ? c 64

顺推解法
设已知终止状态为s ,并假定最优值函数 f k (s) 表示第k 阶段末的结束状态为 s ,从1 阶段到k阶段 所得到的最大效益。 从第1阶段开始,则有 f1 ( s2 ) ? max v1 ( s1 , x1 ) x ?D ( s ) 其中 s ? T ?s , x ? 解此一维极值问题,可得到最优解 x1 ? x1 (s2 ) 和最优 值 f1 (s2 ) 。若x1 ? D1 ?s1 ? 只有一个决策,则 x ? x ?s ? 就写成
n ?1

1

1

1

1

* 1

2

1

1

1

2

在第2阶段,有
f 2 ( s3 ) ? max [v 2 ( s 2 , x 2 ) * f 1 ?s 2 ?
x2 ?D2 ( s2 )
3 2

其中 s ? T ?s , x ? ,解得最优解 x 如此类推,直到第n 阶段,有
2 * 2

2

? x2 ?s3 ? 和最优值 f 2 ( s3 )

f n ( s n ?1 ) ? max [vn ( s n , xn ) * f n ?1 ?s n ?

s n ? Tn* ?s n?1 , xn ?,解得最优解 xn ? xn ?sn?1 ?和最优值 f n (sn?1 ) 其中

xn ?Dn ( sn )

由于终止状态 s 是已知的,故x ? x ?s ?和 f (s ) 是 确定的。再按计算过程的相反顺序推算上去,就可逐 步确定出每阶段的决策及效益。 Remark:若将状态变量的记法改为s0 , s1 ,...., s n 决策变量记法不变,则按顺序解法,此时的最优值 函数为 f (s ) 。因而,这个符号与逆推解法的符号一
n ?1
n n n ?1
n n ?1
k k

样,但含义是不同的,这里的 结束状态。 例 用顺推解法求解下面问题
2 max z ? x1 ? x2 ? x3

sk

是表示k阶段末的

? x1 ? x 2 ? x3 ? c, (c ? 0) ? ? xi ? 0, i ? 1,2,3

解:设 s4 ? c ,令最优值函数 f k ?sk ?1 ? 表示第k 阶段末 的结束状态为 sk ?1 ,从1阶段到k 阶段的最大值 s ?x ?s s2 ? x1 s3 ? x3 ? s4 ? c 设 0? x ?s ?c 0 ? x2 ? s3 则有 x ? s 于是用顺推解法,从前向后依次有
2 2 3
1 2
3 4

f1 ( s2 ) ? max( x1 ) ? s2
x1 ? s 2

及最优解

* x1 ? s2

f 2 ( s3 ) ? max x ? f1 ?s2 ? ? max x ? ?s3 ? x2 ?
0 ? x 2 ? s3 2 2 0 ? x 2 ? s3 2 2

?

?

?

?

4 3 ? 27 s3

及最优解

* x2 ?

2 s3 3

4 1 4 ? 3? f 3 ( s4 ) ? max x3 ? f 2 ?s3 ? ? max ? x3 ? ?s4 ? x3 ? ? ? s4 0 ? x3 ? s 4 0 ? x3 ? s 4 27 ? ? 64

?

?

及最优解 由于已知
* x1 ?

* x3 ?

s4 ? c

1 s4 4

,故易得到最优解为
1 x ? c 2
* 2

1 c 4

1 x ? c, 4
* 3

相应的最优值为 max z ? f1 (c) ? 1 c 4
64

(二)考虑初始状态 s1 ? c ,状态转移函数为
sk ? sk ?1 ? xk , k ? 1,2,3
3 2 2

sk ?1 ? sk ? c
0 ? x3 ? s3 ? s4 ? c ? s4

s4 ? x3 ? s3 设 x1 ? s2 ? s1 ? c s ? x ? s 则有 x ? s ? s ?? c ? s 0 ? x2 ? s2 ? s3 ? c ? s3 于是用顺推解法,从前向后依次有
1 1 2 2

f1 ( s2 ) ? max ( x1 ) ? c ? s2
x1 ? c ? s 2

及最优解

* x1 ? c ? s2

2 2 f 2 (s3 ) ? max x2 ? f1 ?s2 ? ? max x2 ? ?c ? s3 ? x2 ? ? 0? x2 ? c ? s3 0? x2 ? c ? s3

?

?

?

?

4 ?c ? s3 ?3 27

及最优解

2 * x2 ? (c ? s3 ) 3

4 1 ? 3? f 3 ( s4 ) ? max x3 ? f 2 ?s3 ? ? max ? x3 ? ?c ? s4 ? x3 ? ? ? (c ? s 4 ) 4 0 ? x3 ? c ? s 4 0 ? x3 ? c ? s 4 27 ? ? 64

?

?

及最优解

1 * x3 ? (c ? s4 ) 4

由于终止状态 s 4 不知道,故须再对 s 4 求一次极值,即 1 ?c ? s4 ?4 max f 3 ( s4 ) ? max 0? x ? c 0? x ? c 64 显然,只有当 s ? 0 时, f (s ) 才能达到最大值。然后 按计算顺序反推算可求出各阶段的最优决策及最优值。 最后得到最优解为 x ? 1 c x ? 1 c x ? 1 c, 4 2 4 最大值为 1
4 4
4 3 4
* 1

* 2

* 3

max z ? f 3 (0) ?

64

c4

用顺推解法解下列问题
2 2 max F ? 4 x12 ? x2 ? 2 x3 ? 12

?3x1 ? 2 x2 ? x3 ? 9 ? ? xi ? 0, i ? 1,2,3

届 解:按问题中变量的个数分为三个阶段。设状态 变量为 s0 , s1 , s2 , s3 ,并记 s3 ? 9 取 x , x , x 为各阶段的决策变量;各阶段指 f k ?sk ? 标 sk 函数按加法方式结合。令最优值函数 表示 第k阶段的结束状态为 ,从1阶段至k阶段的 s ? 2x ? s s2 ? x3 ? s3 ? 9 3x1 最大值。? s1 设
1 2 3

1

2

2

x1 ? s1 / 3

0 ? x2 ? s2 / 2

则有

0 ? x3 ? s3

于是用顺推解法,从前向后依次有
f1 (s1 ) ? max 4 x
x1 ? s1 / 3

? ?
2 1

4 2 ? s1 9

及最优解

* x1 ? s1 / 3

2 f 2 ( s2 ) ? max ? x2 ? f1 ( s1 ) 0? x2 ? s 2 / 2

?

?

4 ? max [? x ? ( s2 ? 2 x2 ) 2 ? max h2 ( s2 , x2 ) 0? x2 ? s2 / 2 0 ? x2 ? s 2 / 2 9
2 2



dh2 14 16 8 ? x2 ? s 2 ? 0 ? x 2 ? s 2 dx2 9 9 7

因该点不在允许决策集合内,故无须判别。因而 h2 (s2 , x2 ) 的最大值必在两个端点上选取。 s 4 1 而 h (0) ? s 2 , h ( 2 ) ? ? s 2
2

9

2

2

2

4

2

所以 h2 (s2 , x2 )的最大值点在 x2 ? 0

4 2 处,故得到 f 2 (s2 ) ? s2 9

及相应的最优解
0 ? x3 ? s 3

x2 ? 0
*

2 f 3 ( s3 ) ? max 2 x3 ? 12 ? f 2 ( s2 )

?

?

4 ? max [2 x ? 12 ? ( s3 ? x3 ) 2 ? max h3 ( s3 , x3 ) 0 ? x3 ? s 3 0 ? x3 ? s 3 9
2 3

由 又 而

dh3 44 8 2 ? x3 ? s3 ? 0 ? x3 ? s3 dx3 9 9 11
d 2 h3 44 ? ?0 2 dx3 9

,故该点为极小值点。
2 h3 (s3 ) ? 2s3 ? 12

h3 (0) ?

4 2 s3 ? 12 9
3
*

故 h3 (s3 , x3 ) 的最大值点在 x ? s 处。所以得 f 3 (s3 ) ? 2s32 ? 12 及相应的最优解 x ? s 由于 s 3 不知道,故须再对 s 3 求一次极值,即
3
3 3

2 f 3 ( s3 ) ? max 2 s3 ? 12 0 ? s3 ? 9

?

?

显然,当

s3 ? 9

时 f 3 (s3 )才能达到最大值。

所以 为最大值。 再按计算顺序反推算可求得最优解为
x

f1 (9) ? 2 ? 9 2 ? 12 ? 174
* x2 ? 0 ? 0

最大值为

* 1

* x3 ? 9

max F ? f1 (9) ? 174

REMARK (1)若先作代换,令 y1 ? 3x1 , y2 ? 2x2 , y3 ? x3 将原问题变为
4 2 1 2 2 max F ? y1 ? y2 ? 2 y3 ? 12 9 4
? y1 ? y 2 ? y3 ? 9 ? ? yi ? 0, i ? 1,2,3

再解此问题,然后换回即可。 (2)在计算 h2 和 h3 的最大值中,可用凸函数 的性质确定最大值。

练习1

2 max z ? 4 x1 ? 9 x 2 ? 2 x 3

?x1 ? x 2 ? x 3 ? 10 ? ?x i ? 0, i ? 1,2,3
2 2 max F ? 4 x12 ? x2 ? x3 ? 12

练习2 设某人有400万元金额,计划在四年内全部 用于投资中去。已知在一年内若投资用去x 万元就能获得 x 万元的效用。每年没有用掉 的金额,连同利息(年利息1%)可用于下一年 的投资。而每年已打算用于投资的金额不计利 息制订金额的使用计划,而使四年内获得总效用 最大?

?2 x1 ? x2 ? 3 x3 ? 9 ? ? xi ? 0, i ? 1,3 ?x ? 0 ? 2

动态规划应用举例

投资分配问题
现有数量为a(万元)的资金,计划分配给n 个工厂, 用于扩大再生产。 假设:xi 为分配给第i 个工厂的资金数量(万元) ; gi(xi)为第i 个工厂得到资金后提供的利润值(万元)。 问题是如何确定各工厂的资金数,使得总的利润为 最大。 n 据此,有下式: max Z ? g (x )

?
i ?1

i

i

? n ?? xi ? a ? i ?1 ? x ? 0 i ? 1.2.? .n ? i

令:fk(x) = 以数量为x 的资金分配给前k 个工厂,所 得到的最大利润值。 用动态规划求解,就是求 fn(a) 的问题。 当 k=1 时, f1(x) = g1(x) (因为只给一个工厂)

当1<k≤n 时,其递推关系如下: 设:y 为分给第k 个工厂的资金(其中 0≤y ≤ x ),此时 还剩 x - y(万元)的资金需要分配给前 k-1 个工厂,如 果采取最优策略,则得到的最大利润为fk-1(x-y) ,因此 总的利润为:

gk(y) + fk-1(x-y)

所以,根据动态规划的最优化原理,有下式:

f k ( x ) ? max ?g k ( y ) ? f k ?1 ( x ? y )?
0? y ? x

其 中k ? 2.3.?.n
如果a 是以万元为资金分配单位,则式中的y 只取 非负整数0,1,2,…,x。上式可变为:

f k ( x) ?

?g k ( y ) ? y ? 0 ,1, 2 ,?, x
max

f k ?1 ( x ? y )?

例题:
设国家拨给60万元投资,供四个工厂扩建使用,每 个工厂扩建后的利润与投资额的大小有关,投资后的 利润函数如下表所示。
投资 利润

0

10

20

30

40

50

60

g1(x) g2(x) g3(x) g4(x)

0 0 0 0

20 20 25 25

50 40 60 40

65 50 85 50

80 55 100 60

85 60 110 65

85 65 115 70

解:依据题意,是要求 f4(60) 。

按顺序解法计算。 第一阶段:求 f1(x)。显然有 f1(x) = g1(x),得到下表
投资

0 0 0

10 20 10

20 50 20

30 65 30

40 80 40

50 85 50

60 85 60

利润

f1(x) = g1(x)

最优策略

第二阶段:求 f2(x)。此时需考虑第一、第二个工厂如 何进行投资分配,以取得最大的总利润。
f 2 (60 ) ?

?g 2 ( y ) ? y ? 0 ,10,?, 60
max

f1 (60 ? y )?

? g 2 (0) ? f1 (60 ) ? ?0 ? 85 ? ? g (10 ) ? f (50 ) ? ?20 ? 85 ? 1 ? 2 ? ? ? ? g 2 (20 ) ? f1 (40 )? ?40 ? 80 ? ? ? ? ? ? max ? g 2 (30 ) ? f1 (30 ) ? ? max ?50 ? 65 ? ? 120 ? g (40 ) ? f (20 )? ?55 ? 50 ? 1 ? 2 ? ? ? ? g 2 (50 ) ? f1 (10 ) ? ?60 ? 20 ? ? ? ?65 ? 0 ? ? ? ? g 2 (60 ) ? f1 (0) ?
最优策略为(40,20),此时最大利润为120万元。 同理可求得其它 f2(x) 的值。

f 2 (50 ) ?

?g 2 ( y ) ? y ? 0 ,10,?, 50
max

f1 (50 ? y )?

? g 2 (0) ? f1 (50 ) ? ? g (10 ) ? f ( 40 ) ? 1 ? 2 ? ? g 2 ( 20 ) ? f1 (30 ) ? ? ? ?? ? ? 105 ? g 2 (30 ) ? f1 ( 20 ) ? ? g 2 ( 40 ) ? f1 (10 ) ? ? ? ? g 2 (50 ) ? f1 (0) ? ? ?
最优策略为(30,20),此时最大利润为105万元。

f 2 ( 40 ) ?

?g 2 ( y ) ? y ? 0 ,10,?, 40
max

f1 ( 40 ? y )?

? 90

最优策略为(20,20),此时最大利润为90万元。
f 2 (30 ) ?

?g 2 ( y ) ? y ? 0 ,10, 20, 30
max

f1 (30 ? y )?

? 70

最优策略为(20,10),此时最大利润为70万元。

f 2 ( 20 ) ? max ? 50

?g 2 ( y ) ? y ? 0 ,10, 20

f1 ( 20 ? y )?

最优策略为(20,0),此时最大利润为50万元。
f 2 (10 ) ? max ?g 2 ( y ) ? f1 (10 ? y )?
y ? 0 ,10,

? 20 最优策略为(10,0)或( 0 , 10 ) ,此时最大利润 为20万元。

f2(0) =0。最优策略为(0,0),最大利润为0万元。 得到下表

投资 利润

0 0

10 20

20 50

30 70

40 90

50 105

60 120

f2(x) 最优策略

(0,0) (10,0) (20,0) (20,10) (20,20) (30,20) (40,20) (0,10)

第三阶段:求 f3(x)。此时需考虑第一、第二及第三个 工厂如何进行投资分配,以取得最大的总利润。
f 3 (60 ) ?

?g3 ( y ) ? y ? 0 ,10,?, 60
max

f 2 (60 ? y )?

? g3 (0) ? f 2 (60 ) ? ?0 ? 120 ? ? g (10 ) ? f (50 ) ? ?25 ? 105 ? 2 ? 3 ? ? ? ? g3 (20 ) ? f 2 (40 )? ?60 ? 90 ? ? ? ? ? ? max ? g3 (30 ) ? f 2 (30 ) ? ? max ?85 ? 70 ? ? 155 ? g (40 ) ? f (20 )? ?100 ? 50 ? 2 ? 3 ? ? ? ? g3 (50 ) ? f 2 (10 ) ? ?110 ? 20 ? ? ? ?115 ? 0 ? ? ? ? g3 (60 ) ? f 2 (0) ?
最优策略为(20,10,30),最大利润为155万元。

同理可求得其它 f3(x) 的值。得到下表

投资 利润

0 0

10 25

20 60

30 85

40 110

50 135

60 155

f3(x)

最优 (0,0,0) (0,0,10) (0,0,20) (0,0,30) (20,0,20) (20,0,30) (20,10,30) 策略

第四阶段:求 f4(60)。即问题的最优策略。
f 4 (60 ) ?

?g 4 ( y ) ? y ? 0 ,10,?, 60
max

f 3 (60 ? y )?

? g 4 (0) ? f 3 (60 ) ? ?0 ? 155 ? ? g (10 ) ? f (50 ) ? ?25 ? 135 ? 3 ? 4 ? ? ? ? g 4 (20 ) ? f 3 (40 )? ?40 ? 110 ? ? ? ? ? ? max ? g 4 (30 ) ? f 3 (30 ) ? ? max ?50 ? 85 ? ? 160 ? g (40 ) ? f (20 )? ?60 ? 60 ? 3 ? 4 ? ? ? ? g 4 (50 ) ? f 3 (10 ) ? ?65 ? 25 ? ? ? ?70 ? 0 ? ? ? ? g 4 (60 ) ? f 3 (0) ?
最优策略为(20,0,30,10),最大利润为160万元。

例 某公司有9个推销员在全国三个不同市场推 销货物,这三个市场里推销人员数与收益的关 系如下表,试作出使总收益最大的分配方案。

解:设分配人员的顺序为市场1, 2, 3,采用反向阶段编号。

设 sk 为第k阶段尚未分配的人员数,边界条件为 s3=9
设 xk 为第k阶段分配的推销人员数;仍采用反向递推, 状态转移方程为 sk–1=sk – xk

目标函数为

f3 ( x ) ? min ? d ( xi )
x1 , x2 , x3 i ?1

3

解:第一阶段:给第三市场分配
s1 有0~9种可能,第一阶段最优决策表如下:

第二阶段:给第二市场分配

s2 有0~9种可能,第二阶段最优决策表如下:

第三阶段:给第一市场分配

由边界条件 s3=9,第三阶段最优决策表如下:
x3 s3 9 0 1 2 3 4 5 6 7 8 9 x3* f3* 211 213 218 217 215 208 206 202 201 200 2 218

得决策过程:x3*=2, x2*=0, x1*=7, f3*=218 即 市场1 分配 2人,市场2 不分配 ,市场 3 分配 7人 最优解与分配的顺序有关吗?

例 项目选择问题
某工厂预计明年有A,B,C,D四 个新建项目,每个项目的投资额 wk及其投资后的收益 vk如下表所 示。投资总额为30万元,问如何 选择项目才能使总收益最大。 上述问题的静态规划模型如下:
max f ( x ) ? ? vk xk
k

? ? wk xk ? 30 k ? ? ?0 k 项未入选 ? xk ? ? ?1 k 项入选 ?

这是一类0-1规划问题 该问题是经典的旅行背包问 题 (Knapsack) 该问题是 NP-complete

解:设项目选择的顺序为A, B, C, D; 1、阶段 k=1, 2, 3, 4 分别对应 D, C, B, A项目的选择过 程 2、第 k 阶段的状态 sk,代表第 k 阶段初尚未分配的投 资额 3、第 k 阶段的决策变量 xk,,代表第 k 阶段分配的投 资额 4、状态转移方程为 sk-1= sk– wk xk 5、直接效益 dk (sk ,xk)= vk或 0 6、总效益递推公式 该问题的难点在于各阶段的状态的确定,当阶段 增加时,状态数成指数增长。下面利用决策树来 确定各阶段的可能状态。

第一阶段(项目D)的选择过程 s1 <8 时,x1 只能取0;w1 =8, v1 =5
s1 3 5 8 15 18 20 30 x1 0 ? 0 ? 0 1 0 1 0 1 0 1 0 1 d 1 (s1 , x 1 ) s 0 = 0 ? 0 ? 0 5 0 5 0 5 0 5 0 5 s1 -w 1x 1 f 0 (s 0 , x 0*) f 1 (s 1 , x 1*) 3 0 0 ? 5 0 0 ? 8 0 0 0 5 15 0 7 0 5 18 0 10 0 5 20 0 12 0 5 30 0 22 0 5 条件 x 4 =x 2 =1 x 3 =0 x 4 =x 3 =1 x 2 =0 x 3 =x 2 =1 x 4 =0 x 3 =x 2 =0 x 4 =1 x 4 =x 3 =0 x 2 =1 x 4 =x 2 =0 x 3 =1 x 4 =x 3 =x 2=0

第二阶段(项目C)的选择过程

第三阶段(项目B)的选择过程
s3 15 30 x3 0 1 0 1 d 3 (s3 , x 3 ) s 2 = 0 8 0 8 s3 -w 3x 3 15 5 30 20 w 3 =10 f 2 (s 2 , x 2*) f 3 (s 3 , x 3*) 9 9* 0 8 14 14 14 22* v 3 =8 条件 x 4 =1 x 4 =0

第四阶段(项目A)的选择过程
x4 0 30 1 项目 A B C D s4 w4 =15 v 4 =12 d 4 (s4 , x 4 ) s 3 = s4 -w4x 4 f 3 (s 3 , x 3*) f 4 (s 4 , x 4*) 条件 0 30 22 22* 12 15 9 21 决策 投资额 直接收益 v k x 4 =0 0 0 x 3 =1 10 8 x 2 =1 12 9 x 1 =1 8 5 总额 30 22

例:有资金4万元,投资A、B、C三个项目,每 个项目的投资效益与投入该项目的资金有关。三 个项目A、B、C的投资效益(万吨)和投入资金 (万元)的关系见下表:
项目 投入资金 1万元

A
15万吨

B
13万吨

C
11万吨

2万元
3万元 4万元

28万吨
40万吨 51万吨

29万吨
43万吨 55万吨

30万吨
45万吨 58万吨

求对三个项目的最优投资分配,使总投资效益最大。

阶段k:每投资一个项目作为一个阶段; 状态变量xk:投资第k个项目前的资金数; 决策变量dk:第k个项目的投资; 决策允许集合:0≤dk≤xk 状态转移方程:xk+1 =xk -dk 阶段指标:vk (xk ,dk )见表中所示; 递推方程:fk (xk )=max{vk (xk ,dk )+fk+1 (xk+1)} 终端条件:f4 (x4 )=0 k=4,f4 (x4 )=0 k=3,0≤d3≤x3 ,x4 =x3 –d3

x3

D3(x3)

x4

v3(x3,d3) v3(x3,d3)+f4(x4) f3(x3)

d3*

0
1

0
0 1 0 1 2 0

0
1 0 2 1 0 3

0
0 11 0 11 30 0

0+0=0
0+0=0 11+0=11* 0+0=0 11+0=11 30+0=30* 0+0=0

0
11

0
1

2

30

2

3

1
2 3 0 1

2
1 0 4 3 2 1

11
30 45 0 11 30 45

11+0=11
30+0=30 45+0=45* 0+0=0 11+0=11 30+0=30 45+0=45

45

3

4

2 3

58

4

4

0

58

58+0=58*

k=2,0≤d2 ≤x2 ,x3 =x2 –d2
x2 D2(x2) x3 v2(x2,d2) v2(x2,d2)+f3(x3) f2(x2) d2 *

0
1

0
0 1 0

0
1 0 2

0
0 13 0

0+0=0
0+11=11 13+0=13* 0+30=30*

0
13

0
1

2

1
2 0

1
0 3

13
29 0

13+11=24
29+0=29 0+45=45*

30

0

3

1
2 3

2
1 0

13
29 43

13+30=43
29+11=40 43+0=43

45

0

0
1 4 2 3 4

4
3 2 1 0

0
13 29 43 55

0+58=58
13+45=58 29+30=59* 43+11=54 55+0=55 59 2

k=1,0≤d1≤x1,x2=x1-d1
x1 D1(x1) x2 v1(x1,d1) v1(x1,d1)+f2(x 2) 0 1 4 2 3 4 4 3 2 1 0 0 15 28 40 51 0+59=59 15+45=60* 28+30=58 40+13=53 51+0=51 60 1 f1(x1) d1*

最优解为x1=4, d1*=1, x2=x1-d1=3, d2*=0, x3=x2-d2*=3, d3=3, x4=x3-d3=0, 即项目A投资1万元,项目B投资0万元, 项目C投资3万元,最大效益为60万吨。

练习:
求投资分配问题得最优策略,其中a=50 万元,其余 资料如表所示。
投资 利润

0 0 0

10 21 15

20 40 36

30 52 50

40 80 73

50 85 100

g1(x) g2(x)

g3(x)

0

25

60

65

68

70

练习 某公司打算在3个不同的地区设臵4个销售点, 根据市场部门估计,在不同地区设臵不同数量的销 售点每月可得到的利润如表所示。试问在各地区如 何设臵销售点可使每月总利润最大。
地 区 1 2 3 销售点 0 0 0 0 1 16 12 10 2 25 17 14 3 30 21 16 4 32 22 17

x1=2,x2=1,x3=1,f3(4)=47

背包问题
有一个徒步旅行者,其可携带物品重量的限度为a 公 斤,设有n 种物品可供他选择装入包中。已知每种物品 的重量及使用价值(作用),问此人应如何选择携带 的物品(各几件),使所起作用(使用价值)最大?
物品 重量(公斤/件) 每件使用价值

1
a1

2
a2




j
aj




n
an

c1

c2



cj



cn

这就是背包问题。类似的还有工厂里的下料问题、 运输中的货物装载问题、人造卫星内的物品装载问题 等。

设xj 为第j 种物品的装件数(非负整数)则问题的数学 n 模型如下:

max Z ? ? c j x j
j ?1

?n ?? a j x j ? a ? j?i ? x ? 0且为整数 ( j ? 1.2.? .n) ? j
用动态规划方法求解,令

fk(y) = 总重量不超过 y 公斤,包中只装有前k 种物品 时的最大使用价值。
其中y ≥0, k =1,2, …, n 。所以问题就是求 fn(a)

其递推关系式为:
y 0? x k ? ak

f k ( y ) ? max ?ck x k ? f k ?1 ( y ? a k x k )?

其中 2 ? k ? n
当 k=1 时,有:

? y? f1 ( y ) ? c1 ? ? , ?a ? ? 1?

? ? y ?? ? x1 ? ? ?? ?a ? ? 1 ?? ?

? y? y 其中? ?表示不超过 的最大整数 ?a ? a1 ? 1?

例题:求下面背包问题的最优解

max Z ? 8 x1 ? 5 x 2 ? 12 x 3 ? 3 x1 ? 2 x 2 ? 5 x 3 ? 5 ? ? x1 , x 2 , x 3 ? 0且为整数
解:a=5 ,问题是求 f3(5)

1 重量(公斤) 3 使用价值 8

物品

2 2 5

3 5 12

f 3 ( 5) ? max
0? x 3 ?

? 12 x 3 ? 5

f 2 ( 5 ? 5 x 3 )?

a3 x 3整 数

f 3 ( 5) ? max
0? x 3 ?

? 12 x 3 ? 5

f 2 ( 5 ? 5 x 3 )?

=max ? 12 x 3 ? f 2 ( 5 ? 5 x 3 )? =max ? 12 x 3 ? f 2 ( 5 ? 5 x 3 )?
x 3 0, = 1 5 0? x 3 ? 5 x 3整 数

a3 x 3整 数

? ? =max ?0 ? f 2 ( 5), 12 ? f 2 ( 0)? ( x 3 ?1 ) ? ( x3 ? 0 ) ?

f 2 (5) ? max ? 5 x 2 ? f1 (5 ? 2 x 2 )?
0? x 2 ?

=max ? 5 x 2 ? f 1 (5 ? 2 x 2 )?
0? x 2 ?

5 a2 x 2整 数

= max ? 5 x 2 ? f 1 (5 ? 2 x 2 )?
x 2 0,, 2 = 1

5 2 x 2整 数

? ? =max ?0 ? f1 (5), 5 ? f 1 ( 3), 10 ? f 1 (1) ? ( x 2 ?1 ) ( x2 ? 2) ? ( x2 ? 0 ) ?

f 2 (0) ? max ? 5 x 2 ? f1 (0 ? 2 x 2 )?
0? x 2 ?

=max ? 5 x 2 ? f1 (0 ? 2 x 2 )?
0? x 2 ?

0 a2 x 2整 数

=max ? 5 x 2 ? f1 (0 ? 2 x 2 )?
x2 0 =

0 2 x 2整 数

? ? =max ?0 ? f1 (0) ? ? f1 (0) ? ( x2 ? 0 ) ?

? ? ? f 2 (5) ? max ?0 ? f1 (5), 5 ? f1 ( 3), 10 ? f1 (1) ? ( x 2 ?1 ) ( x2 ? 2) ? ( x2 ? 0 ) ? ? max ?8, 5 ? 8, 10? ? 13 ( x1 ? 1, x 2 ? 1)

5 f1 (5) ? c1 x1 ? 8 ? ? 8 3 3 f1 ( 3) ? c1 x1 ? 8 ? ? 8 3 1 f1 (1) ? c1 x1 ? 8 ? ? 0 3 0 f1 (0) ? c1 x1 ? 8 ? ? 0 3

( x1 ? 1) ( x1 ? 1) ( x1 ? 0) ( x1 ? 0)

? ? f 2 (0) max ?0 ? f1 (0) ? ? f1 (0) ? 0 ( x1 ? 0, x 2 ? 0) = ? ( x2 ? 0 ) ?

? ? ? f 3 ( 5) max ?0 ? f 2 ( 5), 12 ? f 2 ( 0)? = ( x 3 ?1 ) ? ( x3 ? 0 ) ? ? max ? 0 ? 13, 12 ? 0 ? ? 13 ( x1 ? 1, x 2 ? 1, x 3 ? 0)
所以,最优解为 X=(1 . 1 . 0),最优值为 Z = 13。

练习1:某厂生产三种产品,各种产品重量与利 润的关系如表所示。现将此三种产品运往市场出售, 运输能力总重量不超过 6 吨,问如何安排运输,使 总利润最大?
种类

1

2

3

重量(吨/公斤)
单件利润(元)

2

3

4

80 130 180

最优方案:X1 =(0.2.0)X2 =(1.0.1)Z=260

练习2:求下列问题的最优解

max Z ? 4 x1 ? 5 x 2 ? 6 x 3 ? 3 x1 ? 4 x 2 ? 5 x 3 ? 10 ? ? x1 , x 2 , x 3 ? 0且为整数
最优值为 Z = 13

X=(2. 1. 0)

排序问题
排序问题指n 种零件经过不同设备加工的顺序问题。其 目的是使加工周期为最短。 1、n × 1 排序问题

即n 种零件经过1 种设备进行加工,如何安排?

例一、
零件代号 加工时间(t) 交货日期(d)

j1

j2

j3

j4

j5

3 23

7 20

1 8

5 6

4 14

(1)平均通过设备的时间最小
按零件加工时间非负次序排列顺序,其时间最小。(即 将加工时间由小到大排列即可)
零件加工顺序 工序时间 实际通过时间 交货时间
j3

j1

j5

j4

j2

1 1 8

3 4 23

4 8 14

5 13 6

7 20 20

平均通过时间

1 x ? ( 20 ? 13 ? 8 ? 4 ? 1) ? 9.2 5

延迟时间 = 13 – 6 = 7
(2)按时交货排列顺序
零件加工顺序 工序时间 实际通过时间
j4
j3 j5

j2

j1

5 5

1 6

4 10

7 17

3 20

交货时间

6

8

14

20

23

延迟时间 = 0

1 平均通过时间 x ? ( 20 ? 17 ? 10 ? 6 ? 5) ? 11.6 5

(3)既满足交货时间,又使平均通过时间最小
零件加工顺序 工序时间 实际通过时间 交货时间
j3

j4

j1

j5

j2

1 1 8

5 6 6

3 9 23

4 13 14

7 20 20

延迟时间 = 0 平均通过时间

1 x ? ( 20 ? 13 ? 9 ? 6 ? 1) ? 9.8 5

2、n × 2 排序问题
即n 种零件经过2 种设备进行加工,如何安排?

例二、
设备 A 零件

j1
6

j2
8

j3
7

j4
3

j5
5

B
A B

3

2

5

9

4

T

经变换为
设备 A B 零件

j4
3 9

j3
7 5

j5
5 4

j1
6 3

j2
8 2

加工周期 T = 3+7+5+6+8+2 = 31 即? t Ai ? t B小 加工顺序图如下:
A B
9

j4
3

j3
7 +2

j5
5 +2 5

j1
6 4 3

j2
8 -5 2

T

3、n × 3 排序问题
即n 种零件经过 3 种设备进行加工,如何安排?

例三、

j1 j2
j3

j4
j5

A 10 7 8 6 6

B 3 5 6 4 5

C 9 3 4 3 8

A B C T

变换

j1 j2
j3

j4
j5

A+B 10+3 7+5 8+6 6+4 6+5

B+C 3+9 5+3 6+4 4+3 5+8

排序
j5

j1
j3

j2 j4

A+B 6+5 10+3 8+6 7+5 6+4
A 6 10 8 7 6 B 5 3 6 5 4

B+C 5+8 3+9 6+4 5+3 4+3
C 8 9 4 3 3

复原
j5

j1
j3

j2 j4

计算

T = 6+10+8+7+6+4+3 = 44

计算依据:

min t Ai ? max t Bi 即可按下式计算



min tC i ? max t Bi ? t B ? t C 或 ? t ci ? t B ? t A

?t

Ai

练习:
j1 j2
j3

j4
j2
j1

A 6 7 9 5

B 4 2 7 8

C 7 8 10 11

j4

j3

T=45

产品生产计划安排问题 例1 某工厂生产某种产品的月生产能力为10件,已知 今后四个月的产品成本及销售量如表所示。如果本月产 量超过销售量时,可以存储起来备以后各月销售,一件 产品的月存储费为2元,试安排月生产计划并做到: 1、保证满足每月的销售量,并规定计划期初和期末 库存为零; 2、在生产能力允许范围内,安排每月生产量计划使 产品总成本(即生产费用加存储费)最低。

? 设xk为第k阶段生产量,则有直接成本 dk (sk, xk)= ck xk+2sk ? 状态转移公式为 Sk-1= sk+ xk- yk ? 总成本递推公式

第一阶段:(即第4月份) 由边界条件和状态转移方程 s0=s1+x1–y1= s1+x1– 6=0 得 s1 +x1 = 6 或 x1 = 6 – s1 估计第一阶段,即第4月份初库存的可能状态: s1 ?[0,5]

第一阶段最优决策表 第二阶段:最大可能库存量 7 件
s1 0 1 2 3 4 5 x 1? 6 5 4 3 2 1 f 1 (s 1 , x 1? ) 456 382 308 234 160 86

由状态转移方程: s1=s2+x2-12?0 及 x2?10,可知 s2?[2,7],min x2=5 由阶段效果递推公式有: f2(2,10)=d2(2,10)+f1*(0,6) =2?2+80?10+456=1260 得第二阶段最优决策表,如下
7 8 9 1182* 1110 1038 966 894 s 1 =4 10 x 2 * f 2 (s 2 ,x2 *) 1260 1182 1104 1026 948 870

s2 x2 2 3 4 5 6 7

5

6

1026* 948* 954 870* 876 882 s 1 =0 s 1 =1 s 1 =2

1104* 1032 960 888 s 1 =3

1260* 10 1188 9 1116 8 1044 7 972 6 900 5 s 1 =5

第二阶段最优决策表
s2 2 3 4 5 6 7
s3 x3 0 1 2 3 4

x2* 10 9 8 7 6 5
5

f 2 (s 2 ,x2 *) 1260 1182 1104 1026 948 870
6 7

第三阶段:最大可能库存量 4 件 由状态转移方程: s2=s3+x3-7?2 及 x3?10,可知 s3?[0,4],min x3=5 由阶段效果递推公式有: f3(1,10)=d3(1,10)+f2*(4,8) =2?1+72?10+1104=1826 得第三阶段最优决策表,如下
8 9 1908 1832 1756 1680 1604 s 2 =6 10 1902* 1826* 1750* 1674* 1598* s 2 =7 x 3 * f 3 (s 3 ,x3 *) 10 10 10 10 10 1902 1826 1750 1674 1598

1838 1768 1762 1698 1692 1686 1628 1622 1616 1610 s 2 =2 s 2 =3 s 2 =4 s 2 =5

第三阶段最优决策表

第四阶段:初始库存量 s4=0 由状态转移方程: s3=s4+x4-6?0 可知 x4?6,由阶段效果递推公式 有:f4(0,6)=d4(0,6)+f3*(0,10) =70?6+1902=2322 得第四阶段最优决策表,如下

回 溯 得 此 表

生产–库存管理问题(连续变量)
设某厂计划全年生产某种产品A。其四个季度的订货量分别为 600公斤,700公斤,500公斤和1200公斤。已知生产产品A的 生产费用与产品的平方成正比,系数为0.005。厂内有仓库可 存放产品,存储费为每公斤每季度1元。求最佳的生产安排使 年总成本最小。 解:四个季度为四个阶段,采用阶段编号与季度顺序一致。 设 sk 为第k季初的库存量,则边界条件为 s1=s5=0 设 xk 为第k季的生产量,设 yk 为第k季的订货量; sk ,xk ,yk 都取实数,状态转移方程为 sk+1=sk+xk - yk 仍采用反向递推,但注意阶段编号是正向的 目标函数为

f1 ( x ) ?

x1 , x2 , x3 , x4 i ?1

min ? (0.005xi2 ? si )

4

第一步:(第四季度) 总效果 f4(s4,x4)=0.005 x42+s4 由边界条件有: s5= s4 + x4 – y4=0,解得:x4*=1200 – s4 将x4*代入 f4(s4,x4)得: f4*(s4)=0.005(1200 – s4)2+s4=7200 –11 s4+0.005 s42 第二步:(第三、四季度) 总效果 f3(s3,x3)=0.005 x32+s3+ f4*(s4) 将 s4= s3 + x3 – 500 代入 f3(s3,x3) 得:

第三步:(第二、三、四季度) 总效果 f2(s2,x2)=0.005 x22+s2+ f3*(s3) 将 s3= s2 + x2 - 700 代入 f2(s2,x2) 得:

注意:最优阶段总效果仅是当前状态的函 数,与其后的决策无关

第四步:(第一、二、三、四季度) 总效果 f1(s1,x1)=0.005 x12+s1+ f2*(s2) 将 s2= s1 + x1 – 600= x1 – 600 代入 f1(s1,x1) 得:

由此回溯:得最优生产–库存方案 x1*=600,s2*=0; x2*=700,s3*=0; x3*=800,s4*=300; x4*=900。

串联系统可靠性问题
例:有 A, B, C 三部机器串联生产某种产品, 由于工艺技术问题,产品常出现次品。统 计结果表明,机器 A, B, C 产生次品的概率 分别为 pA=30%, PB=40%, PC=20%, 而产品 必须经过三部机器顺序加工才能完成。为 了降低产品的次品率,决定拨款 5 万元进 行技术改造,以便最大限度地提高产品的 成品率指标。现提出如下四种改进方案:

A

B

C

不拨款 拨款1万元 拨款2万元 拨款3万元

30% 20% 10% 5%

40% 30% 20% 10%

20% 10% 10% 6%

方案1: 不拨款,机器保持原状; 方案2: 加装监视设备,每部机器需款 1 万元; 方案3: 加装设备,每部机器需款 2 万元; 方案4: 同时加装监视及控制设备,每部机器需 款 3 万元; 采用各方案后,各部机器的次品率如右表。

解:为三台机器分配改造拨款,设拨款顺序为A, B, C,阶段 序号反向编号为 k,即第一阶段计算给机器 C 拨款的效果。 设 sk 为第 k 阶段剩余款,则边界条件为 s3=5; 设 xk 为第 k 阶段的拨款额; 状态转移方程为 sk-1=sk-xk; 目标函数为 max R=(1-PA)(1-PB)(1-PC) 仍采用反向递推 第一阶段 :对机器 C 拨款的效果 R1(s1,x1)=d1(s1,x1)? R0(s0,x0)= d1(s1,x1)
x1 s1 0 1 2 3 4 5 0 0.8 0.8 0.8 0.8 0.8 0.8 1 2 3 x1* 0 1 1, 2 3 3 3 R1 (s1 , x1*) 0.8 0.9 0.9 0.94 0.94 0.94

0.9 0.9 0.9 0.9 0.9

0.9 0.9 0.9 0.9

0.94 0.94 0.94

第二阶段 :对机器 B, C 拨款的效果 第一阶段最优决策表 由于机器 A 最多只需 3 万元,故 s2 ? 2 x1 x1* R1 s1 (s1, x1*) 递推公式: 0 0 0.8 R2(s2,x2)=d2(s2,x2)? R1(s1,x1*) 1 1 0.9 例:R2(3,2)=d2(3,2)? R1(1,1)=(12 1, 2 0.9 0.2) ?0.9=0.72 3 3 0.94 得第二阶段最优决策表
4 5
x2 s2 2 3 4 5

3 3
0

0.94 0.94
1 2 3 x2* 2 2,3 3 3 R2 (s2 , x2*) 0.64 0.72 0.81 0.81

0.54 0.63 0.64 0.564 0.63 0.72 0.564 0.658 0.72 0.564 0.658 0.752

0.72 0.81 0.81

第二阶段最优决策表
x2 x2* s2 2 3 4 5 2 2,3 3 3 R2 (s2, x2*) 0.64 0.72 0.81 0.81

第三阶段 :对机器 A, B, C 拨款的效果 边界条件:s3 = 5 递推公式: R3(s3,x3)=d3(s3,x3)? R2(s2,x2*) 例:R3(5,3)=d3(5,3)? R2(2,2)=(1-0.05) ?0.64=0.608 得第三阶段最优决策表
R3(s3, x3*) 0.648

s3 x3 0 1 2 3 x3* 5 0.567 0.648 0.648 0.608 1,2

回溯 :有多组最优解。 I:x3=1, x2=3, x1=1, R3=0.8 ?0.9 ?0.9=0.648 II:x3=2, x2=2, x1=1, R3= 0.9?0.8?0.9=0.648 III: x3=2, x2=3, x1=0, R3= 0.9?0.9?0.8 =0.648

马尔可夫决策规划
马尔可夫决策规划简称马氏决策规划,其主要解决 随机系统多阶段决策问题。

确定型系统与随机型系统的区别在于系统的状态 转移过程是确定的还是随机的(但有某种随机规律)。 确定型系统,当第k阶段的状态 x 与决策uk ( xk ) 确 定后,第k+1阶段的状态 xk ?1 就完全确定了。对整个 过程来说,若初始状态 x1 给定,又给定某一策略
k

{u1 ( x1 ),..., uk ( xk ),...} ,则整个过程就完全确定了。

在随机系统中,即使给定第k段的状态 xk 和 uk ( xk ),第

k+1段的状态也不能完全确定,而是一个随机变量,只
知道其概率分布。在初始状态 x1 给定时,相应策略为
{u1 (Z1 ),..., uk ( Z k ),...} ,其中 Z k 为系统在第k段的状态集合

表明u (Z )要对第k段状态的一切可能值给定相应的决策。
k k

一、马尔可夫过程
定义:有一类动态随机系统,其系统状态的转

移规律具有无后效性,即已知现时系统所处 的状态,采取决策后虽不能预知下次系统将转 移到哪个状态,但下次转移到的状态所服从的 概率规律是已知的,且与系统之前的发展历史 无关,称这种系统状态的转移规律具有马尔可 夫性质,称这种过程为马尔可夫过程。

考虑一种简单的马氏过程,即状态和时间参数都是离散的马氏过 程

假定相继两次转移之间的时间间隔为常数1;系统 是有限的,即有N个状态,标以1至N编号。记系统在 时刻t处于状态i,而在下一时刻t+1转移到状态j的概率 p ij 为 N 应有

?p
j ?1

ij

?1

0 ? p ij ? 1

其中 pij 表示系统逗留在状态i的概率,称 P ? [ pij ] N ?N 为状态转移矩阵。

例:有一工厂为市场生产某种产品,每月月初对产品 的销售情况进行一次检查,其结果又二:销路好(记 为状态1);也可能销路差(记为状态2)。若处于状 态1,由于各种随机因素的干扰,下月初仍处于销路好 的概率为0.5,转为销路差的概率为0.5;若处于状态2 则下月初转为销路好的概率为0.4,仍处于销路差的概 率为0.6。则状态转移矩阵为
? p11 P?? ? p21 p12 ? ?0.5 ? ? ?0.4 p22 ? ? 0.5? 0.6? ?

二、赋值马氏过程
定义:在具有N个状态的马氏过程,当它在任意时刻 从状态i 转移到状态j时可以获得相应的效益,记为r 。 这种马氏过程随着状态转移可得到一系列的报酬(效 益),称其为赋值马氏过程。称R ? [r ] 为报酬矩阵。
ij

ij

N ?N

例:上例中工厂若某月初销路好,下月初仍销路

好可获利9千元,下月初转为销路差可获利3千元
若某月初销路差,下月初转为销路好可获利3千元, 下月仍为销路差要亏本7千元。则报酬矩阵为
? r11 R?? ?r21 r12 ? ? 9 ? ? ?r r22 ? ? 21 3? ? 7? ?

下面考虑系统经过一定阶段的运行后的总期望报酬。 记 q i 为由状态i 做出一次转移的期望报酬,则有
qi ?

?p
j ?1

N

ij ij

r

(i ? 1,2,...., N )

Q ? [q(1), q(2),..., q( N )]T 称 为一次转移的期望报酬向量。记v n (i )

为系统由状态i经过n次转移之后的总期望报酬,则
vn (i) ? ? pij [rij ? vn?1 ( j )] ? q(i) ? ? pij vn?1 ( j ) (i ? 1,2,...., N )
j ?1 j ?1 N N

其中

p ij

r 表示由状态i转移到状态j的概率,ij 表示由状
Vn ? [vn (1), vn (2),..., vn ( N )]T

态j的相应报酬。称 总期望报酬向量 。

为n 次转移的



P ? [ pij ] N ? N

, R ? [rij ] N ?N
P ? R ? [? pij rij ]N ?1
j ?1 N N N

定义乘法 ?: 则有

Q ? P ? R ? [? p1 j r1 j ,..., ? pnj rnj ]T
j ?1 j ?1

(1) (2)

Vn ? Q ? PVn?1 ,

(n ? 2,3,....)

V1 ? Q

仍以上述工厂为例,由前已知
? 0 .5 P?? ? 0 .4 0 .5 ? 0 .6 ? ?

?9 3 ? R?? 3 ? 7? ? ?

由式(1)可知
?0.5 Q ? P?R ? ? ?0.4 0.5? ?9 ?? 0.6? ? ?3 3 ? ? 6 ? ?? ? 7? ? 3? ? ? ?

即如果当前销路好,则下月获利6000元,否则下月 损失3000元。
? 6 ? V1 ? Q ? ? ? 3? ? ? 0.5? ? 6 ? ? 7.5 ? ? ? ? 3? ? ? ? 2.4? 0.6? ? ? ? ?

? 6 ? ?0.5 V2 ? Q ? PV1 ? ? ? ? ?0.4 ? ? 3? ?

利用式(2)依次类推,可得出该工厂在不同初始状态 (销路好或销路差)下,经若干月后总期望获利情况。

如下表: n(月) 1
vn (1)
6

2
7.5

3
8.55

4
9.555

5
10.5555






(开始销路好)
v n ( 2)
-3 -2.4 -1.44 -0.444 0.5556

(开始销路差)

三、马氏决策规划
在赋值马氏过程中,如果在某状态选用不同的决策能

够 改变相应的状态转移矩阵及报酬矩阵,就产生了动态随机系 统求最优策略的问题。马氏决策规划就是研究这类问题。

下面通过实例介绍马氏决策规划中有限阶段模型 的一种求解方法——值迭代法。设系统目标为总期 望报酬最大化。 例:仍以上述工厂为例,设该厂在每个状态可选的决 策是不登广告(记作方式1)或登广告(记作方式2) 。若不登广告,自然无广告费;若登广告,要花额外

的广告费,但下月初销路好的概率可增加。

选决策方式1的状态转移矩阵及报酬矩阵为:
?0.5 0.5? P ?? 0.4 0.6? ? ?
1

?9 R ?? ?3
1

3 ? ? 7? ?

选决策方式2的状态转移矩阵及报酬矩阵为:
?0.8 0.2? 2 P ?? 0.7 0.3? ? ?
4 ? ?4 R ?? 1 ? 19 ? ? ?
1

问题是在若干月内采取什么决策才能使其总期望 报酬最大。

d pij 表示系统当前处于状态 用n表示系统的阶段数。

i,下一步以d种决策方式转移到状态j的概率。
f n (i ) 表示系统初始状态为i,采取最优策略时的总

期望报酬最大值。 则有如下方程:
d f n (i ) ? max {q (i ) ? ? pij f n ?1 (i )} d d ?{1, 2} j ?1 N

n ? 2,...

f1 (i ) ? max {q d (i )}
d?{1, 2}

由于
? q1 (1) ? ?0.5 0.5? ?9 3 ? ? 6 ? 1 1 Q ? ? 1 ? ? (P ) ? (R ) ? ? ? ? ?3 ? 7? ? ?? 3? ?0.4 0.6? ? ? ? ? ?q (2)?
1

? q 2 (1) ? ?0.8 0.2? ?4 4 ? ? 4 ? 2 2 2 Q ? ? 2 ? ? (P ) ? (R ) ? ? ? ? ?1 ? 19? ? ?? 5? ?0.7 0.3? ? ? ? ? ?q (2)?

因而
f1 (1) ? max{q1 (1), q 2 (1)} ? max{6,4} ? 6 f1 (2) ? max{q1 (2), q 2 (2)} ? max{?3,?5} ? ?3
d1 (1) ? 1 d1 (2) ? 1

d n (i ) 为第n阶段处于i状态时的决策。

这表明,该厂不论处于状态1还是状态2,如果 再继续生产1个月,都应采取决策1,即不论销路好还 是销路差都不登广告。 如果继续生产两个月:
f 2 (1) ? max{q (1) ? ? p f ( j ), q (1) ? ? p12j f1 ( j )}
1 j ?1 1 1j 1 2 j ?1 2 2

? max{6 ? 0.5 ? 6 ? 0.5 ? (?3),4 ? 0.8 ? 6 ? 0.2 ? (?3)}

? max{7.5,8.2} ? 8.2
d 2 (1) ? 2

2 f 2 (2) ? max{ q 1 (2) ? ? p 1 j f1 ( j ), q 2 (2) ? ? p 2 j f1 ( j )} 2

2

2

? max{ ?3 ? 0.4 ? 6 ? 0.6 ? (?3),?5 ? 0.7 ? 6 ? 0.3 ? (?3)}

j ?1

j ?1

? max{ ?2.4,?1.7} ? ?1.7
d 2 (2) ? 2

这表明,如果继续生产两个月,第1个月不登广 告,第2个月登广告。 同样可以计算出经3步、4步、…转移时的结果, 将计算结果列于下表中。 利用上述的值迭代法,可算出系统当前处于状态 i,经任意n步转移应采取怎样的最优策略以及所获 得的总报酬期望值。

n(经营时间/月)

1

2

3

4



f n (1)

(目前销路好,n月后停业的 最大总期望报酬) 月后停 业应采取的最优决策) (目前销路差,n月后停业 的最大总期望报酬) 月后停 业应采取的最优决策)

6

8.2

10.22 12.222



d n (1)(目前销路好,若n

1

2

2

2



f n (2)

-3

-1.7

0.23

2.223



d n (2)(目前销路差,若n

1

2

2

2



一般来说,大多数不断运行的系统没有明显的终 点,对于迭代中的 ,如果直到充分大的n才能停 止过程,那么,值迭代法就不是很有效的。对于无 限期的过程或做多次转移后才结束的过程,可以用 一种直接分析的方法——策略迭代法来求解。 马氏决策规划的基本概念于20世纪60年代建立,

几十年来,无论是理论上还是应用方面都有很大进 展。根据其报酬函数和目标函数的不同,建立不同 类型的优化模型,如有限阶段模型、折扣模型、平 均模型、无界报酬模型等。对于这些模型的理论研 究已取得了较好的效果。

另外,马氏决策规划也被成功应用于许多实际问 题,如机器的最优更换、维修问题、质量控制问题、 水库最优调度问题、随机旅行售货点问题、电话网络 中的最优线路问题、最优投资与消费问题等等。


赞助商链接
相关文章:
第4讲 动态规划
第4讲 动态规划_电脑基础知识_IT/计算机_专业资料。计算机算法设计与分析 第4讲 动态规划 我们先来看一个简单的多阶段决策问题。 现有一张地图,各结点代表城市,...
动态规划讲解大全(含例题及答案)
2.动态规划问题中的术语 阶段:把所给求解问题的过程恰当地分成若干个相互联系的阶段,以便于求解,过程不同,阶段 数就可能不同.描述阶段的变量称为阶段变量。在...
数学模型动态规划
动态规划动态规划(dynamic programming)是运筹学的一个重要分支,它是解决多 阶段决策问题的一种有效的数量化方法.动态规划是由美国学者贝尔曼 (R.Bellman)等人所创立...
动态规划 分类
三、用动态规划法解题的一般模式 动态规划所处理的问题是一个多阶段决策问题,一般由初始状态开始,通过对中 间阶段决策的选择,达到结束状态。这些决策形成了一个决策...
动态规划习题
动态规划习题_理学_高等教育_教育专区。数学模型 第七章 动态规划 规划问题的最终目的就是确定各决策变量的取值, 以使目标函数达到极大或极小。 在线 性规划和非...
动态规划(DP)的使用条件
,但从空间复杂度来看,动态规划算法为 O(n2),而搜索 算法为 O(n),搜索算法反而优于动态规划算法。选择动态规划算法是因 为动态规划算法在空间上可以承受,而搜索...
动态规划与静态规划的关系
动态规划与静态规划的关系 动态规划与静态规划(线性和非线性规划等)研究的对象本质上都是在若 干约束条件下的函数极值问题。 两种规划在很多情况下原则上可以相互 ...
动态规划的技巧——阶段的划分和状态的表示
动态规划的技巧——阶段的划分和状态的表示在动态规划的设计过程中, 阶段的划分和状态的表示是非常重要的两步, 这两步会直接影响该问题的计算复杂性, 有时候阶段...
动态规划例1 求解下列整数规划的最优解
动态规划例1 求解下列整数规划的最优解_研究生入学考试_高等教育_教育专区。天大,考研,运筹学,管理科学与工程例1 求解下列整数规划的最优解: max Z ? 4 x1 ...
动态规划的基本思想
算法思想之3动态规划 15页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 动态规划的基本思想 隐藏>> 动态规划的基...
更多相关标签: