數(shù)學(xué)建模-選課問題

選課問題小組成員：李橋鴿李嘉儀陳清珂一、摘要大學(xué)生在學(xué)習(xí)中常會(huì)遇到選課問題，既要使自己所選擇的課程符合自己的興趣，又要用最少的課程到達(dá)最好的效果，最重要是滿足學(xué)校所修課程的要求以到達(dá)畢業(yè)，有些課程必須在具備根底科目學(xué)習(xí)經(jīng)歷的前提下才能進(jìn)行選擇，，在這多種因素引導(dǎo)下選課過程往往發(fā)生矛盾。因此只有對(duì)各種因素進(jìn)行周密考慮，最終方可得出最優(yōu)化的結(jié)果。選課所得到的結(jié)果必然為整數(shù)，因此此題可以可歸結(jié)為整數(shù)線性規(guī)劃的最優(yōu)化問題。二．問題重述某學(xué)校規(guī)定，其運(yùn)籌學(xué)專業(yè)的學(xué)生想要畢業(yè)，就至少要修過兩門數(shù)學(xué)課，三門運(yùn)籌學(xué)課和兩門計(jì)算機(jī)課。而其備選課程供有9種，按1到9編號(hào)，都有其各自對(duì)應(yīng)的學(xué)分，以及對(duì)于先修課程的要求。在滿足題設(shè)要求的前提下，提出問題：1.學(xué)生畢業(yè)時(shí)最少可以學(xué)習(xí)哪些課程；2.學(xué)生選擇哪些課程可以使自己選修的課程數(shù)量少而所獲總學(xué)分多？3.對(duì)課程數(shù)目和學(xué)分具不同的比例偏好的人，如何選擇？(以偏好比例課程數(shù)比總學(xué)分=7：3為例)三、問題分析

