当前位置:首页 >> 经管营销 >>

010运筹学-动态规划


多阶段决策过程的最优化
动态规划(Dynamic Programming, DP),作为运筹学的一个重要分支 是解决多阶段决策过程最优化的一种非常有效的方法。 1951年, R.Bellman 多阶段决策问题

一系列相互联系的

最优性原理

单阶段决策问题

贝尔曼的名著《动态规划》于1957年出 版,这成了动态规划的第一本著作。

多阶段决策过程的最优化
动态规划的方法,在工程技术、企业管理、工农业生产及军事等部 门中有着广泛的应用,并且获得了显著的效果。

最优路径问题 资源分配问题 经济管理方面的应用 生产与库存问题

设备更新问题



多阶段决策过程的最优化
由于动态规划的方法在众多方面的应用,使他已经成为现代企业管 理中的一种重要的决策方法。 此外,许多实际问题采用动态规划方法去处理,常比线性规划 或非线性规划更加有效。 特别对于离散型的问题,由于解析数学无法施展其术,而动态 规划方法就成为一种非常有效的工具。

多阶段决策过程的最优化
动态规划所研究的对象是多阶段决策问题。

多阶段决策问题是指一类活动过程,它可以按照时间或空间分
为若干个相互联系的阶段,称为“时段”,在每个时段都需要 作出决策。全部过程的决策就是一个决策序列。多阶段决策也

称为“序贯决策”。
在每个时段的决策不仅决定这一时段的效益,而且决定下 一时段的初始状态。 ?多阶段决策过程的决策目标是求一个策略使各阶段总体效益达 到最优,而非各单个阶段最优的简单总和。 ?动态规划解决多阶段决策过程问题的基本思想---将一个n阶段的 决策问题转化为依次求解n个具有递推关系的单阶段决策问题

多阶段决策过程的最优化
动态规划典例——最短路线问题
最优性原理:若某一点在最优路径上,那么从那一点到终点的最短路径 也在最优路径上。

12

13 17 4 B1

2 3 6 8

C1 10 C2 8 C3 9 C4 4

5 8 5

7 D1 3 5 6 2

4
E1 4 F

5
D2

A

5

15 B2

7
7

3 4 8
4

5 1 D3

3

3 3 E2

动态规划的基本概念和基本原理
总结:
在最短路线问题中,将一个五阶段的决策问题转化为依次求解五 个单阶段的决策问题, 其中一个重要的特征是将前面得到的最短 路线的解传递并纳入到下一阶段一并考虑,做到了求解的各个阶 段之间具有递推性.

动态规划的基本概念和基本原理
基本概念:阶段(stage)——是指对整个决策过程的自然划 分,通常按照时间或空间特征分解为若干相互联系的阶段, 以便按阶段的次序逐段解决整个决策过程的优化问题 2 3 6 8 7 7
第二阶段

C1 4 C2

5 8 5

D1 6 2 1 D3 3

3 5 E1 4 F 3 E2

4

B1

A

D2
C3 3 4

5
B2

8
C4 4
第三阶段

第一阶段

第四阶段

第五阶段

动态规划的基本概念和基本原理
2. 状态(state)---每个阶段开始时过程所处的自然状态或 客观条件。它即反映前面各阶段决策的结局,有是本阶 段作出决策的出发点和依据。 状态应该具有“无后效性”,即当某阶段状态给定以后, 在这阶段以后过程的发展不受这段以前各状态的影响。 也就是说,当前的状态是过去历史的一个完整总结,过 程的过去历史只能通过当前状态去影响它未来的发展。 描述各阶段状态的变量称为状态变量(state variable), 记为 sk,状态集合记为Sk .

动态规划的基本概念和基本原理
B1

4 A 5

2 3 6 8 7
7

C1 4
C2

5

8
5

D1

3
5

D2 C3 8 C4 4 3 4 D3

6 2
1 3

E1 4
F 3

B2

E2

S1 ? {s1} ? { A}

S2 ? {B1 , B2 }

S3 ? {C1 , C2 , C3 , C4 }
状态变量sk 具有无后效性.

S4 ? {D1 , D2 , D3} S5 ? {E1 , E2 }

动态规划的基本概念和基本原理
3. 决策(decision)——指某阶段初从给定的状态出发,决策 者在面临的若干种不同方案中作出的选择,从而可以确 定下一阶段的状态,这种选择称为决策。 决策变量uk(sk)表示第k阶段状态为sk时对方案的选择。 决策集合Dk(sk)表示第k阶段状态为sk时决策允许的取值范围, 称为允许决策集合。 uk(sk) Dk(sk) ?

动态规划的基本概念和基本原理
B1

4 A 5

2 3 6 8 7
7

C1 4
C2

5

8
5

D1

3
5

D2 C3 8 C4 4 3 4 D3

6 2
1 3

E1 4
F 3

B2

E2

u2 ( B1 ) ? C3 . u3 (C3 ) ? D3 .

D2 ( B1 ) ? {C1 , C2 , C3}; D3 (C3 ) ? {D2 , D3};

动态规划的基本概念和基本原理
4. 策略(policy)——动态规划问题的各阶段决策组成的一 组有序决策序列就构成一个策略。 含有n个阶段的动态规划问题的策略可以写为 p1,n{u1(s1), u2(s2), …, uk(sk), …, un(sn)}

允许策略集合记为P1,n . 使整个问题达到最优效果的策略称 为最优策略。
把从某一阶段开始到过程最终的决策序列称为问题的子过 程策略或子策略, {uk(sk), uk+1(sk+1), …, un(sn)}

动态规划的基本概念和基本原理
B1 2 3 6 8 B2 7 7 C4 C1 4 C2 5

8 5

D1 6 2 1 D3 3

3 5 E1 4

4
A 5

D2 C3
8 4 3 4

F
3

E2

最优策略为u1(A)=B1, u2(B2)=C2, u3(C2)=D2, u4(D2)=E2, u5(E2)=F .

动态规划的基本概念和基本原理
5. 状态转移方程——假设第k阶段的状态为sk, 本阶段做出 的决策uk(sk)确定后, 则第k+1阶段的状态变量的取值也就 随之确定。动态规划中这种从上一阶段的某一状态值到 下一阶段某一状态的转移规律称为状态转移律。 显然,下一阶段状态sk+1的取值是上一阶段状态变量sk和上 一阶段决策变量uk(sk)的函数, 记为 sk+1 = Tk(sk, uk(sk))

状态转移函数

动态规划的基本概念和基本原理
B1

4 A 5

2 3 6 8 7
7

C1 4
C2

5

8
5

D1

3
5

D2 C3 8 C4 4 3 4 D3

6 2
1 3

E1 4
F 3

B2

E2

s3 ? T2 ( s2 , u2 (s2 )) ? T2 ( B2 , C2 ) ? C2 . sk ?1 ? Tk (sk , uk (sk )) ? uk (sk ).

动态规划的基本概念和基本原理
6. 阶段指标函数——衡量在一个阶段某个状态下各决策所对 应的某种数量指标或效果,通常表示为vk(sk,uk)(表示第k阶 段从状态sk 出发,采取决策uk 时的效益)
7. 指标函数——过程指标值 衡量在选定某策略时,其优劣的数量指标。

定义在整个过程(1到n阶段)上的指标函数记为: V1,n(s1,u1,s2,…,sn,un)
定义在后部子 过程(k到n阶段)上的指标函数记为: Vk,n(sk,uk,…,sn,un),或简记为:Vk,n(sk, pk,n )。 常见指标函数的形式: Vk,n(sk, pk,n )= ∑ vi(si ,ui) Vk,n(sk, pk,n )= ∏ vi(si ,ui)

动态规划的基本概念和基本原理
B1 2 3 6 C1 4 C2

5
8

D1

4
A 5

5
3 4 8 4

3 5

8
B2 7 7 C3

6 D2 2 1 D3 3

E1 4 F 3 E2

vk (sk , uk (sk )) ? d (sk , uk (sk )).

C4

v1 ( s1 , u1 ) ? v1 ( A, B2 ) ? 5.

V2,5 ( B1 , p2,5 )表示从B1出发选择策略p2,5到达F的距离。 V2,5 ( B1 , F ) ? V2,5 ( B1,C1 , D1 , E1 , F ) ? 2 ? 5 ? 3 ? 4 ? 14.

动态规划的基本概念和基本原理
8. 最优指标函数——从第k阶段状态为sk出发,采用最优 策略pk,n*,到过程终止时的最佳效益值,记为fk(sk),

fk(sk)=Vk,n(sk, pk,n*) = Opt Vk,n(sk , pk,n) (max / min )
pk,n? Pk,n

f1(s1)=V1,n(s1, p1,n*) = Opt V1,n(s1, p1,n)

表示整个过程的的最佳效益值。

动态规划的基本概念和基本原理
B1 2 3 6 C1 4 C2

5
8

D1

4
A 5

5
3 4 8 4

3 5

8
B2 7 7 C3

6 D2 2 1 D3 3

E1 4 F 3 E2

C4

* f 2 ( B1 ) ? V2,5 ( B1 , p2,5 ) ? min p2,5?P2,5 V2,5 ( B1 , p2,5 )

f 2 ( B1 )表示从B1到F的最短距离. f1 ( A)表示从A到F的最短距离.

动态规划的基本概念和基本原理
上述基本概念在多阶段决策过程中的关系如下图所示:

决策 uk(sk)
状态 sk 阶段 k T(sk, uk) 状态 sk+1

决策 uk+1(sk+1)
阶段k+1

状态 sk+2

T(sk+1,uk+1)

vk(sk , uk)

vk+1(sk +1, uk+1)

动态规划的基本概念和基本原理
动态规划的逆序解法: 2 3 B1 4 6 A 8 5 7 B2 7 C1 C2 C3 4 5 8 D1 D2 3 4

5

3 5 6 2 1 3

