寻找独立0元素的一种新方法
张联朋
陕西工业职业技术学院工商管理系陕西咸阳712000
摘要：本文根据独立0元素在矩阵行和列中具有互斥性这一特点，提出了利用0元素在矩阵中的位置来判断其是否为独立0元素的对角线方法。关键词：指派问题；匈牙利法；独立0元素；方法中图分类号：文献标识码：文章编号
用匈牙利法求解指派问题的过程，实质上就是在矩阵中不断制造并寻找独立0元素的一个过程，因为足够数量的一族独立0元素本身就是指派问题的一个最优解。整个求解过程从本质上看分为两步：第一步：制造独立0元素。方法是以考尼格（Ko
ig）第一定理“若从系数矩阵（Cij）的一行（列）各元素中分别减去该行（列）的最小元素，所得到的新矩阵（Bij）和原矩阵（Cij）具有相同的最优解”为理论基础，通过对原矩阵进行化简，使矩阵中出现独立0元素。第二步：寻找独立0元素。其本质是从矩阵中已有的0元素中将其中的独立0元素标记出来，一般用“”来表示独立0元素，而用“Ф”来表示那些非独立0元素。在用匈牙利法求解过程中，这一步被称之为“试指派”。具体方法是：检查矩阵的行和列，从中找出“0”元素最少的一行（或列），从该行（或列）标记出一个0元素若该行（或列）有多个“0”元素，则任标一个，“”用表示，并划去元素所在行和列上的其他0元素，“Ф”用表示。若最少0元素行（或列）同时有几行（或列），则从0元素所在列（或行）中最少的开始。在剩下的矩阵中重复上述过程，直至所有0元素都已标记出或划掉为止。倘若矩阵中独立0元素数量小于矩阵的阶数，则需继续化简。这种通过“试指派”的方法虽能很快找到独立0元素，但在寻找之前人们对其位置还是缺乏预见性，因为对于一个
阶方阵，这些独立0元素在矩阵中可能的排列方式多达
种，（注：4！＝24，5！＝120，6！＝720）；另外，这样标记出来的“”在矩阵中也显得很乱。为此，笔者根据独立0元素之间在矩阵的行和列中具有互斥性的特点，提出利用0元素在矩阵中的位置来判断其是否独立0元素的一种新方法对角线法。一、对角线法的原理
f因为在平衡的指派问题（任务数＝作业者数）中，一项任务只能由一个作业者来完成，每个作业者也只能承担其中的一项任务，这表现在矩阵中就是“一行只能有一个独立0元素，一列也只能有一个独立0元素”，所以所有的独立0元素必然分布在方阵的不同行、不同列上，利用这一特点，如果我们对矩阵的行（或列r