匈牙利算法在指派問題中的運用

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

（西南科技大學經濟管理學院，四川綿陽621010）

引言

隨著現代化先進科學技術的發展，先進的生產設施、科學的管理思想等使得生產運作系統功能不斷完善，企業生產運作效率不斷提高。與此同時人員成本頗高仍是限制企業高效、常穩發展的一塊短板。如何在已有經驗數據的基礎上對企業人員進行更高效合理的配置是減小人力成本的一有效舉措。

1 指派問題

指派問題，其目的是安排m個人完成n項任務并使總效率達到最高（即所需總時間最少），也稱為分配或配置問題，是關于資源合理配置或最優配置的問題。

2 匈牙利算法簡介

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

匈牙利算法的步驟：

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

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

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

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

表1.1效率表

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

3 匈牙利算法在具體指派中的運用

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

運用匈牙利完后五項任務分配的指派問題具體步驟如下：

3.1 建立標準化效率矩陣B1。增加人員v5行，其對應五項任務的矩陣分別為0(其他四人的效率最小值)。

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

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

4 結語

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