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

运筹学动态规划


第7章
重点:

动态规划

(Dynamic Programming)

理解动态规划基本概念、最优化原理和基本方程;

通过资源分配、生产与存储和设备更新等问题,学
习应用动态规划解决多阶段决策问题;

重点掌握动态规划模型结构、逆序算法原理、资源
分配问题、生产与存储问题。

难点为动态规划中状态变量、基本方程等的确定。

? 动态规划是用来解决多阶段决策过程最优 化的一种数量方法。其特点在于,它可以 把一个多阶段决策问题变换为几个相互联 系的单阶段最优化问题,从而一个一个地 去解决。 ? 需指出:动态规划是求解某类问题的一种 方法,是考察问题的一种途径,而不是一 种算法。必须对具体问题进行具体分析, 运用动态规划的原理和方法,划分阶段, 建立相应的模型,然后再去求解。

引例: 图中所示为从A到G的路线网络,图中数字表示 相应线路的长度,如何求出从A到G的最短路线?
C1 8 3 6 3 B2 8 7 C2 C3 C4 6 D1 2 2 D2 1 2 3

1
5 A B1

3
5 3

E1 3 5

F1

4

6

3 8
4

D3 3

5 E2 2 6 F2 E3 6

G 3

1

2

3

4

(穷举法48条路线)

5

6

13 13 1 B1 3 6 3 C1 10 8 C2 6 3

7 D1 2

7 E1 3 4 5 F1 5 5 E2 2 6 F2 3 E3 6 3 9 5 6

5 A 18

B2 7 16 6

8

9 5 C3 3 3 8 C4 4

2 6 1 D2 2 3 D3 3 8 4

G

12
1 2 3

6 5 5 A 3 1 3 6 8 C1 6 11 D1 2 13 2 1 D2 2 3 D3 3 13 4 13 E1 3 17 5 F1 4 13 5 G E2 2 6 18 F2 3 E3 6 15 15 5 6 8 8 C2 3 10 5 C3 3 3 8 C4 9 1 2 3 4

B1

B2

7

3 6

最短路的特性:

如果已有从起点到终点的一条最短路,那么从 最短路线上中间任何一点出发到终点的路线仍然是 最短路。(证明用反证法)
1
5 B1
C1

6
8

3 C2 3 6 A 5 3 8 C3 3 B2 7 3 8 6 C4 4
1 2 3

2 D1 2

E1 3

5 F1 4 1 E2 5 G D2 2 2 6 F2 3 3 E3 6 D3 3

4

5

6

§1 动态规划的研究对象和引例
动态系统: 包含随时间变化的因素和变量的系统。 动态决策问题: 系统所处的状态和时刻是进行决策的重要因素。 找到不同时刻的最优决策以及整个过程的最优 策略。
决策 状态 状态 决策 状态 决策

1
阶段

2

?

状态 n

全过程的最优

多阶段决策问题的典型例子

1、 生产决策问题
企业在生产过程中,由于需求是随时间变化的, 因此企业为了获得全年的最佳生产效益,就要在整 个生产过程中逐月或逐季度地根据库存和需求决定 生产计划。

2、机器负荷分配问题
高负荷 g=g(u1)

产品的年产量 投入生产的机 器数量

机器的年完好率为a ,0<a<1 某种机器 低负荷 h=h(u2) 年终完好 的机器? 机器的年完好率为b ,0< b<1 假定开始生产时完好的机器数量为s1。要求制定 一个n年计划,在每年开始时,决定如何重新分配完好 的机器在两种不同的负荷下生产的数量,使在n年内产 品的总产量达到最高。

3、线性规划、非线性规划等静态的规划问题也
可以通过适当地引入阶段的概念,应用动态规划方法 加以解决。 不包含时间因素的静态决策问题(一次决策问 题)也可以适当地引入阶段的概念,作为多阶段的 决策问题用动态规划方法来解决。

4、最短路问题(引例):给定一个交通网络图如
前,其中两点之间的数字表示距离(或花费),试求 从A点到G点的最短距离(总费用最小)。

§2 动态规划的基本概念和定义
B1 3 1 3 6 8 7 6 1 2

C1
8 C2

6 D1

2

5 A

3

B2

5 C3 3 3 8 C4 4 3

2 D2 1 2 3 D3 3 4

E1 3 5 F1 4 5 E2 2 6 F2 3 E3 6

G

5

6

1、阶段、阶段变量
把所给问题的过程,适当(按时间和空间)地分 为若干个相互联系的阶段;描述阶段的变量称为阶段 变量,常用 k 表示。

2、状态、状态变量
每个阶段开始所处的自然状态或客观条件,描述 过程的状况, 通常一个阶段有若干个状态。 描述过程状态 的变量称为状态变 量,它可用一个数、 一组数或一向量来 5 B1 描述,常用 sk 表示 A 3 第 k 阶段的状态。

s2=?
1
C1

6
8

3 C2 3 6 5 8 C3 3 B2 7 3 8 6 C4 4
2 3

2 D1 2

E1 3

5 F1 4 1 E2 5 G D2 2 2 6 F2 3 3 E3 6 D3 3

状态允许集合,状态变量的取值允许集合或范围。
1 4 5 6

3、决策、决策变量
某一阶段、某个状态,可以做出不同的决定(选 择),决定下一阶段的状态,这种决定称为决策。 在最优控制中也称为控制。

uk(sk) ? Dk(sk)
6
8

决策变量,描述决策的变量。

uk(sk),表示第 k 阶段当
允许决策集合,
A

1
6

C1

状态为 sk 时的决策变量。 B1 3 5
3

C2 3

2 D1 2

E1 3

D2(B1 )?

常用 Dk(sk) 表示第 k 阶段从状态 sk出发的 允许决策集合。
1

8 B2 7 6

5 C3 3 3 8 C4 4
3

5 F1 4 1 E2 5 G D2 2 2 6 F2 3 3 E3 6 D3 3

2

4

5

6

4、多阶段决策过程
在每个阶段进行决策 ? 控制过程的发展;

其发展是通过一系列的状态转移来实现的;
系统当前的 状态和决策 系统过去的历 史状态和决策

状态转移方程的一般形式
5 B1

1

C1

6
8

s2=T1(s1, u1)

s1=A,u1 s , u s3=T2(s1, u1,=B1,2) 2 ? ? s2=? sk+1=Tk(s1, u1, s2, u2 ,?, sk, uk)
1

3 C2 3 6 A 5 3 8 C3 3 B2 7 3 8 6 C4 4
2 3

2 D1 2

E1 3

5 F1 4 1 E2 5 G D2 2 2 6 F2 3 3 E3 6 D3 3

4

5

6

图示如下: u1 s1 1 s2 2 u2 s3 ? sk

uk
k

sk+1

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

5、无后效性或马尔可夫性
如果某阶段状态给定后,则在这个阶段以后过程 的发展不受这个阶段以前各阶段状态的影响;过程的 过去历史只能通过当前的状态去影响它未来的发展。

构造动态规划模型时,要充分注意状态变量是否 满足无后效性的要求;
状态转移方程?

状态具有无后效性的多阶段决策过程的状态转 移方程如下: s2=T1(s1, u1) s3=T2(s2, u2) ?? sk+1=Tk(sk, uk)

6、策略
按顺序排列的决策组成的集合。 由过程的第k ?终止状态为止的过程,称为问题 的后部子过程(k 子过程)。 由每段的决策按顺序排列组成的决策函数序列称 为 k 子过程策略。简称 子策略,记为pk,n(sk),5
B1

1

C1

6
8

3 C2 3 6 A 5 即, 3 8 C3 3 B2 7 3 Pk,n(sk)={uk(sk),uk+1(sk+1), 8 6 ?,un(sn)} C4 4
1 2 3

2 D1 2

E1 3

5 F1 4 1 E2 5 G D2 2 2 6 F2 3 3 E3 6 D3 3

4

5

6

