运筹学动态规划.ppt

动态规划
多阶段决策过程及实例
动态规划的基本概念和 基本方程
动态规划的最优性定理
动态规划与静态规划关系
综述
动态规划是运筹学的一个分支,是解决多阶段决策过程最优化问题的一种数学方法。
该方法是由美国数学家贝尔曼()等人在本世纪50年代初提出的。
他们针对多阶段决策问题的特点,把多阶段决策问题变换为一系列互相联系单阶段问题,然后逐个加以解决。
同时,他提出了解决这类问题的“最优性原理”,并成功地解决了生产管理、工程技术等方面的许多实际问题,从而建立了运筹学的一个新分支,即动态规划.
动态规划具有广泛应用,是现代企业管理中一种重要的决策方法。应用动态规划可以解决诸如最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题以及最优控制问题等。
许多问题用动态规划的方法去处理,常比线性规划或非线性规划方法更有效。特别对于离散性的问题。
特别注意:动态规划是求解某类问题的一种方法,是考察问题的一种途径,而不是一种算法(如线性规划是一种算法)。
因而,动态规划没有标准的数学表达式和明确定义的一组规则,而必须对具体问题进行具体分析处理.
多阶段决策过程及实例
多阶段决策问题,是指一类活动过程,它可分为若干个互相联系的阶段,在每一个阶段都需要作出决策,从而使整个过程达到最好的活动效果。
因此,各个阶段决策的选取不是任意确定的,它依赖于当前面临的状态,又影响以后的发展。
每个阶段的决策确定以后,过程也就随之确定。这种把一个问题可看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程。这种问题就称为多阶段决策问题。
一、多阶段决策问题
1
决策
状态
2
决策
状态
状态
n
决策
状态
状态
在多阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的。决策依赖于当前的状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义。因此,把处理它的方法称为动态规划方法。
一些与时间没有关系的静态规划(如线性规划,非线性规划)问题,只要人为地引进“时间”因素,也可把它视为多阶段决策问题,用动态规划方法去处理。
1
决策
状态
2
决策
状态
状态
n
决策
状态
状态
动态规划模型的分类:①离散确定型;②离散随机型,③连续确定型;④连续随机型。
其中离散确定型是最基本的,本章主要针对这种类型的问题,介绍动态规划的基本思想、原理和方法,这些对其它类型的问题也适用。然后通过几个典型的动态规划模型来介绍它的应用。
当建立问题的数学模型后,如果时间参数是离散的,则它就是数学规划问题;如果时间参数是连续的,则属于最优控制问题。
例1 最短路线问题
二、多阶段决策过程问题实例
从A点到E点要铺设一条天然气管道,中间必须经过三个中间站,
第一站可在B1、B2、B3中选择,
第二站可在C1、C2、C3中选择,
第三站可在D1、D2、D3中选择,
要求选择一条由A 到E的铺管路线,使总长度最短。
其中两点连线上的数字表示两点间管线的长度。
E
D3
D1
D2
C1
C3
C2
A
B3
B2
B1
5
4
2
6
3
4
6
5
6
1
2
2
2
3
3
2
3
4
从A点到E点铺设管道,可以按其地理特点自然地分成四个阶段:(如下图所示)
从A到B是第一阶段,从B到C是第二阶段,
从C到D是第三阶段,从D到E是第四阶段,
A
B
C
D
E
阶段1
阶段2
阶段3
阶段4
E
D3
D1
D2
C1
C3
C2
A
B3
B2
B1
5
4
2
6
3
4
6
5
6
1
2
2
2
3
3
2
3
4
在阶段1中,A点是起点,B点是终点,其中B有B1、B2、B3三个可选择的点。
如选B3点,则B3就是阶段1在A点的决策结果;
B3点既是阶段1铺设管道的终点,又是阶段2铺设管道的起点。
A
B
C
D
E
阶段1
阶段2
阶段3
阶段4
E
D3
D1
D2
C1
C3
C2
A
B3
B2
B1
5
4
2
6
3
4
6
5
6
1
2
2
2
3
3
2
3
4