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

运筹学第七章动态规划


第七章 动态规划
动态规划的基本概念和基本原理 动态规划的基本思路 动态规划模型的建立 动态规划思路求解静态问题

多阶段决策过程
状态1 状态

决策1 决策1

状态2 状态

决策2 决策2

状态3 状态

……

状态n 状态

决策n 决策n 动态规划的分类: 动态规划的分类: 离散确定型 连续确定型 离散随机型 连续随机型

应用:最优调度、资源分配、 应用:最优调度、资源分配、最优路径 最优控制、设备更新、 最优控制、设备更新、库存问题

动态规划的基本概念
2 B1 4 A 5 B2 7 C4
k=1 k=2 k=3 k=4 k=5

C1 3 8 4 C2 3 7 C3 8

5 D1 D2 4 4 D3 1 3 6 2 E2 3 5 E1 4 3 F

6 8

5

1、阶段 、 阶段变量: 阶段变量:k 2、状态 、 每个阶段开始所处的自然状态或客观条件 状态变量: 状态变量:s k s k∈ S k 状态集合: 状态集合:S k

无后效性:如果某阶段的状态给定, 无后效性:如果某阶段的状态给定,这阶段以后 过程的发展不受这阶段以前各阶段状态的影响
3、决策、策略 、决策、 (1)决策:某阶段状态确定后,为确定下一阶段的 )决策:某阶段状态确定后, 状态,所作出的决定(选择)。 状态,所作出的决定(选择)。 决策变量: 表示第k阶段状态为 阶段状态为s 决策变量:u k(s k) 表示第 阶段状态为 k时的决策

允许决策集合: 允许决策集合:D k ( s k ) u k(s k) ∈ D k ( s k ) (2)策略: )策略: 各阶段的决策确定后, 各阶段的决策确定后,整个问题的决策序列就构 成一个策略。 成一个策略。p 1 , n { u 1(s 1) , u 2(s 2) , … , u n(s n) } 子策略: 子策略:从某个阶段开始到过程最终的决策序列 p k , n { u k(s k) , u k+1(s k+1) , … , u n(s n) } 最优策略: 最优策略: p* 1 , n 4、状态转移方程 、 从s k的某一状态值到下阶段s k+1某一状态值的转 移规律

状态转移方程: 状态转移方程:s k+1 = T k ( s k , u k )

5、指标函数: 、指标函数: 衡量策略优劣的数量指标 表示第k阶段 (1)阶段指标函数:dk ( s k , u k )表示第 阶段, )阶段指标函数: 表示第 阶段, 从状态s 出发,采取决策u 从状态 k 出发,采取决策 k 时的效益
(2)过程指标函数 V k , n ( s k , p k , n ): ) : 从第k阶段状态 开始到终点, 从第 阶段状态 s k 开始到终点,采用某个子策略 p k , n 时,按预定标准得到的效益值。 按预定标准得到的效益值。 V 1,n( s 1 , p 1,n)

fk (sk ) = V ,n (sk , p*k,n ) k
阶段到第n阶段的最优指标函数 第k阶段到第 阶段的最优指标函数 阶段到第

f1 (s1 ) = V ,n (s1 , p*1,n ) 全过程的最优指标函数 1

动态规划的基本思路
求解离散确定型动态规划, 求解离散确定型动态规划,以最短路问题为例
逆序法: 逆序法: (13) 2 B1 (17) 4 A 3 6 5 (15)8 7 B2 7 (12) C1 (10) C2 8 4 5 5 (7) D1 (5) 6 D2 3 5 (4) E1 4 (0) F

(8) 3 C3 4 (9) 8 C4 4

1 (5) 3 D3

2 (3) 3 E2

2 4 A 5 B2 B1 8 3 6 7 7

C1 8 C2 C3 8 C4 4

5 D1 D2 D3 6 1 3 5 2 3 E2 E1 4 3 F

5 3 4 4

解:该问题划分为5个阶段 k=1,2,3,4,5 sk 表示各 该问题划分为 个阶段 阶段的状态, 表示从第k阶段状态 阶段的状态, f k ( sk)表示从第 阶段状态 k到终点 表示从第 阶段状态s F的最短距离 的最短距离 k=5 S 5 ={ E1 , E2 } f 5 ( E1) = 4 u*5 ( E 1 ) = F f 5 ( E2) = 3 u*5 ( E 2 ) = F

k=4

S 4 ={ D1 , D2 , D3 }

?d(D1 , E1 ) + f5 (E1 ) ? = m ?3 + 4? = 7 f4 (D1 ) = m ? in ? in ?5 + 3? ? ? ?d(D1 , E2 ) + f5 (E2 )?
u*4 ( D 1 ) = E1

?d(D2 , E1 ) + f5 (E1 ) ? = m ?6 + 4? = 5 f4 (D2 ) = m ? in ? in ?2 + 3? ? ? ?d(D2 , E2 ) + f5 (E2 )?
u*4 ( D 2 ) = E2

?d(D3 , E1 ) + f5 (E1 ) ? = m ?1+ 4? = 5 f4 (D3 ) = m ? in ? in ?3 + 3? ? ? ?d(D3 , E2 ) + f5 (E2 )?
u*4 ( D 3 ) = E1

k=3

S 3 ={ C1 , C2 , C3 , C4 }

?d(C1 , D1 ) + f4 (D1 ) ? = m ?5 + 7? = 12 f3 (C1 ) = m ? in ? in ?8 + 5? ? ? ?d(C1 , D2 ) + f4 (D2 )?
u*3 ( C 1 ) = D1

?d(C2 , D1 ) + f4 (D1 ) ? = m ?4 + 7? = 10 f3 (C2 ) = m ? in ? in ?5 + 5? ? ? ?d(C2 , D2 ) + f4 (D2 )?
u*3 ( C 2 ) = D2

?d(C3 , D2 ) + f4 (D2 )? = m ?3 + 5? = 8 f3 (C3 ) = m ? in ? in ?4 + 5? ? ? ?d(C3 , D3 ) + f4 (D3 )?
u*3 ( C 3 ) = D2

?d(C4 , D2 ) + f4 (D2 )? = m ?8 + 5? = 9 f3 (C4 ) = m ? in ? in ?4 + 5? ? ? ?d(C4 , D3 ) + f4 (D3 )?
u*3 ( C 4 ) = D3 k=2 S 2 ={ B1 , B2 }

?d(B1, C1 ) + f3 (C1 ) ? ?2 + 12? ? ? ? ? f2 (B1 ) = m ?d(B1, C2 ) + f3 (C2 )? = m ?3 + 10? = 13 in in ?6 + 8 ? ?d(B1, C3 ) + f3 (C3 )? ? ? ? ?
u*2 ( B 1 ) = C2

?d(B2 , C2 ) + f3 (C2 )? ?8 + 10? ? ? ? ? f2 (B2 ) = m ?d(B2 , C3 ) + f3 (C3 )? = m ?7 + 8 ? = 15 in in ?7 + 9 ? ?d(B2 , C4 ) + f3 (C4 )? ? ? ? ?
u*2 ( B 2 ) = C3

k=1

S 1 ={ A }

?d(A, B1 ) + f2 (B1 ) ? = m ?4 + 13? = 17 f1(A) = m ? in ? in ?5 + 15? ? ? ?d(A, B2 ) + f2 (B2 )?
u*1 ( A ) = B1

?d(C4 , D2 ) + f4 (D2 )? = m ?8 + 5? = 9 f3 (C4 ) = m ? in ? in ?4 + 5? ? ? ?d(C4 , D3 ) + f4 (D3 )?
u*3 ( C 4 ) = D3 k=2 S 2 ={ B1 , B2 }

?d(B1, C1 ) + f3 (C1 ) ? ?2 + 12? ? ? ? ? f2 (B1 ) = m ?d(B1, C2 ) + f3 (C2 )? = m ?3 + 10? = 13 in in ?6 + 8 ? ?d(B1, C3 ) + f3 (C3 )? ? ? ? ?
u*2 ( B 1 ) = C2

