利用Excel轻松求解指派问题.docx

利用Excel轻松求解指派问题 摘要：指派问题是生产管理者在日常工作中常常遇到的一类问题，目前解决指派问题最有效的方法是“匈牙利法”。因“匈牙利法”本身存在的瓶颈问题，使得广阔管理者虽然具有了相应的理论学问，却很难将其应用到实践中去，为了提高广阔管理者的工作效率，文章介绍了一种求解指派问题的简洁方法：即利用Excel供应的“规划求解”模块来快速便利地求解。 关键词：指派问题；规划求解；匈牙利法 一、引言 指派问题是管理者工作中常常会遇到的一类问题，如假设有n项任务，要安排给n个人去完成，由于任务的不同及每个人的专长不同导致完成任务的工作效率、费用等不同。如何将这n项任务合理支配给这n个人，使得总工作效率最高、费用最少就具有很重要的现实意义。这类问题统称为指派问题。指派问题中的任务可以是任何类型的活动，人可以是任何类型的资源，费用可是任何类型的效能。指派问题的应用领域特别广泛，如企事业单位、交通运输行业、学校及竞技体育项目等都会涉及到指派问题。明显如能科学合理地解决指派问题，将能够充分发挥资源优化配置的功能，从而带来极大的经济效益和社会效益。 到目前为止“匈牙利法”是被人们认为求解指派问题最为有效的方法，但“匈牙利法”在应用上存在着肯定的问题：计算过程较繁琐。一般状况下，匈牙利法的计算过程要经过多步，假如中间稍有差错，就有可能导致最终结果的失灵。因而尽管其算法简洁易懂，但是繁琐的计算量使得很多管理者望而却步，因而限制了其在实际中的应用。尽管现在也有一些专业软件如Matlab、Lingo等能够实现指派问题的求解，但由于这些软件的专业性太强，很难在管理者中得到普及，同样限制了其在实际中的应用。本文将介绍一种更为简便的方法来求解指派问题，使得广阔管理者不须要懂匈牙利法也不须要进行繁琐的手工计算就能轻松求解，那就是利用Excel供应的“规划求解”模块来完成。 二、Excel的“规划求解”模块 Excel“规划求解”模块是在Excel2003以后版本中自身封装好的一个独立功能模块，用于求解线性规划问题。指派问题是整数规划问题的特例，同时又是01规划和运输问题的特例，当然也就属于线性规划问题，因而能够利用此模块进行求解。这个模块在Excel初始安装时并没有加载，运用时要先将其加载。Excel2022版中的加载是在“Excel选项”对话框中完成的，详细操作步骤：在“Excel选项”对话框中选择对话框左侧列表框中的“加载项”，在“管理”下拉列表框中选择“Excel加载项”，然后单击“转到”按钮，在弹出的“加载宏”对话框中选中“规划求解加载项”，单击“确定”。加载后的规划求解模块出现在“数据”选项卡中的“分析”组中。 三、标准指派问题的求解 标准指派问题具有以下特点：一是任务数与人数相同，即效益矩阵是一个方阵。二是每个任务只能由一个人来完成。三是每个人只能担当一项任务。四是要求指派方案的总成本最小，即求目标函数的最小值。 假设现有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的要求 这个问题与类似，也是只需在标准指派问题的基础上多添加一个约束条件$C$12=1，此约束条件表示的是人员2肯定要担当任务1。求得的指派方案是：人员1任务4、人员2任务1、人员3任务3和人员4任务2，最低成本是46。 人员4病休，短暂不能担当任何任务 在此种状况下，管理者可依据实际须要来确定是短暂担心排某一任务还是让某一人来担当两项任务。两种状况利用Excel同样能够轻松地解决。 1、短暂担心排某一任务。这时任务数多于人员数，可让人员4仍参加任务的指派，但在效益矩阵中要将人员4完成不同任务的成本都设为0，在指派方案中忽视掉到人员4的指派即可。参数设置和标准指派问题的参数设置相同。求解结果如图3所示，任务3短暂无人担当。这种方法通过设置虚拟人将非标准指派问题转换成了标准指派问题。 图3 2、让某人担当两项任务。仍通过设置虚拟人的方法让这种非标准指派问题变成标准指派问题。即仍让人员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，参数设置仍和标准指派问题的参数设置相同，求解结果如图5所示。相应的指派方案为：人员任务1、人员2任务2和人员4任务3。人员3没有任务可担当，最低成本为23。 五、结束语 通过上述例子我们可以看到不论是标准指派问题还是非标准指派问题都可用Excel的“规划求解”模块轻松实现。因Excel是一款很常用的办公软件，其在人群中的普及率明显要远远高于Matlab、Lingo等这些专业软件，而且运用者不须要了解“匈牙利法”，也不须要具备相应的运筹学学问，只需在设置好的模板中输入相应的效益矩阵的值就可轻松求解，这明显能够极大地提高其工作效率和决策水平。 参考文献： 1、郑烨,王明杰,樊娟.基于匈牙利法的企业员工任务安排问题探讨J.统计与决策,2022(329). 2、陈士成.运筹学,数据、模型与决策M.兰州高校出版社,2022. 3、王桂强.运筹学上机指南与案例导航M.上海人民出版社,2022. 第7页 共7页第 7 页 共 7 页第 7 页 共 7 页第 7 页 共 7 页第 7 页 共 7 页第 7 页 共 7 页第 7 页 共 7 页第 7 页 共 7 页第 7 页 共 7 页第 7 页 共 7 页第 7 页 共 7 页