Page:1
QSC华东理工大学 工商经济学院 运筹学运筹学动态规划
Page:2
QSC华东理工大学 工商经济学院 运筹学生产－库存问题月份 (k ) 1 2 3 4 5 6 7
生产成本 (c k ) 11 18 13 17 20 10 15
需求量 (r k ) 0 8 5 3 2 7 4
产品仓库容量 H=9。期初库存量为 2，要求期末（七月底）库存量为 0。每个月生产的产品在月末入库。求最优生产计划 xk
Page:3
QSC华东理工大学 工商经济学院 运筹学分析处理方法静态处理 —— 线性 (整数 )规划动态处理 —— 动态规划
Page:4
QSC华东理工大学 工商经济学院 运筹学生产－库存问题的动态结构生 产系 统
1 月 初 库 存 量,
s 1 = 0
生 产 量 x 1
决 策 准 则,
生 产 成 本 c 1 x 1 最 小生 产系 统
2 月 初 库 存 量,
s 2
生 产 量 x 2
3 月 初 库 存 量,
s 3
决 策 准 则,
生 产 成 本 c 2 x 2 最 小生 产系 统生 产 量 x 7
7 月 底 库 存 量,
s 8 ＝ 0
决 策 准 则,
生 产 成 本 c 7 x 7 最 小
7 月 初 库 存 量,
s 7
Page:5
QSC华东理工大学 工商经济学院 运筹学阶段最优与总体最优之间的非一致性每一阶段的最优决策未必能保证总体最优总体最优并不能保证每一阶段最优能否通过阶段决策达到总体最优目标？
在什么条件下总体最优包含了阶段最优？
Page:6
QSC华东理工大学 工商经济学院 运筹学一般多阶段决策问题的结构阶 段
1
S 1
决 策 X 1
指 标 值
r 1 ( S 1,X 1 )
阶 段
2
S 2
决 策 X 2
S 3 阶 段
n
决 策 X n
S nS n - 1
指 标 值
r 2 ( S 2,X 2 )
指 标 值
r n ( S n,X n )
Sj,j阶段初系统所处状态
Xj,j阶段所作决策
rj(Sj,Xj),j阶段在状态 Sj下作决策 Xj得到的收益 (成本 )
Page:7
QSC华东理工大学 工商经济学院 运筹学允许状态集合
—— 每一阶段可能初始状态的全体
S S S,j = 1,2,,nj j1 j2?,,
Page:8
QSC华东理工大学 工商经济学院 运筹学决策空间
—— 每一阶段决策变量的允许取值空间
X Sj j( ) ( )? D Sj j
Page:9
QSC华东理工大学 工商经济学院 运筹学状态变换
—— 每一阶段的初始状态经决策变量的作用产生下一阶段的初始状态
S (S Xj + 1 j j? T,)
Page:10
QSC华东理工大学 工商经济学院 运筹学策略
—— 从初始阶段到最终阶段，每一阶段的决策所形成的序列
P S S Sn n1 1 2,( ) ( ),( ),( )S X X,X1 1 2 n
Page:11
QSC华东理工大学 工商经济学院 运筹学子策略
—— 从 k阶段到最终阶段，每一阶段的决策所形成的序列
P S S Sk n k k k k k n,(S ) ( ),( ),( )X X,X+ 1 n1
Page:12
QSC华东理工大学 工商经济学院 运筹学最优指标函数
——当 k阶段的状态为 Sk，并采取 最优子策略
P S S Sk n k k k k k n,(S ) ( ),( ),( )X X,X+ 1 n1
此时得到的从 k到 n+1各阶段指标值的总和：
f (S ) O p t r (S,X ) r (S,X ) r (S,X )k k k k k k + 1 k + 1 k 1 n n n
Page:13
QSC华东理工大学 工商经济学院 运筹学
Bellman最优性原理
“作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面决策所形成的状态，余下的决策必然形成最优子策略,
Page:14
QSC华东理工大学 工商经济学院 运筹学动态规划递归方程
f (S ) O p t r (S,X ) f (S )
k n,n 1,,1
f (S ) 0 ( o r ) 1
k k
X D (S )
k k k k 1 k 1
n 1 n 1
k k k
Page:15
QSC华东理工大学 工商经济学院 运筹学建立动态规划模型及求解步骤划分阶段确定状态变量及允许状态集合确定决策变量及决策空间确定状态转移方程确定转移指标函数并建立递归方程
Page:16
QSC华东理工大学 工商经济学院 运筹学最短路径问题的应用
BA
CB
D
B
C
D
E
C
2
1
2
3
1
2
3
1
2
5
1
12
14
10
6
10
4
13
12
11
3
9
6
5
8
10
5
2
找出 A到 E的最短路径
Page:17
QSC华东理工大学 工商经济学院 运筹学阶段划分
BA
CB
D
B
C
D
E
C
2
1
2
3
1
2
3
1
2
5
1
12
14
10
6
10
4
13
12
11
3
9
6
5
8
10
5
2
I IVIIIII
Page:18
QSC华东理工大学 工商经济学院 运筹学将 A到 E的最短路径问题，转化为三个性质完全相同，但规模较小的子问题求解策略记 S(x)为节点 x到 E的最短路
)(mi n)(,iBAi BSdAS i
)(m i n)(,jCBji CSdBS ji
)(mi n)(,kDCkj DSdCS kj
)( kDS
Page:19
QSC华东理工大学 工商经济学院 运筹学求解
S(D1)=5,S(D2)=2
S C
S D
S D
C D( ) m i n
( )
( )
m i n,1 1
2
1 1
3
9
3 5
9 2
8?
S C
S D
S D
C D( ) m i n
( )
( )
m i n,2 1
2
2 2
6
5
6 5
5 2
7?
S C
S D
S D
C D( ) m i n
( )
( )
m i n,3 1
2
3 2
8
10
8 5
10 2
12?
S(C1)=8； S(C2)=7； S(C3)=12
Page:20
QSC华东理工大学 工商经济学院 运筹学
S B
S C
S C
S C
B C( ) m i n
( )
( )
( )
m i n,1
1
2
3
1 1
12
14
10
12 8
14 7
10 12
20?
S B
S C
S C
S C
B C( ) m i n
( )
( )
( )
m i n,2
1
2
3
2 1
6
10
4
6 8
10 7
4 12
14?
S B
S C
S C
S C
B C( ) m i n
( )
( )
( )
m i n,3
1
2
3
3 2
13
12
11
13 8
12 7
11 12
19?
S(C1)=8； S(C2)=7； S(C3)=12
Page:21
QSC华东理工大学 工商经济学院 运筹学
S(B1)=20； S(B2)=14； S(B3)=19
S A
S B
S B
S B
A B( ) m i n
( )
( )
( )
m i n,?
2
5
1
2 20
5 14
1 19
19
1
2
3
2
Page:22
QSC华东理工大学 工商经济学院 运筹学
BA
CB
D
B
C
D
E
C
2
1
2
3
1
2
3
1
2
5
1
12
14
10
6
10
4
13
12
11
3
9
6
5
8
10
5
2
0
5
2
8
7
12
20
14
18
19
最优解
Page:23
QSC华东理工大学 工商经济学院 运筹学资源分配问题
1 万元 15 万吨 13 万吨 11 万吨
2 万元 28 万吨 29 万吨 30 万吨
3 万元 40 万吨 43 万吨 45 万吨
4 万元 51 万吨 55 万吨 58 万吨
A B C
项目投入资金有资金 4万元,投资 A,B,C三个项目,每个项目的投资效益与投入该项目的资金有关 。 三个项目 A,B,C的投资效益
（ 万吨 ） 和投入资金 （ 万元 ） 的关系见下表：
求对三个项目的最优投资分配,使总投资效益最大 。
Page:24
QSC华东理工大学 工商经济学院 运筹学项目 A 项目 B 项目 C
指标值 (收益 )
V1(s1,x1)
指标值 (收益 )
V2(s2,x2)
指标值 (收益 )
V3(s3,x3)
s1 s2 s3 s4
x1 x2 x3
阶段 k,每投资一个项目作为一个阶段；
状态变量 sk,投资第 k个项目前的资金余额；
决策变量 xk,第 k个项目的投资额；
决策允许集合,Dk(sk)={0≤xk≤sk}
状态转移方程,sk+1=sk-xk
阶段指标,vk(sk,xk)见表中所示 ；
递推方程,fk(sk)=max{vk(sk,xk)+fk+1(sk+1)}
终端条件,f4(s4)=0
Page:25
QSC华东理工大学 工商经济学院 运筹学
s
3
D
3
(s
3
) s
4
v
3
(s
3
,x
3
) v
3
(s
3
,x
3
)+f
4
(s
4
) f
3
(s
3
) x
3
*
0 0 0 0 0+ 0= 0 0 0
0 1 0 0+ 0= 0
1 0 11 11+ 0= 11*
0 2 0 0+ 0= 0
1 1 11 11+ 0= 11
2 0 30 30+ 0= 30*
0 3 0 0+ 0= 0
1 2 11 11+ 0= 11
2 1 30 30+ 0= 30
3 0 45 45+ 0= 45*
0 4 0 0+ 0= 0
1 3 11 11+ 0= 11
2 2 30 30+ 0= 30
3 1 45 45+ 0= 45
4 0 58 58+ 0= 58*
1 11 1
2 30 2
3 45 3
4 58 4
k=4,f4(s4)=0; k=3,0≤ x3≤ s3,s4=s3-x3
Page:26
QSC华东理工大学 工商经济学院 运筹学
k=2,0≤ x2≤ s2,s3=s2-x2
s
2
D
2
( s 2) s
3
v
2
(s
2
,x
2
) v
2
(s
2
,x
2
) + f
3
(s
3
) f
2
(s
2
) x
2
*
0 0 0 0 0+ 0= 0 0 0
0 1 0 0+ 11= 11
1 0 13 13+ 0= 13*
0 2 0 0+ 30= 30*
1 1 13 13+ 11= 24
2 0 29 29+ 0= 29
0 3 0 0+ 45= 45*
1 2 13 13+ 30= 43
2 1 29 29+ 11= 40
3 0 43 43+ 0= 43
0 4 0 0+ 58= 58
1 3 13 13+ 45= 58
2 2 29 29+ 30= 59*
3 1 43 43+ 11= 54
4 0 55 55+ 0= 55
1 13 1
2 30 0
3 45 0
4 59 2
Page:27
QSC华东理工大学 工商经济学院 运筹学
k=1,0≤ x1≤ s1,s2=s1-x1
s 1 D 1 (s 1 ) s 2 v 1 (s 1,x 1 ) v 1 (s 1,x 1 ) + f 2 (s 2 ) f 1 (s 1 ) x 1 *
0 4 0 0+59=59
1 3 15 15 + 45 = 60 *
2 2 28 28 + 30 = 58
3 1 40 40 + 13 = 53
4 0 51 51 + 0=51
4 60 1
最优解为,
s1=4,x1*=1,
s2=s1-x1=3,x2*=0,最大效益为 60万吨
s3=s2-x2*=3,x3*=3,
s4=s3-x3=0
Page:28
QSC华东理工大学 工商经济学院 运筹学机器负荷分配问题某种机器可以在高、低两种负荷下生产。高负荷生产条件下机器完好率为 0.7，即如果年初有 u台完好机器投入生产，则年末完好的机器数量为 0.7u台。
系数 0.7称为完好率。年初投入高负荷运行的 u台机器的年产量为 8u吨。系数 8称为单台产量。低负荷运行时，机器完好率为 0.9，单台产量为 5吨。设开始时有 1000台完好机器，要制订五年计划，每年年初将完好的机器一部分分配到高负荷生产，剩下的机器分配到低负荷生产，使五年的总产量为最高。
Page:29
QSC华东理工大学 工商经济学院 运筹学第
1
年
s1 s2 s3
x1 x2 x3
第
2
年第
3
年第
4
年第
5
年
s4 s5 s6
x4 x5
指标值
(产量 )
V1(s1,x1)
指标值
(产量 )
V2(s2,x2)
指标值
(产量 )
V5(s5,x5)
指标值
(产量 )
V4(s4,x4)
指标值
(产量 )
V3(s3,x3)
Page:30
QSC华东理工大学 工商经济学院 运筹学动态规划模型构造阶段 k,运行年份 （ k=1,2,3,4,5,6） ；
状态变量 xk,第 k年初完好的机器数 （ k=1,2,3,4,5,6） ；
决策变量 dk,第 k年投入高负荷运行的机器数；
状态转移方程,sk+1=0.7xk+0.9(sk-xk)
决策允许集合,Dk(sk)={xk|0?xk?sk}
阶段指标,vk(sk,xk)=8xk+5(sk-xk)
终端条件,f6(s6)=0
递推方程：
fk(sk)=max{vk(sk,xk)+fk+1(sk+1)}
xk?Dk(sk)
=max{8xk+5(sk-xk)+fk+1[0.7xk+0.9(sk-xk)]}
0?xk?sk
Page:31
QSC华东理工大学 工商经济学院 运筹学
555
sx0
66555
sx0
55
853xm a x
)(sf)x5 ( s8xm a x)(sf
55
55
ss
5
*
5 sx?
第
5
年
s5 s6
x5
指标值
(产量 )
V5(s5,x5)
…
+f6(s6)
Page:32
QSC华东理工大学 工商经济学院 运筹学
444
sx0
444444
sx0
5444
sx0
55444
sx0
44
1 3,7 s1 2,3 s1,4 xm ax
)]x0,9 ( s8 [ 0,7 x)x5 ( s8xm ax
8s)x5 ( s8xm ax
)(sf)x5 ( s8xm ax)(sf
44
44
44
44
4
*
4 sx?
第
4
年
s4 s5
x4
指标值
(产量 )
V4(s4,x4)
…
+f5(s5)
Page:33
QSC华东理工大学 工商经济学院 运筹学
f3(s3)=max{8x3+5(s3-x3)+f4(s4)}
0?x3?s3
=max{8x3+5(s3-x3)+13.7s4}
0?x3?s3
=max{8d3+5(s3-d3)+13.7[0.7d3+0.9(s3-d3)]}
0?x3?s3
=max{0.28x3+17.24s3}=17.52s3
0?x3?s3
x3*=s3
s3
x3
第
3
年
s4
指标值
(产量 )
V3(s3,x3)
…
+f4(s4)
Page:34
QSC华东理工大学 工商经济学院 运筹学
f2(s2)=max{8x2+5(s2-x2)+f3(s3)}
0?x2?s2
=max{8x2+5(s2-x2)+17.52s3}
0?x2?s2
=max{8x2+5(s2-x2)+17.52[0.7x2+0.9(s2-x2)]}
0?x2?s2
=max{-0.504x2+20.77s2}=20.77s2
0?x2?s2
x2*=0
s2 s3
x2
第
2
年指标值
(产量 )
V2(s2,x2)
…
+f3(s3)
Page:35
QSC华东理工大学 工商经济学院 运筹学
f1(s1)=max{8x1+5(s1-x1)+f2(s2)}
0?x1?s1
=max{8x1+5(s1-x1)+20.77s2}
0?x1?s1
=max{8x1+5(s1-x1)+20.77[0.7x1+0.9(s1-x1)]}
0?x1?s1
=max{-0.05x1+23.69s1}=23.69s1
0?x1?s1
x1*=0
第
1
年
s1 s2
x1
指标值
(产量 )
V1(s1,x1)
…
+f2(s2)
Page:36
QSC华东理工大学 工商经济学院 运筹学由此可以得到：
f1(s1)=23.69s1,x1*=0
f2(s2)=20.77s2,x2*=0
f3(s3)=17.52s3,x3*=s3
f4(s4)=13.60s4,x4*=s4
f5(s5)=8s5 x5*=s5
用 s1=1000代入，得到五年最大产量为
f1(s1)=f1(1000)=23690
Page:37
QSC华东理工大学 工商经济学院 运筹学每年投入高负荷运行的机器数以及每年初完好的机器数为：
s1=1000
x1*=0,s2=0.7x1+0.9(s1-x1)=900
x2*=0,s3=0.7x2+0.9(s2-x2)=810
x3*=s3=810,s4=0.7x3+0.9(s3-x3)=567
x4*=s4=567,s5=0.7x4+0.9(s4-x4)=397
x5*=s5=397,s6=0.7x5+0.9(s5-x5)=278
Page:38
QSC华东理工大学 工商经济学院 运筹学生产－库存问题生 产系 统
1 月 初 库 存 量,
s 1 = 0
生 产 量 x 1
决 策 准 则,
生 产 成 本 c 1 x 1 最 小生 产系 统
2 月 初 库 存 量,
s 2
生 产 量 x 2
3 月 初 库 存 量,
s 3
决 策 准 则,
生 产 成 本 c 2 x 2 最 小生 产系 统生 产 量 x 7
7 月 底 库 存 量,
s 8 ＝ 0
决 策 准 则,
生 产 成 本 c 7 x 7 最 小
7 月 初 库 存 量,
s 7
Page:39
QSC华东理工大学 工商经济学院 运筹学一个工厂生产某种产品,1～ 7月份生产成本和产品需求量的变化情况如下表：
月份 ( k ) 1 2 3 4 5 6 7
生产成本 (c k ) 11 18 13 17 20 10 15
需求量 (r k ) 0 8 5 3 2 7 4
为了调节生产生产和需求，工厂设有一个产品仓库，库容量 H=9。已知期初库存量为 2，要求期末
（七月低）库存量为 0。每个月生产的产品在月末入库，月初根据当月需求发货。求七个月的生产量，能满足各月的需求，并使生产成本最低,。
Page:40
QSC华东理工大学 工商经济学院 运筹学阶段 k,月份,k=1,2,…,7,8；
状态变量 sk,第 k个月初 （ 发货以前 ） 的库存量；
决策变量 xk,第 k个月的生产量；
状态转移方程,sk+1=sk-rk+xk；
决策允许集合,Dk(sk)={xk| xk?0,rk+1?sk+1?H}
={xk | xk?0,rk+1?sk-rk+xk?H}；
阶段指标,vk(sk,xk)=ckxk；
终端条件,f8(s8)=0,s8=0；
递推方程,fk(sk)=min{vk(sk,xk)+fk+1(sk+1)}
xk?Dk(sk)
=min{ckxk+fk+1(sk-rk+xk)}
xk?Dk(sk)
Page:41
QSC华东理工大学 工商经济学院 运筹学设备更新问题一台设备的价格为 P，运行寿命为 n年，每年的维修费用是设备役龄的函数，记为 C(t)，新设备的役龄为 t=0。旧设备出售的价格是设备役龄的函数，记为 S(t)。在 n年末，役龄为 t的设备残值为 R(t)。现有一台役龄为 T的设备，在使用过程中，使用者每年都面临,继续使用,或
,更新,的策略 。
Page:42
QSC华东理工大学 工商经济学院 运筹学阶段 k：运行年份；
状态变量 sk：设备的役龄 t；
决策变量 xk：
状态转移方程：
阶段指标：
继续使用更新
)(
)( R e
K e e pK
p l a c eRx
k
Kxs
Rx
s
kk
k
k 1
1
1
KxtC
RxtSCP
KxsC
RxsSCP
v
k
k
kk
kk
k
)(
)()0(
)(
)()0(
Page:43
QSC华东理工大学 工商经济学院 运筹学递推方程：
终端条件：
fn(t)=-R(t)
KxtftC
RxftSCP
KxsfsC
RxsfsSCP
sf
kk
kk
kkkk
kkkk
kk
)1()(
)1()()0(
m i n
)()(
)()()0(
m i n)(
1
1
11
11
QSC华东理工大学 工商经济学院 运筹学运筹学动态规划
Page:2
QSC华东理工大学 工商经济学院 运筹学生产－库存问题月份 (k ) 1 2 3 4 5 6 7
生产成本 (c k ) 11 18 13 17 20 10 15
需求量 (r k ) 0 8 5 3 2 7 4
产品仓库容量 H=9。期初库存量为 2，要求期末（七月底）库存量为 0。每个月生产的产品在月末入库。求最优生产计划 xk
Page:3
QSC华东理工大学 工商经济学院 运筹学分析处理方法静态处理 —— 线性 (整数 )规划动态处理 —— 动态规划
Page:4
QSC华东理工大学 工商经济学院 运筹学生产－库存问题的动态结构生 产系 统
1 月 初 库 存 量,
s 1 = 0
生 产 量 x 1
决 策 准 则,
生 产 成 本 c 1 x 1 最 小生 产系 统
2 月 初 库 存 量,
s 2
生 产 量 x 2
3 月 初 库 存 量,
s 3
决 策 准 则,
生 产 成 本 c 2 x 2 最 小生 产系 统生 产 量 x 7
7 月 底 库 存 量,
s 8 ＝ 0
决 策 准 则,
生 产 成 本 c 7 x 7 最 小
7 月 初 库 存 量,
s 7
Page:5
QSC华东理工大学 工商经济学院 运筹学阶段最优与总体最优之间的非一致性每一阶段的最优决策未必能保证总体最优总体最优并不能保证每一阶段最优能否通过阶段决策达到总体最优目标？
在什么条件下总体最优包含了阶段最优？
Page:6
QSC华东理工大学 工商经济学院 运筹学一般多阶段决策问题的结构阶 段
1
S 1
决 策 X 1
指 标 值
r 1 ( S 1,X 1 )
阶 段
2
S 2
决 策 X 2
S 3 阶 段
n
决 策 X n
S nS n - 1
指 标 值
r 2 ( S 2,X 2 )
指 标 值
r n ( S n,X n )
Sj,j阶段初系统所处状态
Xj,j阶段所作决策
rj(Sj,Xj),j阶段在状态 Sj下作决策 Xj得到的收益 (成本 )
Page:7
QSC华东理工大学 工商经济学院 运筹学允许状态集合
—— 每一阶段可能初始状态的全体
S S S,j = 1,2,,nj j1 j2?,,
Page:8
QSC华东理工大学 工商经济学院 运筹学决策空间
—— 每一阶段决策变量的允许取值空间
X Sj j( ) ( )? D Sj j
Page:9
QSC华东理工大学 工商经济学院 运筹学状态变换
—— 每一阶段的初始状态经决策变量的作用产生下一阶段的初始状态
S (S Xj + 1 j j? T,)
Page:10
QSC华东理工大学 工商经济学院 运筹学策略
—— 从初始阶段到最终阶段，每一阶段的决策所形成的序列
P S S Sn n1 1 2,( ) ( ),( ),( )S X X,X1 1 2 n
Page:11
QSC华东理工大学 工商经济学院 运筹学子策略
—— 从 k阶段到最终阶段，每一阶段的决策所形成的序列
P S S Sk n k k k k k n,(S ) ( ),( ),( )X X,X+ 1 n1
Page:12
QSC华东理工大学 工商经济学院 运筹学最优指标函数
——当 k阶段的状态为 Sk，并采取 最优子策略
P S S Sk n k k k k k n,(S ) ( ),( ),( )X X,X+ 1 n1
此时得到的从 k到 n+1各阶段指标值的总和：
f (S ) O p t r (S,X ) r (S,X ) r (S,X )k k k k k k + 1 k + 1 k 1 n n n
Page:13
QSC华东理工大学 工商经济学院 运筹学
Bellman最优性原理
“作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面决策所形成的状态，余下的决策必然形成最优子策略,
Page:14
QSC华东理工大学 工商经济学院 运筹学动态规划递归方程
f (S ) O p t r (S,X ) f (S )
k n,n 1,,1
f (S ) 0 ( o r ) 1
k k
X D (S )
k k k k 1 k 1
n 1 n 1
k k k
Page:15
QSC华东理工大学 工商经济学院 运筹学建立动态规划模型及求解步骤划分阶段确定状态变量及允许状态集合确定决策变量及决策空间确定状态转移方程确定转移指标函数并建立递归方程
Page:16
QSC华东理工大学 工商经济学院 运筹学最短路径问题的应用
BA
CB
D
B
C
D
E
C
2
1
2
3
1
2
3
1
2
5
1
12
14
10
6
10
4
13
12
11
3
9
6
5
8
10
5
2
找出 A到 E的最短路径
Page:17
QSC华东理工大学 工商经济学院 运筹学阶段划分
BA
CB
D
B
C
D
E
C
2
1
2
3
1
2
3
1
2
5
1
12
14
10
6
10
4
13
12
11
3
9
6
5
8
10
5
2
I IVIIIII
Page:18
QSC华东理工大学 工商经济学院 运筹学将 A到 E的最短路径问题，转化为三个性质完全相同，但规模较小的子问题求解策略记 S(x)为节点 x到 E的最短路
)(mi n)(,iBAi BSdAS i
)(m i n)(,jCBji CSdBS ji
)(mi n)(,kDCkj DSdCS kj
)( kDS
Page:19
QSC华东理工大学 工商经济学院 运筹学求解
S(D1)=5,S(D2)=2
S C
S D
S D
C D( ) m i n
( )
( )
m i n,1 1
2
1 1
3
9
3 5
9 2
8?
S C
S D
S D
C D( ) m i n
( )
( )
m i n,2 1
2
2 2
6
5
6 5
5 2
7?
S C
S D
S D
C D( ) m i n
( )
( )
m i n,3 1
2
3 2
8
10
8 5
10 2
12?
S(C1)=8； S(C2)=7； S(C3)=12
Page:20
QSC华东理工大学 工商经济学院 运筹学
S B
S C
S C
S C
B C( ) m i n
( )
( )
( )
m i n,1
1
2
3
1 1
12
14
10
12 8
14 7
10 12
20?
S B
S C
S C
S C
B C( ) m i n
( )
( )
( )
m i n,2
1
2
3
2 1
6
10
4
6 8
10 7
4 12
14?
S B
S C
S C
S C
B C( ) m i n
( )
( )
( )
m i n,3
1
2
3
3 2
13
12
11
13 8
12 7
11 12
19?
S(C1)=8； S(C2)=7； S(C3)=12
Page:21
QSC华东理工大学 工商经济学院 运筹学
S(B1)=20； S(B2)=14； S(B3)=19
S A
S B
S B
S B
A B( ) m i n
( )
( )
( )
m i n,?
2
5
1
2 20
5 14
1 19
19
1
2
3
2
Page:22
QSC华东理工大学 工商经济学院 运筹学
BA
CB
D
B
C
D
E
C
2
1
2
3
1
2
3
1
2
5
1
12
14
10
6
10
4
13
12
11
3
9
6
5
8
10
5
2
0
5
2
8
7
12
20
14
18
19
最优解
Page:23
QSC华东理工大学 工商经济学院 运筹学资源分配问题
1 万元 15 万吨 13 万吨 11 万吨
2 万元 28 万吨 29 万吨 30 万吨
3 万元 40 万吨 43 万吨 45 万吨
4 万元 51 万吨 55 万吨 58 万吨
A B C
项目投入资金有资金 4万元,投资 A,B,C三个项目,每个项目的投资效益与投入该项目的资金有关 。 三个项目 A,B,C的投资效益
（ 万吨 ） 和投入资金 （ 万元 ） 的关系见下表：
求对三个项目的最优投资分配,使总投资效益最大 。
Page:24
QSC华东理工大学 工商经济学院 运筹学项目 A 项目 B 项目 C
指标值 (收益 )
V1(s1,x1)
指标值 (收益 )
V2(s2,x2)
指标值 (收益 )
V3(s3,x3)
s1 s2 s3 s4
x1 x2 x3
阶段 k,每投资一个项目作为一个阶段；
状态变量 sk,投资第 k个项目前的资金余额；
决策变量 xk,第 k个项目的投资额；
决策允许集合,Dk(sk)={0≤xk≤sk}
状态转移方程,sk+1=sk-xk
阶段指标,vk(sk,xk)见表中所示 ；
递推方程,fk(sk)=max{vk(sk,xk)+fk+1(sk+1)}
终端条件,f4(s4)=0
Page:25
QSC华东理工大学 工商经济学院 运筹学
s
3
D
3
(s
3
) s
4
v
3
(s
3
,x
3
) v
3
(s
3
,x
3
)+f
4
(s
4
) f
3
(s
3
) x
3
*
0 0 0 0 0+ 0= 0 0 0
0 1 0 0+ 0= 0
1 0 11 11+ 0= 11*
0 2 0 0+ 0= 0
1 1 11 11+ 0= 11
2 0 30 30+ 0= 30*
0 3 0 0+ 0= 0
1 2 11 11+ 0= 11
2 1 30 30+ 0= 30
3 0 45 45+ 0= 45*
0 4 0 0+ 0= 0
1 3 11 11+ 0= 11
2 2 30 30+ 0= 30
3 1 45 45+ 0= 45
4 0 58 58+ 0= 58*
1 11 1
2 30 2
3 45 3
4 58 4
k=4,f4(s4)=0; k=3,0≤ x3≤ s3,s4=s3-x3
Page:26
QSC华东理工大学 工商经济学院 运筹学
k=2,0≤ x2≤ s2,s3=s2-x2
s
2
D
2
( s 2) s
3
v
2
(s
2
,x
2
) v
2
(s
2
,x
2
) + f
3
(s
3
) f
2
(s
2
) x
2
*
0 0 0 0 0+ 0= 0 0 0
0 1 0 0+ 11= 11
1 0 13 13+ 0= 13*
0 2 0 0+ 30= 30*
1 1 13 13+ 11= 24
2 0 29 29+ 0= 29
0 3 0 0+ 45= 45*
1 2 13 13+ 30= 43
2 1 29 29+ 11= 40
3 0 43 43+ 0= 43
0 4 0 0+ 58= 58
1 3 13 13+ 45= 58
2 2 29 29+ 30= 59*
3 1 43 43+ 11= 54
4 0 55 55+ 0= 55
1 13 1
2 30 0
3 45 0
4 59 2
Page:27
QSC华东理工大学 工商经济学院 运筹学
k=1,0≤ x1≤ s1,s2=s1-x1
s 1 D 1 (s 1 ) s 2 v 1 (s 1,x 1 ) v 1 (s 1,x 1 ) + f 2 (s 2 ) f 1 (s 1 ) x 1 *
0 4 0 0+59=59
1 3 15 15 + 45 = 60 *
2 2 28 28 + 30 = 58
3 1 40 40 + 13 = 53
4 0 51 51 + 0=51
4 60 1
最优解为,
s1=4,x1*=1,
s2=s1-x1=3,x2*=0,最大效益为 60万吨
s3=s2-x2*=3,x3*=3,
s4=s3-x3=0
Page:28
QSC华东理工大学 工商经济学院 运筹学机器负荷分配问题某种机器可以在高、低两种负荷下生产。高负荷生产条件下机器完好率为 0.7，即如果年初有 u台完好机器投入生产，则年末完好的机器数量为 0.7u台。
系数 0.7称为完好率。年初投入高负荷运行的 u台机器的年产量为 8u吨。系数 8称为单台产量。低负荷运行时，机器完好率为 0.9，单台产量为 5吨。设开始时有 1000台完好机器，要制订五年计划，每年年初将完好的机器一部分分配到高负荷生产，剩下的机器分配到低负荷生产，使五年的总产量为最高。
Page:29
QSC华东理工大学 工商经济学院 运筹学第
1
年
s1 s2 s3
x1 x2 x3
第
2
年第
3
年第
4
年第
5
年
s4 s5 s6
x4 x5
指标值
(产量 )
V1(s1,x1)
指标值
(产量 )
V2(s2,x2)
指标值
(产量 )
V5(s5,x5)
指标值
(产量 )
V4(s4,x4)
指标值
(产量 )
V3(s3,x3)
Page:30
QSC华东理工大学 工商经济学院 运筹学动态规划模型构造阶段 k,运行年份 （ k=1,2,3,4,5,6） ；
状态变量 xk,第 k年初完好的机器数 （ k=1,2,3,4,5,6） ；
决策变量 dk,第 k年投入高负荷运行的机器数；
状态转移方程,sk+1=0.7xk+0.9(sk-xk)
决策允许集合,Dk(sk)={xk|0?xk?sk}
阶段指标,vk(sk,xk)=8xk+5(sk-xk)
终端条件,f6(s6)=0
递推方程：
fk(sk)=max{vk(sk,xk)+fk+1(sk+1)}
xk?Dk(sk)
=max{8xk+5(sk-xk)+fk+1[0.7xk+0.9(sk-xk)]}
0?xk?sk
Page:31
QSC华东理工大学 工商经济学院 运筹学
555
sx0
66555
sx0
55
853xm a x
)(sf)x5 ( s8xm a x)(sf
55
55
ss
5
*
5 sx?
第
5
年
s5 s6
x5
指标值
(产量 )
V5(s5,x5)
…
+f6(s6)
Page:32
QSC华东理工大学 工商经济学院 运筹学
444
sx0
444444
sx0
5444
sx0
55444
sx0
44
1 3,7 s1 2,3 s1,4 xm ax
)]x0,9 ( s8 [ 0,7 x)x5 ( s8xm ax
8s)x5 ( s8xm ax
)(sf)x5 ( s8xm ax)(sf
44
44
44
44
4
*
4 sx?
第
4
年
s4 s5
x4
指标值
(产量 )
V4(s4,x4)
…
+f5(s5)
Page:33
QSC华东理工大学 工商经济学院 运筹学
f3(s3)=max{8x3+5(s3-x3)+f4(s4)}
0?x3?s3
=max{8x3+5(s3-x3)+13.7s4}
0?x3?s3
=max{8d3+5(s3-d3)+13.7[0.7d3+0.9(s3-d3)]}
0?x3?s3
=max{0.28x3+17.24s3}=17.52s3
0?x3?s3
x3*=s3
s3
x3
第
3
年
s4
指标值
(产量 )
V3(s3,x3)
…
+f4(s4)
Page:34
QSC华东理工大学 工商经济学院 运筹学
f2(s2)=max{8x2+5(s2-x2)+f3(s3)}
0?x2?s2
=max{8x2+5(s2-x2)+17.52s3}
0?x2?s2
=max{8x2+5(s2-x2)+17.52[0.7x2+0.9(s2-x2)]}
0?x2?s2
=max{-0.504x2+20.77s2}=20.77s2
0?x2?s2
x2*=0
s2 s3
x2
第
2
年指标值
(产量 )
V2(s2,x2)
…
+f3(s3)
Page:35
QSC华东理工大学 工商经济学院 运筹学
f1(s1)=max{8x1+5(s1-x1)+f2(s2)}
0?x1?s1
=max{8x1+5(s1-x1)+20.77s2}
0?x1?s1
=max{8x1+5(s1-x1)+20.77[0.7x1+0.9(s1-x1)]}
0?x1?s1
=max{-0.05x1+23.69s1}=23.69s1
0?x1?s1
x1*=0
第
1
年
s1 s2
x1
指标值
(产量 )
V1(s1,x1)
…
+f2(s2)
Page:36
QSC华东理工大学 工商经济学院 运筹学由此可以得到：
f1(s1)=23.69s1,x1*=0
f2(s2)=20.77s2,x2*=0
f3(s3)=17.52s3,x3*=s3
f4(s4)=13.60s4,x4*=s4
f5(s5)=8s5 x5*=s5
用 s1=1000代入，得到五年最大产量为
f1(s1)=f1(1000)=23690
Page:37
QSC华东理工大学 工商经济学院 运筹学每年投入高负荷运行的机器数以及每年初完好的机器数为：
s1=1000
x1*=0,s2=0.7x1+0.9(s1-x1)=900
x2*=0,s3=0.7x2+0.9(s2-x2)=810
x3*=s3=810,s4=0.7x3+0.9(s3-x3)=567
x4*=s4=567,s5=0.7x4+0.9(s4-x4)=397
x5*=s5=397,s6=0.7x5+0.9(s5-x5)=278
Page:38
QSC华东理工大学 工商经济学院 运筹学生产－库存问题生 产系 统
1 月 初 库 存 量,
s 1 = 0
生 产 量 x 1
决 策 准 则,
生 产 成 本 c 1 x 1 最 小生 产系 统
2 月 初 库 存 量,
s 2
生 产 量 x 2
3 月 初 库 存 量,
s 3
决 策 准 则,
生 产 成 本 c 2 x 2 最 小生 产系 统生 产 量 x 7
7 月 底 库 存 量,
s 8 ＝ 0
决 策 准 则,
生 产 成 本 c 7 x 7 最 小
7 月 初 库 存 量,
s 7
Page:39
QSC华东理工大学 工商经济学院 运筹学一个工厂生产某种产品,1～ 7月份生产成本和产品需求量的变化情况如下表：
月份 ( k ) 1 2 3 4 5 6 7
生产成本 (c k ) 11 18 13 17 20 10 15
需求量 (r k ) 0 8 5 3 2 7 4
为了调节生产生产和需求，工厂设有一个产品仓库，库容量 H=9。已知期初库存量为 2，要求期末
（七月低）库存量为 0。每个月生产的产品在月末入库，月初根据当月需求发货。求七个月的生产量，能满足各月的需求，并使生产成本最低,。
Page:40
QSC华东理工大学 工商经济学院 运筹学阶段 k,月份,k=1,2,…,7,8；
状态变量 sk,第 k个月初 （ 发货以前 ） 的库存量；
决策变量 xk,第 k个月的生产量；
状态转移方程,sk+1=sk-rk+xk；
决策允许集合,Dk(sk)={xk| xk?0,rk+1?sk+1?H}
={xk | xk?0,rk+1?sk-rk+xk?H}；
阶段指标,vk(sk,xk)=ckxk；
终端条件,f8(s8)=0,s8=0；
递推方程,fk(sk)=min{vk(sk,xk)+fk+1(sk+1)}
xk?Dk(sk)
=min{ckxk+fk+1(sk-rk+xk)}
xk?Dk(sk)
Page:41
QSC华东理工大学 工商经济学院 运筹学设备更新问题一台设备的价格为 P，运行寿命为 n年，每年的维修费用是设备役龄的函数，记为 C(t)，新设备的役龄为 t=0。旧设备出售的价格是设备役龄的函数，记为 S(t)。在 n年末，役龄为 t的设备残值为 R(t)。现有一台役龄为 T的设备，在使用过程中，使用者每年都面临,继续使用,或
,更新,的策略 。
Page:42
QSC华东理工大学 工商经济学院 运筹学阶段 k：运行年份；
状态变量 sk：设备的役龄 t；
决策变量 xk：
状态转移方程：
阶段指标：
继续使用更新
)(
)( R e
K e e pK
p l a c eRx
k
Kxs
Rx
s
kk
k
k 1
1
1
KxtC
RxtSCP
KxsC
RxsSCP
v
k
k
kk
kk
k
)(
)()0(
)(
)()0(
Page:43
QSC华东理工大学 工商经济学院 运筹学递推方程：
终端条件：
fn(t)=-R(t)
KxtftC
RxftSCP
KxsfsC
RxsfsSCP
sf
kk
kk
kkkk
kkkk
kk
)1()(
)1()()0(
m i n
)()(
)()()0(
m i n)(
1
1
11
11
