动态规划基本概念与原理，

(1)阶段。

动态规划问题存在若干个相互联系的不同部分,通常根据时间或空间对整个过程进行划分。一般用k表示阶段变量,若整个问题分为n个阶段(Stage),则k＝1,2,…,n。在【例8-1】中,按决策的先后顺序,可将问题分为5个阶段,如图8-1所示。

(2)状态。

状态(State)是指某一阶段开始或结束时所处的自然状况或客观条件,如地理位置、资源量等。通常用Sk表示第k阶段的状态,在【例8-1】中,S1＝{A},S2＝{B1,B2,B3}。状态变量取值的全体称为状态空间或状态集合——状态可能集。状态变量是动态规划中最关键的一个参数,它既是前面各阶段决策的结束点,又是本阶段作出决策的出发点,因此状态也是动态规划问题各阶段信息的传递点和结合点。状态变量具有无后效性(马尔可夫性质),即当某阶段的状态确定后,该阶段以后过程的演变只与当前的状态有关,与这个阶段以前的状态无关。【例8-1】各阶段的状态变量集合如表8-4所示。

表8-4

(3)决策。

决策(Decision)是指当决策者处于某个阶段的某个状态时,面对下一阶段的某一状态做出的选择。可以用决策变量dk(Sk)或xk(Sk)表示第k阶段、状态为Sk的决策。在Sk状态下,决策者可以选择的方案可以是一个集合,称为决策允许集,记作Dk(Sk)或Xk(Sk)。在【例8-1】中,D2(B2)＝{B2 C1,B2 C2},表示在第二阶段初始状态B2时,可以选择的方案可以是B2 C1,B2 C2。

(4)策略和子策略。

策略(Policy)是指按阶段依次做出的决策序列,又称全策略。通常把从第k阶段Sk状态开始到结束的决策序列,称为k后部子策略,简称k子策略(Subpolicy),记作Pkn(Sk)。例如,n阶段动态规划问题的全策略可以表示为P1n(Sn)＝{d1(S1),d2(S2),…,dk(Sk),dk＋1(Sk＋1),…,dn(Sn)}。其中,Pkn(Sk)＝{dk(Sk),dk＋1(Sk＋1),…,dn(Sn)}——k后部子策略;P1k(Sk)＝{d1(S1),d2(S2),…,dk(Sk)}——前部k子策略。

(5)状态转移方程。

在第k阶段某一确定的状态Sk下,一旦决策变量dk(Sk)确定,则第k＋1阶段的状态Sk＋1也就确定了,这一规律称为状态转移律。状态转移律一般用状态转移方程来表示,即

Sk＋1＝T{Sk,dk(Sk)}或T(Sk,dk)

(6)指标函数和最优函数。(www.xing528.com)

衡量某一阶段决策效果的数量指标称为阶段指标,记作Vk{Sk,dk(Sk)}。阶段指标可以是距离、利润、成本、产量或资源消耗等,表示某一阶段决策对目标的贡献。用于衡量已完成子策略优劣的数量指标称为指标函数(Index Function),记为Vk,n{Sk,dk(Sk);Sk＋1,dk＋1(Sk＋1),…,Sn,dn(Sn)}。第k阶段的指标函数可记为Vk{Sk,dk(Sk)}。

最优函数(Optimal Function)是指在某一确定状态选择最优策略后得到的指标函数值,即对应某一最优子策略的某种效益量度,记作fk(Sk)＝OPT{Vk,n},OPT是Optimization(最优化)的缩写,依具体问题可表示为min或max。在【例8-1】中,在S3状态下,选择C2后得到的最优函数为

(7)最优化原理。

理查德·贝尔曼认为,作为整个过程的最优策略,应具有这样的性质:无论过去的状态和决策如何,对先前决策所形成的状态而言,余下的所有决策必然构成最优策略。根据这一原理,计算动态规划问题的递推关系式称为动态规划基本方程。

(8)动态规划基本方程。

以逆序解法为例,动态规划基本方程可表达为:

其中,指标函数有加法合成或乘法合成两种形式。

加法合成:

乘法合成: