席位分配

《席位分配》由会员分享，可在线阅读，更多相关《席位分配（24页珍藏版）》请在金锄头文库上搜索。

1、席位分配问题,南京邮电大学理学院 杨振华,某学校有3个系,共200名学生,其中甲系100名,乙系60名,丙系40名.若学生代表会议设20个席位,公平而又简单的席位分配办法是按学生人数的比例分配,显然甲乙丙三系分别应占有10,6,4席.,现在丙系有6名学生分别转入甲乙两系,三个系的人数分别为103,63,34.各系应得到的席位分别应该是10.3,6.3,3.4.将取整的10,6,3个席位分别分配给三个系.剩下的一个席位按照管惯例(小数部分最大)分给丙系.分配方案仍然是10,6,4席.,增加席位后的分配方案,20个席位会在表决时出现10:10的局面,三个系同意增加一个席位.此时,21个席位中,三个

2、系分别应该得到10.815,6.615,3.570个席位.取整得到的10,6,3个席位分别分配给三个系. 剩下的2个席位若按照惯例(小数部分最大)进行分配,则分别应该分给甲乙两系. 这样,21个席位的分配方案是11,7,3.,不公平现象:总席位增加了一席,丙系少了一席!,分配原则的讨论,在上述的分配原则中,所谓的惯例(即按照小数部分的大小来分配取整后剩下的席位)导致了丙系的不公平. 如何对惯例加以修正? 在席位分配时,若严格按照学生人数的比例分配席位,一般都会出现小数.此时,无论小数部分分配给哪个系,都会出现不公平的情形.我们必须给出一个分配原则,来降低不公平程度.,原则一,设某系的人数为pi

3、,最终得到的席位为ni,则每个席位所代表的人数为pi /ni,显然该数越大,说明对这个系越不公平. 再设总人数为p,总席位数为n,我们考虑以下数学模型 该模型的数学含义是每个系每 个席位代表的人数都和总体每 个席位代表的人数尽量接近,原则一求解,对于前面提到的具体问题,我们仅考虑下面三个可行解x1=(11,7,3),x2=(10,7,4),x3=(11,6,4). 分别代入目标函数(用f表示)中计算可以得到: f(x1)=3.574,f(x2)=1.925,f(x3)=2.027 其中f(x2)值最小,所以应考虑方案x2,即三个系分别得10,7,4个席位.,原则二,类似与上面的原则一,我们可以

4、给出下面的数学模型 其中ni/pi表示某个系平均每个 人分得的席位.n/p表示总体每 个人分得的席位 对于前面的三个方案,其目标函数值分别为 g(11,7,3)=3.21610-4, g(10,7,4)=2.59910-4, g(11,6,4)=2.58510-4. 最合理的方案应该是11,6,4.,不公平程度,分析:上面的两个数学模型从表面上看都有一定的合理之处.但有一个根本的不足,即没有分别衡量各个系的不公平程度. 不公平程度:对于两个系,如果有p1/n1p2/n2,绝对的不公平程度可用p1/n1-p2/n2来衡量. 例如:p1=120,p2=100,n1=n2=10,则p1/n1-p2/

5、n2=12-10=2. 不过若p1=1020,p2=1000,n1=n2=10,仍然有 p1/n1-p2/n2=2.但是后者的不公平程度显然要比前者大为改善.,相对不公平值,既然前述的绝对不公平值不太合理,我们引入相对不公平值: 若p1/n1p2/n2,则定义 对A的相对不公平值为 若p2/n2p1/n1,则定义对 B的相对不公平值为,确定分配方案,假设A,B两方已分别占有n1席和n2席,现在讨论,当总席位增加1席时,应该分配给哪一方. 不失一般性,可设p1/n1p2/n2,即对A不公平. 下面分情况讨论(根据席位和不公平的情况).,(1)p1/(n1+1)p2/n2,即增加一席对A仍然不公平

6、.此时增加的一席显然应分配给A.,(2)p1/n1p2/(n2+1),这种情况不会出现.,(3)p1/(n1+1)p2/n2,A增加一席对B不公平,其相对不公平值为rB(n1+1,n2)=p2(n1+1)/(p1n2)-1,(4)p1/n2p2/(n2+1),B增加一席对A不公平,其相对不公平值为 rA(n1,n2+1)=p1(n2+1)/(p2n1)-1,为分配公平必须使相对不公平值尽量小,因此若rB(n1+1,n2)rA(n1,n2+1)则增加的一席应分配给A,反之分配给B.,Q值的定义,rB(n1+1,n2)Q2,下一席位给甲系, 若Q1Q2,下一席位给乙系.,Q值分配原则,上面的“分离

7、变量”的好处是,对每一方可以独立地计算出一个Q值,然后比较各方的Q值就可以进行席位的分配. 根据上面的分析,最终可以归纳出Q值分配原则: 分别计算各方的Q值,将增加的席位分配给Q值大的一方.,分配方案,对于前面提到的21个席位分配的问题,假设整数部分的19个席位已经分配给三个系,即 n1=10,n2=6,n3=3 下面用Q值方法分配第20及21席. 第20席:Q1=96.4,Q2=94.5,Q3=96.3.Q1最大,第20席应分配给甲系. 第21席:Q1=80.4,Q2=94.5,Q3=96.3.Q3最大,第21席应分配给丙系. 最终的分配方案:11,6,4,问题讨论(一),上面的讨论中(1)

8、,(3),(4)的情况仅针对情况(3)和(4)讨论得到Q值方法,和情况(1)是否矛盾? 解答: 若p1/(n1+1)p2/n2,容易证明Q1Q2,即席位应分配给甲方,Q值方法与(1)中讨论的结论一致.,问题讨论(二),我们的分配原则的基础是相对不公平值的定义.前面的定义是rA(n1,n2)=(p1/n1-p2/n2)/(p2/n2). 若相对不公平值定义为:(p1/n1-p2/n2)/(p1/n1),结论如何? 解答:此时rB(n1+1,n2)=1-(p1n2) /(p2(n1+1) rA(n1,n2+1)=1-(p2n1) /(p1(n2+1). 显然rB(n1+1,n2)Q2. 因此,重新

9、定义后,Q值分配原则是一致的.,问题讨论(三),若相对不公平值定义为:(n1/p1-n2/p2)/(n2/p2),结论如何? 若将上面的分母改为n1/p1,结论如何? 前面的讨论都是基于两方的,对于多方,Q值方法是否仍然合理? (解答略),整数部分的讨论,在给出21个席位的分配方案是,先将19个席位按照各个系的整数部分先进行分配是否合理?也就是说,按照Q值分配方法,各方是否一定能保住己方的整数部分? 某一方人数为p1,总人数为p,总席位数是n,这一方最终的席位数为n1,是否一定有n1p1n/p?,两个系的情况,若竞争席位的是两个系,上面的结论是正确的. 定理:要从两个系(人数分别为p1,p2)

10、中选取n个代表，若按照Q值方法进行分配席位数,两方最终应得的席位数分别为n1与n2,则有nipi n/p. 证明:设ri= pi n/p,mi=ri.考虑r1,r2不是整数的情况. 此时显然有ri -1miri以及n=m1+m2+1. 假设结论不成立,不妨设n1m1-1,此时有n2m2+2(n1+n2=n).,显然当甲方有n1个席位,乙方有m2+1个席位时,下一个席位应该分配给乙方. 因此Q1(n1)Q2(m2+1),从而得出矛盾.,证明(续) Q1(m1-1)Q2(m2+1)?,三个系的情况,如果竞争席位的是三个系,是否各个系仍然能保住自己的整数席位呢? 通过编程可以发现这一结论不再成立.

11、反例1:p1=41,p2=3,p3=3,n=39.各方应分配席位为34.0213,2.48936,2.48936 . 现取n1=33,n2=2,n3=2,各方的Q值为 Q1=1.49822,Q2=Q3=1.5 因此剩下的两个席位应该分配给后两个系.最终的分配方案为33,3,3 甲系未能保住自己的34个席位.,多方竞争的情况(反例2),p1=9215;p2=159;p3=158; p4=157;p5=156;p6=155; n=100;各方应分配席位为92.15,1.59,1.58,1.57,1.56,1.55 现取n1=90;n2=n3=n4= n5= n6=1,则Q1=10368.3;Q2Q

12、3Q4Q5Q6=12012.5, 因此在95个席位分配完之后,剩下的5个席位应分配给后面的五方.最终的席位为n1=90,n2=2,n3=2,n4=2,n5=2,n6=2 甲方少了两个多的席位!,更深入的问题,上面的两个反例说明,Q值方法也有一定的局限性.事实上,任何一种分配原则都将违反一定的常规! 现在仅就Q值方法提出一些问题(选做作业): 两方的时候,各方能保住自己的整数席位,那么三方的时候,各方是否能保住自己的“整数部分-1”个席位?多方的情况结论如何? 各方的人数和总席位数满足什么条件时,各方可以保住自己的整数席位?,总结,数学建模问题的解答不同与常见的数学习题.必须不断地挖掘实际的和理论的各种可能出现的问题,力争完善的解决. 数学建模竞赛的难点之一:挖掘有价值的难度适中的课题加以研究.,