E1 4 F

3
E2

8
4

D3

C4 1. 阶段:划分为5个阶段,k=1,2,3,4,5. 2. 选取各阶段的起点为状态变量sk;
3. 以路线的终点作为决策变量uk(sk); 4. 状态转移方程:sk+1=Tk(sk, uk)= uk ;

动态规划的基本概念和基本原理
5. 阶段指标函数:vk(sk, uk)=d(sk, sk+1) 6. 定义第k到第n阶段的最优指标函数fk(sk): fk (sk)=第k阶段初在状态sk时,第k阶段到第n阶段按最 优策略所走的最短距离。

7. 做动态规划的结构图
k阶段 min
?

k+1阶段 vk(sk, uk)=d(sk, sk+1) uk(sk) ? Dk(sk)

sk
fk(sk)

sk+1=uk
fk+1(sk+1)

动态规划的基本概念和基本原理
8. 建立动态规划基本方程 : fk(sk)= min {d(sk, sk+1)+ fk+1(sk+1)} uk(sk) ? Dk(sk) f6(s6)=0, k=5,4,3,2,1

动态规划的基本概念和基本原理
9. 逆序递推解法: 4 A B1 2 3 6 8 7 7 C1 C2 C3 4

5 8
5 3 4

D1

3 5

5 B2

6 D2 2 1 D3 3

E1 4 F E2 3

8
C4 4

第1步: k=5, 状态变量s5可以取状态E1, E2, S5 ? {E1 , E2 }, 由于从E1, E2出发到F只有1条路线, 即为最短路线,
f5 ( E1 ) ? 4, f5 ( E2 ) ? 3.

提问: 第5阶段的最优策略是什么?

动态规划的基本概念和基本原理
4 A 5 B2 B1 2 3 6 8 7 7 C1

C2 C3

4

5 8 5 3 4

D1

3 5

6 D2 2 1 D3 3

E1 4 F E2 3

8

C4 4 第2步: k=4, 状态变量s4可以取状态D1, D2, D3 ,有
S4 ? {D1 , D2 , D3}, 从状态D1, D2, D3出发到F都有两条路线,
? d ( D1 , E1 ) ? f5 ( E1 ) ? ?3 ? 4 ? f 4 ( D1 ) ? min ? ? ? min ? ??7 ?5 ? 3 ? ?d ( D1 , E2 ) ? f 5 ( E2 ) ?
* D1到终点F 最短距离路径D1 ? E1 ? F , u4 ( D1 ) ? E1.

动态规划的基本概念和基本原理
? d ( D2 , E1 ) ? f 5 ( E1 ) ? ?6 ? 4 ? f 4 ( D2 ) ? min ? ? ? min ? ??5 ? 2 ? 3? ?d ( D2 , E2 ) ? f 5 ( E2 ) ?
* D2到终点F 最短距离路径D2 ? E2 ? F , u4 ( D2 ) ? E2 .

? d ( D3 , E1 ) ? f 5 ( E1 ) ? ?1 ? 4 ? f 4 ( D3 ) ? min ? ? ? min ? ??5 ?3 ? 3? ?d ( D3 , E2 ) ? f 5 ( E2 ) ?
* D3到终点F 最短距离路径D3 ? E1 ? F , u4 ( D3 ) ? E1.

提问: 第4阶段的最优策略是什么? (注意:最优策略一定是与该阶段初始状态有密切联系的!)

动态规划的基本概念和基本原理
4 A 5 B1 2 3 6 8 7 7 C1 C2 C3 8 4

5 8
5

D1

B2

3 4

6 D2 2 1 D3 3

3 5

E1 4
F E2

3

C4 4 第3步: k=3,类似的, 有S3 ? {C1 , C2 , C3 , C4 },

? d (C1 , D1 ) ? f 4 ( D1 ) ? ?5 ? 7 ? f3 (C1 ) ? min ? ? ? min ? ? ? 12 ?8 ? 5 ? ?d (C1 , D2 ) ? f 4 ( D2 ) ?
* C1到终点F 最短距离路径C1 ? D1 ? E1 ? F , u3 (C1 ) ? D1.

动态规划的基本概念和基本原理
* f3 (C2 ) ? 10, u3 (C2 ) ? D2 ; * f3 (C3 ) ? 8, u3 (C3 ) ? D2 ; * f3 (C4 ) ? 9, u3 (C4 ) ? D3.

第4步,k ? 2, S2 ? {B1 , B2 }
* f 2 ( B1 ) ? 13, u2 ( B1 ) ? C2 ; * f 2 ( B2 ) ? 15, u2 ( B2 ) ? C3

第5步,k ? 1, S1 ? { A}

? d ( A, B1 ) ? f 2 ( B1 ) ? ?4 ? 13? f1 ( A) ? min ? ? ? min ? ? ? 17 ?5 ? 15 ? ?d ( A1 , B2 ) ? f 2 ( B2 ) ?
A到终点F 最短距离路径:A ? B1 ? C2 ? D2 ? E2 ? F .

动态规划的基本概念和基本原理
B1 2 3 6 8 7 7 C1 C2 C3

4

5 8

D1

4
A 5

5
3 4

3 5

6 D2 2 1 D3 3

E1 4
F 3

B2

E2

8 C4
4

A到终点F 最短距离路径:A ? B1 ? C2 ? D2 ? E2 ? F .

动态规划的基本概念和基本原理
动态规划的基本思想与基本原理:
从最短路线问题中可以看出,从某一状态出发寻求最优选 择时,它是从下述所有可能的组合中进行优化选取的,将 本阶段决策的指标效益值加上从下阶段开始采取最优策略 时的指标效益值。这是一种递推关系式,按照逆序算法可 以从最后一个阶段反推到过程的开始,即第一阶段。

一般的动态规划基本方程可以表示为: ? f k ( sk ) ? opt [vk ( sk , uk ) ? f k ?1 ( sk ?1 )], k ? n, n ? 1,? ,1. ? u k ?Dk ( sk ) ? ? f n ?1 ( sn ?1 ) ? 0. ?

动态规划的基本概念和基本原理
一般动态规划基本方程还有如下形式: ? f k ( sk ) ? opt [vk ( sk , uk ) ? f k ?1 ( sk ?1 )], k ? n, n ? 1, ?,1. ? uk ?Dk ( sk ) ? ? f n ?1 ( sn ?1 ) ? 1. ?
例:当各阶段的指标函数为求积的关系,如复杂系统工作 的可靠性问题,设部件i (i=1,2,…,n)上装有xi个备用元 件,正常工作的概率为pi(xi), 则整个系统正常工作的可 靠性为 P = ? pi(xi)

动态规划的基本概念和基本原理
总结动态规划逆序解法的十步骤: 1. 正确明确的划分阶段, k=1,2,…,n, 依据决策过程的时间 或空间顺序划分。 2. 正确选择并确定状态变量sk及取值范围Sk,
状态变量应该具有——可知性; 能够确切描述过程的演变; 包含到达该状态前的足够信息; 具有无后效性
sk的确定有时不是很明显。要确定它,通常可以对问题做如下分 析:回答两个问题 (1)什么关系将各个阶段联系在一起? (2)为了决定今后的最优(子)策略,需要当前事件现状的 哪些信息?

动态规划的基本概念和基本原理
3. 确定决策变量uk(sk)及Dk(sk) 。
(决策变量——对过程进行控制的手段,可以离散或连续)

4. 写出状态转移方程: sk+1=Tk(sk, uk)。(随机或确定) 5. 定义阶段指标值:vk(uk, sk)

6. 定义第k阶段到第n阶段的最优指标函数fk(sk).
7. 做出动态规划的结构图 k阶段 vk(sk, uk) opt sk uk(sk) ? Dk(sk) ,? ? fk(sk) k+1阶段

sk+1=Tk(sk, uk)
fk+1(sk+1)

动态规划的基本概念和基本原理
8. 建立动态规划的基本方程: fk(sk)= min {vk(sk, uk)+ fk+1(sk+1)} uk(sk) ? Dk(sk) fn+1(sn+1)=0, k=n,n-1,…,1
或者

fk(sk)= min {vk(sk, uk)+ fk+1(sk+1)} uk(sk) ? Dk(sk)
fn(sn)= opt {vn(sn,un)}, k=n-1,n-2,…,1 un(sn)? Dn(sn) 当最优指标函数为求和形式,边界条件常定义fn+1(sn+1)= 0; 当最优指标函数为求积形式,边界条件常定义fn+1(sn+1)=1.

动态规划的基本概念和基本原理
9. 逆序递推求解动态规划的基本方程,求出最优决策序列 un*, un-1*, …, u2*, u1*

10. 顺序确定最优策略:p1,n*={u1*, u2*, …,un-1*, un* }
s1 s2=T2(s1,u1*) …...

sn=Tn(sn-1,un-1*)

u1*(s1)

u2*(s2)

un*(sn)

动态规划在经济管理中的应用
资源分配问题 背包问题 生产与存贮问题 采购与销售问题

设备更新问题
复合系统工作可靠性问题 货郎担问题

动态规划在经济管理中的应用
例—资源分配问题
资源分配问题是动态规划典型应用之一。它的一般提法是:

有某种资源,总量为a, 用于n个项目,若分配数量ui于第i个 项目, 则第i个项目所产生的效果为gi(ui), 问题是如何分配资 源总量a才能获得n个项目所产生的总效果最优?
静态规划模型为 max z= g1(u1)+g2(u2)+…+gn(un) s.t. u1+u2+…+un≤a u i≥ 0

动态规划在经济管理中的应用
例:某公司根据计划安排,拟将某种高效率的设备5台分 配给所属的甲、乙、丙三个分厂,各分厂若获得这种设备 后可以为公司提供的盈利如下表所示。问这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

