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