選課策略模型論文

1、紹興文理學(xué)院數(shù)學(xué)建模題目:選課策略數(shù)學(xué)模型數(shù)學(xué)系數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)081班學(xué)生 徐貝貝 姚慧 張楚指導(dǎo)老師胡金杰摘要為解決學(xué)生選課問題最優(yōu)解，本文利用 0-1規(guī)劃模型先找出目標(biāo)函數(shù)，再列出約束條件，分三步驟對(duì)最終問題逐層分析化多目標(biāo)規(guī)劃為單目標(biāo)規(guī)劃，分別建立不同的模型，運(yùn)用LINGO軟件求解。從而解決學(xué)生既希望選修課程的數(shù)量少， 又 希望所獲得的學(xué)分多的問題。特點(diǎn)：根據(jù)以上分析，特將模型分為以下四個(gè)(1) 只考慮盡可能多的學(xué)分，而不管所修課程的多少，可建立單目標(biāo)規(guī)劃模型。顯然，這個(gè)問題不必計(jì)算就知道最優(yōu)解是選修全部課程。(2) 在考慮課程最少的情況下，使學(xué)分最多；模型一，選修課的課程最少，不考

2、慮學(xué)分多少；約束條件只有，每人至少學(xué) 習(xí)5門數(shù)學(xué)，2門運(yùn)籌學(xué)，2門計(jì)算機(jī)，1門物理學(xué)，1門經(jīng)濟(jì)學(xué)，2門藝術(shù)類和 先修課的要求建立模型一。模型二：在科目最少的基本前提下，使獲得的學(xué)分盡可能得多，約束條件沒 變，化單目標(biāo)為多目標(biāo)求解。(3) 同時(shí)考慮學(xué)分最多和選修科目最少，并且假設(shè)所占比例三七分。在此假設(shè) 情況下對(duì)模型二稍加調(diào)整形成新的目標(biāo)函數(shù)，最終計(jì)算出結(jié)果。模型三：同時(shí)考慮課程最少和所獲得的學(xué)分最多，并按3:7的重要性建立模型。關(guān)鍵詞0-1規(guī)劃 選修課要求 單目標(biāo)規(guī)劃 多目標(biāo)規(guī)劃一.問題的重述某學(xué)校規(guī)定，運(yùn)籌學(xué)專業(yè)的學(xué)生畢業(yè)時(shí)必須至少學(xué)過五門數(shù)學(xué)課，兩門運(yùn)籌 學(xué)課,兩門計(jì)算機(jī)，一門物理學(xué)，一門

3、經(jīng)濟(jì)學(xué)和兩門藝術(shù)類。這些課程的編號(hào)， 名稱，學(xué)分，所屬類別和選修課的要求如表所示。那么，畢業(yè)時(shí)最少可以學(xué)習(xí)這 些課程中的哪些課程。如果某個(gè)學(xué)生即希望選修課程的數(shù)量最少， 又希望所獲得的學(xué)分最多，他可以 選修哪些課程？課程編號(hào)課程名稱學(xué)分所屬類別先修課要求1微積分5數(shù)學(xué)2數(shù)學(xué)分析5數(shù)學(xué)3實(shí)變函數(shù)4數(shù)學(xué)4泛函分析3數(shù)學(xué)數(shù)學(xué)分析；實(shí)變函數(shù)5線性代數(shù)4數(shù)學(xué)6最優(yōu)化方法4數(shù)學(xué)；運(yùn)籌學(xué)微積分；線性代數(shù)7應(yīng)用統(tǒng)計(jì)4數(shù)學(xué)；運(yùn)籌學(xué)微積分；線性代數(shù)8數(shù)據(jù)結(jié)構(gòu)3數(shù)學(xué)；計(jì)算機(jī)計(jì)算機(jī)編程9操作系統(tǒng)4數(shù)學(xué)；計(jì)算機(jī)10信號(hào)與系統(tǒng)3數(shù)學(xué)；物理學(xué)數(shù)學(xué)分析11風(fēng)險(xiǎn)投資管理2運(yùn)籌學(xué)12預(yù)測(cè)理論4運(yùn)籌學(xué)應(yīng)用統(tǒng)計(jì)13計(jì)算機(jī)模擬3運(yùn)籌學(xué)