根據(jù)題目要求，學(xué)生選修課程必須同時(shí)滿足以下條件：〔1〕任何一個(gè)學(xué)生所選擇的所有課程中，至少應(yīng)包括兩門屬于數(shù)學(xué)類的課程，三門屬于運(yùn)籌學(xué)類的課程以及兩門屬于計(jì)算機(jī)類的課程；〔2〕課程編號(hào)為3、4、5、6、8、9的六門課選修前都必須先學(xué)過其他幾門課。要選3號(hào)或5號(hào)、9號(hào)課程就必須先學(xué)1、2號(hào)課程，要選4號(hào)或6號(hào)課程就必須先學(xué)7號(hào)課程，要學(xué)8號(hào)課程就必須先學(xué)5號(hào)課程。因此，針對(duì)目標(biāo)一，要求所選符合上述要求的課程數(shù)量最少，我們選擇了以下方案首先選擇1,2再選擇課程5,8，其次選擇課程課程7,6；如此來看這樣只用選擇六個(gè)課程就可以完成所也需要的要求，粗略的估計(jì)出選擇1,2,5,8,7,6這幾個(gè)課程是最好的結(jié)果；針對(duì)目標(biāo)二，要求選擇的符合要求的課程數(shù)量最少的同時(shí)其累計(jì)學(xué)分最多，我們也認(rèn)為這個(gè)方案可以獲得的學(xué)分為22分即是最好的結(jié)果。但這都是主觀上的判斷，難免有偏差。由于此題研究的是選課過程的最優(yōu)化結(jié)果，因此首先必須根據(jù)所給條件，分析出各個(gè)課程之間的關(guān)系，并用清晰的數(shù)學(xué)表達(dá)式描述。因此，我們建立0-1型整數(shù)線性規(guī)劃模型，對(duì)結(jié)果進(jìn)行分別預(yù)測(cè)后通過Matlab求解多目標(biāo)規(guī)劃模型，并將之前預(yù)測(cè)結(jié)果和求解結(jié)果進(jìn)行比擬，得到選課結(jié)果的最優(yōu)化組合。四．模型假設(shè)假設(shè)各個(gè)同學(xué)在選修課程中不受其他因素影響，只受學(xué)分和課程門數(shù)影響。假設(shè)學(xué)生選課時(shí)已經(jīng)提前到達(dá)了先修課要求，如在選“最優(yōu)化方法”時(shí)已經(jīng)考慮帶先選了“微積分”和“線性代數(shù)”。假設(shè)學(xué)生的信息是不公開的，且學(xué)生選課不受其他同學(xué)的影響，根據(jù)自己的需求進(jìn)行選課。各個(gè)同學(xué)可以選課數(shù)目最少并且能夠獲得最高的學(xué)分，到達(dá)以較少課時(shí)換取較高學(xué)分的要求。假設(shè)在選課過程中選課都能選上，且能一次性通過該課程的考核并獲得相應(yīng)的學(xué)分。五．變量及符號(hào)說明1.Xi表示選課表中第i門課程的選擇2.Xi=1〔0〕表示選修〔不選〕題目表中編號(hào)順序的9門課程的第i門3.minZ表示選課中獲得的最低學(xué)分4.maxw表示選課中獲得的最高學(xué)分5.第三問中：Z選課數(shù)量，M:學(xué)分多少，Y為學(xué)分?jǐn)?shù)和課程數(shù)的綜合目標(biāo)令xi=1代表選修課程號(hào)為i的課程xi=0代表不選擇選修課程號(hào)為i的課程六．模型建立與求解〔一〕問題一：用xi=1(0)表示選修(不選)按上表中編號(hào)順序的9門課程的第i門課.問題①?zèng)Q策目標(biāo)為選修課程門數(shù)最少,即minz=j=19xi.即minz=x1+x2+x3+x4+x5+x6+x7+x8+x9;其約束條件包括：首先,每人最少要選2門數(shù)學(xué)課,3門運(yùn)籌學(xué)課和2門計(jì)算機(jī)課,其次,某些課有先修課的要求,例如,數(shù)據(jù)結(jié)構(gòu)的先修課是計(jì)算機(jī)編程,這意味著x4=1蘊(yùn)涵x7=1,這個(gè)條件可表示為x4x7或x4-x70.同理,最優(yōu)化方法的先修課是微積分和線性代數(shù)的條件可表示為x3x1,x3x2,此二式可合并為一個(gè)不等式，2x3x1+x2；綜上，按表中課程類別劃分可將此約束表示為x1+x2+x3+x4+x5≥2;x3+x5+x6+x8+x9≥3;x4+x6+x7+x9≥2;x1+x2-2x3≥0;x1+x2-2x5≥0;x7-x4≥0;x7-x6≥0;x5-x8≥0;x1+x2-2x9≥0;xi=0or1(i=0,…,9);將其轉(zhuǎn)化為matlab標(biāo)準(zhǔn)型為:minz=x1+x2+x3+x4+x5+x6+x7+x8+x9;-1-1-1-1-10000X1-200-10-1-10-1-1X2-3000-10-1-10-1X3-2-1-12000000X40000100-100X5≦0-1-10020000X60000001-100X700000100-10X80-1-10000002X90Matlab程序及結(jié)果：>>z=[5,4,4,3,4,3,2,2,3];f=[1;1;1;1;1;1;1;1;1];a=[1,1,1,1,1,0,0,0,0;0,0,1,0,1,1,0,1,0;0,0,0,1,0,1,1,0,1;1,1,-2,0,0,0,0,0,0;1,1,0,0,-2,0,0,0,0;0,0,0,-1,0,0,1,0,0;0,0,0,0,0,-1,1,0,0;0,0,0,0,1,0,0,-1,0;1,1,0,0,0,0,0,0,-2];b=[2;3;2;0;0;0;0;0;0];[x,y]=bintprog(f,-a,-b,[],[]);x,y,c=z*xOptimizationterminated.x=110011110y=6c=20由屏幕最后顯示結(jié)果得:最優(yōu)解x1=x2=x5=x6=x7=x8=1,x3=x4=x9=0目標(biāo)函數(shù)最小值z(mì)=6。即應(yīng)該選修微積分,線性代數(shù),應(yīng)用統(tǒng)計(jì),計(jì)算機(jī)模擬,計(jì)算機(jī)編程,預(yù)測(cè)理論等6門課,最小選課門數(shù)是6,獲得學(xué)分為20.問題二：數(shù)學(xué)模型為：約束條件根本類似于問題一，但在二中我們將選擇的六門課程作為固定指標(biāo)，看是否存在更優(yōu)的選擇在選課少的情況下，使得目標(biāo)函數(shù)總學(xué)分最大化。maxw=5x1+4x2+4x3+3x4+4x5+3x6+2x7+2x8+3x9;x1+x2+x3+x4+x5≥2;x3+x5+x6+x8+x9≥3;x4+x6+x7+x9≥2;x1+x2-2x3≥0;x1+x2-2x5≥0;x7-x4≥0;x7-x6≥0;x5-x8≥0;x1+x2-2x9≥0;x1+x2+x3+x4+x5+x6+x7+x8+x9=6;xi=0or1(i=0,…,9);將其轉(zhuǎn)化為matlab標(biāo)準(zhǔn)型為:minw’=-(5x1+4x2+4x3+3x4+4x5+3x6+2x7+2x8+3x9);-1-1-1-1-10000X1-200-10-1-10-1-1X2-3000-10-1-10-1X3-2-1-12000000X40000100-100X5≦0-1-10020000X60000001-100X700000100-10X80-1-10000002X90X1X2X3X4(111111111)X5≒6X6X7X8X9Matlab程序及結(jié)果：>>f=[5;4;4;3;4;3;2;2;3];a=[1,1,1,1,1,0,0,0,0;0,0,1,0,1,1,0,1,0;0,0,0,1,0,1,1,0,1;1,1,-2,0,0,0,0,0,0;1,1,0,0,-2,0,0,0,0;0,0,0,-1,0,0,1,0,0;0,0,0,0,0,-1,1,0,0;0,0,0,0,1,0,0,-1,0;1,1,0,0,0,0,0,0,-2];b=[2;3;2;0;0;0;0;0;0];aeq=[1,1,1,1,1,1,1,1,1];beq=[6];[x,y]=bintprog(-f,-a,-b,aeq,beq);x,y=-yOptimizationterminated.x=111011100y=22由屏幕最后顯示結(jié)果得:最優(yōu)解x1=x2=x3=x5=x6=x7=1,x4=x8=x9=0在同樣選擇六門課的前提下，目標(biāo)函數(shù)最大值z(mì)=22.也就是最大學(xué)分為22分。故應(yīng)按此種方法進(jìn)行選課。由上述兩個(gè)問題得出的結(jié)果可以看出，22學(xué)分的課程組合與20分的課程組合相比是用課程3-最優(yōu)化方法替換了課程8-預(yù)測(cè)理論，是因?yàn)樗鼈兌紝儆谶\(yùn)籌學(xué)范疇，不同的是課程3同時(shí)屬于數(shù)學(xué)范疇，并且學(xué)分多于課程8.而沒有在第一問求解中就選擇課程3也是因?yàn)樗淼念悇e多于課程8，相對(duì)于選修課程最少這一條件，它顯然不是最優(yōu)的。故而我們認(rèn)為所作出的結(jié)果是合理的，與前期預(yù)測(cè)也較相符。〔三〕問題三：對(duì)學(xué)分?jǐn)?shù)和課程數(shù)加權(quán)形成一個(gè)目標(biāo)，如三七開。最優(yōu)解：x1=x2=x3=x4=x5=x6=x7=x9=1，其它為0總學(xué)分28七、拓展八．模型評(píng)價(jià)本文研究了選課問題的最優(yōu)化選擇，充分考慮了實(shí)際情況，不失一般性，我們討論了多種課程選擇分配的方案并對(duì)每一種方案進(jìn)行了預(yù)算通過課程的數(shù)量比照以及可以獲得的學(xué)分的總和比照最終選擇出一個(gè)選課數(shù)量最少且獲得學(xué)分最多的方案，建立了0-1型整數(shù)線性規(guī)劃模型，對(duì)結(jié)果進(jìn)行分別預(yù)測(cè)后通過Matlab求解多目標(biāo)規(guī)劃模型，并將