求解广义指派问题的转换方法(1)

《求解广义指派问题的转换方法(1)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六届中国青年运筹与管理学者大会论文集秦皇岛，2004年7月16-20日，第222—230页求解广义指派问题的转换方法余英姿张强(北京理工大学管理与经济学院，北京10008)摘要对一类广义指派问题建立了数学模型，这类问题研究的是辨个人执行H项任务，每个人执行的任务数、执行每项任务的人数以及总的指派人项数均有限制，要求最优指派。找到一种转换方法，将这类问题转换为平衡指派问题，从而用传统方法。如匈牙利法求解。最后用一个算例来说明这种转换方法的简便和有效性。关键词指派问题广义转换退化匈牙利法中图分类号：02

2、21文献标识码：AI引言指派问题(又称分配问题)在现实生活中有着广泛韵应用背景，传统的平衡指派问题(AssignmemProblem，简记作AP)Ⅲ研究的是人数与事数相等，一人一事且一事一人的情形，但现实生活还存在着许多更为复杂的指派问题，即广义指派问题(GeneralizedAssignmentProblem，简记作GAP)。对于形形色色的广义指派问题，人们提出了各种解法，而将广义指派问题转换为平衡指派问题的转换方法，却一直是人们的研究重点和首先考虑的方法。这是因为由于平衡指派问题结构的特殊性和简单

3、性，已经存在许多针对平衡指派问题的专门算法，如匈牙利法I”、削高排除法【2】、缩阵分析法”1和差额法14】(尽管存在着特例使该方法无效，但在大多数情况下，该方法仍不失为一种简便，有效的好算法)等。因此，如果我们能将广义指派问题——这类非平衡指派问题较容易地转换为平衡指派问题，然后使用上述专门算法来求解转换后的平衡指派问题，这显然是一种非常实用的做法。文献[5]提出了一类广义指派问题，要求是：允许某些人做多件工作或允许某些工作由多人完成，且当人数Ⅲ不等于工作数n时，要求不剩工作和不剩人。文献[5]以m<

4、n的情形为例，分别讨论了以下三种情形下的转换方法：1)n—Ⅲ=1，允许某人做两件工作：2)求解广义指派问题的转换方法m<"，允许某人做n—"十1件工作；3)m

5、完成一项虚任务。在文献[7]中，提出了～类C-A指派问题。它要求从Ⅲ个人中派出}(o

6、次不超过d，闯如何指派可使该队期望的总分最高。这一问题的数学规划模型可表示如下其中maxc=∑∑q·％l—IJ=lH虬t0≤q≤∑％≤《f=1∥2．．，m』寸mO

7、％s彰，21∥2一，月(2)i=1∑∑b≥dJ=l，；lh=0或1Vi，J(3)f～=l，指派人员f去执行任务，；h=o，否则。cg：人员i执行任务，的效率(如时间，投资等)：c：总效率；“人员i最少执行的任务数：口!：人员i最多执行的任务数；豌：执行任务，最少的人数；b：：执行任务，最多的人数；d：总的被指派的人项数。显然，文献[5]、[6]和[7]所提出的问题都可以看作是这类广义指派问题的特例求解广义指派问题的转换方法因此，找出求解这类问题的有效方法，既有实际价值又有理论意义。我们将上述广义指派问

8、题记为GAP*。对于GAP*，文献[8]将其转化为一个能阁对偶运输法求解的容量运输问题。但是，用求解运输问题的方法来求解指派问题通常是不合算的。本文受文献[5]、[6]和[7]的启发，通过对GAP*模型结构的分析和研究，找到了一种转换方法，不但能将GAP*转换为AP，而且统一了文献[5]、[6]和[7]的特殊转换方法。为求解这一类广义指派问题的转换方法的推广带来便利。从算例可以看出，这种转换方法非常简便而有效。2问题的转换2．1目标最小化GAP*的转换将