【正文】 last = college_select[college_course 1]。 j++) stu_cour[j + num_gonggong] = college_select[j]。 j++){ if(temp[j] != 0) stu_cour[j] = temp[j]。 i++) { col_sel(i)。如果嘗試使用這些算法，可能會得到更好的結果。這為提出更好的方案提供了思路：如果將這種震蕩細化到每天，可能會提出令教師和學生更為滿意的方案。我們建立的模型將這個問題進行拆分并各個擊破，使用計算機模擬驗證了模型的有效性，并通過試驗提出了較為合理的方案?；谝陨嫌懻撐覀兛梢詫ξ宸N安排考試的方案進行評估了。則對于這個學生，他的考試安排均勻程度 該學生的滿意度為根據(jù)我們的樣本進行計算發(fā)現(xiàn)這個的值太?。考墸?，因此采用作為滿意度的計算結果。假設滿意度與均勻程度線性相關。根據(jù)以上兩條假定確定監(jiān)考教師的總人數(shù)及其組成，并按模型中指明的算法為每個教師分配監(jiān)考場次。（1）、先考大面積課程，再考其余課程前10個時間段安排的是10門大面積課程；后面自多至少安排其余時間段的考試。按照我們的約定，編號的范圍是1~300。程序運行后給出的部分結果如下：考試的時間段組合及教室分配（部分）…… …… 131 4 large: 3 middle: 0 small: 1 71 3 large: 3 middle: 0 small: 0 31 3 large: 2 middle: 0 small: 1 21 3 large: 2 middle: 0 small: 129 152 4 large: 3 middle: 1 small: 0 112 4 large: 2 middle: 2 small: 0…… ……（注：第28和第29時間段的部分考試。運行程序，所得的案例如下所示（部分）：程序生成的學生的選課情況（部分）3 10 2 9 11 12 13 265 290 3 10 2 9 11 12 14 13 210 177 ……1 3 2 10 21 22 25 178 244 1 3 2 10 21 22 27 25 214 271 1 3 2 10 21 22 29 30 217 186 ………… 數(shù)字代表所選課程編號。6　 根據(jù)上述說明，可選課程總數(shù)是300門，它們都將在期末進行考試。每個學院人數(shù)各不相同，構成一個以250為首項，10為公差的等差數(shù)列。五. 模型求解及模型檢驗（一）模型使用的案例的獲得為了更好地檢驗模型是否有效、可行，首先需要一個接近實際的待安排案例。如果有，就將他分配在此考場，并將其已監(jiān)考次數(shù)加1。至此，各門考試科目的教室安排和時間安排都已經(jīng)確定。那么，順序分配是將考試時間段依次安排到時間點10……上；橫向分配則是將考試時間段依次安排到時間點1232……上。（2）、先考大容量時間段，再考小容量時間段即將所有時間段按其包含的考生總數(shù)由多到少排序，再按此順序排滿整個日程表。我們設計了如下幾種方案，并將在第五部分“模型檢驗”中確定最佳者。（） 說明：近似認為一天當中的5個時間段間隔均勻，而第一天的最后一次與第二天的第一次考試時間間隔是一天之內兩次考試間隔的4倍。分配時應該遵循的原則有： 每天安排5個時間段，每一個時間段都應安排考試，不留空白。如對于大教室， + 1。算法的目標是實現(xiàn)對于課程，安排最少的教室，并且在此前提下使考場中空置的位置最少，即合理利用。對每一組考試，用不等式（2）進行檢驗，若不滿足，則將其拆分為總參加考試人數(shù)近似相等的兩組。這樣，我們就確定了需要多少個時間段完成考試，以及每一個時間段包括哪些考試。3　 實現(xiàn)算法的程序中，我們用零一矩陣（對稱陣）表示圖。這時，X與Y一起構成一個更高階的完全圖，從而可以合并為一個新節(jié)點。（4）針對其他要求及程序實現(xiàn)的一些問題的說明1　 用程序實現(xiàn)算法（3）時必須注意的是合并節(jié)點X和Y的過程。6　 刷新圖后轉①。2　 圖是否有邊存在，沒有則算法結束。解為：AB可同時考，DE可同時考，CF可同時考圖2. 圖1的補圖（3）逆著色問題的解決算法由考試安排問題按節(jié)點逆著色構建的簡單無向圖，其節(jié)點的度數(shù)反映了對應科目和其它科目組合到一起的難易程度。于是考試最少需要安排的場次等于圖H的逆色數(shù)。（2）問題1轉化為圖節(jié)點著色問題問題1可轉化為一個圖節(jié)點著色問題：G = (V，E)，其中V(G) = {C1，C2...，Cn}，每一條邊CiCj(CiCj∈E)的兩個端點Ci和Cj表示某一位同學的兩門考試課程。而G的逆色數(shù)是指G逆著色數(shù)k的最小值。（1）圖節(jié)點著色問題1　 圖節(jié)點著色問題定義[圖的著色問題]圖G的一個圖節(jié)點著色是指k種顏色1，2，...，k對于G 的各節(jié)點的 一個分配，使得任意兩個相鄰的節(jié)點分配以不同的顏色。（二）模型設計1. 分配各門考試的時間。3. 分配各門考試的時間。 對方案使學校滿意的定義： 使考試持續(xù)的總時間盡量短；設計的安排方案應該簡便易行，不致過于繁復，難以實現(xiàn)。為了做到這一點，我們在決定考試日程方案時總是考慮把考生更多的時間段放在前面。 對教室分配合理的理解：在安排每門考試時，以占用教室數(shù)最少為原則；在此基礎上，使對于每間考場，空置的位置最少。為使問題明確，我們對幾個要求的理解如下：216。這是基于假設2“一個學校的學生選課情況足夠交錯復雜以致能排在同一時間的考試科目不會過多”的。學?？荚囍写嬖谌昙壌蟛糠謱W生都修讀的大面積課程例如大學英語、微積分等。本文通過運用圖論中的著色算法確?？荚嚐o沖突，并遵循時間盡量短的原則。3. 教室有大、中、小三種規(guī)模?？紤]到實際的高校規(guī)模，這個建模問題只有在做到用計算機進行大樣本仿真處理的情況下才算得到真正意義上的解決：手工安排顯然是難以完成的。這些問題在大面積課程, 如高等數(shù)學和線性代數(shù)的考試，和一些全校性的選修課的考試時非常明顯。為了檢驗模型的科學性與可行性，我們設計了一個選課程序，使得可以利用計算機對大批量學生的選課情況進行模擬，以得到一個較為接近實際的選課總表。第九屆華東地區(qū)大學生數(shù)學建模邀請賽論文高校大規(guī)?？荚嚨陌才欧桨竷?yōu)化摘要本文對高校大規(guī)模考試的合理安排問題進行了研究和探討。為了滿足2和4，我們將討論幾種考試時間分配方案并從中得到令學生、老師以及學校都滿意的最優(yōu)者。關鍵字：考試安排 逆著色算法 滿意度一. 問題重述由于高校的在校學生的增多，學校在安排期終考試時總會碰到各種難題，如不能錯開學生的各門課的考試時間，監(jiān)考教師不足，或學生參加考試時間過于集中。歸納起來欲解決的問題有：1. 必須保證不會出現(xiàn)同一學生有兩門考試時間沖突；；2. 合理利用容量不同的考場；3. 安排應盡量合理，使學生、教師和學校都滿意。2. 一個學校的學生選課情況足夠交錯復雜以致能排在同一時間的考試科目不會過多，且用作考場的教室在大面積課程錯開的前提下數(shù)量充足。三. 符號說明：第門課程：監(jiān)考教師的數(shù)量：大型教室可容納的考生人數(shù)：中型教室可容納的考生人數(shù)：小型教室可容納的考生人數(shù)：第個考試時間段：考試總天數(shù)：學生滿意度：教師滿意度四. 問題分析及模型建立（一）問題分析容易看出錯開各個學生的考試時間是安排方案的前提要求：存在學生考試時間沖突的考試安排方案無疑是失敗的。這樣一來，考試安排時可以以考試科目作為其區(qū)分的唯一