Page 125 - 数学建模算法与应用

第四章 线性规划理论与应用

第四节 指派问题

一、指派问题的数学模型

例 7 拟分配 n 人去干 n 项工作，每人干且仅干一项工作，若分配第 i 人去干
第 j 项工作，需花费 cij 单位时间，问应如何分配工作才能使工人花费的总时间
最少？ 能够看出，要给出一个指派问题的实例，只需给出矩阵 C = (cij) ，C 被称
为指派 问题的系数矩阵。

引入变量 xij ，若分配 i 干 j 工作，则取 xij = 1，否则取 xij = 0 。上述指派问
题的数学模型为

二、求解指派问题的匈牙利算法

由于指派问题的特殊性，匈牙利数学家 Konig 提出了一种更简单的解决方

案——匈牙利算法。该算法主要基于这样一个事实，即如果系数矩阵 C=（c ij ）
的行（或列）中的每个元素加上或减去相同的数字以获得新的矩阵 B=（b ij ），
那么以 C 或 B 作为系数矩阵的分配问题具有相同的最优分配。
例 求解系数矩阵 C 的指派问题

115