欢迎来到天天文库
浏览记录
ID:46444078
大小:238.01 KB
页数:15页
时间:2019-11-23
《指派问题的算法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、指派问题的算法分析与实现摘要在企业、公司的运营与管理中,管理者总是希望把人员最佳分派以发挥其最大工作效率,从而降低成本、提高效益。然而,如果没有科学的方法是很难实现优化管理的,由此我们引入了指派问题。指派问题多是求项目的工时最少,而很多情况下人们并不关心项目总工时的多少,而只关心项目能否在最短的时间内完成,即历时最少的指派问题。这类问题研究的是n个人执行n项任务,执行每项任务的人数以及总的指派人项数均有限制,要求最优指派。在运筹学中求解整数规划的指派问题通常是通过匈牙利算法来求解,但指派问题也可以归结为一个0-1整数规划问题,本文
2、先对指派问题进行陈述,引出对实际问题的求解。在指派问题的背景、描述中充分理解该问题,先运用匈牙利算法实现指派问题,然后再建立一个0-1整数规划模型,并运用matlab和lingo编译程序对问题进行编译,运用软件解决模型问题,最终实现指派问题在实际问题中的运用。通过运用匈牙利算法和0-1整数规划同时对指派问题求解,我们发现用0-1整数规划的方法来求解可以更简单,也更方便程序的阅读和理解。与此同时,我们还对0-1整数规划问题由整数数据深入研究到小数数据。最后通过实例来说明运用matlab,lingo编译程序来解决整数规划问题的简便和有
3、效性。关键词:指派问题;匈牙利算法;0-1整数规划;matlab模型;lingo模型1.问题陈述15指派问题又称分配问题,其用途非常广泛,比如某公司指派n个人去做n件事,各人做不同的事,如何安排人员使得总费用最少?若考虑每个职工对工作效率(如熟练程度等),怎样安排会使总销量达到最大?这些都是一个企业经营管理者必须考虑的问题,所以该问题有重要的应用价值。假设有n件工作分派给n个人来做,每项工作只能由一人来做,每个人只能做一项工作。若给出各人对各项工作所具有的工作效率。问应该如何安排人选,及发挥个人特长又能使总的效率最大。为此用0-1
4、整数规划来实现指派问题即如何安排人选。2.背景在现实生活中,有各种性质的指派问题(AssignmentProblem)。例如,在生产管理中,总希望把人员进行最佳分配,以发挥最大的工作效率;某部门有n项任务要完成,而该部门正好有n个人可以分别去完成其中任何一项,但由于任务性质和个人的专长不同,因此各人完成各项不同任务的效益(所费时间或所花费用)也有差别,如果分配每个人完成一项任务且仅为一项任务,则把每项任务分配给哪个人去完成,使完成所有n项任务的总效益为最高(总时间、总费用为最小或创造的价值最大)?这是典型的分配问题或指派问题。又如
5、有n项加工任务,怎样指定n台机器分别去完成,以使总的加工时间最少或总收入最大;有n条航线,怎样指定n艘船分别航行,使总收入最大,等等,都属于指派问题。3.指派问题的描述3.1指派问题的一般形式指派问题的标准形式(以人和事为例)如下。有n个人和n项任务,已知第i个人做第j件事的费用为,要求确定人和事之间的一一对应的指派方案,使完成这n项任务的费用最少。一般把目标函数的系数写为矩阵形式,称矩阵为系数矩阵(CoefficientMatrix15),也称为效益矩阵或价值矩阵。矩阵的元素(i,j=1,2,…n)表示分配第i个人去完成第j项任
6、务时的效益。一般地,以表示给定的资源分配用于给定活动时的有关效益(时间,费用,价值等),且3.2问题的数学模型一般形式在模型中,约束条件式(2)表示每个人只能做一件事,约束条件式(3)表示每件事只能由一个人去做。对于问题的每个可行解,可用解矩阵来表示:当然,作为可行解,矩阵的每列元素中都有且只有一个1,以满足约束条件式(3)。每行元素中也有且只有一个1,以满足约束条件(2)。指派问题n!个可行解。3.3目标函数极大化的指派问题求解时,我们将构造一个新的矩阵,使,其中是一个足够大的常数。一般取中最大的元素作为,求解,所得的解就是原问
7、题的解。事实上,由15可的此结论。4.指派问题实现4.1匈牙利算法4.1.1匈牙利算法的理论基础定理1如果从分配问题的效率矩阵[]的每一行元素中分别减去(或加上)一个常数,从每一列中分别减去(或加上)一个常数,得到一个新的效率矩阵[],则以[]为效率矩阵的分配问题与以[]为效率矩阵的分配问题具有相同的最优解。定理2若矩阵A的元素可以分为‘0’与‘非0’的两部分,则覆盖‘0’元素最少直线数等于位于不同行不同列的‘0’元素的最大个数。4.1.2匈牙利算法的实现步骤第一步:找出矩阵每行的最小元素,分别从每行中减去这个最小元素;第二步:再
8、找去矩阵每列的最小元素,分别从各列减去这个最小元素;第三步:经过这两步变换后,矩阵的每行每列至少都有了一个零元素,接着根据以下准则进行试指派,找出覆盖上面矩阵中所有零元素至少需要多少条直线;(1)从第一行开始,若该行只有一个零元素打上()号。对打(
此文档下载收益归作者所有