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

15《运筹学》(第四版)连续动态规划


第三章 动态规划(Dynamic Programming)

主讲人:莫 莉

moli@hust.edu.cn
2015 年 6 月
水电与数字化工程学院 莫 莉

前节回顾


? 引例


多种应用


? 引例



? 动态规划基本概念
? 离散动态规划

? 动态规划优劣
? 经营管理中的应用

水电与数字化工程学院

莫 莉

前节回顾
动态规划所解决的问题:多阶段问题

动态规划的核心:

在于将问题公式化,也可以说 ,动态规划是将多阶段决策问 题进行公式化的一种技术。

动态规划的优缺点:
?适用范围广,模型算法一体化,方便编程。 ?由于没有统一的标准模型,使得动态规划的应用

难度增加 。
水电与数字化工程学院 莫 莉

前节回顾
动态规划根据多阶段决策过程的时间参量类
型可以分为离散型决策过程和连续型决策过程;

根据决策过程的演变性态又可以分为确定型决策
过程和随机型过程。组合起来有下列类型:

离散确定型、离散随机型、连续确定型、连
续随机型。本章主要介绍离散确定型决策过程。

水电与数字化工程学院

莫 莉

前节回顾
例. (最短路径问题) 下图表示从起点A到终点E之间各点的距离。 求A到E的最短路径。
B1 4
4

2

1 6 7 2 8

C1

8

6
D1 7 C2 5

10
E

A
2

3

B2
4

3 1
C3 1 6 B3 7 5

D2

6

3

水电与数字化工程学院

B4

莫 莉

前节回顾
用穷举法的计算量:

如果从A到E的站点有k个,除A、E之外每站有3个位
置则总共有3k条路径; 计算各路径长度总共要进行3k-1 次比较。随着 k 的值增加时,需要进行的加法和比较的 次数将迅速增加; 例如当 k=20时,加法次数为 4.2550833966227×1015 次,比较 1.3726075472977×1014 次。若用1亿次/秒的计 算机计算需要约508天。

水电与数字化工程学院

莫 莉

前节回顾
基本概念
? 状态(每阶段初始的出发点)
? 最短路问题中,各个节点就是状态 ? 生产库存问题中,库存量是状态 ? 物资分配问题中,剩余的物资量是状态

? 控制变量(决策变量)
? 最短路问题中,走哪条路 ? 生产库存问题中,各阶段的产品生产量 ? 物资分配问题中,分配给每个地区的物资量

? 阶段的编号与递推的方向
? 一般采用反向递推,所以阶段的编号也是逆向的 ? 当然也可以正向递推
水电与数字化工程学院 莫 莉

作业
参照公共邮箱的电子版教材中的页码,完成第3次、第4次作 业,于2015年6月17日完成。
序号
第1次作业 第2次作业

课后作业

页码、题号

备注
图解法,基解,单纯形法 大 M法
对偶问题,对偶问题性质求最优解 对偶单纯形法 判定凸规划,斐波那契法,0.618法 最速下降法,共轭梯度法 变尺度法,Kuhn-Tucker条件 SUMT外点法,SUMT内点法 最短路线
莫 莉

P44-1.1(1),1.3,1.4 P45-1.6(1)(2)
P74-2.3(1)(2),2.7 P75-2.8 P187-7.3,7.4,7.5 P187-7.7,7.13 P188-7.13(3),7.17 P189-7.21,7.23 P211-8.2,8.3

第3次作业 第4次作业

水电与数字化工程学院

前节回顾


? 引例


多种应用


? 引例



? 动态规划基本概念
? 离散动态规划

? 动态规划优劣
? 经营管理中的应用

水电与数字化工程学院

莫 莉

第三章 动态规划
1 2 基本概念介绍 离散动态规划★

3

连续动态规划

4

在水库调度中的应用

水电与数字化工程学院

莫 莉

2.1 引例
例某警卫部门共有12支巡逻队,负责4个要害部位 A, B ,C , D
的警卫巡逻。对每个部位可分别派出2~4支巡逻队,并且派出

巡逻队数的不同,各部位预期在一段时期内可能造成的损失有
差别,具体数字见下表。问该警卫部门应往各部位分别派多少

