6动态规划.docx

7.1多阶段决策过程及实例在生产和科学实验中，有一类活动的过程，由于它的特殊性，可将过程分为若干个互相联系的阶段，在它的每一个阶段都需要作出决策，从而使整个过程达到最好的活动效果因此，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展当各个阶段决策确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动路线这种把一个问题可看作是一个前后关联具有链状结构的多阶段过程（如图2-1所示）就称为多阶段决策过程，也称序贯决策过程这种问题就称为多阶段决策问题图7-1在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前的状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义因此，把处理它的方法称为动态规划方法但是，一些与时间没有关系的静态规划（如线性规划、非线性规划等）问题，只要人为地引进“时间”因素，也可以把它视为多阶段决策问题，用动态规划方法去处理多阶段决策问题很多，现举例如下：例1 最短路线问题设某厂A要把一批货运到E城出售，中间可经过①～⑧城市，各城市间的交通线及距离如图2-2所示，问应选择什么路线，可使总距离最短？图 7-2 某厂货运交通线及距离示意图这是一个4阶段决策问题。

例2 生产与存贮问题某工厂生产并销售某种产品，已知今后4个月市场需求预测如表2-1所示，每月生产单位产品的费用为（千元）其中为生产的固定费用，为可变生产费率，为生产能力供应需求所剩余产品应存入仓库，每月库存单位产品的费用为（千元）计划开始和计划期末库存量都是0试制定4个月的生产计划，在满足用户需求的条件下使总费用最小表7-1月1234（需求）2324这也是一个4阶段决策问题例3 投资决策问题 某公司现有资金Q万元，在今后5年内考虑给A、B、C、D四个项目投资，这些项目的投资期限、回报率均不相同，问应如何确定这些项目每年的投资额，使到第五年末拥有资金的本利总额最大这是一个5阶段决策问题例4 设备更新问题企业在使用设备时都要考虑设备的更新问题，因为设备越陈旧所需的维修费用越多，但购买新设备则要一次性支出较大的费用现在，某企业要决定一台设备未来8年的更新计划，已预测了第j年购买设备的价格为，为设备经过j年后的残值，为设备连续使用j-1年后在第j年的维修费（j＝1，2，…，8），问应在哪年更新设备可使总费用最小这是一个8阶段决策问题，每年年初要作出决策是继续使用旧设备还是购买新设备更多的例子将在后面结合求解介绍。

7.2动态规划的基本概念和方法7.2.1动态规划的基本概念使用动态规划方法解决多阶段决策问题，首先要将实际问题改造成动态规划模型，此时要用到以下概念：（1）阶段 （2）状态 （3）决策和策略 （4）状态转移 （5）指标函数 下面我们结合例题说明这些概念1）阶段（stage）将所给问题的过程，按时间或空间特征分解成若干互相联系的阶段，以便按次序去求解每阶段的解，常用字母表示阶段变量例如在例1中，我们可以将A-E间的最短线路问题按其空间分布分解成一个四阶段决策问题第一阶段包括（A,1），（A,2）,(A,3)第二阶段包括从城市1、2、3到达城市4、5、6的交通线即（1，4）、（1，5）、（1，6）、（2，4）、（2，5）、（2，6）、（3，4）、（3，5）、（3，6）其余阶段依此类推在例2中，我们可以按时间把每个月作为一个阶段，共分为4个阶段本书规定：表示实际问题中的第一决策阶段在一个阶段决策问题中，表示最后一个决策阶段而有些书中存在相反规定）（2）状态（state）各阶段开始时的客观条件叫做状态描述各阶段状态的变量称为状态变量，常用表示第k阶段的状态变量，状态变量的取值集合称为状态集合，用Sk表示。

在例1中，第一阶段状态为A，第二阶段则有第三个状态：城市①，②，③状态变量的集合={A}，后面各段的状态集合分别是：={1,2,3},={4,5,6},={7,8}在例2中，我们可以把每月月初的产品库存量作为状态动态规划中的状态应具有如下性质：当某阶段状态给定以后，在这阶段以后过程的发展不受这段以前各段状态的影响也就是说，过程的过去历史只能通过当前状态去影响它未来的发展，这称为无后效性如果所选定的变量不具备无后效性，就不能作为状态变量来构成动态规划模型如例1中，当某段的初始状态即所在的城市选定以后，从这个状态以后的运货路线只与这个城市有关，不受以前的运货路线影响，所以是满足状态的无后效性的又例如，研究物体（把它看作一个质点）受外力作用后其空间运动的轨迹问题，从描述轨迹这点着眼，可以只选择坐标位置作为过程的状态，但这样不能满足无后效性，因为即使知道了外力的大小和方向，仍无法确定物体受力后的运动方向和轨迹，只有把位置和速度都作为过程的状态变量，才能确定物体运动下一步的方向和轨迹，实现无后效性要求3）决策和策略（Decision and Policy）当各阶段的状态确定以后，就可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策。

表示决策的变量称为决策变量，常用uk（sk）表示第k阶段当状态为sk时的决策变量在实际问题中，决策变量的取值往往限制在一定的范围内，我们称此范围为允许决策集合，常用Dk（sk）表示第k阶段从状态sk出发的允许决策集合，显然有uk（sk）∈Dk（sk）在例1中，第2阶段的状态集合S2={1，2，3}，从城市①出发，可选择走城市④，⑤，⑥，即其允许决策集合为D2（1），={4，5，6}如我们决定选择城市⑤，则此时决策变量可表示为：u2（1）=5在例2中，决策变量是各月的产品产量各段决策确定后，整个问题的决策序列就构成一个策略，用p1，n（u1，u2，…，u n）表示对每个实际问题，可供选择的策略有一定范围，称为允许策略集合，用P表示使整个问题达到最优效果的策略就是最优策略4）状态转移方程动态规划中本阶段的状态往往是上一阶段的决策结果如果给定了第k阶段的状态sk，本阶段决策为uk（sk），则第k+1阶段的状态sk+1也就完全确定，它们的关系可用公式sk+1=Tk（sk，uk）表示，由于它表示了由k阶段到k+1阶段的状态转移规律，所以称为状态转移方程例1中，状态转移方程为sk+1 = uk例2中，第k+1阶段的库存量等于第k阶段的库存量与产量的和减去当月的需求量，即sk+1 = sk+ uk-gk（5）指标函数用于衡量所选定策略优劣的数量指标称为指标函数。

