基于K-means聚类的非标准指派问题的算法研究  

Research on Algorithm for Non-standard Assignment Problem Based on K-means Clustering

作　　者：张影 刘骏豪 乔田田 ZHANG Ying;LIU Junhao;QIAO Tiantian(College of Pipeline and Civil Engineering,China University of Petroleum(Huadong),Qingdao,Shandong 266000,China;Annie Wright Schools,Tacoma 98403,USA;College of Science,China University of Petroleum(Huadong),Qingdao,Shandong 266000,China)

机构地区：[1]中国石油大学(华东)储运与建筑工程学院,山东青岛266000 [2]Annie Wright Schools,USA Tacoma 98403 [3]中国石油大学(华东)理学院,山东青岛266000

出　　处：《数学建模及其应用》2024年第4期19-23,共5页Mathematical Modeling and Its Applications

摘　　要：线性指派问题是优化中常见的一类问题,具有广泛的应用领域.非标准指派问题由于指派的目标数量不同,不适用于通过代价矩阵直接确立顺序.本文利用统计学中的K-means聚类算法将目标数量按照规定数目聚类后,再使用匈牙利算法进行标准指派问题的分配,并将文中算法方案应用于数学建模中人员指派和运输指派问题,最后通过实验数据结果表明该方案行之有效、合理稳定.Linear assignment problem is a typical problem in optimization,which has a wide range of applications.Because of the different number of objects assigned,the non-standard assignment problem is not suitable for directly establishing the order through the cost matrix.In this paper,the K-means clustering algorithm in statistics is used to cluster the number of targets according to the specified number,and then the Hungarian algorithm is used to assign the standard assignment problem,and the algorithm scheme is applied to the problem of personnel assignment and transportation assignment in mathematical modeling.Finally,the experimental data results show that the scheme is effective,reasonable and stable.

关 键 词：指派问题 K-MEANS聚类 匈牙利算法 

分 类 号：O29[理学—应用数学]