第14章-动态规划

1第14章动态规划本章通过将实际问题当作多阶段决策过程来建立数学模型，学习和掌握动态规划的相关知识及其求解的逆序算法，并结合计算机编程解决实际问题。14.1引例：生产计划的制定某工厂与用户订立合同，在四个月内出售一定数量的某种产品，产量限制为10的倍数，工厂每月最多生产100件，产品可以存储，存储费用为每台2百元，每个月的需求量及每件产品的生产成本见表14.1。表14.1生产成本和需要量月份每件生产成本（元）需要量（件）170602727038012047660现在分别在（1）一月初没有存货可用和（2）一月初有20件存货可用这两种情况下确定每月的出产量，要求既能满足每月的合同需求量，又使生产成本和存储费用达到最小。静态的看，本引例是一个整数规划问题，但这里我们可以把这个问题的解决动态地视为各月（一般称为阶段）先后作出决策（这里指生产量）的过程——多阶段的决策过程，而在每个月作决策时，不能仅考虑本月的费用（一般称为阶段指标）因为本月的决策会对以后各月的决策产生影响，因此应考虑从本月直到第四月末的总费用（总指标），而每月的决策依赖于各月初仓库的存货量（一般称为始端）和以前各月如何造成这货存量的情况无关（称为无后效性）。在例2中我们将计算一月初无存货可用时的最优决策见表22表14.2最优生产计划1月2月3月4月月初存储量（件）040700产量（件）1001005060则第四月的决策即为月初仓储数为0时的最优决策，第三、四月的决策即为第三月初仓储数为70时的最优决策，以及第二、三、四月的决策即为第二月初仓储数为40时的最优决策。因为若不然，如对应于第三月初仓储数为70时，第三、四月的最优决策是分别生产80件和30件（即这样的费用比分别生产50件和60件更省），则我们保留第一、二月的生产数，而把第三第四月分别改为80件和30件，这个方案显然优于原来的方案，这和原来的方案是最优相矛盾。这个性质可以简述为：最优决策的任何截断仍是最优的（最优性原理）。把这一最优化问题视为符合最优性原理、无后效性的多阶段决策过程并进行求解的方法称为动态规划方法。14.2动态规划的基本理论复习14.2.1基本思想与逆序解法的直观回顾前面我们已简单介绍了动态规划。为了更便于了解动态规划的基本思想、描述方式和逆序解法，我们来看一个确定网络最短路径问题的例子。例1：（最短路径的确定）以下是一个赋权图，两顶点连线上的数字表示距离，确定一条从始点1v到终点16v铺设管道并使总距离最短的路线。V4162V113V233V825V14456V5581V12253V16V13V9266V15387V63V13V3683V103V74图14.13直观上我们有这样一个重要常识：如果由起点1v经过iv点和jv点而到达终点16v是一条最短路线，则由点iv出发经过jv点到达终点16v的这条路线，对于从iv点出发到达终点的所有可能选择的不同路线来说，必定也是最短路线。例如在最短路线问题中，若找到了1615128521vvvvvvv是由1v点到16v点最短路线，则1615128vvvv应该是由8v点出发到达终点的所有可能选择的不同路线中最短路线。这一特征即为上面所提到的最优性原理：最优性决策的任何截断仍是最优的，这是动态规划的基本原理。根据最优性原理，寻找最短路线可从最后一段开始，用由后向前逐步递推的方法，求出各点到16v点的最短路线，最后求得由1v点到16v点的最短路线，所以动态规划的逆序求解方法是从终点逐段向始点方向寻找最短路线的一种方法。下面逐段完成计算。例1当然可以用图与网络实验中介绍的Dijkstra算法来求解，但这里我们将把该问题看成6个阶段的决策过程，并逆序逐段求解，从而较直观地揭示动态规划的基本思想。6k时，以)(146vf表示由14v到16v的最短距离，以)(156vf表示由15v到16v的最短距离，则4)(146vf，3)(156vf。5k时，出发点有三个11v、12v和13v。若从11v出发有14v和15v两个选择，以)(115vf表示由11v到16v的最短距离，),(14115vvd表示由11v到14v的距离，),(15115vvd表示由11v到15v的距离，)(115vu表示相应的选择或决策，则：可见14115)(vvu，其最短路径为161411vvv。同理，从12v出发也有14v和15v两个选择，)(125vf),(14125vvd、),(15115vvd和)(125vu意义与上面相似，则：735,43min)(),(),(),(min)(1561511514613115115vfvvdvfvvdvf532,45min)(),(),(),(min)(1561512514614125125vfvvdvfvvdvf4可见15125)(vvu，其最短路径为161512vvv。从13v出发，同样有：5135131461451315615()min(,)(),(,)()min64,639fvdvvfvdvvfv可见15135)(vvu，其最短路径为161513vvv。4k时，有三个出发点8v、9v和10v，同样计算如下：752,72min)(),(),(),(min)(1251284115118484vfvvdvfvvdvf可见1284)(vvu，其最短路径为1615128vvvv。692,51min)(),(),(),(min)(1351394125129494vfvvdvfvvdvf可见1294)(vvu，其最短路径为1615129vvvv。893,53min)(),(),(),(min)(1351310412512105104vfvvdvfvvdvf可见12104)(vvu，其最短路径为16151210vvvv。3k时，同样计算有：13)(43vf，843)(vvu；10)(53vf，853)(vvu9)(63vf，963)(vvu；12)(73vf，1073)(vvu2k时，同样计算有：13)(22vf，522)(vvu；16)(32vf，632)(vvu1k时，只有一个出发点1v，则：5可见211)(vvu，所以本题的最短路径为1615128521vvvvvvv。14.2.2动态规划的基本概念及其数学描述（1）阶段整个问题的解决可分为若干个相互联系的阶段依次进行。通常按时间或空间划分阶段，描述阶段的变量称为阶段变量，计为k。（2）状态状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况。个阶段的状态通常用状态变量描述。常用kx表示第k阶段的状态变量。n个阶段的决策过程有1n个状态。用规划方法解决多阶段决策问题时，要求整个过程具有无后效性，即：如果某阶段的状态给定，则此阶段以后过程的发展不受以前状态的影响，未来状态只依赖于当前状态。（3）决策某一阶段的状态确定后，可以作出各种选择从而演变到下一阶段某一状态，这种选择手段称为决策。描述决策的变量称为决策变量。决策变量限制的取值范围称为允许决策集合。用)(kkvu表示第k阶段处于状态kx时的决策变量，它是kx的函数，用)(kkxD表示kx的允许决策的集合。比如在例1中，65422,,)(vvvxD。（4）策略一个由每个阶段的决策按顺序排列组组成的集合称为策略，用p表示。即)(,),(),()(22111nnxuxuxuxp。由第k阶段的状态kx开始到终止状态的后部子过程的策略记为)(kkxp，即)(,),(),()(11nnkkkkkkxuxuxuxp。在实际问题中，可供选择的策略有一定范围，此范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。（5）状态转移方程如果第k个阶段状态变量为kx，作出的决策ku，那么第1k阶段的状态变量1kx也被完全确定。用状态转移方程表示这种演变规律，写作),(1kkkkuxTx。18163,135min)(),(),(),(min)(323112221111vfvvdvfvvdvf6（6）指标函数和最优值函数指标函数是系统执行某一策略所产生结果的数量表示，是用来衡量策略优劣的数量指标，它定义在全过程和所有后部子过程上，分别用V和kV表示。即),,,,,,,(12121nnxxxuuuV和),,,,,(1nknkkxxuuV。过程在某个阶段j的阶段指标函数（或阶段效益）是衡量该阶段决策优劣的数量指标，它取决于状态jx和决策ju，用),(jjjxuv表示。如例1中两顶点间的距离是阶段指标函数，而指标函数则是直到终点16v的距离的和。根据不同的实际问题，效益可以是利润、距离、产量或资源等。指标函数往往是各阶段效益的某种形式。指标函数的最优值称为最优函数。（7）最优策略和最优轨线使指标函数kV达到最优值的策略是从阶段k开始的后部子过程的最优策略，记为***,,nkkuup。*p是全过程的最优策略，简称为最优策略。从初始状态)(*11xx出发，过程按照*p和状态转移方程演变所经历的状态序列},,{*1*1nxx称为最优轨线。14.3动态规划逆序算法的MATLAB程序14.3.1逆序算法的基本方程由例1的求解过程可以看出下面的方程在动态规划逆序求解中起着本质的作用1,,1,),,(,0)()(|)())(,(min)(11111nnkuxTxxfxDuxfxuxvxfkkkknnkkkkkkkkkkk称此为动态规划逆序求解的基本方程。可以把建立动态规划模型归纳成以下几个步骤（1）将问题恰当地划分为若干个阶段；（2）正确选择状态变量，使它既能描述过程的演变，又满足无后效性；（3）规定决策变量，确定每个阶段允许决策集合；（4）写出状态转移方程；（5）确定个阶段各种决策的阶段指标，列出计算各阶段最优后部策略指标的基本方程。714.3.2动态规划逆序算法的MATLAB程序Dynprog.m%M函数dynprog.mfunction[p_opt,fval]=dynprog(x,DecisFun,ObjFun,TransFun)%[p_opt,fval]=dynprog(x,DecisFun,ObjFun,TransFun)%自由始端和终端的动态规划，求指标函数最小值的逆序算法递归计算程序。x是状态变量，一列代表一个阶段状态；%M函数DecisFun（k,x）由阶段k的状态变量x求出相应的允许决策变量；%M函数ObjFun(k,x,u)是阶段指标函数，M函数TransFun(k,x,u)是状态转移函数，其中x是阶段k的某状态变量，u是相应的决策变量；%输出p_opt由4列构成，p_opt=[序号组；最优轨线组；最优策略组；%指标函数组];fval是一个列向量，各元素分别表示p_opt各最优策略组对应始端状态x的最优函数组；k=length(x(1,:));f_opt=nan*ones(size(x));d_opt=f_opt;t_vubm=inf*ones(size(x));x_isnan=~isnan(x);t_vub=inf;%计算终端相关值tmpl=find(x_isnan(:,k));tmp2=length(tmpl);forI=1:tmp2u=feval(DecisFun,k,x(i,k));tmp3=length(u);forj=1:tmp3tmp=feval(ObjFun,k,x(tmpl(i),k),u(j));iftmp=t_vub,f_opt(i,k)=tmp;d_opt(i,k)=u(j);t_vub=tmp;end;end;end%逆推计算各阶段的递归调用程序forii=k-1:-1:1tmp10=find(x_isnan(:,ii));tmp20=length(tmp10