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

張敏捷

（湖北文理學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院 湖北·襄陽 441053）

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

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

將每位老師和每門課分別用一個(gè)點(diǎn)表示，若某位教師能承擔(dān)某門課程的教學(xué)，則將對(duì)應(yīng)的兩個(gè)點(diǎn)連邊。同時(shí)可基于各位老師以往負(fù)責(zé)各門課程的教學(xué)效果，對(duì)這些邊進(jìn)行賦權(quán)。為方便討論，不妨先假設(shè)每位教師都有承擔(dān)這n門課程教學(xué)的能力。此時(shí)，可得到2n個(gè)頂點(diǎn)的賦權(quán)完全二部圖，而此時(shí)課程安排問題便可以看作求賦權(quán)完全二部圖的最大完美匹配問題。

例：某校某學(xué)期要安排五位教師甲、乙、丙、丁、戊承擔(dān)五門課程的教學(xué)任務(wù)。根據(jù)近五年的學(xué)生評(píng)教，統(tǒng)計(jì)出各位教師負(fù)責(zé)相關(guān)課程的平均成績，如下表所示。若以此為依據(jù)安排教學(xué)任務(wù)，如何安排，可使教學(xué)質(zhì)量最好？（假設(shè)每位教師負(fù)責(zé)一門課程的教學(xué)任務(wù)。）

學(xué)生評(píng)教平均成績 課程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

解：首先，將此問題轉(zhuǎn)化為最小完美匹配問題。寫出此問題對(duì)應(yīng)的效益矩陣A，

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

事實(shí)上，我們可以先將矩陣C的各行各列減去相應(yīng)的最小元素，即

因此，我們可以得到如下最優(yōu)方案：教師甲負(fù)責(zé)課程2，教師乙負(fù)責(zé)課程1，教師丙負(fù)責(zé)課程5，教師丁負(fù)責(zé)課程3，教師戊負(fù)責(zé)課程4。此時(shí)總評(píng)教成績?yōu)椋?8+97+97+95+94=481。

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

（2）按照上述方法尋找“0”時(shí)，若在某一步發(fā)現(xiàn)對(duì)應(yīng)的矩陣中含“0”最少的行或列至少含有2個(gè)“0”，則說明最優(yōu)方案并不唯一。我們不妨將上述例題中的數(shù)據(jù)稍作修改：將教師丁負(fù)責(zé)課程3的學(xué)生評(píng)教平均成績由之前的“95”改為“94”。重復(fù)上述過程可得

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

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

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

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

我們可以采用如下方法：

不妨在上述例題中，將教師丙負(fù)責(zé)課程2與課程5的學(xué)生評(píng)教平均成績對(duì)調(diào)，即教師丙負(fù)責(zé)課程1-5的學(xué)生評(píng)教平均成績分別為 92，97，96，93，90。重復(fù)上述過程可得：

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

致謝：

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