陳海偉，王潔

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

一類非平衡指派問(wèn)題的求解

陳海偉，王潔

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

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

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

1 問(wèn)題的提出

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

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

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

例1設(shè)有3項(xiàng)任務(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個(gè)假想任務(wù)D，然后用匈牙利算法求解.

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

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

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

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

此時(shí)有4個(gè)獨(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項(xiàng)任務(wù)，并賦予每個(gè)人完成這些虛擬任務(wù)所費(fèi)的時(shí)間為0，使之轉(zhuǎn)化成任務(wù)數(shù)為m'=(k+1)n的情況，此時(shí)的費(fèi)用矩陣為

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

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

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

得6個(gè)獨(dú)立零元素0*，但最后一項(xiàng)任務(wù)不存在，所以最佳指派為:甲翻譯英文和俄文，乙翻譯日文和法文，丙翻譯德文，最少總時(shí)間為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í)經(jīng)濟(jì)師.