资源描述：
《指派问题的解法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、指派问题的解法总结问题引入：在工作的时候，常常需要对一些人进行工作安排，由于某些条件的限制，每个人只能进行一种工作，怎么安排才能使得总工作时间最小。我们把这一类问题称为指派问题。在这里，我只对人和工作刚好一对一的指派问题的解法进行总结，而对于不是一对一的，则可以通过文献1中的一些方法进行变换。目前问题解法的总结。1:最广泛应用的解法:匈牙利算法。算法简介：库恩(fw.W.Kuhn)于1955年提出了指派问题的解法•他弓I用了匈牙利数学家康尼格一个关于矩阵中0元素的定理：系数矩阵中独立0元素的最多个数等于覆盖所有0元素的最
2、少直线数。这个解法称为匈牙利解法。匈牙利算法虽是运用最广泛的算法，但其操作过程却过于复杂。在划0的时候也不方便记忆，对于初学者来说掌握不便。于是国内很多学者对指派问题给出了几个较简单,方便易记的算法。2:指派问题新解;去目标值子矩阵法。算法描述：任取变量矩阵x某一行中的最小元素，为该行元素目标值的最优解(但不一定是系统目标函数的最优解)，应该是系统目标函数满意解中的一个元素，记作a11划去a11所在的行和列，取剩下的子矩阵中某一行的最小元素，记作a22o依次类推，直到最后一个元素.这些元素相加得系统目标函数的一个满意解，
3、此为一次运算•第二次运算取变量矩阵X中含a以外的任一行，做与上面相同运算，又可以得到系统的第二个满意解•相同地,对于n行做n次运算，共得到系统的n个满意解,系统的最优解即应该是这n个满意解当中的最小值•若第i的最小元素在前面以被取用过，则在进行第i的运算时，不选取该元素，取该行中未被选用过的元素中最小的一个进行运算。算j去分析：相对于匈牙利算法,此算法简单，方便操作。但不能给出所有最优解,得出的最优解唯一,若要给出全部最优解，则算法的次数将大大增加。当矩阵维数较大的时候,可以对矩阵进行划分,以更快计算。算法举例:对于变量
4、矩阵X；T7_211821232217162123151926191815>191916-23.--[21>Xl「231721221623181917=15+18+16+21=70,即系统目标函数的一个满意解为Xi=70（X的下标即为第儿次运算步骤，下同）.同理（前面用过的最小元索按说明中第二条不再重复选取）-28.23T9.2618212厂24：「18212322181919161716171619212317J212319•'151926_19厂】824-17_三L18]=>X2=19+16十17+18=70,182
5、1232217162123T51926191921122182123221716212322」r1519261924181919.18191919191821192322——2123[18j^>X3=19+19+22+18=72,23j5192618231724「1819=23+24+19十17=83.3:递归思想在指派问题中的运用算法描述：对目标函数的解，等于min{a1+A1,a2+A2,a3+A3,..…an+An};其中a为第一行中的第i个元素，Ai为除去第i个元素所在行和列的子矩阵。而求min(a1+A1)就相
6、当于对A1求min,这就又回到了指派问题的求解，只是降了一阶；依次递归，直到只剩下2*2的矩阵，这时候就可以取对角线最小的值,依次往回带。就可以得到最优解。算法分析:算法思路简单明了，但由于算法步骤繁琐，并不适合于手动计算，算法时间复杂度高，但较适合于电脑编程。能给岀所有的最优解。4:指派问题的树算法算法描述：首先给岀一种可行的解，得出其目标函数值，然后在对所有的可行解进行画树，若未画完的分支比第一次给出的目标函数值大，则已经不必再画下去，依次画树,直到所有的可能都画玩,此时记录的目标函数值即为最优解,所有最优解都以画在
7、树里。算法分析同递归分析一样，思路简单，但操作都相对复杂繁琐,并不适合手动解算。较适合编程运算。算法举例例设4项任务4个人的指派问题的效益矩阵如下；2151341104H159141613L78119.求嚴优招派方案.解甘先由行列伏格尔思憑给出初始指派方案:21513E1001415回14161378回9根据初始方案価出初始树枝(见图3几其屮山==•乩=28=24心=20心=】6心=7・S_=28.II算；t他分枝山简化折派树(见图4〉町得j・28・J5优指派方案为：第1个人去完成第4项任务•第2个人去完成第2项任务，第
8、3个人去完成第1项任务•第4个人去完成第3项任务•BB3初始樹枝总结以上的4中指派问题的计算都是对于人数和工作相等的，对于不平衡的算法，也可以化做平衡的来计算，也有一些专门计算不平衡的计算方法，在此不——例举。以上算法中，前2种较时候进行手动计算，算法简单,易掌握。后2种算法，较适合编程计算。参考文献1:《运筹学》，
