匈牙利算法求解教學任務指派問題

楊帆++李慧++胡又農

摘 要 在實際教學中，任務指派問題是一個綜合考慮教師特長、學生滿意度、教師教學精力等多因素的決策問題。應用匈牙利算法建立指派模型，求解復雜因素下的教學任務指派問題，定量、精準地將恰當的教學任務分配給適當的教師，以使系統總體滿意度最大化。該指派優化模型的建立，使得任務分配更加客觀和明確。

關鍵詞 匈牙利算法；教學任務；任務指派問題；MATLAB

中圖分類號：G642 文獻標識碼：B

文章編號：1671-489X（2017）14-0012-03

Hungarian Algorithm for Teaching Task Assignment Problem//YANG Fan， LI Hui， HU Younong

Abstract In a practical teaching， the task assignment problem is a

decision-making problem which considers teachers specialty， stu-dents satisfaction， teachers teaching energy and so on. In this paper，

in order to maximize the overall satisfaction of the system， the assign-

ment model is established by using the Hungarian algorithm to solve the task assignment problems in complex conditions， by assigning appropriate teaching tasks to appropriate teachers quantitatively and

accurately. The assignment optimization model makes task assign-ments more objective and clear.

Key words Hungarian Algorithm； teaching task； task assignment problem； MATLAB

1 前言

隨著教學內容的擴展，各類前沿技術在課堂中得到充分體現，教學課程的設置、教學任務的分配等問題也變得更加復雜。傳統的教學任務指派，主要是根據任務之間的關系、教師的授課情況和學生的偏好，由專門的教學管理人員制定課程表，費時、費力且效率低，屬于典型的經驗型管理。隨著教學管理信息化含量的日益提升，定性的人工進行教學任務指派的情況已無法適應定量、快速、自動的科學管理要求。因此，有必要引入運籌學的理論和方法解決教學任務指派問題，并以計算機輔助解決實際問題。

本文基于匈牙利算法，建立教學任務指派優化模型，分析如何分配教師承擔教學任務以使系統整體滿意度最大化，并采用MATLAB編程實現求解。

2 指派問題

指派問題的常用描述是有n個人可承擔m項任務，由于每人的專長不同，完成不同任務的效率也不同，如何指派哪個人完成哪項任務，使完成所有任務的總效率最高或所需總時間最少？指派問題是運輸問題中的一種特殊情況，“派合適的人去做合適的事”是對該問題的最貼切描述。

指派問題的數學模型通常是：設n個人（或機器）被分配去做m件工作，由于工作性質和各人（或機器）的專長不同，完成不同工作的效益（時間、成本、收益等）將有差別，用系數矩陣C表示，Cij表示第i個人完成第j件工作的效益，Cij≥0（i=1，...，n；j=1，...，m）。當n=m時，為平衡狀態下的標準指派問題；當n>m時，人數多于任務數，屬于不平衡狀態下擇優錄用問題；當n

使得總效益最高（時間最少、成本最小、收益最大等），即目標函數。當且時，為一對一指派問題；否則為多人協作或兼職問題。

求解指派問題的方法通常有分支定界法、隱枚舉法、匈牙利法等[1]。匈牙利算法由匈牙利數學家Edmonds于1965年提出，是基于Hall定理中充分性證明的思想，用增廣路徑求二分圖最大匹配的算法，算法的核心是尋找增廣路徑，也可用于指派問題的求解[2]。

針對多人執行多項工作的指派問題，張云華采用匈牙利算法的基本思想和步驟進行了研究[3]。目標分配問題作為指派問題的一種類型，谷穩綜合匈牙利算法及其進化算法的特點，對機器人足球的目標分配問題進行了研究[4]。為避免匈牙利算法多次試分配導致處理速度慢的不足，周莉等人對尋找獨立零的次序進行改進，得到匈牙利算法求解指派問題的一次性分配算法[5]。李延鵬等人提出利用虛擬工作代替并聯環境，將具有并聯環節的人員指派問題轉化為典型的指派問題，提高了匈牙利算法的適用性[6]。謝博耶夫采用反圈法和對稱差，對匈牙利算法進行了推廣[7]。對于“人少任務多”型指派問題的解決，與“加邊補零”法、“加邊補最小值”法等傳統解法不同，馬曉娜通過差額法對匈牙利算法進行了改進[8]。

3 基于匈牙利算法的任務指派優化模型

問題描述 教學課程的指派優化問題，需要綜合考慮教師教學特長、學生滿意度、課程內容等多因素，追求教學質量、滿意度和教師教學精力等多目標的優化決策問題，任何一個參數的改變都可能影響最終的指派結果。該類問題可描述為：

假設有n名不同教研室的教師，N={N1，N2，...，Nn}，所有教師可以講授課程共m門，M={M1，M2，...，Mm}。已知n名教師對m門課程的擅長程度矩陣G、n名教師的課時上限序列U和學員對教師滿意度序列S，如何安排n名教師教授的課程，使得總體教學質量、教師精力和學生滿意度最優化？

指派優化模型 由于該問題涉及因素較多，因此，采用解析方法或傳統的匈牙利算法難以給出合適結果。總體最優化的前提是教師擅長課程、精力和學生滿意度滿足基本要求，本文采用比值的方式求解三種因素的綜合表現。矩陣G元素值為百分比，Gij值越高，表明第i名教師對第j門課程的擅長程度越好。序列U和S經過歸一化處理后，也可表現為百分比形式，Ui值越高，表明第i名教師的教學任務越飽滿；Si值越高，表明學生對第i名教師的滿意度越高。以Tij表現三種因素綜合影響下第i名教師教授第j門課程的情況。Tij值與Gij、Si呈現正相關關系，而與Ui呈現負相關關系，計算得到：

末位淘汰制是當前高校教師競爭較為常用的制度[9]，對所有教師求解Tij，對Tij按值由高到低排序PT，根據T進行課程指派前的初始末位淘汰。因此，模型的目標方程為：

約束條件如下：

1）n為能夠完成教學任務的教師數量，m為需要完成的教學課程數量，i表示教師，j表示教學課程；

2）教師擅長教學課程的程度矩陣G，其值由教學專

家、往屆學生成績和教師自身資歷確定，其值越高，表明越擅長；

3）教學課時飽滿程度序列U，由教師所承擔的教學任務、科研任務、外出授課學習和自身情況確定，其值越高，表明教師課程任務越重；

4）學生滿意度序列S，由往屆學生評價、本屆學生評價綜合確定，其值越高，表明教師講授課程的受歡迎程度越高；

5）矩陣為修正后的擅長矩陣，依據G、U和S求解T，采用末位淘汰制修正G后成為。

模型求解

1）構建平衡的矩陣G。求解平衡問題是匈牙利算法的特長，當教師數量和教學課程數量不相等時，需要增添虛擬的教師或課程，重新構建平衡的矩陣G。具體方法如下：

①若n>m，一門教學課程可能由多個教師講授，屬于不平衡狀態下擇優錄用問題，可虛擬n-m門課程，構建新的平衡矩陣G={Gn×m∣Gn×（n-m）}。

②若n

③若n=m，屬于平衡狀態下的標準指派問題，直接由匈牙利算法求解。

構建結束后，由求解最大值轉為求解最小值，將目標函數轉為標準的目標函數。即求，令

，則與有相同的最優解。

2）處理擅長矩陣、飽滿序列和滿意度序列。如果某教師Ni無法講授某項課程Mj，則將擅長矩陣G對應元素Gij的值設定為0。對滿意度序列S進行歸一化處理：

對課程飽滿程度序列U進行歸一化處理：

3）修正擅長矩陣G。根據處理后的擅長矩陣、飽滿序列和滿意度序列，求解T進行末位淘汰。將所有Tij值按由高到低的順序進行排序，設定合理的淘汰比例p，對于排名低于p的，取消該教師講授相應課程的安排，即當PT（Tij）≤p時，Gij=0，修正形成矩陣G′。

4 實例分析

某高校計劃開設創客空間，需要開展的教學任務有焊接、車工、鉗銑磨工、數控、3D打印、切割?，F有8名教師可承擔相關課程教學，教師對教學課程的擅長矩陣G見表1。根據教師自身安排、專家組打分和課時等分析，得到教師教學任務的飽滿程度序列U，見表2。通過問卷調查、往屆課程成績、學生座談等形式，得到學生對教師的滿意度序列S，見表3。根據學校本學期末位淘汰安排，執行p=15%的末位淘汰率。計算T并進行排序，如表4所示，得到綜合排名靠后的教師課程為（A2-車工）、（A2-鉗銑磨工）、

（A3-數控）、（A4-車工）、（A6-3D打?。┖停ˋ7-焊接），將其執行末位淘汰改進矩陣G′。

隨后采用匈牙利算法進行最優化指派，使用MATLAB進行編程求解，得到教師A2和A7不參與該項教學任務，其他的如表5所示。

5 結論

在傳統教學任務指派中，需考慮教師擅長度和教學任務飽滿程度、學生滿意度等諸多問題，采用一般經驗進行定性的任務指派費時、費力、效率低。而采用定量分析和計算機輔助解決實際問題，使得結論客觀而可靠。本文從實際教學出發，以教學任務指派問題建立模型，應用匈牙利算法實現總滿意度最高的求解，使得任務分配更加客觀和明確，具備可操作性和可重復性，為教育任務分配提供科學依據。

參考文獻

[1]胡運權，郭耀煌.運籌學教程[M].4版.北京：清華大學出版社，2012.

[2]傅家良.運籌學方法與模型[M].上海：復旦大學出版社，2006.

[3]張云華.論匈牙利算法在指派問題管理工作中的應用[J].價值工程，2016（25）：214-215.

[4]谷穩.基于進化匈牙利算法的目標分配問題研究及應用[D].西安：西安電子科技大學，2013.

[5]周莉，張維華，徐射雕.求解指派問題的一次性分配算法[J].計算機工程與應用，2011（18）：135-138，152.

[6]李廷鵬，錢彥嶺，李岳.基于改進匈牙利算法的多技能人員調度方法[J].國防科技大學學報，2016（2）：144-149.

[7]謝博耶夫.匈牙利算法及其推廣[D].上海：華東師范大學，2016.

[8]馬曉娜.“人少任務多”型指派問題的一種新算法[J].重慶工商大學學報：自然科學版，2014（12）：68-71，75.

[9]姚維.如何看待高校實行“末位淘汰制”[J].亞太教育，

2016（22）：201，189.