文档介绍：第5章整数线性规划 第5节指派问题
在生活中经常遇到这样的问题,某单位需完成n项任务,恰好有n个人可承担这些任务。由于每人的专长不同,各人完成任务不同(或所费时间),效率也不同。于是产生应指派哪个人去完成哪项任务,使完成n项任务的总效率最高(或所需总时间最小)。这类问题称为指派问题或分派问题(assignment problem)。
例7 有一份中文说明书,需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人。他们将中文说明书翻译成不同语种的说明书所需时间如表5-7所示。问应指派何人去完成何工作,使所需总时间最少?
表5-7
类似有:有n项加工任务,怎样指派到n台机床上分别完成的问题;有n条航线,怎样指定n艘船去航行问题……。对应每个指派问题,需有类似表5-7那样的数表,称为效率矩阵或系数矩阵,其元素cij>0(i,j=1,2,…,n)表示指派第i人去完成第j项任务时的效率(或时间、成本等)。解题时需引入变量xij;其取值只能是1或0。并令
当问题要求极小化时数学模型是:
①
②
③
④
显然,解矩阵(xij)中各行各列的元素之和都是1。但这不是最优。
约束条件②说明第j项任务只能由1人去完成;约束条件③说明第i人只能完成1项任务。
满足约束条件②~④的可行解xij也可写成表格或矩阵形式,称为解矩阵。
如例7的一个可行解矩
指派问题是0-1规划的特例,也是运输问题的特例;即n=m,aj=bi=1
当然可用整数线性规划,0-1规划或运输问题的解法去求解,这就如同用单纯形法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法。
指派问题的最优解有这样性质,若从系数矩阵(cij)的一行(列)各元素中分别减去该行(列)的最小元素,得到新矩阵(bij),
那么以(bij)为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。
利用这个性质,可使原系数矩阵变换为含有很多0元素的新系数矩阵,而最优解保持不变,在系数矩阵(bij)中,我们关心位于不同行不同列的0元素,以下简称为独立的0元素。
若能在系数矩阵(bij)中找出n个独立的0元素;则令解矩阵(xij)中对应这n个独立的0元素的元素取值为1,其他元素取值为0。将其代入目标函数中得到zb=0,它一定是最小。
这就是以(bij)为系数矩阵的指派问题的最优解。也就得到了原问题的最优解。
以下用例7来说明指派问题的解法。 第一步:使指派问题的系数矩阵经变换,在各行各列中都出现0元素。 (1) 从系数矩阵的每行元素减去该行的最小元素; (2) 再从所得系数矩阵的每列元素中减去该列的最小元素。 若某行(列)已有0元素,那就不必再减了。 例7的计算为
行列都有零元素