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

动态规划(运筹学)


第六章 动态规划

第一节:现实中的动态规划问题 第二节:动态规划基本概念

第三节:动态规划的基本方法
第四节:动态规划的应用

多式联运是一种以实现货物整体运输最优化为目标的联合运输组织 形式,它以集装箱为媒介,把水路、公路、以及铁路等多种运输方式有 机地结合起来,构筑连续的、综合性的一体化货物运输网络。在集装箱 多式联运系统中,各种运输方式的组织优化直接关系到货物运输的费用 、时间和运输质量。 通常情况下,多式联运组织优化问题具有如下几个方面的特点:
?

? ?

? ? ?

一、两地之间集装箱货物运输有三种可选的运输方式(公路、铁路、水 路运输) 二、集装箱的中转过程有很好的衔接 三、集装箱运量不可以分割,在某两个特定的地点之间,只能选择一种 运输方式 四、集装箱运量对运输价格及运输时间没有明显的影响 五、集装箱运输能力几乎不受限制 六、运输时间须控制在合理范围之内(如集装箱干线船的班期)。

ZH物流公司是一家大型的集装箱多式联运经营企业,在成都设有内 陆集装箱货运站(CFS),经营成都——上海间集装箱货物运输服务,其 多式联运通道的主要节点城市为南京与郑州。现有一个货主需要将2个20 英尺的集装箱从成都运往上海,运输路线为成都-郑州-南京-上海,要求 在货物起运后25-30小时之内到达目的地。

如何制定 运输方式 组合优化 方案使在 满足客户 需求的条 件下降低 集装箱运 输总成本?

成都-郑州 公路运输 铁路运输 水路运输 1474 1353 /

郑州-南京 704 695 / 公路运输 100 公路运输 3

南京-上海 349 303 392 水路运输 36 水路运输 18

运输方式 铁路运输 运 载 工 具 速 70 度(km/h) 运输方式 铁路运输

中转时间(h) 7

多阶段决策问题
阶段、决策、策略

动态规划的基本特性(多阶段决策问题的基本特性) Q = S1 S2



Sk

Sk+1 S’k+1




Sn S’n

T

反证法容易得证。

若 {S1 , … , Sk , Sk+1 , … , Sn , T} 全程最优 则 {Sk+1 , … , Sn , T} 子程最优
5

动态规划方法的基本思路
最短路问题

—— 标号法 11
7 A1 4 6 73 A2 2 4 8 41 A 5
3

4
1 B1 4 7 6 B2 3 63 3 B3 2 3 3 C1 3

11 2 4 Q 3

0
T

4
C2

4

阶段

1

4

动态规划的基本概念
一、阶段
把所研究的问题恰当的划分成若干个相互联系的阶段。用 k = 1,2,…,n 表示阶段序号,称为阶段变量。

二、状态
状态表示某段的初始条件。用sk表示第k段的状态,称为第k段 sk∈Sk 状态变量。

三、决策
是指人们对某一阶段活动中各种不同的行为或方案或途径等的 一种选择。 用xk表示第k段的决策,称为第k段决策变量。由于决策随状态 而变,所以决策变量xk是状态变量sk的函数,记为 xk= xk(sk)

xk ? sk ? ? Dk ? sk ?

k阶段的允许决策集合

四、状态转移方程 sk+1与sk,xk之间必须能够建立一种明确的数量对应关系,记为 Tk(sk,xk), 即有 sk+1 = Tk(sk,xk)
这种明确的数量关系称为状态转移方程。

五、策略
由各阶段决策xk构成的决策序列,称为全过程策略,简称策略,记为

p 1 ( s1 ) , 有


p1(s1) = { x1(s1),x2(s2),… ,xn(sn)} ∈P1 pk(sk) = { xk(sk),xk+1(sk+1),… ,xn(sn)} ∈Pk

称为第k子过程策略,简称子策略。
8

六、指标函数 (1) 阶段指标函数 用vk(sk,xk)表示第k段处于sk状态且所作决策为xk∈P1 时的指标,则它就是第k段指标函数,简记为vk。 (2) 过程指标函数 用fk(sk,xk)表示第k子过程的指标函数。 它是各vk的累积效应。 常用函数:

积函数
和函数

fk(sk,xk) = ? vi(si,xi)
i= k

n n

fk(sk,xk) = ?vi(si,xi)
i= k
9

七、最优解 (1) 最优指标函数 fk*(sk) = opt {fk(sk, pk(sk))}, k=1,2,…,n pk∈Pk (2) 最优策略 能使上式成立的子策略pk*称为最优子策略,记为 pk* (sk) = { xk*(sk),… ,xn*(sn)} 特别当k=1时,称为最优策略,记为 p1* (s1) = { x1*(s1),… ,xk*(sk),… ,xn*(sn)}

(3) 最优决策
构成最优策略的决策称为最优决策,记为xk*。 (4) 最优值:最优策略对应的最优指标 f *1

一、最优化原理 作为一个全过程最优策略具有这样的性质: 无论过去的状态和决策如何,对前面所形成的状态而言, 余下的诸决策必构成最优策略。 二、函数基本方程



f*n+1(sn+1) = 0 f*k(sk) = opt {vk(sk,xk)+fk+1*(sk+1)}
xk∈Xk



f*

=1 f*k(sk) = opt {vk(sk,xk) ×fk+1*(sk+1)}
xk∈Xk

n+1(sn+1)

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

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

11

三、基本步骤 1°建立模型
(1) (2) (3) (4) (5) (6) 划分阶段,设定 k 设定状态变量 sk 设定决策变量 xk 建立状态转移方程 确定指标函数 vk,fk* 建立函数基本方程

2°递推(逆推)求解 3°得出(顺推)结论

12

20
c 19 s 2 14 b 19

8

12
14

d 7 e 12 f 9

3

5 g

6
10 4

5
t

5

6
5 h 8 10

1

a

13 12 11 k=2

2

2
k=4

d1(s)=b d2(b)=d d3(d)=g

k=1

d1(s)=b

k=3 ? ?3 ? 5 ? ?d3 ? d , g ? ? f 4 ? g ? ? ? f3 ? d ? ? min ? ? min ? ? ? ?9 ? 2? ?d3 ? d , h ? ? f 4 ? h ? ? ? ?
=8

f4 ? g ? =5
d4 ? g ? ? t

d4(g)=t

最优策略: p1(s1)={s,b,d,g,t}
最优值: f*1(s)=19

d3 ? d ? ? g

W Vii

今有一辆载货量为6t的载货车,现有3种需要运输的货 物,均可用此载货车装运。若已知这4种货物每一种的质量 和运输例如表6-4所示。在载货量许可的条件下,每车装载 每一种货物的件数不限,应如何搭配这四种货物,才能使 每车装载货物的利润最大?
货物种类
1 2

每件质量(t) 每件运输利润(百元)
2 3 8 13

3

4

18

该问题中的货车可以看做是一个背包,需运载的货物为要 装入背包的物品。 该问题可以看作是一个3阶段的动态规划问题。
14

? ?

步骤1,划分阶段。设每装一种货物为一个阶段,k=1,2,3。 步骤2,确定状态变量。设状态变量为 可用于装载第k种至第n种货物 的装载量。

? ? s1 ? 6 ? ? ? sk ? ?0,1, 2,3, 4,5, 6?? k ? 2,3?
?

?

1) 确定决策变量。设决策变量表示第k种货物的装载件数 ? ? sk ? ? ? ? xk ? Dk ? xk ? ? ?0,1,? , ? ? ? ? k ? 1, 2,3? ? ? ? wk ? ? ? 2) 状态转移方程为

sk ?1 ? sk ? wk xk

? ?

3) 阶段指标函数。第k阶段装载 件货物时所创的利润 。 vk xk 4) 函数的基本方程为
? f k ? sk ? ? opt ? vk xk ? f k ?1 ? sk ? wk xk ? ? ? k ? 1, 2,3? ? ? xk ?Dk ? sk ? ? sk ??0,1,?,6? ? ? f ?s ? ? 0 ? 4 4

w3 ? 4, v3 ? 18

k=3时

s3 ? ?0,1, ? , 6? s ? ? x3 ? ?0,1, ? , 3 ? ? ?0,1 ? 4 ? ? f 3 ? s3 ? ? max ?18 x3 ?
x3 ??0,1 ? s3 ??0,1,?,6?

阶段

x3

18x3
0 0 0 0 0 0 0 0 1 — — — — 18 18 18

s3
k=3 0 1 2 3 4 5 6

f3
0 0 0 0 18 18 18

x

? 3

s4
0 1 2 3 0 1 2

0 0 0 0 1 1 1

w2 ? 3, v2 ? 13

k=2时

s2 ? ?0,1,? , 6? s ? ? x2 ? ?0,1,? , 2 ? ? ?0,1, 2? 3? ? f 2 ? s2 ? ? max ?13 x2 ? f 3 ? s2 ? 3 x2 ? ?
x3 ??0,1,2? s3 ??0,1,?,6?

阶段

x2

13x2 ? f3 ? s2 ? 3x2 ?

s2
k=2

0

1

2

f2
0 0 0 13 18 18 26

? x2

s3
0 1 2 0 4 5 0

0 1 2 3 4 5 6

0+0 0+0 0+0 0+0 0+18 0+18 0+18

— — — 13+0 13+0 13+0 13+0

— — — — — — 26+0

0 0 0 1 0 0 2

w1 ? 2, v1 ? 8

k=1时

s1 ? ?6?

s1 ? ? x1 ? ?0,1,? , ? ? ?0,1, 2,3? 2? ? f1 ? s1 ? ? max ? 8 x1 ? f 2 ? s1 ? 2 x1 ? ?
x1 ??0,1,2,3? s1 ??6?

阶段

x1

8x1 ? f2 ? s1 ? 2x1 ?

s1
k=1 6

0

1

2

3

f1
26

? x1

s2
6,4

0+26 8+18

16+0 24+0

0,1

f1 ? s1 ? =26

阶段

s3

x3

18x3
0
0 0 0 0 0 0 0

1
— — — — 18 18 18

f3
0 0 0 0 18 18 18

x

? 3

s4
0 1 2 3 0 1 2

k=3

0 1 2 3 4 5 6

0 0 0 0 1 1 1

阶段

s2
0 1 2 3 4 5 6 0

x2

13x2 ? f3 ? s2 ? 3x2 ?
0 0+0 0+0 0+0 0+0 0+18 0+18 0+18 1 — — — 13+0 13+0 13+0 13+0
2

k=2

阶段

s1

x1

8x1 ? f2 ? s1 ? 2x1 ?
1 3

2 — — — — — — 26+0

f2
0 0 0 13 18 18 26

? x2
0 0 0 1 0 0 2 ? 1

s3
0 1 2 0 4 5 0

f1
26

x

s2
6,4

k=1

6

0+26 8+18

16+0 24+0

0,1

? ? ? ? ? ? ? 1, x2 ? 0, x3 ?1 x1 ? 0, x2 ? 2, x3 ? 0 x1