?d(B2 , C2 ) + f3 (C2 )? ?8 + 10? ? ? ? ? f2 (B2 ) = m ?d(B2 , C3 ) + f3 (C3 )? = m ?7 + 8 ? = 15 in in ?7 + 9 ? ?d(B2 , C4 ) + f3 (C4 )? ? ? ? ?
u*2 ( B 2 ) = C3

k=3

S 3 ={ C1 , C2 , C3 , C4 }

?d(C1 , D1 ) + f4 (D1 ) ? = m ?5 + 7? = 12 f3 (C1 ) = m ? in ? in ?8 + 5? ? ? ?d(C1 , D2 ) + f4 (D2 )?
u*3 ( C 1 ) = D1

?d(C2 , D1 ) + f4 (D1 ) ? = m ?4 + 7? = 10 f3 (C2 ) = m ? in ? in ?5 + 5? ? ? ?d(C2 , D2 ) + f4 (D2 )?
u*3 ( C 2 ) = D2

?d(C3 , D2 ) + f4 (D2 )? = m ?3 + 5? = 8 f3 (C3 ) = m ? in ? in ?4 + 5? ? ? ?d(C3 , D3 ) + f4 (D3 )?
u*3 ( C 3 ) = D2

k=4

S 4 ={ D1 , D2 , D3 }

?d(D1 , E1 ) + f5 (E1 ) ? = m ?3 + 4? = 7 f4 (D1 ) = m ? in ? in ?5 + 3? ? ? ?d(D1 , E2 ) + f5 (E2 )?
u*4 ( D 1 ) = E1

?d(D2 , E1 ) + f5 (E1 ) ? = m ?6 + 4? = 5 f4 (D2 ) = m ? in ? in ?2 + 3? ? ? ?d(D2 , E2 ) + f5 (E2 )?
u*4 ( D 2 ) = E2

?d(D3 , E1 ) + f5 (E1 ) ? = m ?1+ 4? = 5 f4 (D3 ) = m ? in ? in ?3 + 3? ? ? ?d(D3 , E2 ) + f5 (E2 )?
u*4 ( D 3 ) = E1

k=5

S 5 ={ E1 , E2 } u*5 ( E 1 ) = F u*5 ( E 2 ) = F

f 5(E1)= { d( E 1, F )+ f 6 ( F ) } = 4 f 5(E2)={ d( E 2, F ) + f 6 ( F ) } = 3 动态规划的基本方程: 动态规划的基本方程:

in{ ?fk (sk ) = m dk (sk , uk ) + fk+1(sk+1 )} ?f (s ) = 0 ?6 6
f k ( sk)表示从第 阶段状态 k到终点 的最短距离 表示从第k阶段状态 表示从第 阶段状态s 到终点F的最短距离

u*1 ( A ) = B1 u*4 ( D 2 ) = E2 f 1 ( A ) = 17 2 B1 4 A 5 B2 8 3 6 7 7

u*2 ( B 1 ) = C2 u*5 ( E 2 ) = F

u*3 ( C 2 ) = D2

C1 8 C2 C3 8 C4 4

5 D1 D2 D3 6 1 2 3 E2 3 5 E1 4 3 F

5 3 4 4

动态规划问题具有以下基本特征: 动态规划问题具有以下基本特征:
问题具有多阶段决策的特征。 1 、 问题具有多阶段决策的特征 。 阶段可以按时间 或按空间划分。 或按空间划分。 每一阶段都有相应的“ 状态” 与之对应, 2 、 每一阶段都有相应的 “ 状态 ” 与之对应 , 描述 状态的量称为“状态变量” 状态的量称为“状态变量”。 每一阶段都面临一个决策, 3 、 每一阶段都面临一个决策 , 选择不同的决策将 会导致下一阶段不同的状态。同时, 会导致下一阶段不同的状态 。同时 ,不同的决策 将会导致这一阶段不同的目标函数值。 将会导致这一阶段不同的目标函数值。 4 、 每一阶段的最优解问题可以递归地归结为下一 阶段各个可能状态的最优解问题, 阶段各个可能状态的最优解问题, 各子问题与原 问题具有完全相同的结构。 问题具有完全相同的结构。 能否构造这样的递推 归结,是解决动态规划问题的关键。 归结,是解决动态规划问题的关键。

动态规划的方法:
(1)逆序法 ) (2)顺序法 ) 2 B1 4 A 5 B2 8 3 6 7 7 C4 C2 C3 8 C1 8 4 5 3 4 4 D3 D2 1 3 5 D1 6 2 E2 3 5 E1 4 3 F

解:该问题划分为5个阶段 k=1,2,3,4,5 该问题划分为 个阶段 sk 表示各阶段的状态, f k ( sk+1)表示从起点 到 表示各阶段的状态, 表示从起点A到 表示从起点 阶段状态s 第k阶段状态 k+1的最短距离 阶段状态 k=0 k=1 k=2 f 0 (A) = 0 f 1 ( B1 ) = 4 f 1 ( B2 ) = 5 f 2 ( C1) = 6 f 2 ( C2) = 7 f 2 ( C3) = 10 f 2 ( C4) = 12 u*1 (B1 ) = A u*1 (B2 ) = A u*2 (C1 ) = B1 u*2 (C2 ) = B1 u*2 (C3 ) = B1 u*2 (C4 ) = B2

k=3

f 3 ( D1) = 11 f 3 ( D2) = 12 f 3 ( D3) = 11

u*3 (D1 ) = C1 / C2 u*3 (D2 ) = C2 u*3 (D3 ) = C3 u*4 (E1 ) = D1 u*4 (E2 ) = D2 u*5 (F ) = E2

k=4 k=5

f 4 ( E1) = 14 f 4 ( E2) = 14 f 5 ( F) = 17

最短路径长: A →B1 →C2 → D2 →E2 →F 最短路径长:17 动态规划的基本方程: 动态规划的基本方程:

in{ ?fk (sk+1 ) = m dk (sk+1, uk ) + fk?1(sk )} ?f (s ) = 0 ?0 1

(4) B1 (0) 4 A 5 (5) B2

2 3 6

(6) C1 (7) C2 (10) C3 7 (12) C4 4

5

(11) D1 (12) D2 (14) D3

3

(14) (17) F 2 (14) 3 E2 E1

5 4

动态规划问题的建模与求解
(1)关键:将多阶段过程划分阶段,确定状态变 )关键:将多阶段过程划分阶段, 决策变量、 量、决策变量、指标函数 (2)求解:从边界条件开始,逐渐递推寻优,每 )求解:从边界条件开始,逐渐递推寻优, 个子问题求解时都要用它前面已求出的子问题的 最优结果, 最优结果,最后一个子问题的最优解即整个问题 的最优解 (3)每段最优决策的选取是从全局考虑的,与该 )每段最优决策的选取是从全局考虑的, 段的最优选择一般不同

最优化原理: 最优化原理:最优策略的子策略总是最优的

1、建模 、 (1)划分阶段、确定各阶段的状态变量 )划分阶段、 (2)确定状态转移方程:s k+1 = Tk ( s k , u k ) )确定状态转移方程: s k= Tk ( s k+1 , u k ) (3)指标函数 ) f k ( s k ):第k阶段,从s k出发到终点的最优效益值 阶段, : 阶段 f k ( s k+1 ):从起点到第 阶段 k+1状态的最优效益值 阶段s :从起点到第k阶段

(4)基本递推方程: )基本递推方程: a:逆序法 :

?fk (sk ) = opt{dk (sk , uk ) + fk+1(sk+1 )} ?f (s ) = 0 ? n+1 n+1

顺序法: 顺序法: ?fk (sk+1 ) = opt{dk (sk+1 , uk ) + fk?1(sk )}

?f (s ) = 0 ?0 1

b:逆序法 ?fk (sk ) = opt{dk (sk , uk ) ? fk+1(sk+1)} :

? ? fn+1(sn+1) =1 ? ? f0 (s1) =1

顺序法: 顺序法: ?fk (sk+1) = opt{dk (sk+1, uk ) ? fk?1(sk )}

