公平的席位分配问题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,公平的席位分配问题,数学实验与数学建模,公平的席位分配,系别 学生 比例,20,席的分配,人数 （,%,）比例 结果,甲,103 51.5,乙,63 31.5,丙,34 17.0,总和,200 100.0 20.0 20,21,席的分配,比例 结果,10.815,6.615,3.570,21.000 21,问题,三个系学生共,200,名（甲系,100,，乙系,60,，丙系,40,），代表会议共,20,席，按比例分配，三个系分别为,10,，,6,，,4,席。,现因学生转系，,三系人数为,103,63,34,问,20,席如何分配。,若增加为,21,席，又如何分配。,比例加惯例,对丙系公平吗,系别 学生 比例,20,席的分配,人数 （,%,）比例 结果,甲,103 51.5 10.3,乙,63 31.5 6.3,丙,34 17.0 3.4,总和,200 100.0 20.0 20,系别 学生 比例,20,席的分配,人数 （,%,）比例 结果,甲,103 51.5 10.3,10,乙,63 31.5 6.3,6,丙,34 17.0 3.4,4,总和,200 100.0 20.0 20,21,席的分配,比例 结果,10.815,11,6.615,7,3.570,3,21.000 21,“公平”分配方法,衡量公平分配的数量指标,人数 席位,A,方,p,1,n,1,B,方,p,2,n,2,当,p,1,/,n,1,=,p,2,/,n,2,时，分配公平,p,1,/,n,1,p,2,/,n,2,对,A,的,绝对不公平度,p,1,=150,n,1,=10,p,1,/,n,1,=15,p,2,=100,n,2,=10,p,2,/,n,2,=10,p,1,=1050,n,1,=10,p,1,/,n,1,=105,p,2,=1000,n,2,=10,p,2,/,n,2,=100,p,1,/,n,1,p,2,/,n,2,=5,但后者对,A,的,不公平程度已大大降低!,虽二者,的,绝对不公平度相同,若,p,1,/,n,1,p,2,/,n,2,，,对 不公平,A,p,1,/,n,1,p,2,/,n,2,=5,公平分配方案应使,r,A,r,B,尽量小,设,A,B,已分别有,n,1,n,2,席，若增加1席，问应分给,A,还是,B,不妨设分配开始时,p,1,/,n,1,p,2,/,n,2,，,即对,A,不公平,对,A,的,相对不公平度,将绝对度量改为相对度量,类似地定义,r,B,(,n,1,n,2,),将一次性的席位分配转化为动态的席位分配,即,“公平”分配方法,若,p,1,/,n,1,p,2,/,n,2,，,定义,1,）若,p,1,/(,n,1,+1),p,2,/,n,2,，,则这席应给,A,2,）若,p,1,/(,n,1,+1),p,2,/(,n,2,+1),，,应计算,r,B,(,n,1,+,1,n,2,),应计算,r,A,(,n,1,n,2,+1),若,r,B,(,n,1,+1,n,2,),p,2,/,n,2,问：,p,1,/,n,1,r,A,(,n,1,n,2,+1),则这席应给,B,当,r,B,(,n,1,+1,n,2,),r,A,(,n,1,n,2,+1),该席给,A,r,A,r,B,的定义,该席给,A,否则,该席给,B,定义,该席给,Q,值,较大的一方,推广到,m,方分配席位,该席给,Q,值最大的一方,Q,值方法,计算,，,美学角度,可以鉴赏,几何平均数的平方,三系用,Q,值方法重新分配,21,个席位,按人数比例的整数部分已将,19,席分配完毕,甲系：,p,1,=103,n,1,=10,乙系：,p,2,=63,n,2,=6,丙系：,p,3,=34,n,3,=3,用,Q,值方法分配第,20,席和第,21,席,第20席,第21席,同上,Q,3,最大，,第,21,席,给丙系,甲系,11,席，乙系,6,席，丙系,4,席,Q,值方法分配结果,公平吗？,Q,1,最大，,第,20,席,给甲系,进一步的讨论,Q,值方法比,“,比例加惯例,”,方法更公平吗？,席位分配的理想化准则,已知,:,m,方人数分别为,p,1,p,2,p,m,记总人数为,P,=,p,1,+,p,2,+,p,m,待分配的总席位为,N,。,设理想情况下,m,方分配的席位分别为,n,1,n,2,n,m,(,自然应有,n,1,+,n,2,+,n,m,=N,),，,记,q,i,=,Np,i,/,P,i,=1,2,m,n,i,应是,N,和,p,1,p,m,的函数，即,n,i,=,n,i,(,N,p,1,p,m,),若,q,i,均为整数，显然应,n,i,=,q,i,q,i,=,Np,i,/,P,不全为整数时，,n,i,应满足的准则：,记,q,i,=,floor(,q,i,),向,q,i,方向取整；,q,i,+,=,ceil(,q,i,),向,q,i,方向取整,.,1),q,i,n,i,q,i,+,(,i,=1,2,m,),2),n,i,(,N,p,1,p,m,),n,i,(,N,+1,p,1,p,m,)(,i,=1,2,m,),即,n,i,必取,q,i,q,i,+,之一,即当总席位增加时，,n,i,不应减少,“,比例加惯例,”,方法满足,1,），但不满足,2,）,Q,值方法满足,2,）,但不满足,1,）,。,令人遗憾！,评注：,学习者除了在寻找适当的数学方法解决席位的公平分配这一问题本身建模方法外，还应当从“从建立了相对不公平指标、并最终导出,Q-,值法”这一过程得到启发,尽管,Q-,值法能否被发现并不影响席位分配的最终方案，但用,Q-,值法来表述实现算法更加简洁有效，而且很容易将由两个团体席位分配的算法推广到多个团体的情形，领会“内容”与“形式”的辨证关系，认真对待自己的每一次创作,.,