指派问题的解法.docx

指派问题的解法总结问题引入：在工作的时候，常常需要对一些人进行工作安排，由于某些条件的限制，每个人只能进行一种工作，怎么安排才能使得总工作时间最小。我们把这一类问题称为指派问题。在这里，我只对人和工作刚好一对一的指派问题的解法进行总结，而对于不是一对一的，则可以通过文献1中的一些方法进行变换。目前问题解法的总结。1：最广泛应用的解法：匈牙利算法。算法简介：库恩（fWWKuhn)于1955年提出了指派问题的解法他引用了匈牙利数学家康尼格一个关于矩阵中0元素的定理：系数矩阵中独立0元素的最多个数等于覆盖所有0元素的最少直线数。这个解法称为匈牙利解法。匈牙利算法虽是运用最广泛的算法，但其操作过程却过于复杂。在划0的时候也不方便记忆，对于初学者来说掌握不便。于是国内很多学者对指派问题给出了几个较简单，方便易记的算法。2：指派问题新解法目标值子矩阵法。算法描述：任取变量矩阵X某一行中的最小元素，为该行元素目标值的最优解(但不一定是系统目标函数的最优解)，应该是系统目标函数满意解中的一个元素，记作a11 划去a11 所在的行和列，取剩下的子矩阵中某一行的最小元素，记作a22。依次类推，直到最后一个元素ann 这些元素相加得系统目标函数的一个满意解，此为一次运算第二次运算取变量矩阵X中含a 以外的任一行，做与上面相同运算，又可以得到系统的第二个满意解相同地，对于n行做 n次运算，共得到系统的n个满意解，系统的最优解即应该是这 n个满意解当中的最小值若第i的最小元素在前面以被取用过，则在进行第i的运算时，不选取该元素，取该行中未被选用过的元素中最小的一个进行运算。算法分析：相对于匈牙利算法，此算法简单，方便操作。但不能给出所有最优解，得出的最优解唯一，若要给出全部最优解，则算法的次数将大大增加。当矩阵维数较大的时候，可以对矩阵进行划分，以更快计算。算法举例：对于变量矩阵x；3：递归思想在指派问题中的运用算法描述：对目标函数的解，等于mina1+A1，a2+A2,a3+A3，.an+An；其中ai为第一行中的第i个元素，Ai为除去第i个元素所在行和列的子矩阵。而求min（a1+A1）就相当于对A1求min，这就又回到了指派问题的求解，只是降了一阶；依次递归，直到只剩下2*2的矩阵，这时候就可以取对角线最小的值，依次往回带。就可以得到最优解。算法分析：算法思路简单明了，但由于算法步骤繁琐，并不适合于手动计算，算法时间复杂度高，但较适合于电脑编程。能给出所有的最优解。4：指派问题的树算法算法描述：首先给出一种可行的解，得出其目标函数值，然后在对所有的可行解进行画树，若未画完的分支比第一次给出的目标函数值大，则已经不必再画下去，依次画树，直到所有的可能都画玩，此时记录的目标函数值即为最优解，所有最优解都以画在树里。算法分析 同递归分析一样，思路简单，但操作都相对复杂繁琐，并不适合手动解算。较适合编程运算。算法举例总结以上的4中指派问题的计算都是对于人数和工作相等的，对于不平衡的算法，也可以化做平衡的来计算，也有一些专门计算不平衡的计算方法，在此不一 一例举。以上算法中，前2种较时候进行手动计算，算法简单，易掌握。后2种算法，较适合编程计算。参考文献1：运筹学，本科班，清华大学出版社。2