文档介绍：第四章动态规划
动态决策问题
动态规划的基本概念
最优化原理
动态规划(DP)问题建模及求解
1
动态决策问题
动态决策问题是决策过程具有阶段性或时序性的决策问题。即决策过程可划分为明显的阶段决策问题。
决策过程的分类:根据过程的时间变量是离散的还是连续的,分为离散时间决策过程(discrete-time decision process)和连续时间决策过程(continuous-time decision process),对应的决策问题分为离散型动态决策问题和连续型动态决策问题;
根据过程的演变是确定的还是随机的,分为确定型决策过程(deterministic decision process)和随机型决策过程(stochastic decision process),按决策过程演变的性质分为:确定型动态决策问题和随机型动态决策问题。其中应用最广的是确定型动态(多阶段)决策问题。
“动态”一词强调决策过程及其解决的问题具有时间上的顺序特性。
2
动态规划的基本概念
动态规划(dynamic programming,简称:DP)是运筹学的一个分支,是求解多阶段决策问题的最优化方法。20世纪50年代初,美国数学家R. E. Bellman等人在研究多阶段决策过程(multi-step decision process)的优化问题时,提出了著名的最优性原理(principle of optimality),即把多阶段决策过程转化为一系列单阶段问题,逐个求解,创立了解决这类过程优化问题的新方法—动态规划,并于1957年出版了他的名著《Dynamic Programming》。
动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如:最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动态规划方法比用其它方法求解更为方便。
3
虽然动态规划主要用于求解以时间来划分阶段的动态过程优化问题,但是一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为多阶段的决策过程,也可以用动态规划方法方便地求解。
应当指出,动态规划是求解某类问题的一种方法,是考察问题的一种途径,而不是一种特殊算法(如线性规划是一种算法)。因而,它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则,而必须对具体问题进行具体分析。因此,在学****时,除了要对基本概念和方法正确理解外,应以丰富的想象力去建立模型,用创造性的技巧去求解。这是动态规划的一大弱点,另一弱点是“维数障碍”。
下面以最短路线问题为例,说明动态规划的基本概念。
例4-1:最短路线问题:下面是一个线路网,连线上的数字表示两点之间的距离(或费用)。试寻求一条由A到F 距离最短(或费用最省)的路线。
4
A
B1
B2
B3
C1
C2
C3
D1
D2
D3
E1
E2
F
3
5
4
9
5
4
3
5
1
7
1
5
8
4
6
4
4
2
2
2
6
9
7
5
1
4
一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素:
1. 阶段(stage)n:对整个决策过程的自然划分,即作出决策的若干轮次。如上例n = 1,2,3,4,5。
2. 状态(state)Sn:每一阶段的出发位置。构成状态集,记为Sn
S1={A},S2={B1,B2,B3},S3={C1,C2,C3},S4={D1,D2,D3},S5={E1,E2}。---- 阶段的起点
3. 决策(decision)Xn:从一个阶段某状态演变到下一个阶段某状态的选择,记为Xn(S)。---阶段的终点
构成决策集,记为Dn(Sn)。
D1(S1)={X1(A)}={B1,B2,B3}= S2,
D2(S2)={X2(B1),X2(B2),X2(B3)}={C1,C2;C1,C2,C3 ;C2,C3 }={C1,C2,C3}=S3,
D3(S3)={X3(C1),X3(C2),X3(C3)}={D1,D2;D1,D2,D3; D1,D2,D3}={D1,D2,D3}=S4,
D4(S4)={X4(D1),X4(D2),X4(D3)}={E1,E2;E1,E2;E1,E2}={E1,E2}=S5,
D5(S5)={X5(E1),X5(E2)}={F;F}={F}。
2
A
B
C
D
E
F
1
3
4
5
5
A
B1
B2
B3
C1
C2
C3
D1
D2
D3
E1
E2
F
3
5
4
9
5
4
3
5
1
7
1