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

10运筹学-动态规划


动态规划
动态规划问题实例 ? 动态规划的基本概念与原理 ? 动态规划应用举例
?

引言
动态规划是解决多阶段决策过程最优化的一种方法。该方法 是由美国数学家贝尔曼(R. E. Bellman)等人在20世纪50年代 初提出的。并成功地解决了生产管理、工程技术等方面的许

多问题,从而建立了运筹学的一个新的分支,即动态规划。
Bellman在1957年出版了《Dynamic Programming》一书,是 动态规划领域中的第一本著作。

§1 动态规划问题实例
例1 给定一个线路网络, 要从A向F铺设一条输油管道, 各点间连线上的数字表示距离,问应选择什么路线,可使总

距离最短?
2 4

C1
8 3

5

B1

6 5 8 7

C2 C3

4
5 3 4 8

D1 D2
5 6 2 1

3

E1
3

4

A B2

F E2
3

7

C4

D3
4

动态规划是解决多阶段决策问题的一种方法。所谓多阶段 决策问题是指这样的决策问题:其过程可分为若干个相互联

系的阶段,每一阶段都对应着一组可供选择的决策,每一决
状态A 决策A 状态B 决策B 状态C 决策C 状态D 决策D 状态E 决策E 状态F

A

B

C

D

E

策的选定即依赖于当前面临的状态,又影响以后总体的效果。

当每一阶段的决策选定以后,就构成一个决策序列,称为一个
策略,它对应着一个确定的效果。多阶段决策问题就是寻找使

此效果最好的策略。

§2
一。基本概念

动态规划的基本概念与原理

阶段:是指问题需要做出决策的步数。阶段总数常记为n,相 应的是n个阶段的决策问题。阶段的序号常记为k,称为阶段 变量,k=1,2, …,n. k即可以是顺序编号也可以是逆序编号, 常用顺序编号。 状态:各阶段开始时的客观条件,第k阶段的状态常用状态 变量 sk 表示,状态变量取值的集合称为状态集合,用 Sk 表示。

例如,例1中, S1 ? {A}, S2 ? {B1 , B2 }.

状 态
1

状 态
2

状 态 3

状 态
4

状 态 5

状 态 6

2 4

C1
8 3

5 4

B1

D1 D2 D3
5 6 2 1

3

6
5 8 7 7

C2 C3

5
3 4 8 4

E1
3

4

A B2

F E2
3

C4

第1阶段

第2阶段

第3阶段

第4阶段

第5阶段

决策:是指从某阶段的某个状态出发,在若干个不同方案中 做出的选择。表示决策的变量,称为决策变量,用 uk (sk ) 表示

例如: u3 (C2 ) ? D1 表示走到C阶段,当处于C2 路口时,下一
步奔D1.

决策变量允许的取值范围称为允许决策集合,第k阶段状态为

sk 时的允许决策集合记为 Dk (sk ) ,例如:D2 ( B1 ) ? {C1, C2 , C3}
状态转移方程:是从上一阶段的某一状态值转变为下一阶段
某一状态值的转移规律,用
sk ?1 ? Tk (sk , uk )

表示。

指标函数:分阶段指标函数和过程指标函数。阶段指标函数
是指第k阶段从状态 sk 出发,采取决策 uk 时的效益,用
vk (sk , uk ) 表示。而过程指标函数从第k阶段的某状态出发,

采取子策略 pkn ? {uk , uk ?1 ,?, un } 时所得到的阶段效益之和:
Vkn ( sk , pkn ) ? ? v j (s j , u j )
j ?k n

最优指标函数:表示从第k阶段状态为 sk 时采用最佳策略
* pkn 到过程终止时的最佳效益。记为
* f k (sk ) ? Vkn (sk , pkn )?

pkn ?Dkn ( sk )

opt Vkn (sk , pkn )

其中 opt 可根据具体情况取max 或min。 基本方程:此为逐段递推求和的依据,一般为:
? ? f k ( sk ) ? ? ? ? f n ?1 ( sn?1 ) ? 0
u k ?Dk ( sk )

opt [vk ( sk , uk ) ? f k ?1 ( sk ?1 )] k ? n, n ? 1,?,1

式中opt 可根据题意取 max 或 min.
例如,例1的基本方程为:
? f k ( sk ) ? min{d k ( sk , uk ) ? f k ?1 ( sk ?1 )} k ? 5,4,3,2,1 uk ? ? f 6 ( s6 ) ? 0

最优性原理:无论过去的状态和决策如何,从眼下直到最后 的诸决策必构成最优子策略。

动态规划应用举例
例1 最短路线问题
2 4

C1
8 3

5 4

B1

D1 D2 D3
5 6
2 1

3

6
5 8 7 7

C2 C3

5
3 4 8

E1
3

4

A B2

F E2
3

C4

4

2
4

C1
8 3

5 4 5 3 4 8

B1

D1 D2 D3
5 6 2 1

3

6

C2
7
7

E1
3

4

A
5

8

C3
C4

F E2
3

B2

4

逆序递推方程:
? f k ( sk ) ? min{d k ( sk , uk ) ? f k ?1 ( sk ?1 )} k ? 5,4,3,2,1 uk ? ? f 6 ( s6 ) ? 0

(1)k=5 时,状态 S5 ? {E1 , E2} 最短路。

它们到F 点的距离即为

f 5 ( E1 ) ? 4,

f5 ( E2 ) ? 3;

* * u5 ( E1 ) ? F , u5 ( E2 ) ? F.

2
4

C1
8 3

5 4 5 3 4 8

* u5 ( E1 ) ? F ,

B1

D1 D2 D3
5 6 2 1

3

6

C2
7
7

* u5 ( E2 ) ? F.

E1
3

4

A
5

8

C3
C4

F E2
3

B2

4

(2)k=4 时,状态 S4 ? {D1 , D2 , D3} 它们到F 点需经过中途 点E,需一一分析从E 到 F的最短路:先说从D1到F 的最短路 有两种选择:经过 E1, E2, 比较最短。

2
4

C1
8 3

5 4 5 3 4 8

* u5 ( E1 ) ? F ,

B1

D1 D2 D3
5 6 2 1

3

6

C2
7
7

E1
3

* u5 ( E2 ) ? F.

4

A
5

8

C3
C4

F E2
3

B2

4

f 4 ( D1 ) ? min{ d4 ( D1 , E1 ) ? f5 ( E1 ), d4 ( D1 , E2 ) ? f5 ( E2 )}

? min{ 3 ? 4,5 ? 3} ? 7.
这说明由 D1 到F 的最短距离为7,其路径为 D1 ? E1 ? F.
* ( D1 ) ? E1. 相应的决策为:u4

2
4

C1
8 3

5 4 5 3 4 8

* u5 ( E1 ) ? F ,

B1

D1 D2 D3
5 6 2 1

3

6

C2
7
7

E1
3

* u5 ( E2 ) ? F.

4

A
5

8

C3
C4

F E2
3
* u4 ( D1 ) ? E1.

B2

4

f 4 ( D2 ) ? min{ d4 ( D2 , E1 ) ? f 5 ( E1 ), d4 ( D2 , E2 ) ? f 5 ( E2 )}

? min{ 6 ? 4,2 ? 3} ? 5.
这说明由 D2 到F 的最短距离为5,其路径为 D2 ? E2 ? F.
* u4 ( D2 ) ? E2 . 相应的决策为:

2
4

C1
8 3

5 4 5 3 4 8

* u5 ( E1 ) ? F ,

B1

D1 D2 D3
5 6 2 1

3

6

C2
7
7

E1
3

* u5 ( E2 ) ? F.

4

A
5

8

C3
C4

F E2
3
* u4 ( D1 ) ? E1. * u4 ( D2 ) ? E2 .

B2

4

f 4 ( D3 ) ? min{ d4 ( D3 , E1 ) ? f5 ( E1 ), d4 ( D3 , E2 ) ? f5 ( E2 )}

? min{ 1 ? 4, 3 ? 3} ? 5.
即 D3 到F 的最短距离为5,其路径为 D3 ? E2 ? F. 相应的决策为: u4 ( D3 ) ? E1.
*

f 4 ( D1 ) ? 7
4

2

C1
8 3

5 4 5 3 4 8

* u4 ( D3 ) ? E1.

* u5 ( E1 ) ? F , * u5 ( E2 ) ? F.

B1

D1 D2 D3
5 6 2 1

3

6

C2
7
7

E1
3

4

A
5

8

C3
C4

F E2
3
* u4 ( D1 ) ? E1. * u4 ( D2 ) ? E2 .

f 4 ( D2 ) ? 5

B2

4

(3)k=3 时,状态 S3 ? {C1 , C2 , C3 , C4}

f3 (C1 ) ? min{ d3 (C1 , D1 ) ? f 4 ( D1 ), d3 (C1 , D2 ) ? f 4 ( D2 )}

? min{ 5 ? 7, 8 ? 5} ? 12.
这说明由 C1 到F 的最短距离为12,相应的决策为
* u3 (C1 ) ? D1.

* u3 (C1 ) ? D1.

2

C1
8 3

5 4 5 3 4 8

* u4 ( D3 ) ? E1.

* u5 ( E1 ) ? F , * u5 ( E2 ) ? F.

f 4 ( D3 ) ? 5
A

4

B1

D1 D2 D3
5 6 2 1

3

6

C2
7
7

E1
3

4

5

8

C3
C4

F E2
3
* u4 ( D1 ) ? E1.

B2

* u4 ( D2 ) ? E2 . f3 (C2 ) ? min{ d3 (C2 , D1 ) ? f 4 ( D1 ), d3 (C2 , D2 ) ? f 4 ( D2 )}

f 4 ( D1 ) ? 7

4

f 4 ( D2 ) ? 5

? min{ 4 ? 7,5 ? 5} ? 10.
即由 C2 到F 的最短距离为10,相应的决策为
* u3 (C2 ) ? D2 .

f3 (C3 ) ? min{ d3 (C3 , D2 ) ? f 4 ( D2 ), d3 (C3 , D3 ) ? f 4 ( D3 )}

? min{ 3 ? 5,4 ? 5} ? 8.

* u3 (C1 ) ? D1. * u3 (C2 ) ? D2 .

2

C1
8 3

5 4 5 3 4 8

* u4 ( D3 ) ? E1.

* u5 ( E1 ) ? F , * u5 ( E2 ) ? F.

4

B1

D1 D2 D3
5 6 2 1

3

6

C2
7
7

E1
3

4

A
5

8

C3
C4

F E2
3
* u4 ( D1 ) ? E1. * u4 ( D2 ) ? E2 .

f 4 ( D3 ) ? 5

B2

4

f 4 ( D2 ) ? 5

即由 C3 到F 的最短距离为8,相应的决策为

* u3 (C3 ) ? D2 .

f3 (C4 ) ? min{ d3 (C4 , D2 ) ? f 4 ( D2 ), d3 (C4 , D3 ) ? f 4 ( D3 )}

? min{ 8 ? 5,4 ? 5} ? 9.
即由 C4 到F 的最短距离为9,相应的决策为
* u3 (C4 ) ? D3 .

* u3 (C1 ) ? D1. * u3 (C2 ) ? D2 .

2

C1
8 3

5 4 5 3 4

* u4 ( D3 ) ? E1.

* u5 ( E1 ) ? F , * u5 ( E2 ) ? F.

4

B1

D1 D2
5 6 2 1

3

6

C2
7

E1
3

4

A
5

8

* 8 u3 (C3 ) ? D2 . B2 7 D3 3 * C 4 4 u3 (C4 ) ? D3 . f3 (C1 ) ? 12 f3 (C2 ) ? 10 f 3 (C3 ) ? 8

C3

F E2
* u4 ( D1 ) ? E1. * u4 ( D2 ) ? E2 .

(4)k=2时,状态 S2 ? {B1 , B2 }

f 2 ( B1 ) ? min{ d 2 ( B1 , C1 ) ? f 3 (C1 ), d 2 ( B1 , C2 ) ? f 3 (C2 ), d 2 ( B1 , C3 ) ? f 3 (C3 )} ? min{ 2 ? 12,3 ? 10,6 ? 8} ? 13.
* ( B1 ) ? C2 . 这说明由 B1 到F 的最短距离为13,相应的决策为 u2

* u3 (C1 ) ? D1. * u3 (C2 ) ? D2 .

2

C1
8 3

5 4 5 3 4 8

* u4 ( D3 ) ? E1.

* u5 ( E1 ) ? F , * u5 ( E2 ) ? F.

4

B1

D1 D2 D3
5 6 2 1

3

6

C2
7

E1
3

4

A
5

8

* u3 (C3 ) ? D2 . B2 7 * u3 (C4 ) ? D3 .

C3
C4

F E2
3
* u4 ( D1 ) ? E1. * u4 ( D2 ) ? E2 .

4

f 3 (C4 ) ? 9 f3 (C2 ) ? 10

* u2 ( B1 ) ? C2 .

f 3 (C3 ) ? 8

f 2 ( B2 ) ? min{ d 2 ( B2 , C2 ) ? f 3 (C2 ), d 2 ( B2 , C3 ) ? f 3 (C3 ), d 2 ( B2 , C4 ) ? f 3 (C4 )} ? min{ 8 ? 10,7 ? 8,7 ? 9} ? 15.
即由 B2到F 的最短距离为15,相应的决策为
* u2 ( B2 ) ? C3 .

* u3 (C1 ) ? D1. * u3 (C2 ) ? D2 .

2

C1
8 3

5 4 5 3 4

* u4 ( D3 ) ? E1.

* u5 ( E1 ) ? F , * u5 ( E2 ) ? F.

4

B1

D1 D2 D3
5 6 2 1

3

6

C2
7

E1
3

4

A
5

8

* 8 u3 (C3 ) ? D2 . B2 7 * u3 (C4 ) ? D3 . C4 4 f 2 ( B1 ) ? 13 f 2 ( B2 ) ? 15

C3

F E2
3
* u4 ( D1 ) ? E1. * u4 ( D2 ) ? E2 . * u2 ( B2 ) ? C3 .

* u2 ( B1 ) ? C2 .

(1)k=1 时,只有一个状态点A, 则

f1 ( A) ? min{ d1 ( A, B1 ) ? f 2 ( B1 ), d1 ( A, B2 ) ? f 2 ( B2 )}

? min{ 4 ? 13,5 ? 15} ? 17.
* u 即由 A到F 的最短距离为17,相应的决策为 1 ( A) ? B1.

* u3 (C1 ) ? D1. * u3 (C2 ) ? D2 .

2

C1
8 3

5 4 5 3 4 8

* u4 ( D3 ) ? E1.

* u5 ( E1 ) ? F , * u5 ( E2 ) ? F.

4

B1

D1 D2 D3
5 6 2 1

3

6

C2
7

E1
3

4

A
5

8

* u3 (C3 ) ? D2 . B2 7 * u3 (C4 ) ? D3 .

C3
C4

F E2
3
* u4 ( D1 ) ? E1. * u4 ( D2 ) ? E2 . * u2 ( B2 ) ? C3 .

4

* u2 ( B1 ) ? C2 .

再按计算顺序反推可得最优决策序列:
* u1 ( A) ? B1 ,

* u2 ( B1 ) ? C2 ,

* u3 (C2 ) ? D2 ,

* u4 ( D2 ) ? E2 ,

* u5 ( E2 ) ? F.

所以最优路线为: A ? B1 ? C2 ? D2 ? E2 ? F

顺序递推方程:
? f k ( sk ?1 ) ? min{d k ( sk ?1 , uk ) ? f k ?1 ( sk )} k ? 1,2,3,4,5 uk ? 初始条件 ? f 0 ( s1 ) ? 0

例1:
4

2

C1
8

5

B1

3
6

C2
7

4
5 3 4 8

D1 D2
5 6 2 1

3

E1
3

4

A
5

8

C3 C4

F E2
3

B2

7

D3
4

1阶段

2阶段

3阶段

4阶段

5阶段

行走方向

2
4

C1
8 3

5 4 5 3 4 8

B1

D1 D2 D3
5 6 2 1

3

6

C2
7
7

E1
3

4

A
5

8

C3
C4

F E2
3

B2

4

K=1 时

f1 (s2 ) ? f1 ( B1 ) ? {d1 ( B1, A) ? f 0 (s1 )} f1 (s2 ) ? f1 ( B2 ) ? {d1 ( B2 , A) ? f 0 (s1 )}
注意到:f0 (s1 ) ? f0 ( A) ? 0

所以

f1 ( B1 ) ? 4, u ( B1 ) ? A
* 1

* u f1 ( B2 ) ? 5, 1 ( B2 ) ? A

* u1 ( B2 ) ? A

2
4

C1
8 3

5 4 5 3 4 8

u ( B1 ) ? A
* 1

B1

D1 D2 D3
5 6 2 1

3

6

C2
7
7

E1
3

4

A
5

8

C3
C4

F E2
3

B2

4

K=2 时

f 2 (s3 ) ? f 2 (C1 ) ? {d2 (C1, B1 ) ? f1 ( B1 )} ? 2 ? 4 ? 6

* u2 (C1 ) ? B1

f 2 (s3 ) ? f 2 (C2 ) ? min{ d2 (C2 , B1 ) ? f1 ( B1 ), d2 (C2 , B2 ) ? f1 ( B2 )}

? min{ 3 ? 4,8 ? 5} ? 7

* u2 (C2 ) ? B1

f 2 (s3 ) ? f 2 (C3 ) ? min{ d2 (C3 , B1 ) ? f1 ( B1 ), d2 (C3 , B2 ) ? f1 ( B2 )}

* u1 ( B2 ) ? A * u1 ( B1 ) ? A

2
4

C1
8 3

5 4 5 3 4 8

f 2 (C1 ) ? 6
D1 D2 D3
5 6 2 1 3 3

u (C1 ) ? B1
* 2

B1

6

C2
7
7

E1
3

f 2 (C2 ) ? 7
4

A
* u2 (C2 ) ? B1

5

8

C3
C4

F E2

B2

4
* u2 (C3 ) ? B1

? min{ 6 ? 4,7 ? 5} ? 10,

f 2 (s3 ) ? f 2 (C4 ) ? {d2 (C4 , B2 ) ? f1 ( B2 )} ? 7 ? 5 ? 12,
K=3 时

* u2 (C4 ) ? B2

f 3 (s4 ) ? f 3 ( D1 ) ? min{ d3 ( D1 , C1 ) ? f 2 (C1 ), d 2 ( D1 , C2 ) ? f 2 (C2 )}

? min{ 5 ? 6,4 ? 7} ? 11

* u1 ( B2 ) ? A

2

C1
8 3

5 4 5 3 4 8

f 2 (C1 ) ? 6
D1 D2 D3
5 6 2 1 3 3

u ( B1 ) ? A 4 u (C1 ) ? B1
* 1 * 2

B1

6

C2
7
7

E1
3

f 2 (C2 ) ? 7
4

A
* u2 (C2 ) ? B1

5

8

C3
C4

F E2

B2

* u2 (C3 ) ? B1

f 2 (C3 ) ? 10
f 2 (C4 ) ? 12

4

* u2 (C4 ) ? B2

* u3 ( D1 ) ? C1 ,



* u3 ( D1 ) ? C2

类似地,可算出:

f3 ( D2 ) ? 12 f3 ( D3 ) ? 14

* u3 ( D2 ) ? C2 * u3 ( D3 ) ? C3

u ( B2 ) ? A
* 1 * u1 ( B1 ) ? A

2
4

C1
8 3

5 4 5 3 4 8

* u3 ( D2 ) ? C2

* u3 ( D3 ) ? C3

B1

D1 D2 D3
5 6 2 1

3

u (C1 ) ? B1
* 2

6

C2
7
7

E1
3

4

A

* u2 (C2 ) ? B1

5

8

C3
C4

F E2
3

B2
* 2

u (C3 ) ? B1
* 2

4

u (C4 ) ? B2
* u4 ( E1 ) ? D1

* * u3 ( D1 ) ? C1 , 或 u3 ( D1 ) ? C2

f 4 ( E1 ) ? 14 f 4 ( E2 ) ? 14

f3 ( D1 ) ? 11 f3 ( D2 ) ? 12 f3 ( D3 ) ? 14
* u4 ( E2 ) ? D2

u ( E2 ) ? D2
* 4

f 5 ( F ) ? 17

u ( F ) ? E2
* 5

* 最优策略: u5 ( F ) ? E2

* u3 ( D2 ) ? C2

* u2 (C2 ) ? B1

* u1 ( B1 ) ? A

最短路径: A ? B1 ? C2 ? D2 ? E2 ? F 最短路长:

f 5 ( F ) ? 17

注:顺序解法与逆序解法无本质区别,一般来说,当初始状
态给定时用逆序解法,当终止状态给定时用顺序解法。若问 题给定了一个初始状态与一个终止状态,则两种方法均可使

用。

例2

资源分配问题(离散型)

例:设有6百万元资金用于4个工厂的扩建,已知每个工厂的 利润增长额同投资额的大小有关,见下表。问应如何确定对 这四个工厂的投资额,使总利润增长额最大?
表1
投资额 (j) 工厂(i)

利润增长额

g i ( x j ) (百元)

0 100 200 300 400 500 600 0 20 0 25 0 18 0 28 42 60 75 85 90 45 57 65 70 73 39 61 78 90 95 47 65 74 80 85

1 2 3 4

解:把对四个工厂的投资依次看成4个阶段的决策过程,
确定对第k个工厂的投资额看成第k个阶段的决策, k=1,2,3,4。图示如下:
投资x1

s1 ? 600

工厂1
g1 ( x1 )

状态

s2

投资x2

s2 ? s1 ? x1

工厂2
g 2 ( x2 )

状态

s3

投资x3

投资x4

s3 ? s2 ? x2

工厂3
g 3 ( x3 )

状态

s4

s4 ? s3 ? x3

工厂4
g 4 ( x4 )

s5

状态变量 sk :可用于第k, k+1,…n个工厂的投资额。 决策变量 xk :第 k 阶段对第 k 个工厂的投资额。 允许决策集 Dk : Dk ? {0, 100, ?, sk }

状态转移方程:sk ?1 ? sk

? xk , k ? 1,2,3,4. 其中 s1 ? 600

阶段指标函数 g k ( xk ) :第 k 阶段投资 xk 元时所产生的利 润。(见上表) 最优指标函数 f k (sk ) :第 k 阶段状态为 sk 且采取最佳投资 策略,从第 k 个工厂以及以后的最大总利润。 逆序法基本递推方程:
? f k ( sk ) ? ? ? f 5 ( s5 ) ? 0
0? xk ? s k

max ?g k ( xk ) ? f k ?1 ( sk ?1 )? k ? 4,3,2,1

投资x1

s1 ? 600

工厂1
g1 ( x1 )

状态

s2

投资x2

s2 ? s1 ? x1

工厂2
g 2 ( x2 )

状态

s3

投资x3

投资x4

s3 ? s2 ? x2

工厂3
g3 ( x3 )

状态

s4

s4 ? s3 ? x3

工厂4
g 4 ( x4 )

s5

表1

利润增长额

gi ( x j ) (百元)

投资额 (j) 工厂(i)

0 100 200 300 400 500 600

4

0 28

47 65 74 80 85

解:(1)k=4时 考虑:若到最后一个,第4个工厂投资时,还有资金 s 4 , 若投资于第4个工厂的资金为 x4 ,则最大利润为

投资x1

s1 ? 600

工厂1
g1 ( x1 )

状态

s2

投资x2

s2 ? s1 ? x1

工厂2
g 2 ( x2 )

状态

s3

投资x3

投资x4

s3 ? s2 ? x2

