《指派问题的匈牙利解法》由会员分享，可在线阅读，更多相关《指派问题的匈牙利解法（3页珍藏版）》请在金锄头文库上搜索。
1、指派问题的匈牙利解法1、把各行元素分别减去本行元素的最小值； 然后在此基础上再把每列元素减去本列中的最小值。15 120 3 0 11 84 8 7100 1 7 7 37 9 17 146 9 12 870 2 3 21100 0 5 0 46 7 14 66 9 1210 60 2 3 4 0此时每行及每列中肯定都有0 元素了。2、 确定独立零元素，并作标记。（1） 、首先逐行判断是否有含有独立 0 元素的行，如果有，则按行继续处理；如没有，则要逐列判断是否有含有独立 0 元素的列，若有，则按列继续处理。若既没有含有独立0 元素的行，也没有含有独立 0 元素的列，则仍然按行继续处理。（2）
2、在按行处理时，若某行有 独立 0 元素，把该0 元素标记为 a，把该0 所在的列中的其余 0 元素标记为 b；否则，暂时越过本行，处理后面的行。把所有含有独立 0 元素的行处理完毕后， 再回来处理含有 2 个以及 2 个以上的 0 元素的行： 任选一个 0 做 a 标记，再把该 0 所在行中的其余0 元素及所在列中的其余0 元素都标记为 b。（3）在按列处理时，若某列有 独立 0 元素，把该0 元素标记为 a，把该0 所在的行中的其余 0 元素标记为 b；否则，暂时越过本列，处理后面的列。把所有含有独立 0 元素的列处理完毕后， 再回来处理含有 2 个以及 2 个以上的 0 元素的列： 任选一
3、个 0 做 a 标记，再把该 0 所在列中的其余0 元素及所在行中的其余0 元素都标记为 b。（4） 、重复上述过程，即得到独立零元素（标记a 的“0” ）8 0b3 0a1130a17702 321b0b0a50b4 0a0b2 343、 若独立零元素等于矩阵阶数，则已经得到最优解，若小于矩阵阶数，则继续以下步骤：（1） 、对没有标记 a 的行作标记 c（2） 、在已作标记 c 的行中，对标记 b 所在列作标记 c（3） 、在已作标记 c 的列中，对标记 a 所在的行作标记 c（4） 、对没有标记 c 的行划线，对有标记 c 的列划线 030118 0177302321 00504 0234
4、0/4、 在未被直线覆盖的所有元素中找出一个最小元素（Xmin） ，未被直线覆盖的行（或列）中所有元素都减去这个数。 （注：若未被直线覆盖部分是行数列数，则是按行减，反之则按列） 。/ 011 003011806621210050423405、 这样必然出现负元素， 所以对负元素所在列 （或行） 中各元素都加上这一最小元素 （Xmin）以消除负数。这样，再返回步骤2，确定独立零元素个数。重复上述操作，直到找出最优解。03 0 1180/0 66201 210/10/5 0412 3 40特殊问题：1、 若人数和工作数不等，则用“0”来补全空位2、 若一个人可作几件事，则可化为相同的“几个人”来接受指派，费用系数相同。3、
