存档编号 华北水利水电大学 North China University of Water Resources and Electric Power 毕 业 论 文题目 席位分配问题理论研究 学 院 数学与信息科学 专 业 数学与应用数学 姓 名 学 号 指导教师 完成时间 2014.05.12 独立完成与诚信声明本人郑重声明：所提交的毕业设计（论文）是本人在指导教师的指导下，独立工作所取得的成果并撰写完成的，郑重确认没有剽窃、抄袭等违反学术道德、学术规范的侵权行为。文中除已经标注引用的内容外，不包含其他人或集体已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中作了明确的说明并表示了谢意。本人完全意识到本声明的法律后果由本人承担。毕业设计（论文）作者签名： 指导导师签名： 签字日期： 签字日期：毕业设计（论文）版权使用授权书本人完全了解华北水利水电大学有关保管、使用毕业设计（论文）的规定。特授权华北水利水电大学可以将毕业设计（论文）的全部或部分内容公开和编入有关数据库提供检索，并采用影印、缩印或扫描等复制手段复制、保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交毕业设计（论文）原件或复印件和电子文档（涉密的成果在解密后应遵守此规定）。毕业设计（论文）作者签名： 导师签名：签字日期： 签字日期：目 录North China University of Water Resources and Electric PowerI摘 要iABSTRACTii第一章 绪论31.1 经典席位分配问题的研究背景与意义1第二章 公平席位分配方法及其性质研究12.1节 几种经典席位分配方法的分析总结22.2节 几种席位分配方法的实例比较20第三章 最小遗憾度与余额延续法243.1几个分配方法的最小遗憾度判断标准253.1.1 最小遗憾度标准的思想253.1.2几个席位分配方法的遗憾度算法253.1.3最小遗憾度标准的实例论证263.2最小遗憾度的席位分配方法273.2.1最小遗憾度法的分配方法283.2.2最小遗憾度法的实例论证283.3 余额延续的席位分配法293.3.1余额延续法思想293.3.2余额延续法的分配方法303.3.3余额延续法的实例论证30参考文献32致 谢33附 录34席位分配问题理论研究摘 要本文第二章对Hamilton、经典Q值法、CQ值法、改进Q值法、新Q值法、最小极值法、0-1规划法、平均公平度法、相对尾数法、公平累加法等席位分配方法问题进行了研究，并通过具体例子分析了各个方法的优劣性。第三章 第一部分定义了关于席位分配方法的最小遗憾度标准，根据各个分配方法在某次分配中的分配结果，计算出哪种方法使各部门的遗憾度最小，进而确定哪种分配方法为本次分配的最佳分配方法。得出：某一种分配方法并不完全适合每一次席位分配。第二部分根据最小遗憾度思想提出最小遗憾度法，该方法旨在使各部门的最大遗憾度最小，即计算各个分配方案中的最大遗憾度，进而从中选出遗憾度最小的，遗憾度最小对应的分配方案即为最佳方案。该方法解决了总席位数增加可能导致某部门席位数减少的问题。第三部分基于多次相同席位分配的情况下提出余额延续法，该方法运用Hamilton法分配席位，记录每次席位分配后的余额。在下次席位分配时加上本次所记录的余额，然后进行分配。该方法追求在某一时间段内各个部门的平均分配结果接近分配比例。关键词：席位分配 最小遗憾度法 余额延续法 公平分配THE THEORETICAL STUDY OF SEAT ALLOCATIONABSTRACT This paper mainly talks about the study of following questions：Hamilton, the classical Q value method, CQ value method, the improvement of Q value method, the new Q value method, minimal extremum method, planning method, the average degree of fairness method, the relative mantissa method, fair accumulation method and seat allocation. The main tasks of this paper are as follows.The third chapter ,in the first part defines the standard of minimum regret about seat allocation methods, according to the results in a distribution of various allocation methods, calculate what method the regret of all departments are the youngest, and determine what kind of allocation method is best for this assignment.Conclusion: a method of distribution is not suitable for every seat allocation.The second part, according to minimum sorry thought least regret degree method, this method is aimed at minimum maximum regret degree between the various departments, namely calculating maximum regret degree of each scheme, and then choose the smallest regret degree, regret degree minimum corresponding scheme is the best solution.The method solves the total seats increase may lead to a department in the number of seats.The third part is based on many times the same seats allocated under the condition of continued balance method is put forward, this method use the Hamilton method assigned seats, record every time the balance of the distribution of seats.In the next seat allocation and recorded the balance, then allocated.The pursuit of this method in a certain period of time, the results of the average distribution of each department close to allocation proportion.Key words:seat allocation, minimal regret method, The further balance method,Fair distributioniii华北水利水电大学毕业论文第一章 绪论1.1 经典席位分配问题的研究背景与意义经典席位分配问题来源于美国众议院按各州人口比例分配议员席位名额，该问题的研究在政治学、管理学和经济学领域均有重要应用价值。比如很多大型企业均根据股份比例分配公司董事会席位，即可借鉴公平席位分配方面的研究成果。就席位分配问题而得来的公理化模型而言，其本身就是一个极具挑战性的非线性数学问题，所以对它的研究有着重要的理论价值。美国宪法规定按照各州人口比例给出公平的众议院席位分配方案，1850年到1900年期间，美国众议院采用Vinton 方法来分配各州议员名额。然而，1881年当议会总席位由299席变为300席时，再按相同的方法调整各州议员的名额，结果却使得Alabama 州的议员席位从8个减到7个，这就是著名的Alabama 悖论。后来在1890年议会席位增加时又出现类似情况。1921年，哈佛大学数学家E.V.Huntington 建立了基于名额分配不公平度的数学模型，提出了等比例方法，并于1941年将它写入法律，且沿用至今。自1974年以来，M.L.Balinski 和 H.P.Young 对席位公平问题进行了一系列的研究。他们提出了衡量公平度的一系列公理化原则，在此基础上有提出了配额法，并论证了配额法满足席位单调性的公理化准则。1977年，Balinski等分析了此前提出的一系列公理化公平原则的合理性，并比较了多个席位分配方法的优缺点，其中包括美国众议院沿用至今的等比例法、Wenster 方法和配额法等。Balinski 等简洁地总结出公平席位分配方法应该满足的5条公理化原则，如下：一：（人口单调性）一个单位的人数增加不会导致该单位席位数减少。二：（无偏性）在整个时间上平均，每个单位应得到它自己应分摊的份额。三：（席位单调性）总席位的增加不会使得某单位的席位数减少。四：（公平分摊性）任何单位的席位数都不会偏离其比例的份额数。五：（接近份额性）没有一个单位到另一个单位的名额转让会使得这两个单位都接近他们应得的份额。但是在1980年Balinski 和Young 证明了同时满足上述5条原则的席位分配方案是不存在的。这也就说明不存在一个绝对公平的席位分配方案，只能根据不同的情况，做到相对的最大公平。第二章 公平席位分配方法及其性质研究2.1节 几种经典席位分配方法的分析总结公平席位分配问题的研究其实就是社会中普遍的资源分配问题，研究的结果是试图对有限的资源的分配做到尽可能的公平。比较近的一个例子就是：我校为了召开学生代表会议，各系只能分配到有限的名额，那么问题来了，怎么去分配这些有限的名额，才算合理，或者说让各个系的人都满意呢