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

运筹学 Ch8动态规划


运筹学
Operations Research

第八章 动态规划
Dynamic Programming
8.1 引言 Preface 8.2 动态规划数学模型Mathematical Model of DP 8.3 资源分配问题 Resource Assignment Problem 8.4 生产与存储问题Production and inventory problem 8.5 背包问题 Knapsack Problem 8.6 其它动态规划模型 Other Model of DP

8.1 引言
Preface

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 3

动态规划是运筹学的一个分支,适用于许多类型问题的数学 方法,即它是跨越数学规划的各个领域。一些线性规划,非线性 规划及整数规划等问题都可用动态规划的方法来求解。动态规划 是解决多阶段决策过程最优化的一种方法,它的特点是先将一个 复杂的问题分解成相互联系的若干阶段;每个阶段即为一个小问 题,然后逐个处理,当每一个阶段的决策一旦确定之后,整个过 程的决策也随之确定。由于阶段往往可以用时段表示,这就是 “动态”的含义和由来,当然,动态规划也可以解决一些与时间 无关的静态规划的最优化问题。 动态规划产生于50年代,1951年,美国数学家贝尔曼 (R.Bellman)等人提出了解决多阶段决策问题的“最优化原理”, 并研究了许多实际问题,从而创建了“动态规划”,1957年,出 版了著作“Dynamic Programming”,首次对动态规划的主要内容 作了系统的阐述。

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 4

动态规划的核心就是Bellman提出的最优化理论,即“作为整 个过程的最优策略具有这样的性质:即无论过去的状态和决策如 何,对前面的决策所形成的状态而言,余下的诸决策必须构成最 优策略”利用这个原则,可以把多阶段决策问题的求解过程看成 是一个连续的递推过程,由后向前逐步推算(逆向)。 动态规划问世之后,很快地引起了工程技术、经济、企业管 理、工农业生产以及军事等部门地兴趣,并利用动态规划解决了 许多实际问题,象库存问题、生产调度问题、资源分配问题、设 备更新问题,生产过程最优控制问题等,都取得了良好的效果。 动态规划模型的分类如下: 决策过程的时间变量-离散、连续的变量 决策过程的演变-确定性、随机性 1)离散确定性2)离散随机性 3)连续确定性 4)连续随机性

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 5

8.2 动态规划数学模型
Mathematical Model of DP

【例8.1】最短路径问题 图8-1表示从起点A到终点 E之间各点的距离。求A到E的最短路径。
17 v2 10 13 2 14 7 v3

8.2.1动态规划的原理

Min{2+5,8+8,6+4}=7
7 v5 2 8 6 10 12 5 v6 11 12 8

5 v7 5

8

19 v1
5

8

v8

8

v10 0

13
v4 20

4 v9 4

阶段: 第1阶段

第2阶段 第3阶段 图8-1

第4阶段 第5阶段

8.1 动态规划数学模型 Mathematical Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 7

用WinQSB软件计算时,需要对状态重新编号,如下图所示.
2 10 13 2 1 5 8 7 3 10 12 5 6 8 11 9 2 5 8 6 8 7 5

8

10

13
4

4

阶段: 第1阶段

第2阶段 第3阶段 图8-2

第4阶段 第5阶段

8.1 动态规划数学模型 Mathematical Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 8

用WinQSB软件计算时,当某状态没有路到下阶段某状态时,添加 一条虚拟决策(线条),距离很大,如下图点3到点5. 12 2 5 2 13 8 10 2 8 6 M 6 8 10 1 3 6 10 4 5

5 8
11 11 7 8 9 4

13
4

8.1 动态规划数学模型 Mathematical Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 9

动态规划问题具有以下基本特征 1. 问题具有多阶段决策的特征。阶段可以按时间划分,也 可以按空间划分。

2. 每一阶段都有相应的“ 状态”与之对应。
3. 每一阶段都面临一个决策,选择不同的决策将会导致下 一阶段不同的状态,同时,不同的决策将会导致这一阶段不同 的目标函数值。

4. 每一阶段的最优解问题可以递归地归结为下一阶段各个 可能状态的最优解问题,各子问题与原问题具有完全相同的结 构。能否构造这样的递推归结,是解决动态规划问题的关键。 这种递推归结的过程,称为“ 不变嵌入”。

8.1 动态规划数学模型 Mathematical Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 10

5 . 状态具有无后效性 当某阶段状态确定后,此阶段以后过 程的发展不受此阶段以前各阶段状态的影响。也就是说,过程的 过去历史只能通过当前的状态去影响它的未来的发展,只有当前 的状态是未来过程的初始状态。例如: 3 4 B E 2 A 1 一 C 2

D
5

3 1 三 四 F 2 五

G

4


如上划分阶段不符合无后效性,因为E依赖于B,D而它们分别在第 二、三阶段,同样,F依赖于C、D、E;G依赖于E,F,都不符合无后 效性。如果改为下图就无后效性了。

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 11

B

0 B1 3 1

E

0

E1

2
A 1

4

2
4

D

0

D1

3 1 2 F 五

G



0 C 0 二 C1 三 C2

5 四

8.1 动态规划数学模型 Mathematical Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 12

动态规划基本原理是将一个问题的最优解转化为求子问题的最 优解,研究的对象是决策过程的最优化,其变量是流动的时间 或变动的状态,最后到达整个系统最优。 基本原理一方面说明原问题的最优解中包含了子问题的最优解, 另一方面给出了一种求解问题的思路,将一个难以直接解决的 大问题,分割成一些规模较小的相同子问题,每一个子问题只 解一次,并将结果保存起来以后直接引用,避免每次碰到时都 要重复计算,以便各个击破,分而治之,即分治法,是一种解 决最优化问题的算法策略。

8.1 动态规划数学模型 Mathematical Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 13

8.1.2基本概念 (1)阶段(Stage):把所给问题的过程,恰当地划分成若干个相 互联系的阶段,以便于求解。 阶段可以按时间或空间划分,阶段 数k可以是确定数、不定数或无限数
2 10

13
2 1 5 13 4 11 8

2

7

5

5

8
6 8 8 10

7 3 12

5 6 8 9 4

阶段: 第1阶段

第2阶段

第3阶段

第4阶段 第5阶段

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 14

(2)状态(State):状态就是指过程过去、现在和将来的情况。 状态由过程本身的确定,它反映了过程的具体特征。 在多阶段决策过程中,例如上述最优旅行路线问题中,每一个阶 段都有不同的起点、终点和长度,称每一阶段的起点为该阶段的 状态。每一阶段的起点又是前一阶段的终点。因而,多阶段决策 过程也就是各个阶段状态演变的过程。显然一个阶段通常包含着 若干个状态。描述过程状态的变量,称为状态变量,第k个阶段 的状态变量一般可以记作sk,状态变量取值的全体称为状态集合 (或状态空间),记做Sk ,如果第k个阶段有r个状态,则第k个阶 段状态集合可表示为:

Sk ? {s

(1) k

,s

(2) k

,

,s

(r ) k

}

如上述例子,S3={5,6}

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 15

(3)决策(Decision)xk:从某一状态向下一状态过度时所做的 选择。决策变量记为xk,xk是所在状态sk的函数。 在状态sk下,允许采取决策的全体称为决策允许集合,记为Dk(sk)。 各阶段所有决策组成的集合称为决策集。 (4) 策略(Strategy):从第1阶段开始到最后阶段全过程的决策构成 的序列称为策略,第k阶段到最后阶段的决策序列称为子策略。 (5)状态转移方程(State transformation function):某一状态以 及该状态下的决策,与下一状态之间的函数关系,记为 sk+1=T(sk,xk) 上述sk+1与(sk,xk )存在确定的对应关系,这就是一个确定性过程, 在实际问题中,可能出现随机因素,使sk+1与(sk,xk )存在着非 确定性的关系,这就是一个随机性的过程。 (6)指标函数或收益函数(Return function):是衡量对决策过程 进行控制的效果的数量指标,具体可以是收益、成本、距离等指 标。分为k阶段指标函数、k子过程指标函数及最优指标函数。

8.1 动态规划数学模型 Mathematical Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 16

k阶段指标函数 从k阶段状态sk出发,选择决策xk所产生的第k阶段指标,称为k 阶段指标函数,记为vk(sk,xk)。 过程指标函数 从k阶段状态sk出发,选择决策xk,xk+1,…,xn所产生的过程指标, 称为k子过程指标函数或简称过程指标函数,记为 Vk(sk,xk,xk+1,…,xn)或Vk,n为阶段数。 最优指标函数 从k阶段状态sk出发,对所有的子策略,最优的过程指标函数 称为最优指标函数,记为fk(sk),通常取Vk的最大值或最小值。 (Opt=optimization 表示“max”或“min” xk ?Dk ( sk ) 其中,Pk,n是从k阶段到第n阶段的决策序列。
k ,n

f k ( sk ) ?

opt {V

( sk , Pk ,n )}

8.1 动态规划数学模型 Mathematical Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 17

动态规划要求过程指标满足递推关系 ,即

Vk ( sk , xk , xk ?1 ,
连和形式:

, xn ) ? Vk [v( sk , xk ),Vk ?1 (sk ?1 , xk ?1 ,
VK ? VK ( sk , xk , xk ?1 , ? ? v j ( s j , x j) ? Vn
j ?k n ?1

, xn )]

(8.2)

, xn ) , xn )

? vk ( sk , xk)+VK ( sk+1 , xk ?1 ,

(8.3)

最优指标函数是

f k ( s k ) ? Opt {v k ( s k , x k } ? f k ?1 ( s k ?1 )}, k ? 1,2,? , n
xk ?Dk ( s k )

(8.4)

8.1 动态规划数学模型 Mathematical Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 18

连乘形式(vj≠0) : VK ? VK ( sk , xk , xk ?1 ,

, xn ) , xn )
(8.5)

? vk ( sk , xk ) ?VK ( sk+1 , xk ?1 , ? ? v j ( s j , x j ) ?Vn
j =k n ?1

最优指标函数是

f k ( s k ) ? Opt {v k ( s k , d k } ? f k ?1 ( s k ?1 )}, k ? 1,2,? , n
xk ?Dk ( s k )

(8.6)

动态规划数学模型由式(8.4)或(8.6)、边界条件及状态转移方程 构成。如连和形式的数学模型
? f k ( s k ) ? Opt {v k ( s k , x k } ? f k ?1 ( s k ?1 )}, k ? 1,2,? , n xk ?Dk ( sk ) ? ? ? f n (sn ) ? 0 ?s ? T ( s , x ) k ?1 k k ? ?

8.1 动态规划数学模型 Mathematical Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 19

对于可加性指标函数,上式可以写为

f k ( sk ) ?

xk ?Dk ( sk )

opt {v (s , x } ? f
k k k

k ?1

( sk ?1 )}

k ? 1, 2, , n

上式中“ opt”表示“ max”或“ min”。对于可乘性指标函数, 上式可以写为

f k ( sk ) ?

opt
xk ?Dk ( sk )

{vk ( sk , xk }? f k ?1 ( sk ?1 )}

k ? 1,2,?, n

上式称为动态规划最优指标的递推方程,是动态规划的基本方 程。 终端条件:为了使以上的递推方程有递推的起点,必须要设定 最优指标的终端条件,即确定最后一个状态n下最优指标fn(sn)的 值。

8.1 动态规划数学模型 Mathematical Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 20

用逆序法列表求解例8.1 k=n=5 时,f5(v10)=0 k=4,递推方程为

f 4 ( s 4 ) ? min {v4 (s 4 , x4 ) ? f 5 (s5 )}
x4 ?D4 ( s4 )

s4 v7 v8 v9

D4(s4) v7?v10 v8?v10 v9?v10

s5 v10 v10 v10

v4(s4,x4) 5 8 4

v4(s4,x4)+f5(s5) 5+0=5* 8+0=8* 4+0=4*

f4(s4) 5 8 4

最优决策x4* v7? v10 v8→ v10 v9? v10

8.1 动态规划数学模型 Mathematical Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 21

k=3,递推方程为
f 3 (s3 ) ? min {v3 (s3 , x3 ) ? f 4 (s 4 )}
x3?D3 ( s3 )

表8-2
s3 v5 D3(s3) v5?v7 v 5 ? v8 v 5 ? v9 v6? v7 v 6 ? v8 v 6 ? v9 s4 v7 v8 v9 v7 v8 v9 v3(s3,x3) 2 8 6 12 5 8 v3(s3,x3)+f4(s4) 2+5=7* 8+8=16 6+4=10 12+5=17 5+8=13 8+4=12* f3(s3) 7 最优决策x3* v5?v7

v6

12

v6?v9

8.1 动态规划数学模型 Mathematical Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 22

k=2,递推方程为
f 2 ( s2 ) ? min {v2 ( s2 , x2 ) ? f 3 ( s3 )}
x2?D2 ( s2 )

表8-3
s2 v2 v3 D2(s2) v2? v5 v 2 ? v6 v3? v5 v 3 ? v6 v4? v5 v 4 ? v6 s3 v5 v6 v5 v6 v5 v6 v2(s2,x2) 10 13 7 10 13 11 v2(s2,x2)+f3(s3) 10+7=17* 13+12=25 7+7=14* 10+12=22 13+7=20* 11+12=23 f2(s2) 17 14 最优决策x2* v2? v5 v3?v5

v4

20

v4?v5

8.1 动态规划数学模型 Mathematical Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 23

k=1,递推方程为
f1 ( s1 ) ? min {v1 ( s1 , x1 ) ? f 2 ( s2 )}
x1?D1 ( s1 )

表8-4
s1 v1 D1(s1) s2 v1(s1,x1) v1(s1,x1)+f2(s2) f1(s1) 最优决策x1*

v1?v2 v 1 ? v3 v 1 ? v4

v2 v3 v4

2 8 5

2+17=19* 8+14=22 5+20=25

19

v1?v2

最优值是表8-4中f1(s1)的值,从v1到v10的最短路长为19。最短路 线从表8-4到表8-1回朔,查看最后一列最优决策,得到最短路 径为: v1? v2 ? v5 ? v7 ? v10

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 24

动态规划解题的具体步骤: 1.将问题化成一个多阶段决策过程的最优化问题,并确定过程的历 程n。 2.规定状态变量sk的取法。状态变量应具有以下三个特性: 1)要能够用来描述受控过程的演变特性 2)要满足无后效性 3)可知性:即规定的各阶段状态变量的值,由直接或间接都是可 知的。 3.规定决策变量xk的取法,并写出各段允许的决策集合Dk(sk) 4.写出状态转移方程 5.根据题意列出指标函数V 6.写出动态规划的基本(递推)方程 7.解出DP方程,求出最优值f1(s1)和最优策略
* * p* ? {x1 , x2 , * , xn }

8.1 动态规划数学模型 Mathematical Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 25

作业:教材P188 T2 下一节:资源分配问题

8.3 资源分配问题
Resource Assignment Problem

8.2 资源分配问题 Resource Assignment Problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 27

【例8.2】公司有资金8万元,投资A、B、C三个项目,一个单位投资为 2万 元。每个项目的投资效益率与投入该项目的资金有关。三个项目 A 、 B、 C 的投资效益(万元)和投入资金(万元)的关系见表8-5。求对三个项目的最优 投资分配,使总投资效益最大。 --投资问题 表8-5 项目 A B C 投入资金 2万元 4万元 6万元 8万元 8 15 30 38 9 20 35 40 10 28 35 43

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 28

给B、C项目 给C项目 48 给B项目 0 8 8 2 43 给A项目 37 0 4 0 6 2 6 6 35 给A、B、C项目 2 4 28 6 8 4 8 4 0 2 4 28 6 48 4 10 8 21 0 2 10 0 0
2 0

0 0

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 29

步骤1:第三阶段,假设把资源分配给项目C,显然该阶段有5个 状态(分别给项目C分配资源数0,2,4,6,8),对于状态S3 最优投资数x3(8)=8,最优利润f3(x)=v3(x) 步骤2:第二阶段,假设把资源分配给项目B、C,该阶段也有5个

状态(分别给项目B、C分配资源数0,2,4,6,8),对于状态S3 最优投资数x3(8)=8,动态规划方程应为: 对于x=8 v2(0)+f3(8)=0+43=43 v2(2)+f3(6)=9+35=44 v2(4)+f3(4)=20+28=48 v2(6)+f3(2)=35+10=45 v2(8)+f3(0)=40+0=40 所以 f2(8)= v2(4)+f3(4)=48 最优决策 d2(8)=4 对于x=6,4,2,0亦可以类似地求出相应的最优利润f2(x)和最优决策 d2(x)=4

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 30

步骤三:第一阶段假设把资源分配给项目A,B,C,由于利润函数 都是单调上升的,因此分配给它们8可以达到最优,故该阶段只 有一个状态 动态规划方程为: v1(0)+f2(8)=0+48=48 v1(2)+f2(6)=8+37=45

v1(4)+f2(4)=15+28=43 v1(6)+f2(2)=30+10=40
v1(8)+f2(0)=38+0=38 所以f1(8)= v1(0)+f2(8)=48 最优决策d1(8)=0 因此最优分配为:项目A: 0 , 项目B:4 , 项目C :4 ,可得 最优利润为48万元。

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 31

x f3(x) d3(x) f2(x)

0 0 0 0

2 10 2 10

4 28 4 28

6 35 6 37

8 43 8 48

d2(x)
f1(x) d1(x)

0

0

0

2

4
48 0

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 32

另一种解题模式:

【解】设xk为第k个项目的投资,该问题的静态规划模型为

max Z ? v1 ( x1 ) ? v2 ( x2 ) ? v3 ( x3 ) ? ? x1 ? x2 ? x3 ? 8 ? x ? 0, 2, 4, 6,8 ? j ?

8.2 资源分配问题 Resource Assignment Problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 33

阶段k:每投资一个项目作为一个阶段,k=1,2,3,4。k=4为虚设 的阶段,第一阶段分配给A,B,C项目,第二阶段分配给B,C项目, 第三阶段分配给C项目 状态变量sk:投资第k个项目前的资金数 决策变量xk:第k个项目的投资额 决策允许集合:0≤xk≤sk 状态转移方程:sk+1=sk-xk 阶段指标:vk(sk,xk)见表8-5中的数据 递推方程: f k ( xk ) ? max ?vk ( sk , xk ) ? f k ?1 ( sk ?1 )?

终端条件:f4(s4)=0 数学模型为 f k ( xk ) ? max ?vk ( sk , xk ) ? f k ?1 ( sk ?1 )}, k ? 3, 2,1
? sk ?1 ? sk ? xk ? ? f 4 ( x4 ) ? 0 ? x ? 0, 2, 4, 6,8, k ? 1, 2,3 ? k

8.2 资源分配问题 Resource Assignment Problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 34

k=4,终端条件f4(s4)=0。 k=3,0≤x3≤s3,s4=s3-x3
状态 s3
0 2

决策 x3(s3)
0 0 2 0 2 4 0 2 4 6 0 2

状态转移方程 s4=s3-x3
0 2 0 4 2 0 6 4 2 0 8 6 4 2 0

阶段指标 v3(s3,x3)
0 0 10 0 10 28 0 10 28 35 0 10 28 35 43

过程指标 v3(s3,x3)+f4(s4)
0+0=0 0+0=0 10+0=10* 0+0=0 10+0=10 28+0=28* 0+0=0 10+0=10 28+0=28 35+0=35* 0+0=0 10+0=10 28+0=28 35+0=35 43+0=43*

最优指标 f3(s3)
0 10

最优决策 x3*
0 2

4

28

4

6

35

6

8

4 6 8

43

8

8.2 资源分配问题 Resource Assignment Problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 35

k=2,0≤x2≤s2,s3=s2-x2
s2
0 2

x2(s2)
0 0 2 0 2

s3
0 2 0 4 2

v2(s2,x2)
0 0 9 0 9

f3(s3)
0 10 0 28 10

v2(s2,x2)+f3(s3)
0+0=0 0+10=10* 9+0=9 0+28=28* 9+10=19

f2(s2)
0 10

x2*
0 0

4

28

0

4
0 6 2

0
6 4

20
0 9

0
35 28

20+0=20
0+35=35 9+28=37*

4
6 0 2

2
0 8 6 4 2 0

20
35 0 9 20 35 40

10
0 43 35 28 10 0

20+10=30
35+0=35 0+43=43 9+35=44 20+28=48* 35+10=45 40+0=40

37

2

8

4 6 8

48

4

8.2 资源分配问题 Resource Assignment Problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 36

k=1,0≤x1≤s1,s2=s1-x1
s1 x1(s1) 0 2 s2 8 6 v1(s1,x1) 0 8 f2(s2) 48 37 v1(s1,x1)+f2(s2) 0+48=48* 8+37=45 f1(s1) x1*

8

4
6 8

4
2 0

15
30 38

28
10 0

15+28=43
30+10=40 38+0=38

48

0

最优解为: s1=8, x1*=0, s2=s1-x1=8, x2*=4, s3=s2-x2*=4, x3=4, s4=s3-x3=0。 投资的最优策略是,项目A不投资,项目B投资4万元,项目C投 资4万元,最大效益为48万元

8.2 资源分配问题 Resource Assignment Problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 37

【例8.3】某种设备可在高低两种不同的负荷下进行生产,设在 高负荷下投入生产的设备数量为x,产量为g=10x,设备年完好率 为a=0.75;在低负荷下投入生产的设备数量为y,产量为h=8y, 年完好率为b=0.9。假定开始生产时完好的设备数量s1=100。 制定一个五年计划,确定每年投入高、低两种负荷下生产的设 备数量,使五年内产品的总产量达到最大。 阶段k:运行年份(k=1,2,3,4,5,6),k=1表示第一年初,k=6 表示第五年末(即第六年初); 状态变量sk:第k年初完好的机器数(k=1,2,3,4,5,6),也是第 k-1年末完好的机器数,其中s6表示第五年末(即第六年初)的 完好机器数,s1=100。 决策变量xk:第k年初投入高负荷运行的机器数; 状态转移方程:sk+1=0.75xk+0.9(sk-xk)

8.2 资源分配问题 Resource Assignment Problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 38

决策允许集合:Dk(sk)={xk|0?xk?sk} 阶段指标:vk(sk,xk)=10xk+8(sk-xk) 终端条件:f6(s6)=0 递推方程:
f k ( s k ) ? max ?vk ( s k , xk ) ? f k ?1 ( s k ?1 )? ? max ? 10 x k ? 8( s k ? x k ) ? f k ?1 ?0.75 xk ? 0.9( s k ? xk )??
0 ? xk ? s k xk ?Dk ( sk )

f5 ( s5 ) ? max ?10 x5 ? 8( s5 ? x5 ) ? f 6 ( s6 )?
0? x5 ? s5

? max ?10 x5 ? 8( s5 ? x5 )?
0? x5 ? s5 0? x5 ? s5

? max ?2 x5 ? 8s5 ? ? 10s5

* x5 ? s5时最优

8.2 资源分配问题 Resource Assignment Problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 39

f 4 ( s4 ) ? max ?10 x4 ? 8( s4 ? x4 ) ? f5 ( s5 )?
0? x4 ? s4

? max ?10 x4 ? 8( s4 ? x4 ) ? 10s5 ?
0? x4 ? s4 0? x4 ? s4 0? x4 ? s4

? max ?10 x4 ? 8( s4 ? x4 ) ? 10(0.75 x4 ? 0.9( s4 ? x4 ))? ? max {0.5 x4 ? 17 s4 } ? 17.5s4
* x4 ? s4时最优

f3 ( s3 ) ? max ?10 x3 ? 8( s3 ? x3 ) ? f 4 ( s4 )?
0? x3 ? s3

? max ?10 x3 ? 8( s3 ? x3 ) ? 17.5s4 ?
0? x3 ? s3 0? x3 ? s3 0? x3 ? s3

? max ?10 x3 ? 8( s3 ? x3 ) ? 17.5(0.75 x3 ? 0.9( s3 ? x3 ))? ? max {?0.625 x3 ? 23.75s3} ? 23.75s3
* x3 ? 0时最优

8.2 资源分配问题 Resource Assignment Problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 40

f 2 ( s2 ) ? max ?10 x2 ? 8( s2 ? x2 ) ? f 3 ( s3 )?
0? x2 ? s2

? max ?10 x2 ? 8( s2 ? x2 ) ? 23.75s3 ?
0? x2 ? s2 0? x2 ? s2 0? x2 ? s2

? max ?10 x2 ? 8( s2 ? x2 ) ? 23.75(0.75 x2 ? 0.9( s2 ? x2 ))? ? max {?1.5625 x2 ? 29.375s2 } ? 29.375s2
* x2 ? 0时最优

f1 ( s1 ) ? max ?10 x1 ? 8( s1 ? x1 ) ? f 2 ( s2 )?
0? x1 ? s1

? max ?10 x1 ? 8( s1 ? x1 ) ? 29.375s2 ?
0? x1 ? s1 0? x1 ? s1 0? x1 ? s1

? max ?10 x1 ? 8( s1 ? x1 ) ? 29.375(0.75 x1 ? 0.9( s1 ? x1 ))? ? max{?2.406 x1 ? 34.4375s1} ? 34.4375s1
* x1 ? 0时最优

8.2 资源分配问题 Resource Assignment Problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 41

因为s1=100,五年的最大总产量为f1(s1)=25.7525×100=3443.75。 由x1*= x2*= x3*=0,x4*=s4,x5*=s5,设备的最优分配策略是, 第一年至第三年将设备全部用于低负荷运行,第四年和第五年将 设备全部用于高负荷运行。每年投入高负荷运行的机器数以及每 年初完好的机器数为: s1=100 x1*=0, s2=0.75x1+0.9(s1-x1)=90 x2*=0, s3=0.75x2+0.9(s2-x2)=81 x3*= 0, s4=0.75x3+0.9(s3-x3)=73 x4*= s4=73, s5=0.75x4+0.9(s4-x4)=55 x5*= s5=55, s6=0.75x5+0.9(s5-x5)=41 第五年末还有41台完好设备。

8.2 资源分配问题 Resource Assignment Problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 42

一般地,设一个周期为n年,高负荷生产时设备的完好率为a, 单台产量为g;低负荷完好率为b,单台产量为h。若有t满足
n ?t ?1

?
i ?0

n ?t g ?h a ? ? ? ai g (b ? a) i ?0 i

(8.7)

则最优设备分配策略是:从1~t-1年,年初将全部完好设备投 入低负荷运行,从t~n年,年初将全部完好设备投入高负荷运 行,总产量达到最大 . 在例8.3中, n=5,a=0.75,b=0.9,g=10,h=8,(g-h)/g(b-a)=1.3333 式(8.7)的求和式是完好率a的i次方累加. 由a0=1<1.3333<a0+a1=1.75知,n-t-1=0,t=4,则1~3年低负 荷运行,4~5年为高负荷运行

8.2 资源分配问题 Resource Assignment Problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 43

作业:教材P188 T1,6,8,9

下一节:最优旅行路线问题

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 44

8.3 最优旅行路线问题
Stagecoach problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 45

最优旅行路线问题也是最短路线问题也是通过网络寻找最优路线 问题,因此它也是网络流问题。 例如,下图表示各种路线和从一个状态到另一个状态旅行的策略 费用(保险费)

2
4

10 9

5 8 6 9

4

1

2

8 3 7 10

8

8

1 0

3

6 5 3

9 4

4

4

8

7

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 46

设Cij表示从状态i到状态j的策略费用,那么C12=4, C13=2, C14=3; C25=10,C26=9;C35=6,C36=7,C37=10;C46=3,C47=8;C58=4,C59=8; C68=9,C69=6;C78=5,C79=4;C8,10=8,C9,10=4 该问题划分阶段,确定状态变量和决策变量,以及规定指标函数 都是清楚的,但需注意无后效性。

现在问题是求从状态1到状态10的最安全路线,即使它的总保险费
为最小的路线。 步骤1:旅行推销员已处在第4阶段

显然f4(x4)=Cij 即方f4(8)=C8,10=8,f4(9)=C9,10=4 因为它只有一条路
(一个决策),因此最优决策d4(x)=10 (x=8,9) 步骤2:向后退一阶段,在第3阶段

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 47

对状态5:

对状态6:

?C58 ? f 4 (8) ? ?4 ? 8? f3 (5) ? min ? ? ? min ? ? ? 12 ?8 ? 4? ?C59 ? f 4 (9) ?

d3(5)=8或9

对状态7:

?C68 ? f 4 (8) ? ?9 ? 8 ? f3 (6) ? min ? ? ? min ? ? ? 10 ?6 ? 4 ? ?C69 ? f 4 (9) ?

d3(6)=9

?C78 ? f 4 (8) ? ?5 ? 8 ? f3 (7) ? min ? ? ? min ? ??8 ?4 ? 4 ? ?C79 ? f 4 (9) ?

d3(7)=9

步骤3:处在第2阶段
对状态2:

?C25 ? f3 (5) ? ?10 ? 12? f 2 (2) ? min ? ? ? min ? ? ? 19 ? 9 ? 10 ? ?C26 ? f 4 (6) ?

d2(2)=6

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 48

对状态3

?C35 ? f3 (5) ? ?8 ? 12 ? ? ? ? ? f 2 (3) ? min ?C36 ? f3 (6) ? ? min ?7 ? 10 ? ? 17 ?C ? f (7) ? ?10 ? 8 ? ? 37 3 ? ? ?

d2(3)=6

对状态4

?C46 ? f3 (6) ? ?3 ? 10? f 2 (4) ? min ? ? ? min ? ? ? 13 ?8 ? 10? ?C47 ? f 4 (7) ?

d2(4)=6

步骤4:最后到第1阶段 ?C12 ? f 2 (2) ? ?4 ? 19 ? ? ? ? ? f1 (1) ? min ?C13 ? f 2 (3) ? ? min ?2 ? 17 ? ? 16 ?C ? f (4) ? ? 3 ? 13 ? ? 14 2 ? ? ?

d1(1)=4

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 49

X f4(x) d4(x) f3(x) d3(x) f2(x) d2(x) f1(x)

1

2

3

4

5

6

7

8 8 10

9 4 10

12 8,9 19 6 16 17 6 13 6

10 9

8 9

d1(x) 4 所以最优路线为1->4->6->9->10,最小费用是16

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 50

上面介绍的最优旅行路线问题是阶段为n的最短路线问题,它是

定期的多阶段决策过程。如果上述问题换一种情况,例如:
设有N个点:1,2,…,N 。任两点i-j之间有一弧连结,其长度 为Cij(可代表为费用、距离等),0<Cij≦∞表示i与j之间不存在 5 3 连结它们的弧。今设N为固定点, 2 7 5 2 4 1 试求任一点i至固定点N的最短距离。 5 具体地说:假如N=5,Cij如图所示。
6 5
1

2

0.5

3

这就是一个阶段不固定的最短路线问题。因此,对于线路中 途是否经过别的点,经过多少别的点,全无限制。而阶段数是 不定的,其阶段数应由问题的条件和最优函数确是待求的未知 数。下面我们介绍动态规划中的两种常用的迭代法:函数迭代 法和策略迭代法

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 51

三、函数迭代法和策略迭代法 1、函数迭代法:

其基本思想是以段数(步骤)作为参变数,先求在各个不同阶段 数下的最优策略,然后从这些最优解中再选出最优者,从而同时
确定最优段数。 步骤1:先选定初始函数分f1(i) f1(i)=CiN i=1,2,…,N-1; fr(N)=0 i=N 步骤2:用下列递推关系求出{fk(i)} (1)

? ? Cij ? f k ?1 ( j ) ? ? f k (i) ? min ? ? j ? ? ? fk ( N ) ? 0

j ? i,i=1,2, ,N-1 k>1

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 52

这里fk(i)表示由i点出发至多经过k步到达固定点N的最短路线, 当k增大时,fk(i)逐渐逼近问题的最优解f(i),故此方法称为函数 迭代法 定理2:由(1),(2)式得到的函数序列{fk(i)}收敛于问题的最优解 f(i)且不超过n-1步收敛于函数f(i) 函数迭代法的实质是先找出所有一步到达的路线中的最优者, 其次再找出所有二步内到达到的路线中的最优者。如此继续下去。 不是最优者,所以最优路线必须在n步之内求出。 对于上述例子 f1(1)=C15=2; f1(2)=C25=7;f1(3)=C35=5;f1(4)=C45=3 再逐次递推求{fk(i)}

由于总共只有n个点,如果超过n步,将产生回路,相应的路线必然

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 53

K=2

u*(i)

f 2 (2) ? min ? C2 j ? f1 ( j ) ? ? min ?6 ? 2,0 ? 7,0.5 ? 5,5 ? 3,7 ? 0? ? 5.5 3 ? ? j f 2 (3) ? min ? C3 j ? f1 ( j ) ? ? min ?5 ? 2,0.5 ? 7,0 ? 5,1 ? 3,5 ? 0? ? 4 4 ? ? j 5 f 2 (4) ? min ? ?C4 j ? f1 ( j ) ? ? ? min ? 2 ? 2,5 ? 7,1 ? 5,0 ? 3,3 ? 0? ? 3
j

f 2 (1) ? min ? ?C1 j ? f1 ( j ) ? ? ? min ?0 ? 2,6 ? 7,5 ? 5, 2 ? 3, 2 ? 0? ? 2
j

5

注意:在计算机中由I到I也算是一步,此时Cii=0 K=3 5 ? f3 (1) ? min ? C ? f ( j ) ? min 0 ? 2,6 ? 5.5,5 ? 4, 2 ? 3, 2 ? 0 ? 2 ? ? 1 j 2 ? ?
j j

f3 (2) ? min ? ?C2 j ? f 2 ( j ) ? ? ? min ?6 ? 2,0 ? 5.5,0.5 ? 4,5 ? 3,7 ? 0? ? 4.5 3

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 54

f3 (3) ? min ? ?C3 j ? f 2 ( j ) ? ? ? min ?5 ? 2,0.5 ? 5.5,0 ? 4,1 ? 3,5 ? 0? ? 4 4 f3 (4) ? min ? ?C4 j ? f 2 ( j ) ? ? ? min ? 2 ? 2,5 ? 5.5,1 ? 4,0 ? 3,3 ? 0? ? 3
j j j

5 5

f 4 (2) ? min ? C2 j ? f3 ( j ) ? ? min ?6 ? 2,0 ? 4.5,0.5 ? 4,5 ? 3,7 ? 0? ? 4.5 3 ? ? j f 4 (3) ? min ? C3 j ? f3 ( j ) ? ? min ?5 ? 2,0.5 ? 4.5,0 ? 4,1 ? 3,5 ? 0? ? 4 4 ? ? j f 4 (4) ? min ? ?C4 j ? f 4 ( j ) ? ? ? min ? 2 ? 2,5 ? 4.5,1 ? 4,0 ? 3,3 ? 0? ? 3 5
j

f 4 (1) ? min ? ?C1 j ? f3 ( j ) ? ? ? min ?0 ? 2,6 ? 4.5,5 ? 4, 2 ? 3, 2 ? 0? ? 2

K=4

f 4 (5) ? 0
因为 f3 (i) ? f 4 (i) ? 计算结果如下表

? f (i)

即收敛且步数不超过N-1=4

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 55

u*(i)是根据最短距离的数字,找出对应的最优决策,即找出由i城
出发至5城的最优路线中下一个应到达的城市。但要注意不能取 含有Cii=0的地方作u*(i) i f1 f2 f3 f4 2.策略迭代法u*(i) 1 2 2 2 2 5 2 7 5.5 4.5 4.5 4 3 5 4 4 4 3 4 3 3 3 3 5

其基本思想是:先给出一个没有回路的初始策略{u0(i)}
(i=1,2,…N-1),然后按某种迭代的公式,逐次求得新的策略 U (i),u (i),…直至最终求出最优策略。

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 56

步骤1:先一个没有回路的初始策略{u0(i)}(i=1,2,…,N-1),u0(i)表示在 此策略下由I到达的下一个点。 步骤2:由策略uk(i)求相应的指标函数fk(i),由
? ? f k (i ) ? Ci ,uk ( i ) ? f k (uk (i )) ? ? ? fk ( N ) ? 0 i=1,2, ,N-1

解出,其中Ci,uk(i)为已知 步骤3:由指标函数fk(i)求决策{uk+1(i)},uK+1(i)是

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 57

城市i

1

2

3

4

u0(i)
f0(i) u1(i) f1(i) u2(i) f2(i) u3(i)

5
2 5 2 5 2 5

4
11 3 5.5 3 4.5 3

5
5 5 5 4 4 4

3
6 5 3 5 3 5

从而u3(i)=u2(i) ,i=(1,2,3,4,5) , 找到最优策略u*(i)=(5,3,4,5) , 最短路线解同前 一样。 1---?5 最短距离=2 2--?3-?4-?5 最短距离= 4.5 ,4 ,3

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 58

5.生产计划问题 一、生产计划问题 一个生产项目,在生产批量、生产的成本费用、存贮费用以及市场对产品的 需求情况都是确定数值的条件下,为了根据实际需要制定计划,必需确定不同时期 的生产量和库存量。这个问题也是一个多阶段决策问题。 我们把计划分为几个时期,即为不同的阶段,如果在某个阶段上,增加生产 批量,可以降低成本,但超过了市场需求量,就要存贮,当然需要库存量,因此, 不同时期(阶段)的产量决定了该时期的成本和库存费用,同时,又影响了下一时 期(阶段)的产量和费用。 我们假定 1.按时满足市场对产品的需求量;2. 最末阶段库存量为0 ;3.本时期 最终库存量加上下时期中生产数量,可供下一时期的任何时间使用;4.每个阶段库 存费按本阶段最终的库存量计算。 我们的目标是确定生产计划,使总的生产费用和库存费用之和为最小。

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 59

例如:书P29

生产周期数 i 市场需求量 di

1

2

3

4

5

6

8

4

6

2

10

4

*把生产周期划分成阶段 *状态变量X k为第k个生产周期(阶段)开始的库存量 *决策变量u k为第k个生产周期(阶段)的生产量 *状态转移系数 Xk+1=X k+u k-d k ,其中d k为第k个阶段的需求量。

*指标函数 2014年8月23日星期六 各阶段生产成本费用和库存量之和-----总费用Ck(Xk+1,uk) Ck(Xk+1,uk)=-Xk+1

第8章 动态规划 Dynamic Programming
Page 60

?20 ? 5uk ? ?? ? ? 0 ?

(X7=0)

步骤1:第6阶段:由于最末周期库存量为0,因此,若开始的 存贮量为k,则生产量为d6-k,其最优费用就是C6(x6,u6)
周期开始的存贮 量K 生产量Z=d6-K f6(Z)

0 4 40

1 3 35

2 2 30

3 1 25

4 0 0

步骤2:第5阶段:共有15个状态,对应的周期开始存贮量 Page 61 2014年8月23日星期六 的0、1、2、……、14

第8章 动态规划 Dynamic Programming

对k=0,

f5 ? 0 ? ? min ?? 20 ? 5 ?10 ? 0 ? ? 40, ? 20 ? 5 ?11 ? 1? ? 35, ? 20 ? 5 ?12 ? 2 ? ? 30,
10? z ?14

? 20 ? 5 ?13 ? 3? ? 25, ? 20 ? 5 ?14 ? 4? ? 0? ? 94
对k=1,

U 5 ? 0 ? ? 14

f5 ?1? ? min ?? 20 ? 5 ? 9 ? 0 ? ? 40, ? 20 ? 5 ?10 ? 1? ? 35, ? 20 ? 5 ?11 ? 2 ? ? 30,
9? z ?13

? 20 ? 5 ?12 ? 3? ? 25, ? 20 ? 5 ?13 ? 4? ? 0? ? 89

U 5 ?1? ? 13

.
. .

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 62

对k=10

f5 ?10 ? ? min ?? 0 ? 0 ? ? 40, ? 20 ? 5 ?1 ? 1? ? 35, ? 20 ? 5 ? 2 ? 2 ? ? 30,
0? z ? 4

? 20 ? 5 ? 3 ? 3? ? 25, ? 20 ? 5 ? 4 ? 4 ? ? 0? ? 40
对k=11

U 5 ?10 ? ? 0

f5 ?11? ? min ?? 0 ? 1? ? 35, ? 20 ? 5 ?1 ? 2 ? ? 30, ? 20 ? 5 ? 2 ? 3 ? ? 25,
0? z ?3

? 20 ? 5 ? 3 ? 4 ? ? 0? ? 36

U 5 ?11? ? 0

8.3 生产与存储问题
Production and inventory problem

8.3 生产与存储问题 Production and inventory problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 64

【8.4】一个工厂生产某种产品,1~6月份生产成本和产品需求量 的变化情况见表8-9
表8-9 月份(k) 需求量(dk) 单位产品成本(ck) 1 20 15 2 30 12 3 35 16 4 40 19 5 25 18 6 45 16

没有生产准备成本,单位产品一个月的存储费为hk=0.6元, 月底交货。分别求下列两种情形6个月总成本最小的生产方案。 (1)1月初与6月底存储量为零,不允许缺货,仓库容量为 S=50件,生产能力无限制; (2)其它条件不变,1月初存量为10

8.3 生产与存储问题 Production and inventory problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 65

【解】动态规划求解过程如下。 阶段k:月份,k=1,2,…,7 状态变量sk:第k个月初的库存量 决策变量xk:第k个月的生产量 状态转移方程:sk+1=sk+xk-dk
决策允许集合: Dk ( sk ) ? xk xk ? 0,0 ? sk ? xk ? d k ? 50

?

?

阶段指标: v ( s , x ) ? c x ? h s ? c x ? 0.6s k k k k k k k k k k
终端条件:f7(s7)=0, s7=0 递推方程:
f k ( xk ) ? min ? min
xk ?Dk ( sk )

?vk (sk , xk ) ? ?vk (sk , xk ) ?

f k ?1 ( sk ?1 )? f k ?1 ( sk ? xk ? d k )?

xk ?Dk ( sk )

8.3 生产与存储问题 Production and inventory problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 66

当k=6时,因为s7=0,有 s7 ? s6 ? x6 ? d6 ? s6 ? x6 ? 45 ? 0, x6 ? 45 ? s6 , s6 ? 45 f 6 ( s6 ) ? min ?16 x6 ? 0.6 s6 ? f 7 ( s7 ) }
= min ?16 x6 ? 0.6 s6 } ? ?15.4 s6 ? 720
x6 ? 45 ? s6 x6 ? 45 ? s6 * x6 ? 45 ? s6

当k=5时,由0 ? s6 ? 45,0 ? s5 ? x5 ? d5 ? s5 ? x5 ? 25 ? 45, 得25 ? s5 ? x5 ? 70 ? s5 由于s5≤50,则当25-s5<0时x5的值取“0”,决策允许集合为 D5 ( s5 ) ? ? x5 max[0, 25 ? s5 ] ? x5 ? 70 ? s5 ?
f5 ( s5 ) ? min ?18 x5 ? 0.6s5 ? f 6 ( s6 )}
x5 ?D5 ( s5 )

? min ?18 x5 ? 0.6s5 ? 15.4s6 ? 720} ? min
x5 ?D5 ( s5 ) x5 ?D5 ( s5 )

?2.6 x5 ? 14.8s5 ? 1105}

(其中s6 ? s5 ? x5 ? 25)

??17.4s5 ? 1170 ?? ??14.8s5 ? 1105

* s5 ? 25时,取下界:x5 ? 25 ? s5 * s5 ? 25时,取下界:x5 ?0

8.3 生产与存储问题 Production and inventory problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 67

k=4时, 0 ? s5 ? 25,0 ? s4 ? x4 ? 40 ? 25, 有 40 ? s4 ? x4 ? 65 ? s4 决策允许集合为 D4 ( s4 ) ? ? x4 max[0, 40 ? s4 ] ? x4 ? 65 ? s4 ?
f 4 ( s4 ) ? min ?19 x4 ? 0.6 s4 ? f 5 ( s5 )}
x4 ?D4 ( s4 ) x4 ?D4 ( s4 ) x4 ?D4 ( s4 )

? min ?19 x4 ? 0.6 s4 ? 17.4 s5 ? 1170} ? min ?1.6 x4 ? 16.8s4 ? 1866} ??18.4 s4 ? 1930 ?? ??16.8s4 ? 1866
* s4 ? 40, x4 ? 40 ? s4 * 40 ? s4 ? 50, x4 ?0

25 ? s5 ? 50,x5 =0,25 ? s4 ? x4 ? 40 ? 50, 有 D4 ( s4 ) ? ? x4 65 ? s4 ? x4 ? 90 ? s4 ?
f 4(1) ( s4 ) ? min ?19 x4 ? 0.6 s4 ? f 5 ( s5 )}
x4 ?D4 ( s4 )

? min ?19 x4 ? 0.6 s4 ? 14.8s5 ? 1105} ? min
x4 ?D4 ( s4 ) x4 ?D4 ( s4 )

?4.2 x4 ? 14.2 s4 ? 1697}

? ?18.4 s4 ? 1970

* 取下界:x4 ? 65 ? s4

8.3 生产与存储问题 Production and inventory problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 68

显然该决策不可行,x5=0,s4+x4=65=d4+d5,s5=s6=0,x6=45, 与s5≥25矛盾。因此有
* ??18.4s4 ? 1930 0 ? s4 ? 40, x4 ? 40 ? s4 并且0 ? s5 ? 25, x5 ? 25 ? s5 f 4 (s4 ) ? ? * ? 16.8 s ? 1866 40 ? s ? 50, x 并且0 ? s5 ? 25, x5 ? 25 ? s5 4 4 4 ?0 ?

k=3,当0≤s4≤40时,

0 ? s3 + x3 ? 35 ? 40
D3 ( s3 ) ? ? x3 max[0,35 ? s3 ] ? x3 ? 75 ? s3 ?
f3 ( s3 ) ? min ?16 x3 ? 0.6s3 ? f 4 ( s4 )}
x3?D3 ( s3 )

? min ?16 x3 ? 0.6s3 ? 18.4s4 ? 1930} ? min
x3 ?D3 ( s3 ) x3 ?D3 ( s3 )

??2.4 x3 ? 17.8s3 ? 2574}

? ?15.4s3 ? 2394

* 取上界:x3 ? 75 ? s3

8.3 生产与存储问题 Production and inventory problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 69

当40≤s4≤50时, 40 ? s3 + x3 ? 35 ? 50 D3 ( s3 ) ? ? x3 75 ? s3 ? x3 ? 85 ? s3 ?
f3 ( s3 ) ? min ?16 x3 ? 0.6s3 ? f 4 ( s4 )}
x3?D3 ( s3 )

? min ?16 x3 ? 0.6s3 ? 16.8s4 ? 1866} ? min
x3 ?D3 ( s3 ) x3 ?D3 ( s3 )

??0.8 x3 ? 16.2s3 ? 2454}

? ?15.4s3 ? 2386

* 取上界:x3 ? 85 ? s3

当k=2时,由 40 ? s4 ? 50,0 ? s3 ? 50,0 ? s2 ? x2 ? 30 ? 50, 有

x2的决策允许集合为 D2 ( s2 ) ? ? x2 max[0,30 ? s2 ] ? x2 ? 80 ? s2 ?
f 2 ( s2 ) ?

30 ? s2 ? x2 ? 80 ? s2

?12 x2 ? 0.6s2 ? f3 ( s3 )? ? min ?12 x2 ? 0.6s2 ? 15.4s3 ? 2386? 30 ? s ? x ? 65? s ? min ??3.4 x2 ? 14.8s2 ? 2848? 30 ? s ? x ? 65? s
30 ? s2 ? x2 ? 65? s2
2 2

min

2

? ?11.4s2 ? 2576

2

2

2

* 取上界:x2 ? 80 ? s2

8.3 生产与存储问题 Production and inventory problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 70

0 ? s1 ? x1 ? 20 ? 50, 20 ? s1 ? x1 ? 70 ? s1 当k=1时,由 0 ? s2 ? 50,
只要期初存量s1≤20,则x1的决策允许集合为

D1 ( s1 ) ? ? x1 20 ? s1 ? x1 ? 70 ? s1?

f1 ( s1 ) ? min ?15 x1 ? 0.6s1 ? f 2 ( s2 )?
x1?D1 ( s1 ) x1?D1 ( s1 ) x1?D1 ( s1 )

? min ?15 x1 ? 0.6s1 ? 11.4s2 ? 2584? ? min ?3.6 x1 ? 10.8s1 ? 2804? ? ?14.4s1 ? 2876
* 取下界:x1 ? 20 ? s1

(1)期初存储量s1=0,由各阶段的最优决策xj*及状态转移方程, 回朔可求出最优策略。

8.3 生产与存储问题 Production and inventory problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 71

x1=20, x2=80, x3=85-50=35, x4=0, x5=25-s5=15, x6=45。 总成本为2876

s2=s1+x1-d1=0+20-20=0, s3=s2+x2-d2=0+80-30=50, s4=s3+x3-d3=50+35-35=50>40, s5=50-0-40=10<25, s6=10+15-25=0,

1~6月份生产、存储详细计划表见表8-10所示。 (2)期初存储量s1=10,与前面计算类似,得到x1=10,x2=80, x3=35,x4=0,x5=15,x6=45。

8.3 生产与存储问题 Production and inventory problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 72

表8-10
月份(k) 需求量(dk) 单位产品成本(ck) 单位存储费hk 产量xk 期初存量sk 生产成本CK(xk) 1 20 15 0.6 20 0 300 2 30 12 0.6 80 0 960 3 35 16 0.6 35 50 560 4 40 19 0.6 0 50 0 5 25 18 0.6 15 10 270 6 45 16 0.6 45 0 720 195 110 2810 合计 195

存储成本Hk(sk)
合计

0

0

30

30

6

0

66
2876

8.3 生产与存储问题 Production and inventory problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 73

80 70 60 50 40 30 20 10 0 1 2 3 4 5 6
期初存量sk 需求量(dk) 产量xk

8.3 生产与存储问题 Production and inventory problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 74

作业:教材P189 T 7 下一节:背包问题

8.4 背包问题
Knapsack Problem

8.4 背包问题 Knapsack Problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 76

背包问题数学模型为 max Z ? c1 x1 ? c 2 x 2 ? ? ? c n x n

?w1 x1 ? w2 x 2 ? ? ? wn x n ? W ? ? xi ? 0且为整数,i ? 1, ? , n
式中: ck为第k种物品的单位价值,wk是第k种物品的单位重量或体积, W是背包的重量或体积限制。动态规划的有关要素如下。 阶段k:第k次装载第k种物品(k=1,2,…,n) 状态变量sk:第k次装载时背包还可以装载的重量(或体积) 决策变量xk:第k次装载第k种物品的件数 决策允许集合:Dk(sk)={dk|0? xk?sk/wk,xk为整数} 状态转移方程:sk+1=sk-wkxk 阶段指标:vk=ckxk

8.4 背包问题 Knapsack Problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 77

递推方程: f k ( s k ) ? max?ck xk ? f k ?1 ( s k ?1 )?

? max ?c k x k ? f k ?1 ( s k ? wk x k )?

终端条件:fn+1(sn+1)=0 【例8.5】用动态规划方法求解下列整数规划
max Z ? 60x1 ? 40x2 ? 60 x3 ?3x1 ? 2x2 ? 5 x3 ? 10 ? ? x1 , x2 , x3 ? 0且为整数

【解】终端条件: f4(x4)=0 k=3时,递推方程

f 3 (s3 ) ? max {c3 x3 ? f 4 (s4 )} ? max {60 x3 }
0? x3 ? s3 / w3 0? x3 ? s3 / 5

8.4 背包问题 Knapsack Problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 78

表8-11
s3 0 1 … 5 … D3(s3)={x3|[s3/5]} 0 0 …… 0 1 …… 0 1 2 s4 0 1 …… 5 0 …… 10 5 0 60x3+f4(s4) 0+0=0 0+0=0 …… 0+0=0 60+0=60* …… 0+0=60 60+0=60 120+0=120* f3(s3) 0 0 …… 0 60 …… x3* 0 0 0 1 1

10

120

2

最优决策是;s3为0~4时,x3=0,s3为5~9时,x3=1,s3=10 时,x3=2。 k=2时,递推方程
f 2 (s 2 ) ? max {c2 x2 ? f 3 (s3 )} ? max {40 x2 ? f 3 (s 2 ? 2 x2 )}
0? x2 ? s2 / w2 0 ? x2 ? s 2 / 2

8.4 背包问题 Knapsack Problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 79

表8-12
s2
0 1

D2(s2)
0 0 0 1 0 1
0 1 2

s3
0 1 2 0 3 1
4 2 0

40x2+f3(s3)
0+f3(0)=0+0=0* 0+0=0 0+0=0 40+0=40* 0+0=0 40+0=40*
0+0=0 40+0=40 80+0=80

f2(s2)
0 0

x2*
0 0

2
3

40
40

1
1

4
5

80
80

2
2

0 1 2

5 3 1

0+60=60 40+0=40 80+0=80*



……
0 1 2 3 4 5

……
10 8 6 4 2 0

……
0+120=120 40+60=100 80+60=140 120+0=120 160+0=160 200+0=200*

……

10

200

5

8.4 背包问题 Knapsack Problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 80

第2阶段的最优决策见表8-13
表8-13 s2 f2(s2) x2 0 0 0 1 0 0 2 1 3 1 4 2 5 2 6 3 7 3 8 4 9 4 10 200 5

40 40 80 80 120 120 160 160

k=1时,递推方程

f1 (s1 ) ? max {c1 x1 ? f 2 (s2 )} ? max {60 x1 ? f 2 (s1 ? 3x1 )}
0? x1 ? s1 / w1 0? x1 ? s1 / 3

8.4 背包问题 Knapsack Problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 81

s1=10,w1=3,D1(s1)={0,1,2,3},计算结果见表8-14 表8-14
s1 D 1 ( s1 ) 0 1 2 3 s2 10 7 4 1 60x1+f2(s2) 0+f2(10)=0+200=200* 60+120=180 120+80=200* 180+0=180 f1(s1) x1*

10

200

0,3

由表8-14、8-13、8-11,得到两个最优解:X1=(0,5,0), X2=(3,2,0),最优值Z=200。

8.4 背包问题 Knapsack Problem

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 82

作业:教材P189 T5

下一节:其它动态规划模型

8.5 其它动态规划模型
Other Model of DP

8.5 其它动态规划模型 Other Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 84

8.5.1求解线性规划模型 【例8.6】用动态规划方法求解下列线性规划
max Z ? 6 x1 ? 5 x2 ? 8 x3 ? 20 ?3 x1 ? 2 x2 ? ? x1 ? 4 x2 ? 4 x3 ? 14 ?x , x , x ? 0 ? 1 2 3

【解】首先将问题转化为动态规划模型 阶段数为3,决策变量为xk,状态变量为第k阶段初各约束条件 右端常数的剩余值,用s1k和s2k表示,状态转移方程为 s1,k+1=s1k-a1kxk,s2,k+1=s2k-a2kxk 终端条件 f 4 ( s14 , s24 ) ? 0

