4.3.1 建摸
1、理论依据 -----最优化原理最优化原理：
一个过程的最优策略具有这样的性质，
即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策必构成最优策略
2、动态规划模型的几个 要素,
1)阶段数 k
2)状态变量 sk
3)决策变量 uk （ sk ）
4)指标函数 Vk,n
状态转移方程
kkk usTs,1
5)最优值函数 fk(sk)
3、建立动态规划模型的 基本要求,
1）所研究的问题必须能够分成几个相互联系的阶段，而且在每一个阶段都具有需要进行决策的问题。
2）在每一阶段都必须有若干个与该阶段相关的状态一般情况下，状态是所研究系统在该阶段可能处于的情况或条件建模时总是从与决策有关的条件中，或是从问题的约束条件中去选择状态变量。
3)具有明确的指标函数，且阶段指标值可以计算
4)能正确列出最优值函数的递推公式和边界条件
（ b）能通过现阶段的决策，使当前状态转移成下一阶段的状态即 能够给出状态转移方程kkk usTs,1
（ c）状态的无后效性之前的过程无关最优策略应与的为出发点的后部子过程阶段的状态即以第
k
k
s
sk
状态的选取必须注意以下几个要点：
（ a）在所研究问题的各阶段，都能直接或间接确定状态变量的取值例 （ 资源分配问题 ） 某公司有资金 a万元，拟投资于
n个项目，已知对第 i个项目投资 xi万元，收益为
g i (xi)，问应如何分配资金可使总收益最大？
解：阶段 k=1,2,…,n
状态变量 sk
决策变量 uk,第 k个项目的投资额
：在第 k阶段时可以用于投资第 k到第 n个项目的资金数状态转移方程,sk+1 = sk -uk
指标函数 Vk,n
n
ki
ii ug：
：第 k阶段可分配的资金数为 sk时，
第 k至第 n个项目的最大总收益
}0|{ kkkk suuU
kk sf最优值函数
af1求
kk sf
边界条件：
k=n,n-1,…,2,1
011 nn sf
资源分配问题的动态规划基本方程,





0
1,2,,1,m a x
11
110
nn
kkkksukk
sf
nnksfugsf
kk
建立递推公式,
kk ug11 kk sf
kk su0
m a x
：在第 k阶段分配的资金数为 sk时，
第 k至第 n个项目的最大总收益
kk sf最优值函数某种机器的工作系统由 n个部件串联组成，只要有一个部件失灵，整个系统就不能正常工作。为提高系统工作的可靠性，在每一个部件上均装有主要元件的备用件，并设计了备用元件自动投入装置。显然，备用元件越多，整个系统的可靠性越大，但备用元件增多也会导致系统的成本、重量相应增大。设部件 i(i=1,2,…,n) 上装有 xi个备用元件时，正常工作的概率为 pi （ xi ）。设装一个 i部件的设备元件费用为 ci,重量 wi为，要求整个系统所装备用元件的总费用不超过 C，总重量不超过
W，问如何选择个部件的备用元件数，使整个系统的工作可靠性最大？
例 复合系统工作可靠性问题解：设 A---整个系统正常工作,Ai—部件 i正常工作满足,Cxcn
i
ii
1
Wxw
n
i
ii
1
且为整数0?ix
非线性规划问题
nAPAPAPAP?21?则
,21 nAAAA
iin
i
xp
1?

iin
i
xpP
1
m a x
数学模型为：求系统由 n个部件串联组成，每一个部件上装有备用件，部件 i(i=1,2,…,n) 上装有 xi个备用元件时，正常工作的概率为
pi （ xi ）。设装一个 i部件的设备元件费用为 ci,重量 wi为，
要求总费用不超过 C，总重量不超过 W，问如何选择个部件的备用元件数，使整个系统的工作可靠性最大？
例 复合系统工作可靠性问题解,n个部件 =n个阶段决策变量 uk = 部件 k上所装的备用元件数 xk
状态变量：
sk =第 k个到第 n个部件可使用的总费用
yk =第 k个到第 n个部件容许的总重量状态转移方程：

kkkk ucss 1
kkkk uwyy 1
指标函数 Vk,n
ii
n
ki
up

最优指标函数 fk(sk,yk ） = 在部件 k，可使用的总费用为 sk，总重量为 yk 时，从部件 k
到部件 n的系统工作可靠性的最大值

ku
m a x111, kkkkk ysfup
KU?
复合系统工作可靠性的动态规划 基本方程 为：
kkk ysf,

1,111 nnn ysf
与问题无关
WCf,1求
1,2,,1, nnk
动态规划基本方程,





0
1,2,,1,
11
11
nn
kkkk
u
kk
sf
nnksfugo p tsf
k





1
1,2,,1,
11
11
nn
kkkk
u
kk
sf
nnksfugoptsf
k
或
4.4.2 动态规划模型的 求解解法
离散型连续型
：分段穷举法
：利用解析方法或线性规划方法没有固定的方法具体模型具体分析要求,经验,技巧、灵活难！
投资额工厂 1 2 3
1 4.5 2 5
2 7 4.5 7
3 9 7.5 8
4 10.5 11 10
5 12 15 13
一、离散变量的 分段穷举法例（资源分配问题）某有色金属公司拟拨出 50万元对所属三家冶炼厂进行技术改造，若以十万元为最少分割单位，各厂收益与投资的关系如下表：
问：对三个工厂如何分配，
才能使总收益达到最大？
状态变量 sk：
阶段 k=1,2,3
决策变量 uk：
给工厂 k的投资额在第 k阶段时可供工厂 k到工厂 3分配的资金数
kk su0
状态转移方程：
sk+1 = sk -uk
g k (uk)=给工厂 k投资
uk（十万元）的收益指标函数 Vk,n
3
ki
ii ug


110
m a x kkkk
sukk
sfugsf
kk
fk（ sk ）
投资工厂 k至工厂 3所得的最大总收益求 f1（ 5 ）
=在工厂 k，可供分配的资金数为 sk时，
ku
m ax11 kkkk sfug
kk su0
044?sf
基本方程：
k=3
3s
0
3u 0
1
1
2
2
3
3
)( 33 sf 0 5 7 8
4 5
4 5
10 13
投资额工厂 1 2 3
1 4.5 2 5
2 7 4.5 7
3 9 7.5 8
4 10.5 11 10
5 12 15 13
1,2,3?k
33033
33
m a x ugsf su
*3u 0 1 2 3 4 5
k=2
2s
2u
)( 22 sf
0
0
32 fg?
0
0
1
*2u
0
2
0 1
5 2
0
5
0 1 2
7 7 4.5
0或 1
7
3
0 1 2 3
8 9 9.5 7.5
2
9.5
4 5
0 1 2 3 4
10 10 11.512.511
3
12.5
0 1 2 3 4 5
13 12 12.514.5 16 15
4
16
3322022
22
m a x sfugsf su
投资额工厂 1 2 3
1 4.5 2 5
2 7 4.5 7
3 9 7.5 8
4 10.5 11 10
5 12 15 13
sk+1 = sk -uk
3s
0
3u 0
1
1
2
2
3
3
)( 33 sf 0 5 7 8
4 5
4 5
10 13
*3u 0 1 2 3 4 5
k=1
2211011
11
m a x sfugsf su
sk+1 = sk -uk
投资额工厂 1 2 3
1 4.5 2 5
2 7 4.5 7
3 9 7.5 8
4 10.5 11 10
5 12 15 13
1s
1u
)( 11 sf
2211 sfug?
*1u
5
16
0 1 2 3 4 5
17 16.5 16 15.5 12
1
17
最大总收益：
十万元）(17)5(1?f
最优策略：
1*1?u 3,*2?u 1,*3?u
2s
2u
)( 22 sf
0
0
32 fg?
0
0
1
*2u
0
2
0 1
5 2
0
5
0 1 2
7 7 4.5
0或 1
7
3
0 1 2 3
8 9 9.5 7.5
2
9.5
4 5
0 1 2 3 4
10 10 11.512.511
3
12.5
0 1 2 3 4 5
13 12 12.514.5 16 15
4
16
二、连续变量的解法例（季节工问题）某工厂的生产任务随季节波动，为降低成本宜用季节临时工，但熟练的生产工人临时难以聘到，培训新手费用又高，
各季节工人需用量如下表所示，每季节超过需用量聘用，每人浪费 2000元，聘用或解聘费为 200元乘上两个季节聘用人数之差的平方，
问厂长一年中应如何聘用工人可使总花费最小？（假定工资按实际工作时间计算，则聘用人数可为分数）
季度 i 春 夏 秋 冬 春需用量 gk 255 220 240 200 255
方案 1,255 220 240 200 255
总费用,+200× 352200× 552 +200× 202+200× 402
=1249000
方案 2,255 245 245 245 255
总费用,+[200× 102200× 102 +2000× 25]
+2000× 5 +2000× 45 =190000
解：
阶段 1
，状态变量 sk—第 k-1季度聘用人数决策变量 uk—第 k季度聘用人数状态转移方程,sk+1 = uk
fk（ sk） =第 k-1季度聘用人数为 sk人时，第 k季度到第 4季度的最小总费用
,220≤s2≤ 255
gk≤uk≤255
季度 i 春 夏 秋 冬 春需用量 gk 255 220 240 200 255
2 3 4
k=1,2,34
s1=255,240≤s3≤ 255,200≤s4≤ 255
已知：每季节超过需用量聘用，每人浪费 2000元，聘用和解聘费为 200元乘上两个季节聘用人数之差的平方
=min{ }+fk+1（ sk+1）+2000(uk –gk)
gk≤uk≤255
200(uk –uk-1)2
求 f1（ 255）
=min{ }+fk+1（ uk）+2000(uk –gk)
gk≤uk≤255
200(uk –sk)2
基本方程：
fk（ sk） = min{ }+fk+1（ uk）
f5（ s5） =0
求 f1（ 255）
+2000(uk –gk)
gk≤uk≤255
200(uk –sk)2
min{ }f4（ s4） = +2000(u4 –g4)
g4≤u4≤255
200(u4 –s4)2
u*4=255=200(255 –s4)2
,200≤s4≤ 255当 k=4时
min{ }f3（ s3） = +f4（ u3）+2000(u3 –g3)200(u3 –s3)2
g3≤u3≤255
=min{ }+2000(u3 –200)200(u3 –s3)2
200≤u3≤255
+200(255 –u3)2
当 k=3时,240≤s3≤ 255
k=4,3,2,1
f3（ s3） =min{ }+2000(u3 –200)200(u3 –s3)2
200≤u3≤255
+200(255 –u3)2
233233 2 5 52 0 02 0 02 0 0 02 0 0 uusuh令
333
3
2554002000400 usududh则 10000400800 33 su
0
3
dudh令 12521 33 su得 0800
2
3
2

du
hd且
1 2 521* 33 su
为最小值点即 1 2 521 33 su
所以 f3（ s3） = 2
33
2
3 211 3 02 0 075212 0 0 0211 2 52 0 0 sss
23323 2 6 0501 5 01 0 0 02 5 050 sss
当 k=3时,240≤s3≤ 255
255,2003?u
min{ }
min{ }f2（ s2） = +f3（ u2）+2000(u2 –g2)200(u2 –s2)2
g2≤u2≤255
fk（ sk） = +fk+1（ uk）+2000(uk –gk)g
k≤uk≤255
200(uk –sk)2
已知：
f3（ s3） 2
3323 2 6 0501 5 01 0 0 02 5 050 sss
当 k=2时,220≤s2≤ 255
=min{ }+2000(u2 –240)200(u2 –s2)2
240≤u2≤255 +f3（ u2）
=min{ } 5 8 7 5 0 0 04 8 0 0 0400200300
222222 ussu
240≤u2≤255
状态转移方程,sk+1 = uk
f2（ s2）
当 k=2时,220≤s2≤ 255
=min{ } 5 8 7 5 0 0 04 8 0 0 0400200300
222222 ussu
240≤u2≤255
2du
dh 4 8 0 0 04 0 06 0 0 22 su 0
2
dudh令 8032 22 su得
06 0 02
2
2
du hd且
8032*,22 su
所以 f2（ s2） =
5 8 7 5 0 0 04 8 0 0 0400200300 222222 ussuh令
5 8 7 5 0 0 0)8032(4 8 0 0 0400200)8032(300 222222 ssss
3955000320003200 222 ss
2 5 5,2 4 02?u
为最小值点即 8032 22 su
min{ }fk（ sk） = +fk+1（ uk）+2000(uk –gk)
gk≤uk≤255
200(uk –sk)2
已知：
f2（ s2） 395500032000
3
200
2
2
2 ss
当 k=1时,s1=255
min{ }f1（ 255） = +f2（ u1）+2000(u1 –g1)
g1≤u1≤255
200(u1 –s1)2
=min{ }+2000(u1 –220)
220≤u1≤255
200(u1 –255)2
3 9 5 5 0 0 03 2 0 0 03200 121 uu
状态转移方程,sk+1 = uk
3 2 0 0 034 0 02 0 0 0)2 5 5(4 0 0 11
1
uududh 1 3 2 0 0 03
1 6 0 0
1 u
0
1
dudh令 5.2 4 71?u得 0
3
1600
2
1
2
du hd且 为最小值点即 5.2 4 71?u
f1（ 255） =185000 5.2 4 7*
1?u
f4（ s4） = u*4=255200(255 –s4)2
1 2 521* 33 su
33 sf 23323 2 6 0501 5 01 0 0 02 5 050 sss
8032* 22 suf2（ s2） 395500032000
3
200
2
2
2 ss
5.2 4 7*1?uf1（ 255） =185000
最优策略,5.2 4 7*
1?u 805.2 4 732*2u
=245
1 2 52 4 521*3u
=247.5 u*4=255
最少总费用：为 185000元状态转移方程,sk+1 = uk
最佳聘用方案：
夏季 247.5人，秋季 245人，冬季 247.5人，春季 255人时，