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

李智明

(新疆大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，新疆烏魯木齊830046)

0 引言

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

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

表1 隊(duì)員接力賽所用時(shí)間（單位：s）

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

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

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

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

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

其中i,j=1,2,...,N.最小化指派問題的數(shù)學(xué)模型為

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

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

證明因?yàn)樾示仃嘋=(cij)N×N中每行的最小元素位于不同列，說明這些最小元素位于不同行不同列.根據(jù)匈牙利法，從矩陣C的每行元素減去該行的最小元素，就在對(duì)應(yīng)的位置產(chǎn)生了不同行不同列的零元素.因此，在這些位置上令變量xij=1，其他元素對(duì)應(yīng)的變量xij=0，就得到了最小化指派問題的最優(yōu)解.

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

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

根據(jù)定理1，可得上述兩個(gè)最優(yōu)解.所以該隊(duì)接力賽跑可以有兩種最優(yōu)指派方案：

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

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

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

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

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

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

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

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

例2若一頁文檔被切割成4個(gè)條狀碎片，序號(hào)分別為1,2,3,4，令

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

表2 碎片之間的匹配度

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

通過表2觀察可知，匹配矩陣C中有獨(dú)立最大元素(用括號(hào)()標(biāo)記的元素)，根據(jù)定理2可知此模型的最優(yōu)解矩陣為

注意，通過表2已知最優(yōu)解中x21并不表示序號(hào)2與1中匹配，只是為了湊成4個(gè)“獨(dú)立的元素1”，故它的取值用括號(hào)()標(biāo)注.從最優(yōu)解矩陣中可以看出碎片的匹配順序?yàn)椋?,3,4,2，并且利用最優(yōu)解可計(jì)算最大總匹配度為

3 結(jié)論

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