匈牙利法Hungarianmethod一

分配問題與匈牙利法

AssignmentproblemandHungianmethod

若干項工作或任務(wù)需要若干個人去完成。由于每人的知識、能力、經(jīng)驗的不同，故各人完成不同任務(wù)所需要的時間不同（或其他資源）。問應(yīng)指派哪個人完成何項工作，可使完成所有工作所消耗的總資源最少？問題的提出任務(wù)人員B1B2B3B4A1215134A21041415A39141613A478119

例1：設(shè)某工程有B1,B2,B3,B4

四項任務(wù)，需由四個工人A1,A2,A3,A4去完成，由于任務(wù)性質(zhì)和每個工人的技術(shù)水平不相同，他們完成各項任務(wù)所需的時間也不一樣（見表）。問應(yīng)當(dāng)如何分配，即哪個人去完成哪項任務(wù)，才能使完成四項任務(wù)的總時間最少？數(shù)學(xué)模型設(shè)該問題的解為：用矩陣形式表示為:解矩陣

設(shè)有n項任務(wù)，需有n個人去完成，每個人只能完成一項任務(wù)，每項任務(wù)只能由一個人去完成，設(shè)第i人完成第j項任務(wù)需要的時間是aij,問如何分配才能使完成任務(wù)的總時間最少？一般分配問題設(shè)二分配問題的匈牙利解法定義1

效率矩陣

其中aij0表示第i人完成第j項任務(wù)的效率（時間、費用等）。定義2

任務(wù)的一種分配方法稱為一個匹配。（分配問題的一個解），使目標(biāo)函數(shù)取得最小值的匹配稱為最優(yōu)匹配（最優(yōu)解）特點：每行恰有一個1；每列恰有一個1。匈牙利方法的基本思想效率矩陣：最優(yōu)解:

如果效率矩陣的所有元素aij0,而其中存在一組位于不同行不同列的0元素,則只要令對應(yīng)于這些位置的xij=1，其余xij=0，就可以得到分配問題的最優(yōu)解。定義3位于效率矩陣的不同行不同列的0元素稱為獨立0元素。問題：如何產(chǎn)生這組獨立0元素？匈牙利解法的基本步驟第一步：初始變換獲得0元素。從效率矩陣的每行減去該行的最小元素；然后從所得矩陣的每列減去該列的最小元素，令所得矩陣為B.第二步：在B中尋找位于不同行、不同列的0元素。（1）檢查B的每行每列，從中找出未加標(biāo)記的0元素最少的一排（即行列的統(tǒng)稱），在該排用()標(biāo)出一個0元，若該排有多個0元，則任意標(biāo)出一個即可；（2）把剛得到()號標(biāo)記的0元所在的行、列中的其余0元劃去，用表示；（3）凡是(0)，就成為加了標(biāo)記的0元，返回（1）重復(fù)（1）、（2）、（3），直到所有0元都加上標(biāo)記為止。若得到的加()號的0元素個數(shù)等于n，則結(jié)束；否則轉(zhuǎn)第三步。第三步：找出能覆蓋矩陣中所有0元素的最少直線集合。（1）對沒有(0)的行打；（2）對已經(jīng)打的行中所有元素所在的列打；（3）再對打的列中所有(0)元素所在的行打；（4）重復(fù)（2）（3）直到得不出新的打的行、列為止；（5）對沒有打的行和打的列劃線，即為覆蓋所有0元素的最少直線。第四步：修改矩陣B以增加獨立0元素的個數(shù)。（1）在未被直線覆蓋的所有元素中，找出最小元素；（2）所有打的行都減去此最小元素，然后所有打的列都加上此最小元素，令這個新矩陣為B，返回第二步。三

例題例1：用匈牙利解法解本節(jié)例題效率矩陣：第一步：初始變換2151341041415914161378119249701311260101105740142004201370606905320100得解矩陣：找獨立0元素01370606905320100總時間為:4+4+9+11=28例2：用匈牙利解法解下列分配問題效率矩陣：1279798966671712149151466104107109第一步：初始變換000001279798966671712149151466104107109767645020223000010572980040636550202230000105729800406365第二步：尋找獨立0元素最小元素為

min{10,5,7,2,6,3,6,5}=2-2-2+270202430000835011800404143它有5個獨立0元，得到最優(yōu)解相應(yīng)的解矩陣為最優(yōu)目標(biāo)值：7+6+9+6+4=32例3：求解下列分配問題效率矩陣10978587754652345

工作人員ABCD甲10978乙5877丙5465丁2345

109785877546523457542320103221021012300013200032110200122-1-1+142000210202000114200021020200011第一組最優(yōu)解第二組最優(yōu)解兩點說明1.效率矩陣不是方陣的情況。（即人員與工作數(shù)不相等）

處理方法：增加虛擬人或工作，使兩者相等。虛擬人或工作對應(yīng)的效率矩陣中元素為0。2.最大化分配問題的處理。

如果給出的效率矩陣中的數(shù)字表示每個人完成各項任務(wù)的收益，則問題變成了如何分配任務(wù)才能使總收益最大？處理方法：用效率矩陣中的最大元素減去矩陣中的各個元素得到一個新的矩陣，對這個新的矩陣用匈牙利方法求解。四

《基于匈牙利法的企業(yè)員工任務(wù)分配問題研究》基金項目：國家社科基金資助項目（06BZZ022）統(tǒng)計與決策2011年第5期摘要：現(xiàn)代企業(yè)的發(fā)展，必須依托科學(xué)高效的管理模式，各項資源配置的合理優(yōu)化，以達到提高勞動生產(chǎn)率，降低生產(chǎn)成本和獲取高額利潤的目標(biāo)。因此立足于現(xiàn)代企業(yè)管理的宗旨，通過借鑒匈牙利法，結(jié)合人員任務(wù)分配實例進行分析研究，最終得出人員與崗位配置的最優(yōu)化解，從而為企業(yè)的人事決策提供參考。關(guān)鍵詞：員工任務(wù)分配；匈牙利法；指派；最優(yōu)化解匈牙利法”應(yīng)用的實證分析1、求解最大化問題如果所要求的是最大化問題，那么可以將其轉(zhuǎn)化為最小化問題進行求解。2、求解最小化問題：在應(yīng)用匈牙利法時，求解最小化問題，一般包括：工作時間最小化、生產(chǎn)成本最小化及企業(yè)費用最小化等。在求解最小化問題的過程中，必須充分考慮到以下三種情況:（1）當(dāng)員工數(shù)目與任務(wù)數(shù)目相等。例：假定某企業(yè)有甲、乙、丙、丁、戊五名員工，需要在一定的生產(chǎn)條件下完成A、B、C、D、E五項任務(wù)，每個員工完成每項工作所需要耗費的工時，如表1所示，員工與任務(wù)之間應(yīng)該怎樣進行配置，才能保證完成工作任務(wù)所用的時間最短。

利用匈牙利法可以得出結(jié)論，完成此項任務(wù)的最優(yōu)分配方案是：甲負責(zé)任務(wù)A，乙負責(zé)任務(wù)D，丙負責(zé)任務(wù)B,丁負責(zé)任務(wù)C，戊負責(zé)任務(wù)E。此時工作完成的時間最短，最短時間是：10+8+7+5+10=40小時。（2）當(dāng)員工數(shù)目多于任務(wù)數(shù)目時。

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

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

根據(jù)表3內(nèi)容，可以構(gòu)建效率矩陣C，然后用上文中同樣的方法進行計算，最后得出的結(jié)果是：趙做丙工作，錢做甲工作，孫做乙工作，王做丁工作，此時李沒有分配到任務(wù)，經(jīng)計算得出最短的工作時間為：6+6+7+15=34小時。（3）當(dāng)員工數(shù)目少于任務(wù)數(shù)目時。當(dāng)員工數(shù)目少于任務(wù)數(shù)目的情況下，就必須考慮讓一個員工承擔(dān)兩個或多個任務(wù)。例：B公司安排2名員工去完成3項任務(wù)，每個員工完成任務(wù)的時間如表4所示，求解工作時間最短的任務(wù)分配方案。分析：由于兩名員工要負責(zé)完成三項任務(wù)，因此必須有一名員工承擔(dān)兩項工作，在此，增設(shè)甲1和乙1兩個人，以及虛任務(wù)D來分別表示他們完成此項任務(wù)的情況，從而表4可以變形得到表5利用匈牙利法進行計算，最后得出的任務(wù)分配方案是：甲做B項任務(wù)，乙做A、C項任務(wù)。此時的最短工作時間為：12+6+5=23小時。優(yōu)與劣勢“匈牙利法”在企業(yè)人力資源管理中的優(yōu)劣分析匈牙利法自推廣以來，迄今為止已經(jīng)成為企業(yè)人事決策的重要輔助工具，匈牙利法的最大特點就是能夠科學(xué)的對人員和工作進行合理的配對，即通常所說的“人事匹配”。利用匈牙利法進行合理的勞動分工，發(fā)揮出員工的最大潛能，既可以幫助企業(yè)創(chuàng)造出最大的利潤，實現(xiàn)最初制定的戰(zhàn)略目標(biāo)，同時也可以避免企業(yè)內(nèi)外部各項資源的閑置浪費，發(fā)揮各項資源的邊際效用。然而，任何一種技術(shù)手段和工具本身都具有現(xiàn)實制約性，存在某些不足，因此，匈牙利法在現(xiàn)代企業(yè)人力資源管理中的應(yīng)用也體現(xiàn)出積極和消極兩方面的作用。1.積極作用根據(jù)上文中，匈牙利法在現(xiàn)實應(yīng)用的實證研究，其積極作用主要可以概括為以下幾個方面：（1）為人員配置提供科學(xué)決策。

人力資源作為推動現(xiàn)代企業(yè)前進的內(nèi)驅(qū)力，先進科學(xué)的管理模式可以幫助企業(yè)在短期內(nèi)獲得巨大收益。匈牙利法的應(yīng)用，一方面解決了企業(yè)中經(jīng)常關(guān)注的人員分配問題，促進了生產(chǎn)力的發(fā)展和員工工作積極性的提高，另一方面合理的“能崗配置”，促進了企業(yè)內(nèi)部部門之間以及其他一系列管理活動順暢有序的進行，為企業(yè)利潤的增長，戰(zhàn)略的制定，績效的考評，薪酬的設(shè)置等人力資源管理的重要環(huán)節(jié)提供了科學(xué)可行的決策方法和手段。（2）操作簡單，應(yīng)用性強。

在當(dāng)今國際化的市場競爭中，企業(yè)成本和利潤成為衡量其經(jīng)營績效的重要參考指標(biāo)，企業(yè)經(jīng)營的目標(biāo)都是以最小化的成本換回最大化的利潤回報。隨著現(xiàn)代科技的飛速發(fā)展，企業(yè)必須適應(yīng)時代的潮流，不斷進行技術(shù)創(chuàng)新和產(chǎn)品研發(fā)，在此過程中，科學(xué)合理的決策方案將成為影響企業(yè)發(fā)展的重要因素。匈牙利法不僅可以為企業(yè)人事決策提供可靠的政策建議，同時可以預(yù)測和估算出企業(yè)未來一段時期的成本和收益總量，而且操作方便，應(yīng)用性強，受到了現(xiàn)代企業(yè)管理者的青睞。（3）應(yīng)用的領(lǐng)域較廣泛。

隨著匈牙利法的普遍推廣，其應(yīng)用領(lǐng)域已經(jīng)從現(xiàn)代企業(yè)部門拓寬到了公共事業(yè)單位及交通運輸行業(yè)等等，包括像很多的競技體育類項目，學(xué)校課程安排，以及交通線路的優(yōu)化改良等方面都合理巧妙地利用了匈牙利法的優(yōu)勢和特點，為各行各業(yè)的管理決策活動，提供了科學(xué)保證。因此，匈牙利法的應(yīng)用可以促進社會生產(chǎn)力的發(fā)展，充分發(fā)揮資源優(yōu)化配置的功能，從而節(jié)省了大量不必要資源的投入和消耗，節(jié)約了成本，提高了利潤。2、消極影響匈牙利法的應(yīng)用，盡管給人們的日常管理工作帶來了較大的便利，但是與此同時，其本身也存在著一定的缺陷，具體表現(xiàn)為：（1）計算過程較繁瑣。

經(jīng)過國內(nèi)外學(xué)者的研究發(fā)現(xiàn)，匈牙利法普遍存在的一個較大的問題就是運算量較大，運算過程較繁瑣。一般情況下，匈牙利法的計算過程都要經(jīng)過很多步驟，如果中間稍有差錯，就可能導(dǎo)致最