巡逻队,使总的预期损失为最小。
部位 预期损失 巡逻队数 2 3 4 A 18 14 10 B 38 35 31 C 24 22 21 D 34 31 25

水电与数字化工程学院

莫 莉

2.1 引例
解: 阶段数:把12支巡逻队往各部 位派遣看成依次分四个阶段。
部位 预期损失 巡逻队数 2 3 4 A 18 14 10 B 38 35 31 C 24 22 21 D 34 31 25

状态变量:xk表示每个阶段初
拥有的可派遣的巡逻队数。 集合为:

决策变量:uk表示对各部位派出的巡逻队数,各阶段允许的决策

U k ( xk ) ? {uk 2 ? uk ? 4}, (k ? 1,2,3,4) 状态转移方程:xk+1= xk-uk
若用 vk ( xk , uk ) 表示 k 阶段派出的巡逻队数为u k 时,该阶段的部位的预 期损失值,
水电与数字化工程学院 莫 莉

2.1 引例
设用 f k ( xk ) 表示 k阶段状态为 x k,以此出发采用最优子策略到过
程结束时的预期损失值,则有:
f k ( xk ) ? min {vk ( xk , uk ) ? f k ?1 ( xk ?1 )}
u k ?U k ( xk )

k ? 4,则上式可写为: 采用后向算法,先考虑给 D 部位派巡逻队,
f 4 ( x4 ) ?
f 5 ( x5 ) ? 0
f 4 ( x4 ) ?
水电与数字化工程学院
u 4 ?U 4 ( x4 )

min

?v4 ( x4 , u4 ) ?

f 5 ( x5 )?

u 4 ?U 4 ( x4

min

? v4 ( x4 , u4 )? )
莫 莉

f 4 ( x4 ) ?

u 4 ?U 4 ( x4

min

?v4 ( x4 , u4 )? )

部位 预期损失 巡逻队数 2 3 4

A 18 14 10

2.1 引例 B C D
38 35 31 24 22 21 34 31 25

因 U 4 ( x4 ) ? ?2,3,4?,又 x 4的可能值为 2 ? x 4 ? 6,故由已知数据,可得

下表的结果。 再联合考虑对 C 、 D 两个部位派巡逻队,即 k ? 3。这时有
f 3 ( x3 ) ? min
u3?U 3 ( x3 )

?v3 ( x3 , u3 ) ?
u3

f 4 ( x4 )?

因有 U 3 ( x3 ) ? ?2,3,4?,又 4 ? x3 ? 8,故可得到下表的计算结果。
u4 x4 2 v4(x4, u4) 3 4 f 4 (x4) u4
*

v3(x3, u3) + f 4 (x3-u3)
2 24+34 24+31 24+25 24+25 24+25 3 4

x3 4 5 6 7 8

f 3 (x3) 58 55 49 47 46

u3 * 2 2 2 3 莉 4

2 3 4 5 6

34 34 34 31 31 34 31 25 25 34 31 25 25 34水电与数字化工程学院 31 25 25

2 3 4 4 4

22+34 22+31 21+34 22+25 21+31 22+25 21+25



部位 预期损失 巡逻队数 2 3 4

A B

C

D

x3
4 5 6 7 8

u 3 v3 ( x3 , u3 ) ? f 4 ( x3 ? u3 )
2
24+34 24+31 24+25 24+25 24+25

3

4

? u f 3 ( x引例 3 2.1 3)

18 38 24 34 14 35 22 31 10 31 21 25

22+34 22+31 21+34 22+25 21+31 22+25 21+25

58 55 49 47 46

2 2 2 3 4

下面考虑对 B 、 C、D 三个部位派巡逻队,即 k ? 2,这时有
f 2 ( x2 ) ? min
u 2 ?U 2 ( x2 )

?v2 ( x2 , u2 ) ? f 3 ( x3 )?

同样有 U 2 ( x2 ) ? ?2,3,4? ,又 8 ? x2 ? 10 ,故可得到下表的计算结果。
u2 x2

v2(x2, u2)+f 3 (x2-u2)
2 3 4

f 2 (x2) u2* 87 84 80 2 3 4

