动态规划方法的matlab实现及其应用.doc
《动态规划方法的matlab实现及其应用.doc》由会员分享,可在线阅读,更多相关《动态规划方法的matlab实现及其应用.doc(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 algorithm
3、 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 the
4、solution of a variety of dynamic programming problems. Key words:dynamic programming;reverse algorithm;Matlab achievement8动态规划是一类解决多阶段决策问题的数学方法, 在工程技术、科学管理、工农业生产及军事等领域都有广泛的应用。在理论上,动态规划是求解这类问题全局最优解的一种有效方法,特别是对于实际中某些非线性规划问题可能是最优解的唯一方法。然而,动态规划仅仅决多阶段决策问题的一种方法,或者说是考查问题的一种途径,而不是一种具体的算法。就目前而言,动态规划没有统一的标准模型
5、,其解法也没有标准算法,在实际应用中,需要具体问题具体分析。动态规划模型的求解问题是影响动态规划理论和方法应用的关键所在,而子问题的求解和大量结果的存储、调用更是一个难点所在。然而, 随着计算机技术的快速发展,特别是内存容量和计算速度的增加,使求解较小规模的动态规划问题成为可能,从而使得动态规划的理论和方法在实际中的应用范围迅速增加。目前,在计算机上实现动态规划的一般求解方法并不多见,尤其是用来解决较复杂的具体问题的成果甚少。本文从实际出发,利用数学工具软件matlab 的强大功能, 对动态规划模型的求解方法做了尝试,编写出了动态规划逆序算法的matlab程序,并结合“生产与存储问题”1 和“
6、背包问题”1进行了应用与检验,实际证明结果是令人满意的。1 动态规划的基本模型实际中,要构造一个标准的动态规划模型,通常需要采用以下几个步骤:划分阶段 按照问题的时间或空间特征,把问题分为若干个阶段。这些阶段必须是有序的或者是可排序的(即无后向性) ,否则,应用无效。选择状态 将问题发展到各个阶段时所处的各种客观情况用不同的状态表示,即称为状态。状态的选择要满足无后效性和可知性,即状态不仅依赖于状态的转移规律,还依赖于允许决策集合和指标函数结构。确定决策变量与状态转移方程 当过程处于某一阶段的某个状态时,可以做出不同的决策,描述决策的变量称为决策变量。在决策过程中,由一个状态到另一个状态的演变
7、过程称为状态转移。状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。写出动态规划的基本方程 动态规划的基本方程一般根据实际问题可分为两种形式,逆序形式和顺序形式。这里只考虑逆序形式。动态规划基本方程的逆序形式为f sk k() = opt gv s x ( k k k(,)+f sk+1( k+1) x D sk k k()k nn= , 1,1边界条件f sn+1( n+1) = 0或 f s v s xn n() = n n n(,)其中第k 阶段的状态为sk,其决策变量xk表示状 sk的决策,状态转移方程为sk+1 =T s xk k k( , ), 态处于k 阶段的允许决策集合记
8、为D sk k() , v s xk k k(,) 为指标函数。当求解时,由边界条件从k n= 开始, 由后向前逆推,逐阶段求出最优决策和过程的最优值, 直到最后求出 f s1( 1) 即得到问题的最优解。动态规划逆序解法计算程序框图如下:2 基本方程逆序算法的matlab程序(1)动态规划逆序求最小值的基本方程:f sk k() = x D skmin k k() gv s x( k k k(,) +f sk+1( k+1)k nn= , 1,1边界条件 f s v s xn n() = n n n(,) sk+1 =T s xk k k(,) 。自由始端和终端的动态规划,求指标函数最小值的
9、逆序算法递归计算程序:functionp_opt,fval=dynprog(x,DecisFun,SubObjFu n,TransFun,ObjFun)% x为状态变量,一列代表一个阶段的状态%M_函数DecisFun(k,x)表示由阶段k的状态值x求出相应的允许决策集合% M_函数SubObjFun(k,x,u)表示阶段k的指标函数% M_函数TransFun(k,x,u)是状态转移函数,其中x 是阶段k的状态值,u是其决策集合% M_函数ObjFun(v,f)是第k阶段到最后阶段的指标函数,当ObjFun(v,f)=v+f时,输入ObjFun(v,f)可以省略% 输出p_opt由4列组成,
10、p_opt=序号组,最优轨线组,最优策略组,指标函数值组; % 输出fval是列向量,各元素分别表示p_opt各最优策略组对应始端状态x的最优函数值k=length(x(1,:);% k为阶段数x_isnan=isnan(x); t_vubm=inf*ones(size(x);%t_vubm为指标函数值的上限f_opt=nan*ones(size(x);% f_opt为不同阶段、状态下的最优值矩阵,初值为非数 d_opt=f_opt; % d_opt为不同阶段不同状态下的决策矩阵,初值为非数tmp1=find(x_isnan(:,k);% 找出第k阶段状态值(不是非数)的下标tmp2=leng
11、th(tmp1); for i=1:tmp2u=feval(DecisFun,k,x(tmp1(i),k);% 求出相应的允许决策向量 tmp3=length(u);for j=1:tmp3% 该for语句是为了求出相应的最有函数值以及最优决策tmp=feval(SubObjFun,k,x(tmp1(i),k),u(j); 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 endend for ii=k-1:-1:1% 从后往前面递推求出f_opt以及d_opt tmp10=f
12、ind(x_isnan(:,ii);tmp20=length(tmp10);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;tmp60=find(tmp50=0);% 找出下一阶段的状态值在x(:,ii+1)的下标 if
13、 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; endendendend endfval=f_opt(find(x_isnan(:,1),1);% fval即为最有函数值矩阵p_opt=;tmpx=;tmpd=;tmpf=; tmp0=fi
14、nd(x_isnan(:,1);tmp01=length(tmp0); for i=1:tmp01 tmpd(i)=d_opt(tmp0(i),1);% 求出第一阶段的决策值tmpx(i)=x(tmp0(i),1);% 求出第一阶段的状态值tmpf(i)=feval(SubObjFun,1,tmpx(i),tmpd(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),tmp
15、d (i);tmp1=x(:,ii)-tmpx(i);tmp2=find(tmp1=0); if isempty(tmp2) tmpd(i)=d_opt(tmp2(1),ii);end tmpf(i)=feval(SubObjFun,ii,tmpx(i),tmpd(i);p_opt(k*(i-1)+ii,1234)=ii,tmpx(i),tmpd(i),tmpf(i); endend(2)当状态变量是二维时,也即有两个状态变量,此时动态规划逆序求最小值的基本方程:f sk k() = k k k k k t (min), ( ) (gv s x t u f sk k k k k(,)+ k+1
16、( k+1)x D s u U tk nn= , 1,1边界条件f s v s x t un n() = n n n n n(,),sk+1 =T s xk k k(,),tk+1 =P t uk k k(,)此时上面的程序就无能为力了,为此在程序 dynprog.m基础上进行拓展,我们得到状态变量为二维情况下的指标函数最小值的逆序算法递归计算程序:dynprog1.m,如下:functionp_opt,fval=dynprog1(x1,x2,DecisFun,SubObjFun,TransFun,ObjFun)% (x1,x2)为二维状态变量,其中x1,x2的取值是相互独立的,这里矩阵x1与
17、x2的列数应相同,该程序考虑决策变量也是二维%DecisFun(k,x1,x2),SubObjFun(k,x1,x2,u1, u2),TransFun(k,x1,x2,u1,u2)等M_函数的含义与一维的情形一样,只是它们的参数相应的增加了,ObjFun函数的含义及参数保持不变% p_opt,fval的含义与一位情形一样,只是它们的维数增加了% 下面程序的思路与算法同一维基本相同,只是相应矩阵的维数增加了k1,k=size(x1);k2,k=size(x2); x1_isnan=isnan(x1);x2_isnan=isnan(x2); t_vubm=inf*ones(k1,k2,k);f_o
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 动态 规划 方法 matlab 实现 及其 应用
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【天****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【天****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。