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

管理运筹学--动态规划


第8章 动态规划 Dynamic Programming

华国伟 北京交通大学物流管理系

内容提要
1.多阶段决策过程及实例 2.动态规划的基本概念和基本方程

3.动态规划的最优性原理和最优性定理
4.动态规划和静态规划的关系 5.动态规划应用举例

重点: 理解动态规划基本概念、最优化原理和基本方程; 通过资源分配、生产与存储和设备更新等问题,学习 应用动态规划解决多阶段决策问题; 重点掌握动态规划模型结构、逆序算法原理、资源

分配问题、生产与存储问题.
难点为动态规划中状态变量、基本方程等的确定.

动态规划产生于20世纪50年代, 美国数学

家贝尔曼(R. Bellman)等人提出.
动态规划是求解某类问题的一种方法,是 考察问题的一种途径,而不是一种算法.必 须对具体问题进行具体分析,运用动态规划 的原理和方法,划分阶段,建立相应的模型, 然后再去求解.

动态规划是用来解决多阶段决策过程最优化
的一种数量方法.其特点在于,它可以把一个 多阶段决策问题变换为几个相互联系的同类 型单阶段最优化问题,从而一个一个地去解 决.

1. 多阶段决策过程及实例

多阶段决策过程(序贯决策过程)
决策 决策 决策

状态
1

状态
2

状态



状态
n

状态

收益

收益

收益

2 多阶段决策问题——举例
(1) 时间阶段 例1 机器负荷分配问题
v1
S1=1000台 1 x1 S2

建模? 求解?
v3
S3 3 x3 S4

v2
2 x2

v4
4 x4 S5

v5
5 x5

其中:xi——各年度不同负荷机器的台数(向量); vi——产量

(2) 空间阶段
图中所示为从A到G的路线网络, 图中数字表示相应 线路的长度, 如何求出从A到G的最短路线?
1
5 A 3 B2 B1 6 8 7 3 C1 8 C2 C3 C4 6 D1 2 2 D2 1 2 3 E1 3 5

3
5 3

6 1 2

3 8
4

D3 3

5 E2 2 6 F2 E3 6

F1

4

G 3

3

4

5

6

(穷举法48条路线)

13 13 1 B1 3 6 B2 16 8 7 C1 10 8 C2

6
3

7 D1 2 2

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

5

A
18

3

6

9 5 C3 3 3 8 C4 4 12 3

6 1 D2 2 3 D3 3 8

G

1

2

5

6

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

3 6

13 2 1 D2 2 3 D3 3 13

1

2

4

5

6

最短路的特性:

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

6

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

8

D1

2 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 动态规划的研究对象和引例
动态系统:

包含随时间变化的因素和变量的系统。 动态决策问题:
系统所处的状态和时刻是进行决策的重要因素. 找到不同时刻的最优决策以及整个过程的最优策略.
决策 状态 状态 决策 状态 决策 状态 n

1
阶段

2

?

全过程的最优

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

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

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

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

某种机器

机器的年完好率为a ,0<a<1 低负荷 h=h(u2) 年终完好 的机器? 机器的年完好率为b ,0< b<1

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

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

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

动态规划的基本概念 1. 阶段 2. 状态 3. 决策 4. 策略 5. 状态转移方程 6. 指标函数和最优值函数

建模

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

C1
8 C2

6 D1

2

A

B2

7

5 C3 3 3 8 C4 4 3

3

2 D2 1 2 3 D3 3 4

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

G

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

2、状态、状态变量
每个阶段开始所处的自然状态或客观条件,描述过程 的状况,通常一个阶段有若干个状态. s2=? 描述过程状态的变 1 C1 6 2 E1 3 D1 8 量称为状态变量, 2 5 B1 3 3 5 F1 4 C2 6 5 它可用一个数、一 A 1 5 E2 2 3 D2 8 C3 3 2 组数或一向量来描 6 F2 3 B2 7 3 3 E3 6 述, 常用 sk 表示第 D3 8 6 3 C4 4 k 阶段的状态.
1 2 3 4 5 6

G

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

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

uk(sk) ? Dk(sk)
C1

uk(sk), 表示第 k 阶段当状

1

6
8

态为 sk 时的决策变量. 5 B1 3 6 A 允许决策集合, 3
常用Dk(sk)表示第k阶 段从状态sk出发的允许 决策集合.
1

C2 3

2 D1 2

E1 3

D2(B1 )?

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
4

2

5

6

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

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

状态转移方程的一般形式

1

C1

6
8

s2=T1(s1, u1)