一个n段决策过程，从1到n叫做问题的原过程，对于任意一个给定的k（1≤k≤n），从第k段到第n段的过程称为原过程的一个后部子过程V1，n（s1 ，p1，n）表示初始状态为s1采用策略p1，n时原过程的效益值，而Vk，n（sk ，pk，n）表示在第k阶段状态为sk采用策略pk，n时，后部子过程的效益值最优指标函数记为fk（sk），它表示从k阶段状态为sk采用最优策略p※k，n时，后部子过程的最优效益值fk（sk）与Vk，n（sk ，pk，n）间有关系：fk（sk）= Vk，n（sk ，p※k，n）=opt全称optimization，表示最优当k=1时，f1（s1）就是从初始状态s1到全过程结束的整体最优函数在例1中，指标函数是距离如第2阶段，状态为城市②时，V2，4表示从城市②到城市E的距离，而f2（2）则表示从城市②到城市E的最短距离本问题的总目标是求f1（A），即从城市A到城市E的最短距离而例2中，衡量决策效果的指标函数是生产与存储的费用最优指标函数则是指生产与存储费用之和最低本问题的总目标是求f1（0），即初始库存量为0时，1—4月的最低总费用7.2.2动态规划的基本思想我们结合例1最短路线问题介绍动态规划的基本思想。

上节已分析过，这是个多阶段问题，可以把A到E的路分成4段，第1段从A到城市①、②、③有三种选择，若我们把这段决策定为选择城市②，则②就是下一阶段的起点第2段从②状态出发，又可以有城市④、⑤、⑥三种选择，依此类推，可依阶段求出一个决策序列，即一个策略由于所选路线不同，会有若干个不同策略，我们希望得到一个最优策略，使它们所确定的路线是从A至E的最短路为了求得最短路，一种简单的方法可以求出所有从A至E的可能走法的路长并加以比较不难知道从A至E共有18条不同路径，每条路径要做4次加法，要求出最短路线需要作72次加法运算，17次比较运算，这种方法就是穷举法可以看出，当问题的段数很多，各段的状态也很多时，这种方法的计算量会大大增加，甚至使得求优成为不可能下面介绍动态规划方法动态规划方法基于贝尔曼(R.Bellman)等人提出的最优化原理，这个最优化原理指出：一个过程的最优策略具有这样的性质，即无论初始状态或初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策须构成最优策略动态规划最优性原理对应到该最短路问题是：从A点到E点的最短路线若经过sk点，则此路线由sk点到E点的后半部，必是由sk点到E点的最短路线。

现在我们利用动态规划最优性原理，由最后一段路线开始，向最初阶段递推求解，逐步求出各段各点到终点E的最短路线，最后求得A点到E点的最短路线上面我们已经规定了本例的阶段数、状态变量、决策变量，给出了转移方程、指标函数等再用表示由状态点出发，采用决策到达下一阶段点时的两点间距离第一步从k=4开始，状态变量可取两种状态⑦、⑧，它们到E点的路长分别为4，3第二步k=3，状态变量可取三个值④、⑤、⑥，这是经过一个中途点到达终点E的两级决策问题，从城市④到E有两条路线，需加以比较，取其中最短的，即这说明由城市④到终点E最短距离为7，其路径为④→⑦→E相应决策为即城市⑤到终点最短距离为5，其路径为⑤→⑧→E相应决策为即城市⑥到终点最短距离为5，其路径⑥→⑦→E相应决策为第三步k=2,这是具有三个初始状态①、②、③，要经过两个中途站才能到达终点的三级决策问题由于第3段各点④，⑤，⑥到终点E的最短距离已知，所以我们若求城市①到E的最短距离，只需以它们为基础，分别加上城市①与④、⑤、⑥的一段距离，加以比较取其短者即可即城市①到终点最短距离为9，其路径为①→⑤→⑧→E本段相应决策为第四步k=1,只要一个状态A，则即从城市A到城市E的距离为17。

本段决策为再按计算顺序反推可得最优决策序列{},即,,,所以最优路线为A→城市①→城市⑤→城市⑧→E从例1的计算过程中可以看出，在求解的各阶段，都利用了第段和k+1段的如下关系：①②这种递推关系称为动态规划的基本方程，②式称为边界条件上述最短路线的计算过程也可用图直观表示出来，如图2-3，每个结点上方的括号内的数，表示该点到终点E的最短距离连结各点到E点的粗线表示最短路径这种在图上直接计算的方法叫标号法图7-3容易算出这种方法只进行了18次加运算，11次比较运算，比穷举法计算量小而且随着问题阶段数的增加和复杂程度的提高，计算量将为指数规律减少其次，动态规划的计算结果不仅得到了从A到E的最短路线，而且得到了中间段任一点到E的最短路线，这对许多实际问题来讲，是很有意义的因为我们往往期望知道所有点到终点的最优决策，动态规划方法可以使我们得到整族的最优决策现将动态规划方法的基本思想总结如下：(1) 将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数，从而把问题化成一族同类型的子问题，然后逐个求解。