当前位置:文档之家› 关于代表席位分配问[1]..

关于代表席位分配问[1]..

关于代表席位公平分配问题

安徽大学数学建模教学小组(杨尚俊?执笔)

[摘要] 文献[1]第2章介绍的关于代表席位公平分配问题及Q值方法模型是国内数学建模课程和培训班都要讲授的一个数学建模范例。本文对这个问题提出F值方法和G值方法的方差最小模型。我们的方法与Q值方法对[1]中的例子给出同样的正确结果,但我们的方法比Q值方法较为简便,因为无须用小数尾数优先的惯例先作出少1席的分配。本文更举例说明:在某些情况下Q值方法可能给出不正确的结果;或者可能失效(即不能作出决定)。本文从理论上进一步证明:只要所涉及的两个单位人数不相等,则在任何情况下F值方法和G值方法不可能同时失效, 本文是我们为安徽大学本科生开设的数学建模课讲授这个模型时,学生们发现和提出问题,并经过师生们反复多次热烈讨论所得结论的一个总结。

[关键词] 数学模型;方差;Q值法

[中国图书分类] G420

文献[1]第2章第一节给出下列决定代表席位分配的有趣例子:

例1人数分别为103, 63和34的A,B,C三个单位的一个20人的代表会议,上一届按照人数比例并参照小数尾数优先的惯例决定三单位按10, 6和4分配代表席位.但下一届会议为了避免表决提案时出现10:10的僵持局面,决定增加一席,他们按照上述方法算出的结果是11, 7和3的分配方案(有关计算如表1所示).

表1 按照小数尾数优先惯例的席位分配

增加一席的分配结果显然对单位C不公平(因为他们反而比原来减少了一席),这一事实说明,这种”小数尾数优先”的惯例并非永远合理. 文[1]因此提出相对不公平度的概念并提出Q值方法的数学模型。用这个Q值方法给出的分配方案(表2)是:三单位分别占有11,6,4席,使单位C保住了险些丧失的一席。

表2 按照Q值方法的席位分配

?安徽大学教授,1937年7月出生,电话:0551-*******,email:sjyang@https://www.doczj.com/doc/0812381180.html,

现在考虑代表席位分配问题的一般情形。设某社团共有m 个单位,人数分别为

1,2,...,n p p p ,

社团总人数为1m

i i P p ==∑, 社团代表会议待分配的席位为N ,记i

i p b N P

=. 则i b 是应分给第i 单位席位数(未取整)的理论值. 设i n 是i b 经取整后分给第i 单位席位数的

实际值. 这里取整不外乎向下取整,即i i n b =????或向上取整,即i i n b =????. 使 1i i b n -> 的其它取整显然都不是合理的.

1m

i

i r k ==∑

,其中r i =b i -?b i ?.是b i 的小数尾数. 若k =0,则每个b i 都是整数,这是绝对公平

的理想情况,它一般很难出现. 实际上, k 总是某个正整数,即,总有不只k 个的b i 不是整数.

任何一个可行的代表席位分配方案 (n 1, n 2…, n m ) 都对应于选定某k 个不是整数的b i 为向

上取整,其余m -k 个为向下取整. 显然,将k 个n i 取整为?b i ?的所有可能性共有k

m C 种. 对应于

其中第u 种可能性的一个特性指数是:

2

1()m

i i i i n p P Q u N n N =??

=- ???

∑.

其含义是, 按第u 种可能性取整的情况下,每个代表所代表的平均人数与一个代表所代表的理想平均人数P/N 的方差,其值越小公平性越好.

对任意的 i ≠j 比较两个取整方案u i , u j ,它们仅有的差别是i, j 两单位n i ,n j 的取整情况不同,前者按?b i ?, ?b j ?取整;后者按?b i ?, ?b j ?取整(其余单位的取整情况二者完全相同). 易见

2

2

2

2

222

()()j j i i i j i j i j i i j j j i i i i j i i j p p p p P P P P Q u Q u b b b b b N N b N N b b p p p P P P b b b b N b N N b ???????????? ? ?

????????????????????????????

???? ??---<-???? ? ??????? ?

? ?????????????

??????2

j j j p P b N b ??

?? ?--?? ???????

即 仅依赖于i 的值 2

2

()i i i i i i p p P P i b b b N b N ?????=---???? ? ????? ? ?

??????

??

??

??

越小,对应的 Q(u i ) 越小, 其含意是:

若让使 ? 取最小值的单位i 按?b i ?取整,则任何单位j 按?b j ?取整都有 Q(u i )< Q(u j ). 当b i 不

是整数时有?b i ?-?b j ?=1,从而

22

2222222i i i i i i i i i i i i i p p p p p P P P P b b b N b N b b N b b N ????----=-+=+???? ? ????? ? ?????????????????????????????

上式最右边的一项(P 2/N 2)与i 无关. 由此可见,让对应于使 -p i 2 / ?b i ??b i ? 取前k 个最小值的k

个单位按?b i ?取整,其余单位按?b i ?取整的方案将给出方差最小的,也就是最优的分配方案. 令 F(i)=p i 2 / ?b i ??b i ?, 则有下面的合理确定代表席位的一种方差最小模型--F 值方法模型: 让使F(i) 取前k 个最大值的k 个单位向上取整; 其余m -k 个单位向下取整将给出最优分配方案. 对例1的席位分配问题用F 值方法计算(表3)出20席和21席的公平分配方案分别是(11,6,3) 和 (11,6,4). 结果与用Q 值方法计算出(表2)的分配方案完全一致.

