分配(指派)问题数学模型

---

有n项工作，分配给n个人去完成，一个人只分配一项工作，一项工作只由一人去做。

已知每个人完成每项工作的效率，要求进行人员的合理分配，使总的效率最大。这类问题称分配问题，或称指派问题。

设C_ij表示第i个人从事第j项工作的效率；X_ij表示分配第i个人从事第j项工作的变量，这里X_ij是一特殊变量，称0－1变量。X_ij只能取0或1两个数值，X_ij=1表示第i个人分配干第j项工作，X_ij=0表示第i个人不担任第j项工作。

那末，分配问题的数学模型为：

上述模型通常用一个矩阵表格表示，这个表格以列表示待分配工作人员，行表示待完成工作项目，行列交叉处数值填入效率值C_1j，故称效率矩阵。

一般地，当表中元素C_ij表示时间、费用(或成本)、距离时，这类分派问题欲得到以极小值为目的的最优方案，称极小化分配问题；当C_ij表示产量、售价、利润、产值、得分等时，是以得到极大值最优分配方案为目的，称极大化分配问题。

当上述表格为方阵，即行数与列数相等时，称人员与任务(或称资源与用途)相等的分配问题；否则，称人员与任务数目不等的分配问题。