文档介绍：第六章动态规划
第一节:现实中的动态规划问题
第二节:动态规划基本概念
第三节:动态规划的基本方法
第四节:配载问题
第五节:生产和库存控制问题
第六节:资源分配问题
第七节:动态规划应用
多式联运是一种以实现货物整体运输最优化为目标的联合运输组织形式,它以集装箱为媒介,把水路、公路、以及铁路等多种运输方式有机地结合起来,构筑连续的、综合性的一体化货物运输网络。在集装箱多式联运系统中,各种运输方式的组织优化直接关系到货物运输的费用、时间和运输质量。
第一节:现实中的动态规划问题
一、两地之间集装箱货物运输有三种可选的运输方式(公路、铁路、水路运输)
二、集装箱的中转过程有很好的衔接
三、集装箱运量不可以分割,在某两个特定的地点之间,只能选择一种运输方式
四、集装箱运量对运输价格及运输时间没有明显的影响
五、集装箱运输能力几乎不受限制
六、运输时间须控制在合理范围之内(如集装箱干线船的班期)。
通常情况下,多式联运组织优化问题具有如下几个方面的特点:
ZH物流公司是一家大型的集装箱多式联运经营企业,在成都设有内陆集装箱货运站(CFS),经营成都——上海间集装箱货物运输服务,其多式联运通道的主要节点城市为南京与郑州。现有一个货主需要将2个20英尺的集装箱从成都运往上海,运输路线为成都-郑州-南京-上海,要求在货物起运后25-30小时之内到达目的地。
第一节:现实中的动态规划问题
成都-郑州
郑州-南京
南京-上海
公路运输
1474
704
349
铁路运输
1353
695
303
水路运输
/
/
392
运输方式
铁路运输
公路运输
水路运输
运载工具速度(km/h)
70
100
36
运输方式
铁路运输
公路运输
水路运输
中转时间(h)
7
3
18
如何制定运输方式组合优化方案使在满足客户需求的条件下降低集装箱运输总成本?
5
…
S’k+1
…
…
S2
多阶段决策问题
阶段、决策、策略
动态规划的基本特性(多阶段决策问题的基本特性)
第二节动态规划基本概念
Sk
Sk+1
Sn
T
S’n
Q = S1
反证法容易得证。
若{S1 , …, Sk , Sk+1 , …, Sn , T} 全程最优
则{Sk+1 , …, Sn , T} 子程最优
动态规划方法的基本思路
最短路问题
1
2
3
4
3
4
0
4
7
6
11
7
8
11
阶段
A1
2
4
3
7
4
6
3
2
4
4
1
5
1
4
6
3
3
3
3
4
A3
B1
Q
A2
B2
B3
T
C1
C2
——标号法
三、决策
是指人们对某一阶段活动中各种不同的行为或方案或途径等的
一种选择。
用xk表示第k段的决策,称为第k段决策变量。由于决策随状态
而变,所以决策变量xk是状态变量sk的函数,记为 xk= xk(sk)
动态规划的基本概念
一、阶段
把所研究的问题恰当的划分成若干个相互联系的阶段。用
k = 1,2,…,n 表示阶段序号,称为阶段变量。
二、状态
状态表示某段的初始条件。用sk表示第k段的状态,称为第k段
状态变量。
sk∈Sk
k阶段的允许决策集合
8
四、状态转移方程
sk+1与sk,xk之间必须能够建立一种明确的数量对应关系,记为
Tk(sk,xk), 即有
sk+1 = Tk(sk,xk)
这种明确的数量关系称为状态转移方程。
五、策略
由各阶段决策xk构成的决策序列,称为全过程策略,简称策略,记为
p1(s1),有
p1(s1) = { x1(s1),x2(s2),…,xn(sn)}
pk(sk) = { xk(sk),xk+1(sk+1),…,xn(sn)} ∈Pk
称为第k子过程策略,简称子策略。
∈P1
而
9
六、指标函数
(1) 阶段指标函数
用vk(sk,xk)表示第k段处于sk状态且所作决策为xk
时的指标,则它就是第k段指标函数,简记为vk。
∈P1
(2) 过程指标函数
用fk(sk,xk)表示第k子过程的指标函数。
它是各vk的累积效应。
常用函数:
fk(sk,xk) = vi(si,xi)
n
i= k
fk(sk,xk) = vi(si,xi)
n
i= k
积函数
和函数
七、最优解
(1) 最优指标函数
fk*(sk) = opt {fk(sk, pk(sk))}, k=1,2,…,n pk∈Pk
(2) 最优策略
能使上式成立的子策略pk*称为最优子策略,记为
pk*