8 38+49 35+55 31+58 9 38+47 35+49 31+55 水电与数字化工程学院 10 38+46 35+47 31+49

莫 莉

部位 预期损失 巡逻队数 2 3 4

A B

C

D

u2 x2
8 9 10

v2(x2, u2)+f 3 (x2-u2)

2.1 引例
4
f 2 (x2) u2* 87 84 80 2 3 4

2

3

18 38 24 34 14 35 22 31 10 31 21 25

38+49 35+55 31+58 38+47 35+49 31+55 38+46 35+47 31+49

最后考虑对 A, B, C , D 四个部位 派巡逻队,即 k ? 1,有
f1 ( x1 ) ? min
1 1

u1 x1

v1(x1, u1)+f 2 (x1-u1)

?v1 ( x1 , u1 ) ? u ?U ( x )
1

f 2 ( x2 )?

2 18+80

3 14+84

4 10+87

f 1 (x1)

u1 *

12

97

4

因 x1 ? 12,又 U 1 ( x1 ) ? ?2,3,4? , 计算得右表。
水电与数字化工程学院 莫 莉

u4

v4 ( x 4 , u 4 )
2 3 31 31 31 31 4 34 34 34 34 34

x4
2 3 4 5 6

? f 4 ( x4 ) u 4

x3
4 5 6 7 8

u3

v3 ( x3 , u3 ) ? f 4 ( x3 ? u3 )
2 3 4

2.1 引例
58 55 49 47 46 2 2 2 3 4

f 3 ( x3 )

? u3

25 25 25

34 31 25 25 25

2 3 4 4 4

24+34 24+31 24+25 24+25 24+25

22+34 22+31 21+34 22+25 21+31 22+25 21+25

u2
x2
8 9 10

? u ?4 因此 ,故 x2 ? 12 ? 4 ? 8 , 1 v2 ( x2 , u2 ) ? f3 ( x2 ? u2 ) ? f 2 ( x2 ) u 2 ? u ?2 所以 ,因而 x3 ? 8 ? 2 ? 6, 2 2 3 4 ? u ? 2,推算得 再由前面表知 3 38+49 35+55 31+58 87 2

38+47 35+49 31+55 38+46 35+47 31+49

84 80

3 4

x4 ? 6 ? 2 ? 4

因此该警卫部门的派巡逻队的 最优策略为:A部位4支, B 部位2支, 部位 C部位2支,D 4支,总预期损失为97莫 单位。 莉

u1

v1 ( x1 , u1 ) ? f 2 ( x1 ? u1 )
2 3 4
水电与数字化工程学院 18+80 14+84 10+87

x1
12

f1 ( x1 ) u1?
97 4

2.2 动态规划的特点
动态规划与静态规划的关系
动态规划与静态规划(线性与非线性规划等)研究的对象本质上 都是在若干约束条件下的函数极值问题,两种规划在很多情况下

原则上可以相互转换。
1.动态规划可以看作求决策 u1 , u2 ,?, un 使指标函数 V1n ( x1 , u1 , x2 ,?, xn ) 达到最优(最大或最小)的极值问题,状态转移方程、端点条件 以及允许状态集、允许决策集等是约束条件,原则上可以用非 线性规划方法求解。 2. 一些静态规划只要适当引入阶段变量、状态、决策等就可以 用动态规划方法求解。
水电与数字化工程学院 莫 莉

2.2 动态规划的特点
动态规划的优越性 与静态规划相比,动态规划的优越性在于:

(1)能够得到全局最优解。由于约束条件确定的约束集合往往 很复杂,即使指标函数较简单,用非线性规划方法也很难求出 全局最优解,而动态规划方法把全过程化为一系列结构相似的 子问题,每个子问题的变量个数大大减少,约束集合也简单得 多,易于得到全局最优解。特别是对于约束集合、状态转移和 指标函数不能用分析形式给出的优化问题,可以对每个子过程 用枚举法求解,而约束条件越多,决策的搜索范围越小,求解 也越容易。对于这类问题,动态规划通常是求全局最优解的唯 一方法。
水电与数字化工程学院 莫 莉