动态规划在经济管理中的应用
解:分析、建立动态模型(5分) 根据多阶段决策问题的特征,将此问题转化为三个阶段的 决策问题 1. 阶段k = 1,2,3分别代表甲,乙,丙三个分厂。 2. 状态变量sk:表示给第k个分厂分配设备时还可以分配 的设备数量。 3. 决策变量uk:表示第k个分厂分配的设备数量。允许决 策集合为Dk = { uk|0≤uk≤sk 且为整数}

4. 状态转移方程:sk+1 = sk - uk 。
5. 阶段指标值:利润如表Vk(sk ,uk)。 6. 最优指标函数 fk(sk).

动态规划在经济管理中的应用
或者

fk(sk)= Max ? V(sk ,uk)+ f(sk+1)? k = 3, 2,1, 0 ? uk ? sk 且为整数
f (s4) = 0 或者 fk(sk)= Max ? V(sk ,uk)+ f(sk+1)? k = 2,1, 0 ? uk ? sk 且为整数

f (s3) = Max ? V(s3 ,u3)? 0 ? u3 ? s3且为整数

动态规划在经济管理中的应用
8. 逆序递推求解动态方程: (求解过程(10分)) 第1步: k=3, 状态变量s3 的取值范围为0,1,2,3,4,5 且决 策 变量 0 ≤u3 ≤s3 , u3 = 0, 1, 2, 3, 4, 5有递推方程为 u3 0 1 2 3 4 5 f3 ( 03? u3 max { V3(s3, u3) + 0 }, s ) = ? s3且为整数 V3(s3, u3) 0 1 2 3 4 5 0 0 0 0 0 0 4 4 4 4 4 6 6 6 6 11 11 11

s3

f3(s3)
0 4 6 11

u3* 0 1

12 12

12

12 12

2 3 4 5

动态规划在经济管理中的应用
第2步: k=2, 状态变量s2 的取值范围为0,1,2,3,4, 5 且决策 变量 0 ≤ u2 ≤ s2 , u2 = 0, 1, 2, 3, 4, 5,有递推方程为

f2 ( s2 ) = max { V2(s2, u2) + f3 ( s3 ) }, 0 ? u2 ? s2且为整数
s2 u2 0 1 2

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

V2(s2, u2) + f3 ( s2 - u2 ) 1 2 3 4 5+0

5

f2(s2)
0 5 10 14 16

u2* 0 1 2 2 1, 2

3 4 5

0+12

5+4 10+0 5+6 10+4 11+0 5+11 10+6 11+4 11+0 5+12 10+11 11+6 11+4 11+0

21

2

动态规划在经济管理中的应用
第3步: k=1, 状态变量s1 等于5, 决策变量 0 ≤ u1 ≤ 5 , u1 = 0, 1, 2, 3, 4, 5,有递推方程为

f1 ( s1 ) = max { V1(s1, u1) + f2(s2) }, 0 ? u1 ? 5且为整数
s1

u1
5

V1(s1, u1) + f2 ( s1 – u1 ) 0 1 2 3 4 5 0+21 3+16 7+14 9+10 12+5 13+0

f1(s1) 21

u1* 0, 2

动态规划在经济管理中的应用
9. 按顺序递推可以确定该公司的最优设备分配方案如下: 决策方案(5分) (1)分配0台设备给分厂甲, 分配2台设备给分厂乙, 分配3台 设备给分厂丙;

(2) 分配2台设备给分厂甲, 分配2台设备给分厂乙,分配1 台设备给分厂丙。
此时该公司可以获得最大盈利为21(万元)。

动态规划在经济管理中的应用
例:(离散确定型的动态规划问题) 某一警卫部门共有12支巡逻队,负责4个要害部位A,B,C, D的警卫巡逻。对每个部位可以分别派出2-4支巡逻队, 并且由于派出的巡逻队数的不同,各部位预期在一段时期 内可能造成的损失有差别,具体数字见下表。问该警卫部 门应往各部位多少支巡逻队使总的预期损失最小?
部位 A 18 14 10 B 38 35 31 C 24 22 21 D 34 31 25

巡逻队数
2 3 4

动态规划在经济管理中的应用
逆序算法的求解过程:
1. 阶段:把12支巡逻队往A,B,C,D这4个部位派遣看成依次分 四个阶段,k=1, 2, 3,4.于是,转换为一个四阶段决策问题。 2. 状态变量sk=第k阶段初拥有的可派遣的巡逻队数,它不 仅是前面阶段决策的结果,也是本阶段决策的依据。 3. 决策变量uk 即对各部位派出的巡逻队数。

决策集合为Dk(sk)={uk|2≤ uk≤ 4}, k=1,2,3,4. 状态变量集合 Sk : 已知 s1=12, 2≤u1≤4,
由s2=s1-u1 可知,8≤ s2 ≤10, S2={8, 9, 10}; 同理,4≤s3≤8, S3={4, 5, 6, 7, 8};

2≤s4≤6,S4={2, 3, 4, 5, 6}

动态规划在经济管理中的应用
4. 状态转移方程:由于每阶段初拥有的可派遣的巡逻队数 等于上阶段拥有的数量减去上阶段派出的数,故有
状态转移方程: sk+1= Tk(sk,uk)=sk- uk .

5. 阶段指标函数: 用pk(sk,uk)表示第k阶段派出的巡逻队数 为uk时,该阶段的部位的预期损失值. 6. 定义fk(sk): 表示第k阶段状态为sk时, 第k阶段至过程最终结 束时的预期损失值, fk(sk)=opt Vk,n(sk,uk)=opt ? pk(sk,uk) = pk(sk,uk)+fk+1(sk+1)

动态规划在经济管理中的应用
7. 列出动态规划结构图: k阶段 min k+1阶段 pk(sk, uk) 2≤uk≤4

?

sk
fk(sk)

sk+1=sk-uk
fk+1(sk+1)

8. 列出最优指标函数的递推关系及边界条件: fk(sk)=min { pk(sk, uk)+ fk+1(sk+1)}, 2 ? uk ? 4 f5(s5)=0 . k=4,3,2,1,

动态规划在经济管理中的应用
9. 逆序递推解法: 第1步:k=4, 状态变量s4集合为={2,3,4,5,6}, 2≤u4≤4 , f4(s4)=min { p4(s4,u4)+f5(s5)} 2 ? u4 ? 4 s4 u4 2 3 2 34 34 34 34 34 p4(u4) 3
——

4
—— ——

f4(s4)
34 31 25 25 25

u4*
2 3 4 4 4

31 31 31 31

4
5 6

25 25 25

动态规划在经济管理中的应用
第2步:k=3, 状态变量s3的集合为{4,5,6,7,8}, 2≤u3≤4 , f3(s3)=min { p3(s3,u3)+f4(s4)} 2 ? u3 ? 4 s3

u3
4

5
6 7 8 s4

p3(u3)+f4(s3 - u3) 2 3 4 —— 24+34 —— 24+31 22+34 —— 24+25 22+31 24+25 22+25 24+25 22+25 2 3 4 34 31 25 21+34 21+31 21+25 5 25 6 25

f3(s3) 58

u3* 2

55
49 47

2
2 3

46

4

f4(s4)

动态规划在经济管理中的应用
第3步:k=2, 状态变量s2的集合为{8,9,10}, 2≤u2≤4 , f2(s2)=min { p2(s2,u2)+f3(s3)} 2 ? u2 ? 4 s2 u2 8 9 10 s3 f3(s3) p2(u2)+f3(s2 – u2) 2 3 4 35+55 31+58 38+49 35+49 31+55 38+47 38+46 4 58 35+47 31+49

f2(s2)
87 84 80

u2 * 2 3 4

5 55

6 49

7 47

8 46

动态规划在经济管理中的应用
第4步:k=1, 状态变量s1为12, 2≤u1≤4 , 有 f1(s1)=min { p1(s1,u1)+f2(s2)} 2 ? u1 ? 4 s1 u1 12 s2 f2(s2) p1(u1)+f2(s1 – u1) 2 3 4 14+84 10+87 18+80 8 87 9 10

f1(s1)
97

u1 * 4

84

80

动态规划在经济管理中的应用
10. 确定最优策略: s1=12 s 2= 8 s3=6 s4=2

u ?4
* 1

u ?2
* 2

u ?4
* 3

* u4 ? 2

动态规划在经济管理中的应用
投资分配问题
某公司有资金10万元,若投资于项目i(i=1,2,3)的投资额为ui时, 其收益分别g1(u1)=4u1 , g2(u2)=9u2 , g3(u3)=2u32, 问应该如何 分配投资数额才能使总收益最大? 解: 从表面上看, 这是一个与时间无明显关系的问题, 其静态规划模型为 2 max F ? 4u1 ? 9u2 ? 2u3
?u1 ? u2 ? u3 ? 10 s.t. ? ?ui ? 0, i ? 1, 2,3

可以采用非线性规划算法求解.但是当决策变量ui为非连 续的离散变量时, 非线性规划算法就无能为力了!

动态规划在经济管理中的应用
动态规划的逆序算法的求解过程: (十步骤) 1. 阶段:k=1, 2, 3, 分别表示对项目1投资(k=1), 对项目2 投资(k=2), 及对项目3投资(k=3),即把问题划分为3个 阶段,每个阶段只决定对一个项目的投资金额.

2. 状态变量sk=第k阶段初拥有的可以投资于第k项到第3个 项目的投资金额总量. s1=10.
3. 决策变量uk 即为原静态问题的决策变量uk ,表示第k阶 段分配到第k个项目的资金数量. 决策集合Dk(sk)={uk|0 ≤ uk≤ sk}

动态规划在经济管理中的应用
4. 状态转移方程: sk+1= sk- uk . 5. 阶段指标函数: vk (sk , uk)=gk(uk)

6. 定义fk(sk): 表示第k阶段初拥有的资金总额为sk时, 第k阶段
至第3阶段按照最优投资策略所获得的第k至第3段的总收益. 7. 给出动态规划结构图: k阶段 max k+1阶段 vk(sk, uk)=gk(uk) 0≤uk≤sk

?

sk
fk(sk)

sk+1=sk-uk
fk+1(sk+1)

动态规划在经济管理中的应用
8. 列出逆序递推方程:
? f k ( sk ) ? max {g k (uk ) ? f k ?1 ( sk ?1 )}, k ? 3, 2,1, ? 0?uk ? sk ? ? f 4 ( s4 ) ? 0. ?

9. 逆序递推求解:
第1步:当k ? 3, 由递推方程可得,f3 ( s3 ) ? max {g3 (u3 ) ? f 4 ( s4 )} ? max 2u32
0 ?u3 ? s3 0 ?u3 ? s3

* 2 易知,u3 ? s3时达到最大值,有f3 ( s3 ) ? 2s3 , u3* ? s3 .

注意:这里的s3一定是一个具体数字,尽管目前并不知道, 但是它是会知道的,当u1, u2知道后就可以确定了!

动态规划在经济管理中的应用
第2步:当k ? 2,由递推方程可得 f 2 ( s2 ) ? max {g2 (u2 ) ? f3 ( s3 )} ? max {9u2 ? 2( s2 ? u2 ) 2}
0?u2 ? s2 0?u2 ? s2

可以证明,极大值点只能在端点处达到.
2 当u2 ? 0时,f 2 ( s2 ) ? 2 s2 ; 当u2 ? s2时,f 2 ( s2 ) ? 9 s2 .

9 2 令2 s2 ? 9 s2解得s2 ? ; 2 9 9 ? 2 ? s2 ? 2 , 2 s2 ? 9 s2 ? 2 s2 ( s2 ? 2 ) ? 0, ? * 2 最优决策为u2 ? 0, f 2 ( s2 ) ? 2 s2 ? ? ? s ? 9 , 2 s 2 ? 9 s ? 2 s ( s ? 9 ) ? 0, 2 2 2 2 ? 2 2 2 ? * 最优决策为u2 ? s2 , f 2 ( s2 ) ? 9s2 . ?

动态规划在经济管理中的应用
第3步:当k ? 1, s1 ? 10, 由递推方程可得, f1 (10) ? max{g1 (u1 ) ? f 2 ( s2 )} ? max{4u1 ? f 2 (10 ? u1 )}
0?u1 ?10 0?u1 ?10

当s2 ? 9 / 2时, f1 (10) ? max {4u1 ? 9(10 ? u1 )} ? max {90 ? 5u1} ? 90,
0?u1 ?10 0?u1 ?10

u1* ? 0,此时有s2 ? 10 ? 9 / 2, 矛盾。
当s2 ? 9 / 2时, f1 (10) ? max {4u1 ? 2(10 ? u1 ) 2 },
0 ? u1 ?10

端点值u1 ? 0, f1 (10) ? 200; 端点值u1 ? 10, f1 (10) ? 40,
* 于是, 有u1 ? 0,

动态规划在经济管理中的应用
10. 确定最优策略: s1=10

s2=10>9/2

s3=10

s4=0

u ?0
* 1

u ?0
* 2

* u3 ? s3 ? 10

动态规划在经济管理中的应用
二、背包问题 设有n种物品,每一种物品数量无限。第i种物品每件

重量为wi公斤,每件价值ci元。现有一只可装载重量为W
公斤的背包,求各种物品应各取多少件放入背包,使背 包中物品的价值最高。

这个问题可以用整数规划模型来描述。设xi为第i种
物品装入背包的件数(i =1, 2, …, n),背包中物品的总 价值为z,则 Max z = c1x1+c2x2+ … +cnxn s.t. w1x1+w2x2+…+wnxn≤W x1, x2, …, xn?0 且为整数。

动态规划在经济管理中的应用
下面用动态规划逆序解法求解它。
设 阶段变量k:第k次装载第k种物品(k=1, 2, …, n) 状态变量sk:第k次装载时背包还可以装载的重量; 决策变量uk = xk:第k次装载第k种物品的件数; 决策允许集合:Dk(sk) = { xk | 0? xk?sk/wk,xk为整数}; 状态转移方程: sk+1 = sk? wkxk; 阶段指标: vk = ckxk; 最优过程指标函数fk(sk):第k到n阶段容许装入物品的最大使用价值; 递推方程: fk(sk) = max {ckxk+fk+1(sk+1)} = max {ckxk+fk+1(sk? wkxk)}; x?Dk(sk) 终端条件: fn+1(sn+1) = 0。

动态规划在经济管理中的应用
例3. 某咨询公司有10个工作日可以去处理四种类型的咨 询项目,每种类型的咨询项目中待处理的客户数量、处理每个 客户所需工作日数以及所获得的利润如表10-9所示。显然该公 司在10天内不能处理完所有的客户,它可以自己挑选一些客 户,其余的请其他咨询公司去做,应如何选择客户使得在这10 个工作日中获利最大? 表10-9
咨询项目类 型
1 2 3 4

待处理客户 数
4 3 2 2

处理每个客户 所需工作日数
1 3 4 7

处理每个 客户所获 利润
2 8 11 20

动态规划在经济管理中的应用
解: 我们把此问题分成四个阶段, 第一阶段我们决策将处理多少个第一种咨询项目类型中的客户, 第二阶段决策将处理多少个第二种咨询项目类型中的客户, 第三阶段、第四阶段我们也将作出类似的决策。 我们设 s k =分配给第k种咨询项目到第四种咨询项目的所有客户的总工作 日(第k阶段的状态变量)。 xk=在第k种咨询项目中处理客户的数量(第k阶段的决策变量)。 已知 s1=10, 有 s2

? T1 (s1 , x1 ) ? s1 ? x1 ,

s3 ? T2 ( s2 , x2 ) ? s2 ? 3x2 , s4 ? T3 ( s3 , x3 ) ? s3 ? 4 x3 . 从s k 与 xk的定义可知 s4 ? 7x4
递推方程为

动态规划在经济管理中的应用
动态规划的逆序递推解法: (1) k=4, 状态变量 s4=0,1,…,10.
决策变量uk=xk=0, … , ? s4 / 7 ? 因为 4至多为10,其数值计算见表 r4 ( s4 , x4 ) x4 * f (s )

s

s4

0

1

4

4

x

4

0 1 2 3 4 5 6 7 8 9 10

0 0 0 0 0 0 0
0 0 0 0

- - - - - - -

0 0 0 0 0 0 0 20 20 20 1

0 0 0 0 0 0 0 1 1 1 1

20 20 20 20

动态规划在经济管理中的应用
第三阶段: 当把 s3 ( s3 ? 0,1,2,3,?,10) 个工作日分配给第四类和第

三类咨询项目时,则对每个 s3 值,都有一种最优分配方
案,使其最大盈利即最优3子过程最优指标函数值为
f 3 ( s3 ) ? max ? r2 ( s3 , x3 ) ? f 4 ( s4 ) ?.

s4 ? s3 ? 3x3

x3

因为 f 3 ( s3 ) ? max ?r3 ( s3 , x3 ) ? f 4 ( s3 ? 4 x3 )?. x 因为 s3 至多为10,所以 x3的取值可为0,1,2。其数值计算
3

见表10-11。

动态规划在经济管理中的应用
表10-11

s3
0

x3

r3 ( s3 , x3 ) ? f 4 ( s3 ? 4 x3 )
0 1 - 2 -

f 3 ( s3 )
0

x *3
0

0?0
1
2 3 4

0?0 0?0 0?0
0+0


- -
11 ? 0


- - -

0
0 0 11

0
0 0 1

5
6 7 8 9 10

0+0
0+0

11 ? 0 11 ? 0


- -

11
11 20 22 22 22

1
1 0 2 2 2

0 ? 20
0+20 0+20 0+20

11+0 11+0 11+0 11+0

22 ? 0 22 ? 0 22 ? 0

动态规划在经济管理中的应用
第二阶段: 同样以每个 s 2 值都有一种最优分配方案,使其最大盈利即 最优2子过程最优指标函数值为:
f 2 ( s2 ) ? max ?r2 ( s2 , x2 ) ? f 3 ( s2 ? 3 x2 )?.
x2

因为s3 ? s2 ? 3x2,故有 f 2 ( s2 ) ? max ?r2 ( s2 , x2 ) ? f 3 ( s2 ? 3x2 )?. x 因为 s 2至多为10,所以 x2 的取值为0,1,2,3。其数值计算
2

见表10-12。

动态规划在经济管理中的应用
表10-12

动态规划在经济管理中的应用
第一阶段: 我们已知 s1 ,同样有 ? 10 ,又因为 s2 ? s1 ? x1
x1

f1 ( s1 ) ? max ?r1 ( s1 , x1 ) ? f 2 ( s1 ? x1 )?.
x1

f1 (10 ) ? max ?r1 (10, x1 ) ? f 2 (10 ? x1 )?.
因为s1 ? 10 ,故 x1可取值为0,1,2, … ,10。其数值计算 见表10-13。 表10-13

动态规划在经济管理中的应用
* * 从表10-13可知 f1 (10) ? 28 ,x 1 ? 0 从而得 s2 ? 10 ? x 1 =10

-0=10,在表10-12的 s2 ? 10的这一行可知 x*2 ? 1 ,由 s3 ? s2 ? 3x*2 ? 10 ? 3 ? 7,查表10-11的 s3 ? 7 的这一行可知 x*3 ? 0 ,最后由 s4 ? s3 ? x*3 ? 7 ? 0 ? 7,查表10-10的 s4 ? 7 的这 一行得 x*4 ? 1 ,综上所述得最优解为: *1 ? 0, x*2 ? 1, x*3 ? 0 x x*4 ? 1, 此时最大盈利为28。 现在我们不妨假设该咨询公司的工作计划有所改变,只有 8个工作日来处理这四类咨询项目,那么该咨询公司如何选择 客户使得获利最大呢?我们不必从头开始重做这个问题,而只 要在第一阶段上把s 4 改成8,重新计算就可得到结果,如表10- 14所示,这是动态规划的一个好处。

