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

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

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

3、并且要求每位學(xué)生接受兩位文科與兩位理科老師的面試，請(qǐng)?jiān)诖思僭O(shè)下分別回答問題一與問題二。問題四：請(qǐng)考生與面試?yán)蠋熤g分配的均勻性和面試公平性的關(guān)系。為了保證面試的公平性，除了組織者要考慮，試給出新的分配方案或建議。要求外，認(rèn)為還有哪些重要需二、 符號(hào)說(shuō)明xij ： xij 取 1 表示第 i 個(gè)學(xué)生被第 j 位教師面試，0 則表示沒有；STNM ：M 位老師面試 N 個(gè)學(xué)生的分配矩陣；N , M N , M = STNM . . N , M S：矩陣中第 i 個(gè)行向量；iSTNM Tj ： STNM 矩陣中第 j 個(gè)行向量；) ：向量 S 中元素值大于 n 的元素個(gè)數(shù)；n ： n 值向上取整；三

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

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

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

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

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

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

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

11、據(jù)樣本的取值范圍來(lái)選擇，問題中的學(xué)生和面試?yán)蠋煹臄?shù)量的取值區(qū)間是所有整數(shù)，可能是趨向無(wú)窮大的取值，所以模型中用反正切函數(shù)將輸入和輸出數(shù)據(jù)歸一為（0，1）區(qū)間中，最小整數(shù) 1 變?yōu)?0.5，即為網(wǎng)絡(luò)模型輸入的最小值，- 3 -取值區(qū)間為（0.5，1）。(1) 前 500 個(gè)數(shù)據(jù)作為樣本訓(xùn)練模型 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ù)個(gè)數(shù)都為 1，所以網(wǎng)絡(luò)模型的輸入層和輸出層的節(jié)點(diǎn)數(shù)目都為 1，取隱層節(jié)點(diǎn)的數(shù)目為 15，采曲正切 S 型傳遞函數(shù) tansig,優(yōu)化算法為剃度搜索 traigdx，目標(biāo)精度為 0.0000001，最大迭代次數(shù)為 1000，樣本訓(xùn)練模型，用得到的模型對(duì)

13、樣本數(shù)據(jù)的擬合結(jié)果見圖 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.模型對(duì)學(xué)生數(shù)為 379 時(shí)，需要的老師數(shù)量為 78，因此問題 2 中的 24 個(gè)老師的分配需要有一定的分配方案。圖 1訓(xùn)練樣本曲線與BP 網(wǎng)絡(luò)模型擬合結(jié)果(2) 用前 500 個(gè)數(shù)據(jù)作為樣本訓(xùn)練模型易見，模型的精確度非常高，用所得的模型對(duì)問題中

14、的 501 到 700 個(gè)學(xué)生之間的數(shù)據(jù)對(duì)其所需要的老師數(shù)量進(jìn)行- 4 -，所得結(jié)果見圖 2。圖 2測(cè)試樣本曲線與 BP 網(wǎng)絡(luò)模型檢驗(yàn)結(jié)果用 501700 個(gè)學(xué)生的數(shù)據(jù)作為模型檢驗(yàn)樣本 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,.);檢驗(yàn)結(jié)果，見圖 2用所得到的總體 700 個(gè)數(shù)據(jù)（訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)）的散點(diǎn)圖，分析數(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,.);結(jié)果見圖 3（綠型為神經(jīng)網(wǎng)絡(luò)模型的數(shù)據(jù)散點(diǎn)圖型，點(diǎn)型為模型二數(shù)據(jù)的散(3)點(diǎn)圖），數(shù)據(jù)的分布近似為二次曲線，因而可建立問題的模型，以求解問題。- 5 -圖 3 總樣本曲線與BP 網(wǎng)絡(luò)模型結(jié)果(4)模型設(shè)問題 1 學(xué)生數(shù) x ，所需要的最少老師數(shù)量為 y ，從圖中的曲線可以看出模型函數(shù)曲線的形狀，曲線是具有二次曲線 y ax b （ a,b 為系數(shù)）的相似形狀，具有區(qū)間跳躍。隨著 x 的變

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

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

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

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

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

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

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

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

24、，命中的可以進(jìn)一步優(yōu)化的幾率會(huì)較少；- 8 -目標(biāo)條件Y1Y3Y4總計(jì)目標(biāo)最優(yōu)目標(biāo)調(diào)整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) 由于個(gè)目標(biāo)約束數(shù)字表示的數(shù)量級(jí)不同，為了使各個(gè)目標(biāo)在總目標(biāo)中都具有相對(duì)均衡的影響，必須要通過(guò)標(biāo)數(shù)量相對(duì)接近；調(diào)整，是的后各目3) 由于 Y2 是一個(gè)必要目標(biāo)，而非滿意目標(biāo)，故此應(yīng)該把 Y2 作為可行解的判別條件，而非滿意解的判別條件；具體的分配方案見附件數(shù)據(jù) 2。從方案排列以及各目標(biāo)的數(shù)量表示和其他方案下各目標(biāo)的數(shù)量表示比較來(lái)看，可以得出以下幾點(diǎn)：1)對(duì)于 Y1,Y3,Y4 三個(gè)目標(biāo)約束而言，最終方案相較于鄰近方案在三個(gè)目標(biāo)上面都由優(yōu)化（具體表現(xiàn)為三個(gè)

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

27、（即任兩位學(xué)生的“面試組”都沒有兩位（子問題 1）和三位（子問題 2）面試?yán)蠋熛嗤那樾危黾右粋€(gè)新的約束條件，對(duì)于問題一的子問題 1,2，新增加的約束分別為：子問題 1：可以把 STNM 矩陣劃分為兩個(gè) ST矩陣，兩個(gè) ST M 都滿足每行M 2N N2上有且只有兩個(gè) 1，任何兩行不完全相同；（M 為偶數(shù)，下同）子問題 2：可以把 STNM 矩陣劃分為兩個(gè) ST M 矩陣，兩個(gè) ST都滿足每行M 2NN 2上有且只有兩個(gè) 1；問題二：由于文科和理科的老師各占一半，假定可以通過(guò)列交換把文科老師移動(dòng)到 1,M/2 列，理科老師移動(dòng)到 1+M/2,M 列，則有其滿足條件：可以把 STNM 矩陣劃

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

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

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

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

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

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

34、匹配向量，fval 為最少老師的個(gè)數(shù)ticinit_count=3*N+1;% 初始化所需要的老師最大數(shù)量 var_count=init_count*N; %配對(duì)方案的變量個(gè)數(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);%利用每位學(xué)生都對(duì)應(yīng) 4 個(gè)老師，壓縮搜索空間for i=p:2var_count-1 %

35、利用 2 進(jìn)制變換遍歷所有配對(duì)方案空間% 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% 向量轉(zhuǎn)化為配對(duì)方案矩

36、陣stud_teacher(m,(1:init_count)=deploy_instance(m-1)*init_count+1):m*init_count);endconstrA=(sum(stud_teacher)=4); %每個(gè)學(xué)生配對(duì) 4 個(gè)老師if all(constrA) continue;endsum_tow_lines=zeros(N*(N-1)/2,1); s=0;for m=1:N-1% 統(tǒng)計(jì)任意兩個(gè)學(xué)生對(duì)應(yī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)計(jì)需要的老師數(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個(gè)學(xué)生與第j位老師的關(guān)

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表示動(dòng)態(tài)增

39、加教師時(shí)用到的總列數(shù)n = 0; / n表示動(dòng)態(tài)增加學(xué)生時(shí)用到的總列數(shù)10000; / T_nj表示第j位老師面試的學(xué)生數(shù)t_n= newg; n = 1;m = 4;/g表示增加一個(gè)學(xué)生，需要分配給他的老師的號(hào)碼初始值初始值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+)/ 計(jì)算原來(lái)每位老師面試的學(xué)生數(shù)t_nb = 0;for (b = 0; b m; b+)/ 計(jì)算原來(lái)每位老師面試的學(xué)生數(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+) / 計(jì)算分配給新增學(xué)生的第一位教師號(hào)碼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;/ 給新增的學(xué)生指派第一位教師1; / m個(gè)老師init_m_kong - 1;0; e n; e+) / 找出不可添加給學(xué)生n的老師號(hào)碼，并將此/s_mm_kong=for (e老師標(biāo)志為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); %隨機(jī)生成第三個(gè)點(diǎn)的位置 while(c=a)|(c=b)c=ceil(rand()*init_count);endd=ceil(rand()*init_count); % 隨機(jī)生成第四個(gè)點(diǎn)的位置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)計(jì)任意兩位考官面試相同學(xué)生的數(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); % 最大兩位考官面試相同學(xué)生的數(shù)量的值s=0;flag2=0;for m=1:N-1% 統(tǒng)計(jì)任兩位考生中有相同考官的情況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); % 每位考官面試的學(xué)生數(shù)量的標(biāo)準(zhǔn)差 objVal=t1*q1+t3*q2+t4*q3;% 總目標(biāo)值t1 t3 t4if objVal=pr_times*5 ) % opt_solutionxpr_times=pr_times+1;end if(times_countMax_times)break;end每迭代 5 次，打印方案結(jié)果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=