动态规划

1 动态规划的发展及研究内容

动态规划是运筹学的一个分支,是求解决策过程最优化的数学方法,把多阶段过程转化为一系列单阶段问题,逐个求解的方法——动态规划。

主要用于:求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划(如之前讲的线性规划和非线性规划),只要人为引入时间因素,把它视为多阶段决策过程,也可以套用动态规划的方法。

重点:动态规划是求解某类问题的一种方法,而不是一种特殊算法,必须对具体问题进行具体分析。

1.1 决策过程的分类

根据过程的时间变量是离散的还是连续的,分为离散时间决策过程和连续时间决策过程;根据过程的演变是确定的还是随机的,分为确定性决策过程和随机性决策过程。其中应用最广的是确定性多阶段决策过程。

2 基本概念、基本方程和计算方法

2.1 动态规划的基本概念和基本方法

一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。

2.1.1 阶段

阶段是对整个过程的自然划分。通常根据时间顺序或者空间顺序特征来划分阶段,以便按照阶段的次序解决优化问题。阶段变量一般用$k=1,2,\cdots,n$表示。

2.1.2 状态

状态表示每个阶段开始时过程所处的自然状况。它应能描述过程的特征并且无后效性,即当某阶段的状态变量给定时,这个阶段以后过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是直接或间接可以观测的。

描述状态的变量称状态变量。变量允许取值的范围称允许状态集合用$x_k$表示第$k$阶段的状态变量,它可以是一个数或一个向量。用$X_k$表示第$k$阶段的允许状态集合。

根据过程演变的具体情况,状态变量可以是离散的或连续的。为了计算的方便有时将连续变量离散化;为了分析的方便有时又将离散变量视为连续的。
状态变量简称为状态。

2.1.3 决策

当一个阶段的状态确定后,可以作出各种选择从而演变到下一阶段的某个状态,这种选择手段称为决策,在最优控制问题中也称为控制。

描述决策的变量称为决策变量,变量允许取值的范围称为允许决策集合。用$u_k(x_k)$表示第$k$阶段处于状态$x_k$时的决策变量。它是$x_k$的函数,用$U_k(x_k)$表示$x_k$的允许决策集合。

2.1.4 策略

决策组成的序列称为策略。由初始状态$x_1$开始的全过程的策略记作$p_{1n}(x_1)$,也就是

$$ p_{1n}(x_1)={u_1(x_1),u_2(x_2),\cdots,u_n(x_n)} $$

由第$k$阶段的状态$x_k$开始到终止状态的后部子过程的策略集作$p_{kn}(x_k)$,也就是

$$ p_{kn}(x_k)={u_k(x_k),\cdots,u_n(x_n)},k=1,2,\cdots,n-1 $$

类似地,由第$k$到第$j$阶段的子过程的策略记作

$$ p_{kj}(x_k)={u_k(x_k),\cdots,u_j(x_j)} $$

可供选择的策略有一定的范围,称为允许策略集合,用$p_{1n}(x_1),p_{kn}(x_k),p_{kj}(x_k)$表示。

2.1.5 状态转移方程

在确定性过程中,一旦某阶段的状态和决策为已知,下阶段的状态便完全确定。用状态转移方程表示这种演变规律,写作

$$ x_{k+1}=T_k(x_k,u_k),k=1,2,\cdots,n. \tag{1} $$

2.1.6 指标函数和最优值函数

指标函数是衡量过程优劣的数量指标,它是定义在全过程和所有后部子过程上的数量函数,用$V_{k,n}(x_k,u_k,x_{k+1},\cdots,x_{n+1})$表示,$k=1,2,\cdots,n$。指标函数应该具有可分离性,即$V_{k,n}$可表为$x_k,u_k,V_{k+1,n}$的函数,记为:

$$ V_{k,n}(x_k,u_k,x_{k+1},\cdots,x_{n+1})=\phi_k(x_k,u_k,V_{k+1,n}(x_{k+1},u_{k+1},\cdots,x_{n+1})) $$

并且函数$\phi_k$对于变量$V_{K+1,n}$是严格单调的。

过程在第$j$阶段的阶段指标取决于状态$x_j$和决策$u_j$,用$v_j(x_j,u_j)$表示。指标函数由$v_j(j=1,2,\cdots,n)$组成,常见的形式有:

阶段指标之和,也就是:

$$ V_{k,n}(x_k,u_k,x_{k+1},\cdots,x_{n+1})=\sum^n_{j=k}v_j(x_j,u_j), $$

阶段指标之积,也就是:

$$ V_{k,n}(x_k,u_k,x_{k+1},\cdots,x_{n+1})=\prod_{j=k}^n v_j(x_j,u_j), $$

阶段指标之极大(极小),也就是:

$$ V_{k,n}(x_k,u_k,x_{k+1},\cdots,x_{n+1})=\max_{k \le j \le n}(\min)v_j(x_j,u_j) $$

这些形式下第$k$到第$j$阶段子过程的指标函数为$V_{k,j}(x_k,u_k,\cdots,x_{j+1})$

根据状态转移方程指标函数$V_{k,n}$还可用表示为状态$x_k$和策略$p_{kn}$的函数,即$V_{k,n}(x_k,p_{kn})$。在$x_k$给定时指标函数$V_{k,n}$对$p_{kn}$的最优值称为最优值函数,记为$f_k(x_k)$,即

$$ f_k(x_k)=opt \quad V_{k,n}(x_k,p_{kn}),满足p_{kn}\in p_{kn}(x_k) $$

其中opt可能根据具体需求取max或者min

2.1.7 最优策略和最优轨线

使指标函数$V_{k,n}$达到最优值的策略是从$k$开始的后部子过程的最优策略,记作$p_{kn}^*={u_k^*,\cdots,u_n^*}$。$p_{1n}^*$是全过程的最优策略,简称最优策略。从初始状态$x_1(=x_1^*)$出发,过程按照$p^*_{1n}$和状态转移方程演变所经历的状态序列$\left\{x_1^*,x_2^*,\cdots,x_{n+1}^*\right\}$称为最优轨线。

2.1.8 递归方程

如下方程称为递归方程

$$ \begin{cases} f_{n+1}(x_{n+1})=0或1\\ f_k(x_k)= opt_{u_k\in U_k(x_k)}\left\{v_k(x_k,u_k)\otimes{f_{k+1}(x_{k+1})}\right\},k=n,\cdots,1. \tag{2} \end{cases} $$

在上述方程中,当$\otimes$为加法时取$f_{n+1}(x_{n+1})=0$;当$\otimes$为乘法时,取$f_{n+1}(x_{n+1})=1$。动态规划递归方程是动态规划的最优性原理的基础,即:最优策略的子策略,构成最优子策略。用状态转移方程(1)和递归方程(2)求解动态规划的过程,是由$k=n+1$逆推至$k=1$,所以这种解法也被称为逆序解法。当然,对某些动态规划问题,也可以采用顺序解法。

这时候的状态转移方程和递归方程分别是:

$$ x_k=T^r_k(x_{k+1},u_k),k=1,\cdots,n\\ \begin{cases} f_0(x_1)=0或1\\ f_k(x_{k+1})=opt_{u_k\in{U^r_{k+1}(x_{k+1})}}\left\{v_k(x_{k+1},u_k)\otimes{f_{k-1}(x_{k})}\right\},k=1,\cdots,n. \end{cases} $$

综上所述,如果一个问题能够用动态规划来求解,那么我们可以按照下列步骤,先建立起动态规划的数学模型:

  1. 将过程划分成恰当的阶段
  2. 正确选择状态变量$x_k$,使它既能描述过程的状态,又满足无后效性,同时确定允许状态集合$X_k$。
  3. 选择决策变量$u_k$,确定允许决策集合$U_k(x_k)$。
  4. 写出状态转移方程
  5. 确定阶段指标$v_k(x_k,u_k)$以及指标函数$V_{kn}$的形式(阶段指标之和,阶段指标之积,阶段指标之极大或极小等)。
  6. 写出基本方程也就是最优值函数满足的递归方程,以及端点条件。

3 动态规划与静态规划的关系

动态规划与静态规划(线性与非线性规划等)研究的对象本质上都是在若干约束条件下的函数极值问题。这两种规划在很多情况下原则上可以相互转化。

动态规划可以看作求决策$u_1,u_2,\cdots,u_n$使指标函数$V_{1n}(x_1,u_1,u_2,\cdots,u_n)$达到最优(最大或最小)的极值问题,状态转移方程、端点条件以及允许状态集、允许决策集等是约束条件,原则上可以用非线性规划方法求解。

而一些静态规划只要适当引入阶段变量、状态、决策等就可以用动态规划方法求解。

举例子:用动态规划解下列非线性规划

$$ \max \quad \sum^n_{k=1}g_k(u_k);\\ s.t. \quad \sum^n_{k=1}u_k=a,u_k \ge 0.\\ $$

其中$g_k(u_k)$为任意的已知函数。

解:按照变量$u_k$的序号划分阶段,看作是$n$段决策过程。设状态为$x_1,x_2,\cdots,x_{n+1}$,去问题中的变量$u_1,u_2,\cdots,u_n$为决策。状态转移方程为:

$$ x_1=a,x_{k+1}=x_k-u_k,k=1,2,\cdots,n. $$

取$g_k(u_k)$为阶段指标,最优值函数的基本方程为(注意到$x_{n+1}=0$)

$$ f_k(x_k)=\max_{0 \le u_k \le x_k}[g_k(x_k)+f_{k+1}(x_{k+1})];\\ 0 \le x_k \le a,k=n,n-1,\cdots,2,1;\\ f_{n+1}(0)=0\\ $$

按照逆序解法求出对应于$x_k$每个取值的最优决策$u^*_k(x_k)$,计算至$f_1(a)$后即可利用状态转移方程得到最优状态序列$\left\{x_k^*\right\}$和最优决策序列$\left\{u_k^*(x_k^*)\right\}$

与静态规划相比,动态规划有其优越性:

  1. 能够得到全局最优解。由于约束条件确定的约束集合往往很复杂,即使指标函数较简单,用非线性规划方法也很难求出全局最优解。而动态规划方法把全过程化为 一系列结构相似的子问题,每个子问题的变量个数大大减少,约束集合也简单得多,易于得到全局最优解。特别是对于约束集合、状态转移和指标函数不能用分析形式给出的优化问题,可以对每个子过程用枚举法求解,而约束条件越多,决策的搜索范围越小,求解也越容易。对于这类问题,动态规划通常是求全局最优解的唯一方法。
  2. 可以得到一族最优解。与非线性规划只能得到全过程的一个最优解不同,动态规划得到的是全过程及所有后部子过程的各个状态的一族最优解。 有些实际问题需要这样的解族,即使不需要,它们在分析最优策略和最优值对于状态的稳定性时也是很有用的。当最优策略由于某些原因不能实现时,这样的解族可以用来寻找次优策略。
  3. 能够利用经验提高求解效率。如果实际问题本身就是动态的,由于动态规划方法反映了过程逐段演变的前后联系和动态特征, 在计算中可以利用实际知识和经验提高求解效率。如在策略迭代法中,实际经验能够帮助选择较好的初始策略,提高收敛速度。

动态规划的主要缺点是:

  1. 没有统一的标准模型,也没有构造模型的通用方法,甚至还没有判断一个问题能否构造动态规划模型的准则。这样就只能对每类问题进行具体分析,构造具体的模型。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力和灵活的技巧性,这就带来了应用上的局限性。
  2. 用数值方法求解时存在维数灾难。若一维状态变量有$m$个取值,那么对于$n$维问题,状态$x_k$就有$m^n$个值,对于每个状态值都要计算、存储函数$f_k(x_k)$,对于$n$稍大的实际问题的计算往往是不现实的。目前还没有克服维数灾的有效的一般方法

4 若干典型问题的动态规划模型

4.1 最短路线问题

对于这类问题,阶段按过程的演变划分,状态由各段的初始位置确定,决策为从各个状态出发的走向,即有$x_{k+1}=u_k(x_k)$,阶段指标为相邻两段状态间的距离$d_k(x_k,u_k(x_k))$,指标函数为阶段指标之和,最优值函数$f_k(x_k)$是由$x_k$出发到终点的最短距离(最小费用),基本方程为:

$$ f_k(x_k)=\min_{u_k(x_k)}[d_k(x_k,u_k(x_k))+f_{k+1}(x_{k+1})],k=n,\cdots,1;\\ f_{n+1}(x_{n+1})=0\\ $$

5.2 生产计划问题

对于此类问题,阶段按计划时间自然划分,状态定义为每阶段开始时的储存量$x_k$, 决策为每个阶段的产量$u_k$,记每个阶段的需求量(已知量)为$d_k$,则状态转移方程为:

$$ x_{k+1}=x_k+u_k-d_k,x_k \ge 0,k=1,2,\cdots,n. \tag{3} $$

设每阶段开工的固定成本费为 $a$,生产单位数量产品的成本费为$b$,每阶段单位数量产品的储存费为$c$,阶段指标为阶段的生产成本和储存费之和,即

$$ v_k(x_k,u_k)=cx_k+{ \begin{cases} a+bu_k,u_k \gt 0\\ 0 \end{cases} } \tag{4} $$

指标函数$V_{kn}$为$v_k$之和。最优值函数$f_k(x_k)$为从第$k$段的状态$x_k$出发到过程终结的最小费用,满足

$$ f_k(x_k) = \min_{u_k \in U_k}[v_k(x_k,u_k)+f_{k+1}(x_{k+1})],k=n,\cdots,1. $$

其中允许决策集合$U_k$由每个阶段的最大生产力决定。若设过程终结时允许存储量为$x^0_{n+1}$,则终端条件是

$$ f_{n+1}(x_{n+1}^0)=0 \tag{5} $$

(3)~(5)构成该问题的动态规划模型

5.3 资源分配问题

一种或几种资源(包括资金)分配给若干用户,或投资于几家企业,以获得最大的效益。资源分配问题可以是多阶段决策过程,也可以是静态规划问题,都能构造动态规划模型求解。

Last modification:August 15th, 2019 at 09:30 pm
如果觉得我的文章对你有用,请随意赞赏