工厂3
g3 ( x3 )

状态

s4

s4 ? s3 ? x3

工厂4
g 4 ( x4 )

s5

表1

利润增长额

gi ( x j ) (百元)

投资额 (j) 工厂(i)

0 100 200 300 400 500 600

4

0 28

47 65 74 80 85

f 4 ( s4 ) ? max {g 4 ( x4 ) ? f 5 ( s5 )} (注意到此时 f5 (s5 ) =0) 0? x4 ? s 4
? max {g 4 ( x4 )}
0? x4 ? s 4

投资x1

s1 ? 600

工厂1
g1 ( x1 )

状态

s2

投资x2

s2 ? s1 ? x1

工厂2
g 2 ( x2 )

状态

s3

投资x3

投资x4

s3 ? s2 ? x2

工厂3
g3 ( x3 )

状态

s4

s4 ? s3 ? x3

工厂4
g 4 ( x4 )

s5

表1

利润增长额

gi ( x j ) (百元)

投资额 (j) 工厂(i)

0 100 200 300 400 500 600

4

0 28

47 65 74 80 85

自然问:现在还有多少钱?即 s 4 =?

s 4 =0,100,200,300,400,500,600都有可能。

下面分情况讨论:

表1

利润增长额

gi ( x j ) (百元)

投资额 (j) 工厂(i)

0 100 200 300 400 500 600 0 28 47 65 74 80 85

s4 ? 0 时,

4

f 4 ( s4 ) ? max {g 4 ( x4 )} ? max {g 4 ( x4 )} ? max{g 4 ( x4 )}
0? x4 ? s 4
0 ? x4 ? 0 x4 ? 0

? max {0} ? 0.
s4 ? 100 时,

? x4 ?0

{g 4 ( x4 )} f 4 ( s4 ) ? max {g 4 ( x4 )} ? max {g 4 ( x4 )} ? xmax ? 0 , 100 4
0? x4 ? s 4
0? x4 ?100

? max{ 0,28} ? 28.

? x4 ? 100

其他种情况类似讨论,我们把所有的结果汇总成一个表2。

表2 k=4 时决策表

s4

x4

g 4 ( x4 )
0 100 200 300 400 500 600 0 0 0 0 0 0 0 28 28 28 28 28 28

f 4 (s4 )
0 28 47 65 74 80 85

x

? 4

0 100 200 300 400 500 600

47 47 47 47 47

65 65 74 65 74 80 65 74 80

85

0 100 200 300 400 500 600

表1
投资额 (j) 工厂(i)

利润增长额 gi ( x j ) (百元) 0 100 200 300 400 500 600 0 20 0 25 42 60 75 85 90 45 57 65 70 73

1 2

3 4

0 18 0 28

39 61 78 90 95 47 65 74 80 85

表1

利润增长额

gi ( x j ) (百元)

投资额 (j) 工厂(i) 3

0 100 200 300 400 500 600 0 18 39 61 78 90 95

(2)k=3时 到第三个工厂投资时,可利用的资金还有 s 3 ,

若向第三个工厂投资 x3 (万元),则自此即以后最大利润为:

f 3 ( s3 ) ? max {g 3 ( x3 ) ? f 4 ( s4 )}
0? x3 ? s3

? max {g 3 ( x3 ) ? f 4 ( s3 ? x3 )}
0? x3 ? s3

sk ?1 ? sk ? xk ,

s 3 =?,即现在还有多少钱?它是允许决策集上界。 同样问:
同理

s3 ? S3 ? {0,100 ,200 ,300 ,400 ,500 ,600 }

表1

利润增长额

gi ( x j ) (百元)

投资额 (j) 工厂(i) 3

0 100 200 300 400 500 600 0 18 39 61 78 90 95

仅举一例:s3 ? 300

f 3 (300 ) ? max {g 3 ( x3 ) ? f 4 (300 ? x3 )}
0? x3 ?300

?

x3 ? 0 ,100 , 200 , 300

max

{g 3 ( x3 ) ? f 4 (300 ? x3 )}

? max{g3 (0) ? f 4 (300? 0), g3 (100) ? f 4 (300? 100), g3 (200) ? f 4 (300? 200), g3 (300) ? f 4 (300? 300)} ? max{g3 (0) ? f 4 (300), g3 (100) ? f 4 (200), g3 (200) ? f 4 (100), g3 (300) ? f 4 (0)}

表2 k=4 时决策表

s4

x4
0 0 0 0 0 0 0 表1 28 28 28 28 28 28

g 4 ( x4 )
0 100 200 300 400 500 600

f 4 (s4 )
0 28 47 65 74 80 85

x

? 4

0 100 200 300 400 500 600

47 47 47 47 47

65 65 74 65 74 80 65 74 80

85

0 100 200 300 400 500 600

利润增长额 gi ( x j ) (百元) 0 100 200 300 400 500 600

投资额 (j) 工厂(i)

3

0 18

39 61

78 90 95

f 3 (300) ? max{g3 (0) ? f 4 (300), g3 (100) ? f 4 (200), g3 (200) ? f 4 (100), g3 (300) ? f 4 (0)}

? max{ 0 ? 65,18 ? 47,39 ? 28,61? 0} ? 67

? x3 ? 200

所有情况讨论结果汇总成下表:
表3 k=3 时决策表

x3 s3
0 100 200 300 400 500 600 0 0+0 0+28 0+47 0+65 0+74 0+80 0+85 100 18+0 18+28 18+47 18+65 18+74 18+80

g 3 ( x3 ) ? f 4 (s3 ? x3 )
200 300 400 500 600

? f 3 (s3 ) x3

39+0 39+28 39+47 39+65 39+74

61+0 61+28 78+0 61+74 78+28 90+0 61+65 78+47 90+28 95+0

0 28 47 67 89 108 126

0 0 0 200 300 300 300

(3)k=2 时

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

s2 ? S2 ? {0,100,200,300,400,500,600 }
仅举一例:s2 ? 600
f 2 (600 ) ? max {g 2 ( x 2 ) ? f 3 (600 ? x 2 )}
0? x2 ? 600

?

x2 ? 0 ,100 , 200 , 300 , 400 , 500 , 600

max

{g 2 ( x2 ) ? f 3 (600 ? x2 )}

? max{g 2 (0) ? f 3 (600? 0), g 2 (100) ? f 3 (600? 100), g 2 (200) ? f 3 (600? 200), g 2 (300) ? f 3 (600? 300), g 2 (400) ? f 3 (600? 400), g 2 (500) ? f 3 (600? 500) g 2 (600) ? f 3 (600? 600)}

表1

利润增长额

gi ( x j )

(百元)

投资额 (j) 工厂(i)

0 100 200 300 400 500 600 0 25 45 57 65 70 73

2

f 2 (600) ? max{g 2 (0) ? f 3 (600), g 2 (100) ? f 3 (500), g 2 (200) ? f 3 (400), g 2 (300) ? f 3 (300), g 2 (400) ? f 3 (200), g 2 (500) ? f 3 (100) g 2 (600) ? f 3 (0)}

? max{ 0 ? f 3 (600),25 ? f 3 (500), 45 ? f 3 (400),57 ? f 3 (300), 65 ? f 3 (200),70 ? f 3 (100), 73 ? f 3 (0)}

表3 k=3 时决策表

x3 s3
0 100 200 300 400 500 600 0 0+0 0+28 0+47 0+65 0+74 0+80 0+85 100 18+0 18+28 18+47 18+65 18+74 18+80

g 3 ( x3 ) ? f 4 (s3 ? x3 )
200 300 400 500 600

? f3 (s3 ) x3

39+0 39+28 39+47 39+65 39+74

61+0 61+28 78+0 61+74 78+28 90+0 61+65 78+47 90+28 95+0

0 28 47 67 89 108 126

0 0 0 200 300 300 300

f 2 (600) ? max{ 0 ? f 3 (600),25 ? f 3 (500),45 ? f 3 (400),57 ? f 3 (300), 65 ? f 3 (200),70 ? f3 (100),73 ? f 3 (0)}

? max{ 0 ? 126,25 ? 108,45 ? 89,57 ? 67,65 ? 47, 70 ? 28,73 ? 0} ? 45 ? 89 ? 134. ? x2 ? 200

关于 s2 的其它取值情况及相应的最优决策列于下表
表4 k=2 时决策表

x2 s2
0 100 200 300 400 500 600 0 0+0 0+28 0+47 0+67 0+89 0+108 0+126 100

g 2 ( x2 ) ? f3 (s2 ? x2 )
200 300 400 500 600

f 2 (s2 )
0 28 53 73 92 114 134

x

? 2

25+0 25+28 25+47 25+67 25+89 25+108

45+0 45+28 45+47 45+67 45+89

57+0 57+28 65+0 57+47 65+28 70+0 57+67 65+47 70+28 73+0

0 0 100 200 100或200 100 200

(4)k=1 时 ,此时

s1 ? 600,

f 1 ( s1 ) ? f1 (600 ) ? max {g1 ( x1 ) ? f 2 ( s1 ? x1 )}
0? x1 ? s1

? max {g1 ( x1 ) ? f 2 (600 ? x1 )}
0? x1 ? 600

?

x1 ? 0 ,100 , 200 , 300 , 400 , 500 , 600

max

{g1 ( x1 ) ? f 2 (600 ? x1 )}

? max{g1 (0) ? f 2 (600? 0), g1 (100) ? f 2 (600? 100), g1 (200) ? f 2 (600? 200), g1 (300) ? f 2 (600? 300), g1 (400) ? f 2 (600? 400), g1 (500) ? f 2 (600? 500) g1 (600) ? f 2 (600? 600)}

表1 投资额 (j) 工厂(i)

利润增长额

gi ( x j ) (百元)

0 100 200 300 400 500 600 0 20 42 60 75 85 90

1

f1 (600) ? max{g1 (0) ? f 2 (600? 0), g1 (100) ? f 2 (600? 100), g1 (200) ? f 2 (600? 200), g1 (300) ? f 2 (600? 300), g1 (400) ? f 2 (600? 400), g1 (500) ? f 2 (600? 500) g1 (600) ? f 2 (600? 600)} ? max{ 0 ? f 2 (600? 0),20 ? f 2 (600? 100), 42 ? f 2 (600? 200),60 ? f 2 (600? 300), 75 ? f 2 (600? 400),85 ? f 2 (600? 500) 90 ? f 2 (600? 600)}

表4 k=2 时决策表

x2 s2
0 100 200 300 400 500 600 0 0+0 0+28 0+47 0+67 0+89 0+108 0+126 100 200 25+0 25+28 25+47 25+67 25+89 25+108

g 2 ( x2 ) ? f3 (s2 ? x2 )
300 400 500 600

f 2 ( s2 )
0 28 53 73 92 114 134

x

? 2

45+0 45+28 45+47 45+67 45+89

57+0 57+28 65+0 57+47 65+28 70+0 57+67 65+47 70+28 73+0

0 0 100 200 100或200 100 200

f1 (600) ? max{ 0 ? f 2 (600? 0),20 ? f 2 (600? 100),42 ? f 2 (600? 200), 60 ? f 2 (600? 300),75 ? f 2 (600? 400),85 ? f 2 (600? 500), 90 ? f 2 (600? 600)}

? max{ 0 ? 134,20 ? 114,42 ? 92,60 ? 73,75 ? 53,85 ? 28,90 ? 0} ? max{ 134,134,134,133,128,113,90} ? 134.

汇一表格:
表5 k=1 时决策表

s1

x1
0 100 600 134 134

g1 ( x1 ) ? f 2 (s1 ? x1 )
200 134 300 400 133 138 500 600 113 90

f1 (s1 )
134

? x1

0或100或200

? ? 0,100 ,200 此时对应最大值134 的有三个值: x1 ? ?0 所对应的最优策略分别为:x1

时,由状态转移方程

s2 ? s1 ? x1
所对应的
? x2 ??

知:s2 ? s1 ? x1 ? 600? 0 ? 600

表4 k=2 时决策表

x2 s2
0 100 200 300 400 500 600 0 0+0 0+28 0+47 0+67 0+89 0+108 0+126 100 25+0 25+28 25+47 25+67 25+89 25+108

g 2 ( x2 ) ? f3 (s2 ? x2 )
200 300 400 500 600

f 2 ( s2 )
0 28 53 73 92 114 134

x

? 2

45+0 45+28 45+47 45+67 45+89

57+0 57+28 65+0 57+47 65+28 70+0 57+67 65+47 70+28 73+0

0 0 100 200 100或200 100 200

? x 对应的 2 ? 200

再由状态转移方程
? x3 ??

s3 ? s2 ? x2 ? 600? 200 ? 400 对应的

表3 k=3 时决策表

x3 s3
0 100 200 300 400 500 600 0 0+0 0+28 0+47 0+65 0+74 0+80 0+85 100 18+0 18+28 18+47 18+65 18+74 18+80

g 3 ( x3 ) ? f 4 (s3 ? x3 )
200 300 400 500 600

? f3 (s3 ) x3

39+0 39+28 39+47 39+65 39+74

61+0 61+28 78+0 61+74 78+28 90+0 61+65 78+47 90+28 95+0

0 28 47 67 89 108 126

0 0 0 200 300 300 300

? 所对应的 x3 ? 300 再由状态转移方程

s4 ? s3 ? x3 ? 400? 300 ? 100 对应的

? x4 ??

表2 k=4 时决策表

s4

x4
0 0 0 0 0 0 0 28 28 28 28 28 28

g 4 ( x4 )
0 100 200 300 400 500 600

f 4 (s4 )
0 28 47 65 74 80 85

x

? 4

0 100 200 300 400 500 600

47 47 47 47 47

65 65 74 65 74 80 65 74 80

85

0 100 200 300 400 500 600

? 对应的 x4 ? 100
? ? ? x ? 200 , x x ? 300 , 从而得一最优策略 x ? 0, 2 4 ? 100 3
? 1

同理还有另外三个最优策略:

x ? 200 ,
? x1 ? 100, ? x1 ? 200 ,

? 1

x ? 100, x ? 100, x ? 200 ,
? 2 ? 2

? 2

x ? 200 , x ? 300 , x ? 0,
? 3 ? 3

? 3

? x4 ? 100 ? x4 ? 100 ? x4 ? 200

加上刚才一组
? x1 ? 0,

? x2 ? 200 ,

? x3 ? 300 ,

? x4 ? 100

所有解总利润最大增长额为
f1 (s1 ) ? 134

(百元)

资源分配问题(连续型):设备负荷分配问题。 例(何坚勇/P-256)某公司有500辆运输卡车,在超负荷运

输(即每天满载行驶500km以上)情况下,年利润为25万元/
辆,这时卡车的年损坏率为0.3;在低负荷下运输(即每天行 驶300km以下)情况下,年利润为16万元/辆。年损坏率为 0.1。现要制定一个5年计划,问每年年初应如何分配完好车 辆,在两种不同的负荷下运输的卡车数量,使在5年内的总利

润最大?
解:这是一个以时间为特征的多阶段决策问题。

s1 ? 500

投 x1 辆 超 负荷车

第 1年
g1 ( x1 )

状态

s2

投 x2 辆 超 负荷车

s2 ? 0.9s1 ? 0.2x1

第 2年
g 2 ( x2 )

状态

s3

投 x3 辆 超 负荷车

s3 ? 0.9s2 ? 0.2x2

第 3年

状态

s4

投 x4 辆 超 负荷车

s4 ? 0.9s3 ? 0.2x3 g3 ( x3 )

第 4年
g 4 ( x4 )

状态

s5

投 x4 辆 超 负荷车

s5 ? 0.9s4 ? 0.2x4

第 5年
g5 ( x5 )

状态 s 6

sk ?1 ? (1 ? 0.3) xk ? (1 ? 0.1)(sk ? xk )
? 0.9sk ? 0.2xk

阶段:将5年运输计划看成5个阶段的决策问题。k=1,2,3,4,5 状态变量 sk :第k阶段初完好卡车数量 ,其中 s1 ? 500. 决策变量 xk :表示第k 阶段分配给超负荷运输的卡车数量。

显然,分配给低负荷的卡车数为

sk ? xk

注:这里视 sk , xk 为连续变量。若 sk =0.6表示有一辆卡
车在第k年度有60℅的时间处于完好状态。 xk =0.7表示有 一辆卡车在第k年度有70℅时间在超负荷运输等等。 状态转移方程: sk ?1 ? (1 ? 0.3) xk ? (1 ? 0.1)(sk ? xk )
? 0.9sk ? 0.2xk

k ? 1,2,3,4,5

阶段指标函数 g k ( xk ) :表示第 k 年度利润。 k ? 1,2,3,4,5

gk ( xk ) ? 25xk ?16(sk ? xk )
? 16sk ? 9 xk

k ? 1,2,3,4,5

最优指标函数

f k (sk )

:第 k 年度初完好车辆数为 sk 时,采

用最优策略到第 5 年末所产生的最大利润。

逆序递推式为:

? f k (sk ) ? ? ? f 6 (s6 ) ? 0
1) k=5时

0 ? xk ? s k

max ?g k ( x k ) ? f k ?1 ( s k ?1 )? k ? 5,4,3,2,1

f 5 ( s5 ) ? max {g 5 ( x5 ) ? f 6 ( s 6 )}
0? x5 ? s5

(注意到此时 f 6 (s6 ) =0)

? max {g 5 ( x5 )}
0 ? x5 ? s 5

? max {16 s5 ? 9 x5 }
0? x5 ? s5

f5

f 5 ( s5 ) ? max {16 s5 ? 9 x5 }
0? x5 ? s5

? 16s5 ? 9s5 ? 25s5

16s5

此时 2) k=4 时

x ? s5
* 5

o

s5

x5

f 4 ( s 4 ) ? max {g 4 ( x 4 ) ? f 5 ( s5 )}
0 ? x4 ? s 4

? max {16 s4 ? 9 x4 ? 25 s5 }
0 ? x4 ? s 4

? max {16 s4 ? 9 x4 ? 25(0.9s4 ? 0.2 x4 )}
0 ? x4 ? s 4
0? x4 ? s 4

? max {38.5s4 ? 4 x4 }

同理,只有当 x4 ? s4

时,函数 38.5s4 ? 4 x4

才能达到极大值。故有
* x4 ? s4

f 4 (s4 ) ? 42.5s4
f 3 ( s 3 ) ? max {g 3 ( x3 ) ? f 4 ( s 4 )}
0 ? x3 ? s 3

3) k=3 时

? max {16 s3 ? 9 x3 ? 42.5s4 }
0? x3 ? s3

? max {16 s3 ? 9 x3 ? 42.5(0.9s3 ? 0.2 x3 )}
0? x3 ? s3

? max {54.25 s3 ? 0.5 x3}
0? x3 ? s3

不难得到

* x3 ? s3

f 3 (s3 ) ? 54.75s3

f 3 (s3 ) ? 54.75s3

4) k=2 时
f2
65.275s2

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

? max {16 s2 ? 9 x2 ? 54.75(0.9s2 ? 0.2 x2 )}
0? x2 ? s 2

33.47s2

? max {65.275 s2 ? 1.95 x2 }
0 ? x2 ? s 2

o

x2

可见,只有当 x2 ? 0

时,函数 65.275s2 ? 1.95x2 才能达到
f 2 (s2 ) ? 65.275s2

极大值。故有

* x2 ? 0,

5) k=1 时

f1 ( s1 ) ? f1 (500 ) ? max {g1 ( x1 ) ? f 2 ( s2 )}
0? x1 ? s1

? max {16 s1 ? 9 x1 ? 65.275 s2 }
0? x1 ?500

? max {16 s1 ? 9 x1 ? 65.275(0.9s1 ? 0.2 x1 )}
0? x1 ?500

? max {74.7475 s1 ? 4.055 x1}
0? x1 ?500

s1 ? 4.055x1 才能达到 同理,只有当 x1 ? 0 时,函数 74.7475
极大值。故有
* x1 ? 0,

f1 (s1 ) ? 74.7475 s1 ? 74.7475? 500 ? 37373 .75 (万元)

所对应的最优策略分别为:

? x1 ?0

时,由状态转移方程

sk ?1 ? 0.9sk ? 0.2xk

s2 ? 0.9s1 ? 0.2 x1 ? 0.9 ? 500 ? 450
* ? 0, 由 x2



s3 ? 0.9s2 ? 0.2x2 ? 0.9 ? 450 ? 405
* ? s3 且 再由 x3

s4 ? 0.9s3 ? 0.2x3 ? 0.9 ? 405? 0.2 ? 405 ? 283.5
* x4 ? s4

? s5 ? 0.9s4 ? 0.2x4 ? 0.9 ? 283.5 ? 0.2 ? 283.5 ? 198.45 ? s6 ? 0.9s5 ? 0.2x5 ? 0.9 ?198.45 ? 0.2 ?198.45 ? 138.15

* x5 ? s5

第一年初:500辆车全部用于低负荷运输。
第二年初:还有450辆完好的车,也全部用于低负荷运输。 第三年初:还有405辆完好的车,全部用于超负荷运输。 第四年初:还有238.5辆完好的车,全部用于超负荷运输。 第五年初:还有198.45辆完好的车,全部用于超负荷运输。 到第五年末,即第六年初,还剩余138.15辆完好的车。 实现最大利润
f1 (s1 ) ? 3.74 (亿元)

第5讲

背包问题

一般的提法为:一旅行者携带背包去登山。已知他所能承受 的背包重量的极限为a (千克),现有n种物品可供他选择装入 背包。第i种物品的单位重量为 a i (千克),其价值(可以是表 明本物品对登山者的重要性指标)是携带数量 x i 的函数
g i ( xi )(i=1,2,…n).问旅行者应如何选择携带物品的件

数,以使总价值最大? 此模型解决的是运输工具包括卫星的最优装载问题。 其数学模型为:

设 x i 为第 i 种物品装入的件数,则背包问题可归结为如下
形式的整数规划模型:
max z ? ? g i ( xi )
i ?1 n

?n ?? ai xi ? a ? i ?1 ? 整数 (i ? 1,2, ?, n) ? xi ? 0

下面从一个例子来分析动态规划建模。 例7 /P218 有一辆最大货运量为10 t 的卡车,用以装载3种 货物,每种货物的单位重量及相应单位价值如表7-4 所示。

应如何装载可使总价值最大?

表 7- 4

货物编号i 单位重量(t) 单位价值 ci

1 3 4

2 4 5

3 5 6

设第 i 种货物装载的件数为 x i (i ? 1,2,3), 则问题可表为:
max z ? 4 x1 ? 5x2 ? 6 x3

?3x1 ? 4 x2 ? 5 x3 ? 10 ? xi ? 0, 整数 (i ? 1,2,3) ?

阶段k: 将可装入物品按1,2,3的顺序排序,每段装入一 种物品,共划分3个阶段,即k=1,2,3.

s1 ? s2 ? 3x1

3 x1
货物1

s2 ? s3 ? 4 x2

4 x2
货物2

s3 ? s4 ? 5x3

5 x3
货物3

s4 ? 10

g1 ( x1 ) ? 4 x1

g 2 ( x2 ) ? 5x2

g3 ( x3 ) ? 6 x3

状态变量 s k ?1 :在第k段开始时,背包中允许装入前k种 物品的总重量。 决策变量 xk :装入第k种物品的件数。 状态转移方程:

sk ?1 ? sk ? ak xk

最优指标函数 f k (sk ?1 ) :在背包中允许装入物品的总重量不超 过 s k ?1 kg,采取最优策略只装前k种物品时的最大使用价值

s1 ? s2 ? 3x1

3 x1
货物1

s2 ? s3 ? 4 x2

