MinY???bijxij ?bij?0?
i?1j?1nns.t.?n??xij?1 ?j?1, 2, ?, n??i?1?n??xij?1 ?i?1, 2, ?, n? ?j?1?x?0, 1 ?i, j?1, 2, ?, n??ij??b11 b12 ? b1n???b b ? b?21222n?其中：?bij??? ，称为效率矩阵. 约束条件中的第一个等式表示
? ? ? ?????b b ? b?nn??n1n2第j项任务只能由一个人去完成；第二个等式表示第i个人只能去作一项任务.这种问题的实质就是：找出效率矩阵?bij?中位于不同行、不同列的n个元素，使其和最小. 另一方面，它既可视作0-1规划，也可视作运输问题. 所以解法很多，这里仅根据它的特殊性，介绍一种手工算法——匈牙利法. 至于机器解法可参见第十三章.
二、指派问题的匈牙利算法
匈牙利数学家科尼格（Konig）利用指派问题的特点，给出一种简便、有效，也是十分常用的方法. 基本原理是：如果效率矩阵?bij?中某行各元素，分别减去
??，则两效率矩阵的最优解相同. 对于列也具一个常数K，得到新的效率矩阵?bij有这样的性质. 这个原理不难理解，对任何一项任务来说，n个人完成这项任务的效率表现在效率矩阵中该任务对应的一列上，效率高的人，所用的时间少，效率低的人所用的时间多. 如果对这些时间都加上或减去一个常数K，并不改变n个人完成这项任务的快慢顺序，因此不影响指派方案. 同理对任何一个人来说，他完成各项任务的效率表现在效率矩阵相应的一行上，对这一行所有的时间加上或减去同一个常数K,只会影响完成任务的总时间，不会改变他完成各项任务的快慢顺序，所以也不影响指派方案.
这个原理也可由指派问题的数学模型直接推出，如在例3-4的效率矩阵第2
- 16 -
列每个元素加上常数K，则目标函数变为
y??2x11?(15?K)x12?13x13?4x14?10x21?(4?K)x22?8x23?15x24?9x31?(14?K)x32?16x33?13x34?7x41?(8?K)x42?15x43?9x44容易看出它与原目标函数y相比，多了一项:K(x12?x22?x32?x42),但由约束条件得：x12?x22?x32?x42?1，因此，目标函数只多了一个常数K，约束条件没有变化，所以不会改变最优解，只会使目标函数值增加常数K.
下面就例3-4说明求解最小化指派问题的匈牙利算法的具体步骤： 第一步：修改效率矩阵 在效率矩阵?bij?中，让每行（列）元素减去该行（列）元素的最小值，使每行、每列都至少有一个0元素. 得到矩阵?cij? .
15 13 4 ?-2 11 2 ??2 ?0 13 ?0 13 7 0???????
-4 10 4 8 156 0 4 116 0 0 9?????
? ?bij???????b?c?ijij? 9 ?0 5 7 4??0 5 3 2? 14 16 13?-9 ??????? 7 8 15 9?-7 ?0 ??1 4 0????1 8 2??0 ?
-4 -2
第二步：试求最优指派方案 根据指派问题的实质和求解原理，只要能在修改后的效率矩阵中找到n个不同行、不同列的0元素 ，并令它们所对应的xij?1，其它元素对应的xij?0，这样的指派方案就是最优的. 在矩阵?cij?中，首先找出含0最少的行(列)，并且把其中的一个0括起来，即（0）；然后划掉与（0）同行、同列的0元素，即?.
? 13 7 0?? 13 7 (0)?? 13 7 (0)?? 0? 0? 0?????? 6 0 0 9 6 (0) 0 9 6 0 0 9?????? ?cij????(0) 5 3 2??(0) 5 3 2??(0) 5 3 2?
?????????? 0?1 4 01 4 01 4 0?? ??? ???? ? 0? 0?对于效率矩阵为n阶方阵的最小化指派问题，此时若能得到n个（0）元素，则相应的最优指派方案就确定了. 若所得（0）元素的个数小于n，就要修改效率矩阵，进入下一步骤.
第三步：继续修改效率矩阵 ① 在第二步的最后一个效率矩阵中，过每个（0）元素划一条水平线或竖直线，以覆盖所有0元素（包含（0）、?及0），直
- 17 -
线的个数应与（0）元素个数相同. ② 在直线不穿过（没有覆盖）的所有元素中找出最小元素，记作θ. ③ 没有划水平线的行中各元素减θ，在划竖直线的列中各元素加θ，对所得新的效率矩阵，重新选0元素，回到第二步.
13 7 (0)?-1 ? ? 12 6 (0)?? 0?0 12 6 0?? 0?????? 6 (0) 0 97 0 0 10 7 0 (0) 10???? ?? ??
?(0) 5 3 2?-1 ?0 4 2 ?(0) 4 2 1?1???????? 0??????-1 ? (0) 3 0???? 1 4 0?0 0 3 0?? 0?+1 +1
例3-4的效率矩阵到此已能找到4个不同行、不同列的0元素. 从而相应的最优解为
?0?0?x??ij??1??0000101001??0? ?0?0?将最优解代入目标函数y，可得最优值为：miny?4?8?9?8?29(min)． 这表明，让化验员甲、乙、丙、丁分别担当化验任务D、C、A、B，可使他们总的消耗时间最短，只消耗29min，就能完成四项化验工作.
三、其它类型指派问题的求解
1．最大化指派问题 匈牙利法实质上是一种求最小化指派问题的方法，如果给我们的效率矩阵?bij?中的bij是第i个人去作第j项任务的收益，我们该怎样指派，才能使总收益最大呢？
例3-5 某卫生防疫站准备选拔防疫科、食品科、总务科的三名科长. 几经筛选，仅剩下赵、钱、孙三名候选人. 根据民主评议的统计结果，他们主持各个科的工作能力（以得分多少来衡量）如表3—15所示. 试从工作能力出发，确定各科长的指定方案，使总体效能最大. 表3—15 工作能力表
分析： 用i=1,2,3 分别表示赵、钱、孙三人；用j=1,2,3 分别表示防疫、食品、总务三个科. 则可以设
赵 钱 孙
防疫 35 37 38
食品 30 35 28
总务 27 29 32
工 作 能 力（分）
- 18 -
?1, 表示第i人担任第j科的科长, xij???0, 其他, 于是数学模型为
Max Y???bij xij
i?1j?133?3??xij?1,?i?1?3s.t.??xij?1,?j?1?x?0或 1 ?ij??j?1, 2, 3??i?1, 2, 3? ?i, j?1, 2, 3??353027???其中:?bij???373529?
?382832???实际上，只要找出效率矩阵?bij?中的最大元素b，用b减去矩阵中的每个元素bij，得到的矩阵?cij?我们称为原矩阵对应的缩减矩阵（cij?b?bij）. 易见cij越小表示原效率矩阵中第i个人去作第j项任务的收益越大，反之则收益越小. 因此求?bij?的最大化问题解，等价于求它对应的缩减矩阵?cij?最小化问题的解.
?353027???解 由于?bij???373529?中的最大元素为:b?38,所以它对应的缩减矩
?382832???阵为?cij??b?bij???3811?????139?. 用匈牙利法求?cij?的最优解 ?0106???1?1??3 8 11 ?-3 ?0 5 8 ??0 3 ?(0) 3 ????????-1 1? ? (0) ?cij??? 1 3 9? ?0 2 8? ?0 0 1? ? 0?0 10 7??0 8 0?? 0? 0 10 6?8 (0)????????? ? -2 -7
可见最优解为
?100??010?xij?????，这也是原最大化指派问题的最优解，即派赵、钱、孙分?001???别担任防疫科、食品科和总务科的科长，这样可使总的工作能效达到最大值102分.
2. 效率矩阵不是方阵 在实践中，往往出现人少任务多或人多任务少的情
- 19 -
况. 对效率矩阵来说，表现为矩阵不是方阵. 甚至要求某人不能完成某项任务或某项工作不能由某人去作. 这都需要作适当改进，再应用匈牙利法去解决.
对于效率矩阵不是方阵，可以虚设几行或几列，使其构成方阵，虚设的行（列）的元素要根据目标函数的具体情况确定. 对于后一问题，只要将效率矩阵相应的元素取得充分大（极小问题）或充分小（极大化问题），使得最优指派方案不可能取在该元素上.
例3-6 某研究“SARS”的课题组有三名博士研究员甲、乙、丙，估计他们完成5个子课题A、B、C、D、E的研究任务，能获得利润（单位：万元）分别如表3-16所示，要求每人只能作一个子课题，每项子课题也只能由一个人作，怎样安排工作，可使课题组的总收入最高？ 表3-16 课题研究获利情况 解 3个人要完成5项任务，现虚设2人，构成5人完成5项任务；由于虚设的人是不可能完成任务、获得收益的，因
甲
乙 丙
A 6 8 4
B 5 7 6
C 4 5 7
D 7 4 8
E 6 7 5
而获利为0，这样在效率矩阵中补两行0元素即方阵?bij?，可用匈牙利法求解.
?23?6 5 4 7 6????8 7 5 4 7?01??4 6 7 8 5? b?8 ?cij??b?bij??42?bij??????0 0 0 0 0?88???88?0 0 0 0 0??????412?-1 ?341? 103? ?888?-8 888??-8 10100200??240?002?
?010?010??
?12301??123(0)???01341???(0)13442103? ?4210??cij???????00000?(0)0?0????0?00000??0?(0)0?????0 +1 +1
1?-1 ?1??1?-1 ?03? -1 ?4??0??-8 ?1?0???-8 ?1
?11???(0)0?41??1(0)?10??2(0)0???11??240????(0)0(0)0?2? 或：?41??0?10???1(0)?100?1(0)????20?(0)??240??0?(0)2?
?0?10??(0)10???- 20 -