文档介绍：运筹学第五章动态规划
第五章动态规划
动态规划是运筹学的一个重要分支,它是解决多阶段决策过程最优化的一种数学方法。本章主要介绍动态规划的基本概念、理论和方法。
第一节多阶段决策过程及实例
一、多阶段决策过程
生产和科学实验中,有一类活动的过程,由于它的特殊性,可将过程分为若干个互相联系的阶段,在每个阶段都需要作出决策,从而使整个过程达到最好的活动效果。
各阶段的决策不是任意选取的,它取决于当前阶段所面临的状态,同时该决策又影响到今后各阶段的决策。当各阶段的决策确定后,就组成了一个决策序列,也就决定了整个过程的一条活动路线。这就是多阶段决策过程。
阶段1
阶段9>2
阶段n
状态
状态
状态
状态
状态
决策
决策
决策
多阶段决策过程示意图
……
多阶段决策中,各阶段采取的决策一般说与时间有关,决策依赖当前状态,又随即引起状态转移,故有动态含义,因此称动态规划。
二、多阶段决策实例
例13>.最短路线问题
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
3
3
5
3
3
8
4
2
2
1
2
3
3
3
5
5
2
6
6
4
3
某种机器可在高低两种负荷下生产。
已知,在高负荷下产品年产量g与机器数量u1的关系为:
g=g(u1)
这时机器的完好率为a,0<a<1。
在低负荷下产品年产量h与机器数量u2的关系为:
h=h(u2)
此时机器的完好率为b,0<b<1。
假定开始生产时完好的机器数量为s1。要制定一个五年计划,在每年开始时决定如何重新分配完好机器在高低两种负荷下生产的数量,使五年内产品的产量达到最高?
第二节动态规划的基本概念与基本方程
一、基本概念
: 把所给问题的过程,分成相互联系的子过程,每一子过程称为一个阶段。描述阶段的变量称为阶段变量,一般用k表示。例如例1可分为6个阶段。K=1,2,3,4,5,6
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
它表示每个阶段开始所处的自然条件或客观条件。
描述状态的变量称为状态变量,常用Sk表示第k阶段的状态变量。通常每个阶段的状态有若干个,即是一个点集。
注:这量所说的状态一般要求无后效性。
在例1中,S1={A},S2={B1,B2},……
决策表示在某个阶段,处于某种状态所做的选择。
描述决策的变量,称为决策变量,常用uk(Sk),它是状态变量的函数。
决策变量的允许取值范围,称为允许决策集合,常用Dk(Sk)表示。显然uk(Sk)?? Dk(Sk)
按顺序排列的决策组成的集合。
由过程的第k阶段开始到终止状态为止的过程,称为问题的后部子过程(或称为k子过程)。
k子过程策略,简称子策略,记为pk,n(Sk)。即
pk,n(Sk)= {uk(Sk),uk+1(Sk+1),…,un(Sn)}
当k=1时,此时的决策序列称为全过程的一个策略,简称策略,记为p1,n(S1),即:
p1,n(S1)= {u1(S1),u2(S2),…,un(Sn)}
在实际问题中可供选择的策略有一定范围,称为允许策略集合,用P表示。从允许策略集合找最优效果的策略,称为最优策略。
状态转移方程是确定由一个状态转移到另一状态的演变过程。它是状态和该状态下所做决策的函数。它表示成如下形式:
Sk+1=Tk(Sk,uk)
Tk称为状态转移函数。在例1中,Sk+1=uk(Sk)
用来衡量所实现过程优劣的一种数量指标。它是定义在全过程或所在后部子过程上确定的数量函数。常用Vk,n表示。即
Vk,n= Vk,n(Sk,uk,Sk+1,…,Sn+1) k=1,2,…,n
动态规划的指标函数应满足三个性质:
1)定义在全过程和所有后部子过程上的数量函数
2)具有可分离性,满足递推关系,即:
Vk,n=Vk,n(Sk,uk,Sk+1,…,Sn+1)
= ??k(Sk,uk, Vk+1,n(Sk+1,uk