2.2 动态规划的特点
⑵ 可以得到一族最优解。与非线性规划只能得到全过程的一个 最优解不同,动态规划得到的是全过程及所有后部子过程的 各个状态的一族最优解。有些实际的问题需要这样的解族, 即使不需要,它们在分析最优策略和最优值对于状态的稳定 性时也是很有用的。当最优策略由于某种原因不能实现时, 这样的解族可以用来寻找次优策略。 ⑶ 能够利用经验提高求解效率。如果实际问题本身就是动态的,

由于动态规划方法反映了过程逐段演变的前后联系和动态特 征,在计算中可以利用实际知识和经验提高求解效率。如在 策略迭代法中,实际经验能够帮助寻找较好的初始策略,提 高收敛速度。
水电与数字化工程学院 莫 莉

2.2 动态规划的特点
动态规划的缺点: (1)没有统一的标准模型,也没有构造模型的通用方法,甚至还 没有判断一个问题能否构造动态规划的准则。这样就只能对 每类问题进行具体分析,构造具体的模型。对于较复杂的问 题在选择状态、决策、确定状态转移规律等方面需要丰富的 想象力和灵活的技巧性,这就带来了应用上的局限性。 (2)用数值方法求解时存在维数灾。若一维状态变量有 m 个取 值,那么对于 n维问题,状态 xk 就有 m n个值,对于每个 状态值都要计算、存储函数 f k ( xk ),对于n稍大(即使 n ? 3 )的实际问题的计算往往是不现实的。目前还没有克服维 数灾的有效的一般方法。
水电与数字化工程学院 莫 莉

2.3 在经营管理中的应用
1、资源分配问题
设有某种原料,总数量为a,用于生产n种产品,若分 配数量ui用于生产第i种产品,其收益g(ui)。问应如何分配 原料,才能使生产n种产品的总收入最大? 设状态变量xk表示分配用于生产第k种产品至第n种产 品的原料数量。

决策变量uk表示分配给生产第k种产品的原料数。 状态转移方程为 xk+1=xk-uk
允许决策集合为
水电与数字化工程学院

Uk(xk)=﹛uk︳0≤uk≤xk﹜
莫 莉

2.3 在经营管理中的应用
设状态变量xk表示分配用于生产第k种产品至第n种产 品的原料数量。 决策变量uk表示分配给生产第k种产品的原料数。 状态转移方程为 允许决策集合为 xk+1=xk-uk Uk(xk)=﹛uk︳0≤uk≤xk﹜

令最优值函数 f k ( xk ) 表示以数量为xk的原料分配给第k种产
品至第n种产品所得到的最大总收入。

则动态规划的递推关系式为:
? f k ( x k ) ? max{ g k ( uk ) ? f k ?1 ( x k ? uk )}, k ? 1,2, ? , n ? ? f n?1 ( xn?1 ) ? 0
水电与数字化工程学院

莫 莉

2.3 在经营管理中的应用
例 某公司拟将5台设备分配给所需的甲、乙、丙三个工厂, 各工厂获得设备后获利润见下表。问:这5台设备如何分配给 各工厂,才能使公司得到的利润最大。 单位:万元
工厂 获利 甲 0 乙 0 丙 0

设备台数
0

1
2 3

3
7 9

5
10 11

4
6 11

4
5
水电与数字化工程学院

12
13

11
11

12
12
莫 莉

2.3 在经营管理中的应用
解:将问题按工厂分为三个阶段,甲、乙、丙三个 工厂分别编号为1、2、3。 设xk表示为分配给第k个工厂至第3个工厂的设备台数

uk表示为分配给第k个工厂的设备台数,则 xk+1=xk-uk 为状态转移方程。
Pk(uk)表示为uk台设备分配到第k个工厂所获利润值。 fk(xk)表示为xk台设备分配给第k个工厂至第3个工厂 时所得到的最大利润值。 则有递推关系式为
? f k ( xk ) ? max[ Pk (uk ) ? f k ?1 ( xk ? uk )], k ? 3,2,1 ? 0 ? u k ? xk ? ? f (x ) ? 0 莫 莉 4 水电与数字化工程学院? 4

工厂 获利

2.3 在经营管理中的应用
甲 乙 丙