4 x2
货物2

s3 ? s4 ? 5x3

5 x3
货物3

s4 ? 10

g1 ( x1 ) ? 4 x1

g 2 ( x2 ) ? 5x2

g3 ( x3 ) ? 6 x3

由此可得动态规划的顺序递推方程为:

? f k ( sk ?1 ) ? ? ? f 0 ( s1 ) ? 0

0? ak xk ? sk ?1

max ?g k ( xk ) ? f k ?1 ( sk ?1 ? ak xk )? k ? 1,2,3

K=1 时

f1 ( s2 ) ? max {g1 ( x1 ) ? f 0 ( s1 )} ? max {4 x1}
0?3 x1 ? s2 x1为整数

0?3 x1 ? s2 x1为整数

s1 ? s2 ? 3x1

3 x1
货物1

s2 ? s3 ? 4 x2

4 x2
货物2

s3 ? s4 ? 5x3

5 x3
货物3

s4 ? 10

g1 ( x1 ) ? 4 x1

g 2 ( x2 ) ? 5x2

g3 ( x3 ) ? 6 x3

K=1 时

f1 ( s2 ) ? max {g1 ( x1 ) ? f 0 ( s1 )}
0?3 x1 ? s2 x1为整数

? max {4 x1}
0?3 x1 ? s2 x1为整数

注意到: s2 ?{0,1,?,10}
{4 x1} ? max {4 x1} 例如: s2 ? 7 时, f1 (7) ? 0max x ? 0 ,1, 2 ?3 x ? 7
x1为整数
1
1

? max{ 0,4,8} ? 8

* x1 ?2

其它计算结果见表7-5:

表 7- 5

s2
0 1 2 3 4 5 6 7 8 9 10

x1
0
4 ×0 4 ×0 4 ×0 4 ×0 4 ×0 4 ×0 4 ×0 4 ×0 4 ×0 4 ×0 4 ×0

4 x1
1 2 3

? f1 ( s 2 ) x1

4 ×1 4 ×1 4 ×1 4 ×1 4 ×1 4 ×1 4 ×1 4 ×1

4 ×2 4 ×2 4 ×2 4 ×2 4 ×2

4 ×3 4 ×3

0 0 0 4 4 4 8 8 8 12 12

0 0 0 1 1 1 2 2 2 3 3

s1 ? s2 ? 3x1

3 x1
货物1

s2 ? s3 ? 4 x2

4 x2
货物2

s3 ? s4 ? 5x3

5 x3
货物3

s4 ? 10

g1 ( x1 ) ? 4 x1

g 2 ( x2 ) ? 5x2

g3 ( x3 ) ? 6 x3

K=2 时

f 2 ( s3 ) ? max {g 2 ( x2 ) ? f1 ( s2 )}
0 ? 4 x 2 ? s3 x2为整数

? max {5 x2 ? f1 ( s3 ? 4 x2 )}
0 ? 4 x 2 ? s3 x2为整数

其中

s3 ?{0,1,?,10}

max {5 x2 ? f1 (10 ? 4 x2 )} 例如:s3 ? 10 时, f 2 ( s3 ) ? f 2 (10) ? 0? 4 x ?10
x2为整数
2

? max {5 x2 ? f1 (10 ? 4 x2 )} ? max{0 ? f1 (10),5 ? f1 (6),10 ? f1 (2)}
x2 ?0 ,1, 2

? max{0 ? f1 (10),5 ? f1 (6),10 ? f1 (2)}
? max{ 0 ? 12,5 ? 8,10 ? 0} ? 13
表 7- 5
* x2 ?1

s2
0 1 2 3 4 5 6 7 8 9 10

x1
0 1

4 x1
2 3

? f1 ( s 2 ) x1

4 ×0 4 ×0 4 ×0 4 ×0 4 ×0 4 ×0 4 ×0 4 ×0 4 ×0 4 ×0 4 ×0

4 ×1 4 ×1 4 ×1 4 ×1 4 ×1 4 ×1 4 ×1 4 ×1

4 ×2 4 ×2 4 ×2 4 ×2 4 ×2

4 ×3 4 ×3

0 0 0 4 4 4 8 8 8 12 12

0 0 0 1 1 1 2 2 2 3 3

其它计算结果见表7-6:
表 7- 6

s3

x2
0

5x2 ? f1 (s3 ? 4 x2 )

1

2

f 2 (s3 ) x?
2

0 1 2 3 4 5 6 7 8 9 10

5×0+0 … … … … 5×0+4 5×1+0 …

0

0

5

1

5×0+12

5 ×1+ 8

5 ×2+0

13

1

s1 ? s2 ? 3x1

3 x1
货物1

s2 ? s3 ? 4 x2

4 x2
货物2

s3 ? s4 ? 5x3

5 x3
货物3

s4 ? 10

g1 ( x1 ) ? 4 x1

g 2 ( x2 ) ? 5x2

g3 ( x3 ) ? 6 x3

K=3 时

f 3 ( s4 ) ? f 3 (10) ? max {g 3 ( x3 ) ? f 2 ( s3 )}
0?5 x3 ? s 4 x3为整数

{6 x3 ? f 2 (10 ? 5 x3 )} ? max {6 x3 ? f 2 (10 ? 5 x3 )} ? xmax ? 0,1, 2
0?5 x3 ?10 x3为整数
3

? max{ 0 ? f 2 (10),6 ? f 2 (5),12 ? f 2 (0)}

表 7- 6

s3

x2
0

5x2 ? f1 (s3 ? 4 x2 )

1

2

f 2 (s3 ) x?
2

0 1 2 3 4 5 6 7 8 9 10

5×0+0 … … … … 5×0+4 5×1+0 …

0

0

5

1

5×0+12

5×1+8

5 ×2+0

13

1

? max{ 0 ? f 2 (10),6 ? f 2 (5),12 ? f 2 (0)}
? max{ 0 ? 13,6 ? 5,12 ? 0} ? 13
* x3 ?0

s1 ? s2 ? 3x1

3 x1
货物1

s2 ? s3 ? 4 x2

4 x2
货物2

s3 ? s4 ? 5x3

5 x3
货物3

s4 ? 10

g1 ( x1 ) ? 4 x1

g 2 ( x2 ) ? 5x2

g3 ( x3 ) ? 6 x3



* x3 ?0

* ? 10 ? 0 ? 10 再由状态转移方程 s3 ? s4 ? 5x3

表 7- 6

s3

x2
0

5x2 ? f1 (s3 ? 4 x2 )

1

2

f 2 (s3 ) x?
2

0 1 2 3 4 5 6 7 8 9 10

5×0+0 … … … … 5×0+4 5×1+0 …

0

0

5

1

5×0+12

5 ×1+8

5 ×2+0

13

1

* x ? 2 ?1

* 再由状态转移方程 s2 ? s3 ? 4x2 ? 10 ? 4 ? 6

表 7- 5

s2
0 1 2 3 4 5 6 7 8 9 10

x1
0 4 ×0 4 ×0 4 ×0 4 ×0 4 ×0 4 ×0 4 ×0 4 ×0 4 ×0 4 ×0 4 ×0 1

4 x1
2 3

? f1 ( s 2 ) x1

4 ×1 4 ×1 4 ×1 4 ×1 4 ×1 4 ×1 4 ×1 4 ×1

4 ×2 4 ×2 4 ×2 4 ×2 4 ×2

4 ×3 4 ×3

0 0 0 4 4 4 8 8 8 12 12

0 0 0 1 1 1 2 2 2 3 3

* ? x1 ? 2 最大装载价值为 f3 (10) ? 13.

总结:今后解背包问题应先从k=3入手: k=3时
f 3 ( s4 ) ? f 3 (10) ? max {g 3 ( x3 ) ? f 2 ( s3 )}
0?5 x3 ? s 4 x3为整数

? max {6 x3 ? f 2 (10 ? 5 x3 )} ? max {6 x3 ? f 2 (10 ? 5 x3 )}
0?5 x3 ?10 x3为整数

x3 ? 0,1, 2

? max{ 0 ? f 2 (10),6 ? f 2 (5),12 ? f 2 (0)}
下面应有重点地从k=2中求解三个最优函数值:
f 2 (10)

f 2 (5)

f 2 (0)

K=2 时

f 2 ( s3 ) ? max {g 2 ( x2 ) ? f1 ( s2 )}
0 ? 4 x 2 ? s3 x2为整数

? max {5 x2 ? f1 ( s3 ? 4 x2 )}
0 ? 4 x 2 ? s3 x2为整数

f 2 ( s3 ) ? f 2 (10) ? max {5 x2 ? f1 (10 ? 4 x2 )}
0? 4 x2 ?10 x2为整数

? max {5 x2 ? f1 (10 ? 4 x2 )} ? max{ 0 ? f1 (10),5 ? f1 (6),10 ? f1 (2)} x ?0 ,1, 2
2

f 2 ( s3 ) ? f 2 (5) ? max {5 x2 ? f1 (5 ? 4 x2 )}
0 ? 4 x2 ? 5 x2为整数

? max {5 x2 ? f1 (5 ? 4 x2 )} ? max{ 0 ? f1 (5),5 ? f1 (1)} x ? 0 ,1
2

f 2 ( s3 ) ? f 2 (0) ? max {5 x2 ? f1 (0 ? 4 x2 )}
0 ? 4 x2 ? 0 x2为整数

? max {5 x2 ? f1 (0 ? 4 x2 )} ? max{ 0 ? f1 (0)}
x2 ? 0

所以从第一阶段应有重点地求以下四个数:
f 1 ( 0)

f1 (1)

f1 (2)

f1 (5)

f1 (6)

f1 (10)

K=1 时
0?3 x1 ? 0 x1为整数

f1 ( s2 ) ? max {g1 ( x1 ) ? f 0 ( s1 )} ? max {4 x1}
0?3 x1 ? s2 x1为整数
0?3 x1 ? s2 x1为整数

f1 (0) ? max {4 x1} ? max {4 x1} ? 0
x1 ? 0

* x1 ?0 * x1 ?0

f1 (1) ? max {4 x1} ? max {4 x1} ? 0
0?3 x1 ?1 x1为整数
x1 ? 0

f1 (2) ? max {4 x1} ? max {4 x1} ? 0
0?3 x1 ? 2 x1为整数
x1 ? 0

* x1 ?0

f1 (5) ? max {4 x1} ? max {4 x1} ? max{ 0,4} ? 4
0?3 x1 ?5 x1为整数
x1 ? 0 ,1

* x1 ?1

f1 (6) ? max {4 x1} ? max {4 x1} ? max{ 0,4,8} ? 8
0?3 x1 ? 6 x1为整数
x1 ? 0 ,1, 2

* x1 ?2

f1 (10) ? max {4 x1} ? max {4 x1} ? max{ 0,4,8,12} ? 12
0?3 x1 ?10 x1为整数
x1 ? 0 ,1, 2 , 3

* x1 ?3

由此逐一逆推代回上式: f1 (0) ? 0,
f 2 (0) ? max{5 x2 ? f1 (0 ? 4 x2 )} ? max{ 0 ? f1 (0)} ? 0,
x2 ? 0

* x2 ?0

f1 (2) ? max {4 x1} ? max {4 x1} ? 0
0?3 x1 ? 2 x1为整数
x1 ? 0

* x1 ?0

f1 (5) ? max {4 x1} ? max{4 x1} ? max{ 0,4} ? 4
0?3 x1 ?5 x1为整数
x1 ? 0 ,1

* x1 ?1

f1 (6) ? max {4 x1} ? max {4 x1} ? max{ 0,4,8} ? 8
0?3 x1 ? 6 x1为整数
x1 ? 0 ,1, 2

* x1 ?2

f1 (10) ? max {4 x1} ? max {4 x1} ? max{ 0,4,8,12} ? 12
0?3 x1 ?10 x1为整数
x1 ? 0 ,1, 2 , 3

* x1 ?3

由此逐一逆推代回上式:

f1 (1) ? 0, x1 ? 0
*

f 2 (5) ? max{ 0 ? f1 (5),5 ? f1 (1)}
? max{ 0 ? 4,5 ? 0} ? 5
* x2 ?1

f1 (2) ? max {4 x1} ? max {4 x1} ? 0
0?3 x1 ? 2 x1为整数
x1 ? 0

* x1 ?0

f1 (5) ? max {4 x1} ? max{4 x1} ? max{ 0,4} ? 4
0?3 x1 ?5 x1为整数
x1 ? 0 ,1

* x1 ?1

f1 (6) ? max {4 x1} ? max {4 x1} ? max{ 0,4,8} ? 8
0?3 x1 ? 6 x1为整数
x1 ? 0 ,1, 2

* x1 ?2

f1 (10) ? max {4 x1} ? max {4 x1} ? max{ 0,4,8,12} ? 12
0?3 x1 ?10 x1为整数
x1 ? 0 ,1, 2 , 3

* x1 ?3

由此逐一逆推代回上式:

f 2 (10) ? max{ 0 ? f1 (10),5 ? f1 (6),10 ? f1 (2)}
? max{ 0 ? 12,5 ? 8,10 ? 0} ? 13
* x2 ?1

最后

f3 (10) ? max{ 0 ? f 2 (10),6 ? f 2 (5),12 ? f 2 (0)}
? max{ 0 ? 13,6 ? 5,12 ? 0} ? 13
* x3 ?0

* ?0 最优策略: x3

再由状态转移方程
* x ? 2 ? 1 再由状态转移方程

s3 ? s4 ? 5x ? 10 ? 0 ? 10
* 3
* 2

* ? x s2 ? s3 ? 4x ? 10 ? 4 ? 6 1 ?2

最大装载价值为

f 3 (10) ? 13.

7.9(3)/P-230 用动态规划方法求解:
2 max F ? 4x1 ? 9x2 ? 2x3

?2 x1 ? 4 x2 ? 3x3 ? xi ? 0 ?

? 10 (i ? 1,2,3)

解:我们用背包问题动态规划求解的思路: 人为的划分三个阶段:k=1,2,3 阶段指标函数及其他分配情况如下图:
s1 ? s2 ? 2 x1

2 x1
1

s2 ? s3 ? 4 x2

4 x2
2
g 2 ( x2 ) ? 9 x2

s3 ? s4 ? 3x3

3 x3
3

s4 ? 10

g1 ( x1 ) ? 4 x1

2 g3 ( x3 ) ? 2 x3

s1 ? s2 ? 2 x1

2 x1
1

s2 ? s3 ? 4 x2

4 x2
2
g 2 ( x2 ) ? 9 x2

s3 ? s4 ? 3x3

3 x3
3

s4 ? 10

g1 ( x1 ) ? 4 x1

2 g3 ( x3 ) ? 2 x3

动态规划的顺序递推方程为:

? f k ( sk ?1 ) ? ? ? f 0 ( s1 ) ? 0

0? ak xk ? sk ?1

max ?g k ( xk ) ? f k ?1 ( sk ?1 ? ak xk )? k ? 1,2,3

例(二维背包) 有一辆最大货运量为13t、最大容量为10 件的卡车,用以装载3种货物,每种货物的单位重量及相 应单位价值如下表所示。应如何装载可使总价值最大?
货物编号i 单位重量(t) 单位价值 ci 1 1 4 2 3 5 3 6 8

解:设装载第i种货物的件数为 x i(i=1,2,3),则问题可表述为
max z ? 4x1 ? 5x2 ? 8x3

? x1 ? x2 ? x3 ? 10 ? s.t ? x1 ? 3 x2 ? 6 x3 ? 13 ? ? xi ? 0, i ? 1,2,3 ? xi ? N

u1 ? u2 ? x1 s1 ? s2 ? x1

a1 ? 1

a2 ? 3
u2 ? u3 ? 3x2 s2 ? s3 ? x2

a3 ? 6
u3 ? s4 ? 6 x3 s3 ? s4 ? x3

x1
1

3 x2
2
g 2 ( x2 ) ? 5x2

6 x3
3

u4 ? 13 s4 ? 10

g1 ( x1 ) ? 4 x1

g3 ( x3 ) ? 8x3

关于重量的约束: uk ? uk ?1 ? ak xk 关于件数的约束: 基本方程式:

k ? 1, 2, 3 k ? 1, 2, 3

sk ? sk ?1 ? xk

f (s , u ) ? ? ? k k ?1 k ?1 ? ? ? f 0 (s1 , u1 ) ? 0

0? xk ? sk ?1 0? ak xk ?uk ?1

max ?g k ( xk ) ? f k ?1 (sk ?1 ? xk , u k ?1 ? ak xk )? k ? 1,2,3

u1 ? u2 ? x1 s1 ? s2 ? x1

a1 ? 1

a2 ? 3
u2 ? u3 ? 3x2 s2 ? s3 ? x2

a3 ? 6
u3 ? s4 ? 6 x3 s3 ? s4 ? x3

x1
1

3 x2
2
g 2 ( x2 ) ? 5x2

6 x3
3

u4 ? 13 s4 ? 10

g1 ( x1 ) ? 4 x1

g3 ( x3 ) ? 8x3

? f k ( sk ?1 , uk ?1 ) ? ? ? ? ? f 0 ( s1 , u1 ) ? 0

u 0? xk ? min{sk ?1 ,[ k ?1 ]} ak

max

?g k ( xk ) ? f k ?1 (sk ?1 ? xk , uk ?1 ? ak xk )?

k ? 1,2,3

例5 货郎担问题 货郎担问题也叫推销商问题(traveling salesman problem), 其一般提法为:有n个城市,用1,2,…,n表示,城i, j之间 的距离为 dij ,有一个货郎从城1出发到其他城市一次且仅一 次,最后回到城市1,怎样选择行走路线使总路程最短?
2

6
8 3

5 4

2
4

8 9 10
5 6 2 1

3

6
5 8 7 7

4 5

5
3 4 8 4 5

11

4

1 3

13 12
3 3

7

2

6
8 3

5 4 5 3

2
4

8 9 10
5 6 2 1

3

6 5 8

4
7
7

11

4

1 3

5
8

13 12
3

4
4 5

3

7

一、动态规划解 阶段变量k:按所经过的城市个数划分阶段k, k=1,2,…,n-1.

状态变量 sk :设第k 阶段到达城市i 时途中所经过的k个城市
集合为S,则 sk ? (S , i) 其中
S ? {2,3,?, i ? 1, i ? 1,?, n}

| S |? k

2

6
8
3

5 4 5 3

2
4

8 9 10
5 6 2

3

6 5 8 7 7

4 5

11

4

1 3

13

4
8 4 5

1
3

12

3

7

决策变量 xk :第k 阶段到达城市i 的最短路线上邻接i 的前一 个城市 j 。 j ? 2,3,?, n.

例如:x3 ({2,3,4},5) ? 3 ,表示推销商从城1出发途径城市{2,3,4}
到达城市5时,须先途经城市{2,4}到达城市3,再奔城市5。

2

6
8 3

5 4 5 3

2
4

8 9 10
5 6 2 1

3

6 5 8

4
7
7

11

4

1 3

5
8

13 12
3

4
4 5

3

7

阶段指标函数 d ji: 设从城市1出发,第k-1阶段到达到城市j, 则城市j与下一阶段(第k阶段)的目的地城市i之间的距离为 d ji 最优指标函数 f k (S , i) :从城市1出发,经过S中k个城市,到 达城市i的最短距离.

2
4

1
5

3

则动态规划的顺序递推关系为:

min{ f k ?1 ( S \ j , j ) ? d ji } ? f k (S , i) ? j?S ? ? f 0 (? , i ) ? d1i , i ? 2,3, ? , n, k ? 1,2, ? , n ? 1.
最后算出 f n?1 ( N ,1), N ? {2,3,?, n} ,即为全程的最短距离,同时
可得最优策略,即最优行走路线. 例1 已知 4个城市间距离如表1,求从城市1出发,经其与城

市一次且仅一次最优回到城市1的最短路与距离。

城 城 市 1 2 3 4 0 8 5 6 6 0 8 5 7 9 0 5 9 7 8 0 市 1 2 3 4

解:由边界条件知:

f0 (? ,1) ? d11 ? 0

f0 (? ,2) ? d12 ? 6

f0 (? ,3) ? d13 ? 7

f0 (? ,4) ? d14 ? 9

城 城 市 市 1 2 3 4

1 2 3 4

0 8 5 6

6 0 8 5

7 9 0 5

9 7 8 0

当k=1时,从城市1出发,经过1个城市到达城市i的最短距离 为:
f1 ({3},2) ? f 0 (? ,3) ? d32 ? 7 ? 8 ? 15 f1 ({4},2) ? f 0 (? ,4) ? d42 ? 9 ? 5 ? 14

城 城 市 1 2 3 4 0 8 5 6 6 0 8 5 7 9 0 5 9 7 8 0 市 1 2 3 4

f1 ({2},3) ? f 0 (? ,2) ? d23 ? 6 ? 9 ? 15 f1 ({4},3) ? f 0 (? ,4) ? d43 ? 9 ? 5 ? 14 f1 ({2},4) ? f 0 (? ,2) ? d24 ? 6 ? 7 ? 13 f1 ({3},4) ? f 0 (? ,3) ? d34 ? 7 ? 8 ? 15

f1 ({3},4) ? 15
城 城 市 市 1

f1 ({4},3) ? 14
2 3 4

1 2 3 4

0 8 5 6

6 0 8 5

7 9 0 5

9 7 8 0

当k=2时,从城市1出发,途经2个城市到达城市i的最短距离 为

f 2 ({3,4},2) ? min{f1 ({3},4) ? d 42 , f1 ({4},3) ? d32 } ? min{ 15 ? 5,14 ? 8} ? 20
* x2 ({3,4},2) ? 4

即从城市1出发,途经2个城市{3,4}奔城2,在到2之前应为4 。

f1 ({2},4) ? 13
城 城 市 市 1 2

f1 ({4},2) ? 14
3 4

1 2 3 4

0 8 5 6

6 0 8 5

7 9 0 5

9 7 8 0

f 2 ({2,4},3) ? min{f1 ({2},4) ? d 43 , f1 ({4},2) ? d 23} ? min{ 13 ? 5,14 ? 9} ? 18
* x2 ({2,4},3) ? 4

即从城市1出发,途经2个城市{2,4}奔城3,在到3之前应为4。

f1 ({2},3) ? 15
城 城 市 市 1 2

f1 ({3},2) ? 15
3 4

1 2 3 4

0 8 5 6

6 0 8 5

7 9 0 5

9 7 8 0

f 2 ({2,3},4) ? min{f1 ({2},3) ? d34 , f1 ({3},2) ? d 24 } ? min{ 15 ? 8,15 ? 7} ? 22
* x2 ({2,3},4) ? 2

即从城市1出发,途经2个城市{2,3}奔城4,在到4之前应为2。

f 2 ({2,3},4) ? 22
城 城 市 市 1

f 2 ({2,4},3) ? 18
2 3

f 2 ({3,4},2) ? 20
4

1 2 3 4

0 8 5 6

6 0 8 5

7 9 0 5

9 7 8 0

当k=3时,从城市1出发,途经3个城市到达城市1的最短距离

f3 ({2,3,4},1) ? min{f 2 ({2,3},4) ? d41 , f 2 ({2,4},3) ? d31 , f 2 ({3,4},2) ? d21} ? min{22 ? 6,18 ? 5,20 ? 8} ? 23
* x3 ({2,3,4},1) ? 3
* 逆推回去 x2 ({2,4},3) ? 4; * x1 ({2},4) ? 2

货郎担的最短路线是1 →2→4→3→1。 行走距离为23。

第七讲:设备更新问题 企业中经常会遇到一台设备应该使用多少年更新最合算的问 题。一般来说,一台设备在比较新时,年运转量大,经济收入 高,故障少,维修费用少,但随着使用年限的增加,年运转量

减少因而收入减少,故障变多,维修费用增加。如果更新可提
高年净收入,但是当年要支出一笔数额较大的购买费。 设备更新的一般提法为:在已知一台设备的效益函数 r (t ) ,维

修费用函数 u(t ) 及更新费用函数 c (t )条件下,要求在n年内的
每年年初作出决策,是继续使用旧设备还是更换一台新的,使

使n年总效益最大。

例11(P227) 某台新设备的年效益及年均维修费、更新净费用如 表7-15所示。试确定今后5年内的更新策略,使总收益最大。 表 7-15
役龄 项目

单位:万元
0 5 1 2 3 3.75 4 3 2.5 3 5 2.5 3 3.5

效益 维修费 更新费

rk (t )

4.5 4

u k (t )

0.5 1

1.5 2

ck (t )

0.5 1.5 2.2 2.5

解:以年限划分阶段k:1,2,3,4,5
s1 ? 0

x1
1

s2 ? 1

x2
2
g 2 ( x2 )

s3

x3
3
g3 ( x3 )

s4

x4
4
g 4 ( x4 )

s5

x5
5
g 5 ( x5 )

s6

g1 ( x1 )

? K 第k年初保留使用(keep) 决策变量 xk : xk ? ? ? R 第k年初更新(replacement)
状态变量 sk : 第k年初,设备已使用过的年数,称役龄。

?sk ? 1 xk ? K 状态转移方程:sk ?1 ? ? xk ? R ? 1

役龄

0 5

1

2

3 3.75

4 3 2.5 3

5 2.5 3 3.5

项目

效益 维修费 更新费

rk (t )

4.5 4

uk (t )

0.5 1

1.5 2

ck (t )

0.5 1.5 2.2 2.5

r (t )
u(t )

在第k年设备已使用过t年(或役龄为t年),再使用1
年时的效益。

在第k年设备已使用过t年(或役龄为t年),再使用1年
时的维修费用。

c(t )

在第k年卖掉一台役龄为t年的设备,买进一台新的设 备的更新净费用。

役龄 项目

0 5

1

2

3 3.75

4 3 2.5 3

5 2.5 3 3.5

效益 维修费 更新费

rk (t )

4.5 4

uk (t )

0.5 1

1.5 2

ck (t )

0.5 1.5 2.2 2.5

即:c(t ) ? “买一部新机器的费用”-“卖一部t年役龄的旧机 器 的收益”。 ? rk ( sk ) ? u k ( sk ) 阶段指标函数: g k ( xk ) ? ? ?rk (0) ? u k (0) ? ck ( sk )

xk ? K xk ? R

最优指标函数 f k ( s k ):第k年初,使用一台已用了 sk 年的设 备,到第5年末的最大效益,有

? rk ( sk ) ? u k ( sk ) ? f k ?1 ( sk ? 1) xk ? K f k ( sk ) ? max ? ?rk (0) ? u k (0) ? ck ( sk ) ? f k ?1 (1) xk ? R
按逆序建立递推式:

? f k ( sk ) ? ? ? f 6 ( s6 ) ? 0

xk ? K or R

max ?g k ( xk ) ? f k ?1 ( sk ?1 )? k ? 5,4,3,2,1

下面用逆序法求解:

s1 ? 0

x1
1

s2 ? 1

x2
2
g 2 ( x2 )

s3

x3
3
g3 ( x3 )

s4

x4
4
g 4 ( x4 )

s5

x5
5
g5 ( x5 )

s6

g1 ( x1 )

K=5时:
f 5 ( s5 ) ? max {g 5 ( x5 ) ? f 6 ( s6 )}
x5 ? K or R

? r5 ( s5 ) ? u5 ( s5 ) ? max? ?r5 (0) ? u5 (0) ? c5 ( s5 )
标函数值:

x5 ? K x5 ? R

此时, s 5 的所有可能取值为:1,2,3,4。下分别求最优指

r5 (1) ? u5 (1) ? f 5 (1) ? max ? ?r5 (0) ? u5 (0) ? c5 (1)

x5 ? K x5 ? R

役龄 项目

0 5

1

2

3 3.75

4 3 2.5 3

5 2.5 3 3.5

效益 维修费 更新费

rk (t )

4.5 4

uk (t )

0.5 1

1.5 2

ck (t )

0.5 1.5 2.2 2.5

r5 (1) ? u5 (1) ? f 5 (1) ? max ? ?r5 (0) ? u5 (0) ? c5 (1)
? 4.5 ? 1 ? ? max? ? ? 3.5, ?5 ? 0.5 ? 1.5?

x5 ? K x5 ? R

* (1) ? K 此时,x5

役龄 项目

0 5

1

2

3 3.75

4 3 2.5 3

5 2.5 3 3.5

效益 维修费 更新费

rk (t )

4.5 4

uk (t )

0.5 1

1.5 2

ck (t )

0.5 1.5 2.2 2.5

r5 ( 2) ? u5 ( 2) ? f 5 ( 2) ? max ? ?r5 (0) ? u5 (0) ? c5 ( 2)
? 4 ? 1.5 ? ? max? ? ? 2.5, ?5 ? 0.5 ? 2.2?

x5 ? K x5 ? R

* (2) ? K 此时, x5

役龄 项目

0 5

1

2

3 3.75

4 3 2.5 3

5 2.5 3 3.5

效益 维修费 更新费

rk (t )

4.5 4

uk (t )

0.5 1

1.5 2

ck (t )

0.5 1.5 2.2 2.5

r5 (3) ? u5 (3) ? f 5 (3) ? max ? ?r5 (0) ? u5 (0) ? c5 (3)
? 3.75 ? 2 ? ? max? ? ? 2, ?5 ? 0.5 ? 2.5?

x5 ? K x5 ? R

* (3) ? R 此时,x5

役龄 项目

0 5

1

2

3 3.75

4 3 2.5 3

5 2.5 3 3.5

效益 维修费 更新费

rk (t )

4.5 4

uk (t )

0.5 1

1.5 2

ck (t )

0.5 1.5 2.2 2.5

r5 ( 4) ? u5 ( 4) ? f 5 ( 4) ? max ? ?r5 (0) ? u5 (0) ? c5 ( 4)
? 3 ? 2.5 ? ? max? ? ? 1.5, ?5 ? 0.5 ? 3?

x5 ? K x5 ? R

* (4) ? R 此时,x5

x5 s5
1 2 3 4

x5 ? K ? r5 (s5 ) ? u5 (s5 ) ? ?r5 (0) ? u5 (0) ? c5 (s5 ) x5 ? R
K
3.5 2.5 1.75 0.5

R
3 2.3 2 1.5

f 5 ( s5 )
3.5 2.5 2 1.5

* x5

K K

R R

K=5时最优值表

x5 s5
1 2 3 4

f5 (s5 ) x5
3.5 2.5 2 1.5

*

K K

R R

s1 ? 0

x1
1

s2 ? 1

x2
2
g 2 ( x2 )

s3

x3
3
g3 ( x3 )

s4

x4
4
g 4 ( x4 )

s5

x5
5
g5 ( x5 )

s6

g1 ( x1 )

K=4时:
f 4 ( s4 ) ? max {g 4 ( x4 ) ? f 5 ( s5 )}
x4 ? K or R

? r4 ( s4 ) ? u 4 ( s4 ) ? f 5 ( s4 ? 1) ? max ? ?r4 (0) ? u 4 (0) ? c4 ( s4 ) ? f 5 (1)

x4 ? K x4 ? R

此时, s 4 的所有可能取值为:1,2,3。下分别求最优指
标函数值:

? r4 (1) ? u 4 (1) ? f 5 (1 ? 1) f 4 (1) ? max ? ?r4 (0) ? u 4 (0) ? c4 (1) ? f 5 (1)

x4 ? K x4 ? R

K=5时最优值表 役龄 项目

0 5

1

2

3 3.75

4 3 2.5 3

5 2.5 3 3.5

x5 s5
1 2 3 4

效益 维修费 更新费

rk (t )

4.5 4

f5 (s5 ) x5
3.5 2.5 2 1.5

*

uk (t )

0.5 1

1.5 2

ck (t )

0.5 1.5 2.2 2.5

K K

R R

? r4 (1) ? u 4 (1) ? f 5 (1 ? 1) f 4 (1) ? max ? ?r4 (0) ? u 4 (0) ? c4 (1) ? f 5 (1)

x4 ? K x4 ? R

