面試問題論文doc

1、承諾書我們仔細(xì)閱讀了中國大學(xué)生數(shù)學(xué)建模競賽的競賽規(guī)則.我們完全明白， 在競賽開始后參賽隊員不能以任何方式 （包括電話、電子郵件、網(wǎng)上咨詢等）與隊外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的,如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料） ，必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競賽規(guī)則，以保證競賽的公正、 公平性。如有違反競賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號是（從 A/B/C/D 中選擇一項填寫） ：E我們的參賽報名號為（如果賽區(qū)設(shè)置報名號的話）：所屬學(xué)院 （請?zhí)顚懲?/p>

2、整的全名） ：自動化學(xué)院參賽隊員(打印并簽名 ) ：1.祁冰露2.劉健濱3.李玉杰日期：2009 年 8月21日評閱編號(教師評閱時填寫) ：學(xué)生面試中的教師分組問題探討摘要本文研究了在保證面試工作公平性的情況下，使用計算機(jī)搜索、逐步修正等方法，解決了在 N 一定的條件下，所需教師數(shù)量的最小值 M，并建立 0-1 整數(shù)規(guī)劃模型和多目標(biāo)優(yōu)化模型， 應(yīng)用貪婪法求解模型給出具體的分組情況，最后對模型進(jìn)行了評價并提出改進(jìn)方法。問題一：要解決在給定條件下，求出應(yīng)聘教師最小值問題。只要求出教師 M 與面試學(xué)生 N 的關(guān)系表達(dá)式即可。文中針對題目要求及目標(biāo)建立了單目標(biāo)規(guī)劃模型。為了確定M和 N 的關(guān)系， 我

3、們將教師任意四人分成一組，共有 C 4 M 種不同組合，各組排列按照第一個老師 >第二個老師 >第三個老師 > 第四個老師的優(yōu)先順序進(jìn)行升序或降序排列，再利用計算機(jī)從這組排列中進(jìn)行搜索比較，如果兩組中相同的老師數(shù)超過我們規(guī)定的最大值，則將后面的一組刪除，如此循環(huán)下去，直到搜索結(jié)束。另外，不斷改變M（最小取4）的值，即可求出對應(yīng)的最大面試學(xué)生數(shù)N。但是，教師編碼排序規(guī)則的不同，會直接影響輸出值N，所以，文中設(shè)計四種教師編碼排序規(guī)則，分別編程求解出四組不同的數(shù)據(jù)，根據(jù)四組數(shù)據(jù)對不滿足條件的點(diǎn)進(jìn)行修正，得到最優(yōu)數(shù)據(jù)組。最后，分別對最優(yōu)數(shù)據(jù)組進(jìn)行高斯函數(shù)和多項式擬和，選擇一種誤差較小

4、的擬和方案。 最后得到滿足“沒有兩個教師相同”和“沒有三個教師相同”要求下 M與 N 的關(guān)系表達(dá)式分別為：N 23.63 e N 23.69 e( M38.47 )2 20.5(M 417.8)2 232.65.701e10.95e( M4.897)2 4.186( M 155)2 125.7M15. 552()8.876 e11.28( M 45.49)25.91 e46. 38。問題二：要求在滿足一定條件下，建立學(xué)生與面試?yán)蠋熤苯雍侠淼姆峙淠Ｐ?，給出具體分配方案，并對方案進(jìn)行合理性分析。文中建立了教師與學(xué)生組合分配的多目標(biāo)規(guī)劃模型。求解模型時，通過設(shè)置約束（面試組）的優(yōu)先級別，確定優(yōu)化目標(biāo)

5、，并利用貪婪算法對模型求解，最后給出M與 N的“面試組”方案（詳見附表1）。問題三：要做的是在新加條件（面試?yán)蠋熚睦砀靼耄幻课粚W(xué)生接受兩位文科和兩位理科教師的面試）下，解決問題一和問題二。本問在問題一模型的基礎(chǔ)上，對約束條件稍加修改，得到新的0-1整數(shù)規(guī)劃模型。解決問題二，也是在問題二的結(jié)論上進(jìn)行修改。將問題進(jìn)一步簡化，即從已分配好的“面試組”中挑選出滿足新條件的組合（兩奇兩偶），對余下組合，重新分配，這樣就大大減少了計算量。最后，本文在面試公平性的條件下給出題目以外的合理建議，并對模型進(jìn)行了客觀評價。 關(guān)鍵字 計算機(jī)搜索；數(shù)值擬合；0-1 整數(shù)規(guī)劃；貪婪法.1一. 問題的重述自國家教育局實(shí)施

6、高校自主招生以來，各地高校陸續(xù)采用自主招生的模式進(jìn)行錄取新生。自主招生還處于探索階段，很多方面還不夠完善，正在進(jìn)一步發(fā)展?？忌ㄟ^考試等綜合素質(zhì)的考核后，還要經(jīng)過教師面試，決定是否錄取，這樣就會出現(xiàn)考生與面試?yán)蠋熤g分配的均勻性和面試公平性問題。某高校采用通過專家面試的方式進(jìn)行自主招生, 經(jīng)過初選合格進(jìn)入面試的考生有N 人，擬聘請老師M 人進(jìn)行面試。每位學(xué)生要分別接收“面試組”每位老師的單獨(dú)面試，每個面試組由4 名老師組成，各位老師獨(dú)立對考生進(jìn)行提問并根據(jù)學(xué)生回答問題的情況給予評分。為了保證面試工作的公平性，組織者提出如下要求：Y1：每位老師面試的學(xué)生數(shù)量應(yīng)盡量均衡；Y2：面試不同考生的“面試

7、組”成員不能完全相同；Y3:兩個考生的“面試組”中有兩位或三位老師相同的情形盡量的少；Y4：任意兩位老師面試的兩個學(xué)生集合出現(xiàn)相同學(xué)生的人數(shù)盡量的少。本文要解決下面四個問題：問題一：設(shè)考生數(shù) N 已知，要求在滿足條件二的情況下，說明聘請老師數(shù) M至少分別應(yīng)為多大，才能做到任兩位學(xué)生的“面試組”都沒有兩位以及三位面試?yán)蠋熛嗤那樾?。問題二：根據(jù)條件一至條件四的要求建立學(xué)生與面試?yán)蠋熤苯雍侠淼姆峙淠Ｐ停?并就 N=379 ，M=24 的情形給出每位老師面試學(xué)生名單的具體分配方案，并分析該方案滿足條件一至條件四的情況問題三：假設(shè)面試?yán)蠋熤欣砜婆c文科的老師各占一般，并且要求每位學(xué)生接收兩位文科與兩位理

8、科老師的面試，在此假設(shè)下分別回答問題一與問題二。問題四： 討論考生與面試?yán)蠋熤g分配的均勻性和面試公平性的關(guān)系。為了保證面試的公平性，除了組織者提出的要求外，還有哪些因素需要考慮進(jìn)來，并給出新的分配方案或建議。二 . 模型的假設(shè)1. 假設(shè)每位學(xué)生分別單獨(dú)接受四位老師的面試；2. 假設(shè)面試時老師之間是獨(dú)立進(jìn)行互不影響；3. 假設(shè)每位考生只有一次面試的機(jī)會；4.假設(shè)假設(shè)考生的人數(shù)為N，老師的人數(shù)為M， NCM4 ；5. 假設(shè)所有老師和學(xué)生都嚴(yán)格遵守分配方案；6. 假設(shè)假設(shè)每個老師對待每個學(xué)生都是公正的。三 . 符號說明符號含義備注M表示參加面試的老師人數(shù)N表示參加面試的學(xué)生人數(shù)2xijWjqi ,

9、 j , kpi , j , kQijPjkTijH ijF總F1F2w1w2e1e2AB為 0-1 變量，當(dāng) xij =1 時表示 第 j 個老師面試第 i 個學(xué)生時，表示被 第 j 個老師面試的學(xué)生的個數(shù)為 0-1 變量， 當(dāng) q1 時，表示第 i 個和第 j 個學(xué)i , j ,k生都被第 k 個老師面試為 0-1 變量，當(dāng) pi , j , k1 時，表示 老師 j 、 k 面試都學(xué)生 i學(xué)生 i 和 j 的面試組中含有相同老師的個數(shù)老師 j 、 k 面試相同學(xué)生的個數(shù)為 0-1變量，當(dāng) Tij1時，表示 學(xué)生 i 和 j 的面試組中含有相同老師的個數(shù)分別為2為 0-1變量，當(dāng) H ij

