一類非平衡指派問題的求解

陳海偉，王潔

(商丘工學(xué)院管理系，河南商丘 476000)

一類非平衡指派問題的求解

陳海偉，王潔

(商丘工學(xué)院管理系，河南商丘 476000)

討論了一類非平衡指派問題的求解方法，即要求指派給各人的任務(wù)數(shù)目兩兩之間相差不能超過1，并且要求所需總費(fèi)用或總時間最少的非平衡指派問題，采取虛擬假想任務(wù)或者虛擬假想人的方法將之轉(zhuǎn)化為平衡指派問題進(jìn)行求解.

非平衡指派問題;匈牙利算法;費(fèi)用矩陣;轉(zhuǎn)化

1 問題的提出

在生活中，經(jīng)常會遇到把幾個任務(wù)分配給不同的人員去完成，由于每個人員完成任務(wù)的效率和效益不相同，因此需要科學(xué)地分配任務(wù)，使總效益最高，或使總費(fèi)用最少的問題，這就是指派問題.其通常的提法為:n個人去做m件工作，其中第i個人做第j件工作所需的時間或費(fèi)用cij，記費(fèi)用矩陣為C=(cij)n×m.當(dāng)m=n時，擬每人做1件工作，且每件工作1個人去做，則如何分配任務(wù)可使總費(fèi)用最少?這是人數(shù)和任務(wù)數(shù)相同的指派問題即平衡指派問題，庫恩(Kuhn W W)于1955年給出了其經(jīng)典算法即匈牙利算法［1］.但事實上，生活中遇到的指派問題大多是人員數(shù)和任務(wù)數(shù)不等的情況(人數(shù)n與任務(wù)數(shù)m不相等)，即非平衡的指派問題.此類指派問題的特點(diǎn)是要求各人承擔(dān)的任務(wù)數(shù)量一致，否則在費(fèi)用矩陣中用最小元素法［2］很容易得到使總費(fèi)用最小的指派方案，但這樣一般會出現(xiàn)有些人承擔(dān)多項任務(wù)，而另外有些人分配不到任務(wù)的情形，因此要求指派給各人的任務(wù)數(shù)兩兩相差不能超過1，其次要求總費(fèi)用最小.對于此類不平衡的指派問題，可以采取一定的方法使之轉(zhuǎn)化為平衡的指派問題，然后用匈牙利算法進(jìn)行求解.

2 人數(shù)大于任務(wù)數(shù)(n＞m)

解決方法:虛設(shè)n－m項假想任務(wù)，并賦予每個人完成這些虛擬任務(wù)所費(fèi)的時間為0，將問題轉(zhuǎn)化為人數(shù)與任務(wù)數(shù)相等的指派問題，然后利用匈牙利算法求解.

例1設(shè)有3項任務(wù)A、B、C，可安排甲、乙、丙、丁4人去完成，各人完成任務(wù)的費(fèi)用矩陣P如下，應(yīng)怎樣指派任務(wù)，才能使所需總費(fèi)用最少?

解人數(shù)n=4，任務(wù)數(shù)m=3，人數(shù)大于任務(wù)數(shù)，應(yīng)虛設(shè)1個假想任務(wù)D，然后用匈牙利算法求解.

此時即得4個獨(dú)立的零元素0*，即指派甲完成任務(wù)C，乙完成任務(wù)B，丙完成任務(wù)D，丁完成任務(wù)A.由于任務(wù)D不存在，所以丙并沒有分配任務(wù).

3 人數(shù)小于任務(wù)數(shù)(n＜m)

3.1 任務(wù)數(shù)m是人數(shù)n的k倍(其中k為整數(shù)，且k≥2)

解決方法:1個人完成k項任務(wù)，可采用將1個人虛擬成k個人的方法，將其轉(zhuǎn)化成平衡指派問題，費(fèi)用矩陣則成為kn× kn方陣(矩陣Ⅰ)，再利用匈牙利算法求解.矩陣Ⅰ:

此時有4個獨(dú)立零元素0*，所以最佳指派為甲完成任務(wù)A和D，乙完成任務(wù)B和C，最小費(fèi)用為2+4+4+14=24.

3.2 任務(wù)數(shù)m不是人數(shù)n的整數(shù)倍

解決方法:設(shè)m=kn+b(其中k≥1為整數(shù)，1≤b＜n為整數(shù))，虛設(shè)n－b項任務(wù)，并賦予每個人完成這些虛擬任務(wù)所費(fèi)的時間為0，使之轉(zhuǎn)化成任務(wù)數(shù)為m'=(k+1)n的情況，此時的費(fèi)用矩陣為

然后采用同3.1的做法，可將一個人化成k+1個人，轉(zhuǎn)化為平衡指派問題，費(fèi)用矩陣為(k+1)n×(k+1)n階方陣(矩陣Ⅱ)，然后利用匈牙利算法求解.矩陣Ⅱ:

例3有一份手機(jī)說明書，要分別譯成英、日、德、俄、法5種文字，交給甲、乙、丙3個人去完成(完成工作所需時間如表1)，并且要求分配各人的任務(wù)數(shù)兩兩不能超過1，1種語言也只能由1個人去完成，如何分配任務(wù)，可使總的消耗時間最少?

表1 完成工作所需時間表/hTab.1Schedule to complete the work/h

得6個獨(dú)立零元素0*，但最后一項任務(wù)不存在，所以最佳指派為:甲翻譯英文和俄文，乙翻譯日文和法文，丙翻譯德文，最少總時間為1+2+3+6+14=26 h.

［1］胡運(yùn)權(quán).運(yùn)籌學(xué)教程［M］.3版.北京:清華大學(xué)出版社，2007:142－148.

［2］周溪召.運(yùn)籌學(xué)及應(yīng)用［M］.北京:化學(xué)工業(yè)出版社，2009:46－50.

Solution to Some Class of Unbalanced Assignment Problems

CHEN Hai-wei，WANG Jie

(Department of Management，Shangqiu Institute of Technology，Shangqiu 476000，China)

Discusses solution to some class of unbalanced assignment problems，which requires the task opposite number assigned to each no more than 1，and requires least total time or total expenses.Takes methods of virtual imaginary task or virtual imaginary person，and convert it into balanced assignment problem to solve.

unbalanced assignment problem;Hungarian algorithm;cost matrix;conversion

O224

A

1007－0834(2011)03－0016－03

10.3969/j.issn.1007－0834.2011.03.006

2011－04－20

陳海偉(1983—)，男，河南商丘人，商丘工學(xué)院管理系教師、中級經(jīng)濟(jì)師.