缺省指派问题及其求解算法  

THE ABSENT ASSIGNMENT PROBLEM AND TWO ALGORITHMS FOR FINDING ITS SOLUTIONS

作　　者：谢凡荣[1] 朱家翔[1] 

机构地区：[1]南昌大学数学系,江西南昌330047

出　　处：《南昌大学学报（理科版）》2005年第2期126-132,共7页Journal of Nanchang University(Natural Science)

摘　　要：在研究周良泽于1998年首先提出的最短时限最少耗费缺省指派问题基础上,从对称的角度给出了缺省指派问题的两种不同提法:拟从m个人中派出β个人去干n件事中的β件事(β≤min{m,n},每件事由一个人完成)。已知第i人做第j事的时间为tij,第i人做第j事的耗费为pij,i=1,2,…,m;j=1,2,…,n。问派出哪β个人去完成哪β件事,才能使得:(1)在最短时限内完成n件事中的β件事,并且在满足最短时限前提条件下总耗费最少?(2)以最少总耗费完成n件事中的β件事,并且在满足总耗费最少前提条件下完成时限最短?给出了求解该问题的数值算法,证明了算法的理论依据,并举例说明算法的应用。Based on deep research of the absent assignment problem of least cost subjecting to the shortest time limit presented firstly in document [1] in 1998 , in view of symmetry this paper has given the absent assignment problem two different ways to ask the question as follows . It is intended to assign β persons among m people to fulfil β ones among n tasks . Here β is not greater than m and n, and every task must be fulfiled by only one person . It is known that for the i-th person to fulfil the j-th task takes t_(ij) units time and p_(ij) units cost , where i belongs to set of natural number between 1 and m , and j belongs to set of natural number between 1 and n . There are two questions . The first is , which β persons are assigned to fulfil which β tasks so that β tasks are fulfiled in shortest time limit , and it costs least subjecting to the shortest time limit . The second is , which β persons are assigned to fulfil which β tasks so that β tasks are fulfiled at least cost ,and the time limit is shortest subjecting to the least cost . Two numerical algorithms are presented for solving the problem, the theory of which is proved strictly, and examples are given to demonstrate the application of the algorithms .

关 键 词：指派问题 缺省指派问题 最短时限最少耗费缺省指派问题 最少耗费最短时限缺省指派问题 正则型运输网络 

分 类 号：O157.7[理学—数学]