=A,u ,) 12 1,=B s3=s T (s1, u1 s 2, 1 u 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 5 B1
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

图示如下: s1 u1 1 s2 u2 2 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
4

2

3

=d5(s5,u5)+ V6, 6
1 2 3 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

5

6

(穷举法48条路线)

k=6, 2 E1 3 D1 8 F1 ? G,f6(F1)=4 2 5 B1 3 5 F1 4 C2 3 6 5 F2 ? G,f6(F2)=3 A 1 5 D2 G E2 2 3 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? ?5 ? ? ? 2 ? 3? ?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 E1 3 D1 8 2 5 B1 3 3 5 F1 4 C2 6 5 A 1 5 D2 G E2 2 3 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

6

5 E2 2 6 E3

F1 4 G F2

6

3

求解的各个阶段,我们利用了k 阶段与 k+1 阶段之 间的递推关系: fk ( sk ) = min f 7(s7) = 0
k = 6, 5, 4, 3, 2, 1
u k ? D k ( sk )

{dk (sk , uk ( sk )) + fk+1(sk+1 )}

动态规划基本方程
u k ? D k ( sk )

指标函数是各阶段指标的和

fk ( sk ) = opt {vk (sk , uk ( sk )) + fk+1(sk+1 )}

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

动态规划基本方程
uk ? Dk (sk)

指标函数是各阶段指标的积

fk ( sk ) = opt {vk (sk , uk ( sk )) * fk+1(sk+1 )} fn+1 ( sn+1) = 1 (边界条件)

练习

2

B1
5 1

12

A

14 6 B2 10 4 13 B3 12 11

C1
9

3 6

C2 C3

D1 D2

5

5

E
2

8 10

动态规划的理论基础
最优性原理(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,有

~ sk ? Tk ?1 ( sk ?1 , uk ?1 )

V

0 , n ?1

( s0 ,

p
?

* 0 , n ?1

)?

p0 , k ?1?P 0 , k ?1( s 0 )

opt

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

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

opt

~ ( V k , n ?1 s k ,

p

k , n ?1

)

?

p0,n?1 ? ( p0,k ?1 , pk ,n?1 )

V

0, n ?1

( s 0,

p

*

0, n ?1

)?

p 0,k ?1?P 0,k ?1( s 0 )

min

?V

0, k ?1

( s 0,

p
)

0, k ?1

)

?

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

min V
6

k , n ?1

(s ? k,

p

k , n ?1

?

6 5 1 C1 11 8 8 C2 3 10 5 C3 3 3 8 C4 4 9 2

5
A 3

B1

D1

2

13

3
6 8 7

B2

3 6 0 1

13 2 1 D2 2 3 D3 3 13 3

E1 3 17 5 F1 4 13 5 G E2 2 6 18 F2 3 E3 6 15 15
4 5

推论:若允许策略 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 所确定的)
最优性原理

最优化原理为必要条件,最优性定理为充要条件! 最优化原理为最优性定理的推论! 最优性定理才是动态规划的理论基础!

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

1.将问题的过程划分成恰当的阶段;对于静态问题要人为 地赋予“时间”概念, 以便划分阶段. 2.选择状态变量 sk , 既能描述过程的变化又满足无后效性; 3.确定决策变量 uk 及每一阶段的允许决策集合Dk( sk ); 4.正确写出状态转移方程; 状态转移方程应当具有递推关系. 5.正确写出阶段指标函数和最优指标函数,建立动态规 划基本方程 阶段指标函数是指第k 阶段的收益,最优指标函数是 指从第k 阶段状态出发到第n 阶段末所获得收益的最 优值,最后写出动态规划基本方程。

逆序解法的基本方程
n

(1) 指标函数为“和”的形Vk ,n ( sk , pkn ( sk )) ? ? vi ( si , ui )



i ?k

和、积函数的基本方 相应的基本方程为

f (s ) ? 0 ? ? n ?1 n ?1 ? f ( s ) ? opt {v ( s , u ) ? f ( s )}, k ? n,? , 2,1 k k k k k k ?1 k ?1 ? u ? D k k ?
n

程中边界条件不一样

(2) 指标函数为“积”的形Vk , n ( sk , pkn ( sk )) ? ? vi ( si , ui )

式 相应的基本方程为

i ?k

sk ?1 ? Tk (sk , uk ) f n ?1 ( sn ?1 ) ? 1 ? ? ? f ( s ) ? opt {v ( s , u ) ? f ( s )}, k ? n,? , 2,1 k k k k k k ?1 k ?1 ? uk ?Dk ?

求解时从边界条件开始,逆(或顺)过程行进方 向,逐段递推寻优. 每段决策的选取都是从全局考虑的,与该段的最 优选择答案一般是不同的.

在求整个问题的最优策略时,由于初始状态是已 知的,每段的决策都是该段状态的函数,故最优 策略所经过的各段状态便可逐次变换得到,从而 确定了最优路线.

动态规划和静态规划的关系
二者都属于数学规划的范围,本质上都是求极值的问 题。都是用迭代法逐步求解。 静态规划(如线性规划)研究的问题是与时间无关的, 每步迭代是整体改进。 动态规划是用来解决多阶段决策过程最优化的一种数 量方法。把问题的整体,恰当地分为若干个相互联 系的阶段,按一定的次序去求解单阶段决策问题。 每步迭代是由当前阶段到“下”个阶段。 对于某些静态的问题可以人为的引入时间因素,把它 看作按阶段进行的一个动态规划问题,从而把一个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 , s3 ? x1 0 ? x3 ? s1 , 0 ? x2 ? s2 , 0 ? x1 ? s3

? 指标函数
? 基本方程

Vk ,3 ? ? g i ( xi )
i ?k

3

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

k ? 3,2,1

f3 (s3 ) ? max{4 x1}
0? x1 ? s3 * x 最优决策为 1 ? s3 , 最优目标函数 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

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

2 x3 ? f 2 ( s2 )} 当阶段k=1时,有 f1 ( s1 ) ? 0max{2 ? 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 求解下面问题:
2 max Z ? x1 ? x 2 ? x3

? 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 ? x 3 2 ? x1 ? x2 ? x3 ? c (c? 0) s.t. ? ? xi ? 0, i ? 1,2,3

4、基本方程

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

{vk (sk , xk ) ? f k ?1 (sk ?1 )} ? ? f k (sk ) ? 0max ? 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 s2 得最优决策 x 2 ? s2 , 最优目标函数 f 2 ( s2 ) ? 3 27

当阶段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

例2’ 求解下面问题:

max Z ? 4 x1 ? x 2 ? x3
2

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

练习1
P212 8.5 (1)

练习2

max F ? 4 x ? x ? 2 x ? 12
2 1 2 2 2 3

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

2 2 max F ? 4 x12 ? x2 ? 2 x3 ? 12

?3x1 ? 2 x2 ? x3 ? 9 s.t. ? ? xi ? 0, i ? 1, 2,3 y1 ? 3x1 , y2 ? 2 x2 , y3 ? x3 , 4 2 1 2 2 max F ? y1 ? y2 ? 2 y3 ? 12 9 4 ? y1 ? y2 ? y3 ? 9 s.t. ? ? xi ? 0, i ? 1, 2,3

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

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

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

§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? ukx (s kk) ? sk

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 x3 ? s3
甲 乙 丙

指标函数 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 }

