指派問題匈牙利解法的注記?

李智明

(新疆大學數學與系統科學學院，新疆烏魯木齊830046)

0 引言

指派問題是一種特殊的整數規劃問題[1,2]，指在滿足特定分配要求的條件下，使分配方案總體效果最佳.如：N項任務分配給N個人完成，并且指定每人只能完成一項任務，每項任務只能交給一個人，應如何分配，使得費用最低[3,4].此類問題為最小化指派問題，匈牙利法是求解這類問題的常用方法之一，通過效率矩陣產生獨立零元素，當獨立零元素的個數等于矩陣階數時，獨立零元素對應的決策變量為1，其他元素對應的變量為0，得到了指派問題的最優解矩陣.下面給出一個實例.

例1[5]設A,B,C,D四個隊員參加4×100米接力賽跑，由于各隊員的心理素質、交接棒技術、起跑以及沖刺速度等原因，所跑不同棒次所用時間不盡相同(見表1).請給出各隊員所跑棒次的最優排序.

表1 隊員接力賽所用時間（單位：s）

原解利用匈牙利法求解，求解過程為效率矩陣

對于最大化問題，一般是先找出效率矩陣中的最大值，分別用這個值減去矩陣中的每一個元素，轉化為最小化問題，再使用匈牙利法求解.觀察例1中的效率矩陣，不難發現此效率矩陣每行有最小值，使得它們存在不同行不同列，稱這些最小值為獨立最小元素.對于這類效率矩陣，或者對于最大化指派問題的效率矩陣存在獨立最大元素，即每行有最大值并且它們存在不同行不同列，能否不通過上述處理方法而直接得到最優解矩陣，這個問題在現有教材及文獻中未見提起或者沒有強調[6].

本文針對這兩種情況，通過證明得到如下結論：將效率矩陣的獨立最小元素或獨立最大元素對應位置的決策變量取值為1，其他位置決策變量取值為0，得到最優解矩陣.尤其對于最大化指派問題的求解，不必再轉化成最小化問題，這樣就大大簡化計算過程，更快找到最優解.

1 最小化問題效率矩陣存在獨立最小元素

求解N個資源、N個活動的指派問題，使總效能最小.設cij>0表示分配資源i到活動j的效率，則決策變量

其中i,j=1,2,...,N.最小化指派問題的數學模型為

其中C=(cij)N×N為效率矩陣，其最優解矩陣用X=(xij)N×N表示.

定理1若式(2)中效率矩陣C=(cij)N×N存在獨立最小元素，則這些元素對應的變量xij=1，其他元素對應的變量xij=0，矩陣X=(xij)N×N就是最小化指派問題的最優解矩陣.

證明因為效率矩陣C=(cij)N×N中每行的最小元素位于不同列，說明這些最小元素位于不同行不同列.根據匈牙利法，從矩陣C的每行元素減去該行的最小元素，就在對應的位置產生了不同行不同列的零元素.因此，在這些位置上令變量xij=1，其他元素對應的變量xij=0，就得到了最小化指派問題的最優解.

定理1說明當效率矩陣C=(cij)N×N中有獨立最小元素時，不需要通過行或列變換產生獨立零元素，只需要將這些最小元素對應的位置令xij=1，其他位置令xij=0，就得到了問題的最優解，省去了中間產生獨立零元素的過程.由此可見，在產生獨立零元素之前，先對效率矩陣進行觀察其是否有“獨立最小元素”，若有，通過定理1直接就可以得到問題的最優解矩陣.若沒有，再由效率矩陣的行及列來產生獨立零元素即可.下面對例1給出新解法.

例1新解由表1可知，每行對應的最小值分別為10,10.01,10.01,10，并且有兩種方式使得這些最小值位于不同行不同列（用括號()表示）：

根據定理1，可得上述兩個最優解.所以該隊接力賽跑可以有兩種最優指派方案：

（1）D→B→C→A；（2）D→C→B→A.所用總時間為10+10.01+10.01+10=40.02.

2 最大化問題效率矩陣存在獨立最大元素

對于最大化指派問題模型的建立，只需要將(2)式中的目標函數改為

式(1),(3),(4)就組成了最大化指派問題的數學模型.

定理2若式(4)中效率矩陣C=(cij)N×N中存在獨立最大元素，則這些元素對應的變量xij=1，其他元素對應的變量xij=0，矩陣X=(xij)N×N就是最大化指派問題的最優解矩陣.

證明若效率矩陣C=(cij)N×N中每行的最大元素位于不同列，不妨設為c1j1,c2j2,...,cNjN，其中j1,j2,...,jN∈{1,2,...,N}且它們均不相等.取

則M一定是效率矩陣C=(cij)N×N的最大值.用最大值M減去矩陣中的每一個元素，可知M?c1j1,M?c2j2,...,M?cNjN必為矩陣C每行中最小元素且這些元素位于不同列，由定理1可知，在這些最小元素對應的位置上，即最大元素的位置上令決策變量xij=1，其他元素對應的變量xij=0，就得到最大化指派問題的最優解矩陣.

對于最大化指派問題的求解，類似與最小化問題，首先觀察效率矩陣是否有“獨立最大元素”，若有，通過定理2直接就可以得到問題的最優解矩陣.若沒有，可用匈牙利法的一般處理方法求解即可.

例2若一頁文檔被切割成4個條狀碎片，序號分別為1,2,3,4，令

其中i,j=1,2,3,4.當i=j時，由于第i個碎片的一邊無法與自身匹配，故xii=0,i=1,2,3,4.設cij(i,j=1,2,3,4)為第i個碎片的左邊與第j個碎片右邊的匹配度且cii=0，其匹配度矩陣為C=(cij)4×4如表2.

表2 碎片之間的匹配度

其中序號為1及2的碎片分別為碎片復原的左邊界與右邊界.易知，碎片匹配模型的目標函數為式(4)，約束條件為式(3)，匹配矩陣（或效率矩陣）C=(cij)4×4由表2決定，這個模型為最大化指派問題.

通過表2觀察可知，匹配矩陣C中有獨立最大元素(用括號()標記的元素)，根據定理2可知此模型的最優解矩陣為

注意，通過表2已知最優解中x21并不表示序號2與1中匹配，只是為了湊成4個“獨立的元素1”，故它的取值用括號()標注.從最優解矩陣中可以看出碎片的匹配順序為：1,3,4,2，并且利用最優解可計算最大總匹配度為

3 結論

對于最小化或最大化指派問題，首先要觀察效率矩陣中是否存在獨立的最小或最大元素.當效率矩陣具有這種特點時，僅需在最小或最大元素對應的位置取決策變量為1，其他位置取值為0，直接得到了指派問題的最優解矩陣.當然，若效率矩陣沒有獨立的最小或最大元素，指派問題仍然利用匈牙利法去尋找效率矩陣的獨立零元素來求最優解矩陣.