匈牙利解

匈牙利解法的適用條件

匈牙利解法的適用於基於任務分配問題的標準型，標準型要滿足下述三個條件：

（1）目標要求為min；

（2）效率矩陣

為n階方陣；

（3）陣中所有元素

，且為常數。

指派問題的匈牙利法求解步驟：

（1）變換指派問題的係數矩陣(

) 為(

) ，使在(

) 的各行各列中都出現0元素，即從(

)的每行元素都減去該行的最小元素；再從所得新係數矩陣的每列元素中減去該列的最小元素。

（1）進行試指派，以尋求最優解。在(

)中找儘可能多的獨立0元素，若能找出n 個獨立0元素，就以這n 個獨立0元素對應解矩陣(

)中的元素為1，其餘為0，這就得到最優解。

找獨立0元素，常用的步驟為：

1) 從只有一個0元素的行開始，給該行中的0元素加圈，記作◎ 。然後划去◎ 所在列的其它0元素，記作Ø ；這表示該列所代表的任務已指派完，不必再考慮別人了。依次進行到最後一行。

2) 從只有一個0元素的列開始（畫Ø的不計在內），給該列中的0元素加圈，記作◎；然後划去◎ 所在行的0元素，記作Ø ，表示此人已有任務，不再為其指派其他任務了。依次進行到最後一列。

3) 若仍有沒有劃圈的0元素，且同行(列) 的0元素至少有兩個，比較這行各0元素所在列中0元素的數目，選擇0元素少這個0元素加圈(表示選擇性多的要“禮讓”選擇性少的) 。然後劃掉同行同列的其它0元素。可反覆進行，直到所有0元素都已圈出和劃掉為止。

4) 若◎ 元素的數目m 等於矩陣的階數n （即：m =n ），那么這指派問題的最優解已得到。若m < n，則轉入下一步。

（3）用最少的直線通過所有0元素。其方法：

1) 對沒有◎的行打“√”；

2) 對已打“√” 的行中所有含Ø元素的列打“√” ；

3) 再對打有“√”的列中含◎ 元素的行打“√” ；

4) 重複1)、2)直到得不出新的打√號的行、列為止；

5) 對沒有打√號的行畫橫線，有打√號的列畫縱線，這就得到覆蓋所有0元素的最少直線數 l。

註：l 應等於m ，若不相等，說明試指派過程有誤，回到第2步，另行試指派；若l =m < n ，表示還不能確定最優指派方案，須再變換當前的係數矩陣，以找到n 個獨立的0元素，為此轉第（4）步。

（4）變換矩陣(

) 以增加0元素。在沒有被直線通過的所有元素中找出最小值，沒有被直線通過的所有元素減去這個最小元素；直線交點處的元素加上這個最小值。新係數矩陣的最優解和原問題仍相同。轉回第（2）步。