基于大學(xué)生選課問題的線性規(guī)劃模型

王茜

【摘要】本文針對(duì)大學(xué)生選課問題，分別以選課門數(shù)最少及所得學(xué)分最多為目標(biāo)，建立雙目標(biāo)線性規(guī)劃模型，采用不同方法分別利用lingo軟件進(jìn)行求解，獲得最優(yōu)方案.

【關(guān)鍵詞】線性規(guī)劃；雙目標(biāo)；權(quán)重；大學(xué)生選課

隨著我國(guó)高校教學(xué)改革的推進(jìn)，大學(xué)生選修課逐步增多，紛繁復(fù)雜的選修課令他們眼花繚亂.如何選擇課程，既要滿足課程間的前后順序和學(xué)校的要求，又要符合自己的興趣且達(dá)到門數(shù)最少.本文利用線性規(guī)劃，針對(duì)選修門數(shù)最少和學(xué)分最多，研究了兩種不同的選課模型，利用lingo程序求解，獲得了最優(yōu)方案.

一、問題的提出

某大三學(xué)生，第一學(xué)期的必修課只有一門（2個(gè)學(xué)分）；可供限定選修的課程有8門，任意選修課程有10門.由于有些課程之間有聯(lián)系，所以可能在選修某門課程時(shí)必須同時(shí)選修其他課程，這18門課程的學(xué)分?jǐn)?shù)和要求以及相應(yīng)信息如下表所示.

按學(xué)校規(guī)定，每名學(xué)生每學(xué)期所修總分不能少于21學(xué)分，因此學(xué)生必須在上述18門課程中至少選修19學(xué)分，學(xué)校同時(shí)還規(guī)定學(xué)生每學(xué)期選修任意選修課的學(xué)分不能少于3學(xué)分，也不能超過6學(xué)分.為了達(dá)到學(xué)校的要求，請(qǐng)為該學(xué)生確定一種選課方案.

二、問題分析

由題意可知，我們首先要確定選哪門課的問題，每門課都有選與不選兩種情況.可引入0-1變量xi，即xi=1，選修第i門課，0，不選第i門課，ci表示第i門課的學(xué)分.學(xué)生選擇選修課時(shí)，考慮選修的門數(shù)越少越好，修得的學(xué)分越多越好.故考慮分別以選修門數(shù)和學(xué)分為目標(biāo)建立模型.

三、模型建立與求解

設(shè)Z表示選修門數(shù)，W表示所修得總學(xué)分.

1.建立模型一

得到結(jié)果x1=1，x2=1，x3=1，x4=1，x11=1，minZ=5，即最小需要選擇5門課程，編號(hào)為1，2，3，4，11.

方案二：由方案1得知，最少選修5門課程.當(dāng)選修課程門數(shù)最少時(shí)，所修得學(xué)分越多越好，則以學(xué)分總數(shù)最大為目標(biāo)，則lingo程序如下：

model：

sets：

kehao/1..18/：x，a；

endsets

data：

a=5，5，4，4，3，3，3，2，3，3，3，2，2，2，1，1，1，1；

enddata

max=@sum（kehao（i）：a*x）；

@sum（kehao（i）：x）=5；

@sum（kehao（i）|i#gt#8：a*x）>=3；

@sum（kehao（i）|i#gt#8：a*x）<=6；

x（1）>=x（5）；x（2）>=x（7）；x（8）>=x（9）；x（6）>=x（10）；

x（4）>=x（11）；x（5）>=x（12）；x（7）>=x（13）；x（6）>=x（14）；

@for（kehao（i）：@bin（x））；

end

得到結(jié)果 x1=1，x2=1，x3=1，x4=1，x11=1，max W=21，即在選修5門課程的基礎(chǔ)上，最多可獲得21學(xué)分，所選課程編號(hào)為1，2，3，4，11.

2.建立模型二

由于學(xué)生的偏好不同，對(duì)選修課門數(shù)與學(xué)分重要性的認(rèn)知不同，考慮對(duì)兩者取權(quán)重，建立新的模型如下：

目標(biāo)函數(shù)：minY=a·∑18i=1xi-b·∑18i-1cixi，

其中a，b為權(quán)重，約束條件同模型一.

利用lingo11.0進(jìn)行求解，程序如下：

model：

sets：

kehao/1..18/：x，c；

endsets

data：

c=5，5，4，4，3，3，3，2，3，3，3，2，2，2，1，1，1，1；

enddata

z1=@sum（kehao（i）：x）；

z2=@sum（kehao（i）：c*x）；

min=a*z1-b*z2；

a=0.8；b=0.2；

@sum（kehao（i）：c*x）>=19；

@sum（kehao（i）|i#gt#8：c*x）>=3；

@sum（kehao（i）|i#gt#8：c*x）<=6；

x（1）>=x（5）；x（2）>=x（7）；x（8）>=x（9）；x（6）>=x（10）；

x（4）>=x（11）；x（5）>=x（12）；x（7）>=x（13）；x（6）>=x（14）；

@for（kehao（i）：@bin（x））；

end

分取權(quán)重（0.7，0.3；0.8，0.2；0.9，0.1）進(jìn)行比較，取權(quán)重a=0.8，b=0.2及a=0.9，b=0.1時(shí)，運(yùn)行結(jié)果x1=1，x2=1，x3=1，x4=1，x11=1，最少選5門課程，最大學(xué)分21分.

四、結(jié)束語

對(duì)比上面兩個(gè)模型，本文針對(duì)大學(xué)生選課問題，設(shè)置0-1變量，以選課門數(shù)最少及所得學(xué)分最多為目標(biāo)，從不同角度，通過設(shè)置雙目標(biāo)以及引入權(quán)重將雙目標(biāo)轉(zhuǎn)化為單目標(biāo)的方法，建立線性規(guī)劃模型，利用lingo軟件進(jìn)行求解，所得結(jié)果相同，即為最優(yōu)方案.雙目標(biāo)模型在生活中的應(yīng)用較為常見，但求解往往較為復(fù)雜，本文引入權(quán)重的思想對(duì)雙目標(biāo)模型進(jìn)行轉(zhuǎn)化，為雙目標(biāo)模型的求解提供了新的思路.

【參考文獻(xiàn)】

[1]韓中庚.數(shù)學(xué)建模方法及其應(yīng)用[M].北京：高等教育出版社，2009.

[2]姜啟源，謝金星，葉俊.數(shù)學(xué)模型[M].北京：高等教育出版社，2003.

[3]肖華勇.實(shí)用數(shù)學(xué)建模與軟件應(yīng)用[M].西安：西北工業(yè)大學(xué)出版社，2008.