解 题

max
0x3 s3
8x3

5(s3

x3 )
13.6s4

max
0x3 s3
8
x3

5(s3

x3
)

13.6[0.7
x3

0.9(
s3

x3
)]
阶 段

max
0x3 s3
17.52
x3

17.24(
s3

x3
)
(逆序 解法）
同样的，f3 (s3 ) 是x3的线性单调增函数，
s1=1000， s2 0.7x1* 0.9(s1 x1* ) 0.9s1 900
s3 0.7x2* 0.9(s2 x2* ) 0.9s2 810 s4 0.7x3* 0.9(s3 x3* ) 0.7s3 729 s5 0.7x4* 0.9(s4 x4* ) 0.7s4 656
二、离散随机性动态规划
随机型的动态规划是指状态的转移律是不确定的，即 对给定的状态和决策，下一阶段的到达状态是具有确定概率 分布的随机变量，这个概率分布由本阶段的状态和决策完全 确定。随机型动态规划的基本结构如下图：
管理运筹学
16
图中：1、N表示第k+1阶段可能的状态数 能达 2、到p下1、一p2个、状…态pN的为概给率定。状态sk和决策xk的前提下，可 函数值3、。ci为从k阶段状态sk转移到k+1 阶段状态为i时的指标
如
不
结
合 格
论
阶
第2阶段试制3件产品
段 如 不 合 格
第3个阶段试制5件产品
管理运筹学
22
随机采购问题
例8 某公司打算在5周内采购一批原料，未来5周内的原料的价 格有三种，这些价格的出现概率可以估计，如下表。该部 分由于生产需要，必须在5周内采购这批原料。如果第一周 价格很高，可以等到第2周；同样的，第2周如果仍对价格 不满意，可以等到第3周；类似地，未来几周都可能选择购 买或者等待，但必须保证第5周时采购了该原料。试问该选 择哪种采购方案，才能使得采购费用最小？
过程的演变方式为确定性时，这种动态规划 问题就称为连续确定性动态规划问题。
管理运筹学
3
机器负荷分配问题
一种机器能在高低两种不同的负荷状态下工作。设机 器在高负荷下生产时，产量函数为P1=8u1，其中u1为在高 负荷状态下生产的机器数目，年完好率为a=0.7，即到年底 有70％的机器保持完好。在低负荷下生产时，产量函数为 P2=5u2，其中u2为在低负荷状态下生产的机器数目，年完 好率为b=0.9。设开始生产时共有1000台完好的机器，请 问每年应该如何把完好机器分配给高、低两种负荷下生产， 才能使得5年内生产的产品总产量最高。
f5(s5)

max
0x5 s5
8x5
5(s5

x5 )
f6 (s6 )
解 题 阶 段
max 0x5 s5
8x5
5(s5

x5 ) 0
max 0x5 s5
8x5
5(s5

x5 )
(逆序解 法）
因为f5(s5)是x5的线性单调增函数， 故有x5* =s5，
管理运筹学
4
1、阶段 ：分为5个阶段，每个阶段为1年。
2、状态变量sk： 设状态变量sk表示在第k阶段初拥有的完好机
器数目； k=1,2,3,4,5。
建
3、决策变量xk：决策变量xk表示第k阶段中分配给高负荷状态
模
下生产的机器数目；k=1,2,3,4,5。
阶
显然sk-xk为分配给低负荷状态下生产的机器数目。
4
s4
1000 900 810 567
23.72s1＝23720 20.75s2 17.5s3 13.6s4
5
s5
397
8s5
6
---
278
0
解得前两年应把年初完好机器完全投入低负荷生产，后三年
应把年初完好机器完全投入高负荷生产,才能使5年内生产的产
品总产量最高。
管理运筹学
上面所讨论的最优策略过程，初始端状态 s1=1000台是固定的，终点状态s6没有要求。这种情 况下得到最优决策称为初始端固定终点自由的最优 策略。
管理运筹学第十章：
动态规划应用（2）
小组成员：吴侃、朱优胜 潘建凤、杨婷 刘素琴、廖玉丹
管理运筹学
1
1、阶段
2、状态
3、决策
解 建模阶段 4、最优函数
题
5、状态转移方程
思 路
6、基本方程
解题阶段 逆序解法（例：第三 第二 第一）
结论阶段 即：列出最优解的结果
管理运筹学
2
一、连续确定性动态规划 对于状态变量和决策变量只取连续值，
望费用最小？
管理运筹学
18
1、阶段：三次试制当作三个阶段（k=1,2,3）
建
2、状态变量sk：表示第k次试制前是否已经生
模
产出合格品
阶
段
3、决策变量xk：表示第k次生产的产品件数
4、最优函数fk(sk)：表示从状态sk、决策xk出 发的第k阶段以后的最小期望费用。故有fk(0) ＝0。
管理运筹学
19
5(s1

x1)

f 2 (s2 )

max
0 x1 s1
8x1

5(s1

x1)

20.8s2
解 题 阶

max8
0 x1 s1
x1

5(
s1

x1
)

20.8[0.7
x1

0.9(
s1

x1
)
max 0 x1 s1
1.15x1

23.72s1
段
(逆序解 法）
5、状态转移方程：
p(sk1 1) 0.6xk
p(sk1 0) 1 0.6xk
建
模
6、基本方程：
阶 段
fk (1)
min xk
{c(
xk
)

(1

0.6
xk
)
f
k
1
(0)

0.6
xk
f k 1 (1)}

min xk
{c( xk
)

0.6 xk
f k1 (1)}
7、 C(xk)：表示第k阶段的费用，第k阶段的 费用包括制造成本和装配费用：
题
因此有：f5(s5)=s5，
ห้องสมุดไป่ตู้
阶
即：f5(500)=500；
段
f5(600)=600； f5(700)=700。
(逆序解法）
管理运筹学
25
第四阶段：如第4周购买，则需花费s4；如果不 买，则必须在第5周购买。在第5周采购的费用 的期望值为：s4E 0.3 f5 (500) 0.3 f5 (600) 0.4 f5 (700)
管理运筹学
可见，为了使终点完好的机器数量增加到500 台，需要安排前四年中全部完好机器都要投入低负 荷生产，且在第5年，也只能全部投入高负荷。
相应的最优指标为 f1(s1)=29.4s1-7500＝21900。
可以看到，因为增加了附加条件，总产量f1(s1) 要比终点自由情况下的产量要低。
管理运筹学
C
(
xk
)

2 0

xk
xk 0 xk 0
管理运筹学
20
x3
K
0
= s3
3
00
C(x3)+20× 0.6x3
1
2
3
4
5
6
f3(s3 x3*
)
—————0 0
1 20 15 11.2 9.32 8.59 8.56 8.93 8.56 5
解
x2
C(x2)+8.56× 0.6x2
题 阶
K
0

max
0x4 s4
8x4

5(s4

x4
)
18.5s5

7500

max
0x4 s4
21.7s4

0.7 x4

7500
容易解得 x4* 0 ，f4(s4)=21.7s4-7500。
管理运筹学
依次类推，得
x3* x2* x1* 0
f3(s3)=24.5s3-7500 f2(s2)=27.1s2-7500 f1(s1)=29.4s1-7500 再采用顺序方法递推计算各年的状态，有
显然，由于固定了终点的状态，x5的取值受到了 约束。因此有
f5 (s5 ) max8(4.5s5 2500) 5(s5 4.5s5 2500)
18.5s5 7500
类似的，
f4 (s4 )
max
0x4 s4
8x4
5(s4
x4 )
f5 (s5 )
如果终点附加一定的条件，则问题就称为“终 端固定问题”。例如，规定在第5年度结束时仍要 保持500台机器完好（而不是278台），应如何安排 生产才能使得总产量最大？
下面来分析：
根据终点条件有
s6 0.7x5 0.9(s5 x5 ) 500
可得
x5 4.5s5 2500
管理运筹学
1
2
3
4
5