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

运筹学第五章动态规划


动 态 规 划
(Dynamic programming) 多阶段决策过程的最优化 基本概念和基本原理 动态规划模型的建立与求解 动态规划在经济管理中的应用

创始时间

上个世纪50年代

创始人

美国数学家贝尔曼

(Richard. Bellman)

第一节

多阶段决策过程的最优化

动态规划是用来解决多阶段决策过程最 优化的一种数量方法
这类活动可以按时间顺序分解成若干个相互 联系的阶段,每个阶段都有若干个方案可供选择

多阶段决策过程的最优化的目标:
达到整个活动过程的总体效果最优

系统的动态过程可以按照时间进程分为状态相 互联系而又相互区别的各个阶段,每个阶段都要进 行决策,目的是使整个过程的决策达到最优效果。

决策

决策

决策

状态
1
阶段

状态

2
阶段

状态 ? 状态

n
阶段

分类

? 离散确定型 ? 离散随机型 ? 动态规划 ? ? 连续确定型 ? ? 连续随机型

根据决策过程的时间参数是离散的还是连 续的、过程的演变是确定性的还是随机性的

注意:
动态规划是求解某类问题的一种方法, 是考察问题的一种途径,而不是一种算法。

必须对具体问题进行具体分析,运用 动态规划的原理和方法,建立相应的模型, 然后再用动态规划方法去求解。

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

2. 机器负荷分配问题:某种机器可以在高低两种不同的负 荷下进行生产。在高负荷下进行生产时,产品的年产量 g和 投入生产的机器数量u1的关系为 g=g(u1) 这时,机器的年完好率为a,即如果年初完好机器的数量 为u,到年终完好的机器就为au, 0<a<1。 在低负荷下生产时,产品的年产量h和投入生产的机器 数量u2的关系为 h=h(u2) 相应的机器年完好率b, 0<b<1。 假定开始生产时完好的机器数量为s1。要求制定一个 五年计划,在每年开始时,决定如何重新分配完好的机器 在两种不同的负荷下生产的数量,使在五年内产品的总产 量达到最高。

3 . 线性规划、非线性规划等静态的规划问题也 可以通过适当地引入阶段的概念,应用动态规划 方法加以解决。

不包含时间因素的静态决策问题(本质上 是一次决策问题)也可以适当地引入阶段的 概念,作为多阶段的决策问题用动态规划方 法来解决。

4 . 最短路问题:给定一个交通网络图如下,其中两 点之间的数字表示距离(或花费),试求从A点到G 点的最短距离(总费用最小)。
1 C1 3 6 3 3 6 C3 8 C4 1 2 3 8 D1 1 2 2 2 D2 E2 5 E1 3

5
A 3

B1

6
8 B2 7

C2

5

5
2

F1
3

4
G

3
4 D3

3
3 4 E3

6

6

F2

5

6

第二节 基本概念和基本原理
决策 状态 状态 1
阶段

决策 决策 状态 ? 状态 2 n
阶段 阶段

策略

状态转移

指标函数

基本概念

设从甘肃要铺一条煤气管道到北京,途中须经过三个省: 陕西、山西、河北,每省设一个中间站。各省建站可供选 最 择的地点及各段距离如下图,现要求选择一条甘肃到北京 短 的铺管线路 使总距离最短。 10 5 ○ 5 2 路 8 9 ○ 8 多阶段决策问题 ○ 4 6 问 8 9 2 ○ 7 6 1 ○ 6 3 ○ 题 10 ○ 7 4 3 甘肃 9 ○ 6 1 3 北京 铺设方案1: 路长=21 策略 8 ○ 4 7 ○ 河北 10 1 3 5 8 ○ ○ ○ ○ ○ 山西 陕西
1 4 6 9 10 ○ ○ ○ ○ ○

铺设方案2: 路长= 16

一个策略

每一个阶段的决策合在一起构成一个铺设方案 每个策略对应一个路长 寻找路长最短的铺设方案 寻找最优策略

1、阶段: 通常用k表示阶段,是指对整个 过程的自然划分 划分阶段的规则: 根据时间顺序或空间特征来划分阶段 目的:以便按次序来解优化问题
5
5 ○

10 2 ○ 8 9 8 如最短路问题: ○ 4 6 8 9 2 ○ 6 1 7 ○ 3 6 ○ 10 问题分成4个阶段: ○ 7 4 9 3 甘肃 ○ 3 北京 k=1,2,3,4 6 1 8 ○ 4 7 ○ 河北 山西 陕西 k=1:第一阶段,甘肃 陕西

线路: 1 2,1 3,1 4 k=3:第三阶段:山西 河北 线路: 5 8,5 9, 6 8,6 9, 7 8, 7 9

2、状态: 各阶段开始时所处的自然状况或客观条件 状态变量 sk 描述各阶段状态的变量 ,简称为状态 第k阶段的状态变量

Sk ={sk}

第k阶段的状态集合 5

如最短路问题: 第一阶段的状态: 1 ○

第二阶段的状态: ○ 2 ○ 3 ○ 4 s4 第4阶段的初始状态变量 s4 =⑧

10 2 9 ○ 8 4 6 8 ○ 9 2 ○ 6 1 7 ○ ○ 3 6 10 ○ 4 7 3 甘肃 9 3 北京 ○ 6 1 4 8 7 ○ ○ 河北 山西 陕西
第4阶段的初始状态为

5 ○ 8

8 ○

S3 ={s3} ={⑤,⑥,⑦} S5 ={⑩} 注:n个阶段的决策过程有个n+1状态变量 sn+1,表示sn演变的结果

动态规划中的状态应具有以下性质:
1、能描述过程的特征
2、具有无后效性(马尔可夫性) 当某阶段的状态给定时,这个阶段以后过 程的演变与该阶段以前各阶段的状态无关 3、状态是直接或间接可以观测的

3、决策: 当一个阶段的状态确定后,可以作出各种选
择从而演变到下一阶段的某个状态,这种选 择手段称为决策

决策变量 描述决策的变量 ,简称为决策 u k ?sk ? ? ? ? 第k阶段处于状态 sk时的决策变量
U k ?s k ? ? ?决策变量 uk (sk )允许取值的范围
8 10 ○ 4 9 北京 ○ 河北
8 ○

5

8 96 6 ○ 6 1
7 ○

5 ○

u2 3

u2

? ? ?3? ?

山西

10 2 9 ○ 4 6 2 ○ 1 7 ○ 3 7 3 甘肃 3 4 8 ○ 陕西

允许决 策集合

第2阶段当状态为③时的决策变量 可取值为:⑤,⑥,⑦ 7 决策 3 ? 7 U 2 3 ={⑤,⑥,⑦}

? ?

4、策略:由各阶段的决策组成的序列称为策略 p1,n ?s1 ? ? ? ? 从第一阶段初始状态 s1开始到
第n阶段全过程的策略 即p1,n ?s1 ? ? ? u1 ?s1 ?, u2 ?s2 ?,?un ?sn ??

P?? 策略? ——允许策略集合
8 ○

最优策略:使整个问题达到最优效果的策略
5 8 10 ○ 4 9 策略 =铺设方案 北京 ○ 7 策略 河北 ○ 山西 如{ 1 ? 3 , 3 ? 7 , 7 ? 9 , 9 ? 10} ? p1,4 ?1?

最短路问题:

8 9 6 6 ○ 6 1

5 ○

10 2 9 ○ 4 6 2 ○ 1 7 ○ 3 7 3 甘肃 3 4 8 ○ 陕西

策略:{ 最优策略=最短的铺设路线

} ? p1,4 ?1?

由各阶段的决策组成的序列称为策略 策略:

即p1,n ?s1 ? ? ?u1 ?s1 ?, u2 ?s2 ?,?un ?sn ??
原过程: 一个n段决策过程,从1到n叫作问题的原过程 原过程的一个后部子过程: 对于任意给定的k(1 ≤ k≤n),从第k段到第n段 的过程称为原过程的一个后部子过程

p1,n ?s1 ? ? ? ? 原过程的策略
原过程的一个后部子过程的策略: 即有 n个阶段的决策过程从第 k阶段 初始状态 s k 开始的策略: p ?s ? k ,n k

最短路问题:

10 ○

8 4

8 ○ 9 ○

5

北京

河北

8 9 6 6 ○ 6 1
7 ○

5 ○

山西

10 2 9 ○ 4 6 2 ○ 1 7 ○ 3 7 3 甘肃 3 4 8 ○ 陕西

原过程的一个策略:
{①→ ③ ,③→⑦,⑦ →⑨ ,⑨ → ⑩} = p1,4( ① )

p 2,4 3
p3,4
p 4,4

? ? ? {③→⑦,⑦ →⑨ ,⑨ → ⑩} ? 7 ? ? {⑦ →⑨ ,⑨ → ⑩} ? 9 ? ? {⑨ → ⑩ }
后部子过 程的策略

后部子过 程的策略 后部子过 程的策略

5、状态转移方程:是确定过程由一个状态到另一 个状态的演变过程,描述了状态转移规律。
sk 第k阶段的状态变量 u k ?sk ? ? ?表示第 k阶段处于状态 sk时的决策变量 状态转移方程:
sk ?1 ? Tk (sk , uk )

6、指标函数
V1,n ?s1 , p1,n ? ? ?在初始状态为 s1时采用原过程策略 p1,n 所对应 的指标函数 Vk ,n ?s k , pk ,n ? ? ? ? 在第k阶段状态为 sk时采用后部子过程 策略pk ,n 所对应的指标函数

用于衡量所选定的策略优劣的数量指标称为指标函数

最优策略 p * k ,n : 使指标函数 Vk ,n ?sk , pk ,n ?达到最优的策略
最优值函数 f k ?sk ? ? ? ? 从第k阶段状态 s k 开始到过程终
f k ?sk ? ? Vk ,n ?sk , p *k ,n ? ? opt Vk ,n s k , pk ,n
pk , n ?Pk , n

止采用最优策略 p *k ,n 时的指标函数值

?

?

f1 ?s1 ? ? ?初始状态为 s1时全过程采用最优策略 p *1,n 所对应的指标函数值

动态规划的基本原理

最优化原理: 一个过程的最优策略具有这样的性质,即无论初始 状态及初始决策如何,对于先前决策所形成的状态 而言,其以后的所有决策必构成最优策略 对最短路问题:E
F ○


1


E2

○ D ○
D1
2

C ○ C ○ C ○
1 2 3

B ○ B ○ B ○
1 2 3

A ○

若C1 ? D2 ? E1 ? F 是C1到F的最优策略(最短路)

则不论前面A如何到达B,B又如何到达C1 对状态 C1来说,必有: D2 ? E1 ? F是D2到F的最优策略 E1 ? F是E1到F的最优策略

对最短路问题:

最短路问题的特点:

来源于动态规划 的最优化原理

如果最短路线在第 k阶段通过 s点,则由 s点出发到 达终点的这段路线对于 从s出发到达终点的所有可 能选择的不同路线来说 ,必是最短的

找最短路线的方法:
从最后一阶段开始,用 由后向前的方法,求出 各点到 终点的最短路线,最后 求得由起点到终点的最 短路线

最短路问题的基本方程:
? f k ?s k ? ? min uk ? ? f 5 ?s5 ? ? 0

由后向前迭代

?d ?s k , u k ? ?

f k ?1 ?s k ?1 ?? k=4,3,2,1

递推公式

建立动态规划模型的步骤 1、划分阶段 划分阶段是运用动态规划求解多阶段决策问题的第一 步,在确定多阶段特性后,按时间或空间先后顺序, 将过程划分为若干相互联系的阶段。对于静态问题要 人为地赋予“时间”概念,以便划分阶段。

2、正确选择状态变量

选择变量既要能确切描述过程演变又要满足无后效性, 而且各阶段状态变量的取值能够确定。一般地,状态 变量的选择是从过程演变的特点中寻找。 3、确定决策变量及允许决策集合 通常选择所求解问题的关键变量作为决策变量,同时 要给出决策变量的取值范围,即确定允许决策集合。

4、确定状态转移方程
根据k 阶段状态变量和决策变量,写出k+1阶段状态变 量,状态转移方程应当具有递推关系。

5、确定阶段指标函数和最优指标函数,建立动态规 划基本方程
阶段指标函数是指第k 阶段的收益,最优指标函数 是指从第k 阶段状态出发到第n 阶段末所获得收益的最 优值,最后写出动态规划基本方程。 以上五步是建立动态规划数学模型的一般步骤。由于 动态规划模型与线性规划模型不同,动态规划模型没有统 一的模式,建模时必须根据具体问题具体分析,只有通过 不断实践总结,才能较好掌握建模方法与技巧。

最短路径问题
例一、从A 地到D 地要铺设一条煤气管道,其中需经过 两级中间站,两点之间的连线上的数字表示距离,如 图所示。问应该选择什么路线,使总距离最短?
3
2 A 4 B2 B1 2 1 3 C2 4 C3 3

C1

1 D

3 1

3
2 A 4 B2 B1 2 1 3

C1
C2 4 C3 3

1 D

3 1

解:整个计算过程分三个阶段,从最后一个阶段开始。

第一阶段(C →D): C 有三条路线到终点D 。
显然有 f1 (C1 ) = 1 ; f1(C2 ) = 3 ; f1 (C3 ) = 4

3
2 A 4 B2 B1 2 1 3

C1
C2 4 C3 3

1 D

3 1

第二阶段(B →C): B 到C 有六条路线。
d( B1,C1 ) + f1 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f1 (C2 ) = min 3+3 d( B1,C3 ) + f1 (C3 ) 1+4 4 = min 6 = 4 (最短路线为B1→C1 →D) 5

3
2 A 4 B2 B1 2 1 3

C1
C2 4 C3 3

1 D

3 1

d( B2,C1 ) + f1 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f1 (C2 ) = min 3+3 d( B2,C3 ) + f1 (C3 ) 1+4 3 = min 6 = 3 (最短路线为B2→C1 →D) 5

3
2 A 4 B2 B1 2 1 3

C1
C2 4 C3 3

1 D

3 1

第三阶段( A → B ): A 到B 有二条路线。
f3(A)1 = d(A, B1 )+ f2 ( B1 ) =2+4=6 f3 (A)2 = d(A, B2 )+ f2 ( B2 ) =4+3=7 ∴ f3 (A) = min d(A, B1 )+ f2 ( B1 ) = min{6,7}=6 d(A, B2 )+ f2 ( B2 ) (最短路线为A→B1→C1 →D)

3 2 A 4 B2 B1 2 3 1 3 1

C1 C2 4 3

1 D

C3

最短路线为

A→B1→C1 →D

路长为 6

练习1: 求从A到G的最短路径
1 5 A 3 B2 C1 6 8 5 D2 3 8 4 D3 3 3 E3 1 D1 2 2 E1 5 6

B1
6 8 7

3

C2

3
3

3 5 2 6 F2 F1 4 G

2

E2

6

C3

3

C4

最优路线为:A → B1 → C2 → D1 → E2 → F2 → G

路长=18

C1 6 2 E1 3 1 D1 8 k=6 , F1 G f6(F1)=4 B1 3 5 F1 4 5 2 C2 3 6 A 5 5 1 G F2 G ,f6(F2)=3 E2 D2 3 2 2 B2 87 C3 3 6 F2 3 3 D3 3 E3 6 6 C4 8 3 k=5,出发点E1、E2、E3 4

3? 4 ?d5 ?E1 , F1 ? ? f 6 ?F1 ? ? f 5( E1) ? min ?d 5 ?E , F ? ? f ?F ? ? ? min{ } ? 7 5?3 1 2 6 2 ? ?

u5(E1)=F1
E1 F1 G

? d5 ?E2 , F1 ? ? f 6 ?F1 ? f5 ?E 2? ? min ? ?d5 ?E2 , F2 ? ? f 6 ?F2 ?
? d5 ?E3 , F1 ? ? f 6 ?F1 ? f 5 ?E3? ? min ? ?d5 ?E3 , F2 ? ? f 6 ?F2 ?

5? 4 ? ? ? min{ } ? 5 2?3 ?
6?4 ? }?9 ? ? min{ 6?3 ?

u5(E2)=F2
E2 F2 G

u5(E3)=F2
E3 F2 G

k=4, f4(D1)=7 u4(D1)=E2

k=3,

f3(C1)=13 u3(C1)=D1

f4(D2)=6 u4(D2)=E2 f4(D3)=8 u4(D3)=E2
k=2, f2(B1)=13 u2(B1)=C2

f3(C2)=10 u3(C2)=D1
f3(C3)=9 u3(C3)=D1

f3(C4)=12 u3(C4)=D3

f2(B2)=16 u2(B2)=C3
k=1,

f1(A)= min

d1(A,B1)+ f2(B1)
d1(A,B2)+ f2(B2)

= min

5+13

3+16

=18

u1(A)=B1

u2(B1)=C2

u3(C2)=D1

u4(D1)=E2

u1(A)=B1
E1 F1 G

u2(B1)=C2
E2 F2 G

u3(C2)=D1

u4(D1)=E2 u5(E2)=F2

u5(E1)=F1 u5(E2)=F2

u5(E3)=F2
E3 F2 G

7
1 5 A 3 B2 B1 6 3

5
C1 C2 3 6

9
8
5 D2 3 D3 1 2

u6(F2)=G
E1

D1

2 2

最优策略
5 6 3 5 F1 3 F2 4 G

8
7 6 C3

3
3

E2

2
6

8 4
C4

3

E3

练习2:

求从A到E的最短路径
B1
2

12
14 10

10

C1
9

3

D1
6

5 2

A

5
1

B2 B3

6

4 13

C2
8

5

E

12 11

D2
10

C3

路线为A→B2→C1 →D1 →E ,最短路径为19

生产与存储问题:某工厂生产并销售某种产品。 已知今四个月市场需求预测如下表,又每月生产 j个单位产品的费用为
? 0 c? j ? ? ? ?3 ? j j?0 j ? 1,2,?6
i月 1 2
3

3
2

4
4

g(i)需求 2

每月库存i个单位产品的费用E(i)=0.5i(千 元),该厂最大库存容量为3个单位,每月最大 生产能力为6个单位,计划开始和计划期末库存 量都是零,试制定四个月的生产计划,在满足用 户需求条件下,使总费用最小。 阶段k=1,2,3,4 第k阶段的状态变量sk =第k个月月初的库存量 S1={0}, S2={0,1,2,3}, S3={0,1,2,3},S4={0,1,2,3}

生产与存储问题 某工厂生产并销售某种产品。 已知今后四个月市场需求预测及每月生产j个单位 产品的费用如下:
月 1 2 3 4

需求 2

3

2

4

? 0 c? j ? ? ? ?3 ? j

j?0 j ? 1,2,?6

每月库存i个单位产品的费用E(i)=0.5i(千元),该 厂最大库存容量为3个单位,每月最大生产能力为 6个单位,计划开始和计划期末库存量都是零,试 制定四个月的生产计划,在满足用户需求条件下, 使总费用最小。 k=1,2,3,4 sk=第k个月月初的库存量 S1={0} S2={0,1,2,3} S3={0,1,2,3} S4={0,1,2,3} 决策变量 uk ?sk ? ? 第k月月初库存量为 sk时产品的产量

U1 ?0?={2,3,4,5} U 2 ?1? ={2,3,4,5}

U 3 ?2? ={0,1,2,3} U 4 ?1?={3}

生产与存储问题 某工厂生产并销售某种产品。已知今四个月市 场需求预测如下表,又每月生产j个单位产品的费用为
i月 1 2 3 3 2 4 4 g(i)需求 2

? 0 c? j ? ? ? ?3 ? j

j?0 j ? 1,2,?6

每月库存i个单位产品的费用E(i)=0.5i(千元),该厂最大库存 容量为3个单位,每月最大生产能力为6个单位,计划开始和计 划期末库存量都是零,试制定四个月的生产计划,在满足用户 需求条件下,使总费用最小。

k=1,2,3,4 sk=第k个月月初的库存量 决策变量 uk ? 第k阶段产品的产量 一个策略=一个生产方案
p1, 4 ?0? ? ? 2,3,2,4

? 费用:23(千元) p1, 4 ?0? ? ? 2,5,0,4 ? 费用:21(千元)

最优策略: 使总费用最小的生产方案

生产与存储问题 某工厂生产并销售某种产品。已知今四个月市 场需求预测如下表,又每月生产j个单位产品的费用为
i月 g(i)需求 1 2 2 3 3 2 4 4

? 0 c? j ? ? ? ?3 ? j

j?0 j ? 1,2,?6

每月库存i个单位产品的费用E(i)=0.5i(千元),该厂最大库存 容量为3个单位,每月最大生产能力为6个单位,计划开始和计 划期末库存量都是零,试制定四个月的生产计划,在满足用户 需求条件下,使总费用最小。

阶段k=1,2,3,4 状态变量sk=第k个月月初的库存量 决策变量 uk ?sk ? ? 第k月月初库存量为 sk时产品的产量 状态转移方程:sk ?1 ? uk ? sk ? g (k )

求 f 1 ( 0)

最优值函数 f k ( s k ):第 k月月初库存为 s k时,从本月到 计划结束的最小总费用

最大生产能力为6个单位, 最大库存容量为3个单位, 库存费E(i)=0.5i,计划开始和计划期末库存量为零
i月 1 2
3

3
2

4
4

g(i)需求 2

生产费用 ? 0 c? j ? ? ? ?3 ? j

j?0 j ? 1,2, ? 6

f k ( s k ):第 k月月初库存为 s k时,从本月到计划结束 的最小总费用 求f 4 ( s 4 ) 当k=4时, s4 ? 0,1,2,3

u4(s4)对应的总费用=生产费+库存费 ? c?u 4 ? ? E ( s 4 )

f 4 ?s 4 ? ? min?c?u 4 ? ? E ( s 4 )?
u4

s4 u4
f 4 (s4 )

0 4 7 4

1
3 6.5 3

2
2 6 2

3 1 5.5
1

u *4

最大生产能力为6个单位, 最大库存容量为 s3 s4 3个单位, 0 库存费E(i)=0.5i,计划开始和计划期末库存量为零 0
i月 1 2
3

3
2

4
4

g(i)需求 2

生产费用 ? 0 c? j ? ? ? ?3 ? j

j?0 1 j ? 1,2, ? 6u 3 ? 0

f 4 (1)

1

求f 3 (s3 ) 当k=3时,

s3 ? 0,1,2,3

2 3

u3 ? 1 2

f 4 ( 2) f 4 (3)

分析f 3 (3): 当s3 ? 3时, u3 ?s3 ? ? u3 ?3? ? 0,1,2 u3(3)对应的总费用=生产费+库存费 ? c?u3 ? ? E (3)

u3 ? 2 3 f 3 ( s3 ) ? 第3月月初库存为 s3时,从本月到计划结束 的最小总费用 ? min ?C (u 3 ?s 3 ?) ? E ( s 3 ) ? f 4 ?s 4 ??
u3 ? s 3 ?

f 3 (3) ?min?C(0) ? E(3) ? f 4 ?1?, C(1) ? E(3) ? f 4 ?2?, C(2) ? E(3) ? f 4 ?3??

? min?C (u 3 ?3?) ? E (3) ? f 4 ? s4
u3 ?3 ?

?? 0

最大生产能力为6个单位, 最大库存容量为 s3 3个单位, 库存费E(i)=0.5i,计划开始和计划期末库存量为零
i月 1 2 3 4

g(i)需求 2

3

2

4

s4 u4
f 4 (s4 )

0 4 7 4

1 3 6.5 3

2 2 6 2
u3 ? s 3 ?

3 1 5.5

生产费用 ? 0 c? j ? ? ? ?3 ? j

j?0 j ? 1,2, ? 6

u *4

1

f 3 ?s 3 ? ? min ?C (u 3 ?s 3 ?) ? E ( s 3 ) ? f 4 ?s 4 ??
0 1 2 3

s3 u3
f 3 ?s3 ?
2 3

4 5

1

2 3

4

0 1

2 3

0 1 2

C ? E ? f 4 12 12 .5 13 13.5 11.5 12 12.5 13 8 11.5 12 12.5 8 11.5 12
* ?s3 ? u3

12

11.5

8 0

8 0

2

1

i月 g(i)需求

1 2

2 3

3 2

4 4

当k=2时, 求f 2 (s 2 )

s 2 ? 0,1,2,3

f 2 ( s 2 ) ? 第2月月初库存为 s 2时,从本月到计划结束 的最小总费用

u2(s2)对应的总费用=生产费+库存费
? c?u 2 ? ? E ( s 2 )

f 2 ( s 2 ) ? min ?C (u 2 ) ? E ( s 2 ) ? f 3 ?s 3 ??
u 2 ? s2 ?

k=3

s3 u3
f 3 ?s3 ?
2 3

0

1

2

3

4 5

1

2 3

4

0 1

2 3

0 1 2

C ? E ? f 4 12 12 .5 13 13.5 11.5 12 12.5 13 8 11.5 12 12.5 8 11.5 12
* ?s3 ? u3

12

11.5

8 0

8 0

2
u 2 ? s2 ?

1

f 2 ( s 2 ) ? min ?C (u 2 ) ? E ( s 2 ) ? f 3 ?s 3 ?? 当k=2时,
s2 u2
f 2 ?s 2 ?
0 3 4 5 6 2 3 1 4 5 1 2 2 3 4 0 1 3 2 3

C ? E ? f 3 18 18.5 16 17 17.5 18 15.5 16.5 17 17.5 15 16 13.5 17 14.5 15.5
* ?s2 ? u2

16 5

15.5 4

15

13.5

3

0

i月

1

2

3

4

g(i)需求 2

3

2

4

当k=1时, 求f1 (s1 )

s1 ? 0

f1 (0) ? 第1月初库存为 0时,从第一个月到计划 结束的最低总费用

u1(0)对应的总费用=生产费 ? c?u1 ?
f 1 ?0 ? ? min ?C (u1 ) ? f 2 ?s 2 ??
u1 ? 0 ?

k=2
s2 u2
f 2 ?s 2 ?
0 3 4 5 6 2 3 1 4 5 1 2 2 3 4 0 1 3 2 3

C ? E ? f 3 18 18.5 16 17 17.5 18 15.5 16.5 17 17.5 15 16 13.5 17 14.5 15.5
* ?s2 ? u2

16
5

15.5
4

15
3

13.5
0

? C (u1 ) ? f 2 ?s 2 ?? 当k=1时,f 1 ?0 ? ? min u ?0 ?
1

C ? f2

s1 u1

0 2 3 4 5 21 21.5 22 21 2

* u 结论: f 1 ?0 ? ? 21 1 ?0? ? 2 * ?2? ? 0 u3

* ?0? u1

f 1 ?0 ?

21.5

* ?0? ? 5 u2 * ?0? ? 4 u4

最优生产方案: 第1个月生产2个, 第2个月生产5个, 第3个月生产0个, 第4个月生产4个, 总费用 ? 21

? c?u 4 ? ? E ( s 4 )? k ? 4时, f 4 ?s 4 ? ? min u
4

? min?c?u 4 ? ? E ( s 4 ) ? f 5 ( s5 )?
u4
3

? C (u 3 ) ? E ( s 3 ) ? f 4 ?s 4 ?? k ? 3时,f 3 ?s 3 ? ? min u ?s ?
3

min ?C (u 2 ) ? E ( s 2 ) ? f 3 ?s 3 ?? k ? 2时,f 2 ( s 2 ) ? u ?s ?
k ?1 时,f 1 ?0 ? ? min ?C (u1 ) ? f 2 ?s 2 ??
u1 ? 0 ?
2 2

? s1 ? 0 ?C (u1 ) ? E ( s1 ) ? f 2 ?s 2 ?? f 1 ?s1 ? ? f 1 ?0 ?? min u ?s ?
1 1

生产存储问题的基本方程:
? ? k ? ? ? 5

f ?s k ? ? min ?C (u k ) ? E ( s k ) ? f k ?1 ?s k ?1 ?? k ? 4,3,2,1

f ?s5 ? ? 0

uk ?s k ?

其中 s k ?1 ? s k ? u k ? g ?k ?

最优化原理: 一个过程的最优策略具有这样的性质,即无 论初始状态及初始决策如何,对于先前决策 所形成的状态而言,其以后的所有决策必构 成最优策略
最短路问题的基本方程:
? f k ?s k ? ? min uk ? ? f 5 ?s5 ? ? 0

?d ?s k , u k ? ?

f k ?1 ?s k ?1 ?? k=4,3,2,1

生产存储问题的基本方程为:

? f k ?s k ? ? min?c?u k ? ? E ( s k ) ? f k ?1 ?s k ?1 ?? uk ? ? d ? s k ,u k ? ? f 5 ?s5 ? ? 0

k ? 4,3,2,1

动态规划的基本方程为:

? ? ?

f k ?s k ? ? opt? d ?s k , u k
uk

??

f k ?1 ?s k ?1 ??

f n?1 ?sn?1 ? ? 0

k=n,n-1,n-2, …,3,2,1

其中opt为最优,可取min或max

投资分配问题
现有数量为a(万元)的资金,计划分配给n 个工厂, 用于扩大再生产。 假设:xi 为分配给第i 个工厂的资金数量(万元) ; gi(xi)为第i 个工厂得到资金后提供的利润值(万元)。 问题是如何确定各工厂的资金数,使得总的利润为 最大。 n 据此,有下式:m ax Z ? g (x )

?
i ?1

i

i

? n ?? xi ? a ? i ?1 ? x ? 0 i ? 1 .2 . ? . n ? i

令:fk(x) = 以数量为x 的资金分配给前k 个工厂,所 得到的最大利润值。 用动态规划求解,就是求 fn(a) 的问题。 当 k=1 时, f1(x) = g1(x) (因为只给一个工厂)

当1<k≤n 时,其递推关系如下: 设:y 为分给第k 个工厂的资金(其中 0≤y ≤ x ),此时 还剩 x - y(万元)的资金需要分配给前 k-1 个工厂,如 果采取最优策略,则得到的最大利润为fk-1(x-y) ,因此 总的利润为:

gk(y) + fk-1(x-y)

所以,根据动态规划的最优化原理,有下式:

f k ( x ) ? max?g k ( y ) ? f k ?1 ( x ? y )?
0? y ? x

其 中k ? 2.3.?.n
如果a 是以万元为资金分配单位,则式中的y 只取 非负整数0,1,2,…,x。上式可变为:

f k ( x) ?

? gk ( y) ? y ? 0 ,1, 2 ,?, x
max

f k ?1 ( x ? y )?

例题:
设国家拨给60万元投资,供四个工厂扩建使用,每 个工厂扩建后的利润与投资额的大小有关,投资后的 利润函数如下表所示。
投资 利润

0 0 0

10 20 20

20 50 40

30 65 50

40 80 55

50 85 60

60 85 65

g1(x) g2(x)

g3(x) g4(x)

0 0

25 25

60 40

85 50

100 60

110 65

115 70

解:依据题意,是要求 f4(60) 。

按顺序解法计算。 第一阶段:求 f1(x)。显然有 f1(x) = g1(x),得到下表
投资

0 0 0

10 20 10

20 50 20

30 65 30

40 80 40

50 85 50

60 85 60

利润

f1(x) = g1(x)

最优策略

第二阶段:求 f2(x)。此时需考虑第一、第二个工厂如 何进行投资分配,以取得最大的总利润。
f 2 (60) ?

? g2 ( y ) ? y ? 0 ,10 ,?, 60
max

f1 (60 ? y )?

? g 2 (0) ? f1 (60) ? ?0 ? 85 ? ? g (10) ? f (50) ? ?20 ? 85? 1 ? 2 ? ? ? ? g 2 (20) ? f1 (40)? ?40 ? 80? ? ? ? ? ? max? g 2 (30) ? f1 (30) ? ? max?50 ? 65? ? 120 ? g (40) ? f (20)? ?55 ? 50? 1 ? 2 ? ? ? ? g 2 (50) ? f1 (10) ? ?60 ? 20? ? ? ?65 ? 0 ? ? ? ? g 2 (60) ? f1 (0) ?
最优策略为(40,20),此时最大利润为120万元。 同理可求得其它 f2(x) 的值。

f 2 (50) ?

? g2 ( y) ? y ? 0 ,10 ,?, 50
max

f1 (50 ? y )?

? g 2 (0) ? f1 (50) ? ? g (10) ? f ( 40) ? 1 ? 2 ? ? ? g 2 ( 20) ? f1 (30) ? ? ?? ? ? 105 ? g 2 (30) ? f1 ( 20) ? ? g 2 ( 40) ? f1 (10) ? ? ? ? ? g 2 (50) ? f1 (0) ? ?
最优策略为(30,20),此时最大利润为105万元。

f 2 ( 40) ?

? g2 ( y) ? y ? 0 ,10 ,?, 40
max

f1 ( 40 ? y )?

? 90
最优策略为(20,20),此时最大利润为90万元。

f 2 (30) ?

? g2 ( y) ? y ? 0 ,10 , 20 , 30
max

f1 (30 ? y )?

? 70
最优策略为(20,10),此时最大利润为70万元。

f 2 ( 20) ? max ?g 2 ( y ) ? f1 ( 20 ? y )?
y ? 0 ,10 , 20

? 50
最优策略为(20,0),此时最大利润为50万元。

f 2 (10) ? max?g 2 ( y ) ? f1 (10 ? y )?
y ? 0 ,10 ,

? 20 最优策略为(10,0)或( 0 , 10 ) ,此时最大利润 为20万元。
f2(0) =0。最优策略为(0,0),最大利润为0万元。 得到下表

投资 利润

0 0

10 20

20 50

30 70

40 90

50 105

60 120

f2(x) 最优策略

(0,0) (10,0) (20,0) (20,10) (20,20) (30,20) (40,20) (0,10)

第三阶段:求 f3(x)。此时需考虑第一、第二及第三个 工厂如何进行投资分配,以取得最大的总利润。
f 3 (60) ?

? g3 ( y ) ? y ? 0 ,10 ,?, 60
max

f 2 (60 ? y )?

? g3 (0) ? f 2 (60) ? ?0 ? 120 ? ? g (10) ? f (50) ? ?25 ? 105? 2 ? 3 ? ? ? ? g3 (20) ? f 2 (40)? ?60 ? 90 ? ? ? ? ? ? max? g3 (30) ? f 2 (30) ? ? max?85 ? 70 ? ? 155 ? g (40) ? f (20)? ?100? 50? 2 ? 3 ? ? ? ? g3 (50) ? f 2 (10) ? ?110? 20? ? ? ?115? 0 ? ? ? ? g3 (60) ? f 2 (0) ?
最优策略为(20,10,30),最大利润为155万元。

同理可求得其它 f3(x) 的值。得到下表

投资 利润

0 0

10 25

20 60

30 85

40 110

50 135

60 155

f3(x)

最优 (0,0,0) (0,0,10) (0,0,20) (0,0,30) (20,0,20) (20,0,30) (20,10,30) 策略

第四阶段:求 f4(60)。即问题的最优策略。
f 4 (60) ?

? g4 ( y ) ? y ? 0 ,10 ,?, 60
max

f 3 (60 ? y )?

? g 4 (0) ? f 3 (60) ? ?0 ? 155 ? ? g (10) ? f (50) ? ?25 ? 135? 3 ? 4 ? ? ? ? g 4 (20) ? f 3 (40)? ?40 ? 110? ? ? ? ? ? max? g 4 (30) ? f 3 (30) ? ? max?50 ? 85 ? ? 160 ? g (40) ? f (20)? ?60 ? 60 ? 3 ? 4 ? ? ? ? g 4 (50) ? f 3 (10) ? ?65 ? 25 ? ? ? ?70 ? 0 ? ? ? ? g 4 (60) ? f 3 (0) ?
最优策略为(20,0,30,10),最大利润为160万元。

练习:
求投资分配问题得最优策略,其中a=50 万元,其余 资料如表所示。
投资 利润

0 0

10 21

20 40

30 52

40 80

50 85

g1(x)

g2(x) g3(x)

0 0

15 25

36 60

50 65

73 68

100 70

例:某公司打算在3个不同的地区设置4个销售点, 根据市场部门估计,在不同地区设置不同数量的销 售点每月可得到的利润如表所示。试问在各地区如 何设置销售点可使每月总利润最大。
地 区 1 2 3 销售点 0 0 0 0 1 16 12 10 2 25 17 14 3 30 21 16 4 32 22 17

x1=2,x2=1,x3=1,f3(4)=47

四、背包问题
有一个徒步旅行者,其可携带物品重量的限度为a 公 斤,设有n 种物品可供他选择装入包中。已知每种物品 的重量及使用价值(作用),问此人应如何选择携带 的物品(各几件),使所起作用(使用价值)最大?
物品 重量(公斤/件) 每件使用价值

1
a1

2
a2




j
aj




n
an

c1

c2



cj



cn

这就是背包问题。类似的还有工厂里的下料问题、 运输中的货物装载问题、人造卫星内的物品装载问题 等。

设xj 为第j 种物品的装件数(非负整数)则问题的数学 n 模型如下:

maxZ ? ? c j x j
j ?1

?n ?? a j x j ? a ? j?i ? x ? 0且为整数 ( j ? 1.2.? .n) ? j
用动态规划方法求解,令

fx(y) = 总重量不超过 y 公斤,包中只装有前k 种物品 时的最大使用价值。
其中y ≥0, k =1,2, …, n 。所以问题就是求 fn(a)

其递推关系式为:
y 0? x k ? ak

f k ( y ) ? m ax ?ck x k ? f k ?1 ( y ? a k x k )?

其中 2 ? k ? n
当 k=1 时,有:

? y? f1 ( y ) ? c1 ? ?a ? ? , ? 1?

? ? y ?? ? x1 ? ? ?a ? ?? ? 1 ?? ?

? y? y ? 其中? ? a ?表示不超过 a 的最大整数 1 ? 1?

例题:求下面背包问题的最优解

m axZ ? 8 x1 ? 5 x 2 ? 12 x 3 ? 3 x1 ? 2 x 2 ? 5 x 3 ? 5 ? ? x1 , x 2 , x 3 ? 0且为整数
解:a=5 ,问题是求 f3(5)

1 重量(公斤) 3 使用价值 8
物品

2 2 5

3 5 12

f 3 (5) ? m ax ? 12x 3 ? f 2 (5 ? 5 x 3 )?
5 0? x 3 ? a3 x 3整 数

f 3 ( 5) ? m ax ? 12 x 3 ? f 2 ( 5 ? 5 x 3 )?
0? x 3 ?

=m ax? 12 x 3 ? f 2 ( 5 ? 5 x 3 )?
0? x 3 ?

5 a3 x 3整 数

? 12x 3 ? f 2 (5 ? 5 x 3 )? =m ax
x3 = 0, 1

5 5 x 3整 数

? ? =m ax?0 ? f 2 ( 5), 12 ? f 2 ( 0)? ( x 3 ?1 ) ? ( x3 ? 0 ) ?

f 2 (5) ? m ax ? 5 x 2 ? f 1 (5 ? 2 x 2 )? =m ax? 5 x 2 ? f 1 (5 ? 2 x 2 )? = m ax? 5 x 2 ? f 1 (5 ? 2 x 2 )?
x2 =0, 1, 2 5 0? x 2 ? 2 x 2整 数 5 0? x 2 ? a2 x 2整 数

? ? =m ax?0 ? f 1 (5), 5 ? f 1 ( 3), 10 ? f 1 (1) ? ( x 2 ?1 ) ( x2 ? 2) ? ( x2 ? 0 ) ?

f 2 (0) ? m ax ? 5 x 2 ? f 1 (0 ? 2 x 2 )? =m ax? 5 x 2 ? f1 (0 ? 2 x 2 )? =m ax? 5 x 2 ? f1 (0 ? 2 x 2 )?
x2 =0 0 0? x 2 ? 2 x 2整 数 0 0? x 2 ? a2 x 2整 数

? ? =m ax?0 ? f1 (0) ? ? f1 (0) ? ( x2 ? 0 ) ?

? ? ? f 2 (5) ? max?0 ? f1 (5), 5 ? f1 ( 3), 10 ? f1 (1) ? ( x 2 ?1 ) ( x2 ? 2 ) ? ( x2 ? 0 ) ? ? max?8, 5 ? 8, 10? ? 13 ( x1 ? 1, x2 ? 1)

5 f1 (5) ? c1 x1 ? 8 ? ? 8 3 3 f1 ( 3) ? c1 x1 ? 8 ? ? 8 3 1 f1 (1) ? c1 x1 ? 8 ? ? 0 3 0 f1 (0) ? c1 x1 ? 8 ? ? 0 3

( x1 ? 1) ( x1 ? 1) ( x1 ? 0) ( x1 ? 0)

? ? f 2 ( 0) =max?0 ? f1 (0) ? ? f1 (0) ? 0 ( x1 ? 0, x2 ? 0) ? ( x2 ? 0 ) ?

? ? ? f 3 ( 5) =m ax?0 ? f 2 ( 5), 12 ? f 2 ( 0)? ( x 3 ?1 ) ? ( x3 ? 0 ) ? ? 0 ? 13, 12 ? 0 ? ? m ax ? 13 ( x1 ? 1, x 2 ? 1, x 3 ? 0)
所以,最优解为 X=(1 . 1 . 0),最优值为 Z = 13。

练习1:某厂生产三种产品,各种产品重量与利 润的关系如表所示。现将此三种产品运往市场出售, 运输能力总重量不超过 6 吨,问如何安排运输,使 总利润最大?
种类

1

2

3

重量(吨/公斤)
单件利润(元)

2

3

4

80 130 180

最优方案:X1 =(0.2.0)X2 =(1.0.1)Z=260

练习2:求下列问题的最优解

m axZ ? 4 x1 ? 5 x 2 ? 6 x 3 ? 3 x1 ? 4 x 2 ? 5 x 3 ? 10 ? ? x1 , x 2 , x 3 ? 0且为整数
X=(2. 1. 0) 最优值为 Z = 13

五、排序问题
排序问题指n 种零件经过不同设备加工是的顺序问题。 其目的是使加工周期为最短。 1、n × 1 排序问题

即n 种零件经过1 种设备进行加工,如何安排?

例一、
零件代号 加工时间(t) 交货日期(d)

j1

j2

j3

j4

j5

3 23

7 20

1 8

5 6

4 14

(1)平均通过设备的时间最小
按零件加工时间非负次序排列顺序,其时间最小。(即 将加工时间由小到大排列即可)
零件加工顺序 工序时间 实际通过时间 交货时间
j3
j1

j5

j4

j2

1 1 8

3 4 23

4 8 14

5 13 6

7 20 20

平均通过时间

1 x ? ( 20 ? 13 ? 8 ? 4 ? 1) ? 9.2 5

延迟时间 = 13 – 6 = 7
(2)按时交货排列顺序
零件加工顺序 工序时间 实际通过时间
j4

j3

j5

j2

j1

5 5

1 6

4 10

7 17

3 20

交货时间

6

8

14

20

23

延迟时间 = 0

1 平均通过时间 x ? ( 20 ? 17 ? 10 ? 6 ? 5) ? 11.6 5

(3)既满足交货时间,又使平均通过时间最小
零件加工顺序 工序时间 实际通过时间 交货时间
j3
j4
j1

j5

j2

1 1 8

5 6 6

3 9 23

4 13 14

7 20 20

延迟时间 = 0 平均通过时间

1 x ? ( 20 ? 13 ? 9 ? 6 ? 1) ? 9.8 5

2、n × 2 排序问题
即n 种零件经过2 种设备进行加工,如何安排?

例二、
设备 A 零件

j1
6

j2
8

j3
7

j4
3

j5
5

B
A B

3

2

5

9

4

T

经变换为
设备 A B 零件

j4
3 9

j3
7 5

j5
5 4

j1
6 3

j2
8 2

加工周期 T = 3+7+5+6+8+2 = 31 即? t Ai ? t B小 加工顺序图如下:
A B
j4
3

j3
7 +2 9

j5
5 +2 5

j1
6 4 3

j2
8 -5 2

T

3、n × 3 排序问题
即n 种零件经过 3 种设备进行加工,如何安排?

例三、

j1 j2 j3 j4 j5

A 10 7 8 6 6

B 3 5 6 4 5

C 9 3 4 3 8

A B C T

变换

j1 j2 j3 j4 j5

A+B 10+3 7+5 8+6 6+4 6+5

B+C 3+9 5+3 6+4 4+3 5+8

排序

j5

j1
j3

j2 j4

A+B 6+5 10+3 8+6 7+5 6+4
A 6 10 8 7 6 B 5 3 6 5 4

B+C 5+8 3+9 6+4 5+3 4+3
C 8 9 4 3 3

复原
j5

j1 j3 j2 j4

计算

T = 6+10+8+7+6+4+3 = 44

计算依据:

m int Ai ? m axt Bi 即可按下式计算



m int C i ? m axt Bi ? t B ? t C 或 ? t ci ? t B ? t A

?t

Ai

练习:
j1 j2 j3 j4
j2
j1
A 6 7 9 5 B 4 2 7 8 C 7 8 10 11

j4

j3

T=45


相关文章:
运筹学第五章动态规划.ppt
运筹学第五章动态规划_数学_自然科学_专业资料 暂无评价|0人阅读|0次下载|举报文档 运筹学第五章动态规划_数学_自然科学_专业资料。动态规划 (Dynamic programming...
运筹学 第05章 动态规划_图文.ppt
运筹学 第05章 动态规划 - 运筹学 第五章 动态规划 本章重点 ?动态规划的
大学运筹学经典课件第五章动态规划_图文.ppt
大学运筹学经典课件第五章动态规划 - 第五章 动态规划(Dynamic pr
运筹学第五章 动态规划2_图文.ppt
运筹学第五章 动态规划2 - 第五章 动态规划 动态规划简介 动态规划所解决的问
管理运筹学 第5章 动态规划_图文.ppt
管理运筹学 第5章 动态规划 - 管理运筹学 第五章 动态规划 5.1. 动态规
运筹学教程五动态规划素材_图文.ppt
运筹学教程五动态规划素材 - 第五章 动态规划 不要过河拆桥 1 动态规划 Dy
运筹学第五章_图文.ppt
运筹学第五章 - 第五章 动态规划(Dynamic programming) §
运筹学教程课件五 动态规划_图文.ppt
运筹学教程课件五 动态规划 - 第五章 动态规划 不要过河拆桥 1 动态规划 D
运筹学-动态规划-13,14_图文.ppt
运筹学-动态规划-13,14 - 第五章 动态规划 ? §5.1 动态规划的基本
运筹学动态规划_图文.ppt
运筹学动态规划 - 运筹学 课程主要内容 第一章 第二章 第三章 第四章 第五章 第七章 第八章 第九章 线性规划与单纯形法 对偶理论与灵敏度分析 运输问题 ...
运筹学04_动态规划(2).ppt
运筹学第五章 动态规划2 48页 免费 2.运筹学 动态规划解法 29页 免费如
5.2动态规划的最优性原理_图文.ppt
5.2动态规划的最优性原理 - 运筹学所有课件,考试必用。... 运筹学 第五章 动态规划 §2 动态规划的最优性原理多阶段决策过程的特点是每个阶段都要进行决策,具...
第五章动态规划_图文.ppt
第五章动态规划 - 第五章 动态规划 §5.1多阶段决策问题 §5.2动态规划的基本概念 §5.3动态规划的基本思想及最优性原理 §5.4动态规划的应用 §5.5动态...
第五章动态规划.ppt
运筹学 ”编写 组 2008年12月 第五章 动态规划 内容多阶段决策过程与方
第五章 动态规划 目录.ppt
第五章 动态规划 目录 - 运筹学,山东大学,最新,课件,第三版... 第五章 动态规划 目录_高等教育_教育专区。运筹学,山东大学,最新,课件,第三版 ...
第五章动态规划11.25_图文.ppt
第五章动态规划11.25 - 动态规划 (Dynamic programming
动态规划运筹学基础及其应用胡运权第五版1_图文.ppt
动态规划运筹学基础及其应用胡运权第五版1 - 第五章 动态规划 动态规划 Dyn
运筹学 天津大学第五章_图文.ppt
运筹学 天津大学第五章 - 第五章 动态规划(Dynamic programmi
《运筹学》 第五章习题及 答案.doc
运筹学第五章习题 运筹学》 1.思考题 . (1)试述动态规划的"最优化原理"及它同动态规划基本方程之间的关系. (2)动态规划的阶段如何划分? (3)试述用...
...学与最优化方法课件(修改2007)--第五章--动态规划_....ppt
运筹学与最优化方法课件(修改2007)--第五章--动态规划 - 第五章 动态规划 §1 多阶段决策过程最优化 §2 动态规划基本概念 §3 动态规划基本原理 §4 动态...
更多相关文章: