数学建模(研究生录取问题).doc
- 文档编号:15918575
- 上传时间:2023-07-09
- 格式:DOC
- 页数:18
- 大小:408.04KB
数学建模(研究生录取问题).doc
《数学建模(研究生录取问题).doc》由会员分享,可在线阅读,更多相关《数学建模(研究生录取问题).doc(18页珍藏版)》请在冰点文库上搜索。
江苏师范大学
第五届(2012)数学建模竞赛
我们选择的题号是:
B题研究生录取问题
我们的参赛队号为:
20120402049
B研究生录取问题
问题的重述
某学校M系计划招收10名计划内研究生,依照有关规定由初试上线的前15名学生参加复试,专家组由8位专家组成。
在复试过程中,要求每位专家对每个参加复试学生的以上5个方面都给出一个等级评分,从高到低共分为A,B,C,D四个等级,并将其填入面试表内。
所有参加复试学生的初试成绩、各位专家对学生的5个方面专长的评分见附件表
(1)~表(8)所示。
(1)首先,请你综合考虑学生的初试成绩、复试成绩等因素,帮助主管部门确定10名研究生的录取名单。
然后,要求被录取的10名研究生与10名导师之间做双向选择,即学生可根据自己的专业发展意愿(依次申报2个专业志愿,如表(10)所示)、导师的基本情况和导师对学生的期望要求来选择导师;导师根据学生所报专业志愿、专家组对学生专长的评价和自己对学生的期望要求等来选择学生。
请你给出一种10名研究生和导师之间的最佳双向选择方案(并不要求一名导师只带一名研究生),使师生双方的满意度最大。
(2)根据上面已录取的10名研究生的专业志愿(见附件表(10)),如果每一位导师只能带一名研究生,请你给出一种10名导师与10名研究生双向选择的最佳方案,使得师生双方尽量都满意。
(3)如果由10位导师根据初试的成绩及专家组的面试评价和他们自己对学生的要求条件录取研究生,那么10名研究生的新录取方案是什么?
为简化问题,假设没有申报专业志愿,请你给出这10名研究生各申报一名导师的策略和导师各选择一名研究生的策略。
相互选中的即为确定;对于剩下的导师和学生,再按上述办法进行双向选择,直至确定出每一名导师带一名研究生的方案,使师生都尽量满意。
(4)学校在确定研究生导师的过程中,要充分考虑学生的申报志愿情况。
为此,学校要求根据10名导师和15名学生的综合情况选择5名导师招收研究生,再让这5名导师在15名学生中择优录取10名研究生。
请你给出一种导师和研究生的选择(录取)方案,以及每一名导师带2名研究生的双向选择最佳策略。
(5)请你设计一种更能体现“双向选择”的研究生录取方案,提供给主管部门参考,并说明你的方案的优越性。
目录
一、模型的假设……………………………………4
二、问题的解决及方法………………………………4
1、问题一的求解………………………………4
2、问题二的求解………………………………7
3、问题三的求解………………………………9
4、问题四的求解………………………………11
5、问题五的求解………………………………14
三、模型的评价………………………………………16
四、附录………………………………………………18
一、模型的假设
1.假设模型中各部分(如成绩、导师水平各方面、导师对学生要求等)所占权重和具体水平的量化在录取工作之前已对导师、学生和社会完全公开,体现了公平、公正和公开。
2.本模型假定,作为某学生甲,他对导师A的满意程度,不会因为导师A带的学生数增加而改变。
3.同时假定,某导师A对学生的满意程度是相互独立,且不会因为所带学生数多少而改变。
4、每一导师和学生配对产生的总合意指数是相互独立,且可以叠加。
二、问题解决及方法
1、问题一的求解
最大匹配:
定义:
存在V的两个子集V1和V2,使得每条边有一个顶点属于则称V1,而另一个顶点属于V2,则称图G(V,E)为二部图。
V1和V2:
V1表示所有导师组成的集合,V2表示所有学生组成的集合。
N,M:
分别表示系统中考生和导师的个数,N=|V1|,M=|V2|。
(1)图G是加权二部图,且两个顶点集合为V1和V2。
(2)V1和V2均有a个 1 5
1 5 1 5 2 6
2 6
2 6 3 7
3 7 3 7
4 8 4 8 4 8
a.匹配图
b.非匹配图
c.完美匹配图
(3)对于每个顶点u∈V1和u∈V2,则边e=(u,v)存在。
在上述假定下,将每个顶点组合,可以得到n!
个完美匹配。
假设(3)是合理的,因为如果导师和学生能各取所需,可将它们之间的效益权重定义为o,记u1,u2…,un是V的顶点,v1,v2…,vn是V的顶点,定义wij是ui到vj的权重,因此全矩阵为W=(wij)。
还有称完美匹配M*是最优的,如果对所有的完美匹配M有
我们可以用枚举法,得到最大完美匹配,M*={(u1,v1),(u2,v3),(u3,v2)}
下面要综合考虑学生初试成绩、复试成绩等因素选出10名考生。
用平均分的思想解决得到前十位学生。
将灵活性、创造性、知识性、表达力、外语各分配相应的分数,
A等为1分,B等为0.75分,C等为0.5分,D等为0.25分,
学生/专家
专家1
专家2
专家3
专家4
专家5
专家6
专家7
专家8
平均数
百分比
学生1
4.50
4.50
4.00
4.25
4.75
4.00
4.00
4.50
4.3125
0.07679
学生2
4.00
4.00
4.50
4.50
4.25
4.50
4.50
4.25
4.3125
0.07679
学生3
3.00
4.00
3.25
4.00
4.00
4.00
3.75
3.75
3.7187
0.06622
学生4
4.25
3.25
3.75
3.75
3.50
3.00
4.00
3.75
3.6562
0.06510
学生5
4.00
3.75
3.75
3.50
4.25
4.50
3.75
3.25
3.8436
0.06844
学生6
3.50
3.25
4.00
3.00
3.50
3.75
4.25
3.25
3.5625
0.06343
学生7
3.75
3.25
3.75
3.00
3.00
3.25
3.50
3.75
3.4062
0.06065
学生8
4.25
4.00
3.75
3.75
4.25
3.75
3.00
3.00
3.7187
0.06622
学生9
4.00
4.00
3.75
4.00
3.75
3.25
4.00
4.00
3.8437
0.06844
学生10
3.00
3.00
3.50
3.25
3.25
3.00
3.00
3.00
3.1250
0.05564
学生11
3.25
3.75
3.50
2.75
3.25
3.75
3.25
3.50
3.3750
0.06010
学生12
4.25
4.50
3.75
4.00
4.25
3.75
4.00
4.00
4.0625
0.07234
学生13
3.25
3.75
3.00
4.50
3.25
3.50
3.50
4.25
3.6250
0.06455
学生14
3.25
4.50
3.50
4.00
3.00
4.00
3.25
3.50
3.6250
0.06455
学生15
3.75
3.75
4.25
3.75
4.00
3.75
4.50
4.00
3.9687
0.07067
平均数表示的是8个专家对学生的平均看法,这样可以很好的的到一个学生的整体评价,平均数是由8个专家给出的总分除以8*5=40这个总分。
百分比得出每位学生在15名学生中名次。
再依据笔试成绩算取平均分:
学生/专家
笔试成绩
百分比
学生1
416
0.072259858
学生2
410
0.071217648
学生3
405
0.07034914
学生4
397
0.068959528
学生5
392
0.06809102
学生6
389
0.067569915
学生7
385
0.066875109
学生8
382
0.066354004
学生9
380
0.066006601
学生10
378
0.065659197
学生11
377
0.065485496
学生12
372
0.062532569
学生13
360
0.062532569
学生14
358
0.062185166
学生15
356
0.061837763
这样算又得到一个新的排序,再将15名学生的名次按照笔试成绩算出。
学生/专家
总比
名次
学生1
0.149054858
1
学生2
0.148012648
2
学生3
0.13657014
3
学生4
0.134068528
7
学生5
0.13653802
4
学生6
0.131008915
10
学生7
0.127532109
11
学生8
0.132575004
8
学生9
0.134453601
6
学生10
0.121307197
15
学生11
0.125585496
14
学生12
0.134875569
5
学生13
0.127084569
12
学生14
0.126737166
13
学生15
0.132510763
9
最终选取的学生为:
学生/专家
总比
名次
学生1
0.1490549
1
学生2
0.1480126
2
学生3
0.1365701
3
学生5
0.136538
4
学生12
0.1348756
5
学生9
0.1344536
6
学生4
0.1340685
7
学生8
0.132575
8
学生15
0.1325108
9
学生6
0.1310089
10
学生7
0.1275321
11
学生13
0.1270846
12
学生14
0.1267372
13
学生11
0.1255855
14
学生10
0.1213072
15
将两者的百分比相叠加则得到每位学生通过笔试成绩和专家评价得出其在总体名次,以此得到学生的排名,来选出前十名学生。
本模型将全部的师生双方的满意度用总体合意指数矩阵中的元素和来度量,选择最佳的方案,即等价于寻找在约束下的一个最大匹配。
本问题可以归结为非严格一对多的最优匹配问题:
其中,,表示第个学生和第个导师间的配对关系。
具体含义:
。
(下同)
此问题的求解比较容易,只要选出每一行的最大数就行了。
也即对于中的每个行,,令,即表示第个学生和第个导师标搭配。
经过次后得到的方案,即为最优方案。
导师组情况确定学生面试成绩中各方面的比重,如下式:
问题一最终答案:
学生
1
2
3
5
12
9
4
8
15
6
导师
4
6
3
6
8
1
9
5
1
7
2、问题二的求解
G是加权完全二分图,V(G)的二分图划分为U,V;U={u1,...,un},V={v1,v2,...vn},w(uivi)>=0是学生ui对vi导师的匹配度,求权最大的完备匹配,这种完备匹配称为最佳匹配。
用穷举法的话举也举死了,效率很低。
引入一个定义和一个定理。
定义1:
映射l:
V(G)->R,满足:
任意u∈U,任意v∈V,成立
l(u)+l(v)>=w(uv),则称l(v)是二分图G的可行顶标;令El={uv|uv∈E(G),l(u)+l(v)=w(uv)},称以El为边集的G之生成子图为相等子图,记为Gl
可行顶标是存在的,例如l(u)=mauw(uv),u∈U;l(v)=0,v∈V.
定理1:
Gl的完备匹配即为G的最佳匹配。
证:
设M*是Gl的一个完备匹配,因Gl是G的生成子图,故M*也是G的完备匹配。
M*中的边之端点集合含G的每个顶点恰一次,所以
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告知,欲求二分图的最佳匹配,只需用匈牙利算法求取其相等子图的完备匹配;当Gl中无完备匹配时则需要Kuhn和Mantras给出修改顶标的一个算法,使新的相等子图的最大匹配逐渐扩大,最后出现相等子图的完备匹配。
Kuhn-Mantras算法:
(0)选定初始的可行顶标l,确定Gl,在Gl中选取一个匹配M。
(1)U中顶皆被M许配,止,M即为最佳匹配;否则,取Gl中未被M许配的顶u,令S={u},T为空。
(2)若N(S)真包含T,转(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},转
(2);否则,取Gl中一个M的可增广轨P(u,v),令M=M⊙E(P),转
(1)。
下面我们就将学生和老师的匹配算进去
已知K10,10的权矩阵为
v1v2v3v4v5v6v7v8v9v10
u1355415355
u2220224566
u3244160325
u4011002423
u5121332725
u6331042168
u7221546216
u8135202142
u9234123245
u10223133413
求最佳匹配,其中K5,5的顶划分为U={ui},V={vi},i=1,2,3,4,5.
解:
(1)取可行顶标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定理知无完备匹配。
需要修改顶标。
(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的顶标分别修改成4,2,3,0,3;v1,v2,v3,v4,v5的顶标分别修改成0,1,1,0,0。
(4)用修改后的顶标l得Gl及其上面的一个完备匹配如图7.13。
图中粗实线给出了一个最佳匹配,其最大权是2+4+1+4+3=14。
我们看出:
al>0;修改后的顶标仍是可行顶标;Gl中仍含Gl中的匹配M;Gl中至少会出现不属于M的一条边,所以会造成M的逐渐增广。
得到可行顶标后求最大匹配:
书上这部分没讲,实际上是这样的,对于上面这个例子来说,通过Kuhn-Munkres得到了顶标l(u)={4,2,3,0,3},l(v)={0,1,1,0,0},那么,对于所有的l(ui)+l(vj)=w(i,j),在二分图G设置存在边w(i,j)。
再用匈牙利算法求出最大匹配,再把匹配中的每一边的权值加起来就是最后的结果了
第二题最终答案:
学生
1
2
3
5
12
9
4
8
15
6
导师
4
6
3
8
7
1
9
5
2
10
3、问题三的求解
假如师生双方一开始采用该策略,则每一步配对的总体合意指数都是选最大的。
最后的配对方案可以具体分为个步骤确定。
步骤如下:
Step0:
初始化,将个学生和个导师标记为未分配。
Step1:
求解。
令,并将第个学生和第个导师标记为分配,即两者配对。
……
重复求解
……
直至做完Step,即找到一种双向互动选择的分配方案。
结果如下表:
动态相互选择
步骤序号
匹配的学生
匹配的导师
双方配对的合意指数
1
学生9
导师3
0.73
2
学生3
导师2
0.62
3
学生1
导师4
0.55
4
学生2
导师6
0.53
5
学生4
导师9
0.46
6
学生12
导师7
0.39
7
学生8
导师5
0.39
8
学生5
导师8
0.35
9
学生7
导师10
0.33
10
学生6
导师1
0.1
匹配结果如下,其总体合意指数和为:
4.45。
由于在每一轮的确定和重新选择中,可能丢失许多数值较大的总体合意指数,所以得到最优方案的指标值明显又小于问题1、2中的方案。
作为导师或学生,其策略在于:
想在动态的双向选择中求得自己的最优配对结果,要在每一轮中根据新的寻找自己所在行或列最大数值所在的位置,数值最大即兼顾了自己满足程度最大和配对成功可能性最大的综合。
那么该位置便可为指导自己在本轮进行选择。
问题三的最终答案:
导师1
导师2
导师3
导师4
导师5
导师6
导师7
导师8
导师9
导师10
学生1
0.14
0.17
0.23
0.25
0.47
0.26
0.19
0.17
0.12
0.07
学生2
0.37
0.40
0.49
0.09
0.05
0.53
0.42
0.39
0.12
0.07
学生3
0.59
0.62
0.67
0.22
0.17
0.06
0.03
0.02
0.08
0.04
学生4
0.11
0.12
0.16
0.06
0.03
0.19
0.14
0.12
0.46
0.34
学生5
0.12
0.14
0.19
0.24
0.19
0.46
0.37
0.35
0.10
0.05
学生6
0.10
0.12
0.15
0.06
0.03
0.39
0.33
0.30
0.21
0.13
学生8
0.11
0.14
0.18
0.47
0.39
0.06
0.03
0.02
0.25
0.15
学生9
0.63
0.65
0.73
0.07
0.04
0.22
0.17
0.14
0.09
0.05
学生7
0.29
0.30
0.36
0.05
0.03
0.05
0.02
0.01
0.44
0.33
学生12
0.13
0.15
0.21
0.08
0.05
0.49
0.39
0.37
0.28
0.20
4、问题四的求解
首先确定筛选方案,学校选择5名导师,需要考虑的因素是学生申报志愿与导师的专业方向的吻合度、导师的学术水平指标、学生专业水平与导师对学生期望之间的吻合度。
见以下AHP模型表示图:
学校选导师的标准
由于对5位导师的选择影响到后面由这5位导师选择接收研究生的结果,考虑到双向选择这一大局,要求尽量公正客观的选择出这五位导师。
对于第1个因素,考虑整体学生的专业发展意愿:
第一志愿占的权重为3/5,第二志愿占的权重比为2/5.则:
专业
(1)
(2)
(3)
(4)
志愿1(个数)
4
3
5
3
志愿2(个数)
5
3
4
3
根据权重可算得:
专业
(1)
(2)
(3)
(4)
比重
0.398
0.200
0.202
0.200
所需导师数
2
1
1
1
对于第2个因素,考虑到导师的总体学术水平由四方面(发表论文数、论文检索数、编(译)著作数和科研项目数)体现。
然后,要求被录取的10名研究生与5名导师之间做双向选择,为了更好体现师生间的双向选择过程,这里用学生对导师的满意指数矩阵和导师对学生的满意指数矩阵,来表示他们的满意程度。
根据前面定义,我们可以算出各满意指数矩阵如下:
问题4中学生对导师的满意指数矩阵
导师3
导师2
导师6
导师1
导师8
学生1
0.39
0.2
0.48
0.21
0.31
学生2
0.64
0.45
0.73
0.46
0.56
学生3
0.88
0.71
0.23
0.71
0.07
学生4
0.38
0.2
0.48
0.21
0.32
学生5
0.38
0.2
0.73
0.21
0.57
学生6
0.38
0.21
0.73
0.21
0.57
学生7
0.64
0.45
0.24
0.47
0.06
学生8
0.39
0.21
0.23
0.21
0.06
学生9
0.89
0.7
0.48
0.71
0.31
学生10
0.63
0.47
0.74
0.46
0.57
学生11
0.63
0.46
0.22
0.45
0.07
学生12
0.39
0.2
0.73
0.21
0.56
学生13
0.63
0.46
0.23
0.46
0.07
学生14
0.88
0.71
0.48
0.71
0.32
学生15
0.88
0.7
0.23
0.71
0.07
问题4中导师对学生的满意指数矩阵
导师3
导师2
导师6
导师1
导师8
学生1
0.61
0.6
0.77
0.6
0.76
学生2
0.75
0.74
0.91
0.74
0.89
学生3
0.79
0.79
0.46
0.79
0.46
学生4
0.4
0.38
0.56
0.39
0.55
学生5
0.41
0.4
0.75
0.41
0.74
学生6
0.34
0.34
0.67
0.34
0.67
学生7
0.47
0.44
0.29
0.46
0.27
学生8
0.36
0.34
0.35
0.34
0.33
学生9
0.69
0.68
0.51
0.68
0.51
学生10
0.41
0.43
0.59
0.41
0.58
学生11
0.42
0.44
0.25
0.43
0.28
学生12
0.32
0.31
0.65
0.32
0.65
学生13
0.35
0.34
0.17
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 研究生 录取 问题