指派问题数学模型及其应用

当指派问题的目标函数要求总耗费最少时,问题可以归纳为min型的指派问题;当目标函数要求总绩效最高时,可以归纳为max型的指派问题。这两类问题虽然目标函数的形式不同,但是数学模型是一致的。

指派问题的标准形式(以人和事为例)如下:有n个人和n 项任务,已知第i个人做第j 件事的费用(或时间、效率等)为cij,要求确定人和任务之间的一一对应的指派方案,使得完成这n项任务的费用最少(或时间最少、效率最高等)。

一般把目标函数的系数写为矩阵形式,称矩阵

为系数矩阵(Coefficient Matrix),也称效率矩阵或价值矩阵。矩阵的元素cij(i,j=1,2,…,n)表示分配第i个人去完成第j 项任务时的效益。一般地,以0-1变量xij(i,j=1,2,…,n)表示指派第i个人去完成第j 项任务,(www.xing528.com)

由于每人只允许分配一项任务,且每项任务只能由一人来完成,因此其数学模型(目标函数及约束条件)如下所示:

在上述模型中,第一个约束条件式表示每人只允许分配一项任务,第二个约束条件式表示每项任务只能由一人去做。对于问题的每个可行解,可用解矩阵来表示:

当然,作为可行解,矩阵的每列元素中有且只有一个1,每行元素中也有且只有一个1。指派问题的数学模型与运输问题的相似,但与运输问题相比,指派问题具有自己的特点,它实际上是0-1整数规划问题。虽然可以利用运输问题的求解方法来解指派问题,但是由于指派问题出现严重的自然退化,计算效率不高,指派问题有更简便的解法——匈牙利解法。