10、1時，表示學(xué)生 i 和 j 的面試組中含有相同老師的個數(shù)分別為 3 考生面試的總成績考生面試的理科成績考生面試的文科成績考生理科成績占的權(quán)重考生文科成績占的權(quán)重非線性擬和結(jié)果平均誤差非線性擬和結(jié)果平均誤差全部為奇數(shù)的編碼組合全部為偶數(shù)的編碼組合模型一問題二問題二問題二問題四問題四問題四問題四問題四問題一問題一問題三問題三四 . 問題分析4.1 問題題干的分析面試在自主招生中扮演著越來越重要的角色，考生面試的成績不容忽視。因此如何確定面試專家的分配方案，使錄取工作真正公平合理的進(jìn)行，是各大高校積極考慮的問題。本文要解決的是在公平、均衡的情況下對面試?yán)蠋熯M(jìn)行合理分配。這是一個優(yōu)化問題，所以我們考慮

11、到用目標(biāo)規(guī)劃模型來解決問題一和問題二，問題三可以根據(jù)問題一二稍加修改即可以解決。規(guī)劃模型中的目標(biāo)函數(shù)和約束條件，我們可以根據(jù)將題目中的約束條件、變量和求解目標(biāo)轉(zhuǎn)化為數(shù)學(xué)表達(dá)式，這樣就構(gòu)成了目標(biāo)規(guī)劃模型。最后要做的是求解模型，可以考慮用遺傳算法、極大極小法、理想點(diǎn)法等進(jìn)行模型求解。4.2 問題一的分析問題一要求的是在學(xué)生數(shù)N 已知，且滿足面試不同考生的“面試組”3成員不能完全相同的情況下，計算聘請老師數(shù) M 至少分別應(yīng)為多大，才能做到任兩位學(xué)生的“面試組”都沒有兩位以及三位面試?yán)蠋熛嗤那樾巍栴}一相對較簡單，是一個單目標(biāo)規(guī)劃問題。只要把題目要求的決策變量和約束條件轉(zhuǎn)化成數(shù)學(xué)表達(dá)式，就可以得到目

12、標(biāo)規(guī)劃模型的約束條件和目標(biāo)函數(shù)。由于教師數(shù)M 、學(xué)生數(shù) N 均未知，因此無法求出最少教師數(shù)目或最多學(xué)生數(shù)目。因此考慮應(yīng)用枚舉法（取部分?jǐn)?shù)據(jù)），列出 M 值求出對應(yīng)的最優(yōu)學(xué)生數(shù)N，此步應(yīng)用計算機(jī)編程實(shí)現(xiàn)。最后對所得數(shù)據(jù)進(jìn)行函數(shù)擬合，即可得到面試學(xué)生數(shù)N 與所需最少教師M 的函數(shù)表達(dá)式。4.3 問題二的分析問題二與問題一類似，只是多出了條件Y1和 Y4 ，是一個多目標(biāo)最優(yōu)化問題。條件Y1 （每位老師面試的學(xué)生數(shù)量應(yīng)盡量均衡）作為模型二的約束條件；條件Y4（任意兩位老師面試的兩個學(xué)生集合出現(xiàn)相同學(xué)生的人數(shù)盡量的少）讓求的是盡量最優(yōu)問題，因此可以作為目標(biāo)函數(shù)。我們可以在模型一的基礎(chǔ)上，增加一個約束條件

13、，增加一個目標(biāo)，這樣就建立一個新的多目標(biāo)優(yōu)化模型。我們把“面試組”分為四類，分別為：沒有一個教師相同的情形；有一個教師相同；有兩個教師相同；有三個教師相同，且優(yōu)先級逐次降低。求解模型時，我們采用貪婪法思想編程，按照四種“面試組”的優(yōu)先級順序，分別從 C 4 M 中教師組合中，搜索出面試學(xué)生數(shù)目的“面試組”。至此，對 M=24 ， N=379 進(jìn)行合理公平的分配基本完成。4.4 問題三的分析問題三和問題二相比，增加了新的約束條件“文理科教師各占一半”和“每 位學(xué)生 分別 接受兩位 文科兩 位理 科教師的 面試”。我們假設(shè)1 、3M 1的編碼代表文科教師， 2、 4、 6M 的編碼代表理科教師（M

14、為偶數(shù)的前提下） 。新的條件下解決問題一：只是在模型中加入“文理科教師各占一半”和“每位學(xué)生分別接受兩位文科兩位理科教師的面試”的約束條件，其余做法和模型一完全相同。新條件下解決問題二：將問題轉(zhuǎn)化成數(shù)學(xué)語言，就是我們所求出的所有 378 的教師組合中，必須含有兩個奇數(shù)和兩個偶數(shù)。本問可以直接在模型二結(jié)果的基礎(chǔ)上求解。第一步，挑選出不符合“兩奇、兩偶”的組合；第二步， 將不符合條件的組合相互之間重新安排分配組合，這樣就組成378組“最多有兩個教師相同”的分配方案；第三步，第379 位同學(xué)的“面試組”可以從24 位教師中任選4 位，這樣就會出現(xiàn)5 為同學(xué)的“面試組”有“三個教師相同”的情形。最后對

15、新的分配方案進(jìn)行條件Y1Y4 的合理性分析。4.5 問題四的分析借鑒問題 13 的求解過程及結(jié)果，針對面試面試均勻性與公平性的關(guān)系，給出幾點(diǎn)可行建議，以避免出現(xiàn)面試過程不公平現(xiàn)象的產(chǎn)生。五 . 模型的建立和求解45.1 問題 1 模型的建立及其求解本問題解決的是滿足一定約束條件要求，計算在給出一定的學(xué)生人數(shù)下，所需要教師的最少人數(shù)。我們把這個實(shí)際問題抽象為目標(biāo)規(guī)劃模型的數(shù)學(xué)問題來求解。根據(jù)實(shí)際情況分析，一般面試學(xué)生的個數(shù)要遠(yuǎn)大于教師的個數(shù)。因為教師人數(shù)較少，容易進(jìn)行分組（即按照約束條件將教師每四人分成一組），滿足約束條件的情況下， 所能組合的最大組數(shù)目即可面試學(xué)生的最大人數(shù)。因此，我們改變優(yōu)化

16、變量，當(dāng)教師數(shù)目M 一定的情況下最多可面試的學(xué)生個數(shù)，即求 max N 。5.1.2 沒有兩位老師相同的情形5.1.2.1 模型 1.1的建立（1）設(shè) xi j代表第 j 個老師面試第 i 學(xué)生， xi j 0 表示第 j 個老師不面試第 i 個學(xué)生， xi j1表示第 j 個老師面試第 i 個學(xué)生，用數(shù)學(xué)語言表達(dá)即：第j 個老師面試第 i 個學(xué)生1,（ xi j 為 0 1 變量）。xij0,第j 個老師不面試第 i 個學(xué)生（2）每個學(xué)生只能接受四名老師面試，轉(zhuǎn)化成數(shù)學(xué)表達(dá)式為：Mxik 4(i 1, 2 ,N,。)k 1（3）任意兩位學(xué)生的“面試組”不能有兩個老師相同的情形，轉(zhuǎn)化為M，其中

17、 k 表示第 k 個老如下數(shù)學(xué)表達(dá)式：xik x jk 1(ij; i, j 1,2, ,N )k1師， xi k 、 x j k 是 0 1 變量。通過以上 3 步的模型準(zhǔn)備，針對“沒有兩個老師相同的情形”可建立如下單目標(biāo)規(guī)劃模型 1.1：max N(1)Mxik x jk 1 (i j; i, j 1,2, , N )(2)k 1Mst.xik4(i 1,2, , N )(3)k 1xik, x j k0或1（是 0-1變量）(4)5.1.2.2 模型 1.1 的求解由于 M 是未知數(shù)，所以沒有辦法使用優(yōu)化算法求出具體的N 值，這里我們采用數(shù)值模擬的方法，通過列舉一定的 M 值，求出相應(yīng)的

18、最優(yōu)的N 值，然后通過曲線擬合的方法求出M 和 N 的近似表達(dá)式，從而求出考生數(shù)為N時，至少需要聘請的老師數(shù)M 。列舉 M 值，求相應(yīng)的最優(yōu)的N 值，針對此模型我們設(shè)計了尋優(yōu)算法，此步可以通過 Matlab 編程實(shí)現(xiàn)，程序的算法由以下步驟實(shí)現(xiàn)：Step1：首先對 M 位教師每四人一組進(jìn)行組合，求出所有組合項為CM4 ，把所有項按遞增方式排列成序列S0 ；5Stsp2：從 S0 第一項開始，逐次掃描后面所有項，如果后面項同第一項有兩個或超過數(shù)字相同的就將其刪除，這樣形成了一個新的序列S1 ；Step3：從 S1 的第二項開始，逐次掃描后面所有項，如果后面項同第二項有兩個或超過兩個數(shù)字相同的就將其

19、刪除， 這樣形成了一個新的序列 S2 ，然后從 S2 的第三項開始，逐次掃描后面所有項，如果后面項同第三項有超過兩個數(shù)字相同的就將其刪除，這樣形成了一個新的序列S3 ，依次類推，直到搜索完成。注：考慮到問題二有讓求解24 位教師的面試分配情況，在此，我們只列舉出 4 24 位教師，所能面試的最大學(xué)生數(shù)。將24 位教師分別編號為1、 2、324；學(xué)生分別編號為1、2、 3N。通過 Matlab 軟件編程實(shí)現(xiàn)（見附錄程序1），所得數(shù)據(jù)如表1：表 1 不能有兩個教師相同的情況教師（M） 4567891011121314學(xué)生（ N） 1112233691311教師（M） 151617181920212

20、22324學(xué)生（ N） 13151720212426303335從表 1 得到的數(shù)據(jù)看，當(dāng)教師從13 位增加到 14 時，所能面試的學(xué)生的最大人數(shù)不增加，反而變小了（本文將這種數(shù)稱為“特殊數(shù)”）。這說明算法陷入局部最優(yōu)， 即不能按照表1 數(shù)據(jù)進(jìn)行教師數(shù)M 與學(xué)生數(shù) N 的數(shù)值擬和，局部最優(yōu)擬和出的結(jié)果會產(chǎn)生很大的殘差，致使擬和結(jié)果誤差較大。因此我們將表 1 數(shù)據(jù)進(jìn)行修正， 即將 14 個教師所能面試的最大學(xué)生數(shù)改為13 個教師所能面試的學(xué)生數(shù)13。M 值對應(yīng)的最大我們知道，當(dāng)教師編號按照不同規(guī)則排序，列舉出的N 會不同。所以，本文為得到最優(yōu)結(jié)果或使計算結(jié)果逼近最優(yōu)值，利用 Matlab編程分別

21、求出教師編號按照不同規(guī)則排序情況下，一定數(shù)量教師M 對應(yīng)能面試的最多學(xué)生數(shù)N 值。然后對每組數(shù)據(jù)都按照上述方法進(jìn)行修正，最后可以得到一組最優(yōu)值，即每一個M 值，對應(yīng)能得到真實(shí)的最大N 值。四種教師編碼排序規(guī)則如下：C1：第一個老師編號遞增, 第二個老師編號遞增, 第三個老師編號遞增 ,第四個老師編號遞增；C2：第一個老師編號遞增 , 第二個老師編號遞增 , 第三個老師編號遞增 , 第四個老師編號遞減；C3：第一個老師編號遞增 , 第二個老師編號遞增 , 第三個老師編號遞減 , 第四個老師編號遞減；C4：第一個老師編號遞增 , 第二個老師編號遞減 , 第三個老師編號遞減 , 第四個老師編號遞減；

22、通過 Matlab軟件編程（見附錄程序1），得到四組數(shù)據(jù)分別如下：按 C1 規(guī)則：教師（ M） 4567891011121314學(xué)生（ N） 1112233691311教師（ M） 15161718192021222324學(xué)生（ N） 13151720212426303335按 C2 規(guī)則：6教師（ M）4567891011121314學(xué)生（ N）1112233691312教師（ M）15161718192021222324學(xué)生（ N） 12161720222329303538按 C3 規(guī)則：教師（ M）4567891011121314學(xué)生（ N）1112233691313教師（ M）1516

23、1718192021222324學(xué)生（ N） 14161820232527303136按 C4 規(guī)則：教師（ M） 4567891011121314學(xué)生（ N）1112233691313教師（ M） 15161718192021222324學(xué)生（ N） 13141415152023252525將以上四個表格中的“特殊點(diǎn)”M 對應(yīng)的 N 值，全部修正為第M-1 個數(shù)對應(yīng)的 N 值，最后得到一組修正后的最優(yōu)結(jié)果見下表：教師（ M） 4567891011121314學(xué)生（ N） 1112233691313教師（ M） 15161718192021222324學(xué)生（ N） 1416182023 25

24、29 30 35 38分析上表得到對應(yīng)的學(xué)生數(shù)與所需老師的最少數(shù)量的數(shù)據(jù)如下表2:表 2 “沒有兩個老師相同”已知N 對應(yīng)的最小 M表M479111213141516N1236913131416M1718192021222324N1820232529303538表 2 中顯示， 24 位教師可以面試的最多學(xué)生數(shù)為38 人；而未修正前的表 1 顯示 24 位教師能面試學(xué)生的最大人數(shù)為35 人。由此可見，修正后的數(shù)據(jù)更逼近最優(yōu)解或者即為最優(yōu)解。針對表 2數(shù)據(jù)，為了用 Matlab 編程，進(jìn)行曲線擬合，為了擬合結(jié)果更加準(zhǔn)確，我們采用兩種方式擬合。1) 高斯函數(shù)擬和用 Matlab 編程，采用高斯函數(shù)

25、逼近，擬合所得圖形如下圖1 所示：7圖 1 “沒有兩個老師相同”情形下擬合圖通過運(yùn)行結(jié)果得到的參數(shù)，列出教師數(shù)M 和面試最大面試學(xué)生數(shù)N 的函數(shù)表達(dá)式：M 38.47)2M 4. 897)2M 15. 55)2(（ 1）N 23.63 e20.55.701 e4 .1868.876 e11.282) 多項式擬和直接用 polyfit函數(shù)對數(shù)據(jù)進(jìn)行5 次擬合時 , 所得圖形如下圖2：圖 2 “沒有兩個老師相同”情形下擬合圖得到的函數(shù)表達(dá)式為：f ( x)0.00048x0.01807x 20.30479x 32.74139x 42.25378x5（ 2）5.1.2.3結(jié)果和誤差分析根據(jù)公式（ 1

26、）求出 M擬合值，并與原始值做比較，結(jié)果見下表3：表 3非線性擬和誤差分析表原始數(shù)4791112131516擬合數(shù)4.916.638.4011.5811.5113.6214.4415.97誤差0.910.370.60.580.490.620.560.03原始數(shù)1718192021222324擬合數(shù) 17.19 18.09 19.11 19.74誤差0.190.090.110.268求出表 3中誤差值的平均誤差e10.2508。根據(jù)公式（ 2）求出 M擬合值，并與原始值做比較，結(jié)果見下表4：表 4 線性擬和誤差分析表原始數(shù)4791112131516擬合數(shù)4.716.658.1811.0512.5

27、3114.0814.5115.47誤差0.710.350.820.050.531.080.490.53原始數(shù)1718192021222324擬合數(shù)16.5417.6819.3220.2621.5221.7122.5824.20誤差0.460.320.320.260.520.290.420.20求出表 4中誤差值的平均誤差e20.3063。由此得出，第一種線型擬合的得出的結(jié)果誤差要小，擬合的值更接近真實(shí)值，所以采用第一種方案。即 M一定時，可面試的最大學(xué)生人數(shù) N 與 M 的關(guān)系表達(dá)式為：( M 38.47)2( M 4.897)2( M 15.55) 2N 23.63 e20.55.701 e

28、4 .1868.876 e11.28（ 3）沒有三位老師相同的情形任兩位學(xué)生的“面試組”都沒有三位面試?yán)蠋熛嗤那樾?，設(shè)計模型步驟和算法基本與模型.1.1（見）相同。只有上文中第三小點(diǎn)：任意兩位學(xué)生的“面試組”不能有三位老師相同的情形，更改為如下數(shù)學(xué)M表達(dá)式：xik x jk2，其中 k 表示第 k 個老師，xi k 、( i j; i, j 1, 2, , N )k 1x j k 是 0 1 變量。同理可建立單目標(biāo)規(guī)劃模型1.2：maxNMxik xjk2(ij; i , j1,2, N )k 1Mst.xik4(i 1,2, N )k1x, xj k0或1（是 0-1變量）ik設(shè)計尋優(yōu)算法

29、，利用Matlab 編程（程序及運(yùn)行結(jié)果見附錄程序2），運(yùn)行結(jié)果所得數(shù)據(jù)如表5：表 5不能有三個教師相同的情況教師（ M） 4567891011121314學(xué)生（ N） 113714141826395577教師（ M） 15161718192021222324學(xué)生（ N） 105140140148164189221263315378同理，針對“不能有三個教師相同的情形”，我們也不能直接使用表 2 中一次得出的數(shù)據(jù)擬合。因為，所得數(shù)據(jù)沒有對不合理的數(shù)進(jìn)行修正，也使結(jié)果陷入局部最優(yōu)，最終導(dǎo)致擬和結(jié)果與實(shí)際相差太大的后果。根據(jù)“沒有兩個教師相同的情形” 中的四個教師編碼規(guī)則， 使用 Matlab編程

30、計算出如下四組結(jié)果：按 C1 規(guī)則：9教師（M） 4567891011121314學(xué)生（N） 113714141826395577教師（M） 15161718192021222324學(xué)生（ N） 105140140148164189221263315378按 C2 規(guī)則：教師（M） 4567891011121314學(xué)生（N） 113714152130395571教師（M） 15161718192021222324學(xué)生（N） 95140140163195229272324376424按 C3 規(guī)則：教師（M） 4567891011121314學(xué)生（N） 113714141830395577教師（

31、M） 15161718192021222324學(xué)生（ N） 105140140148177189244295328378按 C4 規(guī)則：教師（M） 4567891011121314學(xué)生（N） 113714142029405472教師（M） 15161718192021222324學(xué)生（N） 96140138163190220 257296331384將以上四個表格中的“特殊點(diǎn)”M對應(yīng)的 N 值，全部修正為第M-1 個數(shù)對應(yīng)的 N 值，最后得到一組修正后的最優(yōu)結(jié)果見下表：教師（ M） 4567891011121314學(xué)生（ N） 113714152130405577教師（ M） 15161718

32、192021222324學(xué)生（ N） 105140140163195229272324376424分析上表得到對應(yīng)的學(xué)生數(shù)與所需老師的最少數(shù)量的數(shù)據(jù)如下表6:表 6“沒有三個老師相同”已知N 對應(yīng)的最小 M表M467891011121314N13714152130405577M15161718192021222324N105140140163195229272324376424對比表6 和表 5：表 3 顯示， 24 位教師可以面試的最多學(xué)生數(shù)為424人；而未修正前的表2 顯示 24 位教師能面試學(xué)生的最大人數(shù)為378 人。教師人數(shù)越大時，所能面試的學(xué)生最大學(xué)生人數(shù)相差越大。因此，修正后的數(shù)據(jù)

33、擬和出的數(shù)值表達(dá)式更能真實(shí)的反映教師數(shù)M 和可面試的最大學(xué)生數(shù)N 的關(guān)系。已經(jīng)證明，采用高斯函數(shù)擬合，比采用多項式擬合得出的結(jié)果更準(zhǔn)確，因此，對“沒有三個教師相同的情形”，我們直接采用高斯函數(shù)進(jìn)行擬合。通過對表4 中的數(shù)據(jù)進(jìn)行數(shù)據(jù)擬和，擬合所得圖形如下圖3 所示：10圖 3 “沒有三個老師相同”情形下的擬合圖由圖 3 也可以看到，曲線擬合效果比較好，基本上所有的點(diǎn)都在曲線的附近浮動。對應(yīng)的M 與 N 的表達(dá)式為：(M 417.82(M 1552M 45.49)2)5.91 e(（ 4）N 23.69 e232.610.95 e125.746.385.2 問題二模型的建立及求解本問題是要求根據(jù)

34、Y1Y4 的要求，建立學(xué)生與面試?yán)蠋熤苯雍侠淼姆峙淠Ｐ汀Ｏ喈?dāng)于在問題一的基礎(chǔ)上增加了約束和目標(biāo)，因此問題二要解決的是一個多目標(biāo)規(guī)劃問題。首先對題目給出的四個要求進(jìn)行量化分析，轉(zhuǎn)化為多目標(biāo)規(guī)劃的四個約束條件；再將問題2 的目標(biāo)轉(zhuǎn)化為數(shù)學(xué)表達(dá)式，得到目標(biāo)函數(shù)，最后進(jìn)行規(guī)劃分配得到到一個多目標(biāo)規(guī)劃求最優(yōu)的模型2。貪婪法思想簡介貪心方法是一種改進(jìn)了的分級處理方法。它首先根據(jù)題意，選取一種量度標(biāo)準(zhǔn)。然后按這種量度標(biāo)準(zhǔn)對這n 個輸入排序，并按序一次輸入一個量。如果這個輸入和當(dāng)前已構(gòu)成在這種量度意義下的部分最優(yōu)解加在一起不能產(chǎn)生一個可行解，則不把此輸入加到這部分解中。這種能夠得到某種量度意義下的最優(yōu)解的分級

35、處理方法稱為貪心方法。由上述定義知，選擇能產(chǎn)生問題最優(yōu)解的最優(yōu)量度標(biāo)準(zhǔn)是使用貪心法設(shè)計求解的核心問題。本問中也建立的優(yōu)先級標(biāo)準(zhǔn)，詳細(xì)見5.2.4 程序算法編寫步驟。5.2.2 將題目要求量化處理1、對于 Y1 的要求：要使每位老師面試的學(xué)生數(shù)量應(yīng)盡量均衡第j 個老師面試第 i 個學(xué)生1,，其中 i = （ 1 ， 2， ， N ） , j =設(shè) xij0,第j 個老師不面試第 i 個學(xué)生（1，2， ，M）則第j 個老師面試學(xué)生的個數(shù)為：11NWjxij(i1,2, N; j1,2, M )i 1要使老師面試的學(xué)生數(shù)量應(yīng)盡量均衡，由于有N 個學(xué)生和M 個老師，則平均每個老師面試學(xué)生的個數(shù)為W4N

36、 ，代入 N 379,M 24， 求得MW63.1667 ，我們可以假設(shè)WiWj12、對于 Y2 的要求：面試不同考生的“面試組”成員不能完全相同通過分析可以求出任意兩位學(xué)生被同一個老師面試為：qi, j ,kxikx jk(i j且 i, j1,2, N ; k1,2, ,M) ，式中， xik, x jk 均為 0 1 變量，所以：，第 i 和第 j 個學(xué)生都被第 k個老師面試qi , j ,k1，第 i 和第 j 個學(xué)生不都被第 k個老師面試0由此得到任意兩個學(xué)生i 和 j 的面試組中含有相同老師的個數(shù)為Qij ，MQijqi , j ,k(ij且 i , j1,2,N ; k1,2,

37、M )k1由于面試不同考生的“面試組”成員不能完全相同，則：Qij43、對于Y3 的要求 : 兩個考生的“面試組”中有兩位或三位老師相同的情形盡量的少通過分析得到：Tij1， Qij2j 且i, j1,2,N0，其它， i1， Qij3j且i , j1,2,NH ij， i0，其它式中 Tij 和 H ij 分別表示任意兩個學(xué)生i 和 j 的面試組中含有相同老師的個數(shù)分別為2和 3的情況。要使這兩種情況數(shù)目盡量少，應(yīng)當(dāng)對含有相同老師的不同組合進(jìn)行加權(quán)處理，由題目公平性的理解，當(dāng)面試組中含有相同老師的數(shù)目越小是，更顯公平性，所以，就是先考慮使兩個老師相同的數(shù)目少，在考慮三個老師相同的數(shù)目少。用數(shù)

38、學(xué)語言表示為求：N1NN1NminZ1TijH ij()i 1 ji 1i1 ji 14、對于 Y4 的要求 : 任意兩位老師面試的兩個學(xué)生集合出現(xiàn)相同學(xué)生的人數(shù)盡量的少設(shè) p xij xik 表示任意兩個老師 j 、 k 面試學(xué)生 i 的情況，由于 xij 和 xik 為 01 變量，則：1，j,k 兩個老師都面試學(xué)生 ipi, j , k0，j,k 兩個老師不都面試學(xué)生 i 所以，任意兩個老師 j 、 k 都面試學(xué)生相同的個數(shù)為：12nPjkpi , j ,ki1根據(jù)題目意思，所以有：M 1Mmin Z2Pjkk 1j k 1模型 2 的建立根據(jù)模型準(zhǔn)備， 以任意兩個學(xué)生的面試組中有兩個老

39、師或三個老師相同的情況盡量少、任意兩個老師面試學(xué)生的集合出現(xiàn)相同學(xué)生盡量少為目標(biāo)，在滿足約束條件下，可以建立整數(shù)規(guī)劃模型如下：N1NN1NminZ1TijH iji1 ji1i 1 ji1M1MminZ2Pjkk 1 jk1WiWj1Mxij4j 1st.Qij4NW jxiji 1xij 為01變量模型解釋：1) 目標(biāo) 1：表示兩個考生的“面試組”中有兩位或三位老師相同的情形盡量的少；2) 目標(biāo) 2：表示任意兩位老師面試的兩個學(xué)生集合出現(xiàn)相同學(xué)生的人數(shù)盡量的少；3) 約束 1：表示每位老師面試的學(xué)生數(shù)量應(yīng)盡量的均衡；4) 約束 2：每位學(xué)生只能接受四位教師的面試；5) 約束 3：表示面試不同

40、考生的“面試組”成員不能完全相同；6) 約束 4：代表第 j 個教師面試學(xué)生的總數(shù)；7) 約束 5：代表第 j 個教師面試第 i 個學(xué)生的 0-1 變量。求解當(dāng) N=379 ， M=24 的分配方案1、設(shè)計算法針對本問，我們設(shè)計了如下尋優(yōu)標(biāo)準(zhǔn)：把“面試組”分為四類，分別為：沒有一個教師相同的情形；有一個教師相同；有兩個教師相同；有三個教師相同，且優(yōu)先級逐次降低。求解模型時，我們采用貪婪法思想編程，按照四種“面試組”的優(yōu)先級順序，分別從 C 4 M 中教師組合中，搜索出面試學(xué)生數(shù)目的“面試組”。至此，對M=24 ， N=379 進(jìn)行合理公平的分配基本完成。程序算法步驟如下：Step1：首先對 M 位教師每四人一組進(jìn)行組合，求出所有組合項為CM4 ，把所