当 k =1时,此决策函数序列成为全过程的一个策 略,简称策略,记为p1,n (s1),即
P1,n(s1)={u1(s1), u2(s2), … , un(sn)} 允许策略集合,可供选择的策略范围,用 P 表示。

最优策略,达到最优效果的策略。
1
5 B1
C1

6
8

3 C2 3 6 A 5 3 8 C3 3 B2 7 3 8 6 C4 4
1 2 3

2 D1 2

E1 3

5 F1 4 1 E2 5 G D2 2 2 6 F2 3 3 E3 6 D3 3

4

5

6

7、指标函数和最优值函数
指标函数,用来衡量所实现过程优劣的一种数量
指标,它是定义在全过程或所有后部子过程上确定

的数量函数。用 Vk, n 表示。
Vk, n= Vk, n (sk, uk , sk+1, uk+1 , ?, sn+1), k =1,2, ?,n 动态规划模型 的指标函数,应具 有可分离性,并满 足递推关系。 uk,Vk+1, n 的函数。
1
5 B1
C1

6
8

3 C2 3 6 A 5 3 8 C3 3 B2 7 3 8 6 即Vk, n可以表示为 sk, C4 4
1 2 3

2 D1 2

E1 3

5 F1 4 1 E2 5 G D2 2 2 6 F2 3 3 E3 6 D3 3

4

5

6

常见的指标函数的形式是:

? 过程和它的任一子过程的指标是它所包含的各阶
段的指标和。即

Vk ,n ( sk , uk ,?, sn ?1 ) ? ? v j ( s j , u j )
j ?k

n

无后效性 的结果

3 C2 3 Vk, n(sk ,uk ,…, sn+1) 6 A 5 3 = vk(sk ,uk)+ Vk+1, n 8 C3 3 B2 7 3 8 6 V5, 6= V5, 6 (s5, u5, V6, 6 ) C4 4 5 B1

其中V(sj, uj ) 表示第 j 阶段的阶段指标。这时上 1 C1 6 2 式可写成 E1 D1
8 5 F1 4 1 E2 5 G D2 2 2 6 F2 3 3 E3 6 D3 3 2 3

=d5(s5,u5)+ V6, 6
1 2 3 4 5 6

? 过程和它的任意子过程的指标是它所包含的 各阶段的指标的乘积。即

Vk ,n ( sk , uk ,?, sn ?1 ) ? ? v j ( s j , u j )
可改写成
j ?k

n

Vk, n(sk ,uk ,…, sn+1) = vk(sk ,uk) ?Vk+1, n(sk+1, uk+1, …, sn+1)

最优值函数: 指标函数的最优值,记为 fk (sk)。表示从第 k 阶 段的状态 sk 到第 n 阶段的终止状态的采取最优策略 所得到的指标函数值。即

f k (sk ) ? opt Vk ,n (sk , uk ,?, sn?1 )
{uk ,?,un }

全过程的最优值函数记为

f1 (s1)

f6 (F1)=4 f6 (s6)=? f6 (F2)=3
1
5 B1
C1

6
8

f5 (E1)=?

3 C2 3 6 A 5 3 8 C3 3 B2 7 3 8 6 C4 4
1 2 3

2 D1 2

E1 3

5 F1 4 1 E2 5 G D2 2 2 6 F2 3 3 E3 6 D3 3

4

5

6

多阶段决策过程的数学模型:(具有无后效性,以和 式为例)
{u1, u2,…,un}

opt

Vk, n(sk , uk , ?, sn+1)= ?vj(sj, uj)
j=k

n

sk+1=Tk(sk, uk)
s.t. sk?Sk uk?Dk k=1,2, …,n

小结:

无后效性

动态规划本质上是多阶段决策过程; 概念:阶段变量 k﹑状态变量 sk﹑决策变量 uk ; 方程:状态转移方程 指标:

sk ?1 ? Tk ( sk , uk )

效益

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

fk (sk)=

{uk , …, un}

opt Vk, n(sk , uk ,…, sn+1)

解多阶段决策过程问题,应求出:
最优策略:即最优决策序列 {u1* , u2* , … , un*} 最优轨线:即执行最优策略时的状态序列 {s1* , s2* , … , sn*} 最优目标函数值: f1(s1)=?

§3

动态规划的基本思想和基本方程

最短路的特性:

如果已有从起点到终点的一条最短路,那么从 最短路线上中间任何一点出发到终点的路线仍然是 最短路。(证明用反证法)
1
5 B1
C1

6
8

3 C2 3 6 A 5 3 8 C3 3 B2 7 3 8 6 C4 4
1 2 3

2 D1 2

E1 3

5 F1 4 1 E2 5 G D2 2 2 6 F2 3 3 E3 6 D3 3

4

(穷举法48条路线)
5 6

k=6, 2 8 D1 2 E1 3 F1 ? G,f6(F1)=4 5 B1 3 5 F1 4 C2 3 6 F2 ? G,f6(F2)=3 A 1 E2 5 5 D2 G 3 2 8 C3 2 3 6 F2 3 B2 7 3 3 E3 6 k=5,出发点有 E1, E2, E3 D3 8 6 3 C4 4 u5(E1)=F1 3?4 ?d ( E , F ) ? f ( F ) ?
1
C1

6

? ? 6 1 f 5 ( E1 ) ? min ? 5 1 1 ? min ? ? ??7 ?5 ? 3? ?d 5 ( E1 , F2 ) ? f 6 ( F2 )?

E1?F1?G u5(E2)=F2 E2?F2?G u5(E3)=F2

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

E3?F2?G

2 8 D1 2 E1 3 5 B1 3 5 F1 4 C2 3 6 A 1 E2 5 5 D2 G 3 2 8 C3 2 3 6 F2 3 B2 7 3 3 E3 6 D3 8 k=2 6 3 C4 4 k=3

1

C1

6

k=4 f4(D1)=7 u4(D1)=E2 f4(D2)=6 u4(D2)=E2

f4(D3)=8 u4(D3)=E2

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

f2(B1)=13 u2(B1)=C2 f2(B2)=10 u2(B2)=C3

f3(C3)=9

u3(C3)=D2

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

k=1 f1(A) = min d1(A,B1)+ f2(B1) d1(A,B2)+ f2(B2) = min 5+13 3+16 = 18 u1(A)=B1

最优决策函数序列{uk }: u1(A)=B1, u2(B1)=C2, u3(C2)=D1, u4(D1)=E2, u5(E2)=F2, u6(F2)=G 最短路线为 A?B1?C2?D1?E2?F2?G
1 5 B1 3 B2 C1 8 C2 3 5 C3 3 3 8 C4 4 6 D1 2 2 1 D2 2 3 D3 3 E1 3 5

最优策略

A

3 6 8 7

F1 4 G F2 3

6

5 E2 2 6 E3

6

求解的各个阶段,我们利用了k 阶段与 k+1 阶 段之间的递推关系: fk ( sk ) = min {dk (sk , uk ( sk )) + fk+1(sk+1 )}
uk ? Dk (sk)

f 7(s7) = 0

k = 6, 5, 4, 3, 2, 1

动态规划基本方程
fk ( sk ) = opt {vk (sk , uk ( sk )) + fk+1(sk+1 )}
uk ? Dk (sk)

fn+1 ( sn+1) = 0 (边界条件)

动态规划的理论基础
最优性原理(R. Bellman ):
“一个过程的最优策略具有这样的性质:即无 论其初始状态及初始决策如何,对于先前决策所形 成的状态而言,余下的诸决策仍构成最优策略。” 含义 最优策略的任何一部分子策略,也是它相应初 始状态的最优策略。每个最优策略只能由最优子策 略构成。

动态规划的最优性定理:设阶段数为 n 的多阶段决 策过程,其阶段编号为k=0,1,...,n-1。允许策略 p*0, n-1= ( u*0, u*1, …, u*n-1 ) 是最优策略的充要条件是: 对任意一个 k, 0 < k < n-1和 s0 ? S0,有

~ ? T (s , u ) sk k ?1 k ?1 k ?1

V

0 , n ?1

