管理运筹学谢家平 博士 副教授研究领域,系统建模与优化、生产与运作管理、物流与供应链管理讲授课程,管理运筹学、管理系统工程、生产运作管理、
供应链管理、国际物流管理、企业资源计划单 位,上海财经大学 国际工商管理学院 供应链管理研究中心
E-mail,jiaping_xie@sina.com.cn
电 话,55036936(H) 65903541(O)
上海财经大学 国际工商管理学院
SHUFE
2
第八章 动态规划
动态规划 Dynamic Programming
研究多阶段决策的最优化问题的方法 。
多阶段决策问题含有一个描述 过程时序 或 空间演变 的阶段变量,将复杂问题划分成若干阶段,根据,最优性原理,,
逐段解决而最终实现全局最优 。
经济,管理,工业生产,工程技术等领域,许多问题可归结为多阶段决策问题 。
一些用线性规划,非线性规划处理有困难的问题,往往可以用动态规划方便地求解 。
动态规划是美国运筹学家贝尔曼 (R.Bellman)等人 1959年提出的。
上海财经大学 国际工商管理学院
SHUFE
3
第一节 多阶段决策问题
多阶段决策：
经济管理决策中，有些管理决策问题可以按 时序 或 空间演变 划分成多个阶段,呈现出明显的阶段性；
于是可把这类决策问题分解成几个相互联系的阶段，每个阶段即为一个子问题；
原有问题的求解就化为逐个求解几个简单的阶段子问题；
每个阶段的决策一旦确定，整个决策过程也随之确定，此类问题称为多阶段决策问题。
例如：
企业生产物流：可分为物料供应、生产制造、分销零售等阶段。
最短路问题：可以按空间顺序划分阶段。
一,问题的提出上海财经大学 国际工商管理学院
SHUFE
4
第一节 多阶段决策问题
从生产厂 Q到某公司 T选择那条路线,使总运费最低 (路程最短 )？
最短路问题
Q T
A1
A2
A3
B1
B2
B3
C1
C1
2
4
3
7
4
6
4
2
4
42
5
1
4
6
3
3
3
3
4
生产商某公司出口港进口港城市阶段 1 阶段 2 阶段 3 阶段 4
上海财经大学 国际工商管理学院
SHUFE
5
第一节 多阶段决策问题
这是一个多阶段决策问题，它可分为四个阶段：
第一阶段：从 Q(制造厂 )到 A(出口港 )；
第二阶段：从 A(出口港 )到 B(进口港 )；
第三阶段：从 B(进口港 )到 C(城市 )；
第四阶段：从 C(城市 )到 T(某公司 )。
每个阶段选取的路线不同，对应从 Q到 T就有一系列不同的运输路线,
从始点 Q到终点 T共有 3× 3× 2× 1=18条不同路线
现在的问题是如何选择一条费用最小的路线？
上海财经大学 国际工商管理学院
SHUFE
6
第一节 多阶段决策问题
最短路径,Q→ A3→ B1→ C1→T
二、动态规划的标号法
Q T
A1
A2
A3
B1
B2
B3
C1
C2
2
4
3
7
4
6
4
2
4
42
5
1
4
6
3
3
3
3
4
阶段 1 阶段 2 阶段 3 阶段 4
0
3,T
4,T
4,C1
7,C2
6,C1
11,B1,B2
8,B1
8,B1
11,A3
上海财经大学 国际工商管理学院
SHUFE
7
第一节 多阶段决策问题
最短路的基本特征
从始点 Q到终点 T 的最短路径,Q→ A3→ B1→ C1→T,则从中点 A3 到终点 T 的最短路径必为,A3→ B1→ C1→T,
从中点 B1 到终点 T 的最短路径必为,B1→ C1→T,… 。
推广：从始点 Q到终点 T 的最短路径：
Q → S1→ S2→ … → Sk→ Sk+1→ … → Sn→T,则从中点 Sk 到终点 T 的最短路径必为,Sk→ Sk+1→ … →
Sn→T 。
三,多阶段决策的基本特征上海财经大学 国际工商管理学院
SHUFE
8
第二节 动态规划原理
阶段 (stage)
处理多阶段决策，需将全过程划为若干阶段，每个阶段进行一次抉择。
各阶段按一定顺序联接在一起组成统一的整体。
用 k表示 阶段变量 。
阶段编号
顺序编号
逆序编号一、动态规划的基本概念上海财经大学 国际工商管理学院
SHUFE
9
第二节 动态规划原理
状态 (state)
状态表示过程发展中某阶段的起始状况 。
过程的发展可以通过各阶段状态的演变来描述 。
状态可用一个变量来描述,称为 状态变量,用 Sk表示 。
选取的状态变量必须满足 无后效性 。
某阶段的状态给定后,则过程未来发展不受该阶段以前各阶段状态的影响 。
第 k 阶段可能有若干状态,用 Sk表示阶段 k的状态集合,
sk(i)表示第 k阶段的第 i 个状态 。
上海财经大学 国际工商管理学院
SHUFE
10
第二节 动态规划原理
决策 (decision)
从上一阶段某状态演变到下一阶段某状态要作一次选择,
称为决策 。
用变量 xk(sk)表示第 k阶段状态为 sk时的决策,称为 决策变量,简记 xk
决策变量的取值被限制在某一范围内,此范围称为允许决策集合 Xk(sk)
上海财经大学 国际工商管理学院
SHUFE
11
第二节 动态规划原理
策略 (policy)
多阶段决策过程中,每一阶段均有一个决策,依序组合成一个全过程的决策序列,称为 全过程策略 。
p1,n(s1)={x1(s1),x2(s2),…,xn(sn)},简记 p1,n ={x1,x2,…,xn}
从过程的某个阶段开始到最终阶段结束称为后部子过程 。
从第 k阶段开始的后部子策略称为 第 k子过程策略 。
pk,n(sk)={xk(sk),xk+1(sk+1),…,xn(sn)},简记 pk,n ={xk,xk+1,…,xn}
每一阶段有若干状态,每个状态又有若干个不同的决策,即有许多策略可供选择 。 全体策略构成允许策略集合 Pk,n(sk)。
能使预期目标达到最优效果的策略称为最优策略 P*k,n,
构成最优策略的各决策称为相应阶段的最优决策 x*k。
上海财经大学 国际工商管理学院
SHUFE
12
第二节 动态规划原理
状态转移方程
下一阶段状态 sk+1 是本阶段状态变量 sk 和决策变量 xk的函数,
即 sk+1 =T(sk,xk(sk)) =T(sk,xk)
从状态 sk出发到下一阶段状态 sk+1的转移规律称为 状态转移方程 。
上海财经大学 国际工商管理学院
SHUFE
13
第二节 动态规划原理
指标函数
用来衡量每一阶段决策效果的优劣的数量指标,称为 阶段指标函数 vk,
阶段指标是状态变量和相应决策变量的函数,即 vk = vk(sk,xk )。
最短问题是运费或路程 。 对阶段的不同状态,采取不同的决策,
运费不同 。
指标函数也可以是利润,成本,产量等 。
从第 k阶段的状态 sk出发到最后阶段结束,各阶段绩效综合起来反映这个后部子过程的绩效,称为 过程指标函数,记为 Vk,n。
Vk,n的大小取决于从第 k阶段到最后阶段所采取的子策略。即
Vk,n = Vk,n (sk,xk,sk+1,xk+1,…,sn)
根据实际问题的性质，指标函数 Vk,n 可以是各个阶段指标的和或积。
从状态 sk出发,选取最优策略所得的指标函数值称为 最优指标函数值 。
fk(sk)=opt{Vk,n }=opt{vk(sk,xk ) + fk+1(sk+1) }
opt表示最优化，取最大 max或最小 min。
上海财经大学 国际工商管理学院
SHUFE
14
第二节 动态规划原理
逆序算法,逆着阶段顺序的方向，由后向前推算。
把寻求最优策略看作连续递推过程，从最终阶段开始，逆着实际过程的进展方向逐段求解；
在每一阶段求解过程中都是其后部子过程最优策略的基础上，
再考虑本阶段的指标函数，求出本阶段的最优策略；
直到第一阶段为止。
最优性原理,美国运筹学家贝尔曼提出
无论过去的状态和决策如何,对前面的决策所形成的状态而言,
余下的诸决策必须构成最优策略 。
将决策问题划分为若干个阶段,全过程的优化问题就分解为子过程的优化问题,由后向前逐步倒推,最优化的子过程逐渐成为全过程最优 。
作为全过程的最优策略 P*1,n的组成部分的任一子策略 P*k,n(Sk)，
一定是从状态 Sk出发直至终点的最优策略 。
二、动态规划方法的基本思路上海财经大学 国际工商管理学院
SHUFE
15
第二节 动态规划原理
据最优性原理,阶段 k的阶段指标 vk(sk,xk )加上 (或乘以 )从下一阶段 k+1
开始到过程结束采取最优策略取得的最优指标函数值 fk+1(sk+1),再从中选出最优,便是阶段 k从状态 sk出发到全过程结束的最优指标函数值 。
0)(
)(),()(
),(
11
11
)(
,
nn
kkkkk
SXx
kk
n
ki
iiink
sf
sfxsvsf
xsvV
o p t
kkk
边界条件：
基本方程：
指标之和，过程指标等于各阶段若
1)(
)(),()(
),(
11
11
)(
,
nn
kkkkk
SXx
kk
n
ki
iiink
sf
sfxsvsf
xsvV
o p t
kkk
边界条件：
基本方程：
指标之积，过程指标等于各阶段若上海财经大学 国际工商管理学院
SHUFE
16
第二节 动态规划原理阶段 1 阶段 2 阶段 k 阶段 k+1 阶段 n… …
状态 S1
决策
x1
状态 S2
v1
决策
x2
状态 S3
v2
决策
xk
状态 Sk+1
vk
决策
xk+1
vk+1
决策
xn
vn
寻求最优解的方向
0)( 11 nn sf边界条件：
)(),()( 11
)(
kkkkk
SXx
kk sfxsvsf opt
kkk
递推方程：
上海财经大学 国际工商管理学院
SHUFE
17
第二节 动态规划原理
建模步骤（小结）
对问题进行阶段划分，确定阶段变量 k
确定状态变量 sk
确定决策变量 xk,允许决策集合 Xk (sk )
写出状态转移方程 sk+1 =Tk (sk,xk)
写出指标函数的基本递推方程
明确边界条件
动态规划模型分类三、动态规划模型过程变量 确定 随机离散连续离散确定型 离散随机型连续确定型 连续随机型上海财经大学 国际工商管理学院
SHUFE
18
第三节 应用举例
资源分配问题：
把有限的资源 (如资金、材料、设备、人力等 )分配给若干使用者，而使某一指标为最优的问题即为资源分配问题。
资源可以有一种或若干种，
只有一种资源可供分配的问题称之为一维资源分配问题。
一维资源分配问题一、资源分配问题设备台数分厂 0 1 2 3 4 5 6
I 0 3 5 6 7 6 5
II 0 4 6 7 8 9 10
III 0 2 5 9 8 8 7
如何分配设备，可使获利最大？
各分厂在不同设备台数下所获利润上海财经大学 国际工商管理学院
SHUFE
19
第三节 应用举例
动态规划的数学模型
将三个分厂看作是三个阶段,即阶段变量 k=1,2,3;
状态变量 sk表示第 k阶段初可分配的设备台数,0≤ sk ≤6;
决策变量 xk 表示第 k 阶段分配给分厂 k 的设备台数，
允许决策集合 Xk (sk)={ xk ︱ 0≤ xk ≤sk};
状态转移方程为 sk+1 = sk - xk ;
阶段指标 vk(sk,xk) 表示第 k 阶段从 sk台设备中分配给 k 分厂
xk台设备的阶段效益 ;
最优指数函数 fk(sk)表示第 k阶段从 sk 开始到最后阶段采用最优分配策略取得的最大的效益值 ;
递推方程函数式
0)(
)(),()(
44
11
)(
m a x
sf
sfxsvsf kkkkk
SXx
kk
kkk
边界条件：
基本方程：
上海财经大学 国际工商管理学院
SHUFE
20
第三节 应用举例
逆序求解
K=3
x3
s3
v3 (s3,x3) f
3 (s3) x3*
第 III分厂在不同设备台数下所获利润
0
1
2
3
4
5
6
0 1 2 3 4 5 6
0
0 2
0 2 5
0 2 5 9
0 2 5 9 8
0 2 5 9 8 8
0 2 5 9 8 8 7
0
2
5
9
9
9
9
0
1
2
3
3
3
3
上海财经大学 国际工商管理学院
SHUFE
21
第三节 应用举例
k=2
x2
s2
v2 (s2,x2)+f3(s3) f
2 (s2) x2*
第 II分厂在不同设备台数下所获利润
0
1
2
3
4
5
6
0 1 2 3 4 5 6
0
0 4
0 4 6
0 4 6 7
0 4 6 7 8
0 4 6 7 8 9
0 4 6 7 8 9 10
0
4
6
9
13
15
16
0
1
1,2
0,1
1
2
3
第 III分厂在设备台数为
s3下所获得的最大利润
0+0
0+2 +0
0+5 +2 +0
0+9 +5 +2 +0
0+9 +9 +5 +2 +0
0+9 +9 +9 +5 +2 +0
0+9 +9 +9 +9 +5 +2 10+0
上海财经大学 国际工商管理学院
SHUFE
22
第三节 应用举例
k=1
x1
s1
v1 (s1,x1)+f2(s2) f
1 (s1) x1*
第 I分厂在不同设备台数下所获利润
0 1 2 3 4 5 6
第 II分厂在设备台数为 s2
下所获得的最大利润
6 0 3 5 6 7 6 5 18 1,2
顺序递推，得出结论
第 I 分厂 1套或 2套
第 II 分厂 2套或 1套
第 III 分厂 3套
+1
6
+15 +13 +9 +6 6+4 +0
上海财经大学 国际工商管理学院
SHUFE
23
第三节 应用举例
企业一年中的产品生产往往是分期分批生产的。
组织每批产品的生产，都要花费一些生产准备费和存贮费用。
若某一时期增大生产批量则可减少生产批次，从而降低生产成本。
与此同时，批量大了，必然增加库存而使存贮费用增加。
在企业产品的生产成本、存贮费用、市场需求量确定的情况下，正确计划各时期的生产量，既满足市场需求，又使总支出最少，这是一个多阶段决策问题。
二、生产与存储问题上海财经大学 国际工商管理学院
SHUFE
24
第三节 应用举例
例,某工厂与用户签订了 4个月的交货合同如表所示该厂生产能力为每月 5万件，该厂仓库的存货能力为 4万件。
已知生产费用为 c=1千元 /万件，在进行生产的月份，工厂要支出固定费用 b=2千元，每月仓库保管费用 h=0.2千元 /万件 /月。
假定开始时及 4月底交货后无存货，试问应在每月各生产多少件产品，才能满足交货任务，又使总费用最小？
月 1 2 3 4
需求量 dk(万件 ) 3 2 3 2
上海财经大学 国际工商管理学院
SHUFE
25
第三节 应用举例
动态规划的数学模型
每个月为一个阶段,即阶段变量 k=1,2,3,4分别表示这四个月 ;
状态变量 sk表示第 k月初的产品库存量,0≤sk ≤4;
决策变量 xk 表示第 k月的生产量,
允许决策集合 Xk (sk)={ xk ︱ 0≤ xk ≤5};
状态转移方程为 sk+1 = sk + xk – dk ;
阶段指标 vk(sk,xk) 表示第 k 月的费用,本月若不安排生产,则仅需支出保管费；本月若安排生产,则需支出生产费用和固定费,同时还需交付保管费 。
当 xk =0时,vk(sk,xk)=h ·s k =0.2sk
当 xk ＞ 0时,vk(sk,xk)=b+c·xk+h·sk =2+xk +0.2sk
最优指数函数 fk(sk)表示第 k阶段从 sk 开始到最后阶段采用最优生产策略实现的最低生产费用 ;
0)(
)(),()(
55
11
)(
m i n
sf
sfxsvsf kkkkk
SXx
kk
kkk
边界条件：
基本方程：
上海财经大学 国际工商管理学院
SHUFE
26
第三节 应用举例
逆序求解
K=4
x4
s4
v4 (s4,x4)=0.2 s4 v4 (s4,x4)=2+ x4+0.2 s4 f
3(s3) x3*
0
1
2
0 1 2
-- -- 4
-- 3.2 --
0.4 -- --
4
3.2
0.4
2
1
0
d4=2,4月末无库存则 s5=0,状态转移方程 s5= s4+ x4 – d4,则
s4= d4 – x4 = 2 – x4
x4≥0,则 s4 = 2 – x4 ={ 0,1,2}
s4≥0,则 x4 = 2 – s4 = {0,1,2}
上海财经大学 国际工商管理学院
SHUFE
27
第三节 应用举例
k=3
x3
s3
0.2 s3 + f4(s4) v3 (s3,x3)+f4(s4) =2+ x3+0.2 s3 + f4(s4) f
3(s3) x3*
0
1
2
3
4
0 1 2 3 4 5
7.4
6.6
5.8
4.6
4.2
5
4
3
0
0
-- --- 9.0 9.2 7.4
-- -- 8.2 8.4 6.6 --
-- 7.4 7.6 5.8 -- --
4.6 6.8 5.0 -- -- --
4 4.2 -- -- -- --
d3=3,0≤s4≤2,状态转移方程 s4= s3+ x3 – d3,则 0≤
s3+ x3 – d3 ≤ 2，即 3≤ s3+ x4 ≤ 5
0≤s3≤4,则 s3 ={ 0,1,2,3,4}
生产能力限制 0≤x3≤5，则 x3 = {0,1,2,3,4,5}
4月在库存量为 s4下的最低生产成本上海财经大学 国际工商管理学院
SHUFE
28
第三节 应用举例
k=2
x2
s2
0.2 s2 + f3(s3) v2 (s2,x2)+f3(s3) =2+ x2+0.2 s2 + f3(s3) f
2(s2) x2*
0
1
2
0 1 2 3 4 5
11.4
10.6
7.8
2
1
0
-- -- 11.4 11.6 11.8 11.6
-- 10.6 10.8 11.0 10.8 11.2
7.8 10.0 10.2 10.0 10.4 --
d2=2,0≤s3≤4,状态转移方程 s3= s2+ x2 – d2,则 0≤
s2+ x2 – d2≤ 4，即 2≤ s2+ x2 ≤ 6
s1=0,则 s2 = s1+ x1 – d1 = x1 – 3； x1 ≤5，则 s2 ≤2
生产能力限制 0≤x2≤5，则 x2 = {0,1,2,3,4,5}
3月在库存量为 s3下的最低生产成本上海财经大学 国际工商管理学院
SHUFE
29
第三节 应用举例
k=1
x1
s1
v1 (s1,x1)+f2(s2) =2+ x2+0.2 s2 + f2(s2) f
1(s1) x1*3 4 5
2月在库存量为 s2下的最低生产成本
0 14.8 5
– 顺序递推，得出结论
– 第 1月生产 5万件
– s2 = s1+ x1 – d1 =0+5-3=2，第 2月不生产
– s3 = s2+ x2 – d2 =2+0-2=0，第 3月生产 5万件
– s4 = s3+ x3 – d3 =0+5-3=2，第 4月不生产
16.4 16.6 14.8
d1=3,s1=0，状态转移方程则 s2 = s1+ x1 – d1 = x1 – 3； s2≥0，则
x1 ≥ 3，
生产能力限制 x1≤5，则 3≤x1 ≤5,x1 = {3,4,5}
上海财经大学 国际工商管理学院
SHUFE
30
第三节 应用举例
有一种设备可以在高低两种不同的负荷下运行，在高负荷下生产时，产品的年产量 Q1与投入生产的设备台数 x1
的关系为,Q1 =9x1,年完好率 (折损后 )a=0.75；在低负荷下生产时，年产量 Q2与投入生产的设备台数 x2的关系为,Q2 =6 x2,年完好率为 b=0.96，若开始时拥有完好机器台数为 100台，要求制定一个 4年计划，在每年初时应决定如何重新分配设备在高低不同的负荷下生产，使得 4
年内产品的总产量达到最高。
三、机器负荷问题上海财经大学 国际工商管理学院
SHUFE
31
第三节 应用举例
动态规划的数学模型
每年为一个阶段,即阶段变量 k=1,2,3,4;
状态变量 sk表示第 k年初所拥有的完好机器台数,s1 =100;
决策变量 xk 表示第 k年投入高负荷生产的机器数,
允许决策集合 Xk (sk)={ xk ︱ 0≤ xk ≤ sk};
状态转移方程为 sk+1 =a xk +b(sk – xk ) =0.75 xk +0.96(sk– xk )
=0.96sk – 0.21xk;
阶段指标 vk(sk,xk) 表示第 k年的产量,vk(sk,xk) = 9xk +6(sk – xk )
=6sk +3xk ;
最优指数函数 fk(sk)表示第 k阶段从 sk 开始到最后阶段采用最优分配策略实现的最大产量 ;
0)(
)21.096.0(36
)(),()(
55
1
0
11
)(
m a x
m a x
sf
xsfxs
sfxsvsf
kkkkk
Sx
kkkkk
SXx
kk
kk
kkk
边界条件：
基本方程：
上海财经大学 国际工商管理学院
SHUFE
32
第三节 应用举例
K=4
44
0
55444
0
44
36
)(),()(
m ax
m ax
44
44
xs
sfxsvsf
sx
sx
f4(s4)是关于 x4 的单增函数，故 x*4 =s4 时,f4(s4)最大,f4(s4)=9 s4
K=3
33
0
3333
0
433
0
44333
0
33
11.164.14
)21.096.0(936
936
)(),()(
m a x
m a x
m a x
m a x
33
33
33
33
xs
xsxs
sxs
sfxsvsf
sx
sx
sx
sx
f3(s3)是关于 x3 的单增函数，故 x*3 =s3 时,f3(s3)最大,f3(s3)=15.75 s3
上海财经大学 国际工商管理学院
SHUFE
33
第三节 应用举例
K=2
22
0
2222
0
322
0
33222
0
22
375.012.21
)21.096.0(75.1536
75.1536
)(),()(
m a x
m a x
m a x
m a x
22
22
22
22
xs
xsxs
sxs
sfxsvsf
sx
sx
sx
sx
f2(s2)是关于 x2 的单减函数，故 x*2 =0 时,f2(s2)最大,f2(s2)=21.12 s2
K=1
21
0
1111
0
311
0
22111
0
11
4 3 5 2.12 7 5 2.26
)21.096.0(12.2136
12.2136
)(),()(
m a x
m a x
m a x
m a x
11
11
11
11
xs
xsxs
sxs
sfxsvsf
sx
sx
sx
sx
f1(s1)是关于 x1 的单减函数，故 x*1 =0 时,f1(s1)最大,f1(s1)=26.275 s1
上海财经大学 国际工商管理学院
SHUFE
34
第三节 应用举例
最优生产策略,x*1 =0,x*2 =0,x*3 =s3,x*4 =s4
各阶段状态：
s1 =100,x*1 =0，
s2 = 0.96s1 – 0.21x1 = 0.96s1 =96,x*2=0，
s3 = 0.96s2 – 0.21x2 = 0.96s2 =92.16,x*2= s3,
s4 = 0.96s3 – 0.21x3 = 0.75s3 =69.12,x*4= s4
s5 = 0.96s4 – 0.21x4 = 0.75s4=51.84
供应链管理、国际物流管理、企业资源计划单 位,上海财经大学 国际工商管理学院 供应链管理研究中心
E-mail,jiaping_xie@sina.com.cn
电 话,55036936(H) 65903541(O)
上海财经大学 国际工商管理学院
SHUFE
2
第八章 动态规划
动态规划 Dynamic Programming
研究多阶段决策的最优化问题的方法 。
多阶段决策问题含有一个描述 过程时序 或 空间演变 的阶段变量,将复杂问题划分成若干阶段,根据,最优性原理,,
逐段解决而最终实现全局最优 。
经济,管理,工业生产,工程技术等领域,许多问题可归结为多阶段决策问题 。
一些用线性规划,非线性规划处理有困难的问题,往往可以用动态规划方便地求解 。
动态规划是美国运筹学家贝尔曼 (R.Bellman)等人 1959年提出的。
上海财经大学 国际工商管理学院
SHUFE
3
第一节 多阶段决策问题
多阶段决策：
经济管理决策中，有些管理决策问题可以按 时序 或 空间演变 划分成多个阶段,呈现出明显的阶段性；
于是可把这类决策问题分解成几个相互联系的阶段，每个阶段即为一个子问题；
原有问题的求解就化为逐个求解几个简单的阶段子问题；
每个阶段的决策一旦确定，整个决策过程也随之确定，此类问题称为多阶段决策问题。
例如：
企业生产物流：可分为物料供应、生产制造、分销零售等阶段。
最短路问题：可以按空间顺序划分阶段。
一,问题的提出上海财经大学 国际工商管理学院
SHUFE
4
第一节 多阶段决策问题
从生产厂 Q到某公司 T选择那条路线,使总运费最低 (路程最短 )？
最短路问题
Q T
A1
A2
A3
B1
B2
B3
C1
C1
2
4
3
7
4
6
4
2
4
42
5
1
4
6
3
3
3
3
4
生产商某公司出口港进口港城市阶段 1 阶段 2 阶段 3 阶段 4
上海财经大学 国际工商管理学院
SHUFE
5
第一节 多阶段决策问题
这是一个多阶段决策问题，它可分为四个阶段：
第一阶段：从 Q(制造厂 )到 A(出口港 )；
第二阶段：从 A(出口港 )到 B(进口港 )；
第三阶段：从 B(进口港 )到 C(城市 )；
第四阶段：从 C(城市 )到 T(某公司 )。
每个阶段选取的路线不同，对应从 Q到 T就有一系列不同的运输路线,
从始点 Q到终点 T共有 3× 3× 2× 1=18条不同路线
现在的问题是如何选择一条费用最小的路线？
上海财经大学 国际工商管理学院
SHUFE
6
第一节 多阶段决策问题
最短路径,Q→ A3→ B1→ C1→T
二、动态规划的标号法
Q T
A1
A2
A3
B1
B2
B3
C1
C2
2
4
3
7
4
6
4
2
4
42
5
1
4
6
3
3
3
3
4
阶段 1 阶段 2 阶段 3 阶段 4
0
3,T
4,T
4,C1
7,C2
6,C1
11,B1,B2
8,B1
8,B1
11,A3
上海财经大学 国际工商管理学院
SHUFE
7
第一节 多阶段决策问题
最短路的基本特征
从始点 Q到终点 T 的最短路径,Q→ A3→ B1→ C1→T,则从中点 A3 到终点 T 的最短路径必为,A3→ B1→ C1→T,
从中点 B1 到终点 T 的最短路径必为,B1→ C1→T,… 。
推广：从始点 Q到终点 T 的最短路径：
Q → S1→ S2→ … → Sk→ Sk+1→ … → Sn→T,则从中点 Sk 到终点 T 的最短路径必为,Sk→ Sk+1→ … →
Sn→T 。
三,多阶段决策的基本特征上海财经大学 国际工商管理学院
SHUFE
8
第二节 动态规划原理
阶段 (stage)
处理多阶段决策，需将全过程划为若干阶段，每个阶段进行一次抉择。
各阶段按一定顺序联接在一起组成统一的整体。
用 k表示 阶段变量 。
阶段编号
顺序编号
逆序编号一、动态规划的基本概念上海财经大学 国际工商管理学院
SHUFE
9
第二节 动态规划原理
状态 (state)
状态表示过程发展中某阶段的起始状况 。
过程的发展可以通过各阶段状态的演变来描述 。
状态可用一个变量来描述,称为 状态变量,用 Sk表示 。
选取的状态变量必须满足 无后效性 。
某阶段的状态给定后,则过程未来发展不受该阶段以前各阶段状态的影响 。
第 k 阶段可能有若干状态,用 Sk表示阶段 k的状态集合,
sk(i)表示第 k阶段的第 i 个状态 。
上海财经大学 国际工商管理学院
SHUFE
10
第二节 动态规划原理
决策 (decision)
从上一阶段某状态演变到下一阶段某状态要作一次选择,
称为决策 。
用变量 xk(sk)表示第 k阶段状态为 sk时的决策,称为 决策变量,简记 xk
决策变量的取值被限制在某一范围内,此范围称为允许决策集合 Xk(sk)
上海财经大学 国际工商管理学院
SHUFE
11
第二节 动态规划原理
策略 (policy)
多阶段决策过程中,每一阶段均有一个决策,依序组合成一个全过程的决策序列,称为 全过程策略 。
p1,n(s1)={x1(s1),x2(s2),…,xn(sn)},简记 p1,n ={x1,x2,…,xn}
从过程的某个阶段开始到最终阶段结束称为后部子过程 。
从第 k阶段开始的后部子策略称为 第 k子过程策略 。
pk,n(sk)={xk(sk),xk+1(sk+1),…,xn(sn)},简记 pk,n ={xk,xk+1,…,xn}
每一阶段有若干状态,每个状态又有若干个不同的决策,即有许多策略可供选择 。 全体策略构成允许策略集合 Pk,n(sk)。
能使预期目标达到最优效果的策略称为最优策略 P*k,n,
构成最优策略的各决策称为相应阶段的最优决策 x*k。
上海财经大学 国际工商管理学院
SHUFE
12
第二节 动态规划原理
状态转移方程
下一阶段状态 sk+1 是本阶段状态变量 sk 和决策变量 xk的函数,
即 sk+1 =T(sk,xk(sk)) =T(sk,xk)
从状态 sk出发到下一阶段状态 sk+1的转移规律称为 状态转移方程 。
上海财经大学 国际工商管理学院
SHUFE
13
第二节 动态规划原理
指标函数
用来衡量每一阶段决策效果的优劣的数量指标,称为 阶段指标函数 vk,
阶段指标是状态变量和相应决策变量的函数,即 vk = vk(sk,xk )。
最短问题是运费或路程 。 对阶段的不同状态,采取不同的决策,
运费不同 。
指标函数也可以是利润,成本,产量等 。
从第 k阶段的状态 sk出发到最后阶段结束,各阶段绩效综合起来反映这个后部子过程的绩效,称为 过程指标函数,记为 Vk,n。
Vk,n的大小取决于从第 k阶段到最后阶段所采取的子策略。即
Vk,n = Vk,n (sk,xk,sk+1,xk+1,…,sn)
根据实际问题的性质，指标函数 Vk,n 可以是各个阶段指标的和或积。
从状态 sk出发,选取最优策略所得的指标函数值称为 最优指标函数值 。
fk(sk)=opt{Vk,n }=opt{vk(sk,xk ) + fk+1(sk+1) }
opt表示最优化，取最大 max或最小 min。
上海财经大学 国际工商管理学院
SHUFE
14
第二节 动态规划原理
逆序算法,逆着阶段顺序的方向，由后向前推算。
把寻求最优策略看作连续递推过程，从最终阶段开始，逆着实际过程的进展方向逐段求解；
在每一阶段求解过程中都是其后部子过程最优策略的基础上，
再考虑本阶段的指标函数，求出本阶段的最优策略；
直到第一阶段为止。
最优性原理,美国运筹学家贝尔曼提出
无论过去的状态和决策如何,对前面的决策所形成的状态而言,
余下的诸决策必须构成最优策略 。
将决策问题划分为若干个阶段,全过程的优化问题就分解为子过程的优化问题,由后向前逐步倒推,最优化的子过程逐渐成为全过程最优 。
作为全过程的最优策略 P*1,n的组成部分的任一子策略 P*k,n(Sk)，
一定是从状态 Sk出发直至终点的最优策略 。
二、动态规划方法的基本思路上海财经大学 国际工商管理学院
SHUFE
15
第二节 动态规划原理
据最优性原理,阶段 k的阶段指标 vk(sk,xk )加上 (或乘以 )从下一阶段 k+1
开始到过程结束采取最优策略取得的最优指标函数值 fk+1(sk+1),再从中选出最优,便是阶段 k从状态 sk出发到全过程结束的最优指标函数值 。
0)(
)(),()(
),(
11
11
)(
,
nn
kkkkk
SXx
kk
n
ki
iiink
sf
sfxsvsf
xsvV
o p t
kkk
边界条件：
基本方程：
指标之和，过程指标等于各阶段若
1)(
)(),()(
),(
11
11
)(
,
nn
kkkkk
SXx
kk
n
ki
iiink
sf
sfxsvsf
xsvV
o p t
kkk
边界条件：
基本方程：
指标之积，过程指标等于各阶段若上海财经大学 国际工商管理学院
SHUFE
16
第二节 动态规划原理阶段 1 阶段 2 阶段 k 阶段 k+1 阶段 n… …
状态 S1
决策
x1
状态 S2
v1
决策
x2
状态 S3
v2
决策
xk
状态 Sk+1
vk
决策
xk+1
vk+1
决策
xn
vn
寻求最优解的方向
0)( 11 nn sf边界条件：
)(),()( 11
)(
kkkkk
SXx
kk sfxsvsf opt
kkk
递推方程：
上海财经大学 国际工商管理学院
SHUFE
17
第二节 动态规划原理
建模步骤（小结）
对问题进行阶段划分，确定阶段变量 k
确定状态变量 sk
确定决策变量 xk,允许决策集合 Xk (sk )
写出状态转移方程 sk+1 =Tk (sk,xk)
写出指标函数的基本递推方程
明确边界条件
动态规划模型分类三、动态规划模型过程变量 确定 随机离散连续离散确定型 离散随机型连续确定型 连续随机型上海财经大学 国际工商管理学院
SHUFE
18
第三节 应用举例
资源分配问题：
把有限的资源 (如资金、材料、设备、人力等 )分配给若干使用者，而使某一指标为最优的问题即为资源分配问题。
资源可以有一种或若干种，
只有一种资源可供分配的问题称之为一维资源分配问题。
一维资源分配问题一、资源分配问题设备台数分厂 0 1 2 3 4 5 6
I 0 3 5 6 7 6 5
II 0 4 6 7 8 9 10
III 0 2 5 9 8 8 7
如何分配设备，可使获利最大？
各分厂在不同设备台数下所获利润上海财经大学 国际工商管理学院
SHUFE
19
第三节 应用举例
动态规划的数学模型
将三个分厂看作是三个阶段,即阶段变量 k=1,2,3;
状态变量 sk表示第 k阶段初可分配的设备台数,0≤ sk ≤6;
决策变量 xk 表示第 k 阶段分配给分厂 k 的设备台数，
允许决策集合 Xk (sk)={ xk ︱ 0≤ xk ≤sk};
状态转移方程为 sk+1 = sk - xk ;
阶段指标 vk(sk,xk) 表示第 k 阶段从 sk台设备中分配给 k 分厂
xk台设备的阶段效益 ;
最优指数函数 fk(sk)表示第 k阶段从 sk 开始到最后阶段采用最优分配策略取得的最大的效益值 ;
递推方程函数式
0)(
)(),()(
44
11
)(
m a x
sf
sfxsvsf kkkkk
SXx
kk
kkk
边界条件：
基本方程：
上海财经大学 国际工商管理学院
SHUFE
20
第三节 应用举例
逆序求解
K=3
x3
s3
v3 (s3,x3) f
3 (s3) x3*
第 III分厂在不同设备台数下所获利润
0
1
2
3
4
5
6
0 1 2 3 4 5 6
0
0 2
0 2 5
0 2 5 9
0 2 5 9 8
0 2 5 9 8 8
0 2 5 9 8 8 7
0
2
5
9
9
9
9
0
1
2
3
3
3
3
上海财经大学 国际工商管理学院
SHUFE
21
第三节 应用举例
k=2
x2
s2
v2 (s2,x2)+f3(s3) f
2 (s2) x2*
第 II分厂在不同设备台数下所获利润
0
1
2
3
4
5
6
0 1 2 3 4 5 6
0
0 4
0 4 6
0 4 6 7
0 4 6 7 8
0 4 6 7 8 9
0 4 6 7 8 9 10
0
4
6
9
13
15
16
0
1
1,2
0,1
1
2
3
第 III分厂在设备台数为
s3下所获得的最大利润
0+0
0+2 +0
0+5 +2 +0
0+9 +5 +2 +0
0+9 +9 +5 +2 +0
0+9 +9 +9 +5 +2 +0
0+9 +9 +9 +9 +5 +2 10+0
上海财经大学 国际工商管理学院
SHUFE
22
第三节 应用举例
k=1
x1
s1
v1 (s1,x1)+f2(s2) f
1 (s1) x1*
第 I分厂在不同设备台数下所获利润
0 1 2 3 4 5 6
第 II分厂在设备台数为 s2
下所获得的最大利润
6 0 3 5 6 7 6 5 18 1,2
顺序递推，得出结论
第 I 分厂 1套或 2套
第 II 分厂 2套或 1套
第 III 分厂 3套
+1
6
+15 +13 +9 +6 6+4 +0
上海财经大学 国际工商管理学院
SHUFE
23
第三节 应用举例
企业一年中的产品生产往往是分期分批生产的。
组织每批产品的生产，都要花费一些生产准备费和存贮费用。
若某一时期增大生产批量则可减少生产批次，从而降低生产成本。
与此同时，批量大了，必然增加库存而使存贮费用增加。
在企业产品的生产成本、存贮费用、市场需求量确定的情况下，正确计划各时期的生产量，既满足市场需求，又使总支出最少，这是一个多阶段决策问题。
二、生产与存储问题上海财经大学 国际工商管理学院
SHUFE
24
第三节 应用举例
例,某工厂与用户签订了 4个月的交货合同如表所示该厂生产能力为每月 5万件，该厂仓库的存货能力为 4万件。
已知生产费用为 c=1千元 /万件，在进行生产的月份，工厂要支出固定费用 b=2千元，每月仓库保管费用 h=0.2千元 /万件 /月。
假定开始时及 4月底交货后无存货，试问应在每月各生产多少件产品，才能满足交货任务，又使总费用最小？
月 1 2 3 4
需求量 dk(万件 ) 3 2 3 2
上海财经大学 国际工商管理学院
SHUFE
25
第三节 应用举例
动态规划的数学模型
每个月为一个阶段,即阶段变量 k=1,2,3,4分别表示这四个月 ;
状态变量 sk表示第 k月初的产品库存量,0≤sk ≤4;
决策变量 xk 表示第 k月的生产量,
允许决策集合 Xk (sk)={ xk ︱ 0≤ xk ≤5};
状态转移方程为 sk+1 = sk + xk – dk ;
阶段指标 vk(sk,xk) 表示第 k 月的费用,本月若不安排生产,则仅需支出保管费；本月若安排生产,则需支出生产费用和固定费,同时还需交付保管费 。
当 xk =0时,vk(sk,xk)=h ·s k =0.2sk
当 xk ＞ 0时,vk(sk,xk)=b+c·xk+h·sk =2+xk +0.2sk
最优指数函数 fk(sk)表示第 k阶段从 sk 开始到最后阶段采用最优生产策略实现的最低生产费用 ;
0)(
)(),()(
55
11
)(
m i n
sf
sfxsvsf kkkkk
SXx
kk
kkk
边界条件：
基本方程：
上海财经大学 国际工商管理学院
SHUFE
26
第三节 应用举例
逆序求解
K=4
x4
s4
v4 (s4,x4)=0.2 s4 v4 (s4,x4)=2+ x4+0.2 s4 f
3(s3) x3*
0
1
2
0 1 2
-- -- 4
-- 3.2 --
0.4 -- --
4
3.2
0.4
2
1
0
d4=2,4月末无库存则 s5=0,状态转移方程 s5= s4+ x4 – d4,则
s4= d4 – x4 = 2 – x4
x4≥0,则 s4 = 2 – x4 ={ 0,1,2}
s4≥0,则 x4 = 2 – s4 = {0,1,2}
上海财经大学 国际工商管理学院
SHUFE
27
第三节 应用举例
k=3
x3
s3
0.2 s3 + f4(s4) v3 (s3,x3)+f4(s4) =2+ x3+0.2 s3 + f4(s4) f
3(s3) x3*
0
1
2
3
4
0 1 2 3 4 5
7.4
6.6
5.8
4.6
4.2
5
4
3
0
0
-- --- 9.0 9.2 7.4
-- -- 8.2 8.4 6.6 --
-- 7.4 7.6 5.8 -- --
4.6 6.8 5.0 -- -- --
4 4.2 -- -- -- --
d3=3,0≤s4≤2,状态转移方程 s4= s3+ x3 – d3,则 0≤
s3+ x3 – d3 ≤ 2，即 3≤ s3+ x4 ≤ 5
0≤s3≤4,则 s3 ={ 0,1,2,3,4}
生产能力限制 0≤x3≤5，则 x3 = {0,1,2,3,4,5}
4月在库存量为 s4下的最低生产成本上海财经大学 国际工商管理学院
SHUFE
28
第三节 应用举例
k=2
x2
s2
0.2 s2 + f3(s3) v2 (s2,x2)+f3(s3) =2+ x2+0.2 s2 + f3(s3) f
2(s2) x2*
0
1
2
0 1 2 3 4 5
11.4
10.6
7.8
2
1
0
-- -- 11.4 11.6 11.8 11.6
-- 10.6 10.8 11.0 10.8 11.2
7.8 10.0 10.2 10.0 10.4 --
d2=2,0≤s3≤4,状态转移方程 s3= s2+ x2 – d2,则 0≤
s2+ x2 – d2≤ 4，即 2≤ s2+ x2 ≤ 6
s1=0,则 s2 = s1+ x1 – d1 = x1 – 3； x1 ≤5，则 s2 ≤2
生产能力限制 0≤x2≤5，则 x2 = {0,1,2,3,4,5}
3月在库存量为 s3下的最低生产成本上海财经大学 国际工商管理学院
SHUFE
29
第三节 应用举例
k=1
x1
s1
v1 (s1,x1)+f2(s2) =2+ x2+0.2 s2 + f2(s2) f
1(s1) x1*3 4 5
2月在库存量为 s2下的最低生产成本
0 14.8 5
– 顺序递推，得出结论
– 第 1月生产 5万件
– s2 = s1+ x1 – d1 =0+5-3=2，第 2月不生产
– s3 = s2+ x2 – d2 =2+0-2=0，第 3月生产 5万件
– s4 = s3+ x3 – d3 =0+5-3=2，第 4月不生产
16.4 16.6 14.8
d1=3,s1=0，状态转移方程则 s2 = s1+ x1 – d1 = x1 – 3； s2≥0，则
x1 ≥ 3，
生产能力限制 x1≤5，则 3≤x1 ≤5,x1 = {3,4,5}
上海财经大学 国际工商管理学院
SHUFE
30
第三节 应用举例
有一种设备可以在高低两种不同的负荷下运行，在高负荷下生产时，产品的年产量 Q1与投入生产的设备台数 x1
的关系为,Q1 =9x1,年完好率 (折损后 )a=0.75；在低负荷下生产时，年产量 Q2与投入生产的设备台数 x2的关系为,Q2 =6 x2,年完好率为 b=0.96，若开始时拥有完好机器台数为 100台，要求制定一个 4年计划，在每年初时应决定如何重新分配设备在高低不同的负荷下生产，使得 4
年内产品的总产量达到最高。
三、机器负荷问题上海财经大学 国际工商管理学院
SHUFE
31
第三节 应用举例
动态规划的数学模型
每年为一个阶段,即阶段变量 k=1,2,3,4;
状态变量 sk表示第 k年初所拥有的完好机器台数,s1 =100;
决策变量 xk 表示第 k年投入高负荷生产的机器数,
允许决策集合 Xk (sk)={ xk ︱ 0≤ xk ≤ sk};
状态转移方程为 sk+1 =a xk +b(sk – xk ) =0.75 xk +0.96(sk– xk )
=0.96sk – 0.21xk;
阶段指标 vk(sk,xk) 表示第 k年的产量,vk(sk,xk) = 9xk +6(sk – xk )
=6sk +3xk ;
最优指数函数 fk(sk)表示第 k阶段从 sk 开始到最后阶段采用最优分配策略实现的最大产量 ;
0)(
)21.096.0(36
)(),()(
55
1
0
11
)(
m a x
m a x
sf
xsfxs
sfxsvsf
kkkkk
Sx
kkkkk
SXx
kk
kk
kkk
边界条件：
基本方程：
上海财经大学 国际工商管理学院
SHUFE
32
第三节 应用举例
K=4
44
0
55444
0
44
36
)(),()(
m ax
m ax
44
44
xs
sfxsvsf
sx
sx
f4(s4)是关于 x4 的单增函数，故 x*4 =s4 时,f4(s4)最大,f4(s4)=9 s4
K=3
33
0
3333
0
433
0
44333
0
33
11.164.14
)21.096.0(936
936
)(),()(
m a x
m a x
m a x
m a x
33
33
33
33
xs
xsxs
sxs
sfxsvsf
sx
sx
sx
sx
f3(s3)是关于 x3 的单增函数，故 x*3 =s3 时,f3(s3)最大,f3(s3)=15.75 s3
上海财经大学 国际工商管理学院
SHUFE
33
第三节 应用举例
K=2
22
0
2222
0
322
0
33222
0
22
375.012.21
)21.096.0(75.1536
75.1536
)(),()(
m a x
m a x
m a x
m a x
22
22
22
22
xs
xsxs
sxs
sfxsvsf
sx
sx
sx
sx
f2(s2)是关于 x2 的单减函数，故 x*2 =0 时,f2(s2)最大,f2(s2)=21.12 s2
K=1
21
0
1111
0
311
0
22111
0
11
4 3 5 2.12 7 5 2.26
)21.096.0(12.2136
12.2136
)(),()(
m a x
m a x
m a x
m a x
11
11
11
11
xs
xsxs
sxs
sfxsvsf
sx
sx
sx
sx
f1(s1)是关于 x1 的单减函数，故 x*1 =0 时,f1(s1)最大,f1(s1)=26.275 s1
上海财经大学 国际工商管理学院
SHUFE
34
第三节 应用举例
最优生产策略,x*1 =0,x*2 =0,x*3 =s3,x*4 =s4
各阶段状态：
s1 =100,x*1 =0，
s2 = 0.96s1 – 0.21x1 = 0.96s1 =96,x*2=0，
s3 = 0.96s2 – 0.21x2 = 0.96s2 =92.16,x*2= s3,
s4 = 0.96s3 – 0.21x3 = 0.75s3 =69.12,x*4= s4
s5 = 0.96s4 – 0.21x4 = 0.75s4=51.84
