单位文秘网 2021-07-20 08:17:30 点击: 次
摘要:指派问题是生产管理者在日常工作中经常遇到的一类问题,目前解决指派问题最有效的方法是“匈牙利法”。因“匈牙利法”本身存在的瓶颈问题,使得广大管理者虽然具有了相应的理论知识,却很难将其应用到实践中去,为了提高广大管理者的工作效率,文章介绍了一种求解指派问题的简单方法:即利用Excel提供的“规划求解”模块来快速方便地求解。
关键词:指派问题;规划求解;匈牙利法
一、引言
指派问题是管理者工作中经常会遇到的一类问题,如假设有n项任务,要分配给n个人去完成,由于任务的不同及每个人的专长不同导致完成任务的工作效率、费用等不同。如何将这n项任务合理安排给这n个人,使得总工作效率最高、费用最少就具有很重要的现实意义。这类问题统称为指派问题。指派问题中的任务可以是任何类型的活动,人可以是任何类型的资源,费用可是任何类型的效能。指派问题的应用领域非常广泛,如企事业单位、交通运输行业、学校及竞技体育项目等都会涉及到指派问题。显然如能科学合理地解决指派问题,将能够充分发挥资源优化配置的功能,从而带来极大的经济效益和社会效益。
到目前为止“匈牙利法”是被人们认为求解指派问题最为有效的方法,但“匈牙利法”在应用上存在着一定的问题:计算过程较繁琐。一般情况下,匈牙利法的计算过程要经过多步,如果中间稍有差错,就有可能导致最终结果的失灵。因而尽管其算法简单易懂,但是繁琐的计算量使得许多管理者望而却步,因而限制了其在实际中的应用。尽管现在也有一些专业软件如Matlab、Lingo等能够实现指派问题的求解,但由于这些软件的专业性太强,很难在管理者中得到普及,同样限制了其在实际中的应用。本文将介绍一种更为简便的方法来求解指派问题,使得广大管理者不需要懂匈牙利法也不需要进行繁琐的手工计算就能轻松求解,那就是利用Excel提供的“规划求解”模块来完成。
二、Excel的“规划求解”模块
Excel“规划求解”模块是在Excel2003以后版本中自身封装好的一个独立功能模块,用于求解线性规划问题。指派问题是整数规划问题的特例,同时又是0-1规划和运输问题的特例,当然也就属于线性规划问题,因而能够利用此模块进行求解。这个模块在Excel初始安装时并没有加载,使用时要先将其加载。Excel2007版中的加载是在“Excel选项”对话框中完成的,具体操作步骤:在“Excel选项”对话框中选择对话框左侧列表框中的“加载项”,在“管理”下拉列表框中选择“Excel加载项”,然后单击“转到(G)…”按钮,在弹出的“加载宏”对话框中选中“规划求解加载项”,单击“确定”。加载后的规划求解模块出现在“数据”选项卡中的“分析”组中。
三、标准指派问题的求解
标准指派问题具有以下特点:一是任务数与人数相同,即效益矩阵是一个方阵。二是每个任务只能由一个人来完成。三是每个人只能承担一项任务。四是要求指派方案的总成本最小,即求目标函数的最小值。
假设现有4项任务,要分配给4个人去完成,每个人完成各项任务的成本如表1所示。
具体求解过程:
(一)建模
首先确定指派问题中的已知条件(即效益矩阵)、目标单元格、可变单元格和约束条件在表格中的大致位置,然后根据实际问题在Excel中建模。建模时要合理安排这些单元格的结构,这关系到以后用起来是否方便。按照标准指派问题的特点,在此我们采用了将决策变量设计成矩阵的形式,当然也可设计成按行或按列排列的形式,但那样看起来不够直观,用起来不太方便,所以我们采用矩阵的形式。
(二)输入约束条件和目标函数
在标准指派问题中一个人只能完成一项任务,一项任务只能由一个人来完成,这些约束条件可利用Excel的公式功能简单地实现。在指派方案的右侧和下侧分别输入这些约束条件,目标函数可利用系统提供的Sumproduct函数来完成。输入完成后的结果如图1所示。
(三)设置求解参数进行求解
单击“数据”选项卡中的“规划求解”命令,在弹出的“规划求解参数”对话框中进行相应的设置,对于此实例设置完成后的结果如图2所示。
单击“选项”按钮,在打开的“规划求解选项”对话框中确保选中“采用线性模型”和“假定非负”两个复选框,然后单击“确定”返回到“规划求解参数”对话框,单击此对话框中的“求解”按钮即可得到指派结果。相应的指派方案是:人员1——任务4、人员2——任务2、人员3——任务1和人员4——任务3,最低成本是36。
四、非标准指派问题的求解
在实际指派工作中,可能会遇到很多特殊的情况。如:
(一)人员3提出不承担任务1的要求
这时只需在标准指派问题的基础上多添加一个约束条件$C$13=0即可轻松求解。新添加的约束条件$C$13=0表示人员3一定不承担任务1。求得的指派方案是:人员1——任务1、人员2——任务2、人员3——任务4和人员4——任务3,最低成本为38。
(二)人员2提出只能承担任务1的要求
这个问题与(1)类似,也是只需在标准指派问题的基础上多添加一个约束条件$C$12=1,此约束条件表示的是人员2一定要承担任务1。求得的指派方案是:人员1——任务4、人员2——任务1、人员3——任务3和人员4——任务2,最低成本是46。
(三)人员4病休,暂时不能承担任何任务
在此种情况下,管理者可根据实际需要来决定是暂时不安排某一任务还是让某一人来承担两项任务。两种情况利用Excel同样能够轻松地解决。
1、暂时不安排某一任务。这时任务数多于人员数,可让人员4仍参与任务的指派,但在效益矩阵中要将人员4完成不同任务的成本都设为0(人员4相当于一虚拟人),在指派方案中忽略掉到人员4的指派即可。参数设置和标准指派问题的参数设置相同。求解结果如图3所示,任务3暂时无人承担。这种方法通过设置虚拟人将非标准指派问题转换成了标准指派问题。
图3
2、让某人承担两项任务。仍通过设置虚拟人的方法让这种非标准指派问题变成标准指派问题。即仍让人员4参与任务的指派(人员4相当于虚拟人),但人员4完成不同任务的成本应是相应任务的三人中的最小值。参数设置和标准指派问题的参数设置仍然相同。求解结果如图4所示。相应的指派方案为:人员1——任务4、人员2——任务2、人员3——任务3和虚拟人—任务1,最低成本为34。虚拟人承担任务1的成本值是4,而4显然是人员1提供的,故最终的指派方案是:人员1——任务4和任务1、人员2——任务2和人员3——任务3。
(四)任务4暂时不安排
这时人员数将多于任务数,将会有一个人没有任务可承担。此时可通过设置虚拟任务的方法将非标准指派问题转换成标准指派问题。即仍让任务4参与安排,但所有人员完成任务4的成本都为0(任务4相当于一虚拟任务),参数设置仍和标准指派问题的参数设置相同,求解结果如图5所示。相应的指派方案为:人员——任务1、人员2——任务2和人员4——任务3。人员3没有任务可承担,最低成本为23。
五、结束语
通过上述例子我们可以看到不论是标准指派问题还是非标准指派问题都可用Excel的“规划求解”模块轻松实现。因Excel是一款很常用的办公软件,其在人群中的普及率显然要远远高于Matlab、Lingo等这些专业软件,而且使用者不需要了解“匈牙利法”,也不需要具备相应的运筹学知识,只需在设置好的模板中输入相应的效益矩阵的值就可轻松求解,这显然能够极大地提高其工作效率和决策水平。
参考文献:
1、郑烨,王明杰,樊娟.基于匈牙利法的企业员工任务分配问题研究[J].统计与决策,2011(329).
2、陈士成.运筹学,数据、模型与决策[M].兰州大学出版社,2009.
3、王桂强.运筹学上机指南与案例导航[M].上海人民出版社,2010.
(作者单位:济南职业学院计算机系)
(责任编辑:单位文秘网) )地址:https://www.kgf8887.com/show-221-67798-1.html
版权声明:
本站由单位文秘网原创策划制作,欢迎订阅或转载,但请注明出处。违者必究。单位文秘网独家运营 版权所有 未经许可不得转载使用