一类广义指派问题的有效解法  

An Efficient Algorithm for a Class of Generalized Assignment Problem

作　　者：余英姿[1] 张强[1] 

机构地区：[1]北京理工大学管理与经济学院

出　　处：《数学的实践与认识》2008年第4期86-92,共7页Mathematics in Practice and Theory

基　　金：国家自然科学基金(70471063，70171036)

摘　　要：提出一类广义指派问题,这类问题研究的是m个人执行n项任务,每个人执行的任务数、执行每项任务的人数以及总的指派人项数均有限制,要求最优指派.对这类广义指派问题建立了数学模型,并找到一种转换方法,将这类问题转换为平衡指派问题,从而用传统方法,如匈牙利法求解.最后用一个箅例来说明这种转换方法的简便和有效性.A special generalized assignment problem is presented. It considers the situation where m persons are assigned to n tasks, there are limits to the number of tasks each person can perform, the number of persons assigned to each task and the total number of assignments, one wish to find the optimal assignment of maximal benefit. The mathematical model of the problem is presented and a method is given to transform the generalized assignment problem to a balanced assignment problem, so it can be solved by traditional methods, e.g. Hungarian method. An example is provided to illustrate the method.

关 键 词：指派问题 广义 转换 退化 匈牙利法 

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