2006年數(shù)學建模優(yōu)秀學生面試問題

1、學生面試問題一、 問題重述高校招生是高考中的一項新生事物，現(xiàn)在仍處于探索階段。某高校擬在全面衡量考生的高中學習成績及綜合表現(xiàn)后再采用面試的方式?jīng)Q定錄取與否。該校在今年招生中，經(jīng)過初選合格進入面試的考生有 N 人，擬聘請老師 M 人。每位學生要分別接受 4 位老師（簡稱該學生的“面試組”）的單獨面試。面試時，各位老師獨立地對考生提問并根據(jù)其回答問題的情況給出評分。由于這是一項性很強的評價工作，老師的專業(yè)可能不同，他們的提問內容、提問方式以及評分也會有較大差異，因此面試同一位考生的“面試組”的具體組成不同會對錄取結果產(chǎn)生一定影響。為了保證面試工作的公平性，組織者提出如下要求：Y1.Y2.Y3.Y4

2、.每位老師面試的學生數(shù)量應盡量均衡；面試不同考生的“面試組”成員不能完全相同；兩個考生的“面試組”中有兩位或三位老師相同的情形盡量的少； 被任意兩位老師面試的兩個學生集合中出現(xiàn)相同學生的人數(shù)盡量少。請回答如下問題：問題一：設考生數(shù) N 已知，在滿足 Y2 條件下，說明聘請老師數(shù) M 至少分別應為多大，才能做到任兩位學生的“面試組”都沒有兩位以及三位面試老師相同的情形。問題二：請根據(jù) Y1Y4 的要求建立學生與面試老師之間合理的分配模型，并就 N379，M24 的情形給出具體的分配方案（每位老師面試哪些學生）及該方案滿足 Y1Y4 這些要求的情況。問題三：假設面試老師中理科與文科的老師各占一半，

3、并且要求每位學生接受兩位文科與兩位理科老師的面試，請在此假設下分別回答問題一與問題二。問題四：請考生與面試老師之間分配的均勻性和面試公平性的關系。為了保證面試的公平性，除了組織者要考慮，試給出新的分配方案或建議。要求外，認為還有哪些重要需二、 符號說明xij ： xij 取 1 表示第 i 個學生被第 j 位教師面試，0 則表示沒有；STNM ：M 位老師面試 N 個學生的分配矩陣；N , M N , M = STNM . . N , M S：矩陣中第 i 個行向量；iSTNM Tj ： STNM 矩陣中第 j 個行向量；) ：向量 S 中元素值大于 n 的元素個數(shù)；n ： n 值向上取整；三

4、、 問題的分析以及模型的建立、求解- 1 -在忽略各子問題的約束和優(yōu)化條件基礎上，此學生面試問題在形式上屬于標準的 0/1 整數(shù)規(guī)劃問題，基本模型建立如下：N , M N , M = STNM . . .N , M 其中 xi, j為0或1 ;n目標函數(shù)max Z countzeroS（1）i i 14ni 1,2,.n滿足約束條件xi, j 4（2）j1其中函數(shù)countzeroS 計算向量 S 中零元素的數(shù)目。問題 11問題分析：根據(jù)問題描述，此問題由于約束條件的不同，可以分為如下兩個子問題：問題 1.1：任兩位學生的“面試組”都沒有兩位面試老師相同；其數(shù)學表達如下：F (Si S j ,

5、2) 2 其中 i,j=1,n 且 ij（3）問題 1.2：任兩位學生的“面試組”都沒有三位面試老師相同；其數(shù)學表達如下：F (Si S j ,2) 3 其中 i,j=1,n 且 ij（4）綜合上述模型和約束條件，本問題可以采用 0/1 整數(shù)規(guī)劃的方法求解。考慮實際的求解環(huán)境，為了在求解精度和求解性能上達到一定的平衡，以下將用幾種不同的模型求解。2模型求解問題 1.10/1 整數(shù)規(guī)劃方式求解采用 0/1 整數(shù)規(guī)劃求解該模型的算法見附件中算法 1。該算法可以求得確定學生數(shù) N 基礎上，最少需要的老師數(shù) M，以及其對應的分配矩陣，模型求得的結果為問題可行域上的最優(yōu)解。但是當 N 較大時，可行域空間

6、極為龐大，搜索性能較差。為了進一步改善求解性能，本文進一步提出其他模型進行改進。2) 組合數(shù)方式求解考慮到問題要求求得老師數(shù) M 至少為多大，即需要確定一個 M 的下限取值。為此用組合數(shù)方法分析滿足問題條件的解的性質：性質 1：可行解 STN M 每一行 4 個元素為 1 的（列）數(shù)位可以組成C 2 個數(shù)位4對；各行生成的C 2 個（列）數(shù)位對組成數(shù)量為 NC 2 的數(shù)位對集合，在此集合中任4何兩個數(shù)位對都不相同。4例：假定第 i 行 4 個元素 1 分別位于第 a,b,c,d 列，則第 i 行的 4 個元素為 1 的數(shù)位可以組成(a,b),(a,c),(a,d),(b,c),(b,d),(c

7、,d)6 個數(shù)位隊。證明：性質 1 中前一部分顯而易見。后一部分的證明可以采用反證法：- 2 -假定所有的數(shù)對中存在 2 個數(shù)對相同，則由于同一行的 4 個數(shù)中不可能產(chǎn)生相同的兩個數(shù)隊，故這兩個數(shù)對必然產(chǎn)生于不同的行 i 和 j。由此可以推斷第 i行和第 j 行存在兩個列數(shù)位相同的元素 1，即兩個學生有兩位面試老師相同，和題目約束條件。因此性質得證。性質 2：可行解STNM 滿足 NC 2 C 24M證明：由性質 1，按照性質 1 的列數(shù)位對生成規(guī)則，所有行可以生成 NC 24個兩兩不同的數(shù)位對。由于所有的數(shù)位對都是基于 1 到 M 的列號產(chǎn)生的二元組合i, j i 1,.,m; j 1,.,