? 4.5 ? 1 ? 2.5 ? * ? max? ? 6 . 5 , 此时, x )?R ? 4 (1 ?5 ? 0.5 ? 1.5 ? 3.5?

K=5时最优值表 役龄 项目

0 5

1

2

3 3.75

4 3 2.5 3

5 2.5 3 3.5

x5 s5
1 2 3 4

效益 维修费 更新费

rk (t )

4.5 4

f5 (s5 ) x5
3.5 2.5 2 1.5

*

uk (t )

0.5 1

1.5 2

ck (t )

0.5 1.5 2.2 2.5

K K

R R

? r4 ( 2) ? u 4 ( 2) ? f 5 ( 2 ? 1) f 4 ( 2) ? max ? ?r4 (0) ? u 4 (0) ? c4 ( 2) ? f 5 (1)

x4 ? K x4 ? R

4 ? 1.5 ? 2 ? ? * x ? max? ? 5 . 8 , 此时, ? 4 (2) ? R ?5 ? 0.5 ? 2.2 ? 3.5?

K=5时最优值表 役龄 项目

0 5

1

2

3 3.75

4 3 2.5 3

5 2.5 3 3.5

x5 s5
1 2 3 4

效益 维修费 更新费

rk (t )

4.5 4

f5 (s5 ) x5
3.5 2.5 2 1.5

*

uk (t )

0.5 1

1.5 2

ck (t )

0.5 1.5 2.2 2.5

K K

R R

? r4 (3) ? u 4 (3) ? f 5 (3 ? 1) f 4 (3) ? max ? ?r4 (0) ? u 4 (0) ? c4 (3) ? f 5 (1)

x4 ? K x4 ? R

? 3.75 ? 2 ? 1.5 ? * x ? max? ? 5 . 5 , 此时, ? 4 (3) ? R ?5 ? 0.5 ? 2.5 ? 3.5?

K=4时最优值表

x4
f 4 (s4 ) x* 4

s4
1 2 3 6.5 5.8 5.5

R R R

s1 ? 0

x1
1

s2 ? 1

x2
2
g 2 ( x2 )

s3

x3
3
g3 ( x3 )

s4

x4
4
g 4 ( x4 )

s5

x5
5
g5 ( x5 )

s6

g1 ( x1 )

K=3时:
f 3 ( s3 ) ? max {g 3 ( x3 ) ? f 4 ( s4 )}
x3 ? K or R

? r3 ( s3 ) ? u3 ( s3 ) ? f 4 ( s3 ? 1) ? max ? ?r3 (0) ? u3 (0) ? c3 ( s3 ) ? f 4 (1)

x3 ? K x3 ? R

此时, s 3 的所有可能取值为:1,2。下分别求最优指 标函数值:

? r3 (1) ? u3 (1) ? f 4 (1 ? 1) f 3 (1) ? max ? ?r3 (0) ? u3 (0) ? c3 (1) ? f 4 (1)

x3 ? K x3 ? R

K=4时最优值表
役龄 项目

0 5

1

2

3 3.75

4 3 2.5 3

5 2.5 3 3.5

x4
f 4 (s4 ) x* 4

效益 维修费 更新费

rk (t )

4.5 4

uk (t )

0.5 1

1.5 2

s4
1 2 3 6.5 5.8 5.5

ck (t )

0.5 1.5 2.2 2.5

R R R

? r3 (1) ? u3 (1) ? f 4 (1 ? 1) f 3 (1) ? max ? ?r3 (0) ? u3 (0) ? c3 (1) ? f 4 (1)

x3 ? K x3 ? R

? 4.5 ? 1 ? 5.8 ? * ? max? ? 9 . 5 , x 1) ? R 此时, ? 3( ?5 ? 0.5 ? 1.5 ? 6.5?

K=4时最优值表
役龄 项目

0 5

1

2

3 3.75

4 3 2.5 3

5 2.5 3 3.5

x4
f 4 (s4 ) x* 4

效益 维修费 更新费

rk (t )

4.5 4

uk (t )

0.5 1

1.5 2

s4
1 2 3 6.5 5.8 5.5

ck (t )

0.5 1.5 2.2 2.5

R R R

? r3 ( 2) ? u3 ( 2) ? f 4 ( 2 ? 1) f 3 ( 2) ? max ? ?r3 (0) ? u3 (0) ? c3 ( 2) ? f 4 (1)

x3 ? K x3 ? R

? 4 ? 1.5 ? 5.5 ? * ? max? ? 8 . 8 , x 此时, ? 3 (2) ? R ?5 ? 0.5 ? 2.2 ? 6.5?

K=3时最优值表

x3 s3
1 2

f3 (s3 ) x* 3
9.5 8.8

R R

s1 ? 0

x1
1

s2 ? 1

x2
2
g 2 ( x2 )

s3

x3
3
g3 ( x3 )

s4

x4
4
g 4 ( x4 )

s5

x5
5
g5 ( x5 )

s6

g1 ( x1 )

K=2时:
f 2 ( s2 ) ? max {g 2 ( x2 ) ? f 3 ( s3 )}
x2 ? K or R

? r2 ( s2 ) ? u 2 ( s2 ) ? f 3 ( s2 ? 1) ? max ? ?r2 (0) ? u 2 (0) ? c2 ( s2 ) ? f 3 (1)
此时, s 2 只能取1。所以

x2 ? K x2 ? R

? r2 (1) ? u 2 (1) ? f 3 (1 ? 1) f 2 (1) ? max ? ?r2 (0) ? u 2 (0) ? c2 (1) ? f 3 (1)

x2 ? K x2 ? R

K=3时最优值表
役龄 项目

0 5

1

2

3 3.75

4 3 2.5 3

5 2.5 3 3.5

x3 s3
1 2

效益 维修费 更新费

rk (t )

4.5 4

f3 (s3 ) x* 3
9.5 8.8

uk (t )

0.5 1

1.5 2

R R

ck (t )

0.5 1.5 2.2 2.5

? r2 (1) ? u 2 (1) ? f 3 (1 ? 1) f 2 (1) ? max ? ?r2 (0) ? u 2 (0) ? c2 (1) ? f 3 (1)

x2 ? K x2 ? R

? 4.5 ? 1 ? 8.8 ? * ? max? ? 12 . 5 , 此时, x )?R ? 2 (1 ?5 ? 0.5 ? 1.5 ? 9.5?

s1 ? 0

x1
1

s2 ? 1

x2
2
g 2 ( x2 )

s3

x3
3
g3 ( x3 )

s4

x4
4
g 4 ( x4 )

s5

x5
5
g5 ( x5 )

s6

g1 ( x1 )

K=1时:
f1 ( s1 ) ? max {g1 ( x1 ) ? f 2 ( s2 )}
x1 ? K or R

? r1 ( s1 ) ? u1 ( s1 ) ? f 2 ( s1 ? 1) ? max ? ?r1 (0) ? u1 (0) ? c1 ( s1 ) ? f 2 (1)
此时, s1 只能取0。所以

x1 ? K x1 ? R

? r1 (0) ? u1 (0) ? f 2 (0 ? 1) f1 (0) ? max ? ?r1 (0) ? u1 (0) ? c1 (0) ? f1 (1)

x1 ? K x1 ? R

役龄 项目

0 5

1

2

3 3.75

4 3 2.5 3

5 2.5 3 3.5

f 2 (1) ? 12.5,
* x2 (1) ? R

效益 维修费 更新费

rk (t )

4.5 4

uk (t )

0.5 1

1.5 2

ck (t )

0.5 1.5 2.2 2.5

? r1 (0) ? u1 (0) ? f 2 (0 ? 1) f1 (0) ? max ? ?r1 (0) ? u1 (0) ? c1 (0) ? f1 (1)

x1 ? K x1 ? R

? 5 ? 0.5 ? 12.5 ? * ? max? ? 17 , 此时, x ? 1 (0) ? K ?5 ? 0.5 ? 0.5 ? 12.5?

s1 ? 0

x1
1

s2 ? 1

x2
2
g 2 ( x2 )

s3

x3
3
g3 ( x3 )

s4

x4
4
g 4 ( x4 )

s5

x5
5
g5 ( x5 )

s6

g1 ( x1 )

?sk ? 1 xk ? K 状态转移方程: sk ?1 ? ? xk ? R ? 1

f1 (0) ? 17,

* x1 (0) ? K

f 2 (1) ? 12.5,

* x2 (1) ? R

* (0) ? K 上述计算递推回去,当 x1

时,由状态转移方程:
查 f 2 (1) ? 12.5, 得

?s1 ? 1 x1 ? K s2 ? ? x1 ? R ? 1

知 s2 ? 1,
* x2 (1) ? R

s1 ? 0

x1
1

s2 ? 1

x2
2
g 2 ( x2 )

s3

x3
3
g3 ( x3 )

s4

x4
4
g 4 ( x4 )

s5

x5
5
g5 ( x5 )

s6

g1 ( x1 )

?sk ? 1 xk ? K 状态转移方程: sk ?1 ? ? xk ? R ? 1

K=3时最优值表

x3 s3
1 2

f3 (s3 ) x* 3
9.5 8.8

f1 (0) ? 17,
有 查

x (0) ? K
* 1

x (1) ? R
* 2

?s2 ? 1 x2 ? K s3 ? ? x2 ? R ? 1

R R

知 s3 ? 1,

f3 (1) ? 9.5,

* x3 (1) ? R 知 s4 ? 1,

s1 ? 0

x1
1

s2 ? 1

x2
2
g 2 ( x2 )

s3

x3
3
g3 ( x3 )

s4

x4
4
g 4 ( x4 )

s5

x5
5
g5 ( x5 )

s6

g1 ( x1 )

?sk ? 1 xk ? K 状态转移方程: sk ?1 ? ? xk ? R ? 1

K=4时最优值表

x4
f 4 (s4 ) x* 4

f1 (0) ? 17,
* x3 (1) ? R

* x1 (0) ? K

* x2 (1) ? R

s4
1 2 3 6.5 5.8 5.5

R R R



* f 4 (1) ? 6.5, x4 (1) ? R 知 s5 ? 1,

s1 ? 0

x1
1

s2 ? 1

x2
2
g 2 ( x2 )

s3

x3
3
g3 ( x3 )

s4

x4
4
g 4 ( x4 )

s5

x5
5
g5 ( x5 )

s6

g1 ( x1 )

?sk ? 1 xk ? K 状态转移方程: sk ?1 ? ? xk ? R ? 1

K=5时最优值表

x5 s5
1 2 3 4

f1 (0) ? 17,
* x3 (1) ? R

* x1 (0) ? K

* x2 (1) ? R

f5 (s5 ) x5
3.5 2.5 2 1.5

*

* x4 (1) ? R

K K



f5 (1) ? 3.5, x (1) ? K
* 5

R R

故本题最优策略为{K , R, R, R, K} ,即第一年初购买的设备 到第二、三、四、年初各更新一次,用到第5年末,其总效 益为17万元。


相关文章:
运筹学第10章-动态规划_图文.ppt
运筹学10章-动态规划 - Page:1 管理运筹学 动态规划 Page:2 综 述 动态规划是解决多阶段决策过程最优 化问题的一种方法。动态规划所研究 的对象是多阶段...
运筹学第10章 动态规划.ppt
运筹学10动态规划_数学_自然科学_专业资料。运筹学是管理类专业的一门重要
运筹学动态规划习题_图文.ppt
运筹学动态规划习题 - 习题三 一、某工厂购进100台机器,准备生产A、B 两种
运筹学10-动态规划_图文.ppt
运筹学10-动态规划 - 第十章 动态规划 10.1 多阶段过程决策问题 10.2 动态规划原理 10.3 动态规划应用举例 10.1 多阶段过程决策问题 多阶段决策过程的最...
运筹学10-动态规划_图文.ppt
运筹学10-动态规划 - 第十章 动态规划 Dynamic Programming 10.1 多阶段决策问题 10.2 动态规划的基本概念和基本方程 10.3 动态规划的建模与求解方法 10...
运筹学第10章 动态规划_图文.ppt
运筹学10动态规划 - Page:1 管理运筹学 动态规划 Page:2 综 述 动态规划是解决多阶段决策过程最优 化问题的一种方法。动态规划所研究 的对象是多阶段...
运筹学第10章 动态规划_图文.ppt
运筹学10动态规划 - 第九章 动态规划 一、基本概念、方程与最优化原理
管理运筹学 第10章 动态规划_图文.ppt
管理运筹学10动态规划 - 第十章 动态规划 §1 多阶段决策过程最优化问题举例 §2 基本概念、基本方程与最优化原理 §3 动态规划的应用(1) §4 动态...
管理运筹学10动态规划_图文.ppt
管理运筹学10动态规划 - 第十章 动态规划 §1 多阶段决策过程最优化问题举例 §2 基本概念、基本方程与最优化原理 §3 §4 动态规划的应用(1) 动态规划的...
运筹学答案_第_10_章__动态规划.pdf
运筹学答案_第_10_章__动态规划 - 第 10动态规划 1、最优解:A
运筹学-动态规划(一)(名校讲义)_图文.ppt
运筹学-动态规划(一)(名校讲义) - 第十七、十八讲 动态规划(一) §1 引
运筹学 动态规划2_图文.ppt
运筹学 动态规划2_数学_自然科学_专业资料。运筹学第十章 动态规划应用举例 第九章 动态规划应用举例本章内容 ?资源分配问题 ?生产与存储问题 ?背包问题 ?复合...
《运筹学》7动态规划_图文.ppt
运筹学》7动态规划 - 运筹学课件 运筹帷幄之中 Dynamic Programming 决胜 动态规划 千里之外第1页 综 述 1951 年,R ...
第10章 动态规划_图文.ppt
10动态规划 - 主要讲述:多阶段决策过程最优化问题举例,基本概念、基本方程与最优化原理,动态规划的应用
运筹学7动态规划.ppt
运筹学7动态规划_数学_自然科学_专业资料。运筹学7动态规划 第七 章动态规划 ...(22) v2 5 (27) v1 6 8 (16) v5 6 5 (10) 9 7 11 6 (22) ...
第八、九讲 动态规划(运筹学基础-清华大学,王永县)_图文.ppt
(1)动态规划运筹学的重要分支之一,它是解决多阶段决 策过程最优化的一种...10 8 8 10 4 9 10 第3阶段 第2阶段 12 19 10 5 2 4 8 8,9 6 9...
运筹学-动态规划(二)(名校讲义)_图文.ppt
运筹学-动态规划(二)(名校讲义) - 第十九讲 动态规划(二) §1 具有隐含
第10章__动态规划_(管理运筹学_第三版_课件__共17章_韩....ppt
10章__动态规划_(管理运筹学_第三版_课件__共17章_韩伯棠)_管理学_高等教育_教育专区。第10章__动态规划_(管理运筹学_第三版_课件__共17章_韩伯棠) ...
运筹学13-动态规划I-12-1_图文.ppt
运筹学13-动态规划I-12-1 - 第13讲 动态规划I 本讲提纲 1. 多阶段决策问题 2. 动态规划的基本概念与最优性原理 3. 动态规划模型的建立 School of Busine...
运筹学课件动态规划_图文.ppt
运筹学课件动态规划 - 第十章 动态规划(DP) Dynamic Program
更多相关文章: