动态规划的原理及应用动态规划是运筹学的一个分支，是求解多阶段决策过程的最优化数学方法。

20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类问题的新方法——动态规划。

动态规划主要用于以时间划分阶段的动态过程优化问题，但一些与时间无关的静态规划如线性规划或非线性规划，人为引进时间因素后，把它们看成多阶段过程，也可用动态规划求解。

1．动态规划的基本理论一．动态规划的术语在研究现实的系统时，我们必须将系统具体的术语抽象为数学统一的术语。

在此先简要介绍动态规划中的常用术语。

级：我们把系统顺序地向前发展划分为若干个阶段，称这些阶段为“级”。

在离散动态规划中，“级”顺序的用自然整数编号，即1，2，…，n.状态（λ）：用来描述、刻画级的特征。

状态可以是单变量，也可以时向量。

在此，我们假设研究的状态具有“无记忆性”，即当前与未来的收益仅决定于当前的状态，并不依赖于过去的状态和决策的历史。

状态空间（Λ）：由全部系统可能存在的状态变量所组成。

决策：在每一级，当状态给定后，往往可以做出不同的决定，从而确定下一级的状态，这种决定称为决策。

描述决策的变量称为决策变量。

对每个状态λ∈Λ，有一非空集X(λ)称为λ的决策集。

决策变量x(λ)∈X（λ）。

变换：若过程在状态λ，选择决策x(λ)，可确定一个状态集T（λ，x(λ)）,过程将从λ移动到其中某个状态.T(λ,x(λ))称为变换函数，它确定过程从一个状态到另一个状态的演变。

T（λ,x(λ)）可分为两种类型，即确定型和不确定型。

确定型的T（λ,x(λ)）只含有一个元。

不确定型指我们不能确切知道决策的结果，但作为某已知概率分布支配的变换结果，在每级状态和决策是确定的。

这时，集函数T（λ,x(λ)）将包含多个元素。

当T（λ,x(λ)）=0 时，过程终止。

策略：顺序排列的决策集，记为v。

所有可能的策略集构成策略空间Γ。

收益：评价给定策略的目标函数r(λ，v)，它依赖于状态和策略。

总收益是集收益s(λ,v)的某个组合（通常为集收益之和）。

若T（λ,x(λ)）=0，则r(λ1，v1)= s(λ1,v1)；若T（λ,x(λ)）= λ2，则r(λ1，v)= s(λ1,v1)+ r(λ1，v2)。

二．序贯决策过程动态规划的寻优过程可以有正序、逆序两种方式。

当初始状态给定时，用逆序方式比较好，当终止状态给定时，用正序方式较好。

采用分级的序贯决策方法，把一个含有n个变量的问题转化为求解n个单变量问题。

为了应用最优化原理，必须满足分级条件，即目标函数可分性和状态可分性。

目标函数可分性：1n j sj =∑ = 1nj sj =∑（λj, vj ）状态可分性：即在n+1 级做决策x(n+1) 后，状态λ(n+1)仅取决于λ(n)和x(n+1) ，而与以前的状态无关。

也就是系统的无记忆性。

三．最优性定理和基本方程Bellman 的最优性原理指出：不管该最优策略上某状态以前的状态和决策如何，对该状态而言,余下的诸决策必构成最优子策略.由此得出最优性定理：策略v(1,n)=( λ1, λ2,…, λn)是最优子策略的充分必要条件是：对任一k(1<k<n),当初状态为x1时,有r(λ1,v*(1,n))=min r(λ1,v(1,n))=min [r(λ1,v(1,k-1))+v(λk,v(k,n))]因此，在策略集V （1,n ）上求最优解，就等价于先在子策略集V （k,n ）上求最优解，然后再求这些子最优解在子策略空间V （1,k-1）上的最优解。

逆序递推的基本方程：r*(λk) = min [r(λk,vk)+r*(λk+1)] 终端条件：r*(λn+1) = 0式中： λk+1 = T(λk, vk)顺序递推的基本方程：r*(λk+1) = min [r(λk+1,vk)+r*(λk)] 始端条件：r*(λ1) = 0式中： λk+1 = T(λk, vk)2．动态规划的应用举例用动态规划求解实际问题，首先要建立动态规划模型，需进行以下几方面工作：（1）正确划分阶段及选择阶段变量k。

（2）正确选择状态变量λk，状态变量应满足以下两个条件：1．能正确描述受控过程的演变特征。

2．无后效性（3）正确选择决策变量及确定个级允许决策集合。

（4）写出状态转移方程（以逆序为例）λk+1 = T(λk, vk)（5）确定阶段目标函数的形式，目标函数必须具有可分性，并满足递推关系。

（6）写出基本方程即最优值函数满足的递推方程及端点条件（以逆序极小化为例）：r*(λk) = min [r(λk,vk)+r*(λk+1)] 终端条件：r*(λn+1) = 0例最短路径问题如图，给定一个运输网络，两点之间连线上的数字表示两点间的距离。

试求一条从A到E的运输路线，使总距离最短。

从图中可以看出，我们可以把从A到E的过程分成若干个阶段，这里是四个阶段。

处于每个阶段时，都要选择走哪条支路——决策，一个阶段的决策除了影响该阶段的效果之外，还影响到下一阶段的初始状态，从而也就影响到整个过程以后的进程。

因此，在进行某一阶段的决策时，就不能只从这一阶段本身考虑，而应使整体的效果最优。

我们可以从最后一个阶段开始，由终点向始点方向逐阶递推，寻找各点到终点的最短路径，当递推到始点时，即得到了从始点到终点的全过程最短路。

