(指派问题)假设需要 N 个人完成 N 项工作, 每人只能完成其中的一项, 第 i 个人完成第 j 项工作的效率(所需时间或费用)不同,效率用 Cij 表示。问题是如何进行指派,完成工作的总效率最高(所需的时间才会最少,或总费用最低)。这就是指派问题,类似的如有 N 项加工任务,如何去分配 N 台机床分别完成等。
指派问题的解法是匈牙利算法。匈牙利数学家狄·康
<尚大教育,教育至上,人才为大:sdedu.cc>
(指派问题)假设需要 N 个人完成 N 项工作, 每人只能完成其中的一项, 第 i 个人完成第 j 项工作的效率(所需时间或费用)不同,效率用 Cij 表示。问题是如何进行指派,完成工作的总效率最高(所需的时间才会最少,或总费用最低)。这就是指派问题,类似的如有 N 项加工任务,如何去分配 N 台机床分别完成等。
指派问题的解法是匈牙利算法。匈牙利数学家狄·康尼格利用指派问题的特点,给出了一种更为简便的方法,俗称匈牙利法。对指派矩阵(效率矩阵)的任意行(列)减去它的最小元素后,所构成的指派问题最优解与原指派问题相同。因为指派矩阵的这种变化并不影响数学模型的约束方程组,而只是使目标函数值减少了某些数值。
<尚大教育,教育至上,人才为大:sdedu.cc>