8、m;i j ，故其數(shù)目不會超過 1 到 M 能夠產(chǎn)生的二元組合最大數(shù)目C 2。故性質 2 得證。由性質 2 可以推出 M 的取值下界條件：MM 1 1 48N(5)2即結論：M 至少應為1 1 48N 時，才可能滿足任兩位學生的“面試組”都沒有兩位面試老師相同。2由于上述計算過程只考慮了該問題的必要性條件，因此求出的下界不一定是問題的下確界，更為精確的下確界模型為 NC 2 C 2 t ，其中t 為關于 N 和 M 的函4M數(shù)。實際的模型計算較為復雜，故此本文接下來將通過其他方法尋求更為精確的模型，并在一定程度上通過其對本模型進行驗證。3)基于最短路徑的階段遞進搜索算法假定 1：存在 N 個學

9、生對應 M 位老師的最優(yōu)分配方案之一的情況下，該最優(yōu)分配方案滿足各老師的面試負荷量相對均衡；假定 2：存在滿足假定 1 的ST( N 1)M 的最優(yōu)分配方案，該方案可由某一個滿足假定 1的 STNM 的最優(yōu)分配方案在不改變現(xiàn)有分配的基礎上擴展取得（即ST( N 1)M 中存在一個 N M 子矩陣等于 STNM ）；由假定 1 和假定 2 可以得出以下兩條搜索規(guī)則：規(guī)則 1：從 STNM 的某一最優(yōu)分配方案向ST( N 1)M 的某一最優(yōu)方案擴展時，只需在STNM 的基礎上增加第 N 1 行，并調整其中非零元素的位置（同時方案根據(jù)需要增加一定數(shù)量的列或者保持列數(shù)不變）；規(guī)則 2：在對 N 1 個

10、學生進行老師分配時，總是先選取在 N 個學生數(shù)下所有老師中面試任務最輕的第一位老師；由規(guī)則 1 及規(guī)則 2 編寫的基于最短路徑的階段遞進搜索算法見附件算法 2。該算法產(chǎn)生的一系列(N , M ) 數(shù)對結果（見附件數(shù)據(jù) 1）可應用于對上述各模型的檢驗及模型擬合度分析。4) 模型驗證及比較根據(jù)附件中的算法 2 得到一批(N , M ) 數(shù)對結果（見附件數(shù)據(jù) 1），選取其中 500個數(shù)據(jù)作為樣本輸入數(shù)據(jù)，建立神經(jīng)網(wǎng)絡模型。由于一個隱層的 BP 神經(jīng)網(wǎng)絡已經(jīng)可以對任意的函數(shù)進行模擬，考慮建立只包含一層隱層的三層網(wǎng)絡模型。又由于神經(jīng)網(wǎng)絡的輸入數(shù)據(jù)是-1，1區(qū)間，首先對數(shù)據(jù)進行歸一化，常用的歸一化方法是根

11、據(jù)樣本的取值范圍來選擇，問題中的學生和面試老師的數(shù)量的取值區(qū)間是所有整數(shù)，可能是趨向無窮大的取值，所以模型中用反正切函數(shù)將輸入和輸出數(shù)據(jù)歸一為（0，1）區(qū)間中，最小整數(shù) 1 變?yōu)?0.5，即為網(wǎng)絡模型輸入的最小值，- 3 -取值區(qū)間為（0.5，1）。(1) 前 500 個數(shù)據(jù)作為樣本訓練模型 x=1:500;y=7 9 10 10 12 13 13 14 14 14 16 17 17 17 18;% (數(shù)據(jù)輸入省略，具體數(shù)據(jù)見附件表格) X=atan(x)*2/pi; Y=atan(y)*2/pi; threshold=0.5 1;net=newff(threshold,15,1,tansig

12、,tansig,traigdx);=trainlm; net.trainParam.epochs=1000; net.trainParam.goal=0.0000001; net=train(net,X,Y); yy=sim(net,X) yT1=tan(1/2*pi*yy); plot(x,yT1, x，x,*,x,y,.);樣本的輸入輸出的數(shù)據(jù)個數(shù)都為 1，所以網(wǎng)絡模型的輸入層和輸出層的節(jié)點數(shù)目都為 1，取隱層節(jié)點的數(shù)目為 15，采曲正切 S 型傳遞函數(shù) tansig,優(yōu)化算法為剃度搜索 traigdx，目標精度為 0.0000001，最大迭代次數(shù)為 1000，樣本訓練模型，用得到的模型對

13、樣本數(shù)據(jù)的擬合結果見圖 1。TRAINLM,Epoch0/1000,MSE2.859e-007/1e-007,Gradient0.00655493/1e-010TRAINLM,Epoch17/1000,MSE9.13425e-008/1e-007,Gradient0.0017508/1e-010TRAINLM, Performance goal met.模型對學生數(shù)為 379 時，需要的老師數(shù)量為 78，因此問題 2 中的 24 個老師的分配需要有一定的分配方案。圖 1訓練樣本曲線與BP 網(wǎng)絡模型擬合結果(2) 用前 500 個數(shù)據(jù)作為樣本訓練模型易見，模型的精確度非常高，用所得的模型對問題中

14、的 501 到 700 個學生之間的數(shù)據(jù)對其所需要的老師數(shù)量進行- 4 -，所得結果見圖 2。圖 2測試樣本曲線與 BP 網(wǎng)絡模型檢驗結果用 501700 個學生的數(shù)據(jù)作為模型檢驗樣本 xt=501:700;yt=90 90 91 91 91 91 91 91 91; %(數(shù)據(jù)輸入省略，具體數(shù)據(jù)見附件表格)X Yan(xt)*2/pi; an(yt)*2/pi;yyt=sim(net,XT); yT2=tan(1/2*pi*yyt); plot(xt,yyT2,xt,xt*,xt,yt,.);檢驗結果，見圖 2用所得到的總體 700 個數(shù)據(jù)（訓練數(shù)據(jù)和測試數(shù)據(jù)）的散點圖，分析數(shù)據(jù)分布的情況和發(fā)

15、現(xiàn)規(guī)律xz=1:700;yz=y,yt;XZ=X,XT;YZ=Y,YT;yyz=sim(net,XZ); yyZ1=tan(1/2*pi*yyz);plot(xz,yyZ1, xz,xz,*,xz,yz,.);結果見圖 3（綠型為神經(jīng)網(wǎng)絡模型的數(shù)據(jù)散點圖型，點型為模型二數(shù)據(jù)的散(3)點圖），數(shù)據(jù)的分布近似為二次曲線，因而可建立問題的模型，以求解問題。- 5 -圖 3 總樣本曲線與BP 網(wǎng)絡模型結果(4)模型設問題 1 學生數(shù) x ，所需要的最少老師數(shù)量為 y ，從圖中的曲線可以看出模型函數(shù)曲線的形狀，曲線是具有二次曲線 y ax b （ a,b 為系數(shù)）的相似形狀，具有區(qū)間跳躍。隨著 x 的變

16、大，相鄰的兩個跳躍點之間是水平線段且長度變大，由于值域 y 的取值為整數(shù)，所以跳躍可能是對二次函數(shù)值取整引起的，因而可假設模型的函數(shù)形式為 y為 ax b 的取整，這個假設具有合理性，由 3 可知建立模型 y ax b ，由總體 700 個數(shù)據(jù)求得相應的 y 2 ，系數(shù) a 可看作變量 x ， y 2 擬合曲線的斜率， 由數(shù)據(jù)可知 y 2 與 x 的比值 2近似為 18 ， 假設模型曲線為y / xy 18x 1 。在同一個圖上畫出三條曲線：樣本曲線、BP 神經(jīng)網(wǎng)絡的模型曲線、y 18x 1的二次曲線。 yyZ2=fix(18.*xz+1).(1/2);plot（xz,yyZ1, xz,xz,

17、*,xz,yyZ2,-,xz,yz,.）;結果見圖 4，三條曲線的非常穩(wěn)合（綠色型為神經(jīng)網(wǎng)絡模型的數(shù)據(jù)散點圖型，點型為模型二數(shù)據(jù)的散點圖，線型為 y 18x 1 的曲線散點圖形），驗證了型 y 18x 1 的合理性，也同時驗證了三個模型對問題求解的有效型。模圖 4樣本曲線、BP 神經(jīng)網(wǎng)絡的模型曲線、 y 18x 1 的二次曲線模型結果- 6 -問題 1.20/1 整數(shù)規(guī)劃方式求解采用 0/1 整數(shù)規(guī)劃求解該模型的算法見附件中算法 1。其算法的優(yōu)缺點同問題 1.1。2)組合數(shù)方式求解同問題 1.1 的思路，考慮到問題要求求得老師數(shù) M 至少為多大，即需要確定一個 M 的下限取值。為此用組合數(shù)方法

18、分析滿足問題條件的解的性質：性質 1：可行解 STNM 每一行 4 個元素為 1 的（列）數(shù)位可以組成C 3 個三元4數(shù)位組；各行生成的C 3 個（列）三元數(shù)位組組成數(shù)量為 NC 3 的數(shù)位組集合，在此4集合中任何兩個數(shù)位組都不相同。4例：假定第 i 行 4 個元素 1 分別位于第 a,b,c,d 列，則第 i 行的 4 個元素為 1 的數(shù)位可以組成(a,b,c),(a,b,d),(a,c,d),(b,c,d)4 個數(shù)位組。證明：性質 1 中前一部分顯而易見。后一部分的證明可以采用反證法：假定所有的數(shù)對中存在 2 個數(shù)位組相同，則由于同一行的 4 個數(shù)中不可能產(chǎn)生相同的兩個數(shù)位組，故這兩個數(shù)位

19、組必然產(chǎn)生于不同的行 i 和 j。由此可以推斷第 i 行和第 j 行存在三個列數(shù)位相同的元素 1，即兩個學生有三位面試老師相同，和題目約束條件。因此性質得證。性質 2：可行解STNM 滿足 NC 3 C 34M證明：由性質 1，按照性質 1 的列數(shù)位對生成規(guī)則，所有行可以生成 NC 34個兩兩不同的數(shù)位組。由于所有的數(shù)位組都是基于 1 到 M 的列號產(chǎn)生的三元組合i, j, k i 1,., m; j 1,.,m; k 1,., m;i j，j k且i k ，故其數(shù)目不會超過 1 到 M 能夠產(chǎn)生的三元組合最大數(shù)目C 3 。故性質 2 得證。M由性質 2 可以推出 M 的取值下界條件滿足：M

20、3 3M 2 2M 24N 0(6)即結論：M 至少應使M 3 3M 2 2M 24N 0 成立時，才可能滿足任兩位學生的“面試組”都沒有三位面試老師相同。由于上述計算過程只考慮了該問題的必要性條件，因此求出的下界不一定是問題的下確界，更為精確的下確界模型為 NC 3 C 3 t ，其中t 為關于 N 和M 的函4M數(shù)。3)基于最短路徑的階段遞進搜索算法假定 1：存在 N 個學生對應 M 位老師的最優(yōu)分配方案之一的情況下，該最優(yōu)分配方案滿足各老師的面試負荷量相對均衡；假定 2：存在滿足假定 1的ST( N 1)M 的最優(yōu)分配方案，該方案可由某一個滿足假定 1的 STNM 的最優(yōu)分配方案在不改變

21、現(xiàn)有分配的基礎上擴展取得（即ST中存在一個 N M 子矩陣等于 ST）；NM ( N 1)M由假定 1 和假定 2 可以得出以下兩條搜索規(guī)則：規(guī)則 1：從STNM 的某一最優(yōu)分配方案向ST的某一最優(yōu)方案擴展時，只( N 1)M需在 STNM 的基礎上增加第 N 1 行，并調整其中非零元素的位置（同時方案根據(jù)需要增加一定數(shù)量的列或者保持列數(shù)不變）；規(guī)則 2：在對 N 1 個學生進行老師分配時，總是先選取在 N 個學生數(shù)下所有老師中面試任務最輕的第一位老師；- 7 -具體算法同問題 1.1 中的實現(xiàn)方式，算法實現(xiàn)略。問題 21.問題分析：根據(jù)問題描述，此問題需要求滿足目標條件 Y1,Y2,Y3,Y

22、4 的滿意解，故屬于一個多目標的決策模型，其解決思路可以應用多目標規(guī)劃的實現(xiàn)方法。常用的多目標規(guī)劃實現(xiàn)方法有多種，實際中應用較多且較簡便的是通過把多目標決策轉化為單目標問題。綜合考慮算法復雜性和性能，本問題將采用加權方法。2. 模型求解本例算法由于學生數(shù)目較多，采用傳統(tǒng)的遍歷式搜索比較的目標決策方法受限于設計和運行環(huán)境，其可行性受到較大影響。為了提高其算法可行性，本例中對于算法做出以下改進：1)把個目標條件的滿意度轉化為數(shù)量指標，通過一定的權重分配把多個目標的數(shù)量指標轉化為單目標的數(shù)量指標。2)改變原有的遍歷式搜索算法，選用從可行解空間中隨機抽取可行集的方式，從可行集中尋找滿意解；3)當可行解

23、；集覆蓋數(shù)量越多時，找到的滿意解更趨近于整個問題的滿意4)通過增加算法的有效迭代次數(shù)，可以增加抽取的可行解數(shù)量。集覆蓋的可行具體的算法實現(xiàn)參見附件算法 3。由于運行環(huán)境的限制，選取了 105 次作為有效迭代次數(shù)，并在每迭代 5次的基礎上打印出個最優(yōu)化分配方案，相應的優(yōu)化情況以表格形式列舉如下：從迭代結果可以歸納出以下幾點：1) 由于采取隨機矩陣生成并比較優(yōu)化方式，在算法復雜度和計算環(huán)境的影響決定了迭代次數(shù)不可能太多，導致優(yōu)化次數(shù)也相對較少。這一點可以通過矩陣的隨機生成原理作出一定的解釋。隨即生成下，每個老師的面試任務負荷量應該相對平均，得出的趨向于滿意解，使得在相對于樣本空間較小的樣本數(shù)條件下

24、，命中的可以進一步優(yōu)化的幾率會較少；- 8 -目標條件Y1Y3Y4總計目標最優(yōu)目標調整10.00010.517.7454有效迭代次數(shù)957.4054477531821.180717.7454966.4043475941920.663717.7454974.16.909516.9095986.3702475891920.629116.9095999.2345481031622.044816.90951006.5916476221719.853816.90951017.20.919516.90951027.0874477001720.357416.90951037.5046477701720.78

25、1616.90951049.7386482131924.059916.90951058.0145478611721.300616.90952) 由于個目標約束數(shù)字表示的數(shù)量級不同，為了使各個目標在總目標中都具有相對均衡的影響，必須要通過標數(shù)量相對接近；調整，是的后各目3) 由于 Y2 是一個必要目標，而非滿意目標，故此應該把 Y2 作為可行解的判別條件，而非滿意解的判別條件；具體的分配方案見附件數(shù)據(jù) 2。從方案排列以及各目標的數(shù)量表示和其他方案下各目標的數(shù)量表示比較來看，可以得出以下幾點：1)對于 Y1,Y3,Y4 三個目標約束而言，最終方案相較于鄰近方案在三個目標上面都由優(yōu)化（具體表現(xiàn)為三個

26、目標的數(shù)量表示都比其它相鄰方案小）；2)由于的設定，以及計算出的 Y1,Y3,Y4 數(shù)量表示的數(shù)量極，可以看出 Y1,Y4 目標偏好度相當，Y3 相對而言目標偏好度較低，此決定是由權重的設定導致，并不是由最終方案的特定導致；由于上面（2）特性的存在，可以認為最終方案在優(yōu)化前提上就考慮了目標 Y1,Y4 的滿意度；Y2 目標由于是一個確定性（可行性）約束，最終方案必然是完全滿足了條件 Y2。3)4)問題 31.問題分析：假設面時老師中理科與文科的老師各占一半，并且要求每位學生接受兩位文科與兩位理科老師的面試。在此條件下，分別對問題一和問題二進行分析：問題一：等同于在問題一滿足現(xiàn)有的約束條件基礎上

27、（即任兩位學生的“面試組”都沒有兩位（子問題 1）和三位（子問題 2）面試老師相同的情形），增加一個新的約束條件，對于問題一的子問題 1,2，新增加的約束分別為：子問題 1：可以把 STNM 矩陣劃分為兩個 ST矩陣，兩個 ST M 都滿足每行M 2N N2上有且只有兩個 1，任何兩行不完全相同；（M 為偶數(shù)，下同）子問題 2：可以把 STNM 矩陣劃分為兩個 ST M 矩陣，兩個 ST都滿足每行M 2NN 2上有且只有兩個 1；問題二：由于文科和理科的老師各占一半，假定可以通過列交換把文科老師移動到 1,M/2 列，理科老師移動到 1+M/2,M 列，則有其滿足條件：可以把 STNM 矩陣劃

28、分為兩個ST M 矩陣，兩個ST M 都滿足每行上有且只有兩個 1。NN222.1)(1)模型求解問題一：子問題 1：類似于問題一中求解的子問題 1.1，考慮 M 取值的下界條件。性質 A： N C 2M2/證明：仿照問題一的子問題 1.1 中性質 2 證明， ST M 滿足每行上有且只有N2- 9 -兩個 1，任何兩行不完全相同，則 N 行上共有 N 個每行上非零元素列號生成的二元數(shù)對，且這些二元數(shù)對兩兩不等。由于 M/2 個列號位置能生成的二元數(shù)對最多有C 2個，故性質 A 得證。M2/則該問題需要同時滿足性質 A 和問題一中子問題 1.1 的性質 2，故其必要條件為： N C 2M2/N

29、C4 C 22M由于M 4* N ，故有M 11 48N2(2) 子問題 2：2)問題二：根據(jù)前面的可以把STNM 矩陣劃分為兩個ST M 矩陣，兩個ST M 都滿足每行NN22上有且只有兩個 1。參照前述附件算法 3，如果仍然采取隨機抽樣篩選局部滿意解的方法，則只需要使隨機出來的可行解滿足前 M/2 列組成的子矩陣每行上只有兩個非零元素。為了操作方便，可以僅把附件算法 3 的隨機矩陣生成規(guī)則：(1) 隨機生成元素為ST矩陣，滿足條件各行元素相加為 2 則保留；M 2N (2) 隨機生成兩個有效的ST矩陣，組一個 STNM ，判斷該矩陣是M 2N 否滿足條件 Y2，如果滿足，則繼續(xù)，否則下一個

30、隨機矩陣；(3) 滿足條件 Y2 的基礎上，進一步判定該矩陣對于 Y1,Y3,Y4 的滿意程度，并和之前取得的滿意解進行比較。問題 4所謂考生與面試老師之間分配的均勻性可以從兩方面理解，一是每個考生被相同數(shù)目的老師面試；二是每位老師面試的學生數(shù)目相等?，F(xiàn)在根據(jù)附件算法 2（基于最短路徑的階段遞進搜索算法）的運行結果可以發(fā)現(xiàn)：當學生數(shù) N 確定且任兩位學生的“面試組”都沒有兩位老師相同的情形下，若 M 為學生數(shù)為 N 時對應的最少的老師數(shù)，此時在這 M 個老師中，任意兩位老師面試的學生數(shù)差額不超過 3。一旦遇到再增加 1 個學生必須至少增加 1 個老師的情況時，新增老師的面試學生數(shù)與其他 M 個

31、老師的面試學生數(shù)有顯著差異，而這種顯著差異隨著 N 的不斷增大而逐漸縮小。所謂面試公平性是許多學生都被同一位老師面試，這是由于該老師自身對不同學生的印象或意見而產(chǎn)生的評判。若在老師面試學生數(shù)目不變的情況下，為了提高面試的公平性，必須增加老師的數(shù)目，使得每個學生盡可能被更多的老師面試?？梢姡S著老師數(shù)目的增多，考生與老師之間的分配正逐步向均勻性逼近。綜上所述，在任兩位學生的“面試組”都沒有兩位老師相同，且 M 為學生數(shù)為 N 時對應的最少的老師數(shù)的情形下，考生與面試老師之間分配的均勻性與面試公平性存在正相關關系。除此之外，當 N 增加 1，考生與面試老師之間分配的均勻性與面試公平性之間的平衡狀態(tài)

32、被破壞，并隨著 N 的逐漸增大，這種平衡狀態(tài)- 10 -又逐漸恢復；反之，當 N 減小 1，考生與面試老師之間分配的均勻性與面試公平性之間的平衡狀態(tài)也被破壞，并隨著 N 的逐漸減小，這種平衡狀態(tài)逐漸，直至當 N 減小到面試分配矩陣中至少有 1 位老師的面試學生只有 1 時，在此基礎上進一步減少一個學生后的面試分配矩陣又達到了新的平衡狀態(tài)?？梢姡ＷC面試的公平性可以充分利用師資力量，但同時這也存在著兩個，一是當學生數(shù)目不斷增大時，每個老師的面試學生數(shù)也在不斷增大，這對老師的面試質量提出了疑問；其次，隨著學生數(shù)目的增大，要保證面試的公平性需要增加一定數(shù)量的老師，這必將增加面試的成本，且對面試工作

33、的組織管理工作提出了巨大。因此，在成本、控制能力、時間的多重約束下，可以重新考慮如何在必需的面試老師數(shù)目的條件下合理分配老師的專業(yè)背景，從而提高老師面試的質量平性，避免了盲目分配給學生專業(yè)不對口的老師。此外，還可以根據(jù)學生的學習情況，把學生分成若干等級，把相關老師分配給給定等級的學生群進行面試；還可以要求每個面試組內必須加一個老師等等。- 11 -四、 附件：1附件算法 1function x,fval=linprog01(N)% x,fval=linprog01(N)函數(shù)求得學生數(shù)為 N 時所需的最少老師的解，為問題 1 的求解程序% x，fval 為最優(yōu)解的返回值% 其中x 為學生與老師的

34、匹配向量，fval 為最少老師的個數(shù)ticinit_count=3*N+1;% 初始化所需要的老師最大數(shù)量 var_count=init_count*N; %配對方案的變量個數(shù) deploy_instance=zeros(var_count,1); x=deploy_instance;opt_solution=init_count;p=2(init_count*(N-1)+3)+2(init_count*(N-1)+2)+2(init_count*(N-1)+1)+2(init_count*(N-1);%利用每位學生都對應 4 個老師，壓縮搜索空間for i=p:2var_count-1 %

35、利用 2 進制變換遍歷所有配對方案空間% strBin_i=dec2bin(i);% deploy_instance=zeros(var_count,1);%for k=1:length(strBin_i)%deploy_instance(k)=str2num(strBin_i(k);% enddeploy_instance=de2bi(i,var_count); % 可行的方案必需滿足變量之和為 4*N if (sum(deploy_instance)=4*N)continueend stud_teacher=zeros(N,init_count);for m=1:N% 向量轉化為配對方案矩

36、陣stud_teacher(m,(1:init_count)=deploy_instance(m-1)*init_count+1):m*init_count);endconstrA=(sum(stud_teacher)=4); %每個學生配對 4 個老師if all(constrA) continue;endsum_tow_lines=zeros(N*(N-1)/2,1); s=0;for m=1:N-1% 統(tǒng)計任意兩個學生對應的相同老師的情況for n=m+1:Ns=s+1; sum_temp=stud_teacher(m,:)+stud_teacher(n,:); sum_temp=(su

37、m_temp1); sum_tow_lines(s,1)=sum(sum_temp);- 12 -endendconstrB=(sum_tow_lines0);% 統(tǒng)計需要的老師數(shù)量objVal=sum(sum_column_result); if objVal=opt_solutionopt_solution=objVal; x=deploy_instance;endendend tocfval=opt_solution;2附件算法 2package test;public class Test private sicx = new10001000; / xij表示第i個學生與第j位老師的關

38、系，若xij=1，表示被面試，xij=0表示沒有private sic finalMAX_TEA_FOR_STUD = 4;public s/ TODOn =try n = catchic void main(String args) Auto-generated method stub0;egarse(args0);(NumberFormatException e) / TODO Auto-generated catch blocke.prStackTrace();for (i = 501; i = 700; i+)test(i);private sictest(N) m; / m表示動態(tài)增

39、加教師時用到的總列數(shù)n = 0; / n表示動態(tài)增加學生時用到的總列數(shù)10000; / T_nj表示第j位老師面試的學生數(shù)t_n= newg; n = 1;m = 4;/g表示增加一個學生，需要分配給他的老師的號碼初始值初始值0;s_m =- 13 -for (a = 0; a N; a+)for (b = 0; b 100; b+)xab = 0;x00 = x01 = x02 = x03 = 1;while (n N) for (b = 0; b m; b+)/ 計算原來每位老師面試的學生數(shù)t_nb = 0;for (b = 0; b m; b+)/ 計算原來每位老師面試的學生數(shù)for (

40、c = 0; c n; c+) if (xcb = 1)t_nb+; t_n_temp; m_kong = m;while (s_m MAX_TEA_FOR_STUD) g = 0;t_n_temp = N;for (b = 0; b m; b+) / 計算分配給新增學生的第一位教師號碼if (xnb = 0) & (t_nb t_n_temp) g = b;t_n_temp = t_nb;m_kong = add_delete(n, m, g, s_m+;m_kong);if(m_kong = 0)break;for ( ifi = 0; i m; i+) (xni = 2)xni = 0;

41、if (s_m 4) for (i = 0; i 4 - s_m;i+) xnm+ = 1; n+;s_m = 0;System.out.prln(m);- 14 -return m;private sicadd_delete(n,m,b,init_m_kong)xnb = 1;/ 給新增的學生指派第一位教師1; / m個老師init_m_kong - 1;0; e n; e+) / 找出不可添加給學生n的老師號碼，并將此/s_mm_kong=for (e老師標志為2if (xeb = 1)for (f = 0; f 0.82);%if(sum(instance)=4)%stud_teache

42、r(i,(1:init_count)=instance;%break;%end%end a=ceil(rand()*init_count); b=ceil(rand()*init_count); whi=a)b=ceil(rand()*init_count);endc=ceil(rand()*init_count); %隨機生成第三個點的位置 while(c=a)|(c=b)c=ceil(rand()*init_count);endd=ceil(rand()*init_count); % 隨機生成第四個點的位置while(d=a)|(d=b)|(d=c) d=ceil(rand()*init_

43、count);end stud_teacher(i,a)=1; stud_teacher(i,b)=1; stud_teacher(i,c)=1;stud_teacher(i,d)=1;endsum_tow_lines=zeros(N*(N-1)/2,1); M=init_count; sum_tow_cols=zeros(M*(M-1)/2,1); s=0;for m=1:M-1 % 統(tǒng)計任意兩位考官面試相同學生的數(shù)量for n=m+1:Ms=s+1; sum_temp=stud_teacher(:,m)+stud_teacher(:,n); sum_temp=(sum_temp1); su

44、m_tow_cols(s,1)=sum(sum_temp);endendt4=max(sum_tow_cols); % 最大兩位考官面試相同學生的數(shù)量的值s=0;flag2=0;for m=1:N-1% 統(tǒng)計任兩位考生中有相同考官的情況for n=m+1:Ns=s+1;- 16 -sum_temp=stud_teacher(m,:)+stud_teacher(n,:); sum_temp=(sum_temp1); sum_tow_lines(s,1)=sum(sum_temp);if (sum_tow_lines(s,1)4) % 不同考生的考官不能完全相同flag2=1; break;end

45、endif flag2=1break;endendif flag2=1continue;endt3=sum(sum_tow_lines);% 考生中有相同考官的情形總數(shù)量 t1=std(sum(stud_teacher); % 每位考官面試的學生數(shù)量的標準差 objVal=t1*q1+t3*q2+t4*q3;% 總目標值t1 t3 t4if objVal=pr_times*5 ) % opt_solutionxpr_times=pr_times+1;end if(times_countMax_times)break;end每迭代 5 次，打印方案結果end tocfval=opt_soluti

46、on;end4附件數(shù)據(jù)1N=1 M=4 N=6 M=12N=11 M=14N=2 M=7N=3 M=9N=7 M=13N=8 M=13N=4 M=10N=9 M=14N=5 M=10N=10 M=14N=12 M=16N=13 M=17N=14 M=17N=15 M=17- 17 -N=16 N=21 N=26 N=31 N=36 N=41 N=46 N=51 N=56 N=61 N=66 N=71 N=76 N=81 N=86 N=91 N=96 N=101 N=106 N=111 N=116 N=121 N=126 N=131 N=136 N=141 N=146 N=151 N=156 N

47、=161 N=166 N=171 N=176 N=181 N=186 N=191 N=196 N=201 N=206 N=211 N=216 N=221 N=226N=231M=18 M=21 M=23 M=25 M=27 M=29 M=30 M=31 M=32 M=33 M=35 M=36 M=37 M=38 M=38 M=39 M=40M=41 M=42 M=43 M=44 M=45 M=46 M=47 M=48 M=48 M=49 M=50 M=50 M=51 M=52 M=53 M=54 M=55 M=56 M=57 M=58 M=58 M=59 M=59 M=60 M=60 M=61

48、M=61N=17 N=22 N=27 N=32 N=37 N=42 N=47 N=52 N=57 N=62 N=67 N=72 N=77 N=82 N=87 N=92N=97M=18 M=22 M=23 M=25 M=27 M=29 M=30 M=31 M=33 M=34 M=35 M=36 M=37 M=38 M=38 M=39M=40N=18 N=23 N=28 N=33 N=38 N=43 N=48 N=53 N=58 N=63 N=68 N=73 N=78 N=83 N=88 N=93N=98M=19 M=22 M=23 M=25 M=28 M=29 M=30 M=31 M=33 M=

49、34 M=35 M=36 M=37 M=38 M=39 M=40M=40N=19 N=24 N=29 N=34 N=39 N=44 N=49 N=54 N=59 N=64 N=69 N=74 N=79 N=84 N=89 N=94N=99M=20 M=22 M=24 M=25 M=28 M=29 M=30 M=31 M=33 M=34 M=36 M=36 M=37 M=38 M=39 M=40M=41N=20 N=25 N=30 N=35 N=40 N=45 N=50 N=55 N=60 N=65 N=70 N=75 N=80 N=85 N=90N=95M=21 M=23 M=24 M=26

50、M=28 M=30 M=31 M=32 M=33 M=35 M=36 M=37 M=37 M=38 M=39M=40N=100 M=41N=102 N=107 N=112 N=117 N=122 N=127 N=132 N=137 N=142 N=147 N=152 N=157 N=162 N=167 N=172 N=177 N=182 N=187 N=192 N=197 N=202 N=207 N=212 N=217 N=222 N=227N=232M=41 M=43 M=43 M=44 M=45 M=46 M=47 M=48 M=49 M=49 M=50 M=51 M=51 M=52 M=

51、54 M=54 M=55 M=56 M=57 M=58 M=58 M=59 M=59 M=60 M=60 M=61M=61N=103 N=108 N=113 N=118 N=123 N=128 N=133 N=138 N=143 N=148 N=153 N=158 N=163 N=168 N=173 N=178 N=183 N=188 N=193 N=198 N=203 N=208 N=213 N=218 N=223 N=228N=233M=41 M=43 M=44 M=44 M=45 M=46 M=47 M=48 M=49 M=49 M=50 M=51 M=52 M=53 M=54 M=54

52、 M=56 M=57 M=57 M=58 M=58 M=59 M=59 M=60 M=60 M=61M=61N=104 N=109 N=114 N=119 N=124 N=129 N=134 N=139 N=144 N=149 N=154 N=159 N=164 N=169 N=174 N=179 N=184 N=189 N=194 N=199 N=204 N=209 N=214 N=219 N=224 N=229N=234M=42 M=43 M=44 M=44 M=45 M=46 M=47 M=48 M=49 M=50 M=50 M=51 M=52 M=53 M=54 M=55 M=56 M

53、=57 M=57 M=58 M=58 M=59 M=60 M=60 M=60 M=61M=61N=105 N=110 N=115 N=120 N=125 N=130 N=135 N=140 N=145 N=150 N=155 N=160 N=165 N=170 N=175 N=180 N=185 N=190 N=195 N=200 N=205 N=210 N=215 N=220 N=225 N=230N=235M=42 M=43 M=44 M=44 M=45 M=46 M=47 M=48 M=49 M=50 M=50 M=51 M=52 M=53 M=54 M=55 M=56 M=57 M=5

54、8 M=58 M=59 M=59 M=60 M=60 M=61 M=61M=62- 18 -N=236 N=241 N=246 N=251 N=256 N=261 N=266 N=271 N=276 N=281 N=286 N=291 N=296 N=301 N=306 N=311 N=316 N=321 N=326 N=331 N=336 N=341 N=346 N=351 N=356 N=361 N=366 N=371 N=376 N=381 N=386 N=391 N=396 N=401 N=406 N=411 N=416 N=421 N=426 N=431 N=436 N=441 N=

55、446N=451M=62 M=62 M=63 M=63 M=65 M=65 M=65 M=66 M=67 M=67 M=68 M=69 M=70 M=70 M=71 M=71 M=72 M=72 M=73 M=74 M=74 M=75 M=75 M=76 M=76 M=77 M=77 M=78 M=78 M=78 M=79 M=80 M=80 M=81 M=81 M=82 M=82 M=83 M=83 M=84 M=84 M=85 M=85M=86N=237 N=242 N=247 N=252 N=257 N=262 N=267 N=272 N=277 N=282 N=287 N=292 N=

56、297 N=302 N=307 N=312 N=317 N=322 N=327 N=332 N=337 N=342 N=347 N=352 N=357 N=362 N=367 N=372 N=377 N=382 N=387 N=392 N=397 N=402 N=407 N=412 N=417 N=422 N=427 N=432 N=437 N=442 N=447N=452M=62 M=62 M=63 M=64 M=65 M=65 M=65 M=67 M=67 M=68 M=68 M=69 M=70 M=70 M=71 M=72 M=72 M=72 M=73 M=74 M=74 M=75 M=

57、75 M=76 M=76 M=77 M=77 M=78 M=78 M=78 M=79 M=80 M=80 M=81 M=81 M=82 M=82 M=83 M=83 M=84 M=84 M=85 M=85M=86N=238 N=243 N=248 N=253 N=258 N=263 N=268 N=273 N=278 N=283 N=288 N=293 N=298 N=303 N=308 N=313 N=318 N=323 N=328 N=333 N=338 N=343 N=348 N=353 N=358 N=363 N=368 N=373 N=378 N=383 N=388 N=393 N=

58、398 N=403 N=408 N=413 N=418 N=423 N=428 N=433 N=438 N=443 N=448N=453M=62 M=62 M=63 M=64 M=65 M=65 M=66 M=67 M=67 M=68 M=68 M=69 M=70 M=70 M=71 M=72 M=72 M=72 M=73 M=74 M=74 M=75 M=75 M=76 M=76 M=77 M=78 M=78 M=78 M=78 M=79 M=80 M=80 M=81 M=81 M=82 M=82 M=83 M=83 M=84 M=85 M=85 M=86M=86N=239 N=244 N=

59、249 N=254 N=259 N=264 N=269 N=274 N=279 N=284 N=289 N=294 N=299 N=304 N=309 N=314 N=319 N=324 N=329 N=334 N=339 N=344 N=349 N=354 N=359 N=364 N=369 N=374 N=379 N=384 N=389 N=394 N=399 N=404 N=409 N=414 N=419 N=424 N=429 N=434 N=439 N=444 N=449N=454M=62 M=62 M=63 M=64 M=65 M=65 M=66 M=67 M=67 M=68 M=

60、68 M=69 M=70 M=71 M=71 M=72 M=72 M=73 M=73 M=74 M=74 M=75 M=75 M=76 M=77 M=77 M=78 M=78 M=78 M=79 M=79 M=80 M=81 M=81 M=82 M=82 M=82 M=83 M=84 M=84 M=85 M=85 M=86M=86N=240 N=245 N=250 N=255 N=260 N=265 N=270 N=275 N=280 N=285 N=290 N=295 N=300 N=305 N=310 N=315 N=320 N=325 N=330 N=335 N=340 N=345 N=