期末考試監(jiān)考安排 數(shù)學(xué)建模論文.doc

2012年河南科技大學(xué)數(shù)學(xué)建模競賽選拔承 諾 書我們仔細閱讀了數(shù)學(xué)建模競賽選拔的規(guī)則.我們完全明白，在做題期間不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊外的任何人研究、討論與選拔題有關(guān)的問題。我們知道，抄襲別人的成果是違反選拔規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。我們鄭重承諾，嚴格遵守選拔規(guī)則，以保證選拔的公正、公平性。如有違反選拔規(guī)則的行為，我們將受到嚴肅處理。我們選擇的題號是（從A/B/C中選擇一項填寫）： A 隊員簽名 ：1. 谷勝輝 2. 高健人 3. 任娟 日期： 2012 年 8 月 16 日2012年河南科技大學(xué)數(shù)學(xué)建模競賽選拔編 號 專 用 頁評閱編號（評閱前進行編號）：評閱記錄（評閱時使用）：評閱人評分備注期末考試監(jiān)考安排摘 要期末考試安排是教務(wù)管理中一項重要而復(fù)雜的工作。傳統(tǒng)的手工安排方式效率低，現(xiàn)考慮利用建立數(shù)學(xué)模型與人工相結(jié)合的方法來分析研究監(jiān)考問題。從已給問題的布局，構(gòu)思出以下方案：首先采用枚舉法分析得出十八種合理的時間分配方案，利用Lingo軟件優(yōu)化得出最優(yōu)時間分配組合。鑒于考場容量有限和考試安排時間最短的考慮，在考試時間與考試課程之間建立一個線性規(guī)劃模型，并利用Lingo軟件進行優(yōu)化求解，得出考試時間的最優(yōu)分配方案。另以最大考場利用率為目標，在有限的考場容量基礎(chǔ)上，在考試課程與考場之間建立一個0-1規(guī)劃模型，利用Lingo軟件進行優(yōu)化求解，得出考場分配的優(yōu)化方案。其次以每位監(jiān)考老師監(jiān)考場數(shù)盡量平均為目標，在監(jiān)考老師監(jiān)考場數(shù)的限制的基礎(chǔ)上，在監(jiān)考老師的分配問題上建立一個0-1規(guī)劃模型，利用Lingo軟件優(yōu)化求解，得出教師的優(yōu)化分配方案。最后依據(jù)平均考場容量的利用率來判斷模型的好壞，模型檢驗得出平均考場容量的利用率均達到90%以上。但針對于實際情況來講平均考場容量利用率高并不一定最優(yōu)，同時需要對模型求得的結(jié)果進行一定的人工改進，建議各院系的教務(wù)人員在監(jiān)考安排中采用數(shù)學(xué)模型與實際相結(jié)合的方法。本文對問題的解決原則：在合理簡化的基礎(chǔ)上，對題目的每個要求，都做到“有數(shù)學(xué)依據(jù)，有理論支撐，力求完善”。關(guān)鍵詞：枚舉法、線性規(guī)劃模型、0-1規(guī)劃模型、Lingo軟件問題重述1. 背 景 每學(xué)期期末，各院系教務(wù)人員都要針對學(xué)校教務(wù)處下達的考試任務(wù)進行監(jiān)考教師的安排，傳統(tǒng)的手工安排方式效率低且容易出錯。我們想從數(shù)學(xué)方面分析該問題，以期能給各院系教務(wù)人員有所幫助，假設(shè)某學(xué)院期末考試現(xiàn)有的監(jiān)考教師、考試課程、各專業(yè)及人數(shù)、教室情況如下：（1） 考試時間一天分三個時間段：上午 8：0011:45下午 14:2017:30晚上 19:4521:20 一個教室前后2門課程的考試時間間隔不能少于20分鐘。 周一周日都可以安排考試。 期末考試開始時間為2013年1月6日。（2）監(jiān)考教師 共有80為監(jiān)考教師，分別是A1，A2，A3 A80，監(jiān)考教師分為3種情況。情況1：A1A10是教授，學(xué)校規(guī)定教授監(jiān)考不能超過2場；情況2：A11A20是有特殊情況的教師，其監(jiān)考不能超過3場；情況3：A21A80教師的監(jiān)考場數(shù)沒有限制。每個考場需要2位監(jiān)考教師。 在安排監(jiān)考的時候要保證各種情況下的教師監(jiān)考場數(shù)盡量平均。（3）考試課程共有100門考試課程，分別是B1，B2， B100，考試課程分為3種情況。情況1：B1B20，考試時間需要60分鐘； 情況2：B21B80，考試時間需要90分鐘；情況3：B81B100，考試時間需要120分鐘。（4）參加考試各專業(yè)，人數(shù)，所學(xué)課程 共有50個專業(yè)，分別是C1，C2， C50。各專業(yè)的人數(shù)，參加考試的課程見附件1的excel表格。假設(shè)每個專業(yè)內(nèi)的學(xué)生所選的課程一致。 （5）能夠作為考場的教室情況 共有50個教室可供選擇，分別是D1，D2，D3 D50，教室分為3種情況。情況1：D1D15，可以容納30 人考試；情況2：D16D40，可以容納45人考試；情況3：D41D50，可以容納60人考試。 2.問 題：（1）假設(shè)不能出現(xiàn)合考的情況，即不能把2門不同的課程放在同一考場一起考試。學(xué)校想要在最短的時間內(nèi)考完所有課程，求出期末考試的最短時間。并做出期末考試的考場安排表，表格可以為excel或者word格式。（2）如果允許合考的情況，及可以把不同的課程放到同一考場考試，其他條件不變，求出期末考試的最短時間。并做出期末考試的考場安排表。（3）為了便于學(xué)生的期末復(fù)習(xí)，學(xué)校規(guī)定每個專業(yè)一天只能考試一門課程，并且老師一天最多監(jiān)考2場，2場考試不能在同一時間段，其他條件不變，求出期末考試的最短時間。并做出期末考試的考場安排表。（4）請給各院系教務(wù)人員安排期末監(jiān)考的一些建議，評價一下你的模型的優(yōu)缺點。問題分析由于考試分為上午、下午、晚上三個時間段，考試課程的考試時間又分為60分鐘、90分鐘、120分鐘三種情況，所以首先應(yīng)該確定在各個時間段的考試課程的分配情況，合理的考試時間方案應(yīng)滿足除考試時間剩余時間不能超過某門課程的考試時間，且對于一個教室前后2門課程的考試時間間隔不能少于20分鐘，應(yīng)用枚舉法列出所有的合理考試時間方案，共十八種，如下表一所示：表一 合理考試時間方案表時間段上午/分鐘下午/分鐘晚上/分鐘方案一60,60,6060,9090方案二60,60,6060,9060方案三60,60,6012090方案四60,60,6012060方案五60,60,6060,6090方案六60,60,6060,6060方案七120,6060,9090方案八120,6060,9060方案九120,6012090方案十120,6012060方案十一120,6060,6090方案十二120,6060,6060方案十三90,9060,9090方案十四90,9060,9060方案十五90,9012090方案十六90,9012060方案十七90,9060,6090方案十八90,9060,6060之后再考慮監(jiān)考老師的分配問題，受監(jiān)考老師人數(shù)的限制每場考試最多安排四十個考場進行考試，對于問題二，在允許合考的情況下應(yīng)充分利用考場的資源，從而使考試時間盡可能的短。對于問題三，由于學(xué)校規(guī)定每個專業(yè)一天只能考試一門課程，所以應(yīng)讓考試課程最多的專業(yè)每天都能考一門，這樣才能盡早的考完。模型假設(shè)1.假設(shè)對于含有同一門課程的專業(yè)，在該課程考試時含有該課程的專業(yè)同時考試；2.所有考生都按時到場考試；3.所有考場的考試都正常進行；符號說明b：表示課程編號，a=1,2，100；c：表示專業(yè)編號，c=1,2，50；d：表示教室編號，也即考場編號，d=1,2，50；i：表示考試模式編號，i=1,2，18；：表示第d個考場的容量；：表示第b門課程是否在t時間段考試（是為1，否為0）；：表示第b門課程的人數(shù)；：表示采用第i種考試模式所用的天數(shù)；：表示第d個考場采用第i種考試模式；:表示安排所有考試的時間段集合，=1,2,3,4,5,6；：表示第a位教師在t時間段是否監(jiān)考d考場（是為1，否為0）；：表示在t時間段d考場是否使用（是為1，否為0）；：表示在t時間段課程b是否在d考場考試（是為1，否為0）；：表示第c個專業(yè)是否有課程b（是為1，否為0）；：表示安排考試的時間段，T=1,2，12； 模型的建立與求解問題一 在不能出現(xiàn)合考的情況下求解：1. 模型建立（1） 考試時間的分配假設(shè)未對有特殊限制的監(jiān)考教師分配監(jiān)考任務(wù)，因為沒有特殊限制的監(jiān)考教師有60人，每個考場需要兩位監(jiān)考教師，所以同一個時間段最多有30個考場進行考試，為了保證參加考試的人數(shù)盡可能的多，這30個考場我們?nèi)镈21-D50（其中D21-D40容量為45人，D41-D50容量為60人），即每場考試可同時容納1500人進行考試，分別根據(jù)60分鐘、90分鐘、120分鐘總?cè)藬?shù)不能超過考場容納人數(shù)的限制，可得如下線性規(guī)劃模型：其中目標函數(shù)為，表示采用第i種考試模式所用的天數(shù)。（2） 考場安排首先引進0-1變量表示在t時間段課程b是否在d考場考試（是取1，否取0），d=1,2，50。再引入0-1變量表示第b門課程是否在t時間段考試（是為1，否為0），并令。由于在t時間段d考場可能用也可能不用，于是再引進0-1變量表示在t時間段d考場是否使用（是為1，否為0），其中。由于目標是使在t時間段考場的利用率盡可能的高，也即所有考場的余量盡可能的少，所以目標函數(shù)為。因為每門課程都要有考場，時間段t內(nèi)考場d內(nèi)的考生總數(shù)不能超過考場的總?cè)萘?，所以可以建立如下整?shù)線性規(guī)劃模型： 其中目標函數(shù)為（3） 監(jiān)考教師的安排監(jiān)考教師的安排是一個分配問題，為了解決該問題先引入0-1變量表示第a位教師在t時間段是否監(jiān)考d考場（是為1，否為0）。由于一個監(jiān)考教師在一個時間段至多只能在一個考場監(jiān)考，所以在t時間段第a位教師至多只能在一個考場監(jiān)考，即。因為情況一的監(jiān)考教師要求監(jiān)考的場數(shù)不能超過2場，所以。因為情況二的監(jiān)考教師要求監(jiān)考的場數(shù)不能超過3場，所以。因為每個考場的監(jiān)考教師為2人，表示在t時間段d考場是否使用（是為1，否為0），則在t時間段第d個考場安排的監(jiān)考教師應(yīng)滿足。要保證各種情況下的教師監(jiān)考場數(shù)盡可能平均，只需使監(jiān)考次數(shù)最多的教師與監(jiān)考次數(shù)最少的教師的差值最小即可，即，于是監(jiān)考教師安排的數(shù)學(xué)模型如下：目標函數(shù)為2. 模型求解（1） 考試時間的分配模型求解用lingo求解，程序見附錄一，結(jié)果顯示分別采用考試模式7、13、15的考試天數(shù)為0.937、0.609、0.430，共計1.976天。（2） 考場安排模型求解由于我們上述假設(shè)未對有特殊限制的監(jiān)考教師分配監(jiān)考任務(wù)，并且未將剩余的20個考場安排考試。再采用人工安排考場，充分利用剩余的考場容量合理分配將（1）的結(jié)果整數(shù)化2天即可。用lingo求解，編寫的程序如下附錄三所示由于運行結(jié)果過于龐雜在此不再顯示，考試安排詳細結(jié)果見附表一。問題二 在允許合考的情況下，在問題一的基礎(chǔ)之上求出期末考試的最短時間1.模型的建立由于受監(jiān)考教師人數(shù)的限制，在同一個時間段最多可以有40個考場考試，因此在允許合考的情況下應(yīng)充分利用考場D16-D50，使考場容量盡可能的大。因而在問題一的基礎(chǔ)之上加上下述條件即可：（1） 考試時間的分配在問題一的基礎(chǔ)之上，為了盡可能充分的利用監(jiān)考教師資源，有特殊情況的監(jiān)考教師也要進行監(jiān)考，由于考試時間為90分鐘的課程較多，為了盡可能的增加每場考試的容量將監(jiān)考教師A1-A20分配給課程B21-B80進行監(jiān)考，以縮短考試時間，約束條件如下：綜上可建立如下優(yōu)化模型：其目標函數(shù)為（2） 考場安排在問題一考場安排的基礎(chǔ)上建立如下的模型： 其目標函數(shù)為（3） 監(jiān)考教師的安排在問題一監(jiān)考教師的安排的基礎(chǔ)上建立如下的模型：其目標函數(shù)為3. 模型求解（1） 考試時間的分配模型求解用lingo求解，程序見附錄二，結(jié)果顯示分別采用考試模式7、13、15的考試天數(shù)為1.009、0.465、0.357，共計1.831天。我們得出考試時間共用2天，根據(jù)問題一的解法求解，在此不再贅述，具體結(jié)果見附表二。問題三 規(guī)定每個專業(yè)一天只能考試一門課程，并且老師一天最多監(jiān)考2場，2場考試不能在同一時間段，其他條件不變，求期末考試的最短時間1. 模型的建立（1） 考試時間的分配設(shè)為第c個專業(yè)第b門課程的考試時間，其中，為了使期末考試時間安排盡可能平衡，以便使學(xué)生可以更好地發(fā)揮，只要使同一專業(yè)不同考試課程最小的時間間隔盡可能的大即可，于是建立如下目標函數(shù)：因為每個專業(yè)一天至多考一門，所以，又因為對于相同課程不同專業(yè)的考試時間相同，即。綜上所述可以建立如下模型：目標函數(shù)為（2） 考場安排、監(jiān)考教師安排考場安排、監(jiān)考教師安排模型同問題一中的考場安排、監(jiān)考教師安排。2. 模型求解用lingo求解，方法同問題一，在此不再贅述，具體結(jié)果見附表三。模型評價對于本問題，我們采用平均考場利用率來對模型進行評價，平均考場的利用率越高說明模型越好。設(shè)平均考場利用率為表示一天內(nèi)各個時間段所有考場容量的利用率的平均值，則計算方法如下：經(jīng)過對問題一到三的考試安排進行計算可知平均考場的利用率都在90%以上，在這里不再一一計算。雖然模型都是按照在最短時間內(nèi)考完所有的課程進行計算的，但其計算結(jié)果僅是個理論值，在實際的期末考試監(jiān)考安排時上述模型得出的結(jié)果并不一定為最優(yōu)，在實際的期末考試監(jiān)考安排時應(yīng)該將模型與實際情況相結(jié)合，這樣才能達到最優(yōu)的效果。各院系的工作人員在對期末考試監(jiān)考安排時，為了達到良好的效果應(yīng)先根據(jù)模型進行計算再在得出的結(jié)果的基礎(chǔ)上進一步根據(jù)實際情況做必要的改動，這樣勢必會減少工作人員的工作量，而且可以達到良好的效果，使考試安排更為合理。這樣教師和同學(xué)都會對考試的安排感到滿意，使考試可以順利圓滿的進行。參考文獻1謝金星，薛毅.優(yōu)化建模與Lindo/Lingo軟件，天津大學(xué)出版社，20052數(shù)學(xué)建模與應(yīng)用，國防工業(yè)出版社3姜啟源，葉俊.數(shù)學(xué)模型（第三版），高等教育出版社附錄附錄一min=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18;1500*(4*x1+5*x2+3*x3+4*x4+5*x5+6*x6+2*x7+3*x8+x9+2*x10+3*x11+4*x12+x13+2*x14+x16+2*x17+3*x18)=3725;1500*(2*x1+x2+x3+x5+2*x7+x8+x9+x11+4*x13+3*x14+3*x15+2*x16+3*x17+2*x18)=8400;1500*(x3+x4+x7+x8+2*x9+2*x10+x11+x12+x15+x16)=2050;x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x180;Global optimal solution found. Objective value: 1.975926 Infeasibilities: 0.000000 Total solver iterations: 3 Model Class: LP Total variables: 18 Nonlinear variables: 0 Integer variables: 0 Total constraints: 5 Nonlinear constraints: 0 Total nonzeros: 77 Nonlinear nonzeros: 0 Variable Value Reduced Cost X1 0.000000 0.1111111 X2 0.000000 0.2222222 X3 0.000000 0.1111111 X4 0.000000 0.2222222 X5 0.000000 0.2222222 X6 0.000000 0.3333333 X7 0.9370370 0.000000 X8 0.000000 0.1111111 X9 0.000000 0.000000 X10 0.000000 0.1111111 X11 0.000000 0.1111111 X12 0.000000 0.2222222 X13 0.6092593 0.000000 X14 0.000000 0.1111111 X15 0.4296296 0.000000 X16 0.000000 0.1111111 X17 0.000000 0.1111111 X18 0.000000 0.2222222 Row Slack or Surplus Dual Price 1 1.975926 -1.000000 2 0.000000 -0.7407407E-04 3 0.000000 -0.1481481E-03 4 0.000000 -0.2222222E-03 5 1.975926 0.000000附錄二min=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18;1500*(4*x1+5*x2+3*x3+4*x4+5*x5+6*x6+2*x7+3*x8+x9+2*x10+3*x11+4*x12+x13+2*x14+x16+2*x17+3*x18)=3725;1500*(2*x1+x2+x3+x5+2*x7+x8+x9+x11+4*x13+3*x14+3*x15+2*x16+3*x17+2*x18)+975=8400;1500*(x3+x4+x7+x8+2*x9+2*x10+x11+x12+x15+x16)=2050;x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x180; Global optimal solution found. Objective value: 1.831481 Infeasibilities: 0.000000 Total solver iterations: 3 Model Class: LP Total variables: 18 Nonlinear variables: 0 Integer variables: 0 Total constraints: 5 Nonlinear constraints: 0 Total nonzeros: 77 Nonlinear nonzeros: 0 Variable Value Reduced Cost X1 0.000000 0.1111111 X2 0.000000 0.2222222 X3 0.000000 0.1111111 X4 0.000000 0.2222222 X5 0.000000 0.2222222 X6 0.000000 0.3333333 X7 1.009259 0.000000 X8 0.000000 0.1111111 X9 0.000000 0.000000 X10 0.000000 0.1111111 X11 0.000000 0.1111111 X12 0.000000 0.2222222 X13 0.4648148 0.000000 X14 0.000000 0.1111111 X15 0.3574074 0.000000 X16 0.000000 0.1111111 X17 0.000000 0.1111111 X18 0.000000 0.2222222 Row Slack or Surplus Dual Price 1 1.831481 -1.000000 2 0.000000 -0.7407407E-04 3 0.000000 -0.1481481E-03 4 0.000000 -0.2222222