这种由后向前的递推方法，正是动态规划的寻优思想。

下面我们对这个问题进行求解。

把从A 到E 的全过程分为四个阶段，用k 表示阶段变量。

第一阶段，有一个初始状态A ，三条可供选择的支路1AB 、2AB 、3AB ，以此类推。

我们用k d （k x ，1k x +）表示在第k 阶段由初始状态k x 到下阶段的初始状态1k x +的支路距离。

用k f （k x ）表示从第k 阶段的k x 到终点E 的最短距离。

用逆序递推的方法：1．阶段k = 4第4阶段有两个初始状态1D 和2D 。

若全过程最短路径经过1D ，则有4f （1D ）= 4 ；若全过程最短路径经过2D ，则有4f （2D ）= 3 。

2．阶段 k = 3假设全过程最短路径在第3阶段经过1C 点：若由11C D E →→，则有3d （1C ，1D ）+4f （1D ）= 4 + 4 = 8若由12C D E →→，则有3d （1C ，2D ）+4f （2D ）= 6 + 3 = 9因此，3f （1C ）= min （8，9）= 8 ，即由1C E →的最短路径是11C D E →→，最短距离是8。

类似地，假设全过程最短路径经过2C 点，则有3f （2C ）= min{[3d （2C ，1D ）+ 4f （1D ）]，[3d （2C ，2D ）+ 4f （2D ）]} = min (7,8) = 7即由2C E →的最短路径是由21C D E →→，最短距离是7。

同理可得出：3f （3C ）= min ( 6 , 6 ) = 6由3C E →的最短路径有两条31C D E →→和32C D E →→，其距离都是6。

3．阶段 k = 2类似地，可计算21()f B 、22()f B 、23()f B 如下：21()f B = min( 15 , 14 , 14 ) = 1422()f B = min(11, 12 , 12 ) = 1123()f B = min(14 , 15 , 13 ) = 13因此，由1B E →的最短路径有三条121B C D E →→→、131B C D E →→→、132B C D E →→→，最短距离都是14；由2B E →的最短路径是211B C D E →→→，距离是11；由3B E →的最短路径有两条：331B C D E →→→和332B C D E →→→，距离是13。

4．阶段 k = 11()f A = min ( 16 , 15 , 16 ) = 15因此，由A E →的全过程最短路径是211A B C D E →→→→，最短距离是15。

从以上过程可以看出，每个阶段中，都求出本阶段的各个初始状态到终点E 的最短路径和最短距离，当逆序递推到过程始点A 时，便得到全过程的最短路径及其最短距离，同时得到一族最优结果（即各阶段的各状态到终点E 的最优结果）。

和穷举法相比，逆叙递推方法大大减少了计算量，且大大丰富了计算结果。

此题也可以用顺序递推的方法求解，解法过程相似，在此就不赘述了。

例 多阶段资产投资的动态规划决策模型1． 多阶段资产投资的决策问题设某资产市场中共有n 种资产可供投资者进行选择，某一投资者要在该市场中进行m(m ＞1)阶段的投资，在每一阶段中该投资者都可在这n 种资产中选择投资。

设该投资者可预测到从开始到第m 个投资阶段中各个阶段单位资产投资的平均收益与风险。

不妨设，在第j(i ＝l ，…，m)个阶段初购买第j(i ＝l ，…，n)种资产，到该阶段末时的平均收益率为j i r ，平均风险损失率为j i q ；而且，若第j—l 阶段末已持有一部分资产，则在第j(j ＝2，…，m)个阶段初，可以决定这些资产是继续持有、还是出售，而出售资产所得的资金可用于该阶段的资产购买。

根据实际情况，每个阶段中每一种资产的买卖均需按交易的金额交纳一定比例的交易费，不妨假设在第j(j ＝l ，…，m)个阶段中买卖第i(i ＝1，…，n)种资产的交易费率为jp。

i多阶段资产投资的决策问题就是要求设计该投资者的一种资产投资组合方案，使得在投资总风险低于一定风险上限要求的前提下，到第m个阶段末时该投资者的投资总收益(即m个阶段的投资收益总和)尽可能大。

为简化问题的考虑，建立以下四点假设：1．投资者只在投资开始时(即第1阶段初)向资产市场投入一定数额的自由资金，在其后的m—1个阶段中不再增加对该资产市场的资金投入；同时，也不把已获得的收益资金从资产市场中抽出。

也就是说，投资者的最终持有的资产和资金只是由最初的自由资金进行了M次投资后获得的。

2．在资产投资中，不允许卖空行为，即投资者出售的资产量不允许超过其当时的实际资产持有量。

3，考虑到投资超分散，投资风险就越小，我们确定投资总风险用各阶段中所投资的各种资产风险中最大的一个来衡量。

而且，投资者的投资风险要求不能高于一个固定的风险上限。

4，投资是持续的，在相邻两阶段间没有其他投资行为。

这样，任一阶段未时投资者的资产及自由资金情况与下一阶段初时的情况相同。

多阶段资产投资决策的动态规划模型为叙述方便，我们引入以下一些记号：js——第j阶段初，投资者拥有的第i种资产的金额(j＝1，…，m ; i = 1 , …，in)；jt——第j阶段韧，投资者拥有的自由资金的金额(j＝1，…，m )；j i x ——第j 阶段初，投资者对第i 种资产的交易金额(j ＝1，…，m ; i = 1 , …，n)；其中：j i x ＜0表示投资者出售第i 种资产；j i x ＞0表示投资者购买第j 种资产。