《数学建模,名额分配问题资料》由会员分享，可在线阅读，更多相关《数学建模,名额分配问题资料（3页珍藏版）》请在金锄头文库上搜索。
1、名额公平分配问题 问题的提出问题的提出 名额分配问题是西方所谓的民主政治问题，美国宪法在第一条第二条款指出： 众议院 议员名额将根据各州的人口比例分配。 。 。 。 。 美国宪法从 1788 年生效以来 200 多年间， 关于公平和人力的实现宪法中所规定的分配原则， 美国的政治家和科学家们展开了激烈的讨 论。并提出了多种方法，但没有一种方法能够得到普遍的认可。下面就日常生活中的实际问 题，考虑合理的分配方案问题。 设某高校有5个系共2500名学生， 各系学生人数见表格。 现有25个学生代表名额， 赢如何分配较为合理。 系别一二三四五总和 人数11056483622481372500 5个系的学
2、生人数 模型假设模型假设 1、要将名额尽可能的公平的分配，首先考虑的是公平量化，所谓公平，就是学生 代表的名额占有率都相等，这样，基于名额占有率相等的分配的方案就是最公平的，在 名额占有率不相等时，应要求差距尽可能的小，才能使分配方案更加公平。 2、在计算各个系别的名额分配占有量，这样就确定了公平的分配方案。 3、通常计算的名额占有量是小数，而名额只能整数的分配，这就需要将小数变成 整数，解决小数变整数的问题通常采用四舍五入法。 名额占有率 = 总名额数 总人数 名额占有量 = 名额占有率 学生数 模型建立模型建立 模型一模型一 名额占有率分配名额占有率分配 可以算出全校名额占有率= 25 2
3、500 = 1%，即每一百人才有一个名额。根据名额占有率 分配： 系别一二三四五总和 人数11056483622481372500 名额数11.056.483.622.481.3725 取整11642124 显然看出，这种方法出现了缺陷，分的总名额数多出一个，而这一个又无法可分， 无论是四舍五入法，还是直接取整，分给二，四其中一个必定对另一个不公平。所以需 要改进。 模型二模型二 Hamilton 方法方法 1790 年，美国乔治华盛顿时代的财政部长亚历山大哈密尔顿（Hamilton）提出 了一种解决名额分配的办法，并于 1792 年被美国国会通过。Hanilton 方法的操作过程 如下： （
4、1） 、先让各州获得份额,的整数部分; （2） 、令r= ,按照r由大到小的顺序将剩余的名额分配给相应的各州，知 道各州名额分配完为止。 按照 Hamilton 的方法对 25 个名额分配如下表： 系别一二三四五总和 人数11056483622481372500 名额数11.056.483.622.481.3725 取整11642124 可以看出在第二个和第四个系别分配时，名额只有一个，小数相等。如果都不分配，名 额就有剩余， 如果都分配， 名额总数不够用。 由此看出， Hanilton 的方法仍然存在缺陷。 需要进一步的改进。 模型三模型三 Huntington-HILL 算法算法 定理：在
5、席位分配方案（,）的基础上，在增加一个席位，方案（+ 1,）优 于（,+ 1）,当且仅当,其中 = (+ 1) 名额分给 Q 值最大的那个单位。 模型求解模型求解 由模型一、二可知名额占有率为 1%，计算各系名额占有量如下图： 系别一二三四五总和 p人数11056483622481372500 n名额占有量 11.056.483.622.481.3725 n整数部分11632123 这样，先把 23 个名额分配到各系别，接下来，第 24 个名额和第 5 个名额用 Q 值方法 进行分配。 对于第 24 个名额，计算得：Q1=11052/ (11*12)=9250.189 Q2=6482/(6*7
6、)=9997.714 Q3=3622/(3*4)=10920.333 Q4=2482/(2*3)=10250.667 Q5=1372/(1*2)=9384.500 比较可知，Q3 最大，所以第 24 个名额给系别三。 对于第 25 个名额，计算得：Q1=11052/ (11*12)=9250.189 Q2=6482/(6*7)=9997.714 Q3=3622/(7*8)=2340.071 Q4=2482/(2*3)=10250.667 Q5=1372/(1*2)=9384.500 比较可知，Q4 最大，所以第 25 个名额应该给系别四。分配的最终结果是：系别一：1 个；别二：6 个；系别三：4 个；系别四：3 个；系别五：1 个。 模型评价模型评价 名额分配问题的关键在于建立既合理又简明的衡量公平程度的指标。 占有率相等是 一种理想化的状态，在实际生活中是十分罕见的。在不公平的情况下，相对不公平度比 绝对不公平度更加准确的反应不公平的实质。Q 值的方法以相对不公平度为前提，将名 额分给 Q 值最大的一方，是相对公平的。 1982 年，Balinsky 和 young 的研究表明：不存在即能避免所有席位的悖论同时又满 足份额法则的席位的分配方法，这就是有名的 席位分配不可能定理