( s0 , p ?

* 0 , n ?1

)?

opt
p0 , k ?1?P 0 , k ?1( s0 )

? V 0,k ?1 ( s0 , p0,k ?1)
k , n ?1

pk , n ?1`?P k , n ?1( ~ k ) s

opt

(~k , p V k , n ?1 s

)

?

p 0 , n ?1 ? ( p 0 , k ? 1 , p k , n ?1 )

证明:必要性

V

0, n ?1

( s0 , p

*

0 , n ?1

)?

opt
p0 ,n?1?P0 ,n?1 ( s0 )

V0,n?1 ( s0 , p0,n?1 ) opt [V0,k ?1 ( s0 , p
0 , k ?1

? ?

opt
p0 ,k ?1?P0 ,k ?1( s0 ) opt
p0 ,k ?1?P0 ,k ?1 ( s0 )

{

pk ,n?1?Pk ,n?1 ( ~k ) s

) ? Vk ,n?1 (~k , pk ,n ?1 )]} s (~ k , p k , n ?1 s )}

{V0,k ?1 ( s0 , p0,k ?1 ) ?

pk ,n?1`?Pk ,n?1( s k )

opt V ~

k , n ?1

充分性:设p0,n-1=(p0,k-1,pk,n-1)为任一策略,sk为由(s0, p0,k-1)所确定的k阶段的起始状态,则有(以最大化 为例)

Vk ,n?1 (~k , pk ,n?1 ) ? s

opt
pk , n ?1?Pk , n ?1 ( sk )

Vk ,n?1 (~k , pk ,n?1 ) s

