数学建模（四）：将多阶段转化为单阶段的动态规划
&1.引言
1）动态规划发展和研究内容
动态规划是求解决策过程最优化的数学方法，它在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。它主要解决的是⎡以时间划分阶段的动态过程的优化问题⎦，但是将一些与时间无关的静态规划人为地引入时间因素，将其视为多阶段决策过程，再运用动态规划方法求解。
我们举两个实例：
例1 最短线路问题：给出一个线路网，连线上的数字表示两点之间的距离（或者是运输货物的费用）。寻求一条由A到G距离最短（或者说是费用最省）的路线。
例2 生产计划问题：工厂生产的某种产品，单位成本为1元/件，每季度开工的固定成本为3000元，工厂每季度的最大生产产品数量为6000件，市场每季度对该产品的需求量分别为2000，3000，2000，4000件。若工厂在第一季度、第二季度生产了全年的需求，则在第三季度、第四季度才能出售的产品需支付存储费0.5元/件*季度，同时规定年初和年末不能够有库存。制定一个生产计划，即安排每个季度的产量，使一年的总费用最少。
2）决策过程的分类
根据过程的时间变量是离散的或是连续的，分为离散时间决策过程（decision process）和连续时间决策过程（continuous-time decision process）；同时也可以根据过程的演算是确定的或是随机的，分为确定性决策过程（deterministic decision process）和随机性决策过程（stochastic decision process），应用最广的是确定性多阶段决策过程。
&2 基本概念、基本方程和计算方法
1）基本概念与基本方程
1.1 阶段
阶段是对整个过程的一个合理划分，通常按照较为明显的时间或空间边界进行划分，以便于将多阶段转化为单阶段问题，并依次序求解。阶段变量一般使用k=1,2,…,n表示。比如前面的最短路线问题，在A点出发就是k=1，在后面就依次为k=2,3,4,5,6，共6个阶段。在例2中直接根据四个季度就可以分为四个阶段。
1.2 状态
状态表示每个阶段开始时过程所处的情况。它被要求能够描述过程的特征并且在被给定后，这个阶段之后的演变与它无关，同时要求状态是直接或间接能够观测到的。
描述状态的变量称为状态变量（state variable），变量允许取值的范围称为允许状态集合（set of admissible states）。用xk表示第k阶段的状态变量，它可以是一个数或一个向量。我们用Xk表示第k阶段的允许状态集合。在前面的最短路线规划问题中，x2就是从A点出发决定去了哪里的结果，可以取B1,B2，或者定义Bi为i，令X2={1,2}；
从上面的描述可以得知，n个阶段的决策过程有n+1个状态变量，xn+1表示xn的演变结果。在例1中x7取G，或者是定义为1，即x7=1 。
1.3 决策
在一个阶段的状态确定后，有各种选择使这个状态演变到下一阶段的某个状态，这样的选择手段称为决策（decision），在最优控制问题中也称为控制（control）。
描述这样的决策，我们使用决策变量，决策变量的取值范围我们称为允许决策集合。使用uk(xk)表示第k阶段处于状态xk时的决策变量，它是xk的函数，用Uk(xk)来表示xk的允许决策集合。在前面举例的最短路线问题中，u2(B1)可以取值为C1,C2,C3，可以记为u2(1)=1,2,3，而U2(1)={1,2,3}。
1.4 策略
由整个动态规划问题过程的所有决策组成的序列集合称为策略，由初始状态x1开始的全过程的策略记作p1n(x1)={u1(x1),u2(x2),…,un(xn)}.
由第k阶段的状态xk开始到终止状态的后部子过程的策略记作pkn(xk)，即
pkn(xk)={uk(xk),…,un(xn)},k=1,2,…,n-1；类似地，从第k到第j阶段的子过程策略记作pkj(xk)={uk(xk),…,uj(xj)}。可供选择的策略也有一定的范围，称为允许策略集合，用P1n(x1),Pkn(xk),Pkj(xk)表示。
1.5 状态转移方程
在确定性决策过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。可以用状态转移方程（equation of state transition）表示这种演变规律，写作
xk+1=Tk(xk,uk)，k=1,2,…,n。在例1中状态转移方程xk+1=uk(xk)。
1.6 指标函数和最优值函数
指标函数是衡量过程优劣的数量指标，是定义在全过程和所有后部子过程上的数量函数，我们使用Vk,n(xk,uk,xk+1,…,xn+1)来表示，k=1,2,…,n。指标函数是具有可分离性的，即Vk,n可以用vk,uk,Vk+1,n来表示，记为
Vk,n(xk,uk,xk+1,…,xn+1)=????k(xk,uk,Vk+1,n(,xk+1,uk+1,…,xn+1))并且????k关于变量Vk+1,n是严格单调的，指标函数是有由阶段指标vj(xj,uj)组成，组成的形式有以下几种
Vk,n还可以被表示为Vk,n(xk,pkn)，当这个函数对pkn求得最优值时，得到一个关于xk的函数，被称为最优值函数，记为fk(xk)，即fk(xk)=opt Vk,n(xk,pkn)。
1.7最优策略和最优轨线
使Vk,n能够取到最优值的策略称为最优策略，记为p*kj={u*k,…,u*j}。按照最优策略，整个过程得到的状态{x*1,x*2,…,x*n+1}称为最优轨线。
1.8递归方程
在动态规划中，利用递归方程求解有两种方法，运用的原理都是动态规划最优性原理的基础，即：最优策略的子策略，构成了最优子策略，我们可以用逆序解法，从k=n+1推导至k=1，也可以用顺序解法；二者的状态转移方程和递归方程是：
1）逆序解法：
2）正序解法：
⊗取加法时递归方程中的第一个方程右端为0，取乘法时为1 。
&3.逆序解法的计算过程
我们以终端自由、始端固定、指标函数取和的形式的逆序解法为例给出计算过程，其他情况容易在这个基础上修改得到；一般化的自由终端条件fn+1(xn+1,i)=????(xn+1,i),i=1,2,…,nn+1
其中????为已知，固定始端的条件表示为X1={x1}。
如果允许状态集合为Xk={xki|i=1,2,…,nk}，i=1,2,…,nk，k=1,2,…,n.
允许决策集合为Uki={uki(j)|j=1,2,…,nki},i=1,2,…,nk，k=1,2,…,n.
对应这其中的每个xki和每个uki(j)的组合，都有状态转移方程和阶段指标，即x(k+1)i(j)=Tk(xki,uki(j))，vk=v(xki,uki(j))。于是基本方程可以表示为
fk(j)(xki)=vk(xki,uki(j))+fk+1(Tk(xki,uki(j)))
fk(xki) = opt fk(j)(xki)
j = 1,2,…,nki,i=1,2,…,nk,k=n,…,2,1.
那么依照这种方法，我们逆序依次求出fk(xxi),uk*(xki)，输出x1*，然后根据uk*(xki)将xk+1*依次求出，可以得到xk*。
&4.动态规划和静态规划的关系
二者的本质都是在研究若干约束条件下的函数极值问题，两种规划在很多情况下原则上可以转换，一些静态规划只要适当引入阶段变量、状态、决策等就可以用动态规划方法求解。例子如下：
我们设状态为x1,x2,…,xn+1，取u1,u2,…,un，状态转移方程为x1=a,xk+1=xk-uk,k=1,2,…,n.于是我们可以用逆序法求解。
&5. 若干典型问题的动态规划模型
1）最短路线问题
在这里的阶段指标为距离dk(xk,uk(xk))，指标函数为阶段指标之和，这样的情况我更喜欢称它为一种“剪枝”，剪去的是在假设当前状态下到终点的非最优子策略；
2）生产计划问题
状态定义为每阶段开始时的存储量xk，决策为每个阶段的产量uk，记每个阶段需求量为dk，状态转移方程为xk+1=xk+uk-dk,xk≥0,k=1,2,…,n.
设每阶段开工的固定成本费为a，生产单位成本费为b，每阶段单位数量产品储存费为c，阶段指标为vk(xk,uk)=cxk+a+b*uk或者是cxk；