文档介绍：第8章动态规划
§ 1多阶段的决策问题
动态规划是一种研究多阶段决策问题的理论与方法。
所谓多阶段决策问题是这样一类的决策过程：它可以系为若干个相互联系的阶段，在每
一阶段分别对应着一组可以选取的决策，当每个阶段的决策选定以后，过程 min
d(B3C) + f(C1) d(B3,C2) + f (C2) =min ,d(B3C) + f(C3)」
5十4
1 +7 =8,B3t C2T D2T
2+6)
(4)当四个阶段联合考虑时
，d(AB) + f(Bi)
「2+11
f(A)=min d( A,B2)十 f (B2) =min 5 + 7 =11,At B3T C2T D2T E 这就是
0A, B3) + f(B3),
、3+8
最短路和最短距离。
从以上的解题可以看出，将一个多阶段的决策问题转化为依次求解的多个单阶段的决
策问题时，一个重要的特征是将上一阶段的解传递纳入下一阶段考虑，即做到求解的多个阶
段间是具有传递性的。
为了将上述解题的思路、步骤推广应用于比较复杂的多阶段决策问题中去，需要引入
动态规划的一■些基本概念。
2-2动态规划的基本概念
.阶段 是指一个问题需要作出决策的步数，通常用k表示问题的所包含的阶段数，称为阶
段变量。K的编号方法有两种
(1)顺序编号法
(2)逆序编号法
.状态 这是动态规划中最关键的一个参数，它既反映多阶段决策的结局，又是本阶段作出
决策的出发点和依据。
状态是动态规划问题多阶段信息传递点和结合点，第k阶段的状态变量是 Sk应包含该阶
段之前决策过程的全部信息，做到从该阶段后作出的决策同这之前的状态和决策相互独立，
各阶段的状态通常用状态 s来描述。
例1中对旅行者每个阶段所处的位置只需用一个状态变量来描述，但有些问题多阶段的 的状态则要用多个变量或向量的形式来描述。向量中所包含的个数称为动态规划中的维数， 动态规划的工作量随维数的增大呈指数倍增大，这种情况称为维数障碍或维数灾难，从而极
大的限制了动态规划问题的实际应用。
.决策是指某阶段处从给定的状态出发，决策者在面临的若干种不同的方案中作出的选择。
决策变量Xk(Sk)表示第k阶段状态为Sk时对方案的选择。Xk(Sk)的取值要受到一定范围的
限制，Dk(Sk)表示k阶段状态为sk时决策允许的取值范围，因而有Xk(Sk)w Dk(Sk),
D(B1)KC1,C2,C3},如果选取下一个到达点为 C2,则X2(B1)= C2。
.策略和子策略 动态规划问题中多阶段决策组成的序列总体称为一个策略。含n个动态规
划问题的策略可以写成为： {X1(S1),X2(S2)J||,Xn(Sn)},如 At B〔 T C2 T D〔 T E 等。
把从某一阶段开始到过程最终的决策序列称为问题的子过程策略或子策略，从k阶段起的策
略可以写成：{Xk(Sk),Xk书(Sk+)MI,Xn(Sn)},如BT C2 T Q T E等都是自策略。
.状态转移律 从的Sk某一状态出发，当 Xk(Sk)的取值决定后，下一阶段 Sk书的取值也随
之而确定。这种从上阶段的某状态的值到下阶段某状态值的转移规律称为状态转移律。显然,
下一阶段的状态 Sk书的取值是上一阶段变量 Sk和上阶段决策变量的函数 Xk(Sk),记为
Sk+=T(&, Xk(Sk))或简写为 Sk+=T(Sk,Xk)称为状态转移方程：如 S2 = B, X2(S2) = C1，
那么S3 =Ci它是X2与S2的函数。
.指标函数有阶段的指标函数和过程的指标函数之分。
阶段的指标函数是对应某一阶段和从该阶段出发的一个阶段的决策的某种效益变量，用 vk(sk,xk)表示，如：v2(B1,xk) = 7,6,5 之分。
过程的指标函数是从状态鼠« =1,2,|||,n)出发至过程的终点，当采取某种子策略时,
按预定的标准得到的效益值，这个值与s-勺效益值有关，又与 sk以后的选取的策略有关，
它是两者的函数值，记作 Vk,n，Vk,n(Sk,Xk,Sk+,Xk+,|||,Sn) 0
过程的指标函数又它所包含的各阶段指标函数的函数。按问题的性质，它可以是各阶
段指标函数的和、积或其他函数形式。当sk的值确定后，指标函数的值就只同k阶段的子
策略有关。
所谓最优指标函数，是指对某一确定状态选取最优策略后得到的指标函数值，实际上
也就是对应某一最优子策略的效益值记作fk(sk),于是有fk(sk) =optVk,n,这里的opt代
表最优化决策，根据效益值的具体含义可以求max或min
vk(sk,xk)vk i(sk i,xki)
2-3最优化原理与动态规划的数学