求解指派问题的匈牙利算法.doc

3.2求解指派问题的匈牙利算法由于指派问题的特殊性，又存在着由匈牙利数学家D.Konig提出的更为简便的解法—匈牙利算法。算法主要依据以下事实：如果系数矩阵)(ijcC一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵)(ijbB，则以C或B为系数矩阵的指派问题具有相同的最优指派。利用上述性质，可将原系数阵C变换为含零元素较多的新系数阵B，而最优解不变。若能在B中找出n个位于不同行不同列的零元素，令解矩阵中相应位置的元素取值为1，其它元素取值为零，则所得该解是以B为系数阵的指派问题的最优解，从而也是原问题的最优解。由C到B的转换可通过先让矩阵C的每行元素均减去其所在行的最小元素得矩阵D，D的每列元素再减去其所在列的最小元素得以实现。下面通过一例子来说明该算法。例7求解指派问题，其系数矩阵为16221917171822241819211722191516C解将第一行元素减去此行中的最小元素15，同样，第二行元素减去17，第三行元素减去17，最后一行的元素减去16，得06310157124074011B再将第3列元素各减去1，得****20531005711407301B以2B为系数矩阵的指派问题有最优指派43124321由等价性，它也是例7的最优指派。有时问题会稍复杂一些。例8求解系数矩阵C的指派问题61071041066141512141217766698979712C解：先作等价变换如下2636040*08957510*00*0032202*056107104106614151214121776669897971246767容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但5n，最优指派还无法看出。此时等价变换还可进行下去。步骤如下：(1)对未选出0元素的行打；(2)对行中0元素所在列打；(3)对列中选中的0元素所在行打；重复（2）、（3）直到无法再打为止。可以证明，若用直线划没有打的行与打的列，就得到了能够覆盖住矩阵中所有零元素的最少条数的直线集合，找出未覆盖的元素中的最小者，令行元素减去此数，列元素加上此数，则原先选中的0元素不变，而未覆盖元素中至少有一个已转变为0，且新矩阵的指派问题与原问题也等价。上述过程可反复采用，直到能选取出足够的0元素为止。例如，对例5变换后的矩阵再变换，第三行、第五行元素减去2，第一列元素加上2，得04140400811353800003420207现在已可看出，最优指派为5314254321。