PPT《第二章初 等模型》

第二章初 等模型

一、公平的席位问题 问题的提出 把定量的席位分配给不同的单位,并使得分配尽可能地 公正 ,这就是所谓的 席位分配 问题.

问题 某学校有3个系,共200名学生,其中甲系有学生100名,乙系有学生60名,丙系有学生40名.现拟成立有20人组成的学生会,问应如何分配学生会名额? 解 3个系的学生数所占须生总额的比例为 ,由此不难得到名额分配方案为 . 若丙系有6名学生转到他系,其中甲系3人,乙系3人,此时应如何分配名额呢? 一般原则是先取整数分配,小数部分按取大原则. 甲系: 乙系: 丙系: 即:甲系10人,乙系6人,丙系4人. 这样的分配方案是否公平呢? 假设学生会成员数上升到21人,问应该如何分配? 甲系: 乙系: 丙系: 即:甲系11人,乙系7人,丙系3人. 从中可以看出这样的分配方案并不合理. 作为丙系的代表是不会接受这样的分配方案的. 模型的建立 假设 1.席位是以整数计量的,并且为有限个,设为 个;

2.参加分配的单位为有限个,并且不超过席位数. 设单位数为 ,即;

3.每个单位有有限个人,席位是按各集体的人员多少来分配的. 所谓公平原则指的是: 每个席位在各自的集体中所代表的人员数希望是相等的. 建模 为体现公平性,引入指标: 设有两个集体,人员数分别是 ,分配到的席位数为 ,故每个席位所代表的人员数分别为 显然,若 ,则对 两个集体而言,分配是绝 ⑴ 对公平的: 若不相等,则 绝对不公平度 为 但下面的例子说明这样的刻画还是有缺陷的. ⑵

2 100

10 1000 D

2 102

10 1020 C

2 10

10 100 B

2 12

10 120 A 绝对不公平度 代表数 席位数 人员数 集体名 在上面的例子中,绝对不公平度都相等: 但实际问题是:间存在的不公平显然要比 间存在的不公平要大. 为此我们引入: 当时, 吃亏,称为的相对不公平度;

⑶ 当时, 吃亏,称⑷为的相对不公平度. 在前例中, 我们的目标是:在每一次分配时都使得相对不公平度都达到最小. 解模 设 单位已有席位 , 单位有席位 ,并假定 吃亏,即 ,因而 有意义. 现考虑下一个席位的分配: ⑴席位分配给 仍然是 吃亏,即 毫无疑问,该席位应该分配给 ⑵把下一个席位分配给 使 吃亏,即 此时可算出 的相对不公平度 ⑸ ⑶把下一个席位分配给 一定是 吃亏,此时相对不公平度为 ⑹ ⑷把下一个席位给 使 吃亏,这是不可能的. 问题的关键就是在⑵⑶情况下,通过比较相对不公平度的大小,确定下一个席位的分配方案,原则是把下一席位分配给相对不公平度大的一方.由此得到以下结论: 当时,这一席位分配给 ;

当时,这一席位分配给 . 若 ,即 上式等价于 ⑺ 引入 ⑻ 则在⑵⑶的情况下,席位应分配给 值大的那一方. 在情况⑴,由于 所以, 因而把席位分配给 符合上面的原则. 把上面讨论的情况一般化就得到 个单位 个席位的分配方法: 当分配一个新的席位时,首先按⑼计算各单位的 , ⑼ 再根据 值最大的一方进行分配. 再回到本节一开始的问题,此时 首先先给各系一个席位,因而 再计算 由此,第4个席位应该给甲系,此时 再计算值: 而 值没有变化,因此得到第5个席位给乙系. 由此得到余下的席位的分配情况(具体分配见下表). 198.45(16)

7 252.6(13)

6 132.3(18) 353.63(11)

5 198.45(14) 530.45(10)

4 96.33(21) 330.75(12) 884.08(7)