1、匈牙利算法示例信管网 ()：最专业信息系统项目管理师网站（二）、解题步骤：指派问题是 0-1 规划的特例，也是运输问题的特例，当然可用整数规划， 0-1 规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法，这就是匈牙利法，即 系数矩阵中独立 0 元素的最多个数等于能覆盖所有 0 元素的最少直线数。 第一步：变换指派问题的系数矩阵（ cij）为 (bij)，使在 (bij)的各行各列中都出现 0元素，即(1) 从（ cij）的每行元素都减去该行的最小元素；(2) 再从所得新系数矩阵的每列元素中减去该列的最小元素。第二步：进行试指派，以寻求
2、最优解。在 (bij)中找尽可能多的独立 0元素，若能找出 n个独立 0元素，就以这 n个独立 0元素对应解矩阵 (xij)中的元素为 1，其余为 0，这就得到最优解。找独立 0元素，常用的步骤为：(1)从只有一个 0元素的行 (列 )开始，给这个 0元素加圈，记作 。然后划去 所在列 (行 )的其它 0元素，记作 ；这表示这列所代表的任务已指派完，不必再考虑别人了。(2)给只有一个 0元素的列 (行 )中的 0元素加圈，记作 ；然后划去 所在行的 0元素，记作 (3)反复进行 (1)， (2)两步，直到尽可能多的 0元素都被圈出和划掉为止。(4)若仍有没有划圈的 0元素，且同行 (列 )的
3、0元素至少有两个，则从剩有 0元素最少的行 (列 )开始，比较这行各 0元素所在列中 0元素的数目，选择 0元素少的那列的这个 0元素加圈 (表示选择性多的要 “礼让 ”选择性少的)。然后划掉同行同列的其它 0元素。可反复进行，直到所有 0元素都已圈出和划掉为止。（ 5）若 元素的数目 m 等于矩阵的阶数 n，那么这指派问题的最优解已得到。若 m n, 则转入下一步。第三步：作最少的直线覆盖所有 0元素。(1)对没有 的行打 号；(2)对已打 号的行中所有含 元素的列打 号；(3)再对打有 号的列中含 元素的行打 号； (4)重复 (2)， (3)直到得不出新的打 号的行、列为止；(5)对没有
4、打 号的行画横线，有打 号的列画纵线，这就得到覆盖所有 0元素的最少直线数 l 。 l 应等于 m，若不相等，说明试指派过程有误，回到第二步 (4)，另行试指派；若 l m n，须再变换当前的系数矩阵，以找到 n个独立的 0元素，为此转第四步。第四步：变换矩阵 (bij)以增加 0元素。在没有被直线覆盖的所有元素中找出最小元素，然后打 各行都减去这最小元素；打 各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第二步。 例一：任务人员 A B C D甲 2 15 13 4乙 10 4 14 15丙 9 14 16 13丁 7 8 11 924974 2 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作 A、 B、 C、 D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？任务人员 A B C D甲 6 7 11 2乙 4 5 9 8丙 3 1 10 4丁 5 9 8 2例二、