3 9 11 11 第三阶段:设将 x3台设备( x3=0,1,2,3,4,5 )全部分配 4 12 11 12 f 3 ( x311 ) ? max[ P 5 13 12 给工厂丙时,最大获利值为 3 (u3 )] u ?x
3 3

f k ( x k ) ? max[ Pk ( uk ) ? f k ?1 ( x k ? uk )], k ? 3,2,1 ? 设备台数 0 0 0 0 ? 0 ? uk 3? x k ? 1 5 4 ? f ( x ) ? 20 7 10 6 ? 4 4

u3
x3
0 1 2 3 4 5
水电与数字化工程学院

P3(u3)
0 1 2 3 4 5

f3(x3) u3*

0

0

0

4

4

1

6
11

6
12

2

11 3

12

12 4 12 5

莫 莉

工厂 获利 设备台数 0 1 3 4 5

甲 0 3 9

乙 0 5

0 1 2 3 4 5 2.3 在经营管理中的应用
丙 0 4

u3 x3
0 1 2 3 5

P3(u3)

f3(x3) u3* 0 4 6 11 12 12 0 1 2 3 4 5

0 4 6 11 12 12 f2(x2) u2* 4 5

第二阶段:最大获利值为 2 7 10 6
11 11 11 12 13 11 u 2 12 12

f 2 ( x2 ) ? max[ P2 (u2 )4? f 3 ( x2 ? u2 )]
u2 x2
0
1 2 3 0 1 P2(u2)+f3(x2-u2) 2 3

4
5

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

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

0 5 10
14 16

0 1 2
2 1,2 2
莫 莉

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

水电与数字化工程学院

工厂 获利 设备台数 0 1 2 3 4 5







u2

x2
0
1 2 3 4 5

2.3 在经营管理中的应用
P2(u2)+f3(x2-u2) 2 3 f2(x2) u2* 0 1 4 5

0 3 7 9 12 13

0 5 10 11 11 11

0 4 6 11 12 12

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

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

0 5 10 14 16

0 1 2 2 1,2
2

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

第一阶段:最优获利值为 f1 (5) ? max[ P1 ( u1 ) ? f 2 (5 ? u1 )]

其中x1=5,u1=0,1,2,3,4,5。
u1 x1
5 0 1 P1(u1)+f2(5-u1) 2 3 4 5 f1(5) u1 *

0+21

3+16

7+14

9+10

12+5

13+0

21

0,2
莫 莉

水电与数字化工程学院

u3 x3
0 1 2

P3(u3)

u2 f3(x3) u3* P2(u2)+f3(x2-u2)
4 x2 5
0 0 1 5+0 2 5+4 10+0 3 5+6 10+4 4 5+11 10+6 5

0
0

1
4

2

3

0 1 2 3 4 5 2.3 在经营管理中的应用

f2(x2) u2*

6

3
4 5

0 0 4 1 0+4 6 2 0+6 11 11 0+11 12 3 12 4 12 0+12 12 0+12 5
0 1
3+16

0 5 10

0 1 2
2 1,2 2

11+0 14 11+4 11+0 16 5+12 10+11 11+6 11+4 11+0 21
3
9+10

u1 x1
5 0+21

P1(u1)+f2(5-u1)

2
7+14

4
12+5

5
13+0

f1(5) 21

u1 * 0,2

然后按计算表格的顺序反推算,可知最优分配方案有两个:

(1)由于u1*=0,根据x2=x1 - u1*=5 - 0=5,查表3 知u2*=2;由于x3=x2 - u2*=5-2= 3,故u3*=x3=3。
即甲厂分配0台,乙厂分配2台,丙厂分配3台。
水电与数字化工程学院 莫 莉

u3 x3
0 1 2

P3(u3)

u2 f3(x3) u3* P2(u2)+f3(x2-u2)
4 x2 5
0 0 1 5+0 2 5+4 10+0 3 5+6 10+4 4 5+11 10+6 5

0
0

1
4

2

3

0 1 2 3 4 5 2.3 在经营管理中的应用

f2(x2) u2*

6

3
4 5

0 0 4 1 0+4 6 2 0+6 11 11 0+11 12 3 12 4 12 0+12 12 0+12 5
0 1
3+16

0 5 10

0 1 2
2 1,2 2

11+0 14 11+4 11+0 16 5+12 10+11 11+6 11+4 11+0 21
3
9+10

u1 x1
5 0+21

P1(u1)+f2(5-u1)

2
7+14

4
12+5

5
13+0

f1(5) 21

u1 * 0,2

(2)由于u1*=2,根据x2=x1-u1*=5-2= 3,查表3知 u2*=2,由于x3=x2 - u2*=3 - 2=1,故u3*=x3=1。
即甲厂分配2台,乙厂分配2台,丙厂分配1台。 上述两个分配方案得的总获利均为21万元。
水电与数字化工程学院

莫 莉

第三章 动态规划
1 2 基本概念介绍 离散动态规划

3

连续动态规划★

4

在水库调度中的应用

水电与数字化工程学院

莫 莉

3.1 连续动态规划的概念
在资源分配问题中,还有一种要考虑资源回收 利用的问题,这里决策变量为连续值,故称为资源 连续分配问题。 这类问题可叙述如下: 设某种资源数量为x1,可投入A和B两种生产, 第一年投入A种生产的数量为u1,则余下的投入B种 生产的数量为x1-u1,收入为g(u1)+h(x1-u1),其中 g(u)和h(u)为已知函数,且g(0)=h(0)=0。年终时两 种资源还可以回收,再投入A、B两种生产。

设年回收率分别为0<a<1和0<b<1,则在第一 年生产后,回收的资源量合计为x2=au1+b(x1-u1)。
水电与数字化工程学院

莫 莉

3.1 连续动态规划的概念
设年回收率分别为0<a<1和0<b<1,则在第一 年生产后,回收的资源量合计为x2=au1+b(x1-u1)。 第二年再将资源数量x2中的u2和x2-u2分别再 投入A、B两种生产,则第二年又可得到收入为 g(u2)+h(x2-u2)。如此继续进行n年,应当如何决 定每年投入A生产的资源数量u1,u2, …,un,才能 使总的收入最大。

水电与数字化工程学院

莫 莉

3.2 例题
例 . 机器负荷分配问题
某厂新购某种新机床125台,据估计,这种机床 5年后将被其它设备所代替。此类机床如在高负荷状 态下工作,每台年创利润10万元,年损坏率为1/2; 如在低负荷状态下工作,每台年创利润6万元,年损 坏率为1/5。问应如何安排这些车床的生产负荷,才 能使5年内获得最大的利润?

解:很自然想到将问题划分为5个阶段,每一年为 一个阶段。
水电与数字化工程学院 莫 莉

3.2 例题
状态变量xk表示第k年年初的完好机床台数。决 策变量uk表示第k年安排高负荷状态下工作的机床台 数,则低负荷状态下工作的机床台数为xk-uk台, 则状态转移方程为
xk ?1 ? ? 1? 1? 4 3 ? ? 1 ? ? uk ? ? 1 ? ? ( xk ? uk ) ? xk ? uk 2? 5? 5 10 ? ?

第k年可得利润为 10uk+6(xk-uk)=4uk+6xk 最优值函数fk(xk)表示由资源xk出发,从第k年开 始到第5年结束时机床所创造利润的最大值,因而 有递推关系式:
水电与数字化工程学院 莫 莉

3.2 例题
最优值函数fk(xk)表示由资源xk出发,从第k年开始到 第5年结束时机床所创造利润的最大值,因而有递 推关系式:
? ? f 6 ( x6 ) ? 0 ? f ( x ) ? max {4u ? 6 x ? f ( x )}, k ? 5,4,3,2,1 k k k k k ?1 k ?1 ? 0 ?u k ? xk ? f 5 ( x5 ) ? max (4u5 ? 6 x5 ) 当k=5时,有
0?u5 ? x5

因4u5+6x5是u5的单调上升函数,故得最大解
[4u4 ? 6 x4 ? f 5 ( x5 )] 当k=4时, f 4 ( x4 ) ? 0max ?u ? x
4 4

u5=x5,f5(x5)=10x5

? max [5u4 ? 6 x4 ? 10 x5 ]
水电与数字化工程学院

0?u 4 ? x4

莫 莉

3.2 例题
当k=5时,有
f 5 ( x5 ) ? max (4u5 ? 6 x5 )
0? u5 ? x5

u5*=x5,f5(x5)=10x5
当k=4时,
f 4 ( x4 ) ? max [4u4 ? 6 x4 ? f 5 ( x5 )]
0 ? u4 ? x4

? max [4u4 ? 6 x4 ? 10 x5 ]
0 ? u4 ? x4

将状态转移函数 x5 ?

4 3 x4 ? u4代入得 5 10

f 4 ( x4 ) ? max (14 x4 ? u4 )
0? u4 ? x4

因14x4+u4是u4的单调上升函数,得u4*=x4, 且 f4(x4)=15x4
水电与数字化工程学院 莫 莉

3.2 例题
当k=5时,有
f 5 ( x5 ) ? max (4u5 ? 6 x5 )
0? u5 ? x5

u5*=x5,f5(x5)=10x5
(14 x4 ? u4 ) 当k=4时, f 4 ( x4 ) ? 0max ?u ? x
4 4

u4*=x4,且 f4(x4)=15x4
[4u3 ? 6 x3 ? f 4 ( x4 )] 当k=3时, f 3 ( x3 ) ? 0max ?u ? x
3 3

? max (4u3 ? 6 x3 ? 15 x4 )

将状态转移函数

4 3 x4 ? x 3 ? u3 5 10
0 ? u3 ? x 3

0? u3 ? x 3

代入得
1 u3 ) 2