2、动态规划的求解方法: 、
(1)逆序法 ) (2)顺序法 ) 顺序法、逆序法的适用条件: 顺序法、逆序法的适用条件: (1)初始状态给定,可使用逆序法 )初始状态给定, (2)终止状态给定,可使用顺序法 )终止状态给定, (3)初始、终止状态都已知,均可使用 )初始、终止状态都已知,

作业: 作业: 7.1

连续确定型动态规划的求解
万元, 例:某公司有资金10万元,若投资于项目 (i = 1 , 2 某公司有资金 万元 若投资于项目i( , 3)的投资额为 i 时,其收益分别为 1( x1 )=4 x1 , 其收益分别为g )的投资额为x g 2 ( x 2 ) = 9 x2 , g 3 ( x 3 ) = 2 x32 , 问应如何分配投资 数额才能使总收益最大? 数额才能使总收益最大? max z = 4 x1 + 9 x2 + 2 x32 x1 + x2 + x3 =10 xi ≥0 (i = 1 , 2 , 3) )

max z = 4 x1 + 9 x2 + 2 x32 x1 + x2 + x3 =10 xi ≥0 (i = 1 , 2 , 3) ) 解:建模:用逆序法 建模:

s1
s1=10

x1
k=1

s2

x2
k=2

s3

x3
k=3

s4

s2=10 - x1 = s1 - x1

s3=10 - x1 - x2 s4=10 - x1 - x2 - x3 = s2 - x2 = s3 - x3 0≤x 0≤ 3≤s3

0≤x 0≤ 1≤s1

0≤x 0≤ 2≤s2

f3(s3) = max (2 x32 )

f2(s2) = max [ 9 x2 + f3(s3) ]

f1(s1) = max [ 4 x1 + f2(s2) ]

s1
s1=10

x1
k=1

s2

x2
k=2

s3

x3
k=3

s4

s2=10 - x1 = s1 - x1

s3=10 - x1 - x2 s4=10 - x1 - x2 - x3 = s2 - x2 = s3 - x3

按问题变量个数划分为3个阶段;状态变量为 按问题变量个数划分为 个阶段;状态变量为s1 , s2 , 个阶段 s3 , s4 并记 1=10; x1 , x2 , x3 为决策变量; 并记s 为决策变量; ; 状态转移方程: 状态转移方程:s k+1 = s k – x k fk ( sk ):第k阶段初始状态为 k ,从第k阶段到第 阶 : 阶段初始状态为s 从第 阶段到第3阶 阶段初始状态为 阶段到第 段的最大收益 基本递推方程: ? 基本递推方程: ?fk (sk ) = m {gk (xk ) + fk+1(sk+1)} ax
0≤xk ≤sk ? ?f4 (s4 ) = 0 ?

k=3 x3* =s3 k=2

f3(s3) = max { 2 x32 } f3(s3) = 2 s32 f2(s2) = max { 9 x2 + f3(s3)} = max { 9 x2 + 2 (s2 - x2 )2 }

0≤x 0≤ 3≤s3 0≤x 0≤ 2≤s2 s3=s2 - x2

f2(s2) = max { 9 x2 + 2 s32 } 令h2 ( s2 , x2 ) = 9 x2 + 2 (s2 - x2 )2
dh2 = 9 + 4(s2 ? x2 )(?1) = 0 dx2
d2h2 =4>0 2 dx2

x2 = s2 –9/4

x2 = s2 –9/4 h2 ( s2 , x2 ) 有最小值, 有最小值, 所以最大值在[0, 的两个端点上 所以最大值在 ,s2]的两个端点上

f2 ( s2 ) = 9 s2 f2 ( 0 ) = 2 s22 s2 < 9/2 ① x2* = s2 f2 (s2 ) = 9 s2 > f2 ( 0 ) ② x2* = 0 f2 ( 0 ) = 2 s22 > f2 ( s2 ) s2 > 9/2 k=1 f1(s1) = max { 4 x1 + f2(s2) } 0≤x 0≤ 1≤10 s2 < 9/2 ① x2* = s2 f2 (s2 ) = 9 s2 f1(s1) = max { 4 x1 + 9 s2 } s2=s1 - x1 = max { 4 x1 + 9 ( s1 - x1 )} = max {9 s1 - 5 x1} x1 = 0 f1(s1) = 9 s1 s2=s1 - x1 =10 - 0=10 > 9/2 与 s2 < 9/2矛盾 舍去 矛盾

f2 ( 0 ) = 2 s22 ② x2* = 0 f1(s1) = max { 4 x1 + 2 s22 } = max { 4 x1 + 2 ( s1 - x1 )2 } 令h1 ( s1 , x1 ) = 4 x1 + 2 ( s1 - x1 )2

s2 > 9/2 s2=s1 - x1

dh1 = 4 + 4(s1 ? x1)(?1) = 0 x1 = s1 – 1 dx1 2 x1 = s1 – 1 h1 ( s1 , x1 ) 有最小值,所 有最小值, d h1 =1 > 0 以最大值在 ,s ]的两个端点上 2 以最大值在[0, 1 的两个端点上 dx1

x1 = s1=10 f1(s1) = 4 s1 = 40 x1 = 0 f1(s1) = 2 s12 = 200 s2=s1 - x1 =10 - 0=10 > 9/2 f1(s1) = 2 s12 = 200 ∴ x1* = 0

∴ x1* = 0 x2 * = 0 x3* =s3 =10

s1=10 s2 = s1 - x1 = 10 - 0 =10 s3= s2 - x2 = 10 - 0 = 10

f1(s1) =200 f2(s2) =200 f3(s3) =200

即全部资金投资于第3个项目,最大收益为 即全部资金投资于第 个项目,最大收益为200万元 个项目 万元

顺序法: 顺序法:

max z = 4 x1 + 9 x2 + 2 x32 x1 + x2 + x3 =10 xi ≥0 (i = 1 , 2 , 3) )

s1
= s2 – x1

x1
k=1

s2

x2
k=2

s3

x3
k=3

s4
s4=10

s1=10 - x3 - x2 - x1 s2=10 - x3 - x2 = s3 - x2

s3=10 – x3 = s4 – x3

0≤x 0≤ 3≤s4 0≤x 0≤ 2≤s3 0≤x 0≤ 1≤s2 f1(s2) = max [ 4 x1] f2(s3) = max [ 9 x2 + f1(s2) ] f3(s4) = max [ 2 x32 + f2(s3) ]

s1
= s2 – x1

x1
k=1

s2

x2
k=2

s3

x3
k=3

s4
s4=10

s1=10 - x3 - x2 - x1 s2=10 - x3 - x2 = s3 - x2

s3=10 – x3 = s4 – x3

按问题变量个数划分为3个阶段;状态变量为 按问题变量个数划分为 个阶段;状态变量为s1 , s2 , 个阶段 s3 , s4 并记 s4=10; x1 , x2 , x3 为决策变量; 为决策变量; ; 状态转移方程: 状态转移方程:s k= s k+1 – x k fk ( sk+1 ):第k阶段终止状态为 k+1 ,从第 阶段到第 阶段终止状态为s 从第1阶段到第 : 阶段终止状态为 k阶段的最大收益 阶段的最大收益 基本递推方程: 基本递推方程: ?f (s ) = m {gk (xk ) + fk?1(sk )} ax ? k k+1
0≤xk ≤sk+1 ? ?f0 (s1) = 0 ?

k=1 x1* =s2 k=2

f1(s2) = max { 4 x1 } f1(s2) = 4 s2 f2(s3) = max { 9 x2 + f1(s2)} = max { 9 x2 + 4 (s3 - x2 ) } = max{ 4 s3 + 5 x2 }

0≤x 0≤ 1≤s2 0≤x 0≤ 2≤s3 s2=s3 - x2

f2(s3) = max { 9 x2 + 4 s2 }

x2* =s3 k=3

f2(s3) = 9 s3 0≤x 0≤ 3≤s4 s3=s4 – x3

f3(s4) = max {2 x32 + f2(s3) } = max { 2 x32 + 9 (s4 – x3) }

f3(s4) = max {2 x32 + 9 s3 }

令h ( s4 , x3 ) = 2 x32 + 9 (s4 – x3)
dh = 4x3 ? 9 = 0 dx3 d2h =4>0 2 dx3

x3= 9/4 此点为极小值点

极大值点应在[ 极大值点应在 0 , s4 ] = [ 0 , 10 ] 的端点 x3 = 0 x3*=10 =10 ∴ x3*= s4=10 x2*= s3=0 x1*=s2=0 f3(s4) = 9s4 =90 (s = 2 x =200 ff33(s44)) = 2 x3322 =200 s3=s4 – x3 =0 s2=s3 - x2 =0 s1= s2 – x1 f3(s4) = 200 f2(s3) =0 f1(s2) =0

动态规划的应用举例
资源分配问题: 资源分配问题:
例:有资金4万元,投资A、B、C三个项目,每个项 有资金4万元,投资A 三个项目, 目的投资效益与投入该项目的资金有关。 目的投资效益与投入该项目的资金有关。三个项目 的投资效益(万吨)和投入资金(万元) A、B、C的投资效益(万吨)和投入资金(万元) 的关系见下表。求对三个项目的最优投资分配, 的关系见下表。求对三个项目的最优投资分配,使 总投资效益最大。 总投资效益最大。
项目
投入资金

A 15万吨 万吨 28万吨 万吨 40万吨 万吨 51万吨 万吨

B 13万吨 万吨 29万吨 万吨 43万吨 万吨 55万吨 万吨

C 11万吨 万吨 30万吨 万吨 45万吨 万吨 58万吨 万吨

1万元 万元 2万元 万元 3万元 万元 4万元 万元

1、建模 、
阶段:每投资一个项目作为一个阶段, 阶段:每投资一个项目作为一个阶段,k=1,2,3 , , 状态变量s 投资第k个项目前的资金数 状态变量 k:投资第 个项目前的资金数 决策变量x 个项目的投资; 决策变量 k:第k个项目的投资; 个项目的投资 决策允许集合: 决策允许集合:0≤xk≤sk 状态转移方程: 状态转移方程:sk+1=sk-xk 阶段指标: 阶段指标:vk(sk,xk)见表中所示 见表中所示 递推方程: 递推方程:fk(sk)=max{vk(sk,xk)+fk+1(sk+1)} 边界条件: 边界条件:f4(s4)=0 2、求解 、 k=4 f4(s4)=0

k=3 0 1 0 0 1 0 1 2 0 1 2 3

0≤x3≤s3 0 1 0 2 1 0 3 2 1 0 0 0 11 0 11 30 0 11 30 45

s4=s3 – x3
f3(s3) x3*

s3 D3(s3) s4 v3(s3,x3) v3(s3,x3)+f4(s4)

2

3

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

0 11

0 1

30

2

45

3

s3 D3(s3) s4 v3(s3,x3) v3(s3,x3)+f4(s4)

f3(s3)

x3*

4

0 1 2 3 4

4 3 2 1 0

0 11 30 45 58

0+0 11+0=11 30+0=30 45+0=45 58+0=58 s3=s2 – x2

58

4

k=2

0≤x2≤s2 0 0 1 0 1 0 0 0 13

s2 D2(s2) s3 v2(s2,x2) v2(s2,x2)+f3(s3)

f2(s2)

x2*

0 1

0+0 0+11=11 13+0=13

0 13

0 1

s3 D3(s3) s4 v3(s3,x3) v3(s3,x3)+f4(s4)

f3(s3)

x3*

2

3

4

0 1 2 0 1 2 3 0 1 2 3 4

2 1 0 3 2 1 0 4 3 2 1 0

0 13 29 0 13 29 43 0 13 29 43 55

0+30=30 13+11=24 29+0=29 0+45=45 13+30=43 29+11=40 43+0=43 0+58=58 13+45=58 29+30=59 43+11=54 55+0=55

30

0

45

0

59

2

k=1

0≤x1≤s1 0 1 2 3 4 4 3 2 1 0 0 15 28 40 51

