劉國璧，孫 群

(1.安徽電子信息職業(yè)技術(shù)學(xué)院，安徽 蚌埠 233030;2.安徽大學(xué) 數(shù)學(xué)與計算科學(xué)學(xué)院，合肥 230039)

基于0－1規(guī)劃的高校選課模型

劉國璧1，2，孫 群1，2

(1.安徽電子信息職業(yè)技術(shù)學(xué)院，安徽 蚌埠 233030;2.安徽大學(xué) 數(shù)學(xué)與計算科學(xué)學(xué)院，合肥 230039)

結(jié)合目前高校選課現(xiàn)狀，研究了由0－1規(guī)劃描述的選課模型，利用計算機軟件LINGO進行編程，給出了選課問題的最優(yōu)解，進而獲得該模型的部分最優(yōu)方案。

0－1規(guī)劃;選課模型;LINGO軟件

0 引言

數(shù)學(xué)建模［1］將數(shù)學(xué)知識應(yīng)用于解決實際問題，在數(shù)學(xué)建模的過程中能充分展示數(shù)學(xué)思想和方法的作用。在高等數(shù)學(xué)的教學(xué)中，需要通過引入一些建模方法和案例，展示如何利用所學(xué)數(shù)學(xué)知識解決實際問題的全部過程，使學(xué)生看到數(shù)學(xué)的作用，這既能促進學(xué)生數(shù)學(xué)思想和方法的培養(yǎng)和提高;也能提高學(xué)生學(xué)習(xí)高等數(shù)學(xué)的興趣。數(shù)學(xué)規(guī)劃是數(shù)學(xué)建模中應(yīng)用較為為廣泛的一種數(shù)學(xué)工具，在全國數(shù)學(xué)建模競賽試題中，幾乎每年都會涉及到數(shù)學(xué)規(guī)劃知識，數(shù)學(xué)規(guī)劃可以解決許多實際的問題，比如貨郎擔(dān)問題、指派問題、選擇運動員問題等。所以，在日常的高等數(shù)學(xué)教學(xué)中，可以適當(dāng)?shù)囊胍恍嶋H的問題，通過數(shù)學(xué)建模，利用數(shù)學(xué)規(guī)劃知識來進行解決。

近幾年，很多高校陸續(xù)采用學(xué)分制［2］，有的高校依據(jù)學(xué)分收取學(xué)費，學(xué)生根據(jù)自身情況選擇課程，但是，不合理的選課會增加學(xué)生的選課費用。所以，如何合理的選擇課程，既能為學(xué)生節(jié)約一定的費用;又能讓學(xué)生合理的學(xué)好知識，是一個值得去研究的實際問題［3］。本文利用數(shù)學(xué)規(guī)劃知識研究了大學(xué)生的選課問題，利用LINGO軟件進行編程，獲得了優(yōu)選方案。

1 選課模型的建立與求解

現(xiàn)在，高校的課程類型主要有三種［2］:必修課、限選課和選修課。必修課是必須選上的學(xué)科，而限選課和任選課沒有強制性的要求，學(xué)生可以根據(jù)自己的實際情況和學(xué)校關(guān)于學(xué)分的有關(guān)規(guī)定，自己選擇。我們借助0－1規(guī)劃理論建立選課模型來解決此問題。下面利用某高校學(xué)生的選課實例對選課模型予以說明。

1.1 問題的提出

某高校大學(xué)二年級下學(xué)期開設(shè)選修課，學(xué)生需要科學(xué)合理的進行選擇，既要考慮學(xué)分、課程數(shù)，又要考慮選修費用?？蛇x課程中必修課共7門，共17個學(xué)分;限選課共14門;任選課共15門。

學(xué)校關(guān)于選課的相關(guān)規(guī)定如下:

①總學(xué)分不能少于35學(xué)分;

②至少選1門任選課;

⑧至少選2門限選課;

④必選課的費用為120元/學(xué)分，限選課的費用為54元/學(xué)分，任選課的費用為49元/學(xué)分。

限選課與任選課的學(xué)分數(shù)和要求以及選修課程之間的相應(yīng)信息見表1所示(必修課程沒有列出)。

表1 課程的學(xué)分數(shù)和要求以及先修課程要求信息

針對上述情況，建立0－1規(guī)劃模型解決以上問題。

1.2 建立模型

1.3 模型求解

模型建立具體過程如下:

①以所選學(xué)分總費用最小值作為目標(biāo)函數(shù)z;

②用xi表示是否選修該課程，其中，xi=1表示選修該課程，xi=0表示不選修該課程;③若在選修課程i時必須同時選修j，用xj－xi=0表示;④若在選修課程i前先選修課程j，用xi－xj≥0表示;

⑤若兩門課程不能同時選，用xi+xj≤1表示。

于是，建立如下的0－1規(guī)劃模型:

運行結(jié)果為:x11=x13=x26=x28=1，其他xi=0，即選修4門課程，課程編號分別為11，13，26，28，此時，最低學(xué)費為2962元。

通常情況下，一個0－1規(guī)劃問題的所有最優(yōu)解很難得到，我們可以通過對變量進行約束，進行隱式枚舉，進而得出它的其它的一些選課方案，具體方法是:在上面的LINGO程序中，每次添加約束xi=0或1(i=1，2，…，29)，經(jīng)過58次運算，得到了很多的最優(yōu)選課方案，部分方案如下表2所示:

表2 部分最優(yōu)選課方案

因為必修課、任選課和限選課的每個學(xué)分的費用不同，由上表可以出，要想使學(xué)費最低，在滿足要求的情況下，盡量選擇費用最低的課程，并且所選的總學(xué)分不能超過18個學(xué)分。本文的選課方案中，學(xué)費最低時應(yīng)選修8個學(xué)分的限選課，10個學(xué)分的任選課，總學(xué)費為2962元。

2 結(jié)束語

本文利用0－1規(guī)劃模型［5］對高校學(xué)生選課問題進行了研究，得出了選課的優(yōu)選方案，說明了此選課模型合理可行，并且課程門數(shù)、學(xué)分數(shù)等可以進行調(diào)節(jié)，有效的解決了學(xué)生的選課問題。

［1］ 姜啟源.數(shù)學(xué)模型［M］.北京:高等教育出版社，2002.

［2］ 張鳳至，張純姑.基于0－1整數(shù)規(guī)劃的高校課程優(yōu)選模型［J］.中國教育發(fā)展研究雜志，2008(4):72－74.

［3］ 王若鵬.基于線性不等式組的選課模型［J］.北京石油化工學(xué)院學(xué)報，2003(4):31－33.

［4］ 雍龍泉.基于整數(shù)規(guī)劃的選課模型［J］.伊犁師范學(xué)院學(xué)報，2006(9):128－130.

［5］ 劉壽春.整數(shù)規(guī)劃模型研究［J］.皖西學(xué)院學(xué)報，2004，4(2):6 －8.

0－1 Planning-based College Course Selection Model

LIU Guo-bi1，2，SUN Qun1，2

(1.Anhui Vocational College of Electronics and Information Technology，Bengbu 233030，China;2.School of Mathematics and Computational Science，Anhui University，Hefei 230039，China)

Combining with the present situation of college courses，this paper discusses a selection model described by 0 －1planning，which uses computer software LINGO to program，gives the optimal solution of the problem and gets the partial optimal plan of this model.

0－1 planning;course model;LINGO software

O29

A

1009－3907(2012)08－0966－03

2012-06-21

2011年國家自然科學(xué)基金項目(61073117/F020509);2012年國家自然科學(xué)基金項目(61175046/F030502);2011年安徽省高等學(xué)校自然科學(xué)研究項目(KJ2011Z025);2011年安徽電子信息職業(yè)技術(shù)學(xué)院院級課題(ADZX1102);2012年安徽省高等學(xué)校自然科學(xué)研究項目(KJ2012Z015)

劉國璧(1981-)，男，安徽蚌埠人，講師，碩士，主要從事智能計算、模糊理論、商空間等方面研究。

責(zé)任編輯:程艷艷