动态规划方法的matlab实现及其应用

动态规划方法的 matlab 实现及其应用 龙京鹏 张华庆 罗明良 刘水林 南昌航空大学 数学与信息科学学院 江西 南昌 摘要 本文运用 matlab 语言实现了动态规划的逆序算法 根据状态变量的维数 编写了指标函数最 小值的逆序算法递归计算程序 两个实例的应用检验了该程序的有效性 同时也表明了该算法程序对 众多类典型的动态规划应用问题尤其是确定离散型的应用问题的通用性 提供了求解各种动态规划问 题的有效工具 关键词 动态规划 基本方程的逆序算法 MATLAB 实现 MATLAB Achieve For Dynamic Programming and Its Application JingpengLong HuaqingZhang MingliangLuo ShuilinLiu School of Mathematics and Information Science Nanchang Hangkong University 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 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 solution of a variety of dynamic programming problems Key words dynamic programming reverse algorithm Matlab achievement 动态规划是一类解决多阶段决策问题的数学方法 在工程技术 科学管理 工农业生产及军事等领域都有 广泛的应用 在理论上 动态规划是求解这类问题全局 最优解的一种有效方法 特别是对于实际中某些非线性 规划问题可能是最优解的唯一方法 然而 动态规划仅 仅决多阶段决策问题的一种方法 或者说是考查问题的 一种途径 而不是一种具体的算法 就目前而言 动态规 划没有统一的标准模型 其解法也没有标准算法 在实际 应用中 需要具体问题具体分析 动态规划模型的求解 问题是影响动态规划理论和方法应用的关键所在 而子 问题的求解和大量结果的存储 调用更是一个难点所在 然而 随着计算机技术的快速发展 特别是内存容量和 计算速度的增加 使求解较小规模的动态规划问题成为 可能 从而使得动态规划的理论和方法在实际中的应用 范围迅速增加 目前 在计算机上实现动态规划的一般求解方法并 不多见 尤其是用来解决较复杂的具体问题的成果甚少 本文从实际出发 利用数学工具软件 matlab 的强大功能 对动态规划模型的求解方法做了尝试 编写出了动态规 划逆序算法的 matlab 程序 并结合 生产与存储问题 1 和 背包问题 1 进行了应用与检验 实际证明结果是 令人满意的 1 动态规划的基本模型 实际中 要构造一个标准的动态规划模型 通常需要 采用以下几个步骤 划分阶段 按照问题的时间或空间特征 把问题分为若 干个阶段 这些阶段必须是有序的或者是可排序的 即无 后向性 否则 应用无效 选择状态 将问题发展到各个阶段时所处的各种 客观情况用不同的状态表示 即称为状态 状态的选择 要满足无后效性和可知性 即状态不仅依赖于状态的转 移规律 还依赖于允许决策集合和指标函数结构 确定决策变量与状态转移方程 当过程处于某一 阶段的某个状态时 可以做出不同的决策 描述决策的变 量称为决策变量 在决策过程中 由一个状态到另一个 状态的演变过程称为状态转移 状态转移就是根据上一 阶段的状态和决策来导出本阶段的状态 写出动态规划的基本方程 动态规划的基本方程一 般根据实际问题可分为两种形式 逆序形式和顺序形式 这里只考虑逆序形式 动态规划基本方程的逆序形式为 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 x n n n n n 其中第 k 阶段的状态为 sk 其决策变量 xk 表示状 sk 的决策 状态转移方程为 sk 1 T s xk k k 态处于 k 阶段的允许决策集合记为 D sk k v s xk k k 为指标函数 2 当求解时 由边界条件从 k n 开始 由后向前逆推 逐 阶段求出最优决策和过程的最优值 直到最后求出 f s1 1 即得到问题的最优解 动态规划逆序解法计算程序框 图如下 3 4 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 自由始端和终端的动态规划 求指标函数最小值的 逆序算法递归计算程序 function p 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 列组成 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 length tmp1 for i 1 tmp2 u 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 end end for ii k 1 1 1 从后往前面递推求出 f opt 以及 d opt tmp10 find x isnan ii tmp20 length t mp10 for i 1 tmp20 u feval DecisFun ii x tmp10 i ii tmp30 length u for j 1 tmp30 tmp00 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 isempty tmp60 if nargin 5 tmp00 tmp00 f opt tmp60 1 ii 1 else tmp00 feval ObjFun tmp00 f opt tmp60 1 ii 1 end if tmp00 t vubm i ii f opt tmp10 i ii tmp00 d opt i ii u j t vubm tmp10 i ii tmp00 end end end end end fval f opt find x isnan 1 1 fval 即为最有函数值矩阵 p opt tmpx tmpd tmpf tmp0 find x isnan 1 tmp01 length tmp 0 for i 1 tmp01 tmpd 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 按顺序求出各 阶段的决策值 状态值以及指标函数值 5 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 end tmpf i feval SubObjFun ii tmpx i tmpd i p opt k i 1 ii 1 2 3 4 ii tmpx i tmpd i tmpf i end end 2 当状态变量是二维时 也即有两个状态变量 此时 动态规划逆序求最小值的基本方程 f sk k k k k k k t min gv s x t u f sk k k k k k 1 k 1 x D s u U t k 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 如下 function p opt fval dynprog1 x1 x2 DecisFun Sub ObjFun TransFun ObjFun x1 x2 为二维状态变量 其中 x1 x2 的取值是相 互独立的 这里矩阵 x1 与 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 opt nan ones k1 k2 k d opt1 f opt d opt2 f opt tmp11 find x1 isnan k tmp12 length t mp11 tmp21 find x2 isnan k tmp22 length t mp21 for i 1 tmp12 for t 1 tmp22 u1 u2 feval DecisFun k x1 tmp11 i k x2 tmp21 t k tmp13 length u1 tmp14 length u2 for j 1 tmp13 for l 1 tmp14 tmp feval SubObjFun k x1 tmp11 i k x2 tmp21 t k u1 j u2 l if tmp t vubm i t k f opt tmp11 i tmp21 t k tmp d opt1 tmp11 i tmp21 t k u1 j d opt2 tmp11 i tmp21 t k u2 l t vubm i t k tmp end end end end end for ii k 1 1 1 tmp011 find x1 isnan ii tmp021 find x2 isnan ii tmp012 length tmp011 tmp022 length tmp021 for i 1 tmp012 for t 1 tmp022 u1 u2 feval DecisFun ii x1 tmp011 i ii x2 tmp021 t ii 令 u2 恒为 1 tmp013 length u1 tmp014 length u2 for j 1 tmp013 for l 1 tmp014 tmp000 feval SubObjFun ii x1 tmp011 i i i x2 tmp021 t ii u1 j u2 l tmp100 feval TransFun ii x1 tmp011 i ii x2 tmp021 t ii u1 j u2 l tmp200 x1 ii 1 tmp100 1 tmp300 x2 ii 1 tmp100 2 tmp400 find tmp200 0 tmp500 find tmp300 0 if isempty tmp400 else tmp000 feval ObjFun tmp000 f opt tmp400 1 mp500 1 ii 1 end if tmp0006 在第 k 时期末库存量为 vk 1 时的存储费 为 h vk k 0 5 v x dk k k 故第 k 时期 内的总成本为 c x h vk k k k 则阶 段指标函数为 V v c x h vk k k k k k 最优值函数 f Vk k 表示从第 k 阶段初始库存量为 V k 时到第四阶段末库存量为 0 时的最小总费用 则有递 推关系式 f vk k max 0 dk vk xkmin 6 V vk k f vk 1 k 1 f v5 5 0 x d v4 44 其中 xk max 0 d vk k 这是因为一方面每阶段生 产的下限为 0 另一方面由于要保证供应 故第 k 阶段 7 末的库存量 vk 1 必须非负 即 v x dk k k 0 所以 x d v k k k v k 的取值范围为 0 min d m dj k 其中 v1 0 v5 0 j k 为求出该问题的最优值 利用上面的计算程序 dynprog m 根据上面所述的阶段指标函数 状态转移函 数和递推关系式 编写出下面 3 个 M 函数 以备主程序 调用 DecisFun m function u DecisFun k x d 2 3 2 4 m 6 if k 4 u d k x else u max 0 d k x m End SubObjFun m function f SubObjFun k x u d 2 3 2 4 if u 0 f 0 5 x u d k else if u 6 f 10 6 else f 3 u 0 5 x u d k end End TransFun m function s 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 TransFun 运行结果如下 p opt 1 0000 0 5 0000 9 5000 2 0000 3 0000 0 0 3 0000 0 6 0000 11 0000 4 0000 fval 20 5000 4 0000 0 0 从上面的结果可知 每个时期的最优决策为 X1 5 x2 0 x3 6 x4 0 其相应的最小总成本为 20 5 千元 从上面的结果中还可以看出 各个时期初的库存量 分别为 V1 0 v2 2 v3 0 v4 4 这里的结果与文 1 的结果完全符合 这说明该程 序是可行的 3 2 二维背包问题 有一个人带一个背包上山 其可携带物品重量的限 度为 10 公斤 背包体积限制为 22 立方米 假设有 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 种物品的件数 可得状态转移方 程 sk 1 s ck u tk k k 1 t ck uk k 允许决策集合为 s tk k Ds u k k uk 0 ukmin w vk k 最优值函数 f s tk k k 表示当总重量不超过 sk 公斤 总体积不超过 tk 立方米背包装入第 t 种物品到 第 3 种物品产生的最大效益值 可得基本方程 f s tk k k u D s tk maxk k k ck u f s tk k 1 k 1 k 1 f v t4 4 4 0 k 3 2 1 下面同样用计算程序 dynprog1 m 求解 在使用此 程序先要建立下面 3 个 M 函数 DecisFun1 m function u1 u2 DecisFun1 k x1 x2 w 3 4 5 v 8 6 4 u1 0 1 min x1 w k x2 v k u2 1 因为这里只有一个决策变量 故令 u2 恒为 1 这样是程序的需要 也可减少计算量 此时 u2 就没有任何意义 只是一个虚拟的量 SubObjFun1 m function f SubObjFun1 k x1 x2 u1 u2 c 4 5 6 f c k u1 求最大值转化为求最小值 8 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 命令空间输入 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 1 10 22 2 1 8 2 4 6 1 1 5 3 0 0 0 1 0 fval 13 从 上面 的结 果可 知 最优 装入 方案 为 u1 2 u2 1 u3 0 也即各种物品分别装入 2 件 1 件 0 件 此时产生的最大效益值为 13 此程序得出的结果与事实相符合 说明此程序是可 行的 4 程序使用的几点说明 程序 dynprog m 只能使用于具体问题中只有一个状 态变量的情形 程序 dynprog1 m 适用于状态变量为二维 的情形 这两个程序都要求各阶段状态变量的取值是离 散的 要使用好这两个程序 关键要做到以下三点 一 要掌握动态规划的基本原理与基本概念 能 对具体问题写出基本方程的逆序形式 要认真读懂这两 个程序 理解程序中每个变量所代表的含义 只有理解 了程序 才能更好地使用程序 才能对运行出的结果进 行分析 二 对具体问题要作具体的分析 要用动态规划 的方法求解问题 要能够写出状态转移方程 基本方程 以及允许决策集合 并要根据这些方程在 matlabruan 软件中建立四个 M 函数 以备主程序调用 三 每个阶段的状态变量的取值一定要合理地离 散化 5 结束语 本文中运用 matlab 语言实现了动态规划 包括状 态变量二维情形 的逆序算法 两个实例的应用检验了 该程序的有效性 同时也表明了该算法程序对众多类典 型的动态规划应用问题尤其是确定离散型的应用问题的 通用性 本文拓展了文 2 中有关动态规划逆序算法的 matlab 程序实现 由原来的一维情形扩展到二维情形 这是一个进步 当问题的阶段数和各阶段的状态数较小 时 这两个程序能够运行出结果 但当问题的阶段数较 和各阶段的状态数较大时 这两个程序运行时就要花费 较长的时间 有时甚至是运行不出结果来 因为花费的 时间太长 参考文献 1 运筹学 教材编写组 运筹学 M 北京 清华大学 出版社 2005 6 2 胡良剑 丁晓东 孙晓君 数学实验 使用 MATLAB M 上海 上海科技出版社 2001 3 张志涌 精通 MATLAB6 5 M 北京 北京航空航天 大学出版社 2003 4 刘保柱 苏彦华 张宏林 MATLAB7 0 从入门到精 通 修订版 北京 人民邮电出版社 2010