s2=s1 – x1
f3(s3) x3*

s3 D3(s3) s4 v3(s3,x3) v3(s3,x3)+f4(s4)

4

0+59=59 15+45=60 28+30=58 40+13=53 51+0=51

60

1

最优解: 最优解:s1=4, x1*=1,s2=s1-x1=3, x2*=0 , , , s3=s2-x2*=3, x3=3, s4=s3-x3=0 , , 即项目A投资 万元,项目B投资 万元,项目C投资 投资1万元 投资0万元 即项目 投资 万元,项目 投资 万元,项目 投资 3万元,最大效益为 万吨。 万元, 万吨。 万元 最大效益为60万吨


相关文章:
第七章运筹学动态规划_图文.ppt
第七章运筹学动态规划 - 动态规划 引言 □动态规划是解决多阶段决策过程最优化的
运筹学PPT 第七章 动态规划_图文.ppt
运筹学PPT 第七章 动态规划 - 运筹学 运筹帷幄之中决胜 第七章动态规划
运筹学第七章动态规划._图文.ppt
运筹学第七章动态规划. - 第七章 动态规划 Dynamic Programmi
运筹学第七章 动态规划_图文.ppt
运筹学第七章 动态规划 - 第七章 动态规划 第一节 多阶段决策问题 例7.1
第七章 运筹学 动态规划2_图文.ppt
第七章 运筹学 动态规划2 - ? ? ? ? ? ? 教学目的与要求:使学生学会利用多阶段问题 的决策思想处理一些简单的实际问题,并会用 WinQSB求解动态规划. 重点与...
第七章运筹学动态规划_图文.ppt
第七章运筹学动态规划 - 第七章 动态规划 最短路径问题 资源分配问题 生产计划
运筹学第七章_动态规划(见28页)_图文.ppt
运筹学第七章_动态规划(见28页) - 第七章 动态规划 第一节 多阶段决策问
运筹学-第七章-动态规划_图文.ppt
运筹学-第七章-动态规划_数学_自然科学_专业资料。运筹学 第七章 动态规划 D
运筹学课件第七章_动态规划_图文.ppt
运筹学课件第七章_动态规划 - 第七章 动态规划 (Dynamic progra
动态规划--运筹学课程设计.doc
运筹学第七章 动态规划 52页 2财富值 运筹学 动态规划 2 18页 1财富
运筹学--第七章 动态规划.doc
运筹学的重要学习资料运筹学的重要学习资料隐藏>> 第七章 动态规划 : 习题七 7.1 计算如图所示的从 A 到 E 的最短路线及其长度(单位:km) (1) 用逆推解法...
广工管理运筹学第七章 动态规划_图文.ppt
广工管理运筹学第七章 动态规划 - 第七章 动态规划 动态规划简介 多阶段决策过
第七章 动态规划(管理运筹学,李军)_图文.ppt
第七章 动态规划(管理运筹学,李军) - 1.多阶段决策过程 2.Bellman
运筹学T14第7章动态规划_图文.ppt
运筹学T14第7章动态规划 - 第七章 动态规划 本章内容重点 7.1引言 7.
第七章 动态规划_图文.ppt
第七章 动态规划_数学_自然科学_专业资料。运筹学ppt 第七章 动态规划 --
运筹学 动态规划应用.ppt
运筹学 动态规划应用_数学_自然科学_专业资料。第七章 动态规划动态规划问题的基
运筹学5(动态规划)_图文.ppt
运筹学5(动态规划) - 第七章 动态规划 7.1 动态规划问题和基本概念 7.
运筹学第七章_图文.ppt
运筹学第七章 - Yunchouxue 第七章 动态规划 1 以最短路问题为例,
运筹学第七章2007_图文.ppt
运筹学第七章2007 - 运筹学基础 主讲教师: 联系电话: 短号: E-mai
第七章 动态规划_图文.ppt
第七章 动态规划 - 运筹学 -Operation’s Research 北京理工大学珠海学院 吴浩然 第七章 动态规划 1 多阶段决策过程的最优化 2 动态规划的基本概念、求解思...
更多相关文章: