蔡禮淵

【摘要】 當(dāng)前中國(guó)高校在教育改革中推行了學(xué)分制，而基于完全學(xué)分制選課的算法研究，對(duì)提高學(xué)生的學(xué)習(xí)積極性和學(xué)校的教學(xué)管理水平有著極其重要的意義.

【關(guān)鍵詞】 完全學(xué)分制；數(shù)學(xué)；模型

隨著高等教育改革的不斷深化，學(xué)分制的推行和選課管理成為其必要內(nèi)容之一，建立基于完全學(xué)分制選課的數(shù)學(xué)模型具有十分重要的意義.

一、模型設(shè)計(jì)構(gòu)想

完全學(xué)分制選課是采集學(xué)生上課需求，調(diào)配教學(xué)資源滿足需求的“多元約束”數(shù)學(xué)模型.在“多元約束”模型里可以定義一個(gè)三元信息組{X，D，A}.其中X={x1，x2…xn}是一個(gè)有限的變量集合，每一個(gè)xi的取值對(duì)應(yīng)一個(gè)非空值域Dxi={d1，d2…dN}.C是有限的約束集合.解多元約束問(wèn)題的辦法就是找出在C約束范圍下的最優(yōu)解Xi.

二、建立數(shù)學(xué)模型

（一）模型元素構(gòu)建

教學(xué)班：Course_Class（CC）.教學(xué)管理部門通常會(huì)根據(jù)選修學(xué)生人數(shù)和教師、教室等資源情況將選課學(xué)生劃分成為一個(gè)或多個(gè)教學(xué)班.教學(xué)班：CC={課程，選課集合，課程容量，任課教師，周學(xué)時(shí)，教室需求，其他略}.CC在模型中是最基本的變量集合.選課信息：SS，指學(xué)生基本的選課信息.定義為SS={學(xué)生，選擇課程，優(yōu)選教師}.教學(xué)時(shí)間：Time，指最高排課時(shí)間.教室：Room，指提供給授課使用的場(chǎng)所以及附帶設(shè)備的統(tǒng)稱.定義為Room={類型，大小，數(shù)量}.約束：指使得選課數(shù)據(jù)能滿足排課要求的約束條件.約束1：有前提課程的選課必須滿足.約束2：學(xué)期最高學(xué)分限制.正常學(xué)生由于精力的制約選擇的課程學(xué)習(xí)量總和是有限制的.約束3：相近課程的學(xué)習(xí).約束4：學(xué)生周課時(shí)限制.約束5：教師的周課時(shí)限制.約束6：同一時(shí)間的教室使用量受教室資源的控制.約束7：周教學(xué)時(shí)間有限.約束8：盡量高地提高選課滿意度.

（二）模型的構(gòu)建和算法的選擇

已知數(shù)學(xué)模型的基本元素，得到多元約束問(wèn)題中的基本變量集合X={x1，x2，…，xn}，也就是模型中的 A nn.同時(shí)，有了基本約束條件A.通過(guò)約束條件A，找出 A nn的值域集合D中最大滿足學(xué)生選課要求和能夠排課的解.其中第1、2、3、4、5條約束是很好滿足的，而第6、7、8條約束只在第一次選課和教學(xué)任務(wù)的安排中無(wú)法得出結(jié)論.當(dāng)?shù)玫降谝淮芜x課結(jié)果后學(xué)校進(jìn)行教學(xué)任務(wù)的統(tǒng)籌，給定人數(shù)太少不能開(kāi)課的課程及合并選擇人數(shù)不夠的課程后，確定教學(xué)班CC={課程，選課集合，課程容量，任課教師，周學(xué)時(shí)，教室需求，其他略}.

如何滿足約束條件5、6、7得到最佳的解.通過(guò)教學(xué)任務(wù)的確定已知應(yīng)有多少個(gè)教學(xué)班，教學(xué)班約束矩陣 A nn的階數(shù)，n得到確認(rèn).讓教學(xué)班約束矩陣 A nn中的每一個(gè)元素aij盡量小.aij小了代表課程與課程的沖突小，排課時(shí)不可排的概率更低.在這里使用聚合算法進(jìn)行分配.聚合算法變量說(shuō)明，如果有A教師的B課程有N名學(xué)生需求，開(kāi)出了不止一個(gè)教學(xué)班，那么就需要進(jìn)行分班.

1.n1表示A教師B課程的X名學(xué)生將被分成的教學(xué)班個(gè)數(shù).

2.n2表示A教師B課程每個(gè)教學(xué)班的學(xué)生人數(shù)上限.

3.N表示選了該門課程的學(xué)生人數(shù).

4.n3表示N名學(xué)生的選課總門數(shù).

5.aik表示第i名學(xué)生選了第k門課程，aik∈{0，1}.

6.ykj表示把選了第k門課程的學(xué)生分到第j個(gè)班，這是一個(gè)決策變量，

目的是使分到第j個(gè)班的學(xué)生選其他課程的 門數(shù)盡量集中.于是有了目標(biāo)函數(shù)minZ=∑ n1 e=1 ∑ n2 j=1 |yj-ye| ；st ∑ N i=1 aik ·ykj≤n2；yj=∑ n3 k=1 ykj為分班人數(shù)限制.第j個(gè)班由選了ji門課的學(xué)生組成，只需要構(gòu)建一個(gè)函數(shù)使得它滿足上述的要求就能使教學(xué)班約束矩陣 A nn中的每一個(gè)元素aij盡量的小.

再引入一個(gè)量稱為閥值，閥值指給定的一個(gè)值，只要aij大于這個(gè)值就認(rèn)為第i門課程和第j門課程沖突不能同時(shí)排課，aij小于這個(gè)值時(shí)認(rèn)為可以排課.有了閥值后，凡aij大于閥值的置為1，小于等于的置為0，aii置為0.得到了一個(gè)新的矩陣 B nn， B nn是一個(gè)主對(duì)角線為0、元素為0，1的主對(duì)角線對(duì)稱簡(jiǎn)單矩陣.

在不考慮課程周學(xué)時(shí)和教室的基礎(chǔ)上， B nn矩陣的秩就是可以排課的最小時(shí)間和.同理，只要 B nn矩陣的秩小于學(xué)校的最大排課時(shí)間，那么不管排課結(jié)果的好壞都一定能進(jìn)行排課.接下來(lái)加入課程的周學(xué)時(shí)，構(gòu)造一個(gè)輔助矩陣 D i，i指的是第i門課程， D i是主對(duì)角線0，1矩陣， D i的階數(shù)m是課程一周最多上課節(jié)數(shù)，1的數(shù)量為i課程的周學(xué)時(shí).用 D i替換 B nn中為1的部分得到了一個(gè)新的n×m階主對(duì)角線為0、主對(duì)角線對(duì)稱的0，1稀疏矩陣 C ，在這里稱之為判定矩陣.只要 C 秩小于等于學(xué)校允許排課時(shí)間的總量，就認(rèn)為在不考慮教室的情況下一定能排出課表.

三、小 結(jié)

本文探索分析了選課管理系統(tǒng)的相關(guān)技術(shù)，對(duì)系統(tǒng)中的一些關(guān)鍵技術(shù)的實(shí)現(xiàn)方法進(jìn)行了研究，并以數(shù)學(xué)模型的形式闡述了該系統(tǒng)的實(shí)現(xiàn)方式，對(duì)于提高學(xué)校的教學(xué)管理水平有著十分重要的意義.

【參考文獻(xiàn)】

[1]Geetanjali Arora Balasubramaniam Aiaswamy Nit.C#專業(yè)項(xiàng)目實(shí)例開(kāi)發(fā)[M].北京：中國(guó)水利水電出版社，2007.

[2]劉楊，等.突破C#編程實(shí)例五十講[M].北京：中國(guó)水利水電出版社，2002.