8.5 其它动态规划模型 Other Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 85

k=3时,决策变量x3的允许集合 ? ? s13 s23 ? ? ? ? D3 ( si 3 ) ? ? x3 | 0 ? x3 ? min ? , ? ? , a13 ? 0, a23 ? 4 ? ? a13 a23 ? ? ? ?

s23 ? ? D3 ( si 3 ) ? ? x3 | 0 ? x3 ? ? 4? ?
f3 ( s13 , s23 ) ? max
0 ? x3 ? s23 4

?c3 x3? ? max

0 ? x3 ? s23 4

?8 x3 ? ? 2s23

* x3 ? s23 4

k=2时,决策变量x2的允许集合

? ? s12 s22 ? ? ? ? D2 ( si 2 ) ? ? x2 | 0 ? x2 ? min ? , ? ? , a12 ? 2, a22 ? 4 ? ? a12 a22 ? ? ? ?
? ? s12 s22 ? ? D2 ( si 2 ) ? ? x2 | 0 ? x2 ? min ? , ? ? ? 2 4 ?? ?

8.5 其它动态规划模型 Other Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 86

状态转移方程为

s13 ? s12 ? 2 x2 , s23 ? s22 ? 4 x2

f 2 ( s12 , s22 ) ? ? ?

?s s ? 0 ? x2 ? min ? 12 , 22 ? ? 2 4 ? ?s s ? 0 ? x2 ? min ? 12 , 22 ? ? 2 4 ? ?s s ? 0 ? x2 ? min ? 12 , 22 ? ? 2 4 ?

max

?c2 x2 ? f3 (s13 , s23 )? ?

?s s ? 0? x2 ? min ? 12 , 22 ? ? 2 4 ?

max

?5 x2 ? 2s23 ?

max max

?5 x2 ? 2( s22 ? 4 x2 )? ?2s22 ? 3x2 ?
* x2 ?0

? 2s22

8.5 其它动态规划模型 Other Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 87

k=1时,决策变量x1的允许集合
? ? s11 s21 ? ? ? ? D1 ( si1 ) ? ? x1 | 0 ? x1 ? min ? , ?? a a ? ? 11 21 ? ? ? ? ? ? 20 ?? ? ? x1 | 0 ? x1 ? min ? ,14 ? ? ? 3 ?? ?

状态转移方程
s12 ? s11 ? 3x1 ? 20 ? 3x1 s22 ? s21 ? x1 ? 14 ? x1

f1 ( s11 , s21 ) ? ? ?
x1 ?

? 20 ? 0? x1 ? min ? ,14 ? ? 3 ?

max

?c1 x1 ? f 2 (s12 , s22 )? ?6 x1 ? 2(14 ? x1 )?
164 3
* x1 ?

? 20 ? 0? x1 ? min ? ,14 ? ? 3 ?

max max

? 20 0? x1 ? min ? ,14 ? ? 3 ?

?4 x1 ? 2 ?14? ? ?

20 3

s 20 20 22 22 11 , s12 ? 0, s22 ? 14 ? , x2 ? 0, s13 ? 0, s23 ? , x3 ? 23 ? 3 3 3 3 4 6 20 11 ? 164 最优解: X ? ? , 0, , Z ? ? ? 6? 3 ? 3

8.5 其它动态规划模型 Other Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 88

8.5.1求解非线性规划模型 【例8.7】用动态规划方法求解下列非线性规划 max Z ? x1 x2 x3
? x1 ? 5 x2 ? 2 x3 ? 20 ? ? x1 , x2 , x3 ? 0

【解】阶段数为3,决策变量为xk,状态变量sk为第k阶段初约 束条件右端常数的剩余值,状态转移方程为sk+1=sk-akxk,阶 段指标是xk,递推方程为

f k ( sk ) ? max ? xk ? f k ?1 ( sk ?1 )?
xk ?D ( sk )

8.5 其它动态规划模型 Other Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 89

终端条件 f 4 ( s4 ) ? 1 k=3时,决策变量允许集合

? s3 s3 ? D3 ( s3 ) ? ? x3 | 0 ? x3 ? ? ? a3 2 ? ?
递推方程

f3 ( s3 ) ? max ? x3 f 4 ( s4 )?
0? x3 ? s3 2

s3 ? max ? x3 ? ? s 2 0? x3 ? 3
2

s3 x ? 2
* 3

8.5 其它动态规划模型 Other Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 90

k=2时,决策变量允许集合

? s2 s2 ? D2 ( s2 ) ? ? x2 | 0 ? x2 ? ? ? a2 5 ? ?
状态转移方程s3=s2-5x2 递推方程
f 2 ( s2 ) ? max ? x2 f3 ( s3 )?
0? x2 ? s2 5

?1 ? ? max ? x2 s3 ? s 0? x2 ? 2 ? 2 ? 5 ?1 ? 1 2 ? max ? x2 ( s2 ? 5 x2 ) ? ? s2 s2 2 0? x2 ? ? ? 40 5 s2 x ? 10
* 2

8.5 其它动态规划模型 Other Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 91

k=1时,决策变量允许集合
? ? s1 D1 ( s1 ) ? ? x1 | 0 ? x1 ? ? 20 ? a1 ? ? 状态转移方程s2=20-x1

递推方程

?1 2? f1 ( s1 ) ? max ? x1 f 2 ( s2 )? ? max ? x1s2 ? 0 ? x2 ? 20 0 ? x1 ? 20 40 ? ? ?1 ? ? max ? x1 (20 ? x1 ) 2 ? 0 ? x1 ? 20 40 ? ? ?1 3 ? ? max ? x1 ? x12 ? 10 x1 ? 0 ? x1 ? 20 40 ? ? 800 20 * ? x1 ? 27 3

得到最优解

800 ? 20 4 10 ? X ? ? , , ? ,Z ? 27 ? 3 3 3?

T

8.5 其它动态规划模型 Other Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 92

8.5.3设备更新问题 设备更新问题在第6章的例6.8曾用Dijkstra算法求解,也能用 动态规划方法求解。设一台设备已使用了(役龄)T年,对一台 使用寿命为n年的设备,怎样制定在n年中每年是更新(Keep) 还是继续使用(Replace)策略,使n年的总收益最大或总成本 最低。下面以总成本最低为标准讨论设备更新的动态规划求 解方法。 P(t):第t年新设备的购置成本,t=0,1,2,…,n。 C(t)是设备第t年的维修费用。这里的t从T年后开始计算, t=0,1,2,…,n,新设备的役龄为t=0。如设备已使用了两 年(T=2),继续使用时第1年t等于0,不是等于1。 S(t)为旧设备第t年出售的价格; R(t)为在n年末,役龄为t的设备残值;

8.5 其它动态规划模型 Other Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 93

阶段k:设备运行年份; 状态变量sk:设备的役龄t; 决策变量xk: ? R 更新
xk ? ? ?K 继续使用

状态转移方程

s k ?1

xk ? R ?1 ?? ? xk ? 1 xk ? K

阶段指标是更新或继续使用的总成本:
? P ( s k ) ? C ( 0) ? S ( s k ) vk ? ? ?C ( s k ) ? P (t ) ? C (0) ? S (t ) ?? ?C (t ) dk ? R dk ? K xk ? R xk ? K

8.5 其它动态规划模型 Other Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 94

递推方程
? P( s k ) ? C (0) ? S ( s k ) ? f k ?1 ( s k ?1 ) f k ( s k ) ? min ? ?C ( s k ) ? f k ?1 ( s k ?1 ) ? P(t ) ? C (0) ? S (t ) ? f k ?1 (t ? 1) ? min ? ?C (t ) ? f k ?1 (t ? 1) xk ? R xk ? K xk ? R xk ? K

终端条件

fn(t)=-R(t)

8.5 其它动态规划模型 Other Model of DP

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 95

作业:教材P189 T 3,4,10

The End of Chapter 8

第8章 动态规划 Dynamic Programming
2014年8月23日星期六

Page 96

习题8.10(1)


赞助商链接
相关文章:
更多相关标签: