动态规划模型在指派问题中的应用

《动态规划模型在指派问题中的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、编号0809313毕业论文（2012届本科）题目：动态规划模型在指派问题中的应用学院：数学与统计学院专业：数学与应用数学作者姓名：景诚指导教师：李拓职称：副教授完成日期：2012年5月30日二○一二年五月15动态规划模型在指派问题中的应用景诚指导教师:李拓(河西学院数学与应用数学专业2012届3班13号甘肃张掖734000)摘要本文利用动态规划的基本理论和方法,考虑了两类一般的非标准指派问题,对它们进行了总结和归纳,得出了一类更一般的非标准指派问题.通过实例,运用所建立的动态规划模型对其进行了求解.关键词动态规划;多阶段决策问题;指派问题;目标函数.中图分类号O224Applicationo

2、ftheDynamicProgrammingModelinAssignmentproblemJingChengInstructorLiTuo(NO.13,Class3of2012.SpecialtyofMathematicsandAppliedMathematics,HexiUniversity,Zhangye,Gansu,734000)Abstract:ThispaperusingthebasictheoryandtheDynamicprogrammingmethodconsidersthetwokindsofgenerallynon-standardassignmentproblem,s

3、ummarizesandconcludesthem,finallyitdrawstheconclusionthatreachesaclassofmoregeneralthanstandardassignmentproblem.Throughouttheexample,usingthedynamicprogrammingmodelgetsitsconclusion.Keywords:TheDynamicProgrammingModel;Multistagedecisionproblem;TheAssignmentproblem;Objectivefunction.1引言动态规划是解决多阶段决策

4、过程最优化的一种方法,它是由美国数学家贝尔曼（RichardBellman)等人在1951年提出来的,他们针对多阶段决策问题的特点,提出了解决这类问题的最优化原理,并成功解决了生产管理、工程技术中遇到的许多决策问题.在现代社会中,动态规划已经成为企业管理中的一种重要决策方法,人们用它能解决很多棘手的问题,如最优路径的选择、资源的最优分配、生产计划的最优决策等等.在现实生活中,我们还经常会遇到这种情况:有项工作,每一项工作可以由一人完成,同时有个人,每一个人可以完成一项工作.要确定完成项工作效率最高或者15总工时最小的分配工作方案,此问题被称为是标准指派问题,即当时的指派问题.但我们在解决实际

5、问题时常常还会遇到下列情况,即人们在工作的分配过程中,有以下特征之一的指派问题:(1)工作项目数与人数不相等;(2）某人不能做某项工作（某事不能由某人做,无法接受的指派）;(3)某人可以同时被指派多个任务;(4)某事可以由多人共同完成;(5)目标函数是与指派有关的总效用最大或最小的函数.该类指派问题被称为是非标准指派问题.由于指派问题也是属于多阶段决策问题,所以本文主要利用动态规划的基本原理和方法解决一类较一般的非标准指派问题,即有项工作欲指派个人去做,当时,要求每项工作只能由一个人去做,第个人可以同时做项工作（某人可以同时被指派多个任务）,其中是待求未知数,满足(为第个人所需工作数的上下限

6、)及(即每个工作都有人做),为已知常数;当时,要求每个人只做一项工作,第项工作可以由个人共同去做（某事可以由多人共同完成）,其中是待求未知数,满足(为第项工作所需人数的上下限)及(即每个人都有工作),为已知常数;第个人做第项工作所用的工作时间或工作效益为.确定使总耗用时间最少或使总效益最大的指派问题.记上述问题为.当且时,问题便是中的问题.当且时,问题便是中的问题.所以问题是一类更一般的非标准指派问题,在经营管理实践中更有意义.本文将应用所总结归纳的动态规划模型对这一类非标准指派问题进行求解,并用匈牙利法对其进行检验,说明本文所运用方法的正确性.2预备知识定义2.1（多阶段决策过程）多阶段决

7、策过程是一类特殊的活动过程,这个过程可以按时间顺序分解成若干相互联系的阶段,我们把它称之为“时段”,在每一个时段上都要作出决策,全部过程的决策构成了一个决策序列.多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最优.由于各阶段决策间有机地联系着,一个阶段决策的执行将影响到下一阶段的决策,以至于影响总体效果,所以决策者在每个阶段决策时不应仅考虑单个阶段最优,还应考虑对最终目标的影响,从而作出对全局来讲是