ax[ g k ? x k ? ? f k ?1 ( s k ?1 )] ? ? f k ?s k ? ? 0m ? x k ? sk ? ? ? 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 ( s4 )} x3*(0) = 0 0? x ? s
3

? g 3 ( 0) ? 0

3

s3 = 1

f 3 (1) ? m ax{ g 3 ( x 3 ) ? f 4 ( s 4 )} x *(1) = 1 3 0? x 3 ? s3 ? g 3 ( 0 )? ? m ax? ?4 ? x 3 ? 0 ,1 g 3 (1) 甲 ? ?
0 1 2 3 4 5 0 3 7 9 12 13
乙 丙 0 4 6 11 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) 2 3 6 0 3 7 9 12 13

乙 0 5 10 11 11 11



s3 = 5

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

0 4 6 11 12 12

结果可写 成表格的 形式:

x3 s3 0 1 2 3 4 5 0 0 1 4

4

5

f3(s3) x*3

11
12 12

0 4 6 11 12 12

0 1 2 3 4 4,5

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 ? s 2

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







12
12

0 4 6 11 12 12

0 1 2 3 4 4,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

s2 = 1

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

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

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

? g 2 (0) ? f 3 (1)? ? m ax? ? x 2 ? 0 ,1 g (1) ? f ( 0 ) 3 ? 2 ? ?0 ? 4 ? ? m ax? ?5 ? x 2 ? 0 ,1 5 ? 0 ? ?
4 5 f3(s3) x*3







12
12

0 4 6 11 12 12

0 1 2 3 4 4,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

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

? 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 0 1 2 3 4 5 g3(x3) 1 4 6 11 2 3 4 5 f3(s3) x*3







12
12

0 4 6 11 12 12

0 1 2 3 4 4,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

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) ? ? ? max ? ? ? x 2 ? 0 ,1, 2 , 3 10 ? 4 f 3 (1) ? ? ? f 3 ( 0 )? ?11 ? 0 ? ?

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

g3(x3) 3 4 5

f3(s3) x*3







11

12
12

0 4 6 11 12 12

0 1 2 3 4 4,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

s2 = 4

f 2 (4) ? m ax{ g 2 ( x 2 ) ? f 3 ( s 3 )} ? g 2 ( 0) ? ? g 2 (1) ? ? ? m ax ? g 2 ( 2) ? x 2 ? 0 ,1 , 2 , 3 , 4 ? g 2 ( 3) ? ? g ( 4) ? ? 2 ? 16
f3(s3) x*3
0? x 2 ? s 2

