《动态规划方法的matlab实现及其应用》由会员分享，可在线阅读，更多相关《动态规划方法的matlab实现及其应用(6页珍藏版)》请在人人文库网上搜索。

1、动态规划方法的动态规划方法的 matlabmatlab 实现及其应用实现及其应用 (龙京鹏，张华庆，罗明良，刘水林) (南昌航空大学，数学与信息科学学院，江西，南昌) 摘要摘要：本文运用 matlab 语言实现了动态规划的逆序算法，根据状态变量的维数，编写了指标函数最 小值的逆序算法递归计算程序。两个实例的应用检验了该程序的有效性，同时也表明了该算法程序对 众多类典型的动态规划应用问题尤其是确定离散型的应用问题的通用性，提供了求解各种动态规划问 题的有效工具。 关键词关键词：动态规划基本方程的逆序算法MATLAB 实现 MATLABMATLAB A Achievechieve ForFor D。

2、ynamicDynamic ProgrammingProgramming andand ItsIts ApplicationApplication (Jingpeng Long，Huaqing Zhang，Mingliang Luo，Shuilin Liu ) (School of Mathematics and Information Science,Nanchang Hangkong University,Nanchang,China) Abstract:Abstract:This article achieves the reverse algorithm of dynamic prog。

3、ramming by using the matlab language，and prepares the recursive calculation program of reverse algorithm which the target function value is the smallest.The application of two examples show that the program is effective，and this algorithm program is general to many typical application of dynamic pro。

4、gramming, especially the application of deterministic discrete.This algorithm program provides a effective tool to the solution of a variety of dynamic programming problems. KeyKey words:words: dynamic programming；reverse algorithm；Matlab achievement 动态规划是一类解决多阶段决策问题的数学方法, 在工程技术、科学管理、工农业生产及军事等领域都有 广。

5、泛的应用。在理论上,动态规划是求解这类问题全局最 优解的一种有效方法,特别是对于实际中某些非线性规 划问题可能是最优解的唯一方法。然而,动态规划仅仅决 多阶段决策问题的一种方法,或者说是考查问题的一种 途径,而不是一种具体的算法。就目前而言,动态规划没 有统一的标准模型,其解法也没有标准算法,在实际应用 中,需要具体问题具体分析。动态规划模型的求解问题是 影响动态规划理论和方法应用的关键所在,而子问题的 求解和大量结果的存储、调用更是一个难点所在。然而, 随着计算机技术的快速发展,特别是内存容量和计算速 度的增加,使求解较小规模的动态规划问题成为可能,从 而使得动态规划的理论和方法在实际中的应。

6、用范围迅速 增加。 目前,在计算机上实现动态规划的一般求解方法并 不多见,尤其是用来解决较复杂的具体问题的成果甚少。 本文从实际出发,利用数学工具软件matlab 的强大功能, 对动态规划模型的求解方法做了尝试,编写出了动态规 划逆序算法的matlab程序，并结合“生产与存储问题” 1 和“背包问题” 1进行了应用与检验,实际证明结果是令 人满意的。 1 1动态规划的基本模型动态规划的基本模型 实际中,要构造一个标准的动态规划模型,通常需要 采用以下几个步骤: 划分阶段按照问题的时间或空间特征,把问题 分为若干个阶段。这些阶段必须是有序的或者是可排序 的(即无后向性) ,否则,应用无效。 选择。

7、状态将问题发展到各个阶段时所处的各种 客观情况用不同的状态表示,即称为状态。状态的选择要 满足无后效性和可知性,即状态不仅依赖于状态的转移 规律,还依赖于允许决策集合和指标函数结构。 确定决策变量与状态转移方程当过程处于某一 阶段的某个状态时,可以做出不同的决策,描述决策的变 量称为决策变量。在决策过程中,由一个状态到另一个状 态的演变过程称为状态转移。状态转移就是根据上一阶 段的状态和决策来导出本阶段的状态。 写出动态规划的基本方程动态规划的基本方程 一般根据实际问题可分为两种形式,逆序形式和顺序形 式。这里只考虑逆序形式。动态规划基本方程的逆序形 式为 11 () () (,)() kkk。

8、 kkkkkkk xDs fsoptg v s xfs + =+ ,1,1kn n= 边界条件 11 ()0 nn fs + = 或 ()(,) nnnnn fsv sx= 其中第k阶段的状态为 k s ,其决策变量 k x 表示状 态处于 k s 的决策,状态转移方程为 1 (,) kkkk sT sx + =, k 阶段的允许决策集合记为 () kk D s , (,) kkk v sx 为 2 指标函数。 当求解时,由边界条件从k n= 开始, 由后向前逆 推,逐阶段求出最优决策和过程的最优值, 直到最后求 出 11 ( )f s 即得到问题的最优解。 动态规划逆序解法计算 程序框图如下。

9、： 2 2基本方程逆序算法的基本方程逆序算法的matlabmatlab程序程序 (1)动态规划逆序求最小值的基本方程： 11 () ()min (,)() kkk kkkkkkk xDs fsg v sxfs + =+ ,1,1kn n= 边界条件 ()(,) nnnnn fsv sx= 1 (,) kkkk sT sx + =。 自由始端和终端的动态规划，求指标函数最小值的 逆序算法递归计算程序： function p_opt,fval=dynprog(x,DecisFun,SubObjFu n,TransFun,ObjFun) % x为状态变量，一列代表一个阶段的状态 % M_函数Deci。

10、sFun(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列组成， p_opt=序号组， 最优轨线组， 最优策略组，指标函数值组; % 输出fval是列向量，各元素分别表示p_opt各最优策 略组对应始端状态x的最优函数值 k=length(x(1,:);% k。

11、为阶段数 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=length(tmp1); for i=1:tmp2 u=feval(DecisFun,k,x(tmp1(i),k); % 求出相应的允许决策向量 tmp3=length(u)。

12、; for j=1:tmp3% 该for语句是为了求 出相应的最有函数值以及最优决策 tmp=feval(SubObjFun,k,x(tmp1(i),k),u(j) ; if tmp6 f=106; else f=3+u+0.5*(x+u-d(k); end End % TransFun.m functions=TransFun(k,x,u) d=2 3 2 4; s=x+u-d(k); 在matlab命令空间输入： x1=0:4;s=nan*ones(5,1);s(1)=0; x=s x1 x1 x1; p_opt,fval=dynprog(x,DecisFun,SubObjF un,Tra。

13、nsFun) 运行结果如下： p_opt = 1.000005.00009.5000 2.00003.000000 3.000006.000011.0000 4.00004.000000 fval = 20.5000 从上面的结果可知，每个时期的最优决策为： X1=5,x2=0,x3=6,x4=0。 其相应的最小总成本为20.5千元。 从上面的结果中还可以看出，各个时期初的库存量 分别为：V1=0,v2=2,v3=0,v4=4 这里的结果与文1的结果完全符合，这说明该程序 是可行的。 3.2 二维背包问题 有一个人带一个背包上山， 其可携带物品重量的限度 为10公斤，背包体积限制为22立方米。。

14、假设有3种物品可 供他选择装入背包。已知第i种物品每件重量为w(i)公 斤，体积为v(i)立方米，携带该物品xi件产生的效益值 为c(i)*xi。问此人该如何选择携带物品，才能使产生的 效益值最大。其中 w=3 4 5;v=8 6 4;c=4 5 6; 解：用动态规划方法求解， 按物品的种类数将该问题分为3各个阶段； si表示用于装入第i种物品到第3种物品的总重 量； ti表示用于装入第i种物品到第3种物品的总体 积； ui表示装入第i种物品的件数； 可得状态转移方程： 11 ( )*,( )* kkkkkk ssc ku ttc ku + = 允许决策集合为： (,)|0min(,) kk 。

15、kkkk kk st D s uuu wv = 最优值函数(,) kkk fs t表示当总重量不超过 k s公 斤，总体积不超过 k t立方米背包装入第t种物品到第3种 物品产生的最大效益值。 可得基本方程： 111 (,) 444 ( , )max ( ( )*(,), ( , )03,2,1 kkkk kkkkkkk uDs t f s tc kufst f v tk + =+ = 下面同样用计算程序dynprog1.m求解： 在使用此程序先要建立下面3个M_函数： % DecisFun1.m function u1,u2=DecisFun1(k,x1,x2) w=3 4 5;v=8 6 。

16、4; u1=0:1:min(x1/w(k),x2/v(k);u2=1; 6 % 因为这里只有一个决策变量，故令u2恒为1， 这样是程序的需要， % 也可减少计算量，此时u2就没有任何意义， 只是一个虚拟的量 % SubObjFun1.m function f=SubObjFun1(k,x1,x2,u1,u2) c=4 5 6; f=-c(k)*u1;% 求最大值转化为求最小值 % TransFun1.m function s=TransFun1(k,x1,x2,u1,u2) w=3 4 5;v=8 6 4; s(1)=x1-u1*w(k);s(2)=x2-u1*v(k); 在matlab命令空。

17、间输入： a1=0:10;b1=0:22;s1=nan*ones(11,1);s1(1)=10; s2=nan*ones(23,1);s2(1)=22; x1=s1 a1 a1;x2=s2 b1 b1; p_opt,fval=dynprog1(x1,x2,DecisFun1,S ubObjFun1,TransFun1) 运行结果如下： p_opt = 1102221-8 24611-5 300010 fval = -13 从 上 面 的 结 果 可 知 ： 最 优 装 入 方 案 为 ： u1=2,u2=1,u3=0;也即各种物品分别装入2件， 1件， 0件， 此时产生的最大效益值为13。 此。

18、程序得出的结果与事实相符合，说明此程序是可 行的。 4 4程序使用的几点说明程序使用的几点说明 程序dynprog.m只能使用于具体问题中只有一个状 态变量的情形，程序dynprog1.m适用于状态变量为二维 的情形。这两个程序都要求各阶段状态变量的取值是离 散的。 要使用好这两个程序，关键要做到以下三点： 一、要掌握动态规划的基本原理与基本概念，能对 具体问题写出基本方程的逆序形式，要认真读懂这两个 程序，理解程序中每个变量所代表的含义，只有理解了 程序，才能更好地使用程序，才能对运行出的结果进行 分析； 二、对具体问题要作具体的分析，要用动态规划的 方法求解问题，要能够写出状态转移方程、基。