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

编号 0809313 毕业论文 （ 2012 届本科）题 目： 动态规划模型在指派问题中的应用 学 院： 数学与统计学院 专 业： 数学与应用数学 作者姓名： 景诚 指导教师： 李拓 职称： 副教授 完成日期： 2012 年 5 月 30 日二一二年 五 月动态规划模型在指派问题中的应用景诚 指导教师:李拓(河西学院 数学与应用数学专业 2012届3班13号 甘肃张掖 734000)摘 要 本文利用动态规划的基本理论和方法, 考虑了两类一般的非标准指派问题, 对它们进行了总结和归纳, 得出了一类更一般的非标准指派问题. 通过实例, 运用所建立的动态规划模型对其进行了求解.关键词 动态规划; 多阶段决策问题; 指派问题; 目标函数.中图分类号 O224 Application of the Dynamic Programming Model in Assignment problemJing Cheng Instructor Li Tuo (NO.13,Class 3 of 2012.Specialty of Mathematics and Applied Mathematics , Hexi University,Zhangye,Gansu,734000)Abstract: This paper using the basic theory and the Dynamic programming method considers the two kinds of generally non-standard assignment problem,summarizes and concludes them, finally it draws the conclusion that reaches a class of more general than standard assignment problem.Throughout the example, using the dynamic programming model gets its conclusion.Keywords: The Dynamic Programming Model; Multi stage decision problem; The Assignment problem; Objective function.1 引言动态规划是解决多阶段决策过程最优化的一种方法, 它是由美国数学家贝尔曼（Richard Bellman)等人在1951年提出来的, 他们针对多阶段决策问题的特点, 提出了解决这类问题的最优化原理, 并成功解决了生产管理、工程技术中遇到的许多决策问题.在现代社会中, 动态规划已经成为企业管理中的一种重要决策方法, 人们用它能解决很多棘手的问题, 如最优路径的选择、资源的最优分配、生产计划的最优决策等等. 在现实生活中, 我们还经常会遇到这种情况: 有项工作, 每一项工作可以由一人完成, 同时有个人, 每一个人可以完成一项工作. 要确定完成项工作效率最高或者总工时最小的分配工作方案, 此问题被称为是标准指派问题, 即当时的指派问题. 但我们在解决实际问题时常常还会遇到下列情况, 即人们在工作的分配过程中, 有以下特征之一的指派问题: (1)工作项目数与人数不相等; (2）某人不能做某项工作（某事不能由某人做, 无法接受的指派）; (3)某人可以同时被指派多个任务; (4)某事可以由多人共同完成; (5)目标函数是与指派有关的总效用最大或最小的函数. 该类指派问题被称为是非标准指派问题. 由于指派问题也是属于多阶段决策问题, 所以本文主要利用动态规划的基本原理和方法解决一类较一般的非标准指派问题, 即有项工作欲指派个人去做,当时, 要求每项工作只能由一个人去做, 第个人可以同时做项工作（某人可以同时被指派多个任务）, 其中是待求未知数, 满足 (为第个人所需工作数的上下限) 及(即每个工作都有人做), 为已知常数; 当时, 要求每个人只做一项工作,第项工作可以由个人共同去做（某事可以由多人共同完成）, 其中是待求未知数,满足(为第项工作所需人数的上下限)及(即每个人都有工作), 为已知常数; 第个人做第项工作所用的工作时间或工作效益为 . 确定使总耗用时间最少或使总效益最大的指派问题. 记上述问题为. 当且时, 问题便是中的问题. 当且时, 问题便是中的问题. 所以问题是一类更一般的非标准指派问题, 在经营管理实践中更有意义. 本文将应用所总结归纳的动态规划模型对这一类非标准指派问题进行求解, 并用匈牙利法对其进行检验, 说明本文所运用方法的正确性. 2 预备知识 定义2.1 （多阶段决策过程）多阶段决策过程是一类特殊的活动过程, 这个过程可以按时间顺序分解成若干相互联系的阶段, 我们把它称之为“时段”, 在每一个时段上都要作出决策, 全部过程的决策构成了一个决策序列. 多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最优. 由于各阶段决策间有机地联系着, 一个阶段决策的执行将影响到下一阶段的决策, 以至于影响总体效果, 所以决策者在每个阶段决策时不应仅考虑单个阶段最优, 还应考虑对最终目标的影响, 从而作出对全局来讲是最优的决策. 而动态规划就是符合这种要求的一种决策方法. 动态规划方法与“时间”关系很紧密, 随着时间过程的发展而决定各时段的决策, 产生一个决策序列, 这就是“动态”的意思. 然而它也可以处理与时间无关的静态问题, 只要在问题中人为地引进“时段”因素, 将问题看成多阶段的决策过程即可.用动态规划方法解决多阶段决策问题,首先要将实际问题写成动态规划模型, 此时要用到以下概念: 1、阶段; 2、状态; 3、决策; 4、策略; 5、状态转移方程; 6、阶段指标函数; 7、过程指标函数; 8、最优指标函数. 这里用一个最短路的简单例子来说明这些概念.下图是给定是一个线路网状图, 选择从地到地去的最短路线. 如图1所示. 图1定义2.2 （阶段）将所给问题的过程, 按时间或空间特征分解为若干相互联系的阶段, 以便按照次序去求解每阶段的解, 每个阶段就是一个子问题, 常用字母表示阶段变量. 上例中, 从到可以分成到, 到, 到三个阶段. 即定义 2.3 （状态）状态是我们所研究的问题在各个阶段的初始形态或客观条件, 而描述各阶段状态的变量称为状态变量, 常用表示第阶段的状态变量, 状态变量的取值集合称为状态集合, 用表示. 在上例中, .动态规划中的状态应具有如下性质: 当某阶段状态给定以后, 在这阶段以后过程的发展不受这一阶段以前各阶段状态的影响. 也就是说, 当前状态是过去历史的一个完整总结, 过程的过去历史只能通过当前状态去影响它未来的发展, 这称之为无后效性. 如果选择的变量不具备无后效性, 就不能作为状态变量来构造动态规划模型. 当某一阶段的初始状态已选定某个点时, 从这个点以后的路线只与该点有关, 不受以前路线的影响,所以满足状态的无后效性.定义2.4 （决策和策略）当各段的状态取定以后, 就可以作出不同的决策,从而确定下一阶段的状态, 这种决策的变量, 称之为决策变量, 常用表示第阶段当状态为时的决策变量. 在实际问题中, 决策变量的取值往往限制在一定的范围内, 我们称这个范围为允许决策集合, 常用表示第阶段从状态出发的允许决策集合,显然, 在上例中, 从第二阶段的状态出发, 可以选择下一阶段的 即允许决策集合为如果决定选择, 则可表示为.各阶段决策确定以后, 整个问题的决策序列就构成一个策略. 对于每一个实际问题而言, 可供选择的策略也有一定的范围, 称之为允许策略集合, 记作 使整个问题达到最优效果的策略就是最优策略.定义2.5 （状态转移方程）动态规划中一个阶段的状态往往是上一个阶段的状态和决策的结果. 如果给定了第阶段的状态, 本阶段决策为, 则第段的的状态也就完全确定. 它们的关系可表示为,由于它表示了由段到段的状态转移规律,所以称之为状态转移方程. 在上例中,状态转移方程为.定义2.6 （阶段指标函数）假设第阶段的状态为, 当执行了决策时,除带来系统状态的转移之外,还产生第阶段的局部效益,它是所求总效益的一部分, 称之为阶段指标函数, 记作定义2.7 （指标函数）用于衡量所选定策略优劣的数量指标称为指标函数.一个阶段决策过程, 从1到叫作问题的原过程, 对于任意一个给定的 从第阶段到第阶段的过程称为原过程的一个后部子过程. 阶段,状态为采用策略时原过程的指标函数值, 而表示在第阶段,状态为采用策略时后部子过程的指标函数值. 表示从第阶段状态采用最优策略到过程终止时的最优值函数. 与间的关系为,(意为最优).当时, 就是从初始状态到全过程结束的整体最优函数.在所给例子中, 指标函数用来衡量策略优劣的数量指标就是距离. 求解最小距离就是所要解决的问题.综上所述, 我们在运用动态规划解决问题的时候可以采取的方法步骤为将多阶段决策过程划分阶段, 恰当地选取状态变量、决策变量,定义最优指标函数, 从而把问题化成一簇同类型的子问题,然后逐个求解.求解时从最后阶段开始, 逆过程方向行进,逐段递推寻优, 在每一个子问题求解时, 都要使用它前面已求出的子问题的最优结果, 最后一个子问题的最优解, 就是整个问题的最优解.定理2.1 （最优化原理）对于最优策略过程中的任意状态而言, 无论其过去的状态和决策如何, 余下的诸决策必构成一个最优子策略.3 所讨论非标准指派问题的动态规划模型的建立和求解步骤对于问题而言, 由于分配的过程是顺序进行的, 所以它具有可分性,因此可以对其建立动态规划模型.建立动态规划模型如下(1)阶段变量: 表示给个人指派工作的顺序;(2)状态变量: (为整数, 这里以工作为状态)表示第阶段初剩余的工作数, 亦即给第个人指派工作前剩余的工作数. 假定全体工作按编号, 记表示为第阶段初工作数为对应项工作的编号集, 则, . 记表示在第阶段初工作数为时, 项工作所有可能的编号集, 则.(3)决策变量: (为整数)表示指派给第阶段的工作数; 即为指派给第人的工作数. (4)允许决策集合: 表示第阶段决策变量可能的取值; 显然, 根据决策变量的定义易得: .(5)状态转移方程. (1) 因为从第阶段到第阶段至少应有个工作数, 从第阶段到第阶段至少可剩余个工作数, 从第阶段到第阶段至多安排个工作数, 从第阶段到第阶段至多可剩余个工作数, 因此:(6)状态集合(2) (7)允许决策集合 (3)记策略, 则最优指派即是确定最优策略和工作的具体分配方案, 使, 满足且保证使总耗时最少或者总效用最大.(8)指标函数: 用表示从第阶段的决策变量为且工作编号集为时从第阶段到第阶段的最优指标, 即从中指派项工作给第个人时, 从第个人至第个人完成所指派的工作所耗用的时间或所得到的效用.(9)最优值函数表示在第阶段工作编号集为时, 从第阶段到第阶段对应最优策略时的总耗用时间或者总效用. 因此, 即表示个人完成全部指派工作所耗用的最少时间或者最大效用. 故只需求出, 并给出相应的工作分派即可. 由动态规划的最优性原理, 可以建立如下的动态规划方程 , (4)其中,是下列问题的最优值 . (5)记表示分派给第个人的工作编号 由动态规划方程(4), (5)逆推可求得最小耗用时间或者最大工作效用, 再沿计算过程反向查找可得第阶段的最佳状态变量及对应的最佳工作编号, 则即为分派给第个人的最佳工作, 即为第阶段的最优分派工作数.综上分析问题的计算步骤如下、;、写出的所有可能值对每一个给出和对每个由公式(4), (5)求;、若, 转, 否则转;、最小耗用时间或最大工作效用为, 最佳状态变量值为, 第个人分派的最佳工作为, 工作数4 动态规划在解决非标准指派问题中的应用4.1 问题描述某公司拟将四名技术员工分配到甲、乙、丙三个工作点工作, 每个人在各个工作点的效用如表所示, 已知第一个人工作数满足, 问该公司如何分配员工才能使得三个工作点的总效用为最大？表一 工作技术员工甲乙丙00001475296337384101113问题分析这个问题属于问题范畴. 已知条件是必须保证每个人都有工作, 对此需要做出三个相关的决策, 即有多少个技术员工分配到三个工作点中的每一个. 工作的分派过程具有明显的顺序性, 因此可以用已建的动态规划模型求解. 以人员为状态变量, 并对人员进行编号, 记为.题目是使最大化效用的指派问题, 所以在已建模型中, 方程(4)应变为.方程(5)应变为.求解过程该指派问题的效用矩阵为解 (1) , , , ., , .(2), , , . , , , , .(3), , , .由上述过程反查表得时, , ;时, , ;时, , .成效评价由上述分析可以得知, 最优分配方案为: 第个人做甲工作, 第个人做乙工作, 第个人和第个人去做丙工作, 这时的效用为最大.问题检验匈牙利法检验过程当第一个工作点必须由两人来做时（见图2）图2最大效用为: 9+7+7+13=36当第一个工作点由一人来做, 第二个工作点由两人来做时（见图3）图3最大效用为: 9+7+11+8=35当第一个工作点由一人来做, 第三个工作点由两人来做时（见图4）图4最大效用为: 9+7+8+13=37综上所述最大效用为37, 这跟题目所得结果相同, 所以解法正确.4.2 问题描述某有色金属公司欲派出三名专家、将对所属五家冶炼厂（编号为厂、厂、厂、厂、厂）进行技术改造,由于人手不够, 该公司只能根据每位专家对各个冶炼厂进行技术改造的时间来加快整体工作进程. 要求人员分配时第一个人的工作数必须满足, 问怎样安排人员才可以使得整体工作进程加快? 已知各个专家对每个厂技术改造时所用的时间矩阵如下所示问题分析很显然, 该问题属于问题范畴, 因此可以运用已建的动态模型来对该问题进行求解. 这里以工作为状态变量, 按三个专家的分为三个阶段. 用表示第阶段初工作数为时对应项工作的编号集, 表示在第阶段初工作数为时, 项工作所有可能的编号集.题目是使所耗时间最少的指派问题, 所以在已建模型中, 方程(4)应变为.方程(5)变为.求解过程解 (1), , , ., , , , .(2), , , ., , ,.或或或(3), , , .由上述过程反查表得时, ,;时, ,;时, ,.成效评价由上述分析可以知道最优的安排方案为: 把专家指派到厂和厂; 把专家指派到厂; 把专家指派到厂