教学论文核心期刊投稿用路径图求解动态规划问题

　　摘 要：本文先介绍了哪些问题常用动态规划的方法求解及建立动态规划模型的具体步骤，接着用一个具体的例子展示如何用路径图解决具体问题。

　　关键词：教学论文核心期刊,动态规范,路径图,多阶段决策

　　一、动态规划简介

　　动态规划是运筹学的一个分支，它是解决多阶段决策过程的最优化的一种数学方法。美国数学家贝尔曼(R.Bellman)等人在1951年根据一 类多阶段决策问题的特点，把多阶段决策问题变换为一系列互相关联的单阶段问题，然后逐个加以解决，从而创建了解决最优化问题的一种新的方法。动态规划的方 法在工程技术、企业管理、工农业生产及军事部门中都有广泛的应用，并且获得了显著的效果。可以用来解决最优路径问题、资源分配问题、设备更新问题、生产调 度问题、库存问题、装载问题、排序问题、货郎担问题、采购与销售问题、限期采购问题、生产过程最优控制问题等。

　　二、建立动态规划模型的步骤

　　动态规范模型在日常生产、生活中应用广泛，建立动态规范模型一般遵循以下步骤：

　　(1)将问题的过程划分成恰当的阶段(一般按时间或空间的先后顺序);

　　(2)正确选择状态变量SK ，使它既能描述过程的演变，又要满足无后效性;

　　(3)正确设立决策变量uk ，明确每阶段的允许决策集合Dk(Sk );(通常选择所求解问题的关键变量作为决策变量)

　　(4)根据第K阶段的状态变量和决策变量正确写出状态转移方程

　　(5)正确写出指标函数

　　指数函数应满足下面三个性质：①是定义在全过程和所以子过程上的数量函数; ② 要具有可分离性，并满足递推关系。③函数对变量 Vk+1，n要严格单调。

　　(6)写出动态规划的基本方程包括边界条件。

　　(7)求解模型。

　　三、用路径图求解动态规划问题应用举例

　　用动态规划的方法求解实际问题通常可以按上面的步骤来建立模型，有部分问题可以化为(最短)路径问题，用路径图能直观的理解上面的算法。

　　如某建筑公司新购置了四台挖掘机，准备分给甲、乙、丙三个公司，事先请专家调查了各分公司的经营情况，并对各种分配方案进行了经济效益的估计，见下表，其中机器数为0时的收益，是指已有的经营收益，问应如何分配这四台机器，使总的收益为最多?

　　本题用动态规划的常规方法建模求解可参看[1]，下面采用本文要讲的路径图的方法来求解，更直观易懂。

　　具体解答过程如下：

　　解：由于有三个公司，所以划分为三个阶段，状态变量 表示第k阶段初分配者手中拥有的机器总数，决策变量 表示第k阶段分配给第k个用户的机器数，状态转移方程为： Sk+1=sk-uk

　　阶段指标函数： vk(sk，uk)=gk(uk)表示k阶段公司k利用所分到的资源(机器)产生的收益;最优值函数fk(sk) 表示将机器数sk 分配给公司k到公司丙所获得的最大收益：

　　表示状态变量所取的值，状态连线上小于5的数字表示决策变量所取的值，[数字]表示该阶段的指标值(收益)， 表示该状态到最后一个公司的最大收益，粗线条表示最优策略路径，从上图很容易看出最大收益为164万元，最优策略是：u1=3，u2=0，u3=1 ，即分给甲3台，乙不分，丙1台时，总收益164万元最大。

　　结束语：

　　对于最段路径问题、资源分配问题、生产与存储计划问题，只要阶段不是太多，状态变量的取值不超过6个，一般可以采用路径图直观的求解出模型的解。

　　参考文献：

　　[1]岳宏志，蔺小林，运筹学[M]，东北财经大学出版社，2012.8.

　　[2]姜启源，谢金星，叶俊. 数学建模(第四版)[M]，北京：高等教育出版社，2011.

《教学论文核心期刊投稿用路径图求解动态规划问题》

本文由职称驿站首发，您身边的高端学术顾问

文章名称： 教学论文核心期刊投稿用路径图求解动态规划问题

文章地址： https://m.zhichengyz.com/p-27417