表3 按照F 值方法的席位分配

注: 不难看出,F 值方法与Q 值方法的基本公式十分相似;但前者较为简单,因为后者必须在事先用小数尾数优先的惯例作出少1席分配方案的基础上进行计算.

与F 值方法模型平行的另一种方差最小模型是以方差

2

1

()m

i i i i p n N Q u P p P =??'=- ???

∑. 代替F 值方法中的方差Q(u). 方差Q '(u)的大小刻画按第u 种可能性取整的情况下,每个人能成为代表的平均机会与理想平均机会N/P 的偏差程度,其值越小公平性越好.

比较两个取整方案u i , u j ,它们仅有i, j 两单位取整情况不同,前者按?b i ?, ?b j ?取整;后者按?b i ?, ?b j ?取整(其余单位的取整情况二者完全相同). 易见

2

2

2

2

22

22()()i j

j i i j i j i j i j i j j j i i i j i i j j b b b b N N N N Q u Q u p p p p p P p P p P p P b b b b N N N N p p p P p P p P p P ???????????????????????? ? ?

???????????????????????????? ? ? ? ??---<--- ? ? ?

? ? ??????

??????? 当b i 不是整数时有

22212i i i i i i i b b b N N N p p P p P p P ??????+???????????? ?---=-

? ? ???????

由此可见(仿F 值方法的推理),让对应于使(2?b i ?+1)/p i 取前k 个最小值的k 个单位按?b i ?取整,

其余单位按?b i ?取整的方案将给出方差最小的,也就是最优的分配方案.令 G(i)= (2?b i ?+1)/p i , 则有下面的合理确定代表席位的G 值方法方差最小模型: 让使G (i) 取最小值的前k 个单位向上取整;其余m -k 个单位向下取整将给出最优分配方案.

表4说明对例1的席位分配问题用G 值方法计算(表4)出20席和21席的公平分配方案也是(11,6,3)和(11,6,4).

表4 按照G 值方法的席位分配

例2 试对人数分别为404, 204, 104, 54, 14的七单位决定78席和79席的公平分配方案? 用Q 值方法模型计算出78席和79席的公平分配方案(表5)分别是 (41,20,10,5,2) 和

(41,21,10,5,2). 用F值方法模型计算出78席和79席的公平分配方案(表6)分别是(41,21,10,5,1) 和(41,21,11,5,1)(注: 用G值方法模型计算结果同F值方法模型).

讨论对例2的七单位79席的席位分配问题,用加一席模型的Q值方法计算出的分配方案是(41,21,10,5,2), 而用方差模型的F值方法或G值方法给出的方案则是(41,21,11,5,1). 二者结果不同. 到底谁错了?

表5 按照Q值方法的席位分配

表6 按照F值方法的席位分配

答案应该是:后者对而前者不对,所依据的两个理由如下:

(1). 79席的理论席位分配为:b=(40.92,20.66,10.53,5.47,1.42); k=3. 按小数尾数优先的惯例,让5 k=2个最小的小数尾数对应的单位向下取整,其余单位向上取整,也得到分配方案(41,21,11,5,1).

(2). 如果在用方差模型给出的78席分配方案上用加一席模型计算39席的话,结果(见表7)也是(41,21,11,5,1).

表7先按F值方法后按Q值方法的席位分配

下面进一步给出例子说明: 可能出现Q值方法和F值方法同时失效的情形(表8); 也可能出现G值方法失效的情形(表9).

例3试对人数为60,10的两单位决定10席代表和试对人数为70,30的两单位决定15席代表的公平分配方案?

表8 G 值方法有效,F 值方法和Q 值方法无效的情形

表9 F 值方法和Q 值方法有效, G 值方法无效的情形

有趣的是成立下之

命题: 除非所涉及的两个单位人数相等,F 值方法和G 值方法不会同时无效.

证: 令n i =?b j ?, 则?b i ?=n i +1. 若F 值方法和G 值方法两个方差模型同时无效,则所涉及的两个单位(设为第i, j 单位)满足

2221

21,(1)(1)

j j

i i i j

i i j j n p n p p p n n n n ++==

++ 由此得 22

(1)(21)(1)(21)

i i i j j j n n n n n n ++=++,22

(1)(21)(1)(21)i i j j j i n n n n n n ++=++ 进一步有 22,()(1)0i i j j i j i j n n n n n n n n +=+-++=

因1+n i +n j >0, 所以, n i =n j 命题得证.

综上所述, 应该认为: 方差最小模型的F 值方法或G 值方法比加一席模型的Q 值方法更好.

参考文献

[1] 姜启源、谢金星、叶俊,《数学模型》第三版[M],高等教育出版社,2003,第2章。

Problem of how to distribute fairly representatives for a

represent convention

Teaching team of mathematical modeling of Anhui University

(Anhui University, Hefei 230039, China)

Abstract: In this paper we study the problem of how to distribute fairly representatives for a represent convention discussed in [1]. We give two mathematical models to solve the problem. We also give examples to explain that the two models is better than the model given in [1].

Keywords : mathematical model; variance; Q-method

作者简介:

杨尚俊,安徽大学教授,研究方向,组合数学及应用,2001年获全国大学生数学建模竞赛优秀指导教师,2006年获安徽省省级教学名师。

相关主题
相关文档 最新文档