相关文章:
运筹学(二)动态规划(1-2014)_图文.ppt
运筹学(二)动态规划(1-2014) - 运筹学(二) 动态规划 动态规划 ? 动态规划是运筹学的一个分支,它是 解决多阶段决策问题的一种数学方法。大 约产生...
15《运筹学》(第四版)连续动态规划_图文.pdf
15《运筹学》(第四版)连续动态规划_工学_高等教育_教育专区。对应教材为《运筹学》(第四版)清华大学出版社,融合多个版本运筹学课件优点。...
运筹学动态规划_图文.ppt
运筹学动态规划 - 动态规划 (Dynamic programming) 动态规
运筹学第八章 动态规划_图文.ppt
运筹学第八章 动态规划 - 第八章 动态规划 8.1 8.2 8.3 8.4 动态规划的研究对象和特点 动态规划的基本概念与最优化原理 动态规划的求解与应用 随机动态规划 ...
运筹学动态规划习题_图文.ppt
运筹学动态规划习题 - 习题三 一、某工厂购进100台机器,准备生产A、B 两种
运筹学5(动态规划)_图文.ppt
运筹学5(动态规划) - 第七章 动态规划 7.1 动态规划问题和基本概念 7.2 动态规划的基本原理 7.3 动态规划的应用 引言 动态规划与多阶段决策: 多阶段决策是...
运筹学动态规划.ppt
运筹学动态规划_数学_自然科学_专业资料。第7章重点: 动态规划 (Dynami
运筹学第五章动态规划.ppt
运筹学第五章动态规划_数学_自然科学_专业资料 暂无评价|0人阅读|0次下载|举报文档 运筹学第五章动态规划_数学_自然科学_专业资料。动态规划 (Dynamic programming...
运筹学7动态规划.ppt
运筹学7动态规划_数学_自然科学_专业资料。运筹学7动态规划 第七 章动态规划 主要内容: §7.1 多阶段决策过程的最优化 §7.2 动态规划的基本概念和基本原理 ...
运筹学动态规划PPT_图文.ppt
运筹学动态规划PPT - 动态规划 (Dynamic programming)
运筹学5(动态规划)_图文.ppt
运筹学5(动态规划) - 第七章 动态规划 7.1 动态规划问题和基本概念 7.2 动态规划的基本原理 7.3 动态规划的应用 引言 动态规划与多阶段决策: 多阶段决策是...
动态规划--运筹学课程设计_图文.doc
动态规划--运筹学课程设计 - 湖南农业大学 综合设计报告 综合设计五 动态规划算法 学生姓名:曾俊扬学号:200840204219 年级专业:2008 级信息...
运筹学---动态规划_图文.ppt
运筹学---动态规划 - 这是关于运筹学里的动态规划的课件ppt... 运筹学---动态规划_理学_高等教育_教育专区。这是关于运筹学里的动态规划的课件ppt 动态...
运筹学 07 动态规划_图文.ppt
运筹学 07 动态规划 - 1 多阶段决策过程的最优化 ? 概述 ? 多阶段决策过程及其最优化 ? 多阶段决策过程举例 ? 动态规划求解的多阶段决策问题的特点 ? 动态...
运筹学动态规划3_背包问题_逆序递推 (1).doc
运筹学动态规划3_背包问题_逆序递推 (1) - 用逆序递推求解背包问题 背包问
运筹学(二)动态的规划(1-2014)_图文.ppt
运筹学(二)动态的规划(1-2014) - 运筹学(二) 动态规划 动态规划 ? 动态规划运筹学的一个分支,它是 解决多阶段决策问题的一种数学方法。大 约...
第三讲 动态规划 高级运筹学课件_图文.ppt
第三讲 动态规划 高级运筹学课件 - 第三讲 动态规划 (Dynamic Pro
动态规划讲解大全(含例题及答案)_图文.pdf
动态规划讲解大全(含例题及答案) - 动态规划讲解大全 动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process) 最优化 的数学方...
动态规划运筹学基础及其应用胡运权第五版_图文.ppt
动态规划运筹学基础及其应用胡运权第五版 - 第九章 动态规划(续) 本章以下内容
运筹学中excel的运用(用excel解决线性规划、动态规划、....pdf
运筹学中excel的运用(用excel解决线性规划、动态规划、排队论等问题) - 1 . 线性规划 2 . 动态规划 3 . 图与网络分析 4 . 决策分析 ...
更多相关文章: