公平席位问题

第2章初等模型如果研究对象的机理比较简单，一般用静态、线性、确定性模型描述就能达到建模的目的，我们基本上可以用初等数学的方法来构造和求解。公平的席位分配是一个十分有趣而重要的问题,它在政治学、管理和对策论等领域具有广泛的应用价值,概括地说,席位分配问题的数学描述如下:设Ns={1,2,⋯,s},表示s个团体集,如一所大学里s个班级,美国的s个不同的州,选举人民代表大会委员的各不同阶层民众等。设h表示总的席位数,pi表示第i个团体的人数，所谓席位分配就是求一组非负的整数序列a1,a2,⋯,as满足条件不过,实际问题中往往还要求寻找一种更加“公平”的分配方式。由于实际的席位分配中为同时保证公平性和合理性,总是会考虑各团体人口数量以外的其它多种因素等，已有研究方法还没有很好的解决这一问题。siiha12.1公平的席位分配系别学生比例20席的分配人数（%）比例结果甲10351.5乙6331.5丙3417.0总和200100.020.02021席的分配比例结果10.8156.6153.57021.00021问题三个系学生共200名（甲系100，乙系60，丙系40），代表会议共20席，按比例分配，三个系分别为10，6，4席。现因学生转系，三系人数为103,63,34,问20席如何分配。若增加为21席，又如何分配。比例加惯例对丙系公平吗系别学生比例20席的分配人数（%）比例结果甲10351.510.3乙6331.56.3丙3417.03.4总和200100.020.020系别学生比例20席的分配人数（%）比例结果甲10351.510.310乙6331.56.36丙3417.03.44总和200100.020.02021席的分配比例结果10.815116.61573.570321.00021例1“公平”分配方法衡量公平分配的数量指标人数席位A方p1n1B方p2n2当p1/n1=p2/n2时，分配公平p1/n1–p2/n2~对A的绝对不公平度p1=150,n1=10,p1/n1=15p2=100,n2=10,p2/n2=10p1=1050,n1=10,p1/n1=105p2=1000,n2=10,p2/n2=100p1/n1–p2/n2=5但后者对A的不公平程度已大大降低!虽二者的绝对不公平度相同若p1/n1p2/n2，对不公平Ap1/n1–p2/n2=5公平分配方案应使rA,rB尽量小设A,B已分别有n1,n2席，若增加1席，问应分给A,还是B不妨设分配开始时p1/n1p2/n2，即对A不公平),(///21222211nnrnpnpnpA~对A的相对不公平度将绝对度量改为相对度量类似地定义rB(n1,n2)将一次性的席位分配转化为动态的席位分配,即“公平”分配方法若p1/n1p2/n2，定义1）若p1/(n1+1)p2/n2，则这席应给A2）若p1/(n1+1)p2/n2，3）若p1/n1p2/(n2+1)，应计算rB(n1+1,n2)应计算rA(n1,n2+1)若rB(n1+1,n2)rA(n1,n2+1),则这席应给应讨论以下几种情况初始p1/n1p2/n2问：p1/n1p2/(n2+1)是否会出现？A否!若rB(n1+1,n2)rA(n1,n2+1),则这席应给B当rB(n1+1,n2)rA(n1,n2+1),该席给ArA,rB的定义)1()1(11212222nnpnnp该席给A否则,该席给B,2,1,)1(2innpQiiii定义该席给Q值较大的一方推广到m方分配席位该席给Q值最大的一方Q值方（QValueMethod)minnpQiiii,2,1,)1(2计算，三系用Q值方法重新分配21个席位按人数比例的整数部分已将19席分配完毕甲系：p1=103,n1=10乙系：p2=63,n2=6丙系：p3=34,n3=3用Q值方法分配第20席和第21席第20席3.964334,5.947663,4.961110103232221QQQ第21席3221,,4.801211103QQQ同上Q3最大，第21席给丙系甲系11席，乙系6席，丙系4席Q值方法分配结果公平吗？Q1最大，第20席给甲系进一步的讨论Q值方法比“比例加惯例”方法更公平吗？席位分配的理想化准则已知:m方人数分别为p1,p2,…,pm,记总人数为P=p1+p2+…+pm,待分配的总席位为N。设理想情况下m方分配的席位分别为n1,n2,…,nm(自然应有n1+n2+…+nm=N)，记qi=Npi/P,i=1,2,…,m,ni应是N和p1,…,pm的函数，即ni=ni(N,p1,…,pm)若qi均为整数，显然应ni=qiqi=Npi/P不全为整数时，ni应满足的准则：记[qi]–=floor(qi)~向qi方向取整；[qi]+=ceil(qi)~向qi方向取整.1)[qi]–ni[qi]+(i=1,2,…,m),2)ni(N,p1,…,pm)ni(N+1,p1,…,pm)(i=1,2,…,m)即ni必取[qi]–,[qi]+之一即当总席位增加时，ni不应减少“比例加惯例”方法满足1），但不满足2）Q值方法满足2）,但不满足1）。令人遗憾！Q值法的评价：i代表各方分配的席位数评注：寻求公平分配席位方法的关键，是建立衡量公平程度的既合理又简明的数量指标，本模型提出的指标是相对不公平度，在这个前提下得到的Q值方法应该是公平的。但是，如果跳出这个前提，站得更高些，提出所谓公平分配的理想化原则，那么这个问题远未解决。下面，我们还将介绍几个席位分配模型（SeatDistributionModel)D’Hondt方法某单位3个部门，甲部门103人，乙部门63人，丙部门34人，年终单位评选20个先进，按比例分配方法，甲、乙、丙各占10.3,6.3,3.4个名额，实际分配为10,6,4个名额。若单位评选21个先进，按比例分配，甲，乙丙各占11,7,3个名额，单位增加了一个先进名额，丙部门反而减少了一个名额。问题前人在解决席位分配问题时采用了许多方法，其中D’Hondt方法是比较典型的方法之一。比利时人D’Hondt提出将甲,乙,丙三系的人数都用整除，将的商从大到小排列，取排列在前的20个数，若这20个数中有m个是甲部门人数被整数相除得到的商，则甲部门分得m个名额，乙、丙部门依次类推。采用这一方案，则20个席位的分配结果为甲:11乙:6丙:3。增加一个席位后21个席位的分配结果为甲:11乙:7丙:3。)3,2,1;3,2,1(iliPl)3,2,1(lPl)3,2,1(ii与比例加惯例的方法相比，有什么差别？D’Hondt方法评价：这一方案虽然克服了比例加惯例方法中因小数变动引起的名额不规则变动，但是在各个部门每个席位所代表的人数不相等的情况下，对席位所代表的平均人数值较大的一方来说，存在着不公平，而且D’Hondt方法不能衡量‘不公平’的大小。“D’Hondt法+Q值法”席位分配模型席位分配模型中,按比例分配法存在较大缺陷,D’Hondt法不能解决不公平的大小问题,Q值法不能解决“分配资格”问题。基于此,提出了“分配资格”这一概念,并将D’Hondt法和Q值法结合起来,建立了D’Hondt+Q值法”席位分配模型。实例表明,该分配模型使席位分配更趋合理。作者：孙玉秋文章发表于江汉石油大学学报（武汉）方法简介：1)第1个名额给人数最多的部门，设为甲部门。2)根据D’dondt法中的值，依次确定第2,3,个名额的‘分配资格’部门，直到已有2个部门有“分配资格”为止,并且有一个部门只有一个名额。设甲、乙部门已具备“分配资格”。3)下面每增加一个名额，则重复如下步骤，直至丙部门具有‘分配资格’止，不失一般性，设其中，m,n分别为已经分配给甲、乙的名额数。iP11nPmP乙甲4)当丙部门也具备‘分配资格’时，余下的名额按Q值法分配。评价：尽管用“D’Hondt+Q值法”与用Q值法得出的结果差别不大,但在名额比较少或参与分配部门比较多的情况下,使用“D’Hondt+Q值法”将更趋合理。掌握了这一方法,决策者就不必再为名额不好协调而一次又一次增加或减少总名额了。其他关于席位分配问题的相关方法及文献1)席位分配问题的数学模型（湖南大学学报）万中,罗汉摘要：利用最小二乘思想描述分配中的公平性,利用网格搜索法进行求解,模型简洁明了,求解算法有效,大量的数值实验为模型的实际应用提供了不少有价值的结论。2)席位分配问题的方法论基础（自然辩证法研究）王志健摘要：阐明了理想化方法的本质。从理想化方法出发导出了最大熵原理,从而奠定了最大熵原理的理论基础。对席位分配问题的若干处理方案进行方法论分析后,证明必须抛弃以“公平度”作为席位分配原则的方案,采用以理想化方法为基础的分配方案———最大熵法。3)席位公平分配的0—1规划模型（系统工程）严余松摘要：针对建模中经典问题席位公平分配进行研究，建立了席位公平分配0—1规划模型，提出了该模型的解法，其结果较Q值法更为合理。4)席位分配的最大概率法(数学的实践与认识)杜跃鹏,杜太生摘要：文章对席位公平分配问题进行了探索,提出了用最大概率作为公平分配的原则,给出了简单算法,并由此给出了一类组合数乘积最大值的计算方法.5)从“席位分配”模型到图书馆书刊采购模型摘要：通过对席位分配模型的研究,从书刊购买的影响因素入手,使用定量的方法,给出了图书馆书刊采购的精确模型。该模型有助于公平地分配经费,购买不同学科书刊。你还能提出其他方法吗？辛苦了