《第14章-动态规划》由会员分享，可在线阅读，更多相关《第14章-动态规划（17页珍藏版）》请在金锄头文库上搜索。
1、精选优质文档-倾情为你奉上第14章 动态规划本章通过将实际问题当作多阶段决策过程来建立数学模型，学习和掌握动态规划的相关知识及其求解的逆序算法，并结合计算机编程解决实际问题。14.1 引例：生产计划的制定某工厂与用户订立合同，在四个月内出售一定数量的某种产品，产量限制为10的倍数，工厂每月最多生产100件，产品可以存储，存储费用为每台2百元，每个月的需求量及每件产品的生产成本见表14.1。表14.1 生产成本和需要量月份每件生产成本（元）需要量（件）170602727038012047660现在分别在（1）一月初没有存货可用和（2）一月初有20件存货可用这两种情况下确定每月的出产量，要求既能满
2、足每月的合同需求量，又使生产成本和存储费用达到最小。静态的看，本引例是一个整数规划问题，但这里我们可以把这个问题的解决动态地视为各月（一般称为阶段）先后作出决策（这里指生产量）的过程多阶段的决策过程，而在每个月作决策时，不能仅考虑本月的费用（一般称为阶段指标）因为本月的决策会对以后各月的决策产生影响，因此应考虑从本月直到第四月末的总费用（总指标），而每月的决策依赖于各月初仓库的存货量（一般称为始端）和以前各月如何造成这货存量的情况无关（称为无后效性）。在例2中我们将计算一月初无存货可用时的最优决策见表2表14.2 最优生产计划1月2月3月4月月初存储量（件）040700产量（件）1001005
3、060则第四月的决策即为月初仓储数为0时的最优决策，第三、四月的决策即为第三月初仓储数为70时的最优决策，以及第二、三、四月的决策即为第二月初仓储数为40时的最优决策。因为若不然，如对应于第三月初仓储数为70时，第三、四月的最优决策是分别生产80件和30件（即这样的费用比分别生产50件和60件更省），则我们保留第一、二月的生产数，而把第三第四月分别改为80件和30件，这个方案显然优于原来的方案，这和原来的方案是最优相矛盾。这个性质可以简述为：最优决策的任何截断仍是最优的（最优性原理）。把这一最优化问题视为符合最优性原理、无后效性的多阶段决策过程并进行求解的方法称为动态规划方法。14.2 动态规
4、划的基本理论复习14.2.1基本思想与逆序解法的直观回顾前面我们已简单介绍了动态规划。为了更便于 了解动态规划的基本思想、描述方式和逆序解法，我们来看一个确定网络最短路径问题的例子。例1：（最短路径的确定）以下是一个赋权图，两顶点连线上的数字表示距离，确定一条从始点到终点铺设管道并使总距离最短的路线。 V4 1 6 2 V11 3 V2 3 3 V8 2 5 V14 4 5 6 V5 5 8 1 V12 2 5 3 V16V1 3 V9 2 6 6 V15 3 8 7 V6 3 V13 V3 6 8 3 V10 3 V7 4 图14.1直观上我们有这样一个重要常识：如果由起点经过点和点而到达终
5、点是一条最短路线，则由点出发经过点到达终点的这条路线，对于从点出发 到达终点的所有可能选择的不同路线来说，必定也是最短路线。例如在最短路线问题中，若找到了是由点到点最短路线，则应该是由点出发到达终点的所有可能选择的不同路线中最短路线。这一特征即为上面所提到的最优性原理：最优性决策的任何截断仍是最优的，这是动态规划的基本原理。根据最优性原理，寻找最短路线可从最后一段开始，用由后向前逐步递推的方法，求出各点到点的最短路线，最后求得由点到点的最短路线，所以动态规划的逆序求解方法是从终点逐段向始点方向寻找最短路线的一种方法。下面逐段完成计算。例1当然可以用图与网络实验中介绍的Dijkstra算法来求解
6、，但这里我们将把该问题看成6个阶段的决策过程，并逆序逐段求解，从而较直观地揭示动态规划的基本思想。时，以表示由到的最短距离，以表示由到的最短距离，则，。时，出发点有三个、和。若从出发有和两个选择，以表示由到的最短距离，表示由到的距离，表示由到的距离，表示相应的选择或决策，则：可见，其最短路径为。同理，从出发也有和两个选择，、和意义与上面相似，则：可见，其最短路径为。从出发，同样有：可见，其最短路径为。时，有三个出发点、和，同样计算如下：可见，其最短路径为。可见，其最短路径为。可见，其最短路径为。时，同样计算有：，；，；，时，同样计算有：，；，时，只有一个出发点，则：可见，所以本题的最短路径为。
7、14.2.2 动态规划的基本概念及其数学描述（1）阶段 整个问题的解决可分为若干个相互联系的阶段依次进行。通常按时间或空间划分阶段，描述阶段的变量称为阶段变量，计为。（2）状态 状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况。个阶段的状态通常用状态变量描述。常用表示第阶段的状态变量。个阶段的决策过程有个状态。用规划方法解决多阶段决策问题时，要求整个过程具有无后效性，即：如果某阶段的状态给定，则此阶段以后过程的发展不受以前状态的影响，未来状态只依赖于当前状态。（3）决策 某一阶段的状态确定后，可以作出各种选择从而演变到下一阶段某一状态，这种选择手段称为决策。描述决策的变
8、量称为决策变量。决策变量限制的取值范围称为允许决策集合。用表示第阶段处于状态时的决策变量，它是的函数，用表示的允许决策的集合。比如在例1中，。（4）策略 一个由每个阶段的决策按顺序排列组组成的集合称为策略，用表示。即。由第阶段的状态开始到终止状态的后部子过程的策略记为，即。在实际问题中，可供选择的策略有一定范围，此范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。（5）状态转移方程 如果第个阶段状态变量为，作出的决策，那么第阶段的状态变量也被完全确定。用状态转移方程表示这种演变规律，写作。（6）指标函数和最优值函数 指标函数是系统执行某一策略所产生结果的数量表示，是用来衡量策
9、略优劣的数量指标，它定义在全过程和所有后部子过程上，分别用和表示。即和。过程在某个阶段的阶段指标函数（或阶段效益）是衡量该阶段决策优劣的数量指标，它取决于状态和决策，用表示。如例1中两顶点间的距离是阶段指标函数，而指标函数则是直到终点的距离的和。根据不同的实际问题，效益可以是利润、距离、产量或资源等。指标函数往往是各阶段效益的某种形式。指标函数的最优值称为最优函数。（7）最优策略和最优轨线 使指标函数达到最优值的策略是从阶段开始的后部子过程的最优策略，记为。是全过程的最优策略，简称为最优策略。从初始状态出发，过程按照和状态转移方程演变所经历的状态序列称为最优轨线。14.3 动态规划逆序算法的M
10、ATLAB程序14.3.1逆序算法的基本方程由例1的求解过程可以看出下面的方程在动态规划逆序求解中起着本质的作用称此为动态规划逆序求解的基本方程。可以把建立动态规划模型归纳成以下几个步骤（1）将问题恰当地划分为若干个阶段；（2）正确选择状态变量，使它既能描述过程的演变，又满足无后效性；（3）规定决策变量，确定每个阶段允许决策集合；（4）写出状态转移方程；（5）确定个阶段各种决策的阶段指标，列出计算各阶段最优后部策略指标的基本方程。14.3.2动态规划逆序算法的MATLAB程序Dynprog.m%M函数dynprog.mfunctionp_opt,fval=dynprog(x,DecisFun,
11、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_
12、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);for I=1:tmp2 u=feval(DecisFun,k,x(i,k); tmp3=length(u); for j=1:tmp3 tmp=feval(ObjFun,k,x(tmpl(i),k), u(j); if tmp=t_vub,
13、 f_opt(i,k)=tmp; d_opt(i,k)=u(j); t_vub=tmp;end;end;end%逆推计算各阶段的递归调用程序for ii=k-1:-1:1 tmp10=find(x_isnan(:,ii);tmp20=length(tmp10); for i=1:tmp20 u=feval(DecisFun,ii,x(i,ii);tmp30=length(u); for j=1:tmp30 tmp00=feval(ObjFun,ii,x(tmp10(i),ii),u(j); tmp40=feval(TransFun,ii,x(tmp10(i),ii),u(j); tmp50=x(:,ii+1)-tmp40; tmp60=find(tmp50= =0); ifisempty(tmp60), tmp00=tmp00+f_opt(tmp60(1),ii+1); if tmp00=t_vubm(i,ii) f_opt(i,ii)=tmp00; d_opt(i,ii)=u(j); t_vubm(i,ii)=tmp00;end;end;end;end;end;fval=f_opt(tmp1,1);% 记录最优决策、最优轨线和相应指标函数值p_opt=;tmpx=;tmpd=;tmpf=;tmp0=find(x_isnan(;,1)
