第五章 动态规划多阶段决策过程的最优化动态规划的基本概念和基本原理本章内容重点动态规划是解决多阶段决策过程最优化问题的一种方法。由美国数学家 贝尔曼
（ Ballman）等人在 20世纪 50年代提出。他们针对 多阶段决策问题 的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理,工程技术等方面的许多实际问题。
动态规划的基本原理多阶段决策过程最优化多阶段决策过程是指这样一类特殊的活动过程，他们可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，
全部过程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问题。
状态
x1 阶段 1
T1
决策 u1
状态
x2
决策 u2
阶段 2
T2
状态
x3,..
状态
xk
决策 uk
阶段 k
Tk
状态
xk+1...
状态
xn
决策 un
阶段 n
Tn
状态
xn+1
多阶段决策问题举例属于多阶段决策类的问题很多,例如：
1)工厂生产过程,由于市场需求是一随着时间而变化的因素,因此,为了取得全年最佳经济效益,就要在全年的生产过程中,逐月或者逐季度地根据库存和需求情况决定生产计划安排 。 显然,可以把每个月作为一个阶段,全年分为 12个阶段 逐次决策 。
2)设备更新问题,一般企业用于生产活动的设备,
刚买来时故障少,经济效益高,即使进行转让,处理价值也高,随着使用年限的增加,就会逐渐变为故障多,维修费用增加,可正常使用的工时减少,加工质量下降,经济效益差,并且,使用的年限越长,处理价值也越低,自然,如果卖去旧的买新的,还需要付出更新费,因此就需要综合权衡决定设备的使用年限,
使总的经济效益最好 。
许多问题的发展过程都与时间因素有关。在这类多阶段决策问题中,阶段的划分常取时间区段 来表示，并且各个阶段上的决策往往也与时间因素有关。这就使它具有了“动态”的含义，
所以把处理这类动态问题的方法称为动态规划方法。
实际中尚有许多不包含时间因素的一类“静态”
决策问题，就其本质而言是一次决策问题，是非动态决策问题，但是也可以 人为地引入阶段的概念 当作多阶段决策问题，应用动态规划方法加以解决。
3） 资源分配问题,便属于这类静态问题 。 如：
某工业部门或公司,拟对其所属企业进行稀缺资源分配,为此需要制定出收益最大的资源分配方案 。
这种问题原本要求一次确定出对各企业的资源分配量,它与时间因素无关,不属动态决策,但是,我们可以人为地规定一个资源分配的阶段和顺序,从而使其变成一个多阶段决策问题 。
4） 运输网络问题,
动态规划模型的分类：
以“时间”角度可分成：
离散型 和连续型。
从信息确定与否可分成：
确定型 和随机型。
从目标函数的个数可分成：
单目标型 和多目标型。
例 5 - 1 （最短路线问题）如图 5 - 1,位于 A 城市的某药厂要把一批产品运往位于 E 城市的销售部．途中可能经过的城市有 8 个：
1B
,
2B
,
3B；
1C
,
2C
,
3C；
1D
,
2
D
．图中两连线上方的数字表示两城市之间的距离．从 A 到 E 走不同的路线，则所经过的城市不同，
因而总路程也不同，试求一条从 A 到 E 的运输路线，
使总路程最短,
第一节 动态规划的基本概念与方法
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4 34
2
3
9
5
5
9
8
7
3
8 4
6
6
6
1
如果用穷举法，先要计算从 A到 B的所有路径的距离，再取最小的路径。
1 阶段（ Stage）
将所给问题的过程，按时间顺序或空间特征分解成若干个相互联系的阶段，以便按次序去求每阶段的解，常用 k表示阶段变量。
我们把从 A到 E看成一个四阶段问题。
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4 34
2
3
9
5
5
9
8
7
3
8 4
A B C D E
6
6
6
1
一 二 三 四
2 状态（ State）
各阶段开始时的客观条件叫做 状态 。描述各阶段状态的变量称为状态变量，常用 sk表示第 k阶段的状态变量，状态变量的取值集合称为状态集合，用 Sk表示。
它应该能够描述过程的特征并且具有 无后向性,即当某阶段的状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关，即每个状态都是过去历史的一个完整总结。
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4 34
2
3
9
5
5
9
8
7
3
8 4
A B C D E
6
6
6
1
当 K=4时，其初始状态 D1或 D2
S4={D1,D2}
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4 34
2
3
9
5
5
9
8
7
3
8 4
A B C D E
6
6
6
1
当 K=3时，其初始状态 C1,C2 或 C3
S3={C1,C2,C3}
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4 34
2
3
9
5
5
9
8
7
3
8 4
A B C D E
6
6
6
1
当 K=2时，其初始状态 B1,B2 或 B3
S2={B1,B2,B3}
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4 34
2
3
9
5
5
9
8
7
3
8 4
A B C D E
6
6
6
1
当 K=1时，其初始状态 A
S1={A}
3.决策
当一个阶段的状态确定后,可以作出各种选择从而演变到下一阶段的某个状态,这种选择手段称为 决策 。
描述决策的变量称 决策变量 。
变量允许取值的范围称 允许决策集合 。 用 xk(sk)表示第 k阶段处于状态 sk时的决策变量,它是 sk的函数,用 Dk(sk)表示了 sk的允许决策集合 。
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4 34
2
3
9
5
5
9
8
7
3
8 4
6
6
6
1
S1={A} x1(A)= B1,x1(A)= B2,x1(A)= B3
D1(A)={B1,B2,B3}
4 状态转移方程动态规划中本阶段的状态往往是上一阶段的决策结果。如果给定了第 k段的状态 Sk,本阶段决策为 xk(Sk),
则第 k+1段的状态 Sk+1由公式,Sk+1=Tk（ Sk,Xk(Sk) ）
确定，称为状态转移方程。
5 指标函数用于衡量所选定策略优劣的数量指标称为指标函数。最优指标函数记为 fk(Sk)。
二、最优化原理和动态规划的基本方法
多阶段决策过程特点要点：阶段，状态，决策，状态转移方程基本思想：
从过程的最后一段开始，用逆序递推方法求解，逐步求出各段各点到终点 E最短路线，最后求出 A点到 E点的最短路线。
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4
3
4
2 39
5
5
9
8
7
3
8
4
6
6
6
1
4 1 1( ) ( ) 4f D d D E
f4(D1)=4
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4
3
4
2 39
5
5
9
8
7
3
8
4
6
6
6
1
f4(D1)=4
4 2 2( ) ( ) 3f D d D E
f4(D2)=3
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4
3
4
2 39
5
5
9
8
7
3
8
4
6
6
6
1
f4(D1)=4
f4(D2)=3
1 1 4 1
31
1 2 4 2
11
(,) ( )
( ) m in
(,) ( )
3 4 7
m in m in 7
5 3 8
C D f D
fC
C D f D
CD
最 优 决 策
f3(C1)=7
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4
3
4
2 39
5
5
9
8
7
3
8
4
6
6
6
1
f4(D1)=4
f4(D2)=3
2 1 4 1
32
2 2 4 2
22
(,) ( )
( ) m in
(,) ( )
6 4 10
m in m in 5
2 3 5
C D f D
fC
C D f D
CD
最 优 决 策
f3(C1)=7
f3(C2)=5
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4
3
4
2 39
5
5
9
8
7
3
8
4
6
6
6
1
f4(D1)=4
f4(D2)=3
3 1 4 1
33
3 2 4 2
31
(,) ( )
( ) m in
(,) ( )
1 4 5
m in m in 5
3 3 6
C D f D
fC
C D f D
CD
最 优 决 策
f3(C1)=7
f3(C2)=5
f3(C3)=5
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4
3
4
2 39
5
5
9
8
7
3
8
4
6
6
6
1
f4(D1)=4
f4(D2)=3
1 1 3 1
21
1 2 3 2
12
(,) ( )
( ) m in
(,) ( )
6 7 13
m in m in 9
4 5 9
B C f C
fB
B C f C
BC
最 优 决 策
f3(C1)=7
f3(C2)=5
f3(C3)=5
f2(B1)=9
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4
3
4
2 39
5
5
9
8
7
3
8
4
6
6
6
1
f4(D1)=4
f4(D2)=3
2 1 3 1
2 2 3 222
2 3 3 3
23
(,) ( )
(,) ( )( ) m in
(,) ( )
8 7 15
m in m in 117 5 12
6 5 11
B C f C
B C f CfB
B C f C
BC
最 优 决 策
f3(C1)=7
f3(C2)=5
f3(C3)=5
f2(B1)=9
f2(B2)=11
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4
3
4
2 39
5
5
9
8
7
3
8
4
6
6
6
1
f4(D1)=4
f4(D2)=3
3 2 3 2
23
3 3 3 3
2
(,) ( )
( ) m in
(,) ( )
8 5 13
m in m in 13 3
9 5 14
B C f C
fB
B C f C
BC
最 优 决 策
f3(C1)=7
f3(C2)=5
f3(C3)=5
f2(B1)=9
f2(B2)=11
f2(B3)=13
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4
3
4
2 39
5
5
9
8
7
3
8
4
6
6
6
1
f4(D1)=4
f4(D2)=3
f3(C1)=7
f3(C2)=5
f3(C3)=5
f2(B1)=9
f2(B2)=11
f2(B3)=13
1 2 1
2 2 21
3 2 3
1
(,) ( )
(,) ( )( ) m i n
(,) ( )
4 9 13
m i n m i n 139 11 20
5 13 18
A B f B
A B f BfA
A B f B
AB
最 优 决 策
f1(A)=13
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4
3
4
2 39
5
5
9
8
7
3
8
4
6
6
6
1
f4(D1)=4
f4(D2)=3
f3(C1)=7
f3(C2)=5
f3(C3)=5
f2(B1)=9
f2(B2)=11
f2(B3)=13
f1(A)=13
状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态
A
从 A到 E的最短路径为 13，路线为 A→B 1→C 2 →D 2→E
（ A,B1） B1 （ B1,C2） C2 （ C2,D2） D2 （ D2,E） E
从以上过程可以看出，每个阶段中，都求出本阶段的各个初始状态到终点 E的最短路径和最短距离，当逆序倒推到过程起点 A时，便得到了全过程的最短路径及最短距离，同时附带得到了一组最优结果（即各阶段的各状态到终点 E的最优结果）。
在上例的多阶段决策问题中，各个阶段采取的政策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有
“动态”的含义，称这种解决多阶段决策最优化问题的方法为 动态规划方法 。
动态规划是运筹学的一个分支。与其说动态规划是一种算法，不如说是一种思维方法来得更贴切。因为动态规划没有固定的框架，即便是应用到同一道题上，也可以建立多种形式的求解算法。
动态规划不像线性规划那样可以提供一套模式，需要的时候，取来就可以使用；它必须对具体问题进行具体分析处理，需要丰富的想象力去建立模型，需要创造性的思想去求解。
动态规划适于解决什么样的问题准确地说，动态规划不是万能的，它只适于解决一定条件的最优策略问题。
(1)状态必须满足最优化原理 ；
(2)状态必须满足无后效性 。
例 5-3 （ 资源分配问题 ）
某医药公司准备在甲、乙、丙三个地区设置四个销售点。
根据预测资料，在各地区设置个数不同销售点后，每月所得到的利润（单位：千元）见表。应如何确定在各地区销售点的个数，才能使每个月所获得的总利润最大。
用
ks
表示前 k 个地区设置的销售点个数，
kx
表示阶段 k 设置的销售点个数,
)( kk sf 表示前 k 个阶段销售点个数为
ks
时的最大利润值（ k= 1,2,3 ）,
表 5 - 10 利润统计表（单位：千元）
销售点个数地区
0 1 2 3 4
甲乙丙
0
0
0
16
13
12
28
24
22
40
34
36
50
42
47
（ Ballman）等人在 20世纪 50年代提出。他们针对 多阶段决策问题 的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理,工程技术等方面的许多实际问题。
动态规划的基本原理多阶段决策过程最优化多阶段决策过程是指这样一类特殊的活动过程，他们可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，
全部过程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问题。
状态
x1 阶段 1
T1
决策 u1
状态
x2
决策 u2
阶段 2
T2
状态
x3,..
状态
xk
决策 uk
阶段 k
Tk
状态
xk+1...
状态
xn
决策 un
阶段 n
Tn
状态
xn+1
多阶段决策问题举例属于多阶段决策类的问题很多,例如：
1)工厂生产过程,由于市场需求是一随着时间而变化的因素,因此,为了取得全年最佳经济效益,就要在全年的生产过程中,逐月或者逐季度地根据库存和需求情况决定生产计划安排 。 显然,可以把每个月作为一个阶段,全年分为 12个阶段 逐次决策 。
2)设备更新问题,一般企业用于生产活动的设备,
刚买来时故障少,经济效益高,即使进行转让,处理价值也高,随着使用年限的增加,就会逐渐变为故障多,维修费用增加,可正常使用的工时减少,加工质量下降,经济效益差,并且,使用的年限越长,处理价值也越低,自然,如果卖去旧的买新的,还需要付出更新费,因此就需要综合权衡决定设备的使用年限,
使总的经济效益最好 。
许多问题的发展过程都与时间因素有关。在这类多阶段决策问题中,阶段的划分常取时间区段 来表示，并且各个阶段上的决策往往也与时间因素有关。这就使它具有了“动态”的含义，
所以把处理这类动态问题的方法称为动态规划方法。
实际中尚有许多不包含时间因素的一类“静态”
决策问题，就其本质而言是一次决策问题，是非动态决策问题，但是也可以 人为地引入阶段的概念 当作多阶段决策问题，应用动态规划方法加以解决。
3） 资源分配问题,便属于这类静态问题 。 如：
某工业部门或公司,拟对其所属企业进行稀缺资源分配,为此需要制定出收益最大的资源分配方案 。
这种问题原本要求一次确定出对各企业的资源分配量,它与时间因素无关,不属动态决策,但是,我们可以人为地规定一个资源分配的阶段和顺序,从而使其变成一个多阶段决策问题 。
4） 运输网络问题,
动态规划模型的分类：
以“时间”角度可分成：
离散型 和连续型。
从信息确定与否可分成：
确定型 和随机型。
从目标函数的个数可分成：
单目标型 和多目标型。
例 5 - 1 （最短路线问题）如图 5 - 1,位于 A 城市的某药厂要把一批产品运往位于 E 城市的销售部．途中可能经过的城市有 8 个：
1B
,
2B
,
3B；
1C
,
2C
,
3C；
1D
,
2
D
．图中两连线上方的数字表示两城市之间的距离．从 A 到 E 走不同的路线，则所经过的城市不同，
因而总路程也不同，试求一条从 A 到 E 的运输路线，
使总路程最短,
第一节 动态规划的基本概念与方法
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4 34
2
3
9
5
5
9
8
7
3
8 4
6
6
6
1
如果用穷举法，先要计算从 A到 B的所有路径的距离，再取最小的路径。
1 阶段（ Stage）
将所给问题的过程，按时间顺序或空间特征分解成若干个相互联系的阶段，以便按次序去求每阶段的解，常用 k表示阶段变量。
我们把从 A到 E看成一个四阶段问题。
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4 34
2
3
9
5
5
9
8
7
3
8 4
A B C D E
6
6
6
1
一 二 三 四
2 状态（ State）
各阶段开始时的客观条件叫做 状态 。描述各阶段状态的变量称为状态变量，常用 sk表示第 k阶段的状态变量，状态变量的取值集合称为状态集合，用 Sk表示。
它应该能够描述过程的特征并且具有 无后向性,即当某阶段的状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关，即每个状态都是过去历史的一个完整总结。
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4 34
2
3
9
5
5
9
8
7
3
8 4
A B C D E
6
6
6
1
当 K=4时，其初始状态 D1或 D2
S4={D1,D2}
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4 34
2
3
9
5
5
9
8
7
3
8 4
A B C D E
6
6
6
1
当 K=3时，其初始状态 C1,C2 或 C3
S3={C1,C2,C3}
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4 34
2
3
9
5
5
9
8
7
3
8 4
A B C D E
6
6
6
1
当 K=2时，其初始状态 B1,B2 或 B3
S2={B1,B2,B3}
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4 34
2
3
9
5
5
9
8
7
3
8 4
A B C D E
6
6
6
1
当 K=1时，其初始状态 A
S1={A}
3.决策
当一个阶段的状态确定后,可以作出各种选择从而演变到下一阶段的某个状态,这种选择手段称为 决策 。
描述决策的变量称 决策变量 。
变量允许取值的范围称 允许决策集合 。 用 xk(sk)表示第 k阶段处于状态 sk时的决策变量,它是 sk的函数,用 Dk(sk)表示了 sk的允许决策集合 。
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4 34
2
3
9
5
5
9
8
7
3
8 4
6
6
6
1
S1={A} x1(A)= B1,x1(A)= B2,x1(A)= B3
D1(A)={B1,B2,B3}
4 状态转移方程动态规划中本阶段的状态往往是上一阶段的决策结果。如果给定了第 k段的状态 Sk,本阶段决策为 xk(Sk),
则第 k+1段的状态 Sk+1由公式,Sk+1=Tk（ Sk,Xk(Sk) ）
确定，称为状态转移方程。
5 指标函数用于衡量所选定策略优劣的数量指标称为指标函数。最优指标函数记为 fk(Sk)。
二、最优化原理和动态规划的基本方法
多阶段决策过程特点要点：阶段，状态，决策，状态转移方程基本思想：
从过程的最后一段开始，用逆序递推方法求解，逐步求出各段各点到终点 E最短路线，最后求出 A点到 E点的最短路线。
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4
3
4
2 39
5
5
9
8
7
3
8
4
6
6
6
1
4 1 1( ) ( ) 4f D d D E
f4(D1)=4
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4
3
4
2 39
5
5
9
8
7
3
8
4
6
6
6
1
f4(D1)=4
4 2 2( ) ( ) 3f D d D E
f4(D2)=3
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4
3
4
2 39
5
5
9
8
7
3
8
4
6
6
6
1
f4(D1)=4
f4(D2)=3
1 1 4 1
31
1 2 4 2
11
(,) ( )
( ) m in
(,) ( )
3 4 7
m in m in 7
5 3 8
C D f D
fC
C D f D
CD
最 优 决 策
f3(C1)=7
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4
3
4
2 39
5
5
9
8
7
3
8
4
6
6
6
1
f4(D1)=4
f4(D2)=3
2 1 4 1
32
2 2 4 2
22
(,) ( )
( ) m in
(,) ( )
6 4 10
m in m in 5
2 3 5
C D f D
fC
C D f D
CD
最 优 决 策
f3(C1)=7
f3(C2)=5
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4
3
4
2 39
5
5
9
8
7
3
8
4
6
6
6
1
f4(D1)=4
f4(D2)=3
3 1 4 1
33
3 2 4 2
31
(,) ( )
( ) m in
(,) ( )
1 4 5
m in m in 5
3 3 6
C D f D
fC
C D f D
CD
最 优 决 策
f3(C1)=7
f3(C2)=5
f3(C3)=5
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4
3
4
2 39
5
5
9
8
7
3
8
4
6
6
6
1
f4(D1)=4
f4(D2)=3
1 1 3 1
21
1 2 3 2
12
(,) ( )
( ) m in
(,) ( )
6 7 13
m in m in 9
4 5 9
B C f C
fB
B C f C
BC
最 优 决 策
f3(C1)=7
f3(C2)=5
f3(C3)=5
f2(B1)=9
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4
3
4
2 39
5
5
9
8
7
3
8
4
6
6
6
1
f4(D1)=4
f4(D2)=3
2 1 3 1
2 2 3 222
2 3 3 3
23
(,) ( )
(,) ( )( ) m in
(,) ( )
8 7 15
m in m in 117 5 12
6 5 11
B C f C
B C f CfB
B C f C
BC
最 优 决 策
f3(C1)=7
f3(C2)=5
f3(C3)=5
f2(B1)=9
f2(B2)=11
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4
3
4
2 39
5
5
9
8
7
3
8
4
6
6
6
1
f4(D1)=4
f4(D2)=3
3 2 3 2
23
3 3 3 3
2
(,) ( )
( ) m in
(,) ( )
8 5 13
m in m in 13 3
9 5 14
B C f C
fB
B C f C
BC
最 优 决 策
f3(C1)=7
f3(C2)=5
f3(C3)=5
f2(B1)=9
f2(B2)=11
f2(B3)=13
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4
3
4
2 39
5
5
9
8
7
3
8
4
6
6
6
1
f4(D1)=4
f4(D2)=3
f3(C1)=7
f3(C2)=5
f3(C3)=5
f2(B1)=9
f2(B2)=11
f2(B3)=13
1 2 1
2 2 21
3 2 3
1
(,) ( )
(,) ( )( ) m i n
(,) ( )
4 9 13
m i n m i n 139 11 20
5 13 18
A B f B
A B f BfA
A B f B
AB
最 优 决 策
f1(A)=13
A
B3
B2
B1
C3
C2
C1
D2
D1
E
4
3
4
2 39
5
5
9
8
7
3
8
4
6
6
6
1
f4(D1)=4
f4(D2)=3
f3(C1)=7
f3(C2)=5
f3(C3)=5
f2(B1)=9
f2(B2)=11
f2(B3)=13
f1(A)=13
状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态
A
从 A到 E的最短路径为 13，路线为 A→B 1→C 2 →D 2→E
（ A,B1） B1 （ B1,C2） C2 （ C2,D2） D2 （ D2,E） E
从以上过程可以看出，每个阶段中，都求出本阶段的各个初始状态到终点 E的最短路径和最短距离，当逆序倒推到过程起点 A时，便得到了全过程的最短路径及最短距离，同时附带得到了一组最优结果（即各阶段的各状态到终点 E的最优结果）。
在上例的多阶段决策问题中，各个阶段采取的政策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有
“动态”的含义，称这种解决多阶段决策最优化问题的方法为 动态规划方法 。
动态规划是运筹学的一个分支。与其说动态规划是一种算法，不如说是一种思维方法来得更贴切。因为动态规划没有固定的框架，即便是应用到同一道题上，也可以建立多种形式的求解算法。
动态规划不像线性规划那样可以提供一套模式，需要的时候，取来就可以使用；它必须对具体问题进行具体分析处理，需要丰富的想象力去建立模型，需要创造性的思想去求解。
动态规划适于解决什么样的问题准确地说，动态规划不是万能的，它只适于解决一定条件的最优策略问题。
(1)状态必须满足最优化原理 ；
(2)状态必须满足无后效性 。
例 5-3 （ 资源分配问题 ）
某医药公司准备在甲、乙、丙三个地区设置四个销售点。
根据预测资料，在各地区设置个数不同销售点后，每月所得到的利润（单位：千元）见表。应如何确定在各地区销售点的个数，才能使每个月所获得的总利润最大。
用
ks
表示前 k 个地区设置的销售点个数，
kx
表示阶段 k 设置的销售点个数,
)( kk sf 表示前 k 个阶段销售点个数为
ks
时的最大利润值（ k= 1,2,3 ）,
表 5 - 10 利润统计表（单位：千元）
销售点个数地区
0 1 2 3 4
甲乙丙
0
0
0
16
13
12
28
24
22
40
34
36
50
42
47
