數(shù)學(xué)建模(研究生錄取問題)

PAGE2江蘇師范大學(xué)第五屆（2012）數(shù)學(xué)建模競賽我們選擇的題號是：B題研究生錄取問題我們的參賽隊號為：20120402049B研究生錄取問題問題的重述某學(xué)校M系計劃招收10名計劃內(nèi)研究生，依照有關(guān)規(guī)定由初試上線的前15名學(xué)生參加復(fù)試，專家組由8位專家組成。在復(fù)試過程中，要求每位專家對每個參加復(fù)試學(xué)生的以上5個方面都給出一個等級評分，從高到低共分為A,B,C,D四個等級，并將其填入面試表內(nèi)。所有參加復(fù)試學(xué)生的初試成績、各位專家對學(xué)生的5個方面專長的評分見附件表(1)～表(8)所示。(1)首先，請你綜合考慮學(xué)生的初試成績、復(fù)試成績等因素，幫助主管部門確定10名研究生的錄取名單。然后，要求被錄取的10名研究生與10名導(dǎo)師之間做雙向選擇，即學(xué)生可根據(jù)自己的專業(yè)發(fā)展意愿（依次申報2個專業(yè)志愿，如表(10)所示）、導(dǎo)師的基本情況和導(dǎo)師對學(xué)生的期望要求來選擇導(dǎo)師；導(dǎo)師根據(jù)學(xué)生所報專業(yè)志愿、專家組對學(xué)生專長的評價和自己對學(xué)生的期望要求等來選擇學(xué)生。請你給出一種10名研究生和導(dǎo)師之間的最佳雙向選擇方案（并不要求一名導(dǎo)師只帶一名研究生），使師生雙方的滿意度最大。(2)根據(jù)上面已錄取的10名研究生的專業(yè)志愿（見附件表（10）），如果每一位導(dǎo)師只能帶一名研究生，請你給出一種10名導(dǎo)師與10名研究生雙向選擇的最佳方案，使得師生雙方盡量都滿意。(3)如果由10位導(dǎo)師根據(jù)初試的成績及專家組的面試評價和他們自己對學(xué)生的要求條件錄取研究生，那么10名研究生的新錄取方案是什么？為簡化問題，假設(shè)沒有申報專業(yè)志愿，請你給出這10名研究生各申報一名導(dǎo)師的策略和導(dǎo)師各選擇一名研究生的策略。相互選中的即為確定；對于剩下的導(dǎo)師和學(xué)生，再按上述辦法進(jìn)行雙向選擇，直至確定出每一名導(dǎo)師帶一名研究生的方案，使師生都盡量滿意。(4)學(xué)校在確定研究生導(dǎo)師的過程中，要充分考慮學(xué)生的申報志愿情況。為此，學(xué)校要求根據(jù)10名導(dǎo)師和15名學(xué)生的綜合情況選擇5名導(dǎo)師招收研究生，再讓這5名導(dǎo)師在15名學(xué)生中擇優(yōu)錄取10名研究生。請你給出一種導(dǎo)師和研究生的選擇（錄?。┓桨?，以及每一名導(dǎo)師帶2名研究生的雙向選擇最佳策略。(5)請你設(shè)計一種更能體現(xiàn)“雙向選擇”的研究生錄取方案，提供給主管部門參考，并說明你的方案的優(yōu)越性。目錄模型的假設(shè)……4問題的解決及方法………………4問題一的求解………………4問題二的求解………………7問題三的求解………………9問題四的求解………………11問題五的求解………………14三、模型的評價………16四、附錄………………18一、模型的假設(shè)假設(shè)模型中各部分（如成績、導(dǎo)師水平各方面、導(dǎo)師對學(xué)生要求等）所占權(quán)重和具體水平的量化在錄取工作之前已對導(dǎo)師、學(xué)生和社會完全公開，體現(xiàn)了公平、公正和公開。本模型假定，作為某學(xué)生甲，他對導(dǎo)師A的滿意程度，不會因?yàn)閷?dǎo)師A帶的學(xué)生數(shù)增加而改變。同時假定，某導(dǎo)師A對學(xué)生的滿意程度是相互獨(dú)立，且不會因?yàn)樗鶐W(xué)生數(shù)多少而改變。4、每一導(dǎo)師和學(xué)生配對產(chǎn)生的總合意指數(shù)是相互獨(dú)立，且可以疊加。二、問題解決及方法1、問題一的求解最大匹配：定義：存在V的兩個子集V1和V2，使得每條邊有一個頂點(diǎn)屬于則稱V1，而另一個頂點(diǎn)屬于V2，則稱圖G(V,E)為二部圖。V1和V2:V1表示有導(dǎo)師組成的集合，V2表示所有學(xué)生組成的集合。N，M：分表示系統(tǒng)中考生和導(dǎo)師的個數(shù)，N=|V1|，M=|V2|。（1）圖G是加權(quán)二部圖，且兩個頂點(diǎn)集合為V1和V2。（2）V1和V2均有a個 1 51 5 1 5 2 62 6 2 6 3 73 7 3 74 8 4 8 4 8 a．匹配圖a．匹配圖b．非匹配圖c．完美匹配圖（3）對于每個頂點(diǎn)u∈V1和u∈V2，則邊e=（u，v）存在。在上述假定下，將每個頂點(diǎn)組合，可以得到n！個完美匹配。假設(shè)（3）是合理的，因?yàn)槿绻麑?dǎo)師和學(xué)生能各取所需，可將它們之間的效益權(quán)重定義為o，記u1，u2…，un是V的頂點(diǎn)，v1，v2…，vn是V的頂點(diǎn)，定義wij是ui到vj的權(quán)重，因此全矩陣為W=（wij）。還有稱完美匹配M*是最優(yōu)的，如果對所有的完美匹配M有我們可以用枚舉法，得到最大完美匹配，M*={（u1，v1），（u2，v3），（u3，v2）}下面要綜合考慮學(xué)生初試成績、復(fù)試成績等因素選出10名考生。用平均分的思想解決得到前十位學(xué)生。將靈活性、創(chuàng)造性、知識性、表達(dá)力、外語各分配相應(yīng)的分?jǐn)?shù)，A等為1分，B等為0.75分，C等為0.5分，D等為0.25分，學(xué)生/專家專家1專家2專家3專家4專家5專家6專家7專家8平均數(shù)百分比學(xué)生14.504.504.004.254.754.004.004.504.31250.07679學(xué)生24.004.004.504.504.254.504.504.254.31250.07679學(xué)生33.004.003.254.004.004.003.753.753.71870.06622學(xué)生44.253.253.753.753.503.004.003.753.65620.06510學(xué)生54.003.753.753.504.254.503.753.253.84360.06844學(xué)生63.503.254.003.003.503.754.253.253.56250.06343學(xué)生73.753.253.753.003.003.253.503.753.40620.06065學(xué)生84.254.003.753.754.253.753.003.003.71870.06622學(xué)生94.004.003.754.003.753.254.004.003.84370.06844學(xué)生103.003.003.503.253.253.003.003.003.12500.05564學(xué)生113.253.753.502.753.253.753.253.503.37500.06010學(xué)生124.254.503.754.004.253.754.004.004.06250.07234學(xué)生133.253.753.004.503.253.503.504.253.62500.06455學(xué)生143.254.503.504.003.004.003.253.503.62500.06455學(xué)生153.753.754.253.754.003.754.504.003.96870.07067平均數(shù)表示的是8個專家對學(xué)生的平均看法，這樣可以很好的的到一個學(xué)生的整體評價，平均數(shù)是由8個專家給出的總分除以8*5=40這個總分。百分比得出每位學(xué)生在15名學(xué)生中名次。再依據(jù)筆試成績算取平均分：學(xué)生/專家筆試成績百分比學(xué)生14160.072259858學(xué)生24100.071217648學(xué)生34050.07034914學(xué)生43970.068959528學(xué)生53920.06809102學(xué)生63890.067569915學(xué)生73850.066875109學(xué)生83820.066354004學(xué)生93800.066006601學(xué)生103780.065659197學(xué)生113770.065485496學(xué)生123720.062532569學(xué)生133600.062532569學(xué)生143580.062185166學(xué)生153560.061837763這樣算又得到一個新的排序，再將15名學(xué)生的名次按照筆試成績算出。學(xué)生/專家總比名次學(xué)生10.1490548581學(xué)生20.1480126482學(xué)生30.136570143學(xué)生40.1340685287學(xué)生50.136538024學(xué)生60生70.12753210911學(xué)生80.1325750048學(xué)生90.1344536016學(xué)生100.12130719715學(xué)生110.12558549614學(xué)生120.1348755695學(xué)生130.12708456912學(xué)生140.12673716613學(xué)生150.1325107639最終選取的學(xué)生為：學(xué)生/專家總比名次學(xué)生10.14905491學(xué)生20.14801262學(xué)生30.13657013學(xué)生50.1365384學(xué)生120.13487565學(xué)生90.13445366學(xué)生40.13406857學(xué)生80.1325758學(xué)生150.13251089學(xué)生60.131008910學(xué)生70.127532111學(xué)生130.127084612學(xué)生140.126737213學(xué)生110.125585514學(xué)生100.121307215將兩者的百分比相疊加則得到每位學(xué)生通過筆試成績和專家評價得出其在總體名次，以此得到學(xué)生的排名，來選出前十名學(xué)生。本模型將全部的師生雙方的滿意度用總體合意指數(shù)矩陣中的元素和來度量，選擇最佳的方案，即等價于尋找在約束下的一個最大匹配。本問題可以歸結(jié)為非嚴(yán)格一對多的最優(yōu)匹配問題： 其中，，表示第個學(xué)生和第個導(dǎo)師間的配對關(guān)系。具體含義：。（下同）此問題的求解比較容易，只要選出每一行的最大數(shù)就行了。也即對于中的每個行，，令，即表示第個學(xué)生和第個導(dǎo)師標(biāo)搭配。經(jīng)過次后得到的方案，即為最優(yōu)方案。導(dǎo)師組情況確定學(xué)生面試成績中各方面的比重，如下式：,問題一最終答案：學(xué)生123512948156導(dǎo)師46368195172、問題二的求解G是加權(quán)完全二分圖，V(G)的二分圖劃分為U，V；U={u1,...,un},V={v1,v2,...vn},w(uivi)>=0是學(xué)生ui對vi導(dǎo)師的匹配度，求權(quán)最大的完備匹配，這種完備匹配稱為最佳匹配。用窮舉法的話舉也舉死了，效率很低。引入一個定義和一個定理。

定義1：映射l:V(G)->R，滿足：任意u∈U,任意v∈V,成立

l(u)+l(v)>=w(uv),則稱l(v)是二分圖G的可行頂標(biāo)；令El={uv|uv∈E(G),l(u)+l(v)=w(uv)},稱以El為邊集的G之生成子圖為相等子圖，記為Gl

可行頂標(biāo)是存在的，例如l(u)=mauw(uv),u∈U;l(v)=0,v∈V.

定理1：Gl的完備匹配即為G的最佳匹配。

證：設(shè)M*是Gl的一個完備匹配，因Gl是G的生成子圖，故M*也是G的完備匹配。M*中的邊之端點(diǎn)集合含G的每個頂點(diǎn)恰一次，所以

W(M*)=Σw(e)=Σl(v)(e∈M*,v∈V(G)).

另一方面，若M是G中任意一個完備匹配，則W(M)=Σw(e)<=Σl(v)(e∈M,v∈V(G)),所以W(M*)>=W(M)，即M*是最佳匹配，證畢。

定理1告知，欲求二分圖的最佳匹配，只需用匈牙利算法求取其相等子圖的完備匹配；當(dāng)Gl中無完備匹配時則需要Kuhn和Mantras給出修改頂標(biāo)的一個算法，使新的相等子圖的最大匹配逐漸擴(kuò)大，最后出現(xiàn)相等子圖的完備匹配。

Kuhn-Mantras算法：

(0)選定初始的可行頂標(biāo)l,確定Gl,在Gl中選取一個匹配M。

(1)U中頂皆被M許配，止，M即為最佳匹配；否則，取Gl中未被M許配的頂u,令S={u},T為空。

(2)若N(S)真包含T，轉(zhuǎn)(3)；若N(S)=T，取

al=min(l(u)+l(v)-w(uv)}(u∈S,v∈T),

l(v)-al,v∈S;

l(v)=l(v)+al,v∈T;

l(v),其它。

l=l,Gl=Gl。

(3)選N(S)-T中一頂v,若v已被M許配，且vz∈M,則S=S∪{z},T=T∪{v},轉(zhuǎn)(2)；否則，取Gl中一個M的可增廣軌P(u,v),令M=M⊙E(P)，轉(zhuǎn)(1)。

下面我們就將學(xué)生和老師的匹配算進(jìn)去

已知K10,10的權(quán)矩陣為

v1v2v3v4v5v6v7v8v9v10

u1355415355

u2220224566

u3244160325

u4011002423

u5121332725

u6331042168

u7221546216u8135202142u9234123245u10223133413求最佳匹配，其中K5,5的頂劃分為U={ui},V={vi},i=1,2,3,4,5.

解：(1)取可行頂標(biāo)l(v)為l(vi)=0,i=1,2,3,4,5；l(u1)=mau(3,5,5,4,1}=5,l(u2)=mau{2,2,0,2,2}=2,l(u3)=mau(2,4,4,1,0}=4,l(u4)=mau{0,1,1,0,0}=1,l(u5)=mau{1,2,1,3,3}=3.

(2)Gl及其上之匹配見附錄，這個圖中ο(G-u2)=3,由Tutte定理知無完備匹配。需要修改頂標(biāo)。(3)u=u4,得S={u4,u3,u1},T={v3,v2},N(S)=T,于是

al=min(l(u)+l(v)-w(uv)}=1.(u∈S,v∈T)

u1,u2,u3,u4,u5的頂標(biāo)分別修改成4,2,3,0,3；v1,v2,v3,v4,v5的頂標(biāo)分別修改成0,1,1,0,0。(4)用修改后的頂標(biāo)l得Gl及其上面的一個完備匹配如圖7.13。圖中粗實(shí)線給出了一個最佳匹配，其最大權(quán)是2+4+1+4+3=14。

我們看出：al>0；修改后的頂標(biāo)仍是可行頂標(biāo)；Gl中仍含Gl中的匹配M；Gl中至少會出現(xiàn)不屬于M的一條邊，所以會造成M的逐漸增廣。得到可行頂標(biāo)后求最大匹配：書上這部分沒講，實(shí)際上是這樣的，對于上面這個例子來說，通過Kuhn-Munkres得到了頂標(biāo)l(u)={4,2,3,0,3},l(v)={0,1,1,0,0},那么，對于所有的l(ui)+l(vj)=w(i,j)，在二分圖G設(shè)置存在邊w(i,j)。再用匈牙利算法求出最大匹配，再把匹配中的每一邊的權(quán)值加起來就是最后的結(jié)果了第二題最終答案：學(xué)生123512948156導(dǎo)師463871952103、問題三的求解假如師生雙方一開始采用該策略，則每一步配對的總體合意指數(shù)都是選最大的。最后的配對方案可以具體分為個步驟確定。步驟如下：Step0：初始化，將個學(xué)生和個導(dǎo)師標(biāo)記為未分配。Step1：求解。令，并將第個學(xué)生和第個導(dǎo)師標(biāo)記為分配，即兩者配對?！貜?fù)求解……直至做完Step，即找到一種雙向互動選擇的分配方案。結(jié)果如下表：動態(tài)相互選擇步驟序號匹配的學(xué)生匹配的導(dǎo)師雙方配對的合意指數(shù)1學(xué)生9導(dǎo)師30.732學(xué)生3導(dǎo)師20.623學(xué)生1導(dǎo)師40.554學(xué)生2導(dǎo)師60.535學(xué)生4導(dǎo)師90.466學(xué)生12導(dǎo)師70.397學(xué)生8導(dǎo)師50.398學(xué)生5導(dǎo)師80.359學(xué)生7導(dǎo)師100.3310學(xué)生6導(dǎo)師10.1匹配結(jié)果如下，其總體合意指數(shù)和為：4.45。由于在每一輪的確定和重新選擇中，可能丟失許多數(shù)值較大的總體合意指數(shù)，所以得到最優(yōu)方案的指標(biāo)值明顯又小于問題1、2中的方案。 作為導(dǎo)師或?qū)W生，其策略在于：想在動態(tài)的雙向選擇中求得自己的最優(yōu)配對結(jié)果，要在每一輪中根據(jù)新的尋找自己所在行或列最大數(shù)值所在的位置，數(shù)值最大即兼顧了自己滿足程度最大和配對成功可能性最大的綜合。那么該位置便可為指導(dǎo)自己在本輪進(jìn)行選擇。問題三的最終答案：導(dǎo)師1導(dǎo)師2導(dǎo)師3導(dǎo)師4導(dǎo)師5導(dǎo)師6導(dǎo)師7導(dǎo)師8導(dǎo)師9導(dǎo)師10學(xué)生10.140.170.230.250.470.260.190.170.120.07學(xué)生20.370.400.490.090.050.530.420.390.120.07學(xué)生30.590.620.670.220.170.060.030.020.080.04學(xué)生40.110.120.160.060.030.190.140.120.460.34學(xué)生50.120.140.190.240.190.460.370.350.100.05學(xué)生60.100.120.150.060.030.390.330.300.210.13學(xué)生80.110.140.180.470.390.060.030.020.250.15學(xué)生90.630.650.730.070.040.220.170.140.090.05學(xué)生70.290.300.360.050.030.050.020.010.440.33學(xué)生120.130.150.210.080.050.490.390.370.280.204、問題四的求解首先確定篩選方案，學(xué)校選擇5名導(dǎo)師，需要考慮的因素是學(xué)生申報志愿與導(dǎo)師的專業(yè)方向的吻合度、導(dǎo)師的學(xué)術(shù)水平指標(biāo)、學(xué)生專業(yè)水平與導(dǎo)師對學(xué)生期望之間的吻合度。見以下AHP模型表示圖：學(xué)校選導(dǎo)師的標(biāo)準(zhǔn)由于對5位導(dǎo)師的選擇影響到后面由這5位導(dǎo)師選擇接收研究生的結(jié)果，考慮到雙向選擇這一大局，要求盡量公正客觀的選擇出這五位導(dǎo)師。對于第1個因素，考慮整體學(xué)生的專業(yè)發(fā)展意愿：第一志愿占的權(quán)重為3/5，第二志愿占的權(quán)重比為2/5.則：專業(yè)（1）（2）（3）（4）志愿1（個數(shù)）4353志愿2（個數(shù)）5343根據(jù)權(quán)重可算得：專業(yè)（1）（2）（3）（4）比重0.3980.2000.2020.200所需導(dǎo)師數(shù)2111對于第2個因素，考慮到導(dǎo)師的總體學(xué)術(shù)水平由四方面（發(fā)表論文數(shù)、論文檢索數(shù)、編（譯）著作數(shù)和科研項(xiàng)目數(shù)）體現(xiàn)。然后，要求被錄取的10名研究生與5名導(dǎo)師之間做雙向選擇，為了更好體現(xiàn)師生間的雙向選擇過程，這里用學(xué)生對導(dǎo)師的滿意指數(shù)矩陣和導(dǎo)師對學(xué)生的滿意指數(shù)矩陣，來表示他們的滿意程度。 根據(jù)前面定義，我們可以算出各滿意指數(shù)矩陣如下：問題4中學(xué)生對導(dǎo)師的滿意指數(shù)矩陣導(dǎo)師3導(dǎo)師2導(dǎo)師6導(dǎo)師1導(dǎo)師8學(xué)生10.390.20.480.210.31學(xué)生20.640.450.730.460.56學(xué)生30.880.710.230.710.07學(xué)生40.380.20.480.210.32學(xué)生50.380.20.730.210.57學(xué)生60.380.210.730.210.57學(xué)生70.640.450.240.470.06學(xué)生80.390.210.230.210.06學(xué)生90.890.70.480.710.31學(xué)生100.630.470.740.460.57學(xué)生110.630.460.220.450.07學(xué)生120.390.20.730.210.56學(xué)生130.630.460.230.460.07學(xué)生140.880.710.480.710.32學(xué)生150.880.70.230.710.07問題4中導(dǎo)師對學(xué)生的滿意指數(shù)矩陣導(dǎo)師3導(dǎo)師2導(dǎo)師6導(dǎo)師1導(dǎo)師8學(xué)生10.610.60.770.60.76學(xué)生20.750.740.910.740.89學(xué)生30.790.790.460.790.46學(xué)生40.40.380.560.390.55學(xué)生50.410.40.750.410.74學(xué)生60.340.340.670.340.67學(xué)生70.470.440.290.460.27學(xué)生80.360.340.350.340.33學(xué)生90.690.680.510.680.51學(xué)生100.410.430.590.410.58學(xué)生110.420.440.250.430.28學(xué)生120.320.310.650.320.65學(xué)生130.350.340.170.360.18學(xué)生140.520.510.340.510.34學(xué)生150.550.540.210.560.22經(jīng)過計算機(jī)求解得這五名導(dǎo)師為：導(dǎo)師序號專業(yè)方向最終分?jǐn)?shù)（排名）導(dǎo)師310.71072導(dǎo)師940.59524導(dǎo)師110.47857導(dǎo)師420.42976導(dǎo)師630.42143導(dǎo)師1040.41666導(dǎo)師210.35596導(dǎo)師730.24157導(dǎo)師520.21310導(dǎo)師830.13691按照問題要求，一名導(dǎo)師配對2名學(xué)生，由5名導(dǎo)師和15名學(xué)生（1對2）得到10個配對的方案。該最優(yōu)匹配問題表述為： 具體過程可運(yùn)用最大匹配問題的廣義匈牙利算法可以求解。復(fù)制的總體合意指數(shù)矩陣，輸入合成新的矩陣，其中0表示的零矩陣。即可得到匹配結(jié)果。問題四最終答案：導(dǎo)師3導(dǎo)師2導(dǎo)師6導(dǎo)師1導(dǎo)師8學(xué)生10.240.120.370.130.24學(xué)生20.480.330.670.340.50學(xué)生30.700.550.110.560.03學(xué)生40.150.080.270.080.17學(xué)生50.160.080.550.090.42學(xué)生60.130.070.490.070.38學(xué)生70.300.200.070.210.02學(xué)生80.140.070.080.070.02學(xué)生90.610.480.250.490.16學(xué)生100.260.200.440.190.33學(xué)生110.260.200.060.200.02學(xué)生120.120.060.480.070.36學(xué)生130.220.160.040.160.01學(xué)生140.460.370.170.360.11學(xué)生150.480.380.050.400.01問題五的求解一名導(dǎo)師最多可配對名學(xué)生的分配方案推廣的模型：（10名導(dǎo)師，15名學(xué)生）1對1得到10個配對的方案。 保持第（1）問至第（3）問中的權(quán)重不變，可以求出15名學(xué)生與10名導(dǎo)師之間配對的總體合意指數(shù)矩陣：15名學(xué)生與10名導(dǎo)師之間配對的總體合意指數(shù)矩陣導(dǎo)師1導(dǎo)師2導(dǎo)師3導(dǎo)師4導(dǎo)師5導(dǎo)師6導(dǎo)師7導(dǎo)師8導(dǎo)師9導(dǎo)師10學(xué)生10.140.180.270.650.580.350.280.260.200.15學(xué)生20.350.400.520.110.070.650.550.530.190.14學(xué)生30.580.630.740.270.230.100.050.040.150.12學(xué)生40.090.120.170.070.050.260.200.190.600.54學(xué)生50.090.120.180.250.210.530.450.440.140.10學(xué)生60.080.100.150.070.040.470.420.390.290.25學(xué)生70.220.240.320.050.030.060.030.020.510.47學(xué)生80.080.100.160.470.420.070.040.030.300.25學(xué)生90.500.540.650.070.040.240.190.170.110.08學(xué)生100.190.240.280.050.030.420.360.350.090.06學(xué)生110.200.240.280.050.030.050.040.030.490.44學(xué)生120.070.090.140.060.040.460.400.380.280.24學(xué)生130.170.190.240.350.320.040.020.020.060.04學(xué)生140.370.410.480.040.020.160.130.120.060.04學(xué)生150.410.430.510.170.140.040.030.020.070.05求解過程，類似第（4）問，運(yùn)用最大匹配問題的廣義匈牙利算法可以求解。由的總體合意指數(shù)矩陣，輸入合成新的矩陣，其中0表示的零矩陣。運(yùn)行程序，即可得到匹配結(jié)果。具體為：新方案的匹配結(jié)果表導(dǎo)師1導(dǎo)師2導(dǎo)師3導(dǎo)師4導(dǎo)師5導(dǎo)師6導(dǎo)師7導(dǎo)師8導(dǎo)師9導(dǎo)師10學(xué)生10.140.180.270.650.580.350.280.260.200.15學(xué)生20.350.400.520.110.070.650.550.530.190.14學(xué)生30.580.630.740.270.230.100.050.040.150.12學(xué)生40.090.120.170.070.050.260.200.190.600.54學(xué)生50.090.120.180.250.210.530.450.440.140.10學(xué)生60.080.100.150.070.040.470.420.390.290.25學(xué)生70.220.240.320.050.030.060.030.020.510.47學(xué)生80.080.100.160.470.420.070.040.030.300.25學(xué)生90.500.540.650.070.040.240.190.170.110.08學(xué)生100.190.240.280.050.030.420.360.350.090.06學(xué)生110.200.240.280.050.030.050.040.030.490.44學(xué)生120.070.090.140.060.040.460.400.380.280.24學(xué)生130.170.190.240.350.320.040.020.020.060.04學(xué)生140.370.410.480.040.020.160.130.120.060.04學(xué)生150.410.430.510.170.140.040.030.020.070.05總體合意指數(shù)和為：5.34。比上述的四種方案對應(yīng)的總體合意指數(shù)和都高。 對于上述這種研究生錄取方案，避免了前四種錄取方式的分步驟進(jìn)行，直接通過總體合意指數(shù)矩陣，運(yùn)用匈牙利算法求解最大匹配問題。降低了錄取工作中間過程的低效，同樣也擴(kuò)大了導(dǎo)師和學(xué)生配對時選擇人選的范圍。模型最后的結(jié)果總體合意指數(shù)和（5.34）也明顯優(yōu)于前四種方案（5.19、4.64和4.45）各種方案對比表方案序號方案內(nèi)容總體合意指數(shù)和1先選10名學(xué)生，再1：多配對5.192先選10名學(xué)生，再1：1配對4.643先導(dǎo)師組選10名學(xué)生，再1：1配對4.454先選5名導(dǎo)師，再1：2配對4.455只進(jìn)行1：1配對5.34（MAX）三、模型的評價優(yōu)點(diǎn)：1.以總體的最大滿意度為主要優(yōu)化目標(biāo)，同時考慮分配方案的穩(wěn)定性，比較符合實(shí)際情況。2.主要模型為采用圖論中加權(quán)二分圖的最大權(quán)匹配問題，計算復(fù)雜度低，量級為O(Nlog2N)3．模型的擴(kuò)展性比較好，可以直接移植到工作指派等問題。缺點(diǎn)：1.關(guān)于滿意度的計算參數(shù)比較多，具體參數(shù)的確定主觀性較強(qiáng)。四、附錄最優(yōu)匹配(Kuhn_Munkras算法)//**StartofPerfectMatch*******************************//Name:PerfectMatchbyKuhn_MunkrasO(n^3)//Description:wistheadjacencymatrix,nx,nyarethesizeofxandy,//lx,lyarethelablesofxandy,fx[i],fy[i]isusedformarking//whetherthei-thnodeisvisited,matx[x]meansxmatchmatx[x],//maty[y]meansymatchmaty[y],actually,matx[x]isuseless,//allthearraysarestartat1intnx,ny,w[MAXN][MAXN],lx[MAXN],ly[MAXN];intfx[MAXN],fy[MAXN],matx[MAXN],maty[MAXN];int