f 3 ( 4) ? ?0 ? 12? ?5 ? 11? f 3 ( 3) ? ? ? ? f 3 ( 2)? ? m ax ?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 0 1 2 3 4 5 g3(x3) 1 4 6 2 3







4

5

11

12
12

0 4 6 11 12 12

0 1 2 3 4 4,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

ax{ g 2 ( x 2 ) ? f 3 ( s 3 )} s2 = 5 f 2 (4) ? 0m ? x ?s ? g 2 ( 0) ? ? g 2 (1) ? ? ? g ( 2) ? ? m ax ? 2 x 2 ? 0 ,1 , 2 , 3 , 4 , 5 g 2 ( 3 ) ? ? ? g 2 ( 4) ? ? ? g 2 ( 5) ? ? 21
2 6 11 3 4 5
2 2

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

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

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

g3(x3)

f3(s3) x*3







12
12

0 4 6 11 12 12

0 1 2 3 4 4,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

结果列于下表:

x2
s2 0 1 2 3 4 5

g2(x2)+f3(s2-x2)
0 1 2 3 4 5 0+0 0+4 5+0 0+6 5+4 10+0 0+11 5+6 10+4 11+0 0+12 5+11 10+6 11+4 11+0 0+12 5+12 10+11 11+6 11+4 11+0

f2(s2) 0 5 10 14 16 21

x*2 0 1 2 2 1,2 2

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) ? ? ? max ? 1 x1 ? , 0 ,1, 2 , 3 , 4 , 5 g 1 ( 3) ? ? ? g 1 ( 4) ? x1*(5) =0,2 ? ? g 1 ( 5) ?
x2
0? x1 ? s1

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

s2

f2(s2) 0 5 10 14 16 21

x*2 0 1 2 2 1,2 2







0 1 2 3 4 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

结果可写成表格的形式
x1 s1 5 0 1 0+21 3+16 g1(x1)+f2(s1-x1) 2 7+14 3 4 5 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台,求最优分配方案? 如果原设备台数是6台,求最优分配方案?

例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

sk ?1 ? sk ? xk
s1

x1 1

s2

x2 2

s3

x3 3

s4

x3 ? s3

ax[ g k ? x k ? ? f k ?1 ( s k ?1 )] ? ? f k ?s k ? ? 0m ? x k ? sk ? ? ? f 4 ( s4 ) ? 0


Dk ( sk )={ uk|0? xk ? sk }





0 1 2 3 4 5

0 3 7 9 12 13

0 5 10 11 11 11

0 4 6 11 12 12

0 1 2 3 4 5

甲 0 3 7 9 12 13

乙 0 5 10 11 11 11

丙 0 4 6 11 12 12

x3 s3 0 1 2 3 4 5 0 0 1 4

g3(x3)
2 3 4 5

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

6
11 12 12 f2(s2)

x2 s2 0

g2(x2)+f3(s2-x2) 1 2 3 4 5+0 5+4 5+6 5+11 5+12

5

0 1 2 3 4 5

0+0 0+4 0+6 0+11 0+12 0+12

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

0 5 10 14 16 21

0 1 2 2 1,2 2

资源分配问题
资源平行分配问题—只合理分配资源, 不考虑回收 决策变量为离散值. 销售点分配问题;投资分配问题;货物分配问题 资源连续分配问题—考虑资源回收利用 决策变量为连续值

资源连续分配问题
数量为s1的某种资源,可投入A和B两种生产.第一年:投入A数量u1, 得收入g (u1 ),回收au1;投入B数量s1 ? u1 ,得收入h( s1 ? u1 ),回收b( s1 ? u1 ). 第二年:资源数量s2 ? au1 ? b( s1 ? u1 ), 如此进行n年,应如何决定u1 ,u2 , ?,un ,使得总收入最大? sk:第k阶段可投入A、B两种生产的资源量, sk ?1 ? auk ? b( sk ? uk ) uk:第k阶段投入A生产的资源量; f k ( sk ) : 资源量sk 从第k阶段至第n阶段得到的最大总收入

5.2 资源连续分配问题
第一年 资源数量 s1

第二年
资源数量 s2=au1+b(s1-u1)

A种生产 数量u1投入 收益g (u1) 年终资源回收率a B种生产 数量s1-u1 收益h (s1-u1) 年终资源回收率b A种生产 数量u2投入;收益g(u2); 年终资源回收率a

B种生产 到 n年 数量s2-u2;收益h(s2-u2); 年终资源回收率b 如此进行 n 年, 如何确定投入 A 的资源量 u1、…、 un, 使总收入最大?

S1

A

B

S2

A

B

S3

u1

s1-u1

u2

s2-u2

此问题的静态规划问题模型为: n
m axZ ?

