文档介绍：动态规划------多阶段决策过程的最优化问题
数学教研室赵立强
2002年6月
一、动态规划的基本方法
在多阶段决策问题中,各个阶段采取的决策一般来说是与时间有关的,决策依赖于当前的状态,而又随即引起状态的转移,一个决策序列就是在状态的运动变化中产生的,固有“动态的含义”。因此,把处理它的方法称为动态规划方法。
多阶段决策过程及实例1
例1.(最短路线问题)如图5-1所示,给出一个线路网络,A为始点,G为终点,两点之间的连线可以表示道路、管道等,连线上的数字表示两点间的距离(或费用)。试选择一条由A到G的线路,使总距离(或费用)为最小。
A
B2
B1
F2
F1
E3
E2
E1
D2
D1
G
C2
C3
C1
C4
D3
5
3
1
3
6
8
7
6
6
8
3
5
3
3
8
4
2
2
2
1
3
3
3
5
5
2
6
6
4
3
多阶段决策过程及实例2
例2(生产一存储问题) 某工厂根据市场调研情况,需制定今后四个月的生产计划,据估计,在这四个月内,市场对该产品需求量如下表所示。
月份(k)
1
2
3
4
需求量(Dk)
2
3
2
4
假定生产每批产品的固定成本费用为3千元,每单位产品生产成本费用为1千元,。并且规定1月初和4月末均无产品库存,试求该厂如何安排各个月的生产与库存,使总成本费用最小。
动态规划的基本概念和基本方程1
1、动态规划的基本概念
阶段
--人为合理划分、独立又相联系的阶段
状态
状态表示在任何一阶段所处的位置。通常一个阶段有若干个状态。描述状态的变量成为状态变量。参数表示第k阶段的状态变量。
决策
在某一阶段,当状态给定后,往往可以作出不同的决定,从而确定下一阶段的状态,这种决定成为决策。描述决策的变量称为决策变量,用表示第k阶段当状态为时的决策变量,它是状态的函数。
动态规划的基本概念和基本方程2
允许决策集
决策变量的取值范围,表示为
状态转移方程
描述从一个状态到另一个状态的演变过程。
策略
由过程的第 k 阶段开始到终点为止的过程,称为问题的后部子过程,由每段的决策组成的决策函数序列。就称为子过程的策略,简称子策略,记为:
为全过程策略,简称策略。
动态规划的基本概念和基本方程3
指标函数和最优指标函数值
指标函数(又称目标函数)是用来衡量所实现过程优劣的一种数量指标,它是定义在过程上的数量函数,用表示:
阶段指标(又称阶段效益)是衡量该段决策效果的数量指标,用表示。
最优指标函数值是指标函数的最优值,记为:
动态规划的基本概念和基本方程4

最短路线有一个重要特性,即如果从起点到终点的最短路线在第 k 站通过点出发到终点的所有可能选择的不同路线来说,必定也是最短的.
采用后推法求最短路径问题
A
B2
B1
F2
F1
E3
E2
E1
D2
D1
G
C2
C3
C1
C4
D3
5
3
1
3
6
8
7
6
6
8
3
5
3
3
8
4
2
2
2
1
3
3
3
5
5
2
6
6
4
3
A
B2
B1
F2
F1
E3
E2
E1
D2
D1
G
C2
C3
C1
C4
D3
5
3
1
3
6
8
7
6
6
8
3
5
3
3
8
4
2
2
2
1
3
3
3
5
5
2
6
6
4
3