4、：計(jì)算機(jī)計(jì)算機(jī)編程14數(shù)學(xué)實(shí)驗(yàn)3運(yùn)籌學(xué)；計(jì)算機(jī)微積分；線性代 數(shù)15西方經(jīng)濟(jì)學(xué)3運(yùn)籌學(xué)；經(jīng)濟(jì)學(xué)16計(jì)算機(jī)編程2計(jì)算機(jī)17VB4計(jì)算機(jī)計(jì)算機(jī)編程18大學(xué)物理5物理學(xué)19物理實(shí)驗(yàn)3物理學(xué)；大學(xué)物理20固體物理學(xué)3物理學(xué)21會(huì)計(jì)學(xué)4經(jīng)濟(jì)學(xué)；22電影藝術(shù)賞析3藝術(shù)23青春期生理衛(wèi)生2藝術(shù)24漢語言文化3藝術(shù)25體育舞蹈3藝術(shù)二符號(hào)說明符號(hào)說明1）xi:表示選修的課程（xi=O 表示不選，xi=1 表示選i=1,2,3,4,5,6,7,8,925）;三模型的假設(shè)1）學(xué)生只要選修就能獲得學(xué)分；2）每個(gè)學(xué)生都必須遵守規(guī)定選修課程；四問題分析。模型一：只考慮課程最少，不考慮學(xué)分，計(jì)算求出結(jié)果。 模型二：既考慮

5、課程最少，又使學(xué)分最多，計(jì)算求出結(jié)果。 模型三：同時(shí)考慮兩者，并考慮二者的權(quán)重，計(jì)算求出結(jié)果。五模型的建立與求解模型一：用xi=1表示選修表中按編號(hào)順序的25門課程（xi=O表示不選；i=1,2,25）.問題的目標(biāo)為選修的課程總數(shù)最少，既min Z=x1+x2+x3+x4+x5+x6+x7+x8+x9+xio+x11+x12+x13+x14+x15+x16+x17+ x18+x19+x20+x21+x22+x23+x24+x25（1）約束條件包括兩個(gè)方面：第一，每個(gè)人每人至少學(xué)習(xí)5門數(shù)學(xué)，2門運(yùn)籌學(xué)，2門計(jì)算機(jī)，1門物理學(xué) 1門經(jīng)濟(jì)學(xué)，2門藝術(shù)類。根據(jù)表中對(duì)每門課程所屬類別的劃分，這一約束可以

6、 表示為x1+x2+x3+x4+x5+x6+x7+x8+x9+x10>=5 (2) x6+x7+x11+x12+x13+x14+x15>=2 (3) x8+x9+x13+x14+x16+x17>=2 (4) x10+x18+x19+x20>=1 (5)x15+x21>=1（ 6）x22+x23+x24+x25>=2（7）第二，某些課程有先修課程的要求。例如“數(shù)據(jù)結(jié)構(gòu)”的先修課是“計(jì)算機(jī)編程”，這意味著如果x8=1,必須想x16=1，這個(gè)可以表示為x8<=x16（注意x8=0 對(duì) x16 沒有影響 ） “泛函分析”先修課是“數(shù)學(xué)分析”和“實(shí)變函數(shù)”的條件

7、可 以表示為 x4<=x2,x4<=x3. 而這兩個(gè)不等式可以用一個(gè)約束表示為 2x4-x2-x3<=0. 這樣，所有課程的先修課要求可表示為如下的約束：2x4-x2-x3<=0（ 8）2x6-x1-x5<=0（ 9）2x7-x1-x5<=0（ 10）x8-x16<=0（11）x10-x2<=0（ 12）x12-x7<=0（ 13）x13-x16<=0（ 14）x14-x1-x5<=0（ 15）x17-x16<=0（ 16）x19-x18<=0（ 17）由上得到以（1）為目標(biāo)函數(shù)、以（ 2）（ 1 7）為約束條件的

8、0-1 規(guī)劃模型。 將這一模型輸入LINGO軟件（見附錄1）,求解得到結(jié)果為x仁x2= x5= x9= x10= x14= x15=x22= x23=1, 其他變量為 0.對(duì)照課程編號(hào)它們是微積分 , 數(shù)學(xué)分析,線 性代數(shù),操作系統(tǒng),信號(hào)與系統(tǒng) ,數(shù)學(xué)實(shí)驗(yàn) ,西方經(jīng)濟(jì)學(xué) ,電影藝術(shù)賞析 ,青春期生 理衛(wèi)生,共9門課程，總學(xué)分為 32.下面我們會(huì)看到，這個(gè)解并不是唯一的，還可以找到與以上不完全相同的 9門 課也滿足所給的約束條件。模型二：如果一個(gè)學(xué)生既希望選修課程少， 又希望所得的學(xué)分盡可能的多， 則除了目 標(biāo)一還可以根據(jù)已知數(shù)據(jù)寫出另一個(gè)目標(biāo)函數(shù)，即Max W=5*x1+5*x2+4*x3+3

9、*x4+4*x5+4*x6+4*x7+3*x8+4*x9+3*x10+2*x11+4 *x12+3*x13+3*x14+3*x15+2*x16+4*x17+5*x18+3*x19+3*x20+4*x21+3*x22+2*x2 3+3*x24+3*x25（ 18）如果模型一得到的結(jié)果是唯一的，則他別無選擇，只能選修上面的 9 門課， 總學(xué)分為32.但是LINGC無法告訴我們一個(gè)優(yōu)化問題的解是否唯一，所以還可能在選修 9 們課的條件下，使總學(xué)分多于 32。為探索這種可能，應(yīng)在上面的規(guī)劃 問題中增加約束x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x1

10、5+x16+x17+x18+x1 9+x20+x21+x22+x23+x24+x25=9（ 19）得到以（ 18）為目標(biāo)函數(shù)、以（ 2） （17）和（ 19）為約束條件的另一個(gè) 0-1 規(guī)劃模型（見附錄 2 ） 。求解后發(fā)現(xiàn)會(huì)得到不同于前面 9 門課程的最優(yōu)解 x1=x2=x5=x9=x10=x14=x15=x22=x24=1,其他變量為0，其中2學(xué)分的“青春期生 理衛(wèi)生”換成了 3學(xué)分的“漢語言文化”，總學(xué)分由 32增至 33.注意這個(gè)模型的 解任然不是唯一的，如 x1=x2=x5=x9=x10=x14=x15=x22=x25=1其他變量為 0, 也是最優(yōu)解。模型三：不像模型一模型二那樣,只

11、考慮課程最少或?qū)W分最多,而是覺得學(xué)分和課程這兩個(gè)目標(biāo)大致應(yīng)該三七開。這時(shí)可以將目標(biāo)函數(shù)Z和-W分別乘以0.7和0.3 ,組成一個(gè)新的目標(biāo)函數(shù)丫，有Min Y=0.7Z-0.3W= （x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x1 8+x19+x20+x21+x22+x23+x24+x25）*0.7-（5*x1+5*x2+4*x3+3*x4+4*x5+4*x6+4*x 7+3*x8+4*x9+3*x10+2*x11+4*x12+3*x13+3*x14+3*x15+2*x16+4*x17+5*x18+3*x 19+3*x2

12、0+4*x21+3*x22+2*x23+3*x24+3*x25）*0.3=-0.8*x1-0.8*x2-0.5*x3-0.2*x4-0.5*x5-0.5*x6-0.5*x7-0.2*x8-0.5*x9- 0.2*x10+0.1*x11-0.5*x12-0.2*x13-0.2*x14-0.2*x15+0.1*x16-0.5*x17-0.8*x 18-0.2*x19-0.2*x20-0.5*x21-0.2*x22+0.1*x23-0.2*x24-0.2*x25（20）得到以（20）為目標(biāo)、以（2）（ 17）為約束的0-1規(guī)劃模型。輸入LINGO求解 （見附錄 3）。得到為x1=x2=x3=x4=x

13、5=x6=x7=x8=x9=x10=x12=x13=x14=x15=x16=x17=x18=x19=x20=x2 2=x24=x25=1,即只有“風(fēng)險(xiǎn)投資管理” “青春期生理衛(wèi)生”沒有選修，共82學(xué)分。六結(jié)果的檢驗(yàn)與分析經(jīng)過檢驗(yàn)輸入式子正確，結(jié)果多次驗(yàn)證一樣。結(jié)果分析： 模型一分析：模型一的結(jié)果為 x1= x2= x5= x9= x10= x14= x15=x22= x23=1 即選修編號(hào)為 1， 2,5,9 ， 10,14,15,22,23 的選修課時(shí)達(dá)到了， 在選修課的課程 最少。最少為 9 門。模型二分析：模型二的結(jié)果為 x1=x2=x5=x9=x10=x14=x15=x22=x24=1

14、即選修編 號(hào)為 1， 2,5,9 ， 10,14,15,22,24 的選修課時(shí)達(dá)到了， 在選修課程最少的情況下， 盡可能的分?jǐn)?shù)最多，最多為 33學(xué)分。模型三分析：課程數(shù)與學(xué)分?jǐn)?shù)按權(quán)重三七分，結(jié)果為 x1=x2=x3=x4=x5=x6=x7=x8=x9=x10=x12=x13=x14=x15=x16=x17=x18=x19=x20=x2 2=x24=x25=1,即只有“風(fēng)險(xiǎn)投資管理” “青春期生理衛(wèi)生”沒有選修，共82學(xué)分。六模型的評(píng)價(jià)與推廣本文運(yùn)用了 0-1 規(guī)劃解決了學(xué)修課選擇的難題，但是還沒有建立滿足不同 需要的學(xué)生，還需要進(jìn)一步的建立模型和計(jì)算。如建立以學(xué)分最多為目標(biāo)的模 型，或建立以課

15、程數(shù)和學(xué)分?jǐn)?shù)等權(quán)重的模型。解決不同的問題。七參考文獻(xiàn)1】姜啟源 謝金星 葉俊，數(shù)學(xué)模型，高等教育出版社， 2003年8月第 3版附錄 1.模型一的求解本文運(yùn)用 LINGO 軟件求解 輸入： min=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18 +x19+x20+x21+x22+x23+x24+x25;x1+x2+x3+x4+x5+x6+x7+x8+x9+x10>=5; x6+x7+x11+x12+x13+x14+x15>=2; x8+x9+x13+x14+x16+x17>=2; x10+x18+x

16、19+x20>=1; x15+x21>=1;x22+x23+x24+x25>=2;2*x4-x2-x3<=0;2*x6-x1-x5<=0;2*x7-x1-x5<=0;x8-x16<=0;x10-x2<=0;x12-x7<=0;x13-x16<=0;2*x14-x1-x5<=0;x17-x16<=0;x19-x18<=0;bin(x1);bin(x2);bin(x3);bin(x4);bin(x5);bin(x6);bin(x7);bin(x8);bin(x9);bin(x10);bin(x11);bin(x12);b

17、in(x13);bin(x14);bin(x15);bin(x16);bin(x17);bin(x18);bin(x19);bin(x20);bin(x21);bin(x22);bin(x23);bin(x24);bin(x25);輸出：Global optimal solution found.Objective value:9.000000Extended solver steps:0Total solver iterations:0VariableValueReduced CostX11.0000001.000000X21.0000001.000000X30.0000001.000000

18、X40.0000001.000000X51.0000001.000000X60.0000001.000000X70.0000001.000000X80.0000001.000000X91.0000001.000000X101.0000001.000000X110.0000001.000000X120.0000001.000000X130.0000001.000000X141.0000001.000000X151.0000001.000000X160.0000001.000000X170.0000001.000000X180.0000001.000000X190.0000001.000000X2

19、00.0000001.000000X210.0000001.000000X221.0000001.000000X231.0000001.000000X240.0000001.000000X250.0000001.000000RowSlack or SurplusDual Pr19.000000-1.00000020.0000000.00000030.0000000.00000040.0000000.00000050.0000000.00000060.0000000.00000070.0000000.00000081.0000000.00000092.0000000.000000102.0000

20、000.000000110.0000000.000000120.0000000.000000130.0000000.000000140.0000000.000000150.0000000.000000160.0000000.000000170.0000000.000000附錄 2.模型二求解本文運(yùn)用 LINGO 軟件求解輸入：Max=5*x1+5*x2+4*x3+3*x4+4*x5+4*x6+4*x7+3*x8+4*x9+3*x10+2*x11+4 *x12+3*x13+3*x14+3*x15+2*x16+4*x17+5*x18+3*x19+3*x20+4*x21+3*x2 2+2*x23+2

21、*x24+3*x25;x1+x2+x3+x4+x5+x6+x7+x8+x9+x10>=5;x6+x7+x11+x12+x13+x14+x15>=2;x8+x9+x13+x14+x16+x17>=2;x10+x18+x19+x20>=1;x15+x21>=1;x22+x23+x24+x25>=2;2*x4-x2-x3<=0;2*x6-x1-x5<=0;2*x7-x1-x5<=0;x8-x16<=0;x10-x2<=0;x12-x7<=0;x13-x16<=0;2*x14-x1-x5<=0;x17-x16<=

22、0;x19-x18<=0;x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+ x19+x20+x21+x22+x23+x24+x25=9 ;bin(x1);bin(x2);bin(x3);bin(x4);bin(x5);bin(x6);bin(x7);bin(x8);bin(x9);bin(x10);bin(x11);bin(x12);bin(x13);bin(x14);bin(x15);bin(x16);bin(x17);bin(x18);bin(x19);bin(x20);bin(x21);bin(x22);

23、bin(x23);bin(x24);bin(x25);輸出：Global optimal solution found.Objective value:33.00000Extended solver steps:0Total solver iterations:0VariableValueReduced CostX11.000000-5.000000X21.000000-5.000000X30.000000-4.000000X40.000000-3.000000X51.000000-4.000000X60.000000-4.000000X70.000000-4.000000X80.000000

24、-3.000000X91.000000-4.000000X101.000000-3.000000X110.000000-2.000000X120.000000-4.000000X130.000000-3.000000X141.000000-3.000000X151.000000-3.000000X160.000000-2.000000X170.000000-4.000000X180.000000-5.000000X190.000000-3.000000X200.000000-3.000000X210.000000-4.000000X221.000000-3.000000X230.000000-

25、2.000000X241.000000-3.000000X250.000000-3.000000RowSlack or Surplus133.000001.00000020.0000000.00000030.0000000.00000040.0000000.00000050.0000000.00000060.0000000.00000070.0000000.00000081.0000000.00000092.0000000.000000102.0000000.000000110.0000000.000000120.0000000.000000130.0000000.000000140.0000

26、000.000000150.0000000.000000160.0000000.000000170.0000000.000000180.0000000.000000Dual Price附錄 3.模型三求解輸入： min=-0.8*x1-0.8*x2-0.5*x3-0.2*x4-0.5*x5-0.5*x6-0.5*x7-0.2*x8-0. 5*x9-0.2*x10+0.1*x11-0.5*x12-0.2*x13-0.2*x14-0.2*x15+0.1*x16-0. 5*x17-0.8*x18-0.2*x19-0.2*x20-0.5*x21-0.2*x22+0.1*x23-0.2*x24-0 .2

27、*x25;x1+x2+x3+x4+x5+x6+x7+x8+x9+x10>=5; x6+x7+x11+x12+x13+x14+x15>=2; x8+x9+x13+x14+x16+x17>=2;x10+x18+x19+x20>=1;x15+x21>=1;x22+x23+x24+x25>=2;2*x4-x2-x3<=0;2*x6-x1-x5<=0;2*x7-x1-x5<=0;x8-x16<=0;x10-x2<=0;x12-x7<=0;x13-x16<=0;2*x14-x1-x5<=0;x17-x16<=0;x19-x18<=0;bin(x1);bin(x2);bin(x3);bin(x4);bin(x5);bin(x6);bin(x7);bin(x8);bin(x9);bin(x10);bin(x11);bin(x12);bin(x13);bin(x14);bin(x15);bin(x16);bin(x17);bin(x18);bin(x19);bin(x20);bin(x21);bin(x22);bin(x23);bin(x24);bin(x25);輸出：-8.500000Global optimal solution found