全國第三屆研究生數(shù)學(xué)建模競賽題 學(xué)生面試問題

全國第三屆研究生數(shù)學(xué)建模競賽題學(xué)生面試問題

第二炮兵工程學(xué)院:陳智江,李明雨,葉慶摘要

本文研究的學(xué)生面試問題,是在給定學(xué)生數(shù)量的前提下,按照每名學(xué)生的面試組由四名老師組成,且各個(gè)學(xué)生的面試組兩兩不完全相同的要求,研究需要的老師數(shù)量,并求出面試分組方案.為了保證面試的公平性,組織者還提出了四條要求,需要考慮除Y2外使其它三條要求盡量滿足的分配方案.第一問是已知學(xué)生數(shù)量為N,求任意兩個(gè)面試組最多只有一名老師相同的最小老師數(shù)量,我們將此問題轉(zhuǎn)化成一個(gè)0-1規(guī)劃模型,并設(shè)計(jì)了優(yōu)化搜索方法,通過MATLAB編程實(shí)現(xiàn)了最少M(fèi)的近似解.在第二問的解決中,首先對Y1-Y4四個(gè)要求進(jìn)行了分析,并分別建立了相應(yīng)的量化指標(biāo),在此基礎(chǔ)上,建立了一個(gè)多目標(biāo)規(guī)劃模型.針對學(xué)生數(shù)較多,模型求解運(yùn)算量大的問題,特別設(shè)計(jì)了優(yōu)化算法,減少了搜索中的運(yùn)算量.同時(shí),通過討論均衡與公平性的含義,以分目標(biāo)為基礎(chǔ),建立了綜合評價(jià)目標(biāo),以此為指引,使搜索算法更具有針對性.計(jì)算結(jié)果表明,分配方案滿足Y1-Y4的情況是非常好的.第二問中還運(yùn)用組合數(shù)學(xué)中區(qū)組設(shè)計(jì)的理論,論證了N=379,M=24時(shí)不存在完全滿足均衡和公平要求的理想分配方案.第三問中,將老師組分成文,理兩類,首先修改了問題一中的相應(yīng)模型和算法,給出了求解結(jié)果.在第二問中提出了啟發(fā)式-混合交叉算法,從模擬結(jié)果看,分配方案比原第二問中的方案要差些,但總體上在各個(gè)指標(biāo)上滿足的情況也是較好的.第四問首先分析了均勻性與面試公平性的關(guān)系,并提出了公平率的評價(jià)指標(biāo).為了解決學(xué)生與面試?yán)蠋熡刑厥怅P(guān)系,及個(gè)別老師打分過于苛刻或?qū)捤傻膯栴},本文提出了規(guī)避的解決方法.關(guān)鍵詞:多目標(biāo)規(guī)劃算法評價(jià)指標(biāo)

2006年全國研究生數(shù)學(xué)建模競賽一等獎

第二炮兵工程學(xué)院:陳智江,李明雨,葉慶

1.問題重述1.問題重述

某高校采用專家面試的方式進(jìn)行自主招生錄取工作.經(jīng)過初選合格進(jìn)入面試的考生有N人,擬聘請老師M人進(jìn)行面試.每位學(xué)生要分別接受"面試組"的每一位老師的單獨(dú)面試.每個(gè)面試組由4名老師組成.各位老師獨(dú)立地對考生提問并根據(jù)其回答問題的情況給出評分.為了保證面試工作的公平性,組織者提出如下要求:Y1:每位老師面試的學(xué)生數(shù)量應(yīng)盡量均衡;Y2:面試不同考生的"面試組"成員不能完全相同;Y3:兩個(gè)考生的"面試組"中有兩位或三位老師相同的情形盡量的少;Y4:任意兩位老師面試的兩個(gè)學(xué)生集合中出現(xiàn)相同學(xué)生的人數(shù)盡量少.請回答如下問題:問題一:設(shè)考生數(shù)N已知,要求在滿足條件二的情況下,說明聘請老師數(shù)M至少分別應(yīng)為多大,才能做到任兩位學(xué)生的"面試組"都沒有兩位以及三位面試?yán)蠋熛嗤那樾?問題二:請根據(jù)條件一至條件四的要求建立學(xué)生與面試?yán)蠋熤g合理的分配模型,并就N=379,M=24的情形給出每位老師面試學(xué)生名單的具體分配方案,并分析該方案滿足條件一至條件四的情況.問題三:假設(shè)面試?yán)蠋熤欣砜婆c文科的老師各占一半,并且要求每位學(xué)生接受兩位文科與兩位理科老師的面試,請?jiān)诖思僭O(shè)下分別回答問題一與問題二.問題四:請討論考生與面試?yán)蠋熤g分配的均勻性和面試公平性的關(guān)系.為了保證面試的公平性,除了組織者提出的要求外,你們認(rèn)為還有哪些重要因素需要考慮,試給出新的分配方案或建議.

2.模型假設(shè)

根據(jù)題意,可以進(jìn)行如下假設(shè):1.所有參加面試的考生在建模中不作區(qū)分,認(rèn)為是完全一樣的;2.所有面試?yán)蠋熞舱J(rèn)為是沒有差別,完全一樣的;3.只考慮面試分組,不考慮時(shí)間安排.

2006年全國研究生數(shù)學(xué)建模競賽一等獎

1

第二炮兵工程學(xué)院:陳智江,李明雨,葉慶

4.制定分派方案時(shí),只考慮盡量使老師交叉混合,而不考慮學(xué)生的主觀要求.

3.符號約定.

MNN2N3N敏N虧N幸老師總數(shù)學(xué)生總數(shù)遇到兩位老師相同情況的學(xué)生人數(shù)遇到三位老師相同情況的學(xué)生人數(shù)敏感學(xué)生的人數(shù)吃虧學(xué)生的人數(shù)幸運(yùn)學(xué)生的人數(shù)第i個(gè)學(xué)生如果分配給第j位老師面試則此值為1,否則為0第i位老師面試的學(xué)生人數(shù)單獨(dú)一位老師面試學(xué)生人數(shù)的最大值評價(jià)每位老師面試人數(shù)均勻性的指標(biāo)兩位老師共同面試人數(shù)的最大值的最小值

xijIi

ImaxRT

X

2

公平率所有老師之間相同的學(xué)生個(gè)數(shù)的均值所有老師之間相同的學(xué)生個(gè)數(shù)的方差

4.模型建立和分析.4.1問題一

4.1.1分析與建模無論是最多只有一位老師相同還是兩位老師相同,該問題的解決都可以看成滿足一定的約束要求,使得在給定的學(xué)生數(shù)下,尋求最少的聘請老師數(shù).因此,我們把問題抽象為一個(gè)規(guī)劃模型來尋優(yōu).

2006年全國研究生數(shù)學(xué)建模競賽一等獎

2

第二炮兵工程學(xué)院:陳智江,李明雨,葉慶

(1)最多只有一位老師重復(fù)的情況設(shè)xij(xij為0,1變量),取值為1時(shí)表示第i個(gè)學(xué)生分配給第j位老師面試,取值為0時(shí)表示第i個(gè)學(xué)生不分配給第j位老師面試,滿足問題要求的約束首先是每個(gè)學(xué)生面試組的成員數(shù)為4,并且使得任意兩個(gè)學(xué)生的面試組最多只有一名老師重復(fù).目標(biāo)是使聘請老師數(shù)M最小,即

MinM

i1,2,,Nxikxijxisxil4xikxijxhkxhj4k,j,h,l1,2,,M且各不相同i,h1,2,,N,ihxij0或1

(4.1)

針對該模型,我們設(shè)計(jì)了尋優(yōu)算法,采用Matlab編程實(shí)現(xiàn).該算法的流程圖如圖1所示.

M0為設(shè)定的初值

是M=M+1

分別計(jì)算各老師面試的總次數(shù)

按面試總次數(shù)將所有老師排序

否

取排序號為I+1的老師為此學(xué)生面試

結(jié)

束

是

是否所有學(xué)生已被安排完

否

是否所有老師已被安排完

是

取下一個(gè)學(xué)生

判斷任意兩位考生面試組中是否有兩位老師相同

是

圖1尋優(yōu)算法流程圖

表1列出了部分?jǐn)?shù)值,圖2是該數(shù)值的可視化.

2006年全國研究生數(shù)學(xué)建模競賽一等獎

3

第二炮兵工程學(xué)院:陳智江,李明雨,葉慶

表1

學(xué)生人數(shù)1234~5

任兩位學(xué)生的"面試組"都沒有兩位老師相同時(shí)最少的老師數(shù)

學(xué)生人數(shù)67~910~1314~15最少老師人數(shù)11121315學(xué)生人數(shù)16~1718~192021~23最少老師人數(shù)16171819學(xué)生人數(shù)24~2728~3031~3233最少老師人數(shù)20212223

最少老師人數(shù)47910

圖2任兩位學(xué)生的"面試組"都沒有兩位老師相同時(shí)最少的老師數(shù)

(2)最多只有兩位老師重復(fù)的情況同(1)中xij的含義相同,(4.1)式中第一個(gè)約束仍然不變,只是使得任意兩個(gè)學(xué)生的面試組最多只有兩名老師重復(fù).

MinM

xikxijxisxil4i1,,Nk,j,s,l1,,M且各不相同xikxijxilxhkxhjxhl6i,h1,,Nxij0或1表2列出了部分?jǐn)?shù)值,圖3是數(shù)值的可視化.表2

(4.2)

任兩位學(xué)生的"面試組"都沒有三位老師相同時(shí)最少的老師數(shù)

4

2006年全國研究生數(shù)學(xué)建模競賽一等獎

第二炮兵工程學(xué)院:陳智江,李明雨,葉慶

學(xué)生人數(shù)

最少老師人數(shù)

學(xué)生人數(shù)

最少老師人數(shù)

學(xué)生人數(shù)

最少老師人數(shù)

學(xué)生人數(shù)

最少老師人數(shù)

12~34~78~1415~1819

4678910

20~2627~4142~5556~7576~105106~140

111213141516

141~143144~165166~195196~229230~263264~309

171819202122

310~358359~404

2324

圖3任兩位學(xué)生的"面試組"都沒有三位老師相同時(shí)最少的老師數(shù)

4.1.24.1.2結(jié)果分析從圖2,圖3可以看出,隨著學(xué)生人數(shù)增加,最少面試?yán)蠋煍?shù)是增多的;而且隨著老師數(shù)增多,學(xué)生人數(shù)的變化率是加快的,這種趨勢是比較符合直觀經(jīng)驗(yàn)的.但在圖3數(shù)據(jù)中也發(fā)現(xiàn)有個(gè)別不滿足這種情況的點(diǎn).對于原因還未找到,有可能是算法精

2006年全國研究生數(shù)學(xué)建模競賽一等獎

5

第二炮兵工程學(xué)院:陳智江,李明雨,葉慶

度的問題.并且每個(gè)最少面試?yán)蠋煍?shù)上,都有一個(gè)學(xué)生數(shù)的"持續(xù)期".

4.2問題二

4.2.1理想的分派方案的存在性分析

這里我們認(rèn)為理想的分派應(yīng)當(dāng)是同時(shí)嚴(yán)格滿足題中四條要求的分派.通過對Y1~Y4的分析,我們發(fā)現(xiàn)這樣的分配方案就是滿足平衡不完全區(qū)組設(shè)計(jì)要求的某種構(gòu)形.而具有(b,v,r,k,)-構(gòu)形的平衡區(qū)組設(shè)計(jì)的必要條件如定理1[1]:定理1對于一個(gè)平衡不完全區(qū)組設(shè)計(jì),有(4.3)

bkvr和r(k1)(v1)

當(dāng)我們將學(xué)生與老師間的某個(gè)理想分派方案看成一個(gè)平衡區(qū)組設(shè)計(jì)結(jié)果,則學(xué)生數(shù)v,老師數(shù)b,任兩位學(xué)生的"面試組"中相同的個(gè)數(shù)以及每位老師面試的學(xué)生人數(shù)k應(yīng)該滿足(4.3)我們以學(xué)生數(shù)379,.老師數(shù)24進(jìn)行檢驗(yàn),發(fā)現(xiàn)同時(shí)滿足(4.3)式兩個(gè)方程的整數(shù)k是不存在的.這就說明,并不是在任意給定的學(xué)生數(shù)和老師數(shù)下同時(shí)嚴(yán)均存在滿足Y1~Y4的理想方案.通過以上分析可知,當(dāng)N379,M24時(shí),同時(shí)嚴(yán)格滿足四條標(biāo)準(zhǔn)的理想分派是不存在的.基于上述分析,可知四條標(biāo)準(zhǔn)不能同時(shí)嚴(yán)格格滿足四條標(biāo)準(zhǔn)的理想分派是不存在的滿足.那么,若僅以其中某一標(biāo)準(zhǔn)是否嚴(yán)格滿足作為衡量成員交叉混合好壞的唯一依據(jù),可行嗎我們在論證絕對理想的分派是否存在的過程中發(fā)現(xiàn):這四條標(biāo)準(zhǔn)間存在著某些內(nèi)在的微妙的聯(lián)系,僅以一條標(biāo)準(zhǔn)作為衡量依據(jù),一味追求單一標(biāo)準(zhǔn)的嚴(yán)格滿足,將會使其他標(biāo)準(zhǔn)的滿足程度發(fā)生相應(yīng)的改變,這種改變通常是向著不理想的方向發(fā)展的.因此,我們應(yīng)該將四條標(biāo)準(zhǔn)綜合考慮,尋找一種使它們都盡可能滿足的規(guī)則.基于上述分析,我們設(shè)計(jì)了如下模型.根據(jù)對題目中組織者提出的要求的分析,發(fā)現(xiàn)Y2這一要求實(shí)際上是對學(xué)生和老師分配模型作了強(qiáng)制性的限制,可以作為模型中的約束來考慮.而Y1,Y3,Y4條件體現(xiàn)了組織者對面試工作的均衡性和公平性的要求.而根據(jù)實(shí)際經(jīng)驗(yàn)判斷,均衡性和公平性往往是相互矛盾的兩個(gè)方面,因此這個(gè)問題實(shí)際上是一個(gè)多目標(biāo)規(guī)劃問題.建立模型的關(guān)鍵首先需要通過對要求的理解,對每一個(gè)優(yōu)化目標(biāo)進(jìn)行量化,同時(shí)還需要考慮各個(gè)目標(biāo)對整個(gè)分配方案的作用關(guān)系.

2006年全國研究生數(shù)學(xué)建模競賽一等獎

6

第二炮兵工程學(xué)院:陳智江,李明雨,葉慶

4.2.24.2.2對每一個(gè)評價(jià)標(biāo)準(zhǔn)的量化

(1)對于題目給出的條件Y1每位老師面試的人數(shù)完全均衡,是指分配方案中每位老師面試的人數(shù)完全相等.但是在多種目標(biāo)的約束下,完全達(dá)到這個(gè)目標(biāo)是很難的.因此盡量均衡,也就要盡量使每位老師面試人數(shù)與所有老師面試人數(shù)的最大值之比應(yīng)接近1.用一個(gè)量化的指標(biāo)來表示,我們選取上述比值與1之差的平方和取得最小值,即

M

R=Min(

i1

IiImax

1)2

(2)對于題目給出的條件Y2不同考生的"面試組"成員不能完全相同,這是必須滿足的約束條件.對于那些不同學(xué)生的"面試組"的四位老師完全相同的情況,不符合此條件,可以直接排除在本題的思考范圍之外,不進(jìn)行考慮.(3)對于題目給出的條件Y3用任意兩位學(xué)生面試組中三位老師相同的組合數(shù)N3與任意兩名學(xué)生面試分配的總組合數(shù)N之比,來標(biāo)準(zhǔn)化有三位老師相同的情形;用任意兩位學(xué)生面試組中兩位老師相同的組合數(shù)N2與任意兩名學(xué)生面試分配的總組合數(shù)N之比,來標(biāo)準(zhǔn)化有兩位老師相同的情形.可以采用兩種方式來表達(dá)滿足條件Y3的要求.一種是采用優(yōu)先序的方法,另一種是采用兩個(gè)指標(biāo)加權(quán)和來綜合兩個(gè)方面.從公平性的角度來看,我們認(rèn)為優(yōu)先滿足使三位老師相同的情況盡量少,在此基礎(chǔ)上進(jìn)一步要求兩位老師相同的情況盡量少,更能體現(xiàn)公平性的原則.因此,在后面的具體方案計(jì)算中,為了分配搜索中的尋優(yōu),雖然采用兩個(gè)指標(biāo)的加權(quán)和,單是將滿足三個(gè)指標(biāo)時(shí)選的較大.(4)對于題目給出的條件Y4雖然用任意兩個(gè)老師共同面試的學(xué)生個(gè)數(shù)tij中的最大值可以反映Y4的要求,但考慮到即使相同的maxtij值,對不同大小的學(xué)生總數(shù),它反映公平性的程度是不一樣的,因此,這里采用tij除以總學(xué)生數(shù)來反映Y4這一要求,并使該指標(biāo)盡量小,即maxtijT=Min(

i,j

N

)

2006年全國研究生數(shù)學(xué)建模競賽一等獎

7

第二炮兵工程學(xué)院:陳智江,李明雨,葉慶

4.2.34.2.3建立多目標(biāo)規(guī)劃模型

對4.2.1提出的多個(gè)指標(biāo),應(yīng)進(jìn)行綜合考慮.一種可行的方法是將幾個(gè)指標(biāo)按照不同的優(yōu)先級進(jìn)行排序.我們選用的優(yōu)先序依次為z1,z2,z3,z4,如下模型所示:

M

z1minR(

i1

IiImax

1)2

z2

分目標(biāo)

z3z4

N3NNmin2NmaxtijminN

min

(4.3)

z1z12z23z34z4綜合目標(biāo):123412341

xxijxisxil4s.t.ikxij0或1

i1,,Nk,j,s,l1,,M且各不相同

4.2.44.2.4模型求解的算法

(1)模型的思路設(shè)計(jì)由前文,絕對理想的分派是不存在的,僅僅追求單一標(biāo)準(zhǔn)嚴(yán)格滿足的作法也是不可行的,那么,尋找一種使四條標(biāo)準(zhǔn)都盡可能滿足的規(guī)則是當(dāng)前的關(guān)鍵.通常,人們在安排該學(xué)生面試時(shí),總是根據(jù)前幾次面試的安排情況來決定本次面試?yán)蠋煹姆峙?因此,我們從以下兩個(gè)方面出發(fā)進(jìn)行思路設(shè)計(jì):*假設(shè)目前已安排了i1次面試,在安排第i次面試時(shí),首先應(yīng)該根據(jù)每個(gè)老師在前

i1次面試中與學(xué)生見面次數(shù)由多到少的順序,對老師進(jìn)行排序.在制訂分派計(jì)劃時(shí),

應(yīng)以此順序?qū)蠋熂右钥紤].因?yàn)?如果先安排那些同其他老師見面次數(shù)少的人,一旦他們進(jìn)行面試學(xué)生后,再安排那些與學(xué)生見面次數(shù)較多的人時(shí),就會出現(xiàn)無論這些人被分派到哪一組,都有

2006年全國研究生數(shù)學(xué)建模競賽一等獎

8

第二炮兵工程學(xué)院:陳智江,李明雨,葉慶

可能同已見過多次面的老師分在同一組.為避免以上情況發(fā)生,我們應(yīng)優(yōu)先考慮分派那些同學(xué)生見面次數(shù)較多的人.*在老師的優(yōu)先排序方案確定之后,就可以依次對各個(gè)老師的分派加以考慮了.假

1個(gè)老師已被編入面試小組內(nèi),由于第i

定前i

名老師面試不同的學(xué)生產(chǎn)生的效果是

不同的,而效果的好壞又是以四條標(biāo)準(zhǔn)的滿足程度來衡量的.因此,通過對不同面試四條標(biāo)準(zhǔn)滿足程度的對比,可確定究竟將其面試哪一個(gè)學(xué)生.由于這四條標(biāo)準(zhǔn)對某個(gè)老師來說都是限制性的.如果我們希望以四條標(biāo)準(zhǔn)的綜合滿足程度來描述交叉混合好壞的話,則這種綜合滿足程度可看作是各約束條件的一個(gè)方面.于是我們可以通過比較各面試小組對第i名老師綜合滿足程度的大小來決定該組老師應(yīng)去哪個(gè)學(xué)生的面試小組.對某個(gè)老師來說,他最終被編入的面試組必是對他綜合滿足程度最大的組.(2)狀態(tài)變量的定義由于該模型在求解過程中,將某位老師編入哪一位學(xué)生面試組取決于前幾次面試的安排情況,故模型求解的關(guān)鍵就在于如何存儲和利用前幾次面試的安排的的信息.在這里,我們定義"當(dāng)前狀態(tài)"為前幾次面試的安排情況.主要包括以下幾個(gè)方面.前幾次面試的安排中,每位老師面試學(xué)生的個(gè)數(shù).

它是確定面試?yán)蠋焹?yōu)先排序準(zhǔn)則及由見面熟引起的盡量滿足目標(biāo)為Y1的重要因素.Ii表示第i個(gè)老師幾次面試學(xué)生的次數(shù)(i=1,2,……,24).*前幾次面試的安排中,任意兩面試?yán)蠋熤g的相同的學(xué)生次數(shù).它是確定面試?yán)蠋熋嬖嚹莻€(gè)學(xué)生的重要因素.程序中,通過數(shù)組Tij(1ji24)來存儲.Tij表示老師i與老師j在前幾次面試中的相同的學(xué)生次數(shù).*兩個(gè)考生的"面試組"中有兩位或三位老師相同的情形判斷方案優(yōu)劣的一條標(biāo)準(zhǔn).可以作為方案的備選標(biāo)準(zhǔn).(3)流程框圖圖4是整個(gè)算法的框圖,它包括了對面試組的安排以及各種統(tǒng)計(jì)指標(biāo)的計(jì)算輸出.根據(jù)算法,我們用MATLAB7.0編制了程序,見附件1.m,2.m.安排面試?yán)蠋煏r(shí)應(yīng)以各組人數(shù)盡量均衡性,公平性為主要原則.

2006年全國研究生數(shù)學(xué)建模競賽一等獎

9

第二炮兵工程學(xué)院:陳智江,李明雨,葉慶

開

始

數(shù)否達(dá)到面試了379個(gè)學(xué)生否

是

結(jié)

束

計(jì)算不同面試組老師都不同,一個(gè),兩個(gè),三個(gè)相同的組數(shù)初始數(shù)為n=0

計(jì)算每位老師面試的學(xué)生數(shù)量

按照面試學(xué)生的數(shù)量進(jìn)行排序

從小到大產(chǎn)生4位面試?yán)蠋?/p>

判斷該組老師與其他組老師的相同數(shù)為M

是n=n+1

計(jì)算該組老師于以往面試的老師之間相同學(xué)生個(gè)數(shù)的方差

否

判斷該組老師對以往老師之間相同學(xué)生個(gè)數(shù)的方差的影響的大小

對方差大小進(jìn)行排序

選擇最小的一組作為面試組

進(jìn)行新一輪的面試

判

斷n的組數(shù)已經(jīng)用完

圖4面試分組程序流程圖

(4)算法步驟:假設(shè)進(jìn)行了第i個(gè)學(xué)生的面試,判斷i是否達(dá)到要求,如果i=379則結(jié)束,否則繼續(xù)判斷;

2006年全國研究生數(shù)學(xué)建模競賽一等獎

10

第二炮兵工程學(xué)院:陳智江,李明雨,葉慶

依次選擇面試?yán)蠋熛嗤瑐€(gè)數(shù)最少的排序進(jìn)行選擇,如果選擇完畢,則任意兩個(gè)學(xué)生面試?yán)蠋熛嗤瑐€(gè)數(shù)增加1;計(jì)算每位面試?yán)蠋煹拿嬖噷W(xué)生數(shù)量,并按照由小到大的順序進(jìn)行優(yōu)選選擇排序,選擇4位老師作為該學(xué)生的面試?yán)蠋?計(jì)算所有老師之間相同學(xué)生次數(shù)的方差;作為進(jìn)一步選擇的依據(jù);找到最佳的一組老師作為該學(xué)生的面試?yán)蠋?直至滿足所有面試要求結(jié)束;

4.2.54.2.5模型結(jié)果

Y1滿足的情況

每個(gè)老師的面試學(xué)生個(gè)數(shù)Ti(1i24)如表3所示,5為每個(gè)老師的面試學(xué)生圖個(gè)數(shù)的條形圖.表3每個(gè)老師的面試學(xué)生個(gè)數(shù)老師序面試學(xué)生個(gè)數(shù)號123456786363636363636363910111213141516老師序號面試學(xué)生個(gè)老師序號數(shù)63636363686464631718192021222324面試學(xué)生個(gè)數(shù)6363636364636463

2006年全國研究生數(shù)學(xué)建模競賽一等獎

11

第二炮兵工程學(xué)院:陳智江,李明雨,葉慶

70

60

50

40

30

20

10

0

0

5

10

15

20

25

圖5所有老師面試學(xué)生個(gè)數(shù)的統(tǒng)計(jì)圖Y2滿足的情況

兩個(gè)考生的"面試組"中有零位,一位,兩位,三位,四位老師相同的指標(biāo)值如表4所示:表4相同老師數(shù)量的個(gè)數(shù)的組數(shù)相同老師數(shù)量的個(gè)數(shù)該組數(shù)的比值t00.464t10.415t20.120t30.001t40

可以看出該分配方案對滿足沒有三位老師相同的情況是非常好的,但對兩位相同的情況有一定程度的不滿足,但是從綜合評價(jià)指標(biāo)看還是比較優(yōu)的.Y4滿足的情況

任意兩個(gè)老師之間相同的學(xué)生個(gè)數(shù),為一個(gè)23×24的三角矩陣Tij(1ji24)(見附錄1).對Y4滿足的評價(jià)指標(biāo)值為T=0.032.可以看出24位老師面試的學(xué)生數(shù)是相當(dāng)均勻的.

4.2.6模型的結(jié)果分析

2006年全國研究生數(shù)學(xué)建模競賽一等獎

12

第二炮兵工程學(xué)院:陳智江,李明雨,葉慶

分配方案如下:Sij(1i379,1j4)為表示第i個(gè)學(xué)生的第j個(gè)面試?yán)蠋?(見附錄2)(1)公共學(xué)生數(shù)的評估從以上結(jié)果我們可以看出,最小公共學(xué)生數(shù)目為7,最大數(shù)為12,所以公共學(xué)生數(shù)是很小的,而且最大公共學(xué)生數(shù)為12的只有1組.可見公共學(xué)生數(shù)是令人滿意的.(2)公共老師數(shù)的評估本模型最終結(jié)果中,雖然沒能保證公共老師數(shù)沒有,但從見面次數(shù)結(jié)果統(tǒng)計(jì)表來看,各老師之間的見面次數(shù)是比較合理的,沒有出現(xiàn)兩位老師,三位老師共同面試次數(shù)過多的情況.如表4所示.(3)老師工作量在對結(jié)果的分析中,我們發(fā)現(xiàn),老師面試次數(shù)最大的為64,最小的為63,不同老師之間工作量最大之差不超過1,所以老師工作量非常均衡的.綜上所述,該分配方案對Y1-Y4的滿足情況是比較好的.

4.3問題三

在對老師進(jìn)行編組時(shí),作如下規(guī)定:1-12位文科老師,13-24位理科老師;其余條件見以上模型.4.3.1對問題一的模型的重新修改面試?yán)蠋煼殖晌?理兩類后,模型與4.1.1問題一中最大的不同是要求一個(gè)學(xué)生的面試方案中必須包括兩個(gè)文科老師和兩個(gè)理科老師,故約束上需要修改.改進(jìn)后的模型為

MinM

xikxijxisxil4i1,,N,(k,j是文科老師,s,l是理科老師)k,j,s,l1,,M且各不相同xikxijxilxhkxhjxhl6i,h1,,Nxij0或1

2006年全國研究生數(shù)學(xué)建模競賽一等獎

13

第二炮兵工程學(xué)院:陳智江,李明雨,葉慶

4.3.2對問題一的模型的求解結(jié)果及分析表5任兩位學(xué)生的"面試組"都沒有兩位老師相同時(shí)最少的老師數(shù)

學(xué)生人數(shù)123~56~9最少老師人數(shù)481012學(xué)生人數(shù)1011~1415~1718~23最少老師人數(shù)14161820學(xué)生人數(shù)24~2627~33最少老師人數(shù)2224

圖6任兩位學(xué)生的"面試組"都沒有兩位老師相同時(shí)最少的老師

表6任兩位學(xué)生的"面試組"都沒有三位老師相同時(shí)最少的老師數(shù)

學(xué)生人數(shù)12~34~12最少老師人數(shù)468學(xué)生人數(shù)19~3637~6364~112最少老師人數(shù)121416學(xué)生人數(shù)130~182183~230231~313最少老師人數(shù)202224

2006年全國研究生數(shù)學(xué)建模競賽一等獎

14

第二炮兵工程學(xué)院:陳智江,李明雨,葉慶

13~18

10

113~129

18

圖7任兩位學(xué)生的"面試組"都沒有三位老師相同時(shí)最少的老師數(shù)可以看出,求解結(jié)果具有與4.1.2類似的變化結(jié)論.

4.3.3問題3的結(jié)果

兩個(gè)考生的"面試組"中有零位,一位,兩位,三位老師相同的數(shù)量

ti(i0,1,2,3,4)如表7所示.

表7相同老師數(shù)量的個(gè)數(shù)的組數(shù)相同老師數(shù)量的個(gè)數(shù)t0t10.403t20.122t3272t40.004

該組數(shù)在總體中的比值0.471

每個(gè)老師的面試學(xué)生個(gè)數(shù)Ti(1i24)如表8所示.

表8每個(gè)老師的面試學(xué)生個(gè)數(shù)

2006年全國研究生數(shù)學(xué)建模競賽一等獎

15

第二炮兵工程學(xué)院:陳智江,李明雨,葉慶

老師序號12345678

面試學(xué)生個(gè)數(shù)6666666766656463

70

老師序號910111213141516

面試學(xué)生個(gè)數(shù)5858615868626466

老師序號1718192021222324

面試學(xué)生個(gè)數(shù)6165636261656160

60

50

40

30

20

10

0

0

5

10

15

20

25

圖8每位老師的面試學(xué)生個(gè)數(shù)條形圖

任意兩個(gè)老師之間相同的學(xué)生個(gè)數(shù),為一個(gè)23×24的三角矩陣Tij(1ji24)見附錄4.面試分組方案如下:Sij(1i379,1j4)為表示第i個(gè)學(xué)生的第j個(gè)面試?yán)蠋?見附錄3.

2006年全國研究生數(shù)學(xué)建模競賽一等獎

16

第二炮兵工程學(xué)院:陳智江,李明雨,葉慶

4.3.4模型的結(jié)果分析

(1)公共學(xué)生數(shù)的評估從以上結(jié)果我們可以看出,最小公共學(xué)生數(shù)目為4,最大數(shù)為15,所以公共學(xué)生數(shù)是很小的,而且最大公共學(xué)生數(shù)為15的只有3組.可見公共學(xué)生數(shù)是令人滿意的.(2)公共老師數(shù)的評估本模型最終結(jié)果中,雖然沒能保證公共老師數(shù)沒有,但從見面次數(shù)結(jié)果統(tǒng)計(jì)表來看,各老師之間的見面次數(shù)是比較合理的,沒有出現(xiàn)兩位老師,三位老師共同面試次數(shù)過多的情況.如表7所示(3)老師工作量在對結(jié)果的分析中,我們發(fā)現(xiàn),老師面試次數(shù)最大的為67,最小的為58,不同老師之間工作量最大之差不超過9,所以老師工作量是比較均衡的.

4.4問題四

4.4.1假設(shè)與實(shí)際情況的偏差

上述的全部解題過程引用了這樣兩條隱含的假設(shè):一是任何一位老師對任何一名學(xué)生都沒有先入為主的較好或較差印象.二是每一位老師的打分習(xí)慣完全相同,沒有特殊偏好.但是實(shí)際上這兩條假設(shè)并不成立.一是某位老師可能與某名學(xué)生有特殊關(guān)系,面試打分會受到影響.二是每一名老師在實(shí)際的打分過程中有自己的風(fēng)格.對于大多數(shù)老師,面試打分一般會集中在某個(gè)不大的區(qū)間內(nèi).對于這些老師,可以稱為標(biāo)準(zhǔn)型.可能有個(gè)別老師面試打分習(xí)慣性偏低或偏高,其打分值與大多數(shù)老師有顯著差異.偏低的稱為苛刻型老師,偏高的稱為寬松型老師.苛刻型老師和寬松型老師屬于個(gè)別情況,數(shù)量比較少,甚至不一定存在.

4.4.2特殊關(guān)系對公平性的影響

當(dāng)某位老師與某位學(xué)生有特殊關(guān)系的時(shí)候,面試打分可能會受到影響.為確保公平,應(yīng)實(shí)行規(guī)避,不安排這位老師對這名學(xué)生進(jìn)行面試.可以在已經(jīng)生成的分組方案

2006年全國研究生數(shù)學(xué)建模競賽一等獎

17

第二炮兵工程學(xué)院:陳智江,李明雨,葉慶

中進(jìn)行一些局部的調(diào)整,把他與另外一名與他的"面試組"完全不同的學(xué)生對換即可.

4.4.3老師打分偏好對公平性的影響

根據(jù)每一名老師以往參加面試的打分情況,設(shè)這多名老師當(dāng)中第i名老師打分的期望值分別為gi.這次參加面試的某學(xué)生A的面試組成員為第w,x,y,z號老師.組織者和老師對學(xué)生A的情況一無所知.學(xué)生A的面試成績的期望值為.4如果這四位老師都屬于標(biāo)準(zhǔn)型,則這次面試對學(xué)生A是公平的.如果這四位老師當(dāng)中有兩位是苛刻型,而沒有一位是寬松型,則學(xué)生A在這次面試中吃虧.如果這四位老師當(dāng)中有兩位是寬松型,而沒有一位是苛刻型,則學(xué)生A在這次面試中占便宜.如果不考慮老師打分的習(xí)慣,完全隨機(jī)地進(jìn)行分組,不可避免地會有一部分學(xué)生在面試中吃虧,同時(shí)也有一部分學(xué)生在面試中占便宜.如果能夠科學(xué)合理地進(jìn)行分組,把苛刻型老師和寬松型老師進(jìn)行搭配分組,則會相對公平一些.如果完全隨機(jī)地分布,雖然可以避免出現(xiàn)苛刻型老師過度聚集或?qū)捤尚屠蠋熯^度聚集的情況,從而在一定程度上可以避免出現(xiàn)極度不公平現(xiàn)象,但是與此同時(shí),完全隨機(jī)分布也排除了苛刻型老師和寬松型老師搭配分組的合理方案,因此完全隨機(jī)分組的公平性具有局限性.合理的解決方法是在分組過程中對苛刻型老師和寬松型老師搭配分組.只有少數(shù)學(xué)生會遇到"面試組"內(nèi)同時(shí)有兩位苛刻型老師,或同時(shí)有兩位寬松型老師的情況.對于這種比例較小的例外情況,可以使用規(guī)避的方法解決.即在計(jì)算過程中,分組的時(shí)候判斷是否出現(xiàn)了上述情況.遇到苛刻型老師的時(shí)候,優(yōu)先把他與寬松型老師安排在一起.遇到寬松型老師的時(shí)候,優(yōu)先把他與苛刻型老師安排在一起.應(yīng)盡量避免把兩個(gè)苛刻型老師分配到同一個(gè)沒有寬松型老師的小組內(nèi).對于已經(jīng)生成的面試分組方案,要檢測其公平性.對公平性不符合要求的,把吃虧或占便宜的學(xué)生的"面試組"進(jìn)行一下局部的調(diào)整,將多余的苛刻型或?qū)捤尚屠蠋熤脫Q出去,換回同樣數(shù)量的標(biāo)準(zhǔn)型老師.