匈牙利法
匈牙利法的理论基础
(1)若从效率矩阵(cij)的行(或列)的各元素中分别减去该行(或列)的最小元素后得到一个新矩阵(bij),则以(bij)为效率矩阵的指派问题与原问题有相同的最优解。
经过上述变换后，(bij)中的每行和每列都至少含有一个0元素，称位于不同行不同列的0元素为独立的0元素。
(2)若(bij)有n个独立的0元素，由此可得一个解矩阵，
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
为在X中令对应于(bij)的0元素位置的元素为1，其它位置的元素为0，则X为指派问题的最优解。
(3)D.König定理:矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。
根据上面的原理，匈牙利法可分为如下的四个步骤:
1.对效率矩阵(cij)做变换得(bij)，使(bij)中每行每列均有0元素，实现的方法是:
(1)从(cij)的每行元素中减去该行的最小元素;
(2)再从所得矩阵的每列元素中减去该列的最小元素，得(bij).
2.求(bij)的独立0元素。行列相间地对0元素给出两种标记“*”和“?”，它们分别表示该元素“是”或“不是”独立0元素，在所有的0元素全局有标记时，若独立0元素(即标有*的0元素)的个数为n时，已得最优解，否则转第3步，
标记的方法是:搜索含有未被标记的0元素且个数最少的行(或列)，等概率地从中随机选择一个0元素给以标记*，并对该元素所在的行和列中其它未被标记的0元素给以标记?。
显然标记过程可在有限步完成，从经济意义上看，当给位置为(i,j) 的0元素标记*时，就意味着将第j项工作分配给第i个人员，此时完成任务的效率最高，同时对人员i和工作j的指派已经完成，需将对第i行和第j列的未被标 记的0元素标记?,以示以后不再考虑它们的指派，应当说明:在按行(或列)进行标记时，若有多个未被标记的0元素时，上述方法只保证这种指派的局部最优 性，在全局上是否最优依赖于独立0元素的个数是否等于n .
3.确定矩阵(bij)中独立0元素的最多个数m,当m
数学
数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划
上体现为矩阵(bij)中的0元素还不足够的多。下一 步的目的是对(bij)再做变换以得到更多的0元素，从经济上讲，就是如何选择一些工作由效率次高的人员去完成。
4.对(bij)再做变换以增加独立0元素的个数。
方法为:求出所有已标记“?”的行中且未被删除部分包含元素的最小值，然后，所有已标记的行中的每一个元素(含已删除部分)加上这一最小值，而它删除的列中的每一个元素减去该值，得到一个新矩阵，仍记为(bij),去掉所有的标记，转第2步。
在人员数和任务n不是很大时，匈牙利法是求解指派问题的有效方法，且易于编制成软件，。
在实际问题中还可能遇到极大型的指派问题，我们可以将之转化为极小型问题，然后应用匈牙利法求解，具体地，
令
C’ij=M-Cij， i，j=1,2,3,„,n
其中M为一个足够大的正数以保证c’ij非负，例如可取M 为矩阵C中的最大元素，这样可生成一个以(c’ij)为矩阵的极小型指派问题，由于，
nM为固定的常数，两个指派问题有最同的最优解。
在实际的任务分配中，还可能出现人员(或设备)数与任务数不相等的情况，而且要求每个人员只先 完成一件任务(在人员数少于任务数时)，或者有些人员可暂不安排任务(在人员数多余任务数时)，可称这样的问题为不平衡的指派问题，此时，可通过虚拟人员 或虚拟任务使之转化为一般(平衡)的指派问题，即在原矩阵中增加一些行或者列，使之成为方阵，在极小型问题中所增加的元素应充分的大，如为原矩阵中最大的元素的值，而在极大型问题中增加的元素应足够的小。如可取零值。
浙公网安备 33021202002483