最短时限缺省指派问题的一种解法  

The Absent Assignment Problem to the Shortest Time Limit and its Algorithm

作　　者：李珍萍[1] 王亮 

机构地区：[1]潍坊医学院数学教研室,山东潍坊261042 [2]昌潍师专数学系,山东潍坊261043

出　　处：《运筹与管理》2000年第2期55-61,共7页Operations Research and Management Science

摘　　要：将周良泽在 1998年提出的最短时限缺省指派问题转化成赋权二分图的最小权 K-匹配问题。研究了其解的最优性充分及必要条件 ,并给出了适合在图上求解的生长树法及适合在表上直接求解的标号法 ,最后给出一个实例。该解法是一种较简便的算法。The absent assignment problem to the shortest time limit which is given by Zhou Lingze in 1998 has been transformed to the minimum weighted k matching problem in bipartite graph with weight. The paper studies the necessary and sufficient condition of its optimal solution. The yielding tree algorithm which is fit for graph and the labeling algorithm which is fit for table are given. An example is given at last. The algorithm in this paper proves to be a good algorithm.

关 键 词：缺省指派 最短时限 K-匹配 生长树 标号法 

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