动态规划在经济管理中的应用
表10-14

如上一样可从表10-14,10-12,10-11,10-10得到两组最优解 ? x *1 ? 1 如下: ? x1 ? 2 ? * ?x ? 4 ? 2 ?x 2 ? 0 ?)? ?? ) ? * ? x3 ? 0 ?x 3 ? 0 ? x4 ? 3 ? x*4 ? 1 ? ? 它们的最优解(即最大盈利)都为22。 一旦咨询的工作日不是减少而是增加,那么我们不仅要重新计 算第一阶段,而且要在第二、第三、第四阶段的计算表上补上增加 的工作日的新的信息,也可得到新的结果。

动态规划在经济管理中的应用
例—生产与存贮问题
某工厂生产并销售某种产品,已知今后四个月市场需求预 测如下表示,每月生产单位产品费用为C( j )=3+j ( j >0 ), 每月库存j单位产品的费用为E( j )=0.5 j (千元), 该厂最大库 存量为3单位,每月最大生产能力为6单位,计划开始和计 划期末库存量都为零,试指定四个月的生产计划,在满足 用户需求条件下总费用最小。 i月 gi需求 1 2 2 3 3 2 4 4

动态规划在经济管理中的应用
1. 阶段k: k=1,2,3,4, k 表示月份 2. 状态变量sk=第k月份初(k-1月份末)的库存量, 已知 s1=s5=0. 3. 决策变量uk=第k月份生产量 根据条件, 有0≤uk≤6, 0≤sk≤3,

4。状态转移方程: sk+1=sk+uk-dk
由上式可知,uk=dk-sk+sk+1 , 以下需要确定决策集合Dk(sk):

动态规划在经济管理中的应用
由上式可知,uk=dk-sk+sk+1 , 以下需要确定决策集合Dk(sk): s4=0,1,2,3, s3=0,1,2,3, u4=d4-s4+s5=d4-s4=4-s4; u3=d3-s3+s4=2-s3+s4 , u3=d3-s3+d4-u4=6-s3-u4, 2-s3≤u3≤5-s3 u3≤6-s3

max{0, 2-s3}≤ u3≤min{6, 5-s3, 6-s3}

s2=0,1,2,3,

u2=d2-s2+s3 =3-s2+s3,

3-s2≤u2≤6-s2
u2≤9-s2

u2=d2-s2+s3=d2-s2+(d3-u3+s4) =d2+d3-s2-u3+(d4-u4)=d2+d3+d4-(u3+u4)-s2, max{0,3-s2}≤u2≤min{6,6-s2,9-s2}

动态规划在经济管理中的应用
5. 阶段指标函数
?0, 当u k ? 0, vk ( sk , u k ) ? u k ? 3? (u k ) ? 0.5sk , 其中? (u k ) ? ? ?1,当u k ? 0,

6. 定义fk(sk)=第k月初库存为sk件产品时,从第k月初至第4月 末的生产总成本最低的费用 7. 动态规划状态转移结构图 k阶段 min k+1阶段

vk ( sk , uk ) ? uk ? 3? (uk ) ? 0.5sk

?

sk
fk(sk)

uk(sk) ?Dk(sk)

sk+1=sk+uk-dk
fk+1(sk+1)

动态规划在经济管理中的应用
8. 列出最优指标函数的递推关系及边界条件:
fk(sk)=min {uk+ 3? (uk)+0.5sk+ fk+1(s k+1)},
uk ? Dk ( sk )

k=4,3,2,1

f5(s5)=0 , 9. 逆序递推求解:

第1步, k=4, s4的取值为0,1,2,3, 又有u4= 4-s4, f4(s4)=min {u4+ 3 ? (u4)+0.5s4+ f5(s5)},
u4

s4 u4 f4(s4) u4*(s4)

0 4 7 4

1 3 6.5 3

2 2 6 2

3 1 5.5 1

4 0 5 0

动态规划在经济管理中的应用
第2步, k=3, s3的取值为0,1,2,3, u3 的取值范围为 max{0, 2-s3}≤ u3≤min{6, 5-s3, 6-s3}的整数, f3(s3)=min {u3+ 3 ? (u3)+0.5s3+ f4(s4)}, s3 u3 0 0 1 2 3 s4 f4 (s4) u3+ 3? (u3)+0.5s3+ f4(s3+u3-d3)}, f3(s3) u3* 1 2 3 4 5 5+7 6+6.5 7+6 8+5.5 12 2 11.5 1 4.5+7 5.5+6.5 6.5+6 7.5+5.5 8 0
u3

1+7 5+6.5 6+6 7.5+5.5 1.5+7 5.5+6.5 6.5+6 0 1 2 3 4 7 6.5 6 5.5 5

8

0

动态规划在经济管理中的应用
第3步, k=2, s2的取值为0,1,2,3, u2 的取值范围为max{0, 3-s3}≤ u3≤min{6, 6-s3, 9-s3}的整数, f2(s2)=min {u2+ 3 ? (u2)+0.5s2+ f3(s3)},
u2 s2 0 1 2 0

u2 u2+ 3? (u2)+0.5s2+ f3(s2+u2-d2)}, 1 2 3 4 5

6

f2(s2) 16 15.5 15

u2 *
5 4 3

6+12

7+11.5

8+8
8.5+8

9+8

6.5+12 6.5+11.5 7.5+8 5+12 6+11.5 7+8 8+8

3 1.5+12 5.5+11.5 6.5+8 s3 f3(s3) 0 12 1 11.5 2 8

7.5+8
3 8

13.5

0

动态规划在经济管理中的应用
第4步, k=1, s1的取值为0, u1 的取值范围为2≤ u1≤5的整数, f1(s1)=min {u1+ 3 ? (u1)+0.5s1+ f2(s2)},
u1
u1
s1 u1+ 3? (u1)+0.5s1+ f2(s1+u1-d1)} 2 3 4 5 5+16 0 16 6+15.5 1 15.5 2 15 7+15 3 13.5 8+13.5

f1(s1)
21

u1 * 2

0
s2 f2(s2)

动态规划在经济管理中的应用
10. 最优策略.

s1=0 u1*=2

s2=0 u2*=5

s3=2 u3*=0

s4=2

s5=0

u4*=2

动态规划在经济管理中的应用
例3——生产与存储问题 某厂经过调查知在未来四个月中每月市场对该厂产品的需求量 如表,该厂每批产品的生产准备费(固定成本)为 3 千元,若不生 产则为零。每件产品的生产成本(可变成本)为 1千元。该厂最大 生产能力为每批不超过 6 件,每件产品每月的库存费用为 0.5 千元, 第一月初该厂没有此产品的库存,并要求第四月末也无库存剩余。 该厂每月初应如何计划产品的生产量及库存量,才能既满足市场对 该厂产品的需求又使其总费用最低。 产品需求表 k(月) 1月 2月 3月 4月

dk(需求量)件

2

3

2

4
83

动态规划在经济管理中的应用
建立动态规划模型: 1. 阶段 k :第 k月,k = 1,2,3,4
2. 3.

状态变量 sk :第 k月初(k-1月末)的库存量,已知 s1 = s5 = 0。 决策变量 uk :第 k月的生产量。 根据条件有: 0 ≤ uk ≤ 6 , min(sk+1) ≤ sk+1 ≤ max( sk+1 ) 状态转移方程: sk+1 = sk + uk - dk 因此,决策集合
Dk(sk)= { uk | 0 ≤ uk ≤ 6, min(sk+1)≤ sk+1 ≤ max( sk+1 )}
= { uk | max [ 0,dk - sk + min(sk+1)] ≤ uk ≤ min [ 6,dk - sk + max(sk+1)] }

4.

84

动态规划在经济管理中的应用
阶段指标值(函数): vk(sk,uk)= uk + 3 ?( uk ) + 0.5sk ,
5.

其中 ?( uk ) =

0
1

当 uk = 0
当 uk > 0

6. 定义 fk(sk):第 k月初库存量为 sk 时,第 k月至第 四月末的

最低总费用。
7. 作出动态规划结构图:

k 阶段

k+1阶段 uk + 3 ?( uk ) + 0.5sk uk ? Dk(sk)

min

sk

sk+1 = sk + uk - dk
fk+1(sk+1)

( ? ) fk(sk)

85

动态规划在经济管理中的应用
8.

动态方程:(逆序递推方程)
uk ? Dk(sk)

fk(sk)=

min { uk + 3 ?( uk ) + 0.5sk + fk+1(sk+1)},k= 4,3,2,1

f5(s5)= f5( 0 )= 0

因为第 5月计划期已结束,没有费用产生了。

9. 逆序递推求解动态规划方程。

k = 4, s4 取值集合为 0,1,2,3,4。 因 min s5 = max s5 = 0
D4(s4)= { u4 | max [ 0, d4 - s4 ] ≤ u4 ≤ min [ 6, d4 - s4 ] } = {u4 | u4 = d4 - s4 = 4 - s4 }

f4(s4)=

min { u4 + 3 ?( u4 ) + 0.5s4 + 0 }

86

动态规划在经济管理中的应用
min { u4 + 3 ?( u4 ) + 0.5s4 + 0 } 0 4 7 4 1 3 6.5 3 2 2 6 2 3 1 5.5 1 4 0 2 0

f4(s4)=
s4

u4 f4(s4) u*4

87

动态规划在经济管理中的应用
k = 3, s3 取值集合为 0,1,2,3,4,5,6。
min s4 = 0,max s4 = 4 D3(s3)= { u3 | max [ 0, d3 - s3 + min(s4)] ≤ u3 ≤ min [ 6,d3 – s3 + max (s4 )] }

= { u3 | max [ 0,2 - s3 ] ≤ u3 ≤ min [ 6,6 - s3 ] }

f3(s3)=

min { u3 + 3 ?( u3 ) + 0.5s3 + f4(s4 = s3 + u3 - d3 )}

88

动态规划在经济管理中的应用
f3(s3)=
u3 s3
0 1
4.5+7

min { u3 + 3 ?( u3 ) + 0.5s3 + f4(s4 = s3 + u3 - d3 )}
[ u3 + 3 ?( u3 ) + 0.5s3 ] + f4(s4 ) f3(s3) u* 3
11 10.5 6 5

0

1

2
5+7 5.5+6.5

3
6+6.5 6.5+6

4
7+6 7.5+5.5

5
8+5.5 8.5+2

6
9+2

2
3 4 5 6

1+7
1.5+6.5 2+6 2.5+5.5 3+2

5+6.5
5.5+6 6+5.5 6.5+2

6+6
6.5+5.5 7+2

7+5.5
7.5+2

8+2

8
8 8 8 5

0
0 0 0 0

s4 f4(s4)

0 7

1 6.5

2 6

3 5.5

4 2
89

动态规划在经济管理中的应用
k = 2, s2 取值集合为 0,1,2,3,4。
min s3 = 0,max s3 = 6 D2(s2)= { u2 | max [ 0, d2 – s2 + min(s3)] ≤ u2 ≤ min [ 6,d2 – s2 + max (s3)] } = { u2 | max [ 0,3 – s2 ] ≤ u2 ≤ min [ 6,9 – s2 ] }

f2(s2)=

min { u2 + 3 ?( u2 ) + 0.5s2 + f3(s3 = s2 + u2 – d2 )}

90

动态规划在经济管理中的应用
f2(s2)=
u2 s2
0 1 2 3
1.5+11 5+11 5.5+10.5 5.5+11 6+10.5 6.5+8

min { u2 + 3 ?( u2 ) + 0.5s2 + f3(s3 = s2 + u2 – d2 )}
[ u2 + 3 ?( u2 ) + 0.5s2 ] + f3(s3 )
1 2 3
6+11 6.5+10.5 7+8 7.5+8

0

4
7+10.5 7.5+8 8+8 8.5+8

5
8+8 8.5+8 9+8 9.5+8

6
9+8 9.5+8 10+8 10.5+5

f2(s2)
16 15.5 15 12.5

u*2
5 4 3 0

4

2+10.5

6+8

7+8

8+8

9+8

10+5

12.5
5 8 6 5

0

s3 f3(s3)

0 11

1 10.5

2 8

3 8

4 8

91

动态规划在经济管理中的应用
k = 1, s1 取值集合为 0 。
min s2 = 0,max s2 = 4 D1(s1)= { u1 | max [ 0, d1 – s1 + min(s2)] ≤ u1 ≤ min [ 6, d1 – s1 + max (s2 )] } = { u1 | max [ 0,2 – s1 ] ≤ u1 ≤ min [ 6,6 – s1 ] } = { u 1 | 2 ≤ u1 ≤ 6 }

f1(s1)=

min { u1 + 3 ?( u1 ) + 0.5s1 + f2(s2 = s1 + u1 – d1 )}

92

动态规划在经济管理中的应用
f1(s1)=
s2
f2(s2)

min { u1 + 3 ?( u1 ) + 0.5s1 + f2(s2 = s1 + u1 – d1 )}
0 16 1 15.5 2 15 3 12.5 4 12.5

u1 s1 2

[ u1 + 3 ?( u1 ) + 0.5s1 ] + f2(s2 ) 3 4 5 6

f2(s2) u* 2

0

5+16

6+15.5

7+15

8+12.5

9+12.5

20.5

5

93

动态规划在经济管理中的应用
10.

顺序确定最优策略。 p*14 = { u*1 ,u*2 , u*3 ,u*4 } s 1= 0 u*1= 5 s 2= 3 u*2= 0 s 3= 0 u*3= 6 s 4= 4 u*4= 0

该厂按以上生产与库存方案计划其总费用将是最低的,为 20.5 千元。

94

动态规划在经济管理中的应用
例4——复合系统可靠性问题

p1

p2



pn

pk表示系统中第 k 个部件的可靠度,即在给定标准下正常工作 的概率。根据系统可靠性理论知,提高整个系统可靠性的一种十分 有效的方法是采用冗余(储备——并联)技术。当系统中第k个部 件的冗余数量为 uk 时,则系统中第k个部件的可靠度提高为: pk(uk)= 1 -(1 - pk)1+ uk 当系统中第 k 个部件(1,2,…,n)的冗余数量为 uk 时,从而整 个系统的可靠度为: P = ? pk(uk)

95

动态规划在经济管理中的应用
例:一台机器的三个重要部件对整台机器的正常运行起着至关重要 的作用,他们的可靠度及成本分别为: p1 = 0.9, p2 = 0.7, p3 = 0.6; c1 = 2, c2 = 1, c3 = 3; (单位:万元) 如果采用冗余技术来提高整台机器的可靠度,而提供的冗余经 费仅有 3 万元,这三个重要部件应该怎样冗余才能使整台机器的可 靠度最高。 这实际上是一个 3 万元如何分配使用在这三个重要部件冗余的 资源分配问题,其动态规划结构图如下:
k阶段 k+1阶段
pk(uk) 0≤ uk ≤ sk /ck 且为整数

max
(?)

sk
fk(sk)

sk+1 = sk + ckuk
fk+1(sk+1)
96

动态规划在经济管理中的应用
动态方程:(逆序递推方程)
fk(sk)= max { [ 1 -(1 - pk)1+ uk ] * fk+1(sk+1)},k= 3,2,1 uk ? Dk(sk) f4(s4)= 1

逆序递推求解动态规划方程。 (1) k = 3 s3 取值集合为: 0≤ s3 ≤ 3 f3(s3)= max { [ 1 –(1 - p3)1+ u3 ] * f4(s4)} f3( 0≤ s3 < 3)= max { [ 1 –(1 - 0.6)1 ] * 1 } = 0.6 u*3( s3 < 3 )= 0 f3(s3 = 3 )= max { [ 1 -)1 - 0.6)1+1 ] * 1 } = 0.84 u*3( s3 = 3)= 1
97

动态规划在经济管理中的应用
k=2 s2 可能取值集合为 1, 3 f2(s2)= max { [ 1 –(1 – p2)1+ u2 ] * f3(s3)} f2(1)= max (1 - 0.3)* f3(1) (1 - 0.3 )* f3(0)
2

= max

0.7 * 0.6

=0.546

0.91 * 0.6 u*2(1)= 1 0.7 * 0.84 = max 0.91 * 0.6 0.973 * 0.6 0.992 * 0.6 =0.595

(1 - 0.3)* f3(3) f2(3)= max (1 - 0.3 )* f3(2)
2

(1 - 0.3 )* f3(1)
(1 - 0.3 )* f3(0)
4

3

u*2(3)= 3
98

动态规划在经济管理中的应用
k=1 s1可能取值集合为: 3 (1 - 0.1)* f2(3) (1 - 0.1 )* f2(1)
2

f1(3)= max

0.9 * 0.595 = max 0.99 * 0.546 = 0.541

顺序确定最优策略。 s1= 3 u*1= 1 s2= 1 u*2= 1 s3= 0

u*1(3)= 1

u*3= 0

99

动态规划在经济管理中的应用
例——设备更新问题 在工业和交通运输企业中,经常会遇到因设备陈旧或部分损坏 需要更新的问题。那么,从经济上分析,一台(一批)设备应该使 用多少年后进行更新最为恰当,或合理的更新年限是多少?从而使 在某一时间内的总收入达到最大(或总成本达到最小)。这是设备 更新问题所要研究的。

100

动态规划在经济管理中的应用
设备更新问题的一般性描述: 已知一台设备的效益函数r(t),维修费用函数u(t),更新费 用函数c(t),在n 年内,每年年初都须作出决策,是继续使用 (Keep)旧设备还是更换(Replace)一台新的设备,使在n年内总 净效益最大。 设: r k(t)——在第k 年初设备已使用了t 年(或称役龄为t年)的 设备在第k 年再使用的效益。 u k(t)——在第k 年初设备已使用了t 年时继续使用的第k 年 中的维修费用。 c k(t)——在第k 年初设备已使用了t 年时的更新费用。 ? ——为折扣因子(0 ≤ ? ≤1),表示一年以后的单位收入 的价值视为现年的 ? 单位。
101

动态规划在经济管理中的应用
建立动态规划模型:
1.

阶段 k :表计划使用设备的年数,k=1,2,…,n

2.
3.

4.
5.

状态变量 sk :第 k 年初,设备已使用过的年数(役龄)。 决策变量 xk :第 k 年初更新设备,或保留使用旧设备。 Dk(sk)= { xk | xk =R ,K } 状态转移方程: sk+1 = 1 (当 xk =R ) sk+1 = sk + 1 (当xk = K ) 阶段指标值(函数)
vk(sk,xk)=

r k( sk )- u k( sk )
r k(0)- u k(0)- c k( sk )

当xk = K
当xk = R

102

动态规划在经济管理中的应用
定义 fk(sk):第 k 年初,设备已使用了 sk 年时,第 k 年至 第 n 年末的最大效益。 7. 动态规划结构图:
6.

第k+1年

1
第k 年 Max fk+1(1 )

sk
fk(sk)

(∑)

第k+1年

sk + 1
fk+1(sk+ 1)
103

动态规划在经济管理中的应用
8.

动态方程:(逆序递推方程)

fk(sk) = Max

fn+1(sn+1) = 0
9. 逆序递推求解动态规划方程。

k = n,…,2,1

104

动态规划在经济管理中的应用
某台新设备的年效益及年均维修费、更新净费用如表所示。试确定 今后 5 年内的更新策略,使总收益最大。( 取? = 1) 单位:万元
役龄 项目 效益r k(t) 维修费u k(t) 0 5 0.5 1 4.5 1 2 4 1.5 3 3.75 2 4 3 2.5 5 2.5 3

更新费c k(t)

0.5

1.5

2.2

2.5

3

3.5

105

动态规划在经济管理中的应用
k=5 s5 取值集合为:1,2,3,4

f5( 1 ) = Max

= Max

= 3.5

x*5(1)= K

f5( 2 ) = Max f5 ( 3 ) = 2 f5( 4 ) = 1.5

=3

x*5(2)= K x*5(3)= R x*5(4)= R
106

动态规划在经济管理中的应用
k=4 s4 取值集合为: 1,2,3

f4( 1 ) = Max = Max f4( 2 ) = 5.8 = 6.5 x*4(1)= R x*4(2)= R

f4( 3 ) = 5.5

x*4(3)= R

107

动态规划在经济管理中的应用
k=3 s3 取值集合为: 1,2

f3( 1 ) = Max = Max = 9.5 x*3(1)= R

f3( 2 ) = Max

= Max

= 8.8

x*3(2)= R
108

动态规划在经济管理中的应用
k=2 s2 取值集合为: 1

f2( 1 ) = Max

= Max

= 12.5

x*2(1)= R

109

动态规划在经济管理中的应用
k=1 s1 = 0

f1( 0 ) = Max

= Max 顺序确定最优策略: 年份
sk 役龄

= 17

x*1(0)= K

1 0

2 1

3 1

4 1

5 1

xk决策

K

R

R

R

K
110

动态规划在经济管理中的应用
连续确定性动态规划
对于状态变量和决策变量只取连续值,过程的演变方式为确定 性时,这种动态规划问题就称为连续确定性动态规划问题。

动态规划在经济管理中的应用
机器负荷分配问题
某种机器可以在两种负荷下生产,在高负荷下生产的产量 函数为g=8u,u为投入的机器数量,年完好率为a=0.7; 在低 负荷下生产的产量函数为h=5y, y为投入的机器数量,年完 好率为b=0.9. 开始生产时完好机器数量为s1=1000台,问每 年应该如何分配机器在两种负荷下生产可以使五年内生产 的产品总产量最高?

动态规划在经济管理中的应用
1. 阶段k: k=1,2,3,4, 5, k 表示年份 2. 状态变量sk=第k年份初(k-1年份末)可以分配的机器 数量, 已知s1=1000. 3. 决策变量uk=第k年分配到在高负荷下生产的机器数量, yk=sk-uk=第k年分配到低负荷下生产的机器数量 .

允许决策集合为Dk(sk)={uk|0≤uk≤sk}.
4。状态转移方程: sk+1=sk – 0.3uk – 0.1(sk-uk) =0.7uk+0.9(sk-uk) = 0.9sk-0.2uk

动态规划在经济管理中的应用
5. 阶段指标函数vk(sk,uk)=第k阶段初有sk台机器可以分配,有 uk台分配的高负荷下生产,sk-uk台分配到低负荷下生产的机器 数量,在本阶段所生产出来的全部产品数

vk(sk, uk)=8uk+5(sk-uk)
6. 定义fk(sk)=第k年初有sk台机器可以分配,从第k年初至第5 年末按照最优分配策略分配机器到高低负荷下生产出来的产 品的最高产品数量 7. 动态规划状态转移结构图

动态规划在经济管理中的应用
8. 列出最优指标函数的递推关系及边界条件: fk(sk)=max {8uk+ 5(sk-uk)+ fk+1(s k+1)},
0 ? uk ? sk

k=5,4,3,2,1

f6(s6)=0 ,

或者
fk(sk)=max {8uk+ 5(sk-uk)+ fk+1(s k+1)},
0 ? uk ? sk

k=4,3,2,1

f5(s5)=max {8u5+ 5(s5-u5)}
0 ? u5 ? s5

动态规划在经济管理中的应用
9. 逆序递推求解: 第1步, k=5, f5(s5)=max {8u5+ 5(s5-u5)}=max{5s5+3u5} =8s5 0 ? u5 ? s5 0 ? u5 ? s5 最优决策为u5*(s5)=s5. 第2步, k=4, f4(s4)=max {8u4+ 5(s4-u4)+f5(s5)}
0 ? u4 ? s4 0 ? u4 ? s4 0 ? u4 ? s4

=max{8u4+5(s4-u4)+8*[0.7u4+ 0.9(s4-u4)]} =max{12.2s4+1.4u4 }=13.6s4

最优决策为u4*(s4)=s4.

动态规划在经济管理中的应用
第3步, k=3, f3(s3)=max {8u3+ 5(s3-u3)+f4(s4)}
0 ? u3 ? s3 0 ? u3 ? s3

=max{8u3+5(s3-u3)+13.6*[0.9s3-0.2u3]} =max{17.24s3+0.28u3 }=17.52s3
0 ? u3 ? s3

最优决策为u3*(s3)=s3.

动态规划在经济管理中的应用
第4步, k=2,

f2(s2)=max {8u2+ 5(s2-u2)+f3(s3)}
0 ? u2 ? s2 0 ? u2 ? s2

=max{8u2+5(s2-u2)+17.52*[0.9s2-0.2u2]}

=max{20.768s2-0.504u2 }=20.768s2
0 ? u2 ? s2

最优决策为u2*(s2)=0.

动态规划在经济管理中的应用
第5步, k=1, f1(1000)=max {8u1+ 5(s1-u1)+f2(s2)}
0 ? u1 ? 1000 0 ? u1 ? 1000 0 ? u1 ? 1000

=max{8u1+5(1000-u1)+20.768*[0.9*1000-0.2u1]}

=max{23691.2-1.1536u1 }=23691.2

最优决策为u1*(s1)=0.

动态规划在经济管理中的应用
10. 最优策略为 s1=1000, u1*=0, s2= 0.9s1-0.2u1 =900, u2*=0, s3= 0.9s2-0.2u2 =810, u3*=s3 = 810, s4= 0.9s3-0.2u3 =567, u4*=s4 =567

s5= 0.9s4-0.2u4 =397, u5*=s5 =397

动态规划在经济管理中的应用
随机动态规划简介 随机动态规划不同于确定型动态规划之处在于其下一阶段的状 态不是由当前阶段的状态以及决策完全确定。确切地说。下一阶段 的状态是什么,服从一个概率分布。不过,这个概率分布仍由当前 阶段的状态以及决策完全确定。由此,我们得到随机动态规划的基 本结构。下图给出了这种结构的形象描绘:

121

动态规划在经济管理中的应用
随机动态规划简介 随机动态规划的基本结构图
v1
k阶段
k+1阶段 s1k+1

fk+1( s1k+1 )
s2k+1

p1
决策

p2 uk … pN

v2


opt

sk
fk(sk)

fk+1( s2k+1 ) …

uk ? Dk(sk)

vN
sNk+1

fk+1( sNk+1 )
122

