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

劉國(guó)璧，孫 群

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

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

劉國(guó)璧1，2，孫 群1，2

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

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

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

0 引言

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

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

1 選課模型的建立與求解

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

1.1 問(wèn)題的提出

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

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

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

②至少選1門任選課;

⑧至少選2門限選課;

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

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

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

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

1.2 建立模型

1.3 模型求解

模型建立具體過(guò)程如下:

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

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

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

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

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

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

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

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

2 結(jié)束語(yǔ)

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

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

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

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

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

［5］ 劉壽春.整數(shù)規(guī)劃模型研究［J］.皖西學(xué)院學(xué)報(bào)，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年國(guó)家自然科學(xué)基金項(xiàng)目(61073117/F020509);2012年國(guó)家自然科學(xué)基金項(xiàng)目(61175046/F030502);2011年安徽省高等學(xué)校自然科學(xué)研究項(xiàng)目(KJ2011Z025);2011年安徽電子信息職業(yè)技術(shù)學(xué)院院級(jí)課題(ADZX1102);2012年安徽省高等學(xué)校自然科學(xué)研究項(xiàng)目(KJ2012Z015)

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

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