资源描述:
《基于动态规划的生产计划优化模型研究与应用》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、基于动态规划的生产计划优化模型研究与应用/竺竺竺///基于动态规划的生产计划优化模型研究与应用0引言胡明.黄营(佛山科学技术学院计算机系,佛山528000)摘要:动态规划是运筹学的一个分支,是一种多阶段决策过程,可用于解决多目标决策问题,以使系统的总效果最优以某企业生产计划的优化安排为实例.在该企业产品的生产能力,生产成本,库存成本等约束务件下,利用动态规划方法建立生产计划安排模型,通过模型求解解决了该企业产品生产计划的优化问题.同时以精练的c++代码实现了相应程序.关键词:动态规划;生产计划;优化;C++企业在保证一定销售量的前提下.在
2、制定生产计划时要考虑生产和贮存两种费用生产费用通常取决于生产率(单位时间的产量1,生产率越高费用越大;贮存费用自然由已经生产出来的产品数量决定.数量越多费用越大.所谓生产计划这里简单地看作是到每一刻为止的累积产量.建模目的是寻求优化的生产计划.使完成预定销售量所需的总费用最小或尽可能的小『1】.动态规划(DynamicProgramming)是运筹学的一个分支.是一种多阶段决策过程.主要用于解决多目标决策问题,以使系统的总效果摄优121.这个性质非常适合于生产计划控制系统的动态特征笔者基于某企业产品的生产能力,生产成本,库存成本前提下,利
3、用动态规划方法解决了该企业产品生产计划的优化问题.1动态规划的基本概念和原理1.1基本概念①阶段.阶段指对整个过程的自然划分.通常按时问或空间特征分解成若干互相联系的阶段.以便按阶段的次序解决优化问题.描述阶段的变量称为阶段变量.用k表示;②状态.每一个阶段所处的自然状况或客观条件称为状态.状态变量用s表示,状态变量集合用S表示.状态具有无后效性,即在某一阶段以后过程的发展不受以前状态的影响.仅受当前状态的制约.根据收稿日期:2009—04—16修稿日期:2009—06-28作者简介:胡明(1971一),男,湖北松滋人,实验师,硕士多阶段
4、决策过程的时间参量特征.过程分为离散决策过程和连续决策过程.为了计算方便,有时将连续变量离散化:为了分析方便.有时又将离散变量视为连续的:③决策.当各阶段的状态确定以后,可以作出不同的选择.从而确定下一阶段状态.这个选择称为决策.决策变量用uk(s)表示,即第k阶段状态处于s时的决策变量.所有决策的集合称为全过程策略;④允许决策集合.即决策变量的取值范围,用Dk(Sk)表示;⑤状态转移方程.系统由某阶段的一个状态转变到下一阶段的另一状态称状态转移.体现转移规律的方程称状态转移方程"l=,)或(s扣i=.(,);⑥阶段指标.衡量某阶段决策效
5、果的数量指标^,);⑦指标函数.衡量选定策略决策效果的数量指标.用.(,P)表示第k阶段状态为,后部子策略为P时,后部子过程的指标函数值;相应的最优指标函数值记为(s).1.2基本原理动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件.要做到这一点,必须先将问题的过程分成几个相互联系的阶段.恰当地选取状态变量和决策变量及定义函数.从而把一个大问题化成一组同类型的子问题,然后逐个求解翻.即从初始MODERNCOMPUTER2009.7现代计算机^总第三____期v现代计算机^总第:二-_期\竺竺竺状态和边界条件开始.逐段递
6、推.在每一个子问题的求解中,均利用了它前面子问题的结果,依次进行,最后子问题的解.就是整个问题的最终解其中建立递推方程组是动态规划的核心但值得注意的是,动态规划不同于线性规划.动态规划是求解某类问题的一种方法.是考察问题的一种途径,而不是一种特殊算法.也就是说,动态规划是一种决策方式,并没有固定的求解方法.用丰富的想象力建立模型.用创造性的技巧去求解是动态规划的关键[41.1.3Bellman最优化原理"最优化原理"是动态规划的核心.所有动态规划问题的递推关系都是根据这个原理建立起来的最优性原理,即整个过程的最优策略具有这样的性质:无论过
7、程过去的状态和决策如何.对前面的决策所形成的状态而言.余下的诸决策必须构成最优策略简而言之,最优性原理的含义就是:最优策略的任何一部分子策略也必须是最优的2动态规划的数学模型和求解步骤2.1动态规划的数学模型根据决策过程行进方向与(多阶段)实际问题行进方向的同异.可将动态规划求解方法分为顺序解法和逆序解法.顺序解法的数学模型如下:f(sh1)=opt{(s¨,uk)①"(sk)lfo(s1)--0或I其中①表示+或x.逆序解法的数学模型如下:f(sk)=opt{Vk(,Uk)①l(sh1)}【£件l(.)---o或I其中0表示+或×.Uk
8、∈Dk()k=l,2,?一,nukEDk(sh1)k=n,n—I,?--,I其中,.)=0或I或(s.)或i称为边界条件.2.2动态规划的求解步骤利用动态规划求解实际问题,其求解步骤如下:①确