匈牙利算法在指派問題中的運(yùn)用

鐘莉夢桃，易磊，葛巍，歐懿坤

（西南科技大學(xué)經(jīng)濟(jì)管理學(xué)院，四川綿陽621010）

引言

隨著現(xiàn)代化先進(jìn)科學(xué)技術(shù)的發(fā)展，先進(jìn)的生產(chǎn)設(shè)施、科學(xué)的管理思想等使得生產(chǎn)運(yùn)作系統(tǒng)功能不斷完善，企業(yè)生產(chǎn)運(yùn)作效率不斷提高。與此同時(shí)人員成本頗高仍是限制企業(yè)高效、常穩(wěn)發(fā)展的一塊短板。如何在已有經(jīng)驗(yàn)數(shù)據(jù)的基礎(chǔ)上對(duì)企業(yè)人員進(jìn)行更高效合理的配置是減小人力成本的一有效舉措。

1 指派問題

指派問題，其目的是安排m個(gè)人完成n項(xiàng)任務(wù)并使總效率達(dá)到最高（即所需總時(shí)間最少），也稱為分配或配置問題，是關(guān)于資源合理配置或最優(yōu)配置的問題。

2 匈牙利算法簡介

匈牙利算法，是基于效率矩陣每一行元素減去該行位勢，每一列元素減去該列位勢后得到的新效率矩陣和原效率矩陣最優(yōu)解相同，以及矩陣A中覆蓋所有0元素的最少直線數(shù)等于位于不同行不同列的零元素（即獨(dú)立元素）的最大個(gè)數(shù)這兩個(gè)定理來解指派問題的計(jì)算方法。其具有三個(gè)運(yùn)算前提：目標(biāo)函數(shù)求最小值、人數(shù)m與任務(wù)數(shù)n相等以及效率非負(fù)。

匈牙利算法的步驟：

2.1 建立資源配置方案的效率矩陣，并轉(zhuǎn)換為匈牙利算法所要求的標(biāo)準(zhǔn)型d×d階矩陣B，其中d=max(n,m)。當(dāng)人數(shù)m 小于任務(wù)數(shù)n時(shí)，增加虛擬人員行，當(dāng)任務(wù)數(shù)n小于人數(shù)m時(shí)，增加虛擬任務(wù)列。

2.2 分別找出當(dāng)前效率矩陣中每行每列的最小元素，并分別從每行、每列中減去該元素，形成新效率矩陣。

2.3 用最少直線數(shù)k覆蓋所有零元素。

2.4 當(dāng)k=d時(shí)停止運(yùn)算，得到最優(yōu)配置方案，當(dāng)k≠d時(shí)，從矩陣未被覆蓋的數(shù)字中找到最小數(shù)值s,未被覆蓋的元素減去s,直線相交處元素加上s,被直線覆蓋而沒有相交的元素不變,得到新效率矩陣C1。

表1.1效率表

2.5 重復(fù)以上步驟2、3，直至k=d。

3 匈牙利算法在具體指派中的運(yùn)用

現(xiàn)要求四個(gè)人（v1、v2、v3、v4）完成五項(xiàng)任務(wù)（u1、u2、u3、u4、u5），其中某人將完成兩項(xiàng)，四人各自完成五項(xiàng)工作的效率如表1.1所示。

運(yùn)用匈牙利完后五項(xiàng)任務(wù)分配的指派問題具體步驟如下：

3.1 建立標(biāo)準(zhǔn)化效率矩陣B1。增加人員v5行，其對(duì)應(yīng)五項(xiàng)任務(wù)的矩陣分別為0(其他四人的效率最小值)。

3.2 找出當(dāng)前效率矩陣中每行的最小元素，并從每行中減去該元素，形成新效率矩陣B2。找出效率矩陣B2中每列的最小元素，并從每列中減去該元素，形成新效率矩陣B3。

由以上最終指派矩陣E得出結(jié)論：人員v1完成任務(wù)u3，u4，（E中顯示虛擬人員v5完成任務(wù)u4，此時(shí)由完成任務(wù)u4效率最高的v1完成），人員v2完成任務(wù)u5，人員v3完成任務(wù)u1，人員v4完成任務(wù)u2。

4 結(jié)語

提高人員工作效率降低人力資源成本是企業(yè)不斷消除浪費(fèi)、降低成本，積極進(jìn)取的經(jīng)營思想，是企業(yè)的求生之路。而資源的優(yōu)化配置正是企業(yè)提高生產(chǎn)運(yùn)作管理系統(tǒng)，以減少企業(yè)成本增加消費(fèi)者剩余的一種有效途徑。本文結(jié)合實(shí)際案例，運(yùn)用運(yùn)籌學(xué)中求解指派問題的匈牙利法建立指派問題模型并求得效率在理想狀況下的最優(yōu)解，驗(yàn)證了匈牙利法在求解實(shí)際人員分配方案的可行性。