动态规划在经济管理中的应用
随机动态规划的基本方程:
fk(sk)= opt { ? pi(vi+ fk+1( sik+1 ) )} k = n-1,…,2,1 pivi } { ?
N N

uk ? Dk(sk) i =1

fn(sn)=

un ? Dn(sn) i =1

opt

下面我们通过一个例子来具体阐述如何求解动态规划问题 请看案例——

123

动态规划在经济管理中的应用
随机动态规划简介 某公司相信对一个开发项目进行投资会取得成功。若投资会成 功的话,公司就可以获得与投资数额相同的利润,若投资失败的话, 公司非但得不到利润,就连投资也完全不能收回。公司对有关资料 详细分析后认为,每次投资成功的概率为 2/3,失败的概率为 1/3。 目前公司对此项目进行投资的总资金有 3 百万元,为了有效控制投 资风险,公司计划分三次投入资金(如果有资金的话)。公司需要 作出的决策是每次应投入多少资金(以百万元为单位),才能使三 次投资结束后公司最终获得 2 百万元利润(即最终拥有 5 百万元总 资金)的概率最大。

124

动态规划在经济管理中的应用
随机动态规划简介 1、阶段 k :第 k 次投资,k = 1,2,3 2、状态变量 sk :第 k 次投资时拥有可用于投资的资金数量。 3、决策变量 uk :第 k 次投资的资金数量。 决策集合 Dk(sk)= { uk | uk = 0,1,2,…, sk } 4、状态转移方程:
sk+1 = sk + uk sk - uk 第 k 次投资确实成功。 第 k 次投资确实失败。

5、定义阶段指标值(函数): 成功的概率为 2/3,失败的概率为 1/3。
125

动态规划在经济管理中的应用
随机动态规划简介 6、定义fk( sk ):第 k 次投资时拥有可用于投资的资金数量 sk , 并一直投资到第 3 次投资结束后公司获得 2 百万元利润的最大概率。 我们应该注意到这样一个事实——即使前两次投资失败了,公司仍 k+1阶段 然有机会最终赢得 2 百万元的利润。 7、随机动态规划的基本结构图:
s k + uk
k阶段

决策

max
( ? )

sk fk(sk)

uk uk =0,1,…,sk

fk+1( sk + uk )
sk- uk

fk+1( sk - uk )

126

动态规划在经济管理中的应用
随机动态规划简介 8、随机动态方程:
fk(sk)= max {(2/3) fk+1( sk + uk )+(1/3) fk+1( sk - uk )} uk =0,1,…,sk k = 3,2,1 f4(s4)=


0 1

s4 ? 5 s4 ≥ 5

127

动态规划在经济管理中的应用
随机动态规划简介 9、逆序递推求解随机动态方程。 k=3
s3 f3(s3) u*3

s3 = 0,1,2,3,4,5,…,12 0
0 …

1
0 …

2
0 …

3
2/3 2,3

4
2/3 1,2,3,4

≥5 1 0,≤ s3 - 5

128

动态规划在经济管理中的应用
随机动态规划简介 k=2
u2

s2 = 0,1,2,3,4,5,6
(2/3)f3(s2 + u2 )+(1/3)f3(s2 - u2 )

s2
0 1 2 3 4
≥5

0
0 0 0 2/3 2/3 1 0 0

1
0 4/9 4/9 8/9

2

3

4

f2(s2) 0 0

u*2
… … 1,2 0,2,3 1 0, ≤ s3 - 5
129

4/9 2/3 2/3 2/3 2/3 2/3

4/9 2/3 8/9 1

s3
f3(s3)

1
0

2
0

3
2/3

4
2/3

≥5
1

动态规划在经济管理中的应用
随机动态规划简介 k=1 s1 = 3
u1 s1 3 s2 f2(s2)
(2/3)f2(s1 + u1 )+(1/3)f2(s1 – u1 )

0 2/3 0 0 1 0

1 20/27 2 4/9

2 2/3 3 2/3

3 2/3 4 8/9

f1(s1) 20/27 ≥5 1

u*1
1

于是,我们有最优策略:

130

动态规划在经济管理中的应用
随机动态规划简介 最优投资策略为:
成功 s2=4,u*2=1 s1=3,u*1=1

成功 s3=5,u*3=0
失败 s3=3,u*3=2 or 3 成功 s3=3 ,u*3=2,3

失败 s2=2,u*2=1
u*2=2

失败 s3=1 ,投资失败。
成功 s3=4,u*3=1,…,4 失败 s3=0,投资失败。
131

动态规划在经济管理中的应用

动态规划的基本概念和基本原理
最优化原理:一个过程的最优策略具有这样的性 质:即无论过去的状态和决策如何,对于先前决 策所形成的状态而言,其以后的所有决策必构成 最优策略。

动态规划在经济管理中的应用
例:某公司根据计划安排,拟将某种高效率的设备4台分 配给所属的甲、乙、丙三个分厂,各分厂若获得这种设备 后可以为公司提供的盈利如下表所示。问这4台设备如何 分配给各分厂才能使该公司得到的盈利最大?
工厂 设备数

甲 0
3 7 9 12

乙 0
5 10 11 11

丙 0
4 6 11 12

(单位:万元)

0
1 2 3 4

动态规划在经济管理中的应用
解:分析、建立动态模型(5分) 根据多阶段决策问题的特征,将此问题转化为三个阶段的 决策问题 1. 阶段k = 1,2,3分别代表甲,乙,丙三个分厂。 2. 状态变量sk:表示给第k个分厂分配设备时还可以分配 的设备数量。 3. 决策变量uk:表示第k个分厂分配的设备数量。允许决 策集合为Dk = { uk|0≤uk≤sk 且为整数}

4. 状态转移方程:sk+1 = sk - uk 。
5. 阶段指标值:利润如表Vk(sk ,uk)。 6. 最优指标函数 fk(sk).

动态规划在经济管理中的应用
7. 动态递推方程:

fk(sk)= Max ? V(sk ,uk)+ f(sk+1)? k = 2,1, 0 ? uk ? sk 且为整数
f (s3) = Max ? V(s3 ,u3)? 0 ? u3 ? s3且为整数 或者 fk(sk)= Max ? V(sk ,uk)+ f(sk+1)? k = 3, 2,1, 0 ? uk ? sk 且为整数 f (s4) = 0

动态规划在经济管理中的应用
8. 逆序递推求解动态方程: (求解过程(10分)) 第1步: k=3, 状态变量s3 的取值范围为0,1,2,3,4, 且决策 变量 0 ≤u3 ≤s3 , u3 = 0, 1, 2, 3, 4, 有递推方程为 f3 ( s3 ) = max { V3(s3, u3) + 0 }, 0 ? u3 ? s3且为整数 V3(s3, u3) 0 1 2 3 4 0

s3

u3
0

f3(s3)
0

u3*
0

1
2 3 4

0
0

4 4 4 4 6 6 6 11 11

4
6 11 12

1
2 3 4

0 0

12

动态规划在经济管理中的应用
第2步: k=2, 状态变量s2 的取值范围为0,1,2,3,4, 且决策 变量 0 ≤ u2 ≤ s2 , u2 = 0, 1, 2, 3, 4, 有递推方程为

f2 ( s2 ) = max { V2(s2, u2) + f3 ( s3 ) }, 0 ? u2 ? s2且为整数
s2 u2 0 1 2

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

V2(s2, u2) + f3 ( s2 - u2 ) 1 2 3 4 5+0 5+4 10+0 5+6 10+4 5+11 10+6

f2(s2) 0 5 10 14 16

u2* 0 1 2 2 1, 2

3 4

11+0 11+4 11+0

动态规划在经济管理中的应用
第3步: k=1, 状态变量s1 等于4, 决策变量 0 ≤ u1 ≤ 4 , u1 = 0, 1, 2, 3, 4, 有递推方程为

f1 ( s1 ) = max { V1(s1, u1) + f2(s2) }, 0 ? u1 ? 4且为整数
s1

u1
4

V1(s1, u1) + f2 ( s1 – u1 ) 0 1 2 3 4 0+16 3+14 7+10 9+5 12+0

f1(s1) 17

u1* 1, 2

动态规划在经济管理中的应用
9. 按顺序递推可以确定该公司的最优设备分配方案如下: 决策方案(5分) (1)分配1台设备给分厂甲, 分配2台设备给分厂乙, 分配1台 设备给分厂丙;

(2) 分配2台设备给分厂甲, 分配2台设备给分厂乙。
此时该公司可以获得最大盈利为17(万元)。


相关文章:
15《运筹学》(第四版)连续动态规划_图文.pdf
15《运筹学》(第四版)连续动态规划_工学_高等教育_教育专区。对应教材为《运筹学》(第四版)清华大学出版社,融合多个版本运筹学课件优点。...
运筹学-第3版-课件-动态规划例题_图文.ppt
运筹学-第3版-课件-动态规划例题 - 8.1 用动态规划方法求整数规划模型,而
运筹学第八章 动态规划_图文.ppt
运筹学第八章 动态规划 - 第八章 动态规划 8.1 8.2 8.3 8.4 动态规划的研究对象和特点 动态规划的基本概念与最优化原理 动态规划的求解与应用 随机动态规划 ...
运筹学动态规划_图文.ppt
运筹学动态规划 - 动态规划(Dynamic Programming) 动态规划是美国数学家Bellman创立的。Bellman50年代执教于普林 斯顿和斯坦福大学,后进入兰德(Rand)研究所...
运筹学7动态规划.ppt
运筹学7动态规划_数学_自然科学_专业资料。运筹学7动态规划 第七 章动态规划 主要内容: §7.1 多阶段决策过程的最优化 §7.2 动态规划的基本概念和基本原理 ...
运筹学动态规划.ppt
运筹学动态规划_数学_自然科学_专业资料。第7章重点: 动态规划 (Dynamic Programming) 理解动态规划基本概念、最优化原理和基本方程; 通过资源分配、生产与存储和设备...
运筹学第10章-动态规划_图文.ppt
运筹学第10章-动态规划 - Page:1 管理运筹学 动态规划 Page:2 综 述 动态规划是解决多阶段决策过程最优 化问题的一种方法。动态规划所研究 的对象是多阶段...
第七章运筹学动态规划_图文.ppt
第七章运筹学动态规划 - 动态规划 引言 □动态规划是解决多阶段决策过程最优化的
运筹学动态规划习题_图文.ppt
运筹学动态规划习题 - 习题三 一、某工厂购进100台机器,准备生产A、B 两种
运筹学第五章动态规划.ppt
运筹学第五章动态规划_数学_自然科学_专业资料 暂无评价|0人阅读|0次下载|举报文档 运筹学第五章动态规划_数学_自然科学_专业资料。动态规划 (Dynamic programming...
运筹学-动态规划_图文.ppt
运筹学-动态规划 - 动态规划 (Dynamic programming) 动态
运筹学动态规划_图文.ppt
运筹学动态规划 - 动态规划 (Dynamic programming) 动态规划的基本思想 最短路径问题 资源分配问题 生产计划问题 背包问题 复合系统工作可靠性问题 动态规划是用...
运筹学第10章 动态规划.ppt
运筹学第10章 动态规划_数学_自然科学_专业资料。运筹学是管理类专业的一门重要
清华大学运筹学课件动态规划_图文.pdf
清华大学运筹学课件动态规划 - 动态规划 主要内容 基本概念 多阶段问题 建模与
运筹学 动态规划应用.ppt
运筹学 动态规划应用_数学_自然科学_专业资料。第七章 动态规划动态规划问题的基本概念和基本原理 动态规划模型的建立与求解 应用举例 应用举例 1。背包问题 2。...
运筹学及应用案例-动态规划.doc
运筹学及应用案例-动态规划 - 徐州工程学院数理学院 案例分析报告 课程名称 案例分析题目 专班姓学业级名号 运筹学及应用 农场五年计划的制定 指导教 ...
运筹学---动态规划_图文.ppt
运筹学---动态规划 - 这是关于运筹学里的动态规划的课件ppt... 运筹学---动态规划_理学_高等教育_教育专区。这是关于运筹学里的动态规划的课件ppt 动态...
第三讲 动态规划 (高级运筹学课件)_图文.ppt
第三讲 动态规划 (高级运筹学课件)_理学_高等教育_教育专区。(高级运筹学课件) 第三讲 动态规划 (Dynamic Programming) 动态规划是 1951 年由美国数学家贝尔曼( ...
运筹学动态规划_图文.ppt
运筹学动态规划 - 动态规划 (Dynamic programming) 背包问
运筹学-动态规划_图文.ppt
运筹学-动态规划 - Page:1 运动 态筹 规 划学 华东理工大学 工商经济
更多相关文章: