基于匈牙利法的企業員工任務分配問題研究

鄭燁，王明杰，樊娟

（湖南大學政治與公共管理學院，長沙410082）

基于匈牙利法的企業員工任務分配問題研究

鄭燁，王明杰，樊娟

（湖南大學政治與公共管理學院，長沙410082）

現代企業的發展，必須依托科學高效的管理模式，各項資源配置的合理優化，以達到提高勞動生產率，降低生產成本和獲取高額利潤的目標。因此立足于現代企業管理的宗旨，通過借鑒匈牙利法，結合人員任務分配實例進行分析研究，最終得出人員與崗位配置的最優化解，從而為企業的人事決策提供參考。

員工任務分配；匈牙利法；指派；最優化解

管理工作中，企業經常會遇到這樣的決策問題：N個人，M項任務，由于每個人的特點和能力不同，因此完成不同任務所花費的成本Cij和效率也各不同，若指定每項任務有其中的一個人完成，應如何分配任務，使得企業花費的成本最低，同時也能激發個人的工作動力，做到“因崗設職，動態適應”的原則。這類工作最優匹配的問題在運籌學中被稱為指派問題（Assignment Problem），而匈牙利法被作為解決分配問題的有效算法，在企業管理決策中常常為管理者們提供了有效人事決策方案。

1 指派問題的數學模型和“匈牙利法”概述

1 .1指派問題

指派問題（Assignment Problem）是指在滿足特定指派要求條件下，使指派方案總體效果最佳。如：有若干項工作需要分配給若干人（或部門）來完成；有若干項合同需要選擇若干個投標者來承包；有若干班級需要安排在若干教室里上課等[1]。通常在企業人力資源管理工作中，由于每個人的能力特長不同，因而完成任務的時間和績效也就不盡相同。因此，指派問題就是要利用各種定量分析的方法，科學最優化地分配任務，使完成某項任務所花費的總成本最低或總收益最大。現假設有N個員工，M項任務，由于現實中，M和N的數量可能不同，因此指派問題可以分為以下三種情況考慮：

(1)當M=N的時候，即任務的數量等于人的數量，此時每人一項任務。

(2)當M>N時,即任務的數量多于人的數量。這時可以通過虛設(M-N)個人構成一個M×M的效率矩陣,并且這個(MN)人在執行M項任務時的效率應該是成本最高的。

(3)當M

通過虛設任務或人,使得指派問題要求最小化，即：時間、成本及資源耗費等為最小，現假設Xij=1，表示由第i個人去做第j項工作，否則Xij=0，于是得出指派模型為：

目標函數表示完成全部n項工作所消耗的總資源最少，Cij表示指派第i個人去完成第j項任務時所消耗的資源,有Cij(i=1,2,3,…,n；j=1，2，3，…，n)組成的方陣,稱為系數矩陣,簡記為C。

約束條件（1）說明第j項任務只能由一個人去完成，約束條件（2）說明第i人只能完成一項任務[2]。

Xij=0或1，其中

1 .2匈牙利法

1955年庫恩(W．W．Kuhn)提出了指派問題的解法，該方法是以匈牙利數學家考尼格(Konig)提出的一個關于矩陣中O元素的定理為基礎，因此得名匈牙利法[3]。其基本步驟是：(1)簡化效率矩陣，在行列中構建0元素；(2)試進行一個完全分配方案，對矩陣中的0元素作分配標記；(3)畫蓋0線，作覆蓋所有0元素的最少數的直線集合；(4)增加0元素，重復前述步驟。參閱各種文獻資料，當前國內學者在指派問題中的匈牙利算法問題的研究主要集中在以下兩個層面：

（1）匈牙利法的應用領域。國內學者韓志偉，謝駿（2008）等將匈牙利法應用到艦船維修保障資源分配問題中，提出匈牙利法的主要依據是，在效率矩陣的任何行或列中，加上或減去同一常數，并不改變最優分配。利用此性質，可使原來的效率矩陣轉變為含有很多新元素的效率矩陣，找出在其中的位于不同行、不同列的N個獨立的元素，將其取值為1，其他元素取值為0，得到原分配問題的最優解[4]。此外，石巖濤（2006）通過運用匈牙利法對一個航班時刻表中的機組人員在異地的停留時間進行分析調研后，進而提出了科學合理的人員分配方案[5]。與此同時，匈牙利法在實際管理工作中的應用也是較為廣泛的，劉曉紅，徐揚（2003）提出了基于模糊關系的工作分配算法，通過建立員工個體能力矩陣和建立工作滿意程度的模糊集，將匈牙利法應用到工作分配方案的求解中[6]。陳玉蘭（2006）介紹了匈牙利法在解決分配工作、汽車運輸以及人員選拔問題中的應用，通過舉例論證，將匈牙利法的應用過程和步驟清楚地進行了論證說明[7]。

（2）匈牙利法的不足和改進。熊燕華（2009）總結了匈牙利法的特點，并對現有的改進研究進行了探討，提出了匈牙利法應用的處理技巧，經驗證得出改進方法是有效的[8]。顧大全，左莉（2003）等通過全面分析匈牙利算法，找到了存在的問題及原因，對該算法進行了改進，同時提出了程序設計的關鍵技術，將匈牙利算法變為解決分配問題的最有效算法[9]。

綜合上述學者的研究，筆者認為匈牙利法在指派問題中的應用是非常廣泛有效的，尤其是在管理工作中的應用，目前很多企業在員工工作配置決策中，以及在其他資源分配問題上，匈牙利法都是比較常用的一種決策工具。鑒于此，筆者通過利用匈牙利算法對企業員工任務分配問題進行研究，從而得出科學的結論。

2 “匈牙利法”應用的實證分析

在企業的勞動組織過程中，為了提高人力資源配置的有效性，通常可以采用運籌學的定量分析方法，在解決員工任務的指派問題時，企業所普遍采用的就是匈牙利法，目的是為了實現員工與任務配置的科學化、合理化。基于上文中的指派模型，并結合實際案例，匈牙利法的應用可以推廣到以下方面[10]。

2.1 求解最小化問題

在應用匈牙利法時，求解最小化問題，一般包括：工作時間最小化、生產成本最小化及企業費用最小化等。在求解最小化問題的過程中，必須充分考慮到以下三種情況：

（1）當員工數目與任務數目相等。例：假定某企業有甲、乙、丙、丁、戊五名員工，需要在一定的生產條件下完成A、B、C、D、E五項任務，每個員工完成每項工作所需要耗費的工時，如表1所示，員工與任務之間應該怎樣進行配置，才能保證完成工作任務所用的時間最短。

表1 各員工完成任務的時間匯總表（單位：小時）

解：①以各個員工完成各項任務的時間構造效率矩陣一

②對矩陣一進行行約減，即每一行數據減去本行數據中的最小數，得到矩陣二

a、找出未被“蓋0”線覆蓋的數中的最小值λ=1，b、將未被“蓋0”線覆蓋住的數字減去λ，c、將“蓋0”線交叉點的數加上λ，因此得到矩陣五

目等于矩陣的維度，以此類推，得到最終的矩陣六

根據矩陣七可以得出結論，完成此項任務的最優分配方案是：甲負責任務A，乙負責任務D，丙負責任務B,丁負責任務C，戊負責任務E。此時工作完成的時間最短，最短時間是：10+8+7+5+10=40小時。

（2）當員工數目多于任務數目時。根據上文中指派模型的內容，當員工數目多于任務的數量時，可以通過增加虛任務，使得員工和任務二者達到匹配，增加的虛任務的工作時間和利潤都為“0”，此時企業的成本最小。例：A公司目前有趙、錢、孫、李、王五名員工，需要在既定的工作條件下完成甲、乙、丙、丁，四項工作，每個員工的工時如表2所示，求解保證工作時間最短的任務分配法。

表2 A公司員工完成任務的工時表（1）（單位：小時）

分析：此案例中，由五個員工負責四項任務，則必有一名員工沒有任務，此時企業可以通過增設虛任務E，各員工完成任務E的時間均為0，因此該做法又回歸到第一種情況，可以采用匈牙利法進行計算。表2進行變形后得到表3，即增設一項虛任務之后的情況。

表3 A公司員工完成任務的工時表（2）（單位：小時）

根據表3內容，可以構建效率矩陣C，然后用上文中同樣的方法進行計算，最后得出的結果是：趙做丙工作，錢做甲工作，孫做乙工作，王做丁工作，此時李沒有分配到任務，經計算得出最短的工作時間為：6+6+7+15=34小時。

（3）當員工數目少于任務數目時。當員工數目少于任務數目的情況下，就必須考慮讓一個員工承擔兩個或多個任務。例：B公司安排2名員工去完成3項任務，每個員工完成任務的時間如表4所示，求解工作時間最短的任務分配方案。

分析：由于兩名員工要負責完成三項任務，因此必須有一名員工承擔兩項工作，在此，增設甲1和乙1兩個人，以及虛任務D來分別表示他們完成此項任務的情況，從而表4可以變形得到表5所示：

表4 B公司員工完成任務的工時表（1）（單位：小時）

表5 B公司員工完成任務的工時表（2）（單位：小時）

利用匈牙利法進行計算，最后得出的任務分配方案是：甲做B項任務，乙做A、C項任務。此時的最短工作時間為：12+6+5=23小時。

2.2 求解最大化問題

如果所要求的是最大化問題如maxF,那么可以將其轉化為最小化問題進行求解。一般方法是:取e是一個很大的正數,一般可以取：

e=maxcij(i=1,2,…，n;j=1,2,…，n)令：bij=e-cij(i,j=1,2,…，n)

例：某外貿公司目前有5名員工完成5項任務，每個員工完成各項任務所獲得利潤如表6所示，如何進行任務分配以保證該公司獲得最大的利潤額。

表6 某外貿公司員工完成任務的收益匯總表（單位：萬元）

分析：根據上表中的數據可以得出，表中最大數據為19，用19分別減去表中的各個數據，則數據表可以轉化為表7所示，此時可以利用匈牙利法進行求解。

表7 某外貿公司員工完成任務的收益轉換表（單位：萬元）

通過表中的數據，構造效率矩陣，然后按照上文中介紹的匈牙利法求解最小化問題的解法步驟進行計算，最終得出保證該公司獲利最大的任務分配方案是：甲做D工作，乙做B工作，丙做E工作，丁做A工作，戊做C工作，此時該外貿公司可以獲得最大利潤額為：17+19+12+9+7=64萬元。

綜上所述，匈牙利法的應用方面主要集中在求解最小化問題和求解最大化問題，無論是求解最小化問題還是求解最大化問題，匈牙利法的使用都是為了給企業帶大最大的效益，或耗費最低成本。因此，人力資源管理作為現代企業長期發展的核心和根本保障，指派問題的匈牙利法在企業部門中的應用，為企業的人員配置等工作提供了科學有效的決策建議。

3 “匈牙利法”在企業人力資源管理中的優劣分析

匈牙利法自推廣以來，迄今為止已經成為企業人事決策的重要輔助工具，匈牙利法的最大特點就是能夠科學的對人員和工作進行合理的配對，即通常所說的“人事匹配”。利用匈牙利法進行合理的勞動分工，發揮出員工的最大潛能，既可以幫助企業創造出最大的利潤，實現最初制定的戰略目標，同時也可以避免企業內外部各項資源的閑置浪費，發揮各項資源的邊際效用[12]。然而，任何一種技術手段和工具本身都具有現實制約性，存在某些不足，因此，匈牙利法在現代企業人力資源管理中的應用也體現出積極和消極兩方面的作用。

3.1 積極作用

根據上文中，匈牙利法在現實應用的實證研究，其積極作用主要可以概括為以下幾個方面：

（1）為人員配置提供科學決策。人力資源作為推動現代企業前進的內驅力，先進科學的管理模式可以幫助企業在短期內獲得巨大收益。匈牙利法的應用，一方面解決了企業中經常關注的人員分配問題，促進了生產力的發展和員工工作積極性的提高，另一方面合理的“能崗配置”，促進了企業內部部門之間以及其他一系列管理活動順暢有序的進行，為企業利潤的增長，戰略的制定，績效的考評，薪酬的設置等人力資源管理的重要環節提供了科學可行的決策方法和手段。

（2）操作簡單，應用性強。在當今國際化的市場競爭中，企業成本和利潤成為衡量其經營績效的重要參考指標，企業經營的目標都是以最小化的成本換回最大化的利潤回報。隨著現代科技的飛速發展，企業必須適應時代的潮流，不斷進行技術創新和產品研發，在此過程中，科學合理的決策方案將成為影響企業發展的重要因素。匈牙利法不僅可以為企業人事決策提供可靠的政策建議，同時可以預測和估算出企業未來一段時期的成本和收益總量，而且操作方便，應用性強，受到了現代企業管理者的青睞。

（3）應用的領域較廣泛。隨著匈牙利法的普遍推廣，其應用領域已經從現代企業部門拓寬到了公共事業單位及交通運輸行業等等，包括像很多的競技體育類項目，學校課程安排，以及交通線路的優化改良等方面都合理巧妙地利用了匈牙利法的優勢和特點，為各行各業的管理決策活動，提供了科學保證。因此，匈牙利法的應用可以促進社會生產力的發展，充分發揮資源優化配置的功能，從而節省了大量不必要資源的投入和消耗，節約了成本，提高了利潤。

3.2 消極影響

匈牙利法的應用，盡管給人們的日常管理工作帶來了較大的便利，但是與此同時，其本身也存在著一定的缺陷，具體表現為：

（1）計算過程較繁瑣。經過國內外學者的研究發現，匈牙利法普遍存在的一個較大的問題就是運算量較大，運算過程較繁瑣。一般情況下，匈牙利法的計算過程都要經過很多步驟，如果中間稍有差錯，就可能導致最終結果的失靈。盡管其應用簡單易懂，但是繁瑣的計算量，使得國內學者長期以來不斷探索如何優化和改進這種方法，以提高其應用效率。

（2）無法處理一些特殊數據。盡管目前匈牙利法處理了很多與指派問題相關的分配問題、調度問題，大多數情況下，由于假定的效率矩陣的維度不多，數據較少，因而很難找出應用中的問題。然而，當處理一些較復雜的問題以及一些特殊的數據時，匈牙利算法不收斂從而導致了無法找出最終的最優解，矩陣的維度越高，不收斂的情況就越容易發生。因此，目前很多學者對于匈牙利法的應用進行不斷地修正完善，為了盡量避免各種計算偏差和失誤的發生。

4結束語

隨著現代科技的發展和生產力水平的提升，現代企業人力資源管理中應該采用定量分析的方法對企業中的員工進行崗位的配置和調整，以實現動態適應的原則。匈牙利法在企業員工任務分配中的應用，有助于解決企業人力資源管理中經常出現的用人主觀和隨意等問題，同時對企業戰略目標的實現、人員培訓和開發、績效考評、薪酬調整及職業生涯規劃等一系列管理活動都起到了重要的影響意義。因此，在科學高效地利用匈牙利法的基礎上，也必須善于發現其本身存在的缺陷和問題，不斷優化改進，以保證企業各項管理工作的客觀高效。

[1]嚴文利.求解指派問題的新方法[J]．南京審計學院學報，2009，（6）.

[2]袁遷，劉舒燕.關于匈牙利法的優化[J].武漢理工大學學報，2007，(3).

[3]張聯朋.對指派問題匈牙利解法的兩點改進[J]．西安航空技術高等專科學校學報，2007,(1).

[4]謝駿，韓志偉等.匈牙利法在艦船維修保障資源分配中的應用[J]．中國修船，2008，（2）.

[5]石巖濤.一個世紀指派問題的研究[J]．運籌與管理，2006，（4）.

[6]劉曉紅，徐揚等.基于模糊關系的人力資源管理工作分配算法[J]．軟科學，2003，（4）.

[7]陳玉蘭.指派模型在管理工作中的應用[J]．吉林財稅高等專科學校學報，2006，（4）.

[8]熊燕華.對國內求解指派問題的匈牙利法改進的評述[J]．中國制造業信息化，2009,(10).

[9]顧大全，左莉等.匈牙利法存在的問題及改進方法[J]．微機發展，2003，（4）.

[10]王瓊華,王剛.指派問題數學建模的匈牙利解法[J]．昆明冶金高等專科學校學報,2006,(5).

[11]黃龍生，徐光輝.有資格限制的指派問題的求解方法[J]．運籌與管理，2005，（1）.

[12]吳志明.招聘與選拔實務手冊[M]．北京：機械工業出版社，2006.

（責任編輯/亦民）

F270.5

A

1002-6487(2011)05-0182-04

國家社科基金資助項目（06BZZ022）

鄭燁（1986-），男，新疆阿克蘇人，碩士研究生，研究方向：人力資源管理。

王明杰（1967-），男，湖南邵陽人，博士后，教授，研究方向：人力資源管理，現代政府管理，政府信息化。

樊娟（1986-），女，陜西西安人，碩士研究生，研究方向：行政管理理論與實踐。