《动态规划方法的matlab实现及其应用》由会员分享，可在线阅读，更多相关《动态规划方法的matlab实现及其应用（8页珍藏版）》请在金锄头文库上搜索。
1、动态规划方法的matlab实现及其应用（龙京鹏，张华庆，罗明良，刘水林）（南昌航空大学，数学与信息科学学院，江西，南昌）摘要：本文运用matlab语言实现了动态规划的逆序算法，根据状态变量的维数，编写了指标函数最 小值的逆序算法递归计算程序。两个实例的应用检验了该程序的有效性，同时也表明了该算法程序对 众多类典型的动态规划应用问题尤其是确定离散型的应用问题的通用性，提供了求解各种动态规划问 题的有效工具。关键词：动态规划基本方程的逆序算法MATLAB实现MATLAB Achieve For Dynamic Programming and Its Application(JingpengLong
2、， HuaqingZhang， MingliangLuo， ShuilinLiu)(School of Mathematics and Information Science,Nanchang HangkongUniversity,Nanchang,China)Abstract:This article achieves the reverse algorithm of dynamic programming by using the matlab language，and prepares the recursive calculation program of reverse algori
3、thm which thetargetfunctionvalueisthesmallest.Theapplicationoftwoexamplesshowthattheprogram is effective，and this algorithm program is general to many typical application of dynamic programming,especially the application of deterministic discrete.This algorithm program provides a effective tool to t
4、he solution of a variety of dynamic programming problems. Key words:dynamic programming； reverse algorithm； Matlab achievement)+f动态规划是一类解决多阶段决策问题的数学方法， 在工程技术、科学管理、工农业生产及军事等领域都有 广泛的应用。在理论上，动态规划是求解这类问题全局 最优解的一种有效方法，特别是对于实际中某些非线性 规划问题可能是最优解的唯一方法。然而，动态规划仅 仅决多阶段决策问题的一种方法,或者说是考查问题的 一种途径，而不是一种具体的算法。就目前而言,动
5、态规 划没有统一的标准模型，其解法也没有标准算法,在实际 应用中，需要具体问题具体分析。动态规划模型的求解 问题是影响动态规划理论和方法应用的关键所在，而子 问题的求解和大量结果的存储、调用更是一个难点所 在。然而，随着计算机技术的快速发展,特别是内存容 量和计算速度的增加，使求解较小规模的动态规划问题 成为可能，从而使得动态规划的理论和方法在实际中的 应用范围迅速增加。目前，在计算机上实现动态规划的一般求解方法并 不多见，尤其是用来解决较复杂的具体问题的成果甚 少。本文从实际出发，利用数学工具软件matlab的强大 功能，对动态规划模型的求解方法做了尝试，编写出了 动态规划逆序算法的matl
6、ab程序，并结合“生产与存 储问题” E和“背包问题” E进行了应用与检验,实际证 明结果是令人满意的。 划分阶段 按照问题的时间或空间特征，把问题分为若 干个阶段。这些阶段必须是有序的或者是可排序的（即无 后向性），否则，应用无效。 选择状态将问题发展到各个阶段时所处的各种 客观情况用不同的状态表示，即称为状态。状态的选择 要满足无后效性和可知性，即状态不仅依赖于状态的转 移规律，还依赖于允许决策集合和指标函数结构。 确定决策变量与状态转移方程当过程处于某一 阶段的某个状态时，可以做出不同的决策,描述决策的变 量称为决策变量。在决策过程中，由一个状态到另一个 状态的演变过程称为状态转移。状态
7、转移就是根据上一 阶段的状态和决策来导出本阶段的状态。 写出动态规划的基本方程 动态规划的基本方程一 般根据实际问题可分为两种形式，逆序形式和顺序形式。 这里只考虑逆序形式。动态规划基本方程的逆序形式为fSk k(Sk+1( k+1) x D s& kk()k nn= , -1, ,1边界条件1动态规划的基本模型实际中，要构造一个标准的动态规划模型，通常需要 采用以下几个步骤：/ Sn+1( n+1) = 0 或 / S V S Xn n() = n n n(， )其中第k阶段的状态为&,其决策变量X表示状 sk的决策，状态转移方程为sk+i =Ts xkkk（，态处于 k阶段的允许决策集合记
8、为D skk（ ）, v s xkkk（，）为指标函数。当求解时，由边界条件从k n=开始，由后向前逆推, 逐阶段求出最优决策和过程的最优值，直到最后求出/ si（ 1）即得到问题的最优解。动态规划逆序解法计算程 序框图如下：3出)兰0动态规1J sk k()=T ) + f s (， J k+1、k+k=n2x D Skmin L k k()即 S x( k k k( 1)k nn= , -1, ,1边界条件J S V S xnn()=n n n(，) Sk+1自由始端和终端的动态规划，求指标函数最小值的 逆疗算法递归计算程序.况.(日|.)二 口口二二 r v, ( Sp_p琪玉兀,jDe
9、cisn,TransFun,ObjFun)j 二d标x函数态昏撰列代表表个阶段的r出-堂相应的允许决策集合% M 函数 SubObjFun (k存储f心海k.(m)% M_函数 TransFun (k,I x 是阶段k的状态值，uFun,SubObjFuJ状态由阶段k的状态值x求x,u)表示阶段k的指标函x,u)是状态转移函数，其中 是其决策集合% M_函数ObjFun (v,f)是第k阶段到最后阶段的指 标函数，当ibjFun (v,f)=v+f 时，输入 ObjFunopt由4列组,列向量，各元素分别表端状态-x的最优函数值k=length(x(1,:);%输出pT 线组，最优策略组，指标
10、pt=序号组，最优轨 值组;%调出心是各最优tp_(值组:popt% k为阶m为指标xisnan=isnan(x);曰t_vubm=f*ones(size(x);%t_vub函数值的上限内存替换f也f_opt=nan*onesCsize(x);!京甲同哂为非数 d_opt=f_opt; % d_o -态下的决策矩阵，初值为非数 tmp1 = find(x_isnan(:,k);状态值d不是非数)的下标状态下的最优值矩阵，初值pt为不同阶段不同状%找出第k阶段k=l 玖p2=le|:tmp2u=feval(DecisFun,k,x(tmp1I %求出相应的允许决策向量length(u);=1:t
11、mp3%有函数值以及最优决策Ligth(tmpl)；tmp3 =技k _-l_for j 出相应的最tmp=feval(SubObjFun,k,x(t该for语句是为了求停)ip1(i),k),u(j)(2)当状态变量是二维时，也即有两个状态变量，此时动态规划逆序求最小值的基本方程：f sk k()= k k k k min)，e ( ) 3 s x U f Sk k k k 如,)+ kx D s u U t.m，; if tmp=t_vubm(i,k)f_opt(tmp1(i),k)=tmp;d_opt(tmp1(i),k)=u(j);t_vubm(i,k)=tmp; end end en
12、d for ii=k- 1:-1:1%从后往前面递推求出f_opt以及d_opt tmp10=find(x_isnan(:,ii);tmp20=length(t mp10);for i=1:tmp20u=feval(DecisFun,ii,x(tmp10(i),ii); tmp30=length(u);for j=1:tmp30tmp00=feval(SubObjFun,ii,x(tmp10(i),ii), u(j);tmp40=feval(TransFun,ii,x(tmp10(i),ii),u(j);%由该状态值及相应的决策值求出下一阶段的状态值 tmp50=x(:,ii+1)-tmp40
13、; tmp60=find(tmp50=0);%找出下一阶段的状态值在x(:,ii + 1)的下标if isempty(tmp60)if nargin5tmp00=tmp00 + f_opt(tmp60(1),ii + 1);elsetmp00 = feval(ObjFun,tmp00,f_opt(tmp60(1), ii+1); endif tmp00=t_vubm(i,ii)f_opt(tmp10(i),ii)=tmp00;d_opt(i,ii)=u(j);t_vubm(tmp10(i),ii)=tmp00;endendendendendfval=f_opt(find(x_isnan(:,1
14、),1);% fval即为最有函数值矩阵p_opt=;tmpx=;tmpd=;tmpf=;tmp0=find(x_isnan(:,1);tmp01=length(tmp0); for i=1:tmp01tmpd(i)=d_opt(tmp0(i),1);-%求出第一阶段的决策值tmpx(i)=x(tmp0(i),1);%求出第一阶段的状态值tmpf(i)=feval(SubObjFun,1,tmpx(i),tm pd(i);%求出第一阶段的指标函数值p_opt(k*(i-1)+1,12 3 4)=1,tmpx(i),tmpd(i),tmpf(i);for ii=2:k%按顺序求出各阶段的决策值、状态值以及指标函数值tmpx(i)=feval(TransFun,ii-1,tmpx(i),tmpd(i) );tmp1=x(:,ii)-tmpx(i);tmp2=find(tmp1=0);if isempty(tmp2)tmpd(i)=d_opt(tmp2(1),ii);endtmpf(i)=feval(SubObjFun,ii,tmpx(i),tmpd( i);p_opt(k*(i-1)+ii,1234)=ii,tmpx(i),tmpd(i),tmpf(i);endendk nn= , -1, ,1边界条件f S V S X t Un