? { g( u
i ?1

i

) ? h( s i ? ui )}

? f (s ) ? 0 n ?1 n ?1 ? ? {g (uk ) ? h( sk ? uk ) ? f k ?1 (auk ? b( sk ? uk ))}, ? f k ( sk ) ? 0max ?uk ? sk ? ? ?k ? n,? , 2,1

? 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 ?

例4

机器负荷分配问题
投入生产的机 器数量

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

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

分析: 阶段? 状态变量 sk 决策变量 uk 0 ? uk ? sk s k – uk 状态转移方程 第 k 年初拥有的完 好机器台数 第 k 年高负荷下投 入的机器数 第 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 ( sk , uk ) ? 8uk ? 5( sk ? 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) 基本方程为 fk(sk) =max {8uk+5(sk-uk)+fk+1(0.7uk+0.9(sk-uk))}
0 ? uk ? sk

k = 1, 2, …, 5

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 ? s4

0

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

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

依次类推可得,
* u3 ? s3 * u2 ? 0 * u1 ?0

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 ? s3 , u4 ? s4 , u5 ? s5

最高产量为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 f5 ( s5 ) ? 3u5 ? 5s5 ? 17.5s5 ? 7500
u *4 ? 0 f 4 (s4 ) ? 20.75s4 ? 0.5u4 ? 7500 ? 20.75s4 ? 7500

k=4 其他略

练习 1

生产与存储问题
设某公司对某种产品要制订一项n个阶段的生产(或购买) 计划.已知它的初始库存量为0,每阶段生产(或购买)该产 品的数量有上限的限制;每阶段对该产品的需求量是已 知的,公司保证供应;在n阶段末的终结库存量为0.问该公 司如何制订每个阶段的生产(或采购)计划,从而使总成 本最小. 1 2 3 4 时期 (k) 3 2 4 需求量 (dk) 2 固定成本为 3千元,单位产品成本为1千元,最大生产批 量不超过6个单位,每个时期末未售出的产品,每单位需 付存贮费0.5千元.

按4个时期将问题分为4个阶段。 第k个时期内的生产成本为: xk ? 0 ?0, ? ck ? xk ? ? ?3 ? 1? xk , xk ? 1, 2,..., 6 ? ?, xk ? 6 ?
hk ? vk ? ? 0.5vk , 第k时期末库存量为vk时存贮费用为:

状态转移方程:vk ?1 ? vk ? dk ? xk
ck ? xk ? ? hk ? vk ? 第k时内的总成本为:
? f k ? vk ? ? min ? ck ? xk ? ? hk ? vk ? ? f k ?1 ? vk ? d k ? xk ? ? k ? 2,3, 4 ? ? 0? xk ?? k ? ? ?? k ? min ? vk ? d k , 6 ? ? f1 ? v1 ? ? min ? c1 ? x1 ? ? h1 ? v1 ? ? ? ? ? x1 ? min ? v1 ? d1 ,6 ? ?

? f k ? vk ? ? min ? ck ? xk ? ? hk ? vk ? ? f k ?1 ? vk ? d k ? xk ? ? k ? 2,3, 4 ? ? 0 ? x ? ? k k ? ? ?? k ? min ? vk ? d k , 6 ? ? f1 ? v1 ? ? min ? c1 ? x1 ? ? h1 ? v1 ? ? ? ? ? x1 ? min ? v1 ? d1 ,6 ? ?

k ? 1时,f1 ? v1 ? ?
x1 ? 2

c1 ? x1 ? ? h1 ? v1 ?? ? ? ? x1 ? min ? v1 ? 2,6? min

v1 ? 0, f1 ? 0 ? ? min ?3 ? x1 ? 0.5 ? 0? ? 5, x1 ? 2
v1 ? 1, f1 ?1? ? min ?3 ? x1 ? 0.5 ?1? ? 6.5, x1 ? 3
x1 ?3

v1 ? 2, f1 ? 2 ? ? min ?3 ? x1 ? 0.5 ? 2? ? 8, x1 ? 4

v1 ? 3, f1 ? 3? ? min ?3 ? x1 ? 0.5 ? 3? ? 9.5, x1 ? 5
x1 ?5

x1 ? 4

v1 ? 4, f1 ? 4 ? ? min ?3 ? x1 ? 0.5 ? 4? ? 11, x1 ? 6
x1 ? 6

k ? 2时,f 2 ? v2 ? ? min ? c2 ? x2 ? ? h2 ? v2 ? ? f1 ? v1 ? ? ? ? 0? x2 ?? 2 ? min ? c2 ? x2 ? ? h2 ? v2 ? ? f1 ? v2 ? 3 ? x2 ? ? ? ? 0? x2 ?? 2
f 2 ? 0 ? ? min ? c2 ? x2 ? ? h2 ? 0 ? ? f1 ? 3 ? x2 ? ? ? ? 0 ? x2 ? 3 ?c2 ? 0 ? ? h2 ? 0 ? ? f1 ? 3? ? ? ? c 1 ? h 0 ? f 2 2? ? 2? ? 1 ? ?? ? ? min ? 9.5 ? c2 ? 2 ? ? h2 ? 0 ? ? f1 ?1? ? ? ? ? ?c2 ? 3? ? h2 ? 0 ? ? f1 ? 0 ? ? ?

x2 ? 0

f 2 ?1? ? min ? c2 ? x2 ? ? h2 ?1? ? f1 ? 4 ? x2 ? ? ? 11.5, x2 ? 0 ? ? 0? x2 ? 4 f 2 ? 2 ? ? min ? c2 ? x2 ? ? h2 ? 2 ? ? f1 ? 5 ? x2 ? ? ? 14, x2 ? 5 ? ? 0? x2 ?5 f 2 ? 3? ? min ? c2 ? x2 ? ? h2 ? 3? ? f1 ? 6 ? x2 ? ? ? 15.5, x2 ? 6 ? ? 0? x2 ? 6

k ? 3时,f3 ? v3 ? ? min ? c3 ? x3 ? ? h3 ? v3 ? ? f3 ? v3 ? 2 ? x3 ?? ? ? 0? x3 ?? 3
f3 ? 0 ? ? min ? c3 ? x3 ? ? h3 ? 0 ? ? f 2 ? 2 ? x3 ? ? ? 0 ? x3 ? 2 ? ?c3 ? 0 ? ? h3 ? 0 ? ? f 2 ? 2 ? ? ? ? ? min ? c3 ?1? ? h3 ? 0 ? ? f 2 ?1? ? ? 14 ? ?c3 ? 2 ? ? h3 ? 0 ? ? f 2 ? 0 ? ? ? x3 ? 0

f3 ?1? ? 16, x3 ? 0 or 3 f3 ? 2 ? ? 17.5, x3 ? 4 f3 ? 3? ? 19, x3 ? 5 f 4 ? 4 ? ? 20.5, x3 ? 6

f 4 ? 0 ? ? min ? c4 ? x4 ? ? h4 ? 0 ? ? f 3 ? 4 ? x4 ? ? ? ? 0? x4 ? 4 ? c4 ? 0 ? ? h4 ? 0 ? ? f3 ? 4 ? ? ? ? ? c4 ?1? ? h4 ? 0 ? ? f3 ? 3? ? ? min ?c4 ? 2 ? ? h4 ? 0 ? ? f 3 ? 2 ? ? ? 20.5 ? ? x4 ? 0 ? c4 ? 3? ? h4 ? 0 ? ? f3 ?1? ? ?c 4 ? h 0 ? f 0 ? ? 4 ? ? 4 ? ? 3 ? ??

k =4时,v4 ? 0,

x1 ? 5, x2 ? 0, x3 ? 6, x4 ? 0

生产与存储问题的特征
阶段i 需求量di 生产量xi 库存量vi 0 — — 0 1 2 5 3 2 3 0 0 3 2 6 4 4 4 0 0

vi ?1 xi ? 0, 再生产点性质。 如果vi ? 0, 则称阶段i为再生产点。 需求不确定的生产存储问题中,最优策略有 s策略,(s, S )策略

§6

生产与存贮问题

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

最初库存量: s1
生产的固定成本: K 单位产品的阶段库存费用: h 阶段生产能力为: B

阶段市场的需求: dk
单位产品的消耗费用: L 仓库容量: M

问如何安排各阶段产量,使计划周期内的费用总和最小.

状态变量 xk:
阶段 k 的初始库存量,s1已知,sn+1 = 0

不能超过库存容量M, sk

?M

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

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

sk ? B

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

dk ? sk ? uk
dk-sk ? uk ? min{B, dk+dk+1+?+dn-sk}

状态转移方程
sk ?1 ? sk ? uk ? dk

阶段效益
为阶段生产费用和库存费用之和,即

gk (sk , uk ) ? K ? Luk ? h(sk ? uk ? dk )
阶段 k 的生产费用 k 阶段末的库存费用

动态规划基本方程
f k (sk ) ? min {K ? Luk ? h(sk ? uk ? d k ) ? f k ?1 (sk ?1 )}
uk ?Dk ( sk )

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

例5 已知 n = 3, K = 8, L = 2, h = 2, s1 = 1, M = 4, s4 = 0, B = 6, d1 = 3, d2 = 4, d3 = 3, 求解生产与库存问题. 解:递推方程 0 ? sk ? min {M, dk+ dk+1+?+ dn}, (k =1, 2, ?, n) dk-sk ? uk ? min{B, dk+dk+1+?+dn-sk}
f k (sk ) ? min {K ? Luk ? h(sk ? uk ? d k ) ? f k ?1 (sk ?1 )}
uk ?Dk ( sk )

f 4 ( s4 ) = 0,k = 1, 2, 3
仓库容量4

当 k ? 3时, f3 ? s3 ? ?

8 ? 2u3 ? ? 3? s ?u ? min?6,3? s ? min
3 3 3

? 8 ? 2(3 ? s3 ) ? 14 ? 2s3

dk-sk ? uk ?min{B,dk+dk+1+?+dn-sk}
n ? ? 0 ? s3 ? min ?M , ? di ? ? min ?M , d3? ? 3 i ?k ? ?

s3:0~3
u3 0

f3(s3)= 14-2s3
1 2 3 14 12 10

u3 =3-s3
f3(s3) 14 12 10 8 u*3(s3) 3 2 1 0

s3 0 1 2 3

8

例5 已知 n = 3, K = 8, L = 2, h = 2, s1 = 1, M = 4, s4 = 0, B = 6, d1 = 3, d2 = 4, d3 = 3, 求解生产与库存问题.

容量4

s3 ? s2 ? u2 ? d2

sk ?1 ? sk ? uk ? dk

4+3

0 ? s2 ? min{M, d2+ d3} =min{4,7}=4 4-s2?u2?min{B,d2+d3-s2}=min{6,7-s2}

uk?dk-s

k

f2 (s2 ) =min {8+2u2+2(s2 +u2-4)+ f3 (s2 + u2-4)}
4-s2 ? u2 ? min{6,7-s2}

f2 (s2 ) =min {4u2+2s2+ f3 (s2 + u2-4)}
s3 0 1 2 3 u2 u3 f3(s3) 14 12 10 8 u*3(s3) 3 2 1 0

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

s2 0 1 2 3 4

0

1

2

3

4

5

6

f2(s2) u*2(s2) 4 3 2 1 0

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

例5 已知 n = 3, K = 8, L = 2, h = 2, s1 = 1, M = 4, s4 = 0, B = 6, d1 = 3, d2 = 4, d3 = 3, 求解生产与库存问题.
f k (sk ) ? min {K ? Luk ? h(sk ? uk ? d k ) ? f k ?1 (sk ?1 )}

k =1

uk ?Dk ( sk )

dk-sk ? uk ? min{B, dk+dk+1+?+dn-sk}

f1 (s1 ) ? min {4u1 ? 2s1 ? 2) ? f2 ( s2 )}
uk ?Dk ( sk )

s1 = 1
u1 1 2

2 ? u1 ? 6
3 4 5 6 f1(s1) u*1(s1) 42 2

s1

10+2+30 14+2+28 18+2+26 22+2+24 26+2+22

u2 s2 0 1 2 3 4

0

1

2

3

4

5

6

f2(s2) u*2(s2) 4 3 2 1 0

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

s3 0 1 2 3

u3

f3(s3) 14 12 10 8

u*3(s3) 3 2 1 0

s1 ? 0
* u1 ?2

s2 ? s1 ? u1 ? d1 ? 1 ? 2 ? 3 ? 0
* u2 ?4

s3 ? s2 ? u2 ? d 2 ? 0 ? 4 ? 4 ? 0
* u3 ?3

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

{1,0,0,0}

s3=s2+u2-d2=0+4-4=0

最优目标函数值为42.

§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 ( s ) ? max { v ( s , x ) ? ? f ( s )} ? k k j k k k ? 1 k ? 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)

单位:万元 役龄

项目 5 4.5 4 3.75 3 效益IK(t) 运行费OK(t) 0.5 1 1.5 2 2.5 更新费CK(t) 0.5 1.5 2.2 2.5 3 解:n=5 ?I 5 (s5 ) ? O5 (s5 ) k ?5 f 5 (s5 ) ? max ? ?I 5 (0) ? O5 (0) ? c5 (s5 ) 状态变量s5可取1,2,3,4

0

1

2

3

4

5
2.5 3 3.5

x5 ? K x5 ? R

卖掉役龄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 ) ? f5 (s4 ? 1) f 4 (s4 ) ? max ? ?I 4 (0) ? O4 (0) ? c4 (s4 ) ? f5 (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) f3 (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# 0 1 2 3 4 5

0 0 -

3 5 4

6 10 8

10 12 11

12 - 15

- - 18

考研试题
1. 下列关于动态规划问题的说法不正确的是( )。 A.应用推理或逆推法可能会得出不同的最优解 B.状态变量应具有无后效性 C.动态规划模型中,阶段是按时间或空间划分的 D.问题的阶段数等于问题中的子问题的数目 2. 用动态规划方法求解多阶段问题时,指标函数应满 足( )。 A.定义在全过程和后部子过程上的数量函数 B.具有可分离性,满足递推关系 C.严格单调 D.以上A、B、C都是

3. 下述的( )不能设为动态规划中的状态变量. A.生产企业某种产品的每月月初库存 B.某种设备每年年末的可利用量 C.送货车辆行驶过的路程 D.送货车辆行驶时的速度


相关文章:
管理运筹学第6章-动态规划_图文.ppt
管理运筹学第6章-动态规划 - 本科院校管理运筹学课件。48学时,教师原创... 本科院校管理运筹学课件。48学时,教师原创 6.动态规划( 6.动态规划(dynamic programming...
管理运筹学 第5章 动态规划_图文.ppt
管理运筹学 第5章 动态规划 - 第五章 动态规划 5.1. 动态规划的基本概念和最优化原理 5.2. 动态规划模型的建立与求解 5.3. 动态规划在经济管理中的应用 ...
管理运筹学讲义 第6章动态规划.ppt
管理运筹学讲义 第6章动态规划_电脑基础知识_IT/计算机_专业资料。管理运筹学讲义 第6章动态规划 第6章 动态规划学习要点 Sub title ? 理解多阶段决策问题的基本...
管理运筹学 第六章 动态规划_图文.ppt
管理运筹学 第六章 动态规划 - 第六章 动态规划 广东工业大学管理学院 第六章 动态规划 6.1 动态规划的基本概念 6.2 最优化原理 6.3 经济管理问题举例 多...
管理运筹学讲义动态规划1_图文.ppt
管理运筹学讲义动态规划1 - SHUFE 运筹学课件 运筹帷幄之中 Dynamic Programming 决胜 动态规划 千里之外 1 上海电力学院管文...
管理运筹学第3章:动态规划_图文.ppt
管理运筹学第3章:动态规划 - 第三章:动态规划 3.1 基本概念 一、动态决策
管理运筹学10动态规划_图文.ppt
管理运筹学10动态规划 - 第十章 动态规划 §1 多阶段决策过程最优化问题举例 §2 基本概念、基本方程与最优化原理 §3 §4 动态规划的应用(1) 动态规划的...
管理运筹学讲义:动态规划(1)_图文.ppt
管理运筹学讲义:动态规划(1) - SHUFE 运筹学课件 运筹帷幄之中 Dynamic Programming 决胜 动态规划 千里之外 1 上海电力学...
管理运筹学课件第9章动态规划_图文.ppt
管理运筹学课件第9章动态规划 - 第9章 动态规划 教学目标与要求 ? ? ?
管理运筹学讲义:动态规划.ppt
管理运筹学讲义:动态规划_管理学_高等教育_教育专区。数学建模管理运筹学谢家平
管理运筹学课件第9章 动态规划_图文.ppt
管理运筹学课件第9章 动态规划 - 第9章 动态规划 教学目标与要求 ? ? ?
管理运筹学讲义 第6章 动态规划_图文.ppt
管理运筹学讲义 第6章 动态规划 - 第6章 动态规划 学习要点 Sub tit
《管理运筹学》案例演示(动态规划)_图文.ppt
管理运筹学》案例演示(动态规划) - 例.(生产与库存问题)某电视机厂为生产电
管理运筹学讲义:动态规划_图文.ppt
管理运筹学讲义:动态规划 - 1 2 3 4 5 6 7 8 9 10 11 12 第七章 动态规划 ? 动态规划Dynamic Programming 研究多阶段决策的最优化问题的方...
第10章__动态规划_(管理运筹学_第三版_课件__共17章_韩....ppt
第10章__动态规划_(管理运筹学_第三版_课件__共17章_韩伯棠)_管理学_高等教育_教育专区。第10章__动态规划_(管理运筹学_第三版_课件__共17章_韩伯棠) ...
管理运筹学讲义 第6 章 动态规划_图文.ppt
管理运筹学讲义 第6 章 动态规划 - 管理运筹学-管理科学方法 谢家平 编著 中国人民大学出版社 第6 章 动态规划 学习要点 Sub title ? 理解多阶段决策问题的...
管理运筹学5动态规划_图文.ppt
管理运筹学5动态规划 - 第三章: 第三章:动态规划 3.1 动态规划的基本概念
运筹学第10章 动态规划_图文.ppt
运筹学第10章 动态规划 - Page:1 管理运筹学 动态规划 Page:2 综 述 动态规划是解决多阶段决策过程最优 化问题的一种方法。动态规划所研究 的对象是多阶段...
《管理运筹学》案例演示(动态规划)_图文.ppt
管理运筹学》案例演示(动态规划) - 使用计算机软件包求解(附件1) A B
管理运筹学教案_动态规划1_图文.ppt
动态规划的研究对象和引例 动态规划的基本概念和定义 动态规划的基本思想和基本方程 动态规划的理论基础和具体迭代方 法 2011-3-11 管理运筹学课程组 ftp://211...
更多相关文章: