匈牙利算法求解教学任务指派问题

杨帆++李慧++胡又农

摘 要 在实际教学中，任务指派问题是一个综合考虑教师特长、学生满意度、教师教学精力等多因素的决策问题。应用匈牙利算法建立指派模型，求解复杂因素下的教学任务指派问题，定量、精准地将恰当的教学任务分配给适当的教师，以使系统总体满意度最大化。该指派优化模型的建立，使得任务分配更加客观和明确。

关键词 匈牙利算法；教学任务；任务指派问题；MATLAB

中图分类号：G642 文献标识码：B

文章编号：1671-489X（2017）14-0012-03

Hungarian Algorithm for Teaching Task Assignment Problem//YANG Fan， LI Hui， HU Younong

Abstract In a practical teaching， the task assignment problem is a

decision-making problem which considers teachers specialty， stu-dents satisfaction， teachers teaching energy and so on. In this paper，

in order to maximize the overall satisfaction of the system， the assign-

ment model is established by using the Hungarian algorithm to solve the task assignment problems in complex conditions， by assigning appropriate teaching tasks to appropriate teachers quantitatively and

accurately. The assignment optimization model makes task assign-ments more objective and clear.

Key words Hungarian Algorithm； teaching task； task assignment problem； MATLAB

1 前言

随着教学内容的扩展，各类前沿技术在课堂中得到充分体现，教学课程的设置、教学任务的分配等问题也变得更加复杂。传统的教学任务指派，主要是根据任务之间的关系、教师的授课情况和学生的偏好，由专门的教学管理人员制定课程表，费时、费力且效率低，属于典型的经验型管理。随着教学管理信息化含量的日益提升，定性的人工进行教学任务指派的情况已无法适应定量、快速、自动的科学管理要求。因此，有必要引入运筹学的理论和方法解决教学任务指派问题，并以计算机辅助解决实际问题。

本文基于匈牙利算法，建立教学任务指派优化模型，分析如何分配教师承担教学任务以使系统整体满意度最大化，并采用MATLAB编程实现求解。

2 指派问题

指派问题的常用描述是有n个人可承担m项任务，由于每人的专长不同，完成不同任务的效率也不同，如何指派哪个人完成哪项任务，使完成所有任务的总效率最高或所需总时间最少？指派问题是运输问题中的一种特殊情况，“派合适的人去做合适的事”是对该问题的最贴切描述。

指派问题的数学模型通常是：设n个人（或机器）被分配去做m件工作，由于工作性质和各人（或机器）的专长不同，完成不同工作的效益（时间、成本、收益等）将有差别，用系数矩阵C表示，Cij表示第i个人完成第j件工作的效益，Cij≥0（i=1，...，n；j=1，...，m）。当n=m时，为平衡状态下的标准指派问题；当n>m时，人数多于任务数，属于不平衡状态下择优录用问题；当n

使得总效益最高（时间最少、成本最小、收益最大等），即目标函数。当且时，为一对一指派问题；否则为多人协作或兼职问题。

求解指派问题的方法通常有分支定界法、隐枚举法、匈牙利法等[1]。匈牙利算法由匈牙利数学家Edmonds于1965年提出，是基于Hall定理中充分性证明的思想，用增广路径求二分图最大匹配的算法，算法的核心是寻找增广路径，也可用于指派问题的求解[2]。

针对多人执行多项工作的指派问题，张云华采用匈牙利算法的基本思想和步骤进行了研究[3]。目标分配问题作为指派问题的一种类型，谷稳综合匈牙利算法及其进化算法的特点，对机器人足球的目标分配问题进行了研究[4]。为避免匈牙利算法多次试分配导致处理速度慢的不足，周莉等人对寻找独立零的次序进行改进，得到匈牙利算法求解指派问题的一次性分配算法[5]。李延鹏等人提出利用虚拟工作代替并联环境，将具有并联环节的人员指派问题转化为典型的指派问题，提高了匈牙利算法的适用性[6]。谢博耶夫采用反圈法和对称差，对匈牙利算法进行了推广[7]。对于“人少任务多”型指派问题的解决，与“加边补零”法、“加边补最小值”法等传统解法不同，马晓娜通过差额法对匈牙利算法进行了改进[8]。

3 基于匈牙利算法的任务指派优化模型

问题描述 教学课程的指派优化问题，需要综合考虑教师教学特长、学生满意度、课程内容等多因素，追求教学质量、满意度和教师教学精力等多目标的优化决策问题，任何一个参数的改变都可能影响最终的指派结果。该类问题可描述为：

假设有n名不同教研室的教师，N={N1，N2，...，Nn}，所有教师可以讲授课程共m门，M={M1，M2，...，Mm}。已知n名教师对m门课程的擅长程度矩阵G、n名教师的课时上限序列U和学员对教师满意度序列S，如何安排n名教師教授的课程，使得总体教学质量、教师精力和学生满意度最优化？

指派优化模型 由于该问题涉及因素较多，因此，采用解析方法或传统的匈牙利算法难以给出合适结果。总体最优化的前提是教师擅长课程、精力和学生满意度满足基本要求，本文采用比值的方式求解三种因素的综合表现。矩阵G元素值为百分比，Gij值越高，表明第i名教师对第j门课程的擅长程度越好。序列U和S经过归一化处理后，也可表现为百分比形式，Ui值越高，表明第i名教师的教学任务越饱满；Si值越高，表明学生对第i名教师的满意度越高。以Tij表现三种因素综合影响下第i名教师教授第j门课程的情况。Tij值与Gij、Si呈现正相关关系，而与Ui呈现负相关关系，计算得到：

末位淘汰制是当前高校教师竞争较为常用的制度[9]，对所有教师求解Tij，对Tij按值由高到低排序PT，根据T进行课程指派前的初始末位淘汰。因此，模型的目标方程为：

约束条件如下：

1）n为能够完成教学任务的教师数量，m为需要完成的教学课程数量，i表示教师，j表示教学课程；

2）教师擅长教学课程的程度矩阵G，其值由教学专

家、往届学生成绩和教师自身资历确定，其值越高，表明越擅长；

3）教学课时饱满程度序列U，由教师所承担的教学任务、科研任务、外出授课学习和自身情况确定，其值越高，表明教师课程任务越重；

4）学生满意度序列S，由往届学生评价、本届学生评价综合确定，其值越高，表明教师讲授课程的受欢迎程度越高；

5）矩阵为修正后的擅长矩阵，依据G、U和S求解T，采用末位淘汰制修正G后成为。

模型求解

1）构建平衡的矩阵G。求解平衡问题是匈牙利算法的特长，当教师数量和教学课程数量不相等时，需要增添虚拟的教师或课程，重新构建平衡的矩阵G。具体方法如下：

①若n>m，一门教学课程可能由多个教师讲授，属于不平衡状态下择优录用问题，可虚拟n-m门课程，構建新的平衡矩阵G={Gn×m∣Gn×（n-m）}。

②若n

③若n=m，属于平衡状态下的标准指派问题，直接由匈牙利算法求解。

构建结束后，由求解最大值转为求解最小值，将目标函数转为标准的目标函数。即求，令

，则与有相同的最优解。

2）处理擅长矩阵、饱满序列和满意度序列。如果某教师Ni无法讲授某项课程Mj，则将擅长矩阵G对应元素Gij的值设定为0。对满意度序列S进行归一化处理：

对课程饱满程度序列U进行归一化处理：

3）修正擅长矩阵G。根据处理后的擅长矩阵、饱满序列和满意度序列，求解T进行末位淘汰。将所有Tij值按由高到低的顺序进行排序，设定合理的淘汰比例p，对于排名低于p的，取消该教师讲授相应课程的安排，即当PT（Tij）≤p时，Gij=0，修正形成矩阵G′。

4 实例分析

某高校计划开设创客空间，需要开展的教学任务有焊接、车工、钳铣磨工、数控、3D打印、切割。现有8名教师可承担相关课程教学，教师对教学课程的擅长矩阵G见表1。根据教师自身安排、专家组打分和课时等分析，得到教师教学任务的饱满程度序列U，见表2。通过问卷调查、往届课程成绩、学生座谈等形式，得到学生对教师的满意度序列S，见表3。根据学校本学期末位淘汰安排，执行p=15%的末位淘汰率。计算T并进行排序，如表4所示，得到综合排名靠后的教师课程为（A2-车工）、（A2-钳铣磨工）、

（A3-数控）、（A4-车工）、（A6-3D打印）和（A7-焊接），将其执行末位淘汰改进矩阵G′。

随后采用匈牙利算法进行最优化指派，使用MATLAB进行编程求解，得到教师A2和A7不参与该项教学任务，其他的如表5所示。

5 结论

在传统教学任务指派中，需考虑教师擅长度和教学任务饱满程度、学生满意度等诸多问题，采用一般经验进行定性的任务指派费时、费力、效率低。而采用定量分析和计算机辅助解决实际问题，使得结论客观而可靠。本文从实际教学出发，以教学任务指派问题建立模型，应用匈牙利算法实现总满意度最高的求解，使得任务分配更加客观和明确，具备可操作性和可重复性，为教育任务分配提供科学依据。

参考文献

[1]胡运权，郭耀煌.运筹学教程[M].4版.北京：清华大学出版社，2012.

[2]傅家良.运筹学方法与模型[M].上海：复旦大学出版社，2006.

[3]张云华.论匈牙利算法在指派问题管理工作中的应用[J].价值工程，2016（25）：214-215.

[4]谷稳.基于进化匈牙利算法的目标分配问题研究及应用[D].西安：西安电子科技大学，2013.

[5]周莉，张维华，徐射雕.求解指派问题的一次性分配算法[J].计算机工程与应用，2011（18）：135-138，152.

[6]李廷鹏，钱彦岭，李岳.基于改进匈牙利算法的多技能人员调度方法[J].国防科技大学学报，2016（2）：144-149.

[7]谢博耶夫.匈牙利算法及其推广[D].上海：华东师范大学，2016.

[8]马晓娜.“人少任务多”型指派问题的一种新算法[J].重庆工商大学学报：自然科学版，2014（12）：68-71，75.

[9]姚维.如何看待高校实行“末位淘汰制”[J].亚太教育，

2016（22）：201，189.