課程安排中的匹配問題及求解

張敏捷

（湖北文理學院數學與統計學學院 湖北·襄陽 441053）

為保障教學質量，各級各類的學校都要結合自己的師資力量，合理地安排教學，盡最大的努力讓學生受到最好的教育。因此，在現有師資條件下，如何合理地安排教師進行課程教學，具有重要的研究意義。

例如，某學校某教學部，要安排n位教師負責n門課程的教學工作。為盡量減輕教師的教學負擔，要求每位教師負責一門課程的教學工作。如何安排可以達到最好的教學效果？

將每位老師和每門課分別用一個點表示，若某位教師能承擔某門課程的教學，則將對應的兩個點連邊。同時可基于各位老師以往負責各門課程的教學效果，對這些邊進行賦權。為方便討論，不妨先假設每位教師都有承擔這n門課程教學的能力。此時，可得到2n個頂點的賦權完全二部圖，而此時課程安排問題便可以看作求賦權完全二部圖的最大完美匹配問題。

例：某校某學期要安排五位教師甲、乙、丙、丁、戊承擔五門課程的教學任務。根據近五年的學生評教，統計出各位教師負責相關課程的平均成績，如下表所示。若以此為依據安排教學任務，如何安排，可使教學質量最好？（假設每位教師負責一門課程的教學任務。）

學生評教平均成績 課程1 課程2 課程3 課程4 課程5教師甲 93 98 94 93 90教師乙 97 94 90 94 93教師丙 92 90 96 93 97教師丁 95 93 95 90 95教師戊 90 97 93 94 90

解：首先，將此問題轉化為最小完美匹配問題。寫出此問題對應的效益矩陣A，

注意到矩陣A中最大元是98。分別用98減去矩陣A中各元素，得到矩陣C。不難驗證，求解以A為效益矩陣的最大完美匹配問題等同于求解以C為效益矩陣的最小完美匹配問題。

事實上，我們可以先將矩陣C的各行各列減去相應的最小元素，即

因此，我們可以得到如下最優方案：教師甲負責課程2，教師乙負責課程1，教師丙負責課程5，教師丁負責課程3，教師戊負責課程4。此時總評教成績為：98+97+97+95+94=481。

以上，我們將課程安排問題轉化為了二部圖的最大完美匹配問題，并利用匈牙利法對其進行了具體的求解。下面，我們給出關于此問題的幾點思考與推廣：

（2）按照上述方法尋找“0”時，若在某一步發現對應的矩陣中含“0”最少的行或列至少含有2個“0”，則說明最優方案并不唯一。我們不妨將上述例題中的數據稍作修改：將教師丁負責課程3的學生評教平均成績由之前的“95”改為“94”。重復上述過程可得

此時，我們就會自然而然地考慮：到底有多少個最優方案呢？通過上述過程，不難發現，確定最優方案的個數等同于尋找矩陣中位于不同行、不同列的5個“0”的組數。而這個問題又可以轉化為求其補矩陣的積和式的問題。在文獻[3]中，鐘守楠教授和高成修教授給出了矩陣的補矩陣及其積和式的定義：

定義1：將矩陣M中“0”改為“1”，非零元都改為“1”，所得矩陣稱為M的補矩陣。

由定義2發現，方陣積和式的定義與方陣行列式的定義極為相似，只是在各項前面不用考慮正負號了而已。因此，計算矩陣積和式最有效的方法便是利用行列式計算中按行（列）展開的思想進行的，我們也通常通過按某一行（列）展開來計算方陣的積和式，只需注意展開時需要考慮該行各元素乘以對應的余子式之和，而不是代數余子式。

（1）值得注意的是，對于效益矩陣或C者經過上述變形后的效益矩陣，如果其補矩陣的積和式為0，并不能說明這個問題沒有最優方案。站在枚舉的角度思考，此問題等同于在5種可能的方案里面找最優方案，故最優方案是一定存在的。

我們可以采用如下方法：

不妨在上述例題中，將教師丙負責課程2與課程5的學生評教平均成績對調，即教師丙負責課程1-5的學生評教平均成績分別為 92，97，96，93，90。重復上述過程可得：

（2）此問題可考慮借助于Lindo或者Lingo程序來求解。尤其是當教師的人數與課程的門數不相等的情形。具體解決思路值得進一步研究。

致謝：

感謝國家自然科學青年基金（No.11901179）的資助；感謝湖北文理學院科研啟動基金的資助。