f 3 ( x 3 ) ? max (18 x 3 ?
水电与数字化工程学院

因18x3-0.5u3是u3的单调下降函数,得u3*=0,且f3(x3)=18x3
莫 莉

3.2 例题
当k=5时 u5*=x5,f5(x5)=10x5

当k=4时
当k=3时

u4*=x4,且 f4(x4)=15x4
u3*=0,且 f3(x3)=18x3

同理,可求得当k=2时,u2*=0,且f2(x2)=20.4x2
当k=1时,u1*=0,且f1(x1)=22.32x1 将x1=125代入得 f1(125)=2790 由u1*=0,x1=125,代入 最优安排可排成下表:
水电与数字化工程学院 莫 莉

4 3 x 2 ? x1 ? u1,得x2=100, 5 10 4 4 4 3 类似可得 x 3 ? x 2 ? 80 , , x4 ? x 3 ? 64 x5 ? x4 ? u4 ? 32 5 10 5 5

3.2 例题
4 3 由u1*=0,x1=125,代入 x2 ? x1 ? u1,得x2=100, 5 10
4 4 4 类似可得 x 3 ? x 2 ? 80, x5 ? x4 ? x4 ? x 3 ? 64, 5
3 u4 ? 32 10

5

5

最优安排可排成下表:
年初完好台数 第一年 x1=125 高负荷工作台数 低负荷工作台数 u1=0 x1-u1=125

第二年
第三年 第四年

x2=100
x3=80 x4=64

u2 =0
u3 =0 u4=64

x2-u2 =100
x3-u3 =80 x4-u4 =0

第五年

x5=32

u5=32

x5-u5 =0
莫 莉

此时总利润为2790万元。
水电与数字化工程学院


相关文章:
15《运筹学》(第四版)连续动态规划_图文.pdf
15《运筹学》(第四版)连续动态规划_工学_高等教育_教育专区。对应教材为《运筹
14《运筹学》(第四版)动态规划基本概念_图文.pdf
14《运筹学》(第四版)动态规划基本概念_工学_高等教育_教育专区。对应教材为...4 15 17 决策变量:用yk和zk分别表示第k月的订 货量和销售量,H=1000为仓库...
天大15秋《运筹学》在线作业一满分答案.doc
天大15《运筹学》在线作业一满分答案_教育学_高等教育_教育专区。《运筹学》...2.5 连续动态规划常用求解方法是() 表格方式 公式递推 决策树 多阶段决策 ...
运筹学-动态规划-15,16_图文.ppt
运筹学-动态规划-15,16_经济学_高等教育_教育专区。运筹学-动态规划 第五章 动态规划 ? §5.1 动态规划的基本概念 §5.2 动态规划的模型、基本原理 §5.3...
天大15秋《运筹学》在线作业一100分答案.doc
天大15《运筹学》在线作业一100分答案_电大_成人教育_教育专区。《运筹学》...连续动态规划常用求解方法是() A. 表格方式 B. 公式递推 C. 决策树 D....
天大15秋季《运筹学》在线作业一答案.doc
天大15秋季《运筹学》在线作业一答案 - 《运筹学》在线作业一 一、单选题(共 40 道试题,共 100 分。 ) 1. 运筹学为管理人员制定决策提供了() . 定性基础...
天大15秋季《运筹学》在线作业一 答案.doc
天大15秋季《运筹学》在线作业一 答案 - 谋学网 www.mouxue.com 《运筹学》在线作业一 一、单选题(共 40 道试题,共 100 分。 ) 1. 运筹学为管理人员制定...
运筹学15_动态规划III_图文.pdf
动态规划(三)李田 华东理工大学商学院 2014年春季学期 提纲 ? 可靠性问题 ? ...运筹学-动态规划(三)(名... 27页 免费 15《运筹学》(第四版)连... ...
01《运筹学》(第四版)线性规划模型_图文.ppt
01《运筹学》(第四版)线性规划模型_工学_高等教育...动态规划应用 水电与数字化工程学院 莫莉 1.1 线性...15页 1下载券 运筹学 线性规划 数学模... 31页...
2014-2015-2《运筹学》复习提纲(第四版).pdf
2014-2015-2《运筹学》复习提纲(第四版) - 2014-2015-2《运筹学》复习提纲 1. P18 线性规划问题解的几种情况:唯一最优解、无穷多最优解、无界解、无可行...
天大15春《运筹学》在线作业一满分答案.doc
天大15《运筹学》在线作业一满分答案 - 《运筹学》在线作业一 1. 动态规划递推求解的理论基础是()最优性原理 A. Saaty B. Carners C. Bellman D. Coope...
08《运筹学》(第四版)非线性规划最优性条件_图文.pdf
08《运筹学》(第四版)非线性规划最优性条件_工学_高等教育_教育专区。对应...线性规划模型 ? 线性规划解 非线性规划 ? 最优性条件 ? 一维搜索 动态规划 ...
《管理运筹学》案例演示(动态规划)_图文.ppt
《管理运筹学》案例演示(动态规划) - 例.(生产与库存问题)某电视机厂为生产电
《管理运筹学》第四版课后习题解析(下).doc
《管理运筹学》第四版课后习题解析(下)_管理学_...第 10 章动态规划 1.解: 最优解为 A—B2—C1...[4,6] 所需人数 16 15 14 12 时间段 [6,7]...
大工15春《运筹学》在线作业3满分答案.doc
大工15《运筹学》在线作业3满分答案 - 大工 15《运筹学》在线作业 3 一、单选题(共 5 道试题,共 40 分。 ) 1. 假设对于一个动态规划问题,应用顺推...
大连理工大学15秋《运筹学》在线作业1满分答案.doc
大连理工大学15《运筹学》在线作业1满分答案 - 大工 15《运筹学》在线作业 1 满分答案 一、单选题(共 5 道试题,共 40 分。 ) 1. 数学规划模型的三...
运筹学大纲(13、14级使用)2014.9.doc
2、 《运筹学》教材编写组.运筹学(第版).北京:清华大学出版社,2005 年。...15 单纯形法 运输问题 整数规划 目标规划 动态规划(经济统计学、物流管理上到...
运筹学-第3版-课件-动态规划例题_图文.ppt
运筹学-第3版-课件-动态规划例题_理学_高等教育_教育专区。8.1 用动态规划...高级科学家的 人数 小 1 组 2 3 0 1 2 解 0.40 0.20 0.15 0.60 ...
《运筹学》7动态规划_图文.ppt
《运筹学》7动态规划 - 运筹学课件 运筹帷幄之中 Dynamic Programming 决胜 动态规划 千里之外第1页 综 述 1951 年,R ...
运筹学 动态规划应用.ppt
运筹学 动态规划应用_数学_自然科学_专业资料。第七章 动态规划动态规划问题的...近似解 作业第四版: P223 题7.9(1) P225 题7.15 第三版: P229 题7....
更多相关文章: