求解集合覆盖问题的离散动态凸化方法  

A discrete dynamic convexizing method for set covering problem

作　　者：刘秀梅[1] 欧阳菲 LIU Xiu-mei;OUYANG Fei(General Education Center, Quanzhou Institute of Technology, Quanzhou, Fujian 362000, China)

机构地区：[1]泉州理工学院通识教育中心

出　　处：《宁德师范学院学报（自然科学版）》2019年第2期120-123,133,共5页Journal of Ningde Normal University(Natural Science)

基　　金：福建省中青年教师教育科研项目(JAT171213)

摘　　要：集合覆盖问题是一个基本的组合优化问题,它是NP(多项式复杂程度的非确定性)完全问题.通过罚函数把问题转化为一个无约束最优化问题,给出一个辅助函数.它和问题有相同的离散全局极小解,设计一个算法,通过极小化该辅助函数得到问题的一个近似离散全局极小解.数值试验表明,算法对求解集合覆盖问题是有效的.The set covering problem is a fundamental combinatorial problem. This paper converts this problem to an equivalent non-constrained problem through a penalty function. An auxiliary function which has the same discrete global m inimizer as the set covering problem is designed.An algorithm is designed,solving the auxiliary function to find the approximate global minimal solution of the set covering problem. Numerical experiments on a test problem show that the algorithm is efficient.

关 键 词：集合覆盖 离散全局极小解 罚函数 辅助函数 

分 类 号：O224[理学—运筹学与控制论]