( s0 , p 0,n ?1 ) ? V0,k ?1 ( s0 , p0,k ?1) ? Vk ,n ?1 (~k , pk ,n ?1 ) s V 0,n?1 ? V0,k ?1 ( s0 , p0,k ?1 ) ? ? ? p k , n ?1`?P k , n ?1( ~ k ) s

opt

(~ k , p k ,n ?1) V k ,n?1 s {V0,k ?1 ( s0 , p0,k ?1 )

p 0, k ?1`?P 0, k ?1( ~ 0 ) s p k , n ?1`?P k , n ?1( ~ k ) s

opt

opt

V k ,n?1 (~ k , pk ,n?1)} s

* ? V0,n ?1 ( s0 , p0,n ?1 )

推论:若允许策略 p*0, n-1 是最优策略,则对任意 的 k ,0< k < n-1,它的子策略 p*k, n-1 对于以 s*k = Tk-1 (s*k-1, u*k-1 )为起点的 k 到 n-1子过程来说,必是 最优策略。(注意:k 段状态 s*k ,是由 s0 和 p*0, k-1 所确定的)
最优性原理

动态规划(逆序法)小结:

? 将问题的过程划分成恰当的阶段; ? 选择状态变量 sk , 既能描述过程的变化又满足无后效 性; ? 确定决策变量 uk 及每一阶段的允许决策集合Dk( sk ); ? 正确写出状态转移方程; ? 正确写出指标函数 Vk,n 的关系,它应满足下面三个性 质: 1.是定义在全过程和所有后部子过程上的数量函数; 2.要具有可分离性,并满足递推关系。即 Vk, n (sk , uk , ?, sn+1) = ? k [sk , uk ,Vk+1, n (sk+1, uk+1 , ?, sn+1)]

3.函数 ?k(sk,uk,Vk+1, n)对于变量 Vk+1, n 要 严格单调求

? 解时从边界条件开始,逆(或顺)过程行进方向, 逐段递推寻优。 ? 每段决策的选取都是从全局考虑的,与该段的最优 选择答案一般是不同的。
? 在求整个问题的最优策略时,由于初始状态是已知 的,每段的决策都是该段状态的函数,故最优策略 所经过的各段状态便可逐次变换得到,从而确定了 最优路线。

§4 动态规划与静态规划
例1 某公司有资金10万元,若投资于项目i(i=1, 2, 3) 的投资额为xi时,其效益分别为

g1 ( x1 ) ? 4 x1 , g 2 ( x2 ) ? 9 x2 , g 3 ( x3 ) ?
问如何分配投资数额才能使总效益最大? 解:可列出静态规划问题的模型如下

2 2 x3

max Z ? 4 x1 ? 9 x2 ?

2 2 x3

? x1 ? x2 ? x3 ? 10 s.t. ? ? xi ? 0, (i ? 1,2,3)

? 分阶段: 分三个阶段,即k=3,2,1。 ? 确定决策变量: 通常可以取静态规划中的变量为决策变量。
? 确定状态变量: 每一阶段可使用的资金数为状态变量sk。 ? 状态转移方程
s1 ? 10, s2 ? s1 ? x3 , s3 ? s2 ? x2 0 ? x3 ? s1 , 0 ? x2 ? s2 , 0 ? x1 ? s3

?
?

指标函数 Vk ,3 ? ? g i ( xi )
i ?k

3

基本方程

? f k (sk ) ? max {g k ( xk ) ? f k ?1 (sk ?1 )} ? 0? xk ? sk ? ? f 4 (s4 ) ? 0 ?
当阶段 k =3 时,有

k ? 3, 2,1

f3 (s3 ) ? max{4 x1}
0? x1 ? s3

最优决策为 x ? s3 , 最优目标函数
* 1

f3 (s3 ) ? 4s3

当阶段k=2时,有
f 2 ( s2 ) ? max {9 x2 ? f3 ( s3 )}
0? x2 ? s2 0? x2 ? s2 0? x2 ? s2

2阶导数>0

? max {9 x2 ? 4s3} ? max {9 x2 ? 4( s2 ? x2 )}

最优决策为 x ? s2 ,
* 2

最优目标函数 f 2 ( s2 ) ? 9s2
3 1

当阶段k=1时,有 f1 ( s1 ) ? 0max{2 x32 ? f 2 ( s2 )} ? x ?s
2 ? max{2 x3 ? 9( s1 ? x3 )} 0 ? x3 ? s1

是凸函数,最大值点只能在[0,s1]的端点上取得,即
2 f1 ( s1 ) ? max{2 x3 ? 9(10 ? x3 )} ? 200 (最优决策) x3 ?10 2 f1 ( s1 ) ? max{2 x3 ? 9(10 ? x3 )} ? 90 x3 ? 0

所以

* * x2 ? 0, s3 ? s2 ? x2 ? 10 * x3 ? s3 ? 10

最优投资方案是全部资金投于第3个项目,可得 最大收益200万元。 例2 求解下面问题:

max Z ? x1 ? x 2 ? x3 2 ? x1 ? x2 ? x3 ? c (c? 0) s.t. ? ? xi ? 0, i ? 1,2,3
(考虑用动态规划的逆序法进行求解。)

解题思路?

解:
1、将该问题划分为三个阶段,即k=1,2,3 2、确定状态变量并可得状态转移方程:

s3 ? x3 ; x3 ? s3 ;
3、指标函数

s3 ? x2 ? s2 ; 0 ? x2 ? s2 ;
3

s2 ? x1 ? s1 ? c 0 ? x1 ? s1 ? c

2 V1,3 ? ? vi ( si , xi ) ? x1 x2 x3 i ?1

max Z ? x1 ? x 2 ? x3 2 ? x1 ? x2 ? x3 ? c (c? 0) s.t. ? ? xi ? 0, i ? 1,2,3

4、基本方程

最优值函数
k ? 3, 2,1

? f k (sk ) ? max {vk ( sk , xk ) ? f k ?1 ( sk ?1 )} ? 0? xk ? sk ? ? f 4 ( s4 ) ? 1 ?

最优决策

当阶段k=3时,有

f3 (s3 ) ? max ( x3 ) ? s3
x3 ? s3

x ? s3
* 3

当阶段k=2时,有
2 2 f 2 ( s2 ) ? max [ x2 f 3 ( s3 )] ? max [ x2 ( s2 ? x2 )] 0 ? x2 ? s 2 * 0 ? x2 ? s 2

2 4 3 得最优决策 x 2 ? 3 s2 , 最优目标函数 f 2 ( s2 ) ? 27 s2

当阶段k=1时,有
4 f1 ( s1 ) ? max [ x1 f 2 ( s2 )] ? max [ x1 ( s1 ? x1 ) 3 ] 0? x1 ? s1 0? x1 ? s1 27

最优决策

最优目标函数

1 x ? s1 , 4 因此最后可得:
* 1

1 4 f1 ( s1 ) ? s1 64

1 1 4 ? c, f1 ( s1 ) ? c 4 64 2 1 1 3 * x2 ? s 2 ? c, f 2 (s 2 ) ? c 3 2 16 1 1 * x3 ? c, f 3 ( s3 ) ? c 4 4
* x1

动态规划的优缺点 优点:
? 最优解是全局最优解。

? 能得到一系列(包括子过程)的最优解。
? 不需要对系统状态转移方程、阶段效应函数等 的解析性质作任何假设。 缺点: ? 没有统一的标准模型和标准的算法可供使用。

? 应用的局限性,要求满足“无后效性”。
? “维数灾难”问题。

§5

资源分配问题

5.1 资源平行分配问题
设有某种原料,总数量为 a,用于生产 n 种产 品。若分配数量 xi 用于生产第 i 种产品,其收益为 gi ( xi ),问应如何分配,才能使生产 n 种产品的总 收入最大? Max Z = g1(x1)+g2(x2)+ ?+gn(xn) s.t. x 1+ x 2 + ? + x n = a xi ? 0 i = 1, 2, ?, n 静态规 划模型

例3 某公司拟将5台某种设备分配给所属的甲、 乙、丙三个工厂,各工厂若获得这种设备,可以为 公司提供的盈利如表。 问:这五台设备如何分配给各工厂,才能使公 司得到的盈利最大。
工厂 盈利 设备台数







0 1 2 3 4 5

0 3 7 9 12 13

0 5 10 11 11 11

0 4 6 11 12 12

s3的可达状态集合

决策变量 0? ukxkk) ? sk (s

s2的可达状态集合
s1的可达状态集合

3个阶段 如何划分 阶段
甲 乙 丙

状态转移方程?

0 1 2 3 4 5

0 3 7 9 12 13

0 5 10 11 11 11

0 4 6 11 12 12

s1

x1 1

s2

x2 2

s3

x3 3

s4

sk ?1 ? sk ? xk
指标函数 gk(xk)? 基本方程? 甲 乙 丙

0 1 2 3 4 5

0 3 7 9 12 13

0 5 10 11 11 11

0 4 6 11 12 12

解:将问题按工厂分为三个阶段,甲、乙、丙分 别编号为1,2,3。 决策变量xk::
分配给生产第 k 个工厂的设备数量 状态变量 sk : 分配给第 k 个工厂 至第 3 个工厂的设备 数量。 甲 乙 丙

0 1 2 3 4 5

0 3 7 9 12 13

0 5 10 11 11 11

0 4 6 11 12 12

状态转移方程: 基本方程:

sk+1 = sk - xk

xk的取值 范围? Dk ( sk )={ uk|0? xk ? sk }

? f k ?s k ? ? max [ g k ? x k ? ? f k ?1 ( s k ?1 )] ? 0? x k ? s k ? ? f 4 ( s4 ) ? 0 ?
数量为 sk 的原料分 配给第 k 个工厂至 第 3 个工厂所得到 的最大总收益 甲 乙 丙

0 1 2 3 4 5

0 3 7 9 12 13

0 5 10 11 11 11

0 4 6 11 12 12

k =3,s3=0,1,2,3,4,5,0? x3 ? s3
s3 = 0

f 3 (0) ? max { g 3 ( x 3 ) ? f 4 ( s 4 )} x3*(0) = 0 0? x ? s
3

? g 3 ( 0) ? 0

3

s3 = 1

f 3 (1) ? max { g 3 ( x 3 ) ? f 4 ( s 4 )} x *(1) = 1 3 0? x 3 ? s3 ? g 3 ( 0 )? ? max ? ??4 x 3 ? 0 ,1 g 3 (1) 甲 ? ?
0 1 2 3 4 5 0 3 7 9 12 13
乙 丙 0 0 4 4 6 6 11 11 12 12 12 12

s3 = 2

f 3 ( 2) ? 6

x3*(2) = 2

s3 = 3 f 3 ( 3) ? 11
x3*(3) = 3

0 5 10 11 11 11

s3 = 4

f 3 (4) ? 12
x3*(4) = 4

甲 0 1 2 3 4 5 g3(x3) 1 4 2 3 4 5 0 3 7 9 12 13

乙 0 5 10 11 11 11

丙 0 0 4 4 6 6 11 11 12 12 12 12

s3 = 5

f 3 (5) ? 12
x3*(5) = 4,5

结果可写 成表格的 形式:

x3 s3 0 0 0 1 2 3 4 5

f3(s3) x*3 0 4 6 11 12 12 1 1 2 3 4 4,5

6

11

12

12

k =2,s3 = s2 - x2,s2=0,1,2,3,4,5,0? x2 ? s2,有

s2 = 0

f 2 (0) ? max { g 2 ( x 2 ) ? f 3 ( s 3 )} ? g 2 (0) ? 0
0? x 2 ? s2

x2*(0) = 0
x3 s3 0 0 1 2 3 4 5 0 g3(x3) 1 4 2 3 4 f3(s x*3 5 3) 0 1 4 1 6 2 11 3 12 4 12 4,5







6

1 1

1 2

1

0 1 2 3 4 5

0 3 7 9 12 13

0 5 10 11 11 11

0 4 6 11 12 12

s2 = 1

f 2 (1) ? max { g 2 ( x 2 ) ? f 3 ( s 3 )}
0? x 2 ? s2

x2*(1) =1
x3 s3 0 0 1 2 3 4 5 0 g3(x3) 1 4 2 3

? g 2 (0) ? f 3 (1)? ? max ? ? x 2 ? 0 ,1 g (1) ? f ( 0) 3 ? 2 ? ?0 ? 4 ? ? max ? ??5 x 2 ? 0 ,1 5 ? 0 ? ?
f3(s x*3 5 3) 0 1 4 1 6 2 11 3 12 4 12 4,5







4

6

1 1

1 2

1

0 1 2 3 4 5

0 3 7 9 12 13

0 5 10 11 11 11

0 4 6 11 12 12

s2 = 2
f 2 ( 2) ? max { g 2 ( x 2 ) ? f 3 ( s 3 )}
0? x 2 ? s2

? g 2 ( 0 ) ? f 3 ( 2 )? ?0 ? 6 ? ? ? ? ? ? max ? g 2 (1) ? f 3 (1) ? ? max ?5 ? 4 ? ? 10 x 2 ? 0 ,1 , 2 x 2 ? 0 ,1 , 2 ? g ( 2 ) ? f ( 0 )? ?10 ? 0? ? ? 3 ? 2 ? x2*(2) =2
x3 s3 0 0 1 2 3 4 5 0 g3(x3) 1 4 2 3 4 f3(s x*3 5 3) 0 1 4 1 6 2 11 3 12 4 12 4,5







6

1 1

1 2

1

0 1 2 3 4 5

0 3 7 9 12 13

0 5 10 11 11 11

0 4 6 11 12 12

s2 = 3

f 2 ( 3) ? max { g 2 ( x 2 ) ? f 3 ( s 3 )} ? g 2 ( 0) ? ? g 2 (1) ? ? ? max ? x 2 ? 0 ,1 , 2 , 3 g 2 ( 2 ) ? ? ? g 2 ( 3) ? ? ? 14
0? x 2 ? s2

f 3 ( 3 )? ?0 ? 11? ?5 ? 6 ? f 3 ( 2) ? ? ? ? x max , 3 ?10 ? 4? f 3 (1) 2 ? 0 ,1 , 2 ? ? ? f 3 ( 0 )? ?11 ? 0 ? ?

x2*(3) =2
x3 s3 0 0 1 2 3 4 5 0

g3(x3) 1 4 2 3 4

f3(s x*3 5 3) 0 1 4 1 6 2 11 3 12 4 12 4,5







6

1 1

1 2

1

0 1 2 3 4 5

0 3 7 9 12 13

0 5 10 11 11 11

0 4 6 11 12 12

s2 = 4

f 2 (4) ? max { g 2 ( x 2 ) ? f 3 ( s 3 )} ? g 2 ( 0) ? ? g 2 (1) ? ? ? max ? g 2 ( 2) ? x 2 ? 0 ,1 , 2 , 3 , 4 ? g 2 ( 3) ? ? g ( 4) ? ? 2 ? 16
f3(s x*3 5 3) 0 1 4 1 6 2 11 3 12 4 12 4,5
0? x 2 ? s2

f 3 ( 4) ? ?0 ? 12? ?5 ? 11? f 3 ( 3) ? ? ? ? f 3 ( 2)? ? max ?10 ? 6? x 2 ? 0 ,1 , 2 , 3 , 4 ?11 ? 4 ? f 3 (1) ? ?11 ? 0 ? f 3 ( 0) ? ? ? ?

x2*(4) =1,2
x3 s3 0 0 1 2 3 4 5 0 g3(x3) 1 4 2 3







4

6

1 1

1 2

1

0 1 2 3 4 5

0 3 7 9 12 13

0 5 10 11 11 11

0 4 6 11 12 12

s2 = 5

f 2 (4) ? max { g 2 ( x 2 ) ? f 3 ( s 3 )} ? g 2 ( 0) ? ? g 2 (1) ? ? ? g 2 ( 2) ? ? max ? x 2 ? 0 ,1 , 2 , 3 , 4 , 5 g 2 ( 3 ) ? ? ? g 2 ( 4) ? ? g 2 ( 5) ? ? ? 21
3 4 f3(s x*3 5 3) 0 1 4 1 6 2 11 3 12 4 12 4,5
0? x 2 ? s2

x2*(5) =2
x3 s3 0 0 1 2 3 4 5 0

f 3 ( 5) ? f 3 ( 4) ? ? f 3 ( 3 )? ? f 3 ( 2 )? ? f 3 (1) ? f 3 ( 0) ? ?

?0 ? 12 ? ?5 ? 12 ? ?10 ? 11? ? ? max ? ? x 2 ? 0 ,1, 2 , 3 , 4 , 5 11 ? 6 ? ? ?11 ? 4 ? ?11 ? 0 ? ? ?

g3(x3) 1 4 2







6

1 1

1 2

1

0 1 2 3 4 5

0 3 7 9 12 13

0 5 10 11 11 11

0 4 6 11 12 12

结果列于下表:
x2 s2 0 1 2 3 4 5 0 0+0 0+4 0+6 0+11 0+12 0+12 1 5+0 5+4 5+6 5+11 5+12 g2(x2)+f3(s2-x2) 2 3 4 5 f2(s2) 0 5 10 14 16 21 x*2 0 1 2 2 1,2 2

10+0 10+4 11+0 10+6 11+4 11+0 10+1 11+6 11+4 11+0 1

k =1时, s2 = s1 - x1, s1 = 5, 0? x1 ? s1,有

f 1 ( s1 ) ? max { g1 ( x1 ) ? f 2 ( s 2 )} ? g 1 ( 0) ? ? g1 (1) ? ? g ( 2) ? ? 1 ? max ? x1 ? , 0 ,1, 2 , 3 , 4 , 5 g 1 ( 3) ? ? ? g 1 ( 4) ? x1*(5) =0,2 ? g 1 ( 5) ? ?
x2
s2 0 1 2 3 4 5 f2(s2) 0 5 10 14 16 21 x*2 0 1 2 2 1,2 2
0? x1 ? s1

f 2 ( 5) ? ?0 ? 21? ?3 ? 16? f 2 ( 4) ? ?7 ? 14? f 2 ( 3 )? ? ? ? ? ? max ?9 ? 10? ? 21 f 2 ( 2) ? ? ? f 2 (1) ? ?12 ? 5 ? ?13 ? 0 ? f 2 ( 0) ? ? ? ?







0 1 2 3 4 5

0 3 7 9 12 13

0 5 10 11 11 11

0 4 6 11 12 12

结果可写成表格的形式
x1 s1 5 0 1 g1(x1)+f2(s1-x1) 2 3 4 5 0+21 3+16 7+14 9+10 12+5 13+0 f1(s1) 21 x*1 0,2

最优分配方案一:由 x1* = 0,根据 s2 = s1- x1* = 5- 0 最优分配方案? = 5,查表知 x2* = 2,由s3 = s2- x2* = 5 - 2 = 3,故 x3* = s3 =3。即得甲工厂分配0台,乙工厂分配2台,丙 工厂分配3台。

最优分配方案二:由 x1* = 2,根据 s2 = s1 - x1* = 5- 2 = 3,查表知 x2*= 2,由 s3 = s2 - x2*= 3 - 2 =1, 故 x3* = s3 =1。即得甲工厂分配2台,乙工厂分配2台, 丙工厂分配1台。 以上两个分配方案所得到的总盈利均为21万元。 问题: 如果原设备台数是4台,求最优分配方案? 如果原设备台数是3台,求最优分配方案?

5.2 资源连续分配问题
第一年 资源数量 s1 A种生产 数量u1投入 收益g (u1) 年终资源回收率a B种生产 数量s1-u1 收益h (s1-u1) 年终资源回收率b A种生产 数量u2投入;收益g(u2); 年终资源回收率a B种生产 数量s2-u2;收益h(s2-u2); 年终资源回收率b

第二年

资源数量 s2=au1+b(s1-u1)
到n年

如此进行 n 年,如何确定投入 A 的资源量 u1、…、un,使总收入最大? 此问题的静态规划问题模型为:

max Z ? ? { g ( ui ) ? h( s i ? ui )} ? s 2 ? au1 ? b( s1 ? u1 ) ? s 3 ? au2 ? b( s 2 ? u2 ) ? s .t .?? ? ? ? s n ?1 ? aun ? b( s n ? un ) ?0 ? u ? s , i ? 1,2, ? , n i i ?
i ?1

n

例4

机器负荷分配问题

投入生产的机 器数量

高负荷: 产量函数 g = 8u1, 机 年完好率为 a=0.7, 器 低负荷: 产量函数 h = 5y, 年完好率为 b=0.9。

假定开始生产时完好机器的数量为1000台。
试问每年如何安排机器在高低两种负荷下的生 产,可使5年内生产的产品总产量最高?

分析:

阶段? 第 k 年初拥有的完 好机器台数 第 k 年高负荷下投 入的机器数

状态变量 sk 决策变量 uk 0 ? uk ? sk sk – uk

第 k 年低负荷下投 入的机器数

状态转移方程
sk+1 = auk+ b(sk - uk) = 0.7uk+ 0.9 (sk - uk)

递推方程? fk(sk) =max {8uk+5(sk-uk)+fk+1(0.7uk+0.9(sk-uk))}
0 ? uk ? sk

f6(s6) = 0 k = 5, 4, 3, 2, 1 指标函数 第k年度产量为 v k ( s k , uk ) ? 8uk ? 5( s k ? uk ) sk+1

V1, 5 ? ? v k ( s k , uk )
k ?1

5

阶段指标

解:设阶段序数 k 表示年度,sk为第 k 年初拥有的 完好机器台数,第 k 年度高负荷下投入的机器数为 uk台。 则状态转移方程为 sk+1 = 0.7uk+ 0.9 (sk - uk) 基本方程为 k = 1, 2, …, 5

fk(sk) =max {8uk+5(sk-uk)+fk+1(0.7uk+0.9(sk-uk))}
0 ? u k ? sk

f6(s6) = 0

k = 5, 4, 3, 2, 1

k=5

f 5 ( s5 ) ? max {8u5 ? 5( s5 ? u5 ) ? f 6 ( s6 )}
0 ? u 5 ? s5 0 ? u 5 ? s5

? max {3u5 ? 5s5 }
u*5 = s5 k=4 f5(s5) = 8s5
0?u 4 ? s 4

0

f 4 ( s4 ) ? max {8u4 ? 5( s4 ? u4 ) ? f 6 (0.7u4 ? 0.9( s4 ? u4 ))} ? max {13.6u4 ? 12.2( s4 ? u4 )}
0?u 4 ? s 4 0?u 4 ? s 4

? max {1.4u4 ? 12.2s4 }
u*4 = s4 f4(s4) = 13.6s4

依次类推可得,

u ? s3 u ?0 u ?0
* 3 * 2 * 1

f 3 ( s 3 ) ? 17.5 s 3 f 2 ( s 2 ) ? 20.8 s 2 f 1 ( s1 ) ? 23.7 s1

因此最优策略为
* * * * * u1 ? 0, u2 ? 0, u3 ? s 3 , u4 ? s 4 , u5 ? s 5

最高产量为23700。 练习:1. 每年年初的完好机器数。 2. 如规定在第五年结束时完好机器数为500台, 该如何安排生产?

k=5

s6 ? 0.7u5 ? 0.9( s5 ? u5 ) ? 500 u5 ? (0.9s5 ? 500 ) / 0.2 ? 4.5s5 ? 2500

f 5 ( s5 ) ? max {8u5 ? 5( s5 ? u5 ) ? f 6 ( s6 )}
0 ? u 5 ? s5 0 ? u 5 ? s5

? max {3u5 ? 5s5 }
u *5 ? 4.5s5 ? 2500 f 5 ( s5 ) ? 3u5 ? 5s5 ? 17.5s5 ? 7500

k = 4 u *4 ? 0
f5 ( s5 ) ? 20.75s4 ? 0.5u4 ? 7500 ? 20.75s4 ? 7500

其他略

§6

生产与存贮问题

一个生产部门,如何在已知生产成本、库存费用和 各阶段市场需求条件下,决定各阶段产量,使计划内的 费用总和为最小的问题。 生产周期分为 n 个阶段,已知 最初库存量: x1 阶段市场的需求:dk

生产的固定成本:K
阶段生产能力为B

单位产品的消耗费用:L

单位产品的阶段库存费用:h 仓库容量:M 问如何安排各阶段产量,使计划周期内的费用总和 最小。

状态变量 xk:

阶段 k 的初始库存量,x1已知,xn+1 = 0 不能超过库存容量M,xk

?M

不能超过阶段 k 至阶段 n 的需求总量 xk ? dk+ dk+1+?+ dn,k =1, 2, ?, n
0 ? xk ? min {M, dk+ dk+1+?+ dn}, (k =1, 2, ?, n)

决策变量 uk: 阶段 k 的产量 不超过生产能力

xk ? B

不超过 k?n 阶段的总需求减去第 k 阶段初的 库存量, uk ? dk+ dk+1+?+ dn-xk 不小于该阶段的需求和库存量之差,

d k ? xk ? uk
d k -x k ? u k ? min{B,d k + d k + 1 +?+ d n -x k }

状态转移方程

xk ?1 ? xk ? u k ? d k
阶段效益
为阶段生产费用和库存费用之和,即

g k ( xk , uk ) ? K ? Luk ? h( xk ? uk ? d k )
阶段 k 的生产费用 k 阶段末的库存费用

动态规划基本方程

f k ( xk ) ? min {K ? Luk ? h( xk ? uk ? d k ) ? f k ?1 ( xk ?1 )}
uk ?Dk ( xk )

fn+1(xn+1)= 0,k = 1, 2, ?, n

例5 已知 n = 3,K = 8,L = 2,h = 2,x1 = 1,M = 4, x4 = 0,B = 6,d1 = 3,d2 = 4,d3 = 3,求解生产与库存 问题。 解:递推方程

f k ( xk ) ? min {K ? Luk ? h( xk ? uk ? d k ) ? f k ?1 ( xk ?1 )}
uk ?Dk ( xk )

f 4 ( x4 ) = 0,k = 1, 2, 3
当 k ? 3 时 f 3 ?x3 ? ? 仓库容量4

min

3 ? x3 ? u 3 ? m in 6,3? x3

?

?

?8 ? 2u3?

=8+2(3-x3)=14-2x3

dk-xk ? uk ? min{B,dk+ dk+1+?+ dn-xk}
n ? ? 0 ? x3 ? min ?M , ? d i ? ? min i ?k ? ?

?M , d 3 ? ? 3

x3:0~3 若 x3 = 0, 若 x3 = 1, 若 x3 = 2,

f3(x3)= 14-2x3 则 f3(0) =14 则 f3 (1) = 12 则 f3 (2) = 10

u3 =3-x3 u*3 (0) = 3 u*3 (1) = 2 u*3 (2) = 1

若 x3 = 3,
u3 x3 0 1 2 3 8 0

则 f3 (3) = 8
1 2 3 14 12 10

u*3 (0) = 0
f3(x3) 14 12 10 8 u*3(x3) 3 2 1 0

x ? x k u u? d2 x3k ?1 ? 2x? ? 2 k ? d k
容量4

4+3

0 ? x2 ? min{M,d2+ d3} = m i n { 4 , 7 } = 4
4-x 2 ? u 2 ? min{B,d 2 + d 3 -x 2 }=min{6,7-x 2 } uk ? dk-xk f2 (x2 )= min {8+2u2+2(x2 +u2-4)+ f3 (x2 + u2-4)}

4-x2 ? u2 ? min{6,7-x2}

x2 = 0

f 2 (0) ? min {8 ? 2u 2 ? 2(u 2 ? 4) ? f 3 (u 2 ? 4)}
u 2 ? 4 , 5, 6

?16 ? 0 ? 14 ? ?18 ? 2 ? 12 ? ? 30 ? min ? ? ?20 ? 4 ? 10 ? ? ?

u*2 (0) = 4

4-x2 ? u2 ? min{6,7-x2}

x2 = 1

f 2 (1) ? min {8 ? 2u 2 ? 2(u 2 ? 3) ? f 3 (u 2 ? 3)}
u 2 ? 3, 4 , 5 , 6

?14 ? 0 ? 14 ? ?16 ? 2 ? 12 ? ? ? 28 ? min ? ?28 ? 4 ? 10 ? ? ? ?20 ? 6 ? 8 ?

u*2 (1) = 3

x2 = 2

f 2 (2) ? min {8 ? 2u2 ? 2(u2 ? 2) ? f 3 (u2 ? 2)}
u 2 ? 2 , 3, 4 , 5

?12 ? 0 ? 14 ? ?14 ? 2 ? 12 ? ? ? 26 ? min ? ?16 ? 4 ? 10 ? ? ? 18 ? 6 ? 8 ? ?

u*2 (2) = 2

4-x2 ? u2 ? min{6,7-x2}

x2 = 3

f 2 (3) ? min {8 ? 2u 2 ? 2(u 2 ? 1) ? f 3 (u 2 ? 1)}
u 2 ?1, 2 , 3, 4

?10 ? 0 ? 14 ? u*2 (3) = 1 ?12 ? 2 ? 12 ? ? ? 24 ? min ? ?14 ? 4 ? 10 ? ? ? ?16 ? 6 ? 8 ?

x2 = 4

f 2 (4) ? min {8 ? 2u2 ? 2u2 ? f 3 (u2 )}
u 2 ? 0 ,1, 2 , 3

结果见下表:
u2 x2 0 1 2 3 4 0 1

?8 ? 0 ? 14 ? ?10 ? 2 ? 12 ? ? ? 22 ? min ? ?12 ? 4 ? 10 ? ? ? ?14 ? 6 ? 8 ? 4-x
2 3 4 5

u*2(4)=0 ? u2 ? min{6,7-x2}
6 f2(x2) u*2(x2) 4 3 2 1 0

2

16+0+14 18+2+12 20+4+10 30 14+0+14 16+2+12 18+4+10 20+6+8 12+0+14 14+2+12 16+4+10 18+6+8 10+0+14 12+2+12 14+4+10 16+6+8 8+0+14 10+2+12 12+4+10 14+6+8 28 26 24 22

k =1

x1 =1

x2= x1+ u1-d1=1+ u1-3= u1- 2 2?u1?6

f1 (1) ? ?

u1 ? 2 , 3, 4 , 5 , 6

min {8 ? 2u1 ? 2( x1 ? u1 ? d1 ) ? f 2 ( x2 )} min {8 ? 2u1 ? 2(u1 ? 2) ? f 2 (u2 ? 2)}

u1 ? 2 , 3, 4 , 5, 6

?12 ? 0 ? 30 ? ?14 ? 2 ? 28 ? ? ? ? min ?16 ? 4 ? 26 ? ? 42 ? ? ?18 ? 6 ? 24 ? ?20 ? 8 ? 22 ? f2=30 ? ?
u1 x1 1 2 3 4 5

u*1 (1) = 2

6

f1(x1) u*1(x1) 42 2

12+0+30 14+2+28 16+4+26 18+6+24 20+8+22

u2 x2 0 1 2 3 4

0

1

2

3

4

5

f3=14 (x ) 6 f
2 2

u*2(x2) 4 3 2 1 0

16+0+14 18+2+12 20+4+10 30 14+0+14 16+2+12 18+4+10 20+6+8 12+0+14 14+2+12 16+4+10 18+6+8 10+0+14 12+2+12 14+4+10 16+6+8 8+0+14 10+2+12 12+4+10 14+6+8 28 26 24 22

u3 x3 0 1 2 3

0

1

2

3 14

f 3(x3) 14 12 10 8

u*3(x3) 3 2 1 0

12 10 8

最优决策为 u*1 (1) = 2,u*2 (0) = 4, u*3 (0) = 3 最优路线为 (状态变量)
x2=u1-2=0

{1,0,0,0}

x 3 =x 2 +u 2 -d 2 =0+4-4=0

最优目标函数值为42。

? 2维生产与经营问题
例6:某商店在未来的 4 个月里,准备利用它的一个仓 库专门经销某种产品,仓库最大容量为1000。假定该 商店每月只能出卖仓库现有的货。当商店在某月订货 时,下月初才能到货。预测该商店未来四个月的买卖 价格如表,假设商店在 1 月开始经销时,仓库储有该 购买单价 销售单价 商品 500 。求若不计库 月份(k) (ck) (pk) 存费用,该商店应如何 1 10 12 制定 1月至 4 月的订货 2 9 8 与销售计划,使预期获 3 11 13 利最大?
4 15 17

§7

设备更新问题

设备更新问题提法如下(以一台机器为例): n为设备计划使用年数。 Ik(t) 为第k年(阶段)机器役龄为t年的一台机器 运行(在使用一年)所得的收入。 Ok(t) 为第k年机器役龄为t年的一台机器运行(再 使用一年)时所需运行的费用(或维修费用) 。 Ck(t) 为第k年机器役龄为t年的一台机器更新时所 需的净费用(处理一台役龄为t的旧设备,买进一台新 设备的更新净费用)。

?为折扣因子,表示一年以后的收入是上一年的? 单位。
要求在n年内的每年年初作出决策,是继续使用旧 设备还是更换一台新的,使n年内总效益最大?

建立动态规划模型如下:
? 阶段k(k=1,2,…,n)表示计划使用该设备的 年限数。

? 状态变量sk:第k年初,设备已使用过的年数,即 役龄。
? 决策变量xk:是第k年初更新,还是保留使用旧设 备,分别用R ,K表示。

? 状态转移方程为:

?sk ? 1 sk ?1 ? ? ?1
? 阶段效益为:

xk ? K xk ? R

? I j ( sk ) ? O j ( sk ) ? v j ( s k , xk ) ? ? ?I j (0) ? O j (0) ? c j ( sk ) ?

xk ? K xk ? R

? 最优指标函数fk(sk):表示第k年初,使用一台已用了 sk年的设备,到第n年末的最大收益。

? 动态规划的基本方程为

? f k ( sk ) ? max {v j ( sk , xk ) ? ?f k ?1 ( sk ?1 )} ? xk ? K or R ? ? f n ?1 ( sn ?1 ) ? 0 ?
实际上
? I k ( sk ) ? Ok ( sk ) ? ? f k ?1 ( sk ?1 ) f k ( sk ) ? max ? ? I k (0) ? Ok (0) ? ck ( sk ) ? ? f k ?1 (1) xk ? K xk ? R

例7:设某台新设备的年效益及年均维修费用、更新 净费用如下表,试确定今后五年内的更新策略,使总 效益最大。(设?=1)

单位:万元 役龄 项目 效益IK(t) 0 5 1 2 3 3.7 5 2 4 5

4.5 4

3 2.5

2. 3 运行费OK(t) 0. 1 1. 5 5 5 更新费CK(t) 0. 1.5 2. 2.5 3 3.5 解:n=5 5 2 x5 ? K ?I 5 (s5 ) ? O5 ( s5 ) k ?5 f 5 ( s5 ) ? max ? ?I 5 (0) ? O5 (0) ? c5 ( s5 ) x5 ? R 状态变量s5可取1,2,3,4

卖掉役龄2年的设 备,买入新设备 的更新费用

x5 ? K ? I 5 (1) ? O5 (1) f 5 (1) ? max ? ? I 5 (0) ? O5 (0) ? c5 (1) x5 ? R ?4.5 ? 1 ? max ? ? 3.5 x5 (1) ? K ?5 ? 0.5 ? 1.5

x5 ? K ?I 5 (2) ? O5 (2) f 5 (2) ? max ? ?I 5 (0) ? O5 (0) ? c5 (2) x5 ? R ?4.5 ? 1.5 ? max ? ? 2.5 x5 (2) ? K ?5 ? 0.5 ? 2.2

x5 ? K ? I 5 (3) ? O5 (3) f 5 (3) ? max ? x5 ? R ? I 5 (0) ? O5 (0) ? c5 (3) ?3.75 ? 2 ? max ? ?2 x5 (3) ? R ?5 ? 0.5 ? 2.5 ? I 5 (4) ? O5 (4) f 5 (4) ? max ? ? I 5 (0) ? O5 (0) ? c5 (4) ?3 ? 2.5 ? max ? ? 1.5 ?5 ? 0.5 ? 3 x5 ? K x5 ? R x5 (4) ? R

k ?4

?I 4 (s4 ) ? O4 (s4 ) ? f 5 (s4 ? 1) f 4 (s4 ) ? max ? ?I 4 (0) ? O4 (0) ? c4 (s4 ) ? f 5 (1)

x4 ? K x4 ? R

状态变量s4可取1,2,3

x4 ? K ? I 4 ( s4 ) ? O4 ( s4 ) ? f 5 ( s4 ? 1) f 4 (1) ? max ? s4 ?1 I (0) ? O (0) ? c ( s ) ? f (1) x4 ? R ? 4 4 4 4 5 ?4.5 ? 1 ? 2.5 ? ? max ? ? ? 6.5 x4 (1) ? R ?5 ? 0.5 ? 1.5 ? 3.5?

x4 ? K ? I 4 ( s4 ) ? O4 ( s4 ) ? f 5 ( s4 ? 1) f 4 (2) ? max ? s4 ? 2 I (0) ? O (0) ? c ( s ) ? f (1) x4 ? R ? 4 4 4 4 5 ?4 ? 1.5 ? 2 ? ? max ? ? ? 5.8 x4 (2) ? R ?5 ? 0.5 ? 2.2 ? 3.5?

x4 ? K ? I 4 ( s4 ) ? O4 ( s4 ) ? f 5 ( s4 ? 1) f 4 (3) ? max ? s4 ?3 I (0) ? O (0) ? c ( s ) ? f (1) x4 ? R ? 4 4 4 4 5 ?3.75 ? 2 ? 1.5 ? ? max ? ? ? 5.5 x4 (3) ? R ?5 ? 0.5 ? 2.5 ? 3.5?

k ?3

?I 3 (s3 ) ? O3 (s3 ) ? f 4 (s3 ? 1) f 3 (s3 ) ? max ? ?I 3 (0) ? O3 (0) ? c3 (s3 ) ? f 4 (1)

x3 ? K x3 ? R

此时s3可取1或2

x3 ? K ?I 3 ( s3 ) ? O3 ( s3 ) ? f 4 ( s3 ? 1) f 3 (1) ? max ? s3 ?1 I (0) ? O (0) ? c ( s ) ? f (1) x3 ? R ?3 3 3 3 4 ?4.5 ? 1 ? 5.8 ? ? max ? x3 (1) ? R ? ? 9.5 ?5 ? 0.5 ? 1.5 ? 6.5?

x3 ? K ? I 3 ( s3 ) ? O3 ( s3 ) ? f 4 ( s3 ? 1) f 3 (2) ? max ? s3 ? 2 I (0) ? O (0) ? c ( s ) ? f (1) x3 ? R ? 3 3 3 3 4 ?4 ? 1.5 ? 5.5 ? ? max ? x3 (2) ? R ? ? 8.8 ?5 ? 0.5 ? 2.2 ? 6.5?
k ?2 ?I 2 (s2 ) ? O2 ( s2 ) ? f 3 (s2 ? 1) f 2 ( s2 ) ? max ? ?I 2 (0) ? O2 (0) ? c2 (s2 ) ? f 3 (1) x2 ? K x2 ? R

由于状态s2只能取1,所以有
x2 ? K ? I 2 ( s2 ) ? O2 ( s2 ) ? f 3 ( s2 ? 1) f 2 (1) ? max ? s2 ?1 I (0) ? O (0) ? c ( s ) ? f (1) x2 ? R ? 2 2 2 2 3 ?4.5 ? 1 ? 8.8 ? ? max ? x2 (1) ? R ? ? 12.5 ?5 ? 0.5 ? 1.5 ? 9.5?

k ?1

?I1 (s1 ) ? O1 (s1 ) ? f 2 (s1 ? 1) f1 (s1 ) ? max ? ?I1 (0) ? O1 (0) ? c1 (s1 ) ? f 2 (1)

x1 ? K x1 ? R

由于状态s1只能取0,所以有

? I1 ( s1 ) ? O1 ( s1 ) ? f 2 ( s1 ? 1) f1 (0) ? max ? s1 ?0 ? I (0) ? O (0) ? c ( s ) ? f (1) 1 1 1 1 2 ?5 ? 0.5 ? 12.5 ? ? max ? ? ? 17 ?5 ? 0.5 ? 0.5 ? 12.5?
寻找最优解,上述过程递推回去。

x1 ? K x1 ? R x1 (0) ? K

当x*1(0)=K,由状态转移方程

?s1 ? 1 s2 ? ? ?1
? s2 ? 1 s3 ? ? ?1

x1 ? K x1 ? R
x2 ? K x2 ? R

s2=1,查f2(1)得x*2=R

s4=1,查f4(1)得x*4=R s5=1,查f5(1)得x*5=K

s3=1,查f3(1)得x*3=R 本例的最优策略是{K,R,R,R,K},即第一 年初购买的设备到第二、三、四年初各更换一次,用 到第五年年末,总效益为17万元。

练习:现有资金5百万元,可对三个项目进行投 资,投资额均为整数(单位为百万元)。其中2#项目 的投资不得超过3百万元,1#和3#项目的投资均不得 超过4百万元,3#项目至少要投资1百万元。每个项目 投资五年后,预计可获得的收益如下表所示。如何投 资可望获得最大收益?请用动态规划方法求解。
投资额项 目 1# 2# 3# 1 0 2 3 4 5

3
0 5

6
10 8

10
12 11

12
- 15


- 18

0 -

4


相关文章:
运筹学动态规划_图文.ppt
运筹学动态规划 - 动态规划(Dynamic Programming) 动态规划
运筹学7动态规划.ppt
运筹学7动态规划_数学_自然科学_专业资料。运筹学7动态规划 第七 章动态规划 主要内容: §7.1 多阶段决策过程的最优化 §7.2 动态规划的基本概念和基本原理 ...
运筹学5(动态规划)_图文.ppt
运筹学5(动态规划) - 第七章 动态规划 7.1 动态规划问题和基本概念 7.2 动态规划的基本原理 7.3 动态规划的应用 引言 动态规划与多阶段决策: 多阶段决策是...
运筹学动态规划习题_图文.ppt
运筹学动态规划习题 - 习题三 一、某工厂购进100台机器,准备生产A、B 两种
运筹学动态规划_图文.ppt
运筹学动态规划 - 动态规划 (Dynamic programming) 动态规
清华大学运筹学课件动态规划_图文.pdf
清华大学运筹学课件动态规划 - 动态规划 主要内容 基本概念 多阶段问题 建模与
运筹学动态规划分析_图文.ppt
运筹学动态规划分析 - Page:1 运动 态筹 规 划学 华东理工大学 工商经
运筹学动态规划.ppt
运筹学动态规划_数学_自然科学_专业资料。第7章重点: 动态规划 (Dynami
运筹学5(动态规划)_图文.ppt
运筹学5(动态规划) - 第七章 动态规划 7.1 动态规划问题和基本概念 7.2 动态规划的基本原理 7.3 动态规划的应用 引言 动态规划与多阶段决策: 多阶段决策是...
运筹学 动态规划应用.ppt
运筹学 动态规划应用_数学_自然科学_专业资料。第七章 动态规划动态规划问题的基
15《运筹学》(第四版)连续动态规划_图文.pdf
15《运筹学》(第四版)连续动态规划_工学_高等教育_教育专区。对应教材为《运筹学》(第四版)清华大学出版社,融合多个版本运筹学课件优点。...
运筹学5(动态规划)_图文.ppt
运筹学5(动态规划) - 第七章 动态规划 7.1 动态规划问题和基本概念 7.2 动态规划的基本原理 7.3 动态规划的应用 引言 动态规划与多阶段决策: 多阶段决策是...
运筹学课件(动态规划)_图文.ppt
运筹学课件(动态规划) - 动态规划 (Dynamic programming) 动态规划的基本思想 最短路径问题 投资分配问题 背包问题 动态规划是用来解决多阶段决策过程最优 化...
运筹学---动态规划_图文.ppt
运筹学---动态规划 - 这是关于运筹学里的动态规划的课件ppt... 运筹学---动态规划_理学_高等教育_教育专区。这是关于运筹学里的动态规划的课件ppt 动态...
运筹学第八章 动态规划_图文.ppt
运筹学第八章 动态规划 - 第八章 动态规划 8.1 8.2 8.3 8.4 动态规划的研究对象和特点 动态规划的基本概念与最优化原理 动态规划的求解与应用 随机动态规划 ...
运筹学动态规划PPT_图文.ppt
运筹学动态规划PPT - 动态规划 (Dynamic programming)
运筹学第10章 动态规划_图文.ppt
运筹学第10章 动态规划 - Page:1 管理运筹学 动态规划 Page:2
运筹学 07 动态规划_图文.ppt
运筹学 07 动态规划 - 1 多阶段决策过程的最优化 ? 概述 ? 多阶段决策过程及其最优化 ? 多阶段决策过程举例 ? 动态规划求解的多阶段决策问题的特点 ? 动态...
运筹学04_动态规划(2).ppt
48页 免费 2.运筹学 动态规划解法 29页 免费如要投诉违规内容,请到百度文
运筹学中excel的运用(用excel解决线性规划、动态规划、....pdf
运筹学中excel的运用(用excel解决线性规划、动态规划、排队论等问题) - 1 . 线性规划 2 . 动态规划 3 . 图与网络分析 4 . 决策分析 ...
更多相关文章: