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

匈牙利算法求解教学任务指派问题 思想，用增广路径求二分图最大匹配的算法，算法的核心是找寻增广路径，也可用于指派问题的求解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×mGn×。 若n<m，教学课程数量超过教师数量，属于不平衡状态下一人身兼数职问题，可虚拟m-n名教师，构建新的平衡矩阵G=Gn×mG×m。 若n=m，属于平衡状态下的标准指派问题，干脆由匈牙利算法求解。 构建结束后，由求解最大值转为求解最小值，将目标函数转为标准的目标函数。即求，令 ，则与有相同的最优解。 2）处理擅长矩阵、饱满序列和满足度序列。假如某老师Ni无法讲授某项课程Mj，则将擅长矩阵G对应元素Gij的值设定为0。对满足度序列S进行归一化处理： 对课程饱满程度序列U进行归一化处理： 3）修正擅长矩阵G。依据处理后的擅长矩阵、饱满序列和满足度序列，求解T进行末位淘汰。将全部Tij值按由高到低的依次进行排序，设定合理的淘汰比例p，对于排名低于p的，取消该老师讲授相应课程的支配，即当PTp时，Gij=0，修正形成矩阵G。 4 实例分析 某高校安排开设创客空间，须要开展的教学任务有焊接、车工、钳铣磨工、数控、3D打印、切割。现有8名老师可担当相关课程教学，老师对教学课程的擅长矩阵G见表1。依据老师自身支配、专家组打分和课时等分析，得到老师教学任务的饱满程度序列U，见表2。通过问卷调查、往届课程成果、学生座谈等形式，得到学生对老师的满足度序列S，见表3。依据学校本学期末位淘汰支配，执行p=15%的末位淘汰率。计算T并进行排序，如表4所示，得到综合排名靠后的老师课程为、 、和，将其执行末位淘汰改进矩阵G。 随后采纳匈牙利算法进行最优化指派，运用MATLAB进行编程求解，得到老师A2和A7不参加该项教学任务，其他的如表5所示。 5 结论 在传统教学任务指派中，需考虑老师擅长度和教学任务饱满程度、学生满足度等诸多问题，采纳一般阅历进行定性的任务指派费时、费劲、效率低。而采纳定量分析和计算机协助解决实际问题，使得结论客观而牢靠。本文从实际教学动身，以教学任务指派问题建立模型，应用匈牙利算法实现总满足度最高的求解，使得任务安排更加客观和明确，具备可操作性和可重复性，为教化任务安排供应科学依据。 参考文献 1胡运权，郭耀煌.运筹学教程M.4版.北京：清华高校出版社，2022. 2傅家良.运筹学方法与模型M.上海：复旦高校出版社，2022. 3张云华.论匈牙利算法在指派问题管理工作中的应用J.价值工程，2022：214-215. 4谷稳.基于进化匈牙利算法的目标安排问题探讨及应用D.西安：西安电子科技高校，2022. 5周莉，张维华，徐射雕.求解指派问题的一次性安排算法J.计算机工程与应用，2022：135-138，152. 6李廷鹏，钱彦岭，李岳.基于改进匈牙利算法的多技能人员调度方法J.国防科技高校学报，2022：144-149. 7谢博耶夫.匈牙利算法及其推广D.上海：华东师范高校，2022. 8马晓娜.“人少任务多”型指派问题的一种新算法J.重庆工商高校学报：自然科学版，2022：68-73，75. 9姚维.如何看待高校实行“末位淘汰制”J.亚太教化， 2022：201，189. 第6页 共6页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页第 6 页 共 6 页