文档介绍：关于运筹学动态规划
第1页，讲稿共28张，创作于星期三
多阶段决策问题：是动态决策问题的一种特殊形式。在多阶段决策过程中，系统的动态过程可以按照时间进程分为相互联系而又相互区别的各个阶段，而且在每个阶段都要进行决策。目的是使整个。换句话说，过程的过去历史只能通过当前的状态去影响它未来的发展，这个性质称为无后效性。在构造决策过程的动态规划模型时，要充分注意是否满足无后效性的要求。如果状态不能满足无后效性的要求，应适当地改变状态的定义或规定方法，以使状态变量能满足无后效性的要求。
状态具有无后效性的多阶段决策过程的状态转移方程如下
能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即具有无后效性的多阶段决策过程。
动态规划中能
处理的状态转移
方程的形式。
第7页，讲稿共28张，创作于星期三
5 策略：策略是一个按顺序排列的决策组成的集合。由过程的第k阶段开始到终止状态为止的过程，称为问题的后部子过程（或称为k子过程）。由每段的决策按顺序排列组成的决策函数序列称为k子过程策略，简称子策略，记为pk,n(sk)，即
当k=1时，此决策函数序列成为全过程的一个策略，简称策略，记为p1,n (s1).即
在实际问题中，可供选择的策略有一定范围，此范围称为允许策略集合，用p表示。从允许策略集合中找出达到最优效果的策略称为最优策略。
6 指标函数和最优值函数：用来衡量所实现过程优劣的一种数量指标，称为指标函数，它是定义在全过程或所有后部子过程上确定的数量函数。Vk, n表示之。即
第8页，讲稿共28张，创作于星期三
动态规划模型的指标函数，应具有可分离性，并满足递推关系。即Vk,n可以表示为sk,uk,Vk+1,n的函数。
常见的指标函数的形式是：
过程和它的任一子过程的指标是它所包含的各阶段的指标和。即
其中vj(sj,uj)表示第j阶段的阶段指标。这时上式可写成
无后效性的结果。
第9页，讲稿共28张，创作于星期三
过程和它的任意子过程的指标是它所包含的各阶段的指标的乘积。即
则可改写成
最优值函数：表示从第k阶段的状态sk开始到第n阶段的终止状态的过程，采取最优策略所得到的指标函数值。即
第10页，讲稿共28张，创作于星期三
多阶段决策过程的数学模型：（具有无后效性的多阶段决策过程）
所谓求解多阶段决策过程问题，就是要求出
（1） 最优策略，即最优决策序列
（2） 最优轨线，即执行最优策略时的状态序列
第11页，讲稿共28张，创作于星期三
（3）最优目标函数值
f1(s1)
从k到终点最优
子策略的最优目标函数值
第12页，讲稿共28张，创作于星期三
第三节：动态规划的基本思想和基本方程
以最短路问题的解法为例来说明。（穷举法48条路线）
A
B1
B2
C1
C2
C3
C4
D1
D2
D3
E1
E2
E3
F1
F2
G
5
3
1
3
6
8
7
6
6
8
3
5
3
3
8
4
2
2
1
2
3
3
3
5
5
2
6
6
4
3
1
2
3
4
5
6
第13页，讲稿共28张，创作于星期三
最短路的特性：如果已有从起点到终点的一条最短路，那么从最短路线上中间任何一点出发到终点的路线仍然是最短路。（证明:用反证法）
当k=6时,由F1到终点G只有一条路线，故f6(F1)=，f6(F2)=3.
当k=5时，出发点有E1,E2,E3三个。
u5(E1)=F1
E1 F1 G
u5(E2)=F2
E2 F2 G
u5(E3)=F2
E3 F3 G
第14页，讲稿共28张，创作于星期三
当k=4时，有
当k=3时，有
当k=2时，有
第15页，讲稿共28张，创作于星期三
当k=1时，有
且u1(A)=B1，于是得到从起点A到终点G的最短距离为18。
为了找到最短路线,再按计算的顺序反推之,可求出最优决策函数序列{uk}：u1(A)=B1,u2(B1)=C2,u3=(C2)=D1,u4(D1)=E2,u5(E2)=F2,u6(F2)=G，
即最优策略。
最短路线为AB1C2D1E2F2G。
A
B1
B2
C1
C2
C3
C4
D1
D2
D3
E1
E2
E3
F1
F2
G
5
3
1
3
6
8
7
6
8
3
5
3
3
8
4
2
2
1
2
3
3
3
5
5
2
6
6
4
3
6
0
4
3
7
5
9