席位分配问题的Dhondt模型和相对尾数模型

1、席位分配问题的Dhondt模型和相对尾数模型摘要：讨论公平席位分配的模型已有很多。本文首先用比例加惯例法、Q值法、Dhondt法对问题中名额进行了分配，再对Dhondt法的合理性进行了分析，并在Q值法对绝对尾数（绝对不公平度）的处理方式基础上，提出了相对尾数模型，并讨论了其满足Young公理的1，3，4条；在模型求解上，全部由MATLAB程序来实现名额分配。关键词：相对尾数 Balinsky & Young不可能定理 MATLAB正文1 问题复述公平的席位分配问题是一个非常有趣而重要的问题，它在政治学、管理学和对策论等领域具有广泛的应用价值。处理这个问题的最早的方法是Hamilton法

2、，即比例加惯例法；后来出现了Q值法；1974年M.L.Balinski和H.P.Young引入了席位分配问题的公理体系研究方法，并于1982年证明了同时满足五个公理的席位分配方法是不存在的；因此，我们只能根据实际建立在一定公平准则下成立并尽量多的满足Young公理的算法。这里，我们需要理解并运用比例加惯例法、Q值法、Dhondt法对宿舍委员会名额进行分配，继而提出更优的公平分配席位的方法。2 模型假设2.1合理假设2.1.1 比例加惯例法、Q值法等分配模型均为已知；2.1.2 各个宿舍相互独立互不影响，人数保持不变；2.1.3 委员分配以各宿舍人数为唯一权重。2.2 符号约定符号意义第个宿舍的

3、Q值第个宿舍的人数第个宿舍分配的名额总人数总名额数第个宿舍的理想分配名额总席位增加一个时第个宿舍的理想分配名额第个宿舍的分配比例，即第个宿舍的绝对尾数值第个宿舍的相对尾数值总席位增加一席时第个宿舍的相对尾数值按比例分配后剩余名额3 模型的建立与求解3.1按比例加惯例模型分配根据比例加惯例分配模型的原理，编写MATLAB程序实现（附录-程序1，2，3，附录-输入及运行结果1），结果如表所示：表1（比例加惯例法分配结果）：宿舍学生人数10个席位的分配15个席位的分配比例分配的席位惯例分配的结果比例分配的席位惯例分配的结果A2352334B3333345C4324466总数100091013153.

4、2按Q值法模型分配首先用比例分配法对名额进行初步分配，再根据表达式 对剩下的名额进行分配，编写MATLAB程序实现求解（附录-程序4，5，附录-输入及运行结果2）：表2（Q值法分配结果）：宿舍学生人数10个席位的分配15个席位的分配比例分配名额Q值最终分配名额比例分配名额Q值最终分配名额A23529204.17234602.084B33339240.75345544.455C43249331.2564443.436总数100091013153.3 Dhondt模型3.3.1 模型建立设，分别表示宿舍总人数和总分配席位数，()表示各宿舍人数，令()，则得到一个数列，将该数列按递减顺序重新排列，得

5、到，其中表示中第大的项。取中前项，则相应得到()，,即为按Dhondt模型分配的结果。3.3.2 按Dhondt模型分配根据建立的Dhondt模型，编写MATLAB程序求出结果（附件-程序6，附录-输入及运行结果3）：表3（Dhondt模型分配结果）：宿舍人数10个名额的分配15个名额的分配A23523B33335C43257总数100010153.4 相对尾数模型3.4.1 模型准备讨论一般情况:个宿舍人数分别为,总人数为,待分配的席位为个,理想化的分配结果是(),满足,记()。显然,若全为整数,应有=(),当不全为整数时,需要确定同时满足下面公理的分配方案。公理一：(),即取或之一,其中=

6、,=,表示的整数部分。公理二：,即总席位增加时,各宿舍的席位数不应该减少。公理一显然满足Balinsky & Young不可能定理 (见附录) 中的公理4（公平分摊性）,公理二满足其的公理1（人口单调性）和公理3（名额单调性）。令,称其为对第个宿舍的绝对尾数值。令,称其为对第个宿舍的相对尾数值。3.4.2 模型建立与求解由于人数都是整数,为使分配趋于公平,需所有的越小越好,所以趋于公平的分配方案应该是最大的达到最小,即所有的达到最小。为方便起见,首先考虑只有两个宿舍的情形,即,且,和不全是整数(实际上,他们同为整数或小数)。记,为总席位增加一席时的分配结果和相对尾数。给出定理:定理:以

7、下分配方案满足公理一,二，1) 若,且,则取,即按比例加惯例法分配;2) 若,则取,;3) 若,则取,。定理证明见附录。按照定理，对三个宿舍的情形进行讨论。设,全部为零(实际上,如果有一个为零,即是按两个宿舍分配),可以做以下分配:1) 当时,按比例分配取整后,剩余的席位分配给绝对尾数较大的宿舍,即按比例加惯例法分配;2) 当时,按比例分配后,若剩余一个席位,则分配给第一个宿舍,若剩余两个席位,则分配一席给第一个宿舍,另外一席分配给第二三个宿舍中绝对尾数值较大者；3) 当时，按比例分配后，若剩余一个席位分配给第一二个宿舍中绝对尾数值较大者，若剩余两个席位，则分配给第一二宿舍各一席；4) 当时，

8、按比例分配后,若剩余一个席位,则分配给第一个宿舍,若剩余两个席位,则分配给第二个宿舍。一般地，对个宿舍，设,，不全为零，且，则当时，将剩余的个席位分配给第一至第个宿舍各一席，当时， 个席位分配给第一至第个宿舍及和较大的宿舍各一席，当（）时， 个席位分配给第一至第个宿舍及，中较大的宿舍各一席，当（）， 个席位分配给第一至第个宿舍及，中个较大的所对应的宿舍各一席。最后，编写出尾数法的MATLAB程序，实现3本题中的名额分配（附录-程序7，附录-输入及运行结果4）。表4（尾数法分配结果）：宿舍人数10个名额的分配15个名额的分配A23534B33335C43246总数100010154 模型检验及结

9、果分析席位分配的尾数模型满足Young公理的1、3、4条，是以严格证明了的定理形式给出。对按上述四种分配模型分配的结果列表比较。 表5（各方法分配结果的比较1）：宿舍学生人数20个席位的分配21个席位的分配BQDRBQDRA1031011111011111110B6366667677C3443343434总数2002020202021212121表6（各方法分配结果的比较2）：宿舍学生人数10个席位的分配15个席位的分配BQDRBQDRA23532234434B33333335555C43245546676总数10001010101015151515表格中，B表示比例加惯例法，Q表示Q值法，D

10、表示D'hondt法，R表示相对尾数法。“比例加惯例”法用各团体人数占团体总人数的比例乘以总席位数, 取其整数位为第一次分配, 再次分配时, 则按小数位的大小分, 大的先分配, 直到席位分完。从表4看到，当总席位数增加时，C宿舍分得的席位却减少；Q值法利用相对不公平度建立了衡量不公平程度的数量指标, 进而将席位分给最不公平的一方。 Dhondt方法将各团体的人数用正整数相除, 其商数组成一个表, 将数从大到小取, 直到取得的商数的个数等于总席位数, 统计出每个团体被取到的商数的个数, 即为该团体分得的席位数。 5 优缺点分析及改进从对模型的检验与分析可以看到，上面讨论的三个模型都有自身

11、的不足：比例加惯例法满足公理一，却不满足公理二；Q值法满足公理二但不满足公理一；Dhondt法也不能解决对每个宿舍成员公平的大小问题；尾数法虽然满足公理一和二，但由于两个公理本身只满足Young公理体系的部分，也不尽完美。优点：尾数模型打破Q值法的对绝对尾数的比较方法，以相对尾数来讨论，使得模型满足了Young公理体系中更多的公理，虽不尽完善，但相比之前的四种方法是很大的改进。并且，这种对已有方法改进的思想很有启发意义。改进：本文中只给出了尾数法对3个宿舍的名额分配程序，对不定数量宿舍的分配没能程序实现，是可以改进的。参考文献 1 姜启源等 数学建模M（第三版）北京高等教育出版社,2004.2

12、427. 2 岳林 关于Q值法的一种新定义J. 系统工程.1995,13(4):7073. 3 高尚 席位分配的最大熵法J.数学的实践与认识,1996,26(2):7375. 4 吴承祯,洪伟 资源公平分配的遗传算法研究J.运筹与管理,1998,7(2):2328. 5 吴黎军 名额分配问题中的拟合法J.生物数学报,1995,10(3):7781. 6 严余松 席位分配问题的0-1规划模型J.系统工程,1996,14(5):5153. 7 林建良 席位分配的最小极差法J.华南理工大学学报,2001,29(1):2123. 8 杜跃鹏 杜太生 席位分配的最大概率法J.数学的实践与认识,2003,

13、33(7):1519. 9 王秀莲 席位分配问题的相对尾数法J.数学的实践与认识,2007,37(9):8185.附录Balinsky & Young不可能定理公理 1 (份额单调性) 一个州人口的增加不会导致它失去席位。公理 2 (无偏性) 在整个时间上平均, 每个州应得到它自己应分摊的份额。公理 3 (席位单调性) 总席位增加不会导致某个州名额减少。公理 4 (公平分摊性) 任何州的席位数都不会偏离其比例的份额数。公理 5 (接近份额性) 没有从一个州到另一个州的名额转让会使得这两个州都接近它们应得的份额。程序：1 函数bili.mfunction me,m=bili(n,N,M)

14、me=n.*(M/N);m=floor(me);i=length(n);fprintf('按比例分配的结果 : n');for j=1:i fprintf('第 %g 个宿舍的人数为: %g n',j,m(j);end 2 函数guanli.mfunction guanli(e,m,M)maxe,j=max(e);fprintf('给第 %g 个宿舍再分一个名额',j);m(j)=m(j)+1;e(j)=0;if sum(m)=M fprintf('nnn按比例加惯例法分配的结果是 : n'); for i=1:length(m)

15、 fprintf('第 %g 个宿舍名额为 : %gn',i,m(i); endelse guanli(e,m,M);end3 函数biliguanli.mfunction biliguanli()n=input('各宿舍人数 输入格式 number :');N=sum(n);M=input('输入总席位数 :');me,m=bili(n,N,M);e=me-m;if e=0guanli(e,m,M);else fprintf('nnn按比例加惯例法分配的结果是 : n'); for i=1:length(m) fprintf(&

16、#39;第 %g 个宿舍名额为 : %gn',i,m(i); endend4 函数qzhi.mfunction qzhi(q,m,M)maxq,j=max(q);fprintf('给第 %g 个宿舍再分一个名额n',j);m(j)=m(j)+1;q(j)=0;if sum(m)=M fprintf('nnn按Q值法分配的结果是 : n'); for i=1:length(m) fprintf('第 %g 个宿舍名额为 : %gn',i,m(i); endelse qzhi(q,m,M);end5 函数Qzhifa.mfunction Qz

17、hifa()n=input('输入各宿舍人数 格式为： number :');N=sum(n);M=input('输入总席位数 :');me,m=bili(n,N,M);fprintf('各宿舍的Q值为：n')for i=1:length(n) q(i)=n(i)2/(m(i)*(m(i)+1); fprintf('%gn',q(i);endfprintf('按Q值分配的结果 : n');if me=mqzhi(q,m,M);else fprintf('nnn按Q值法分配的结果是 : n'); fo

18、r i=1:length(m) fprintf('第 %g 个宿舍名额为 : %gn',i,m(i); endend6 函数 dhondt.mfunction dhondt()n=input('各宿舍人数 输入格式 number :');N=sum(n);M=input('输入总席位数 :');nm=0;k=length(n);m(k)=0;s=0;for i=1:M for j=1:k s=(i-1)*k+j; nm(s)=n(j)/i; end endfprintf('按 D''hondt分配顺序为：nn')f

19、or i=1:M maxd,j=max(nm); l=mod(j,k); if l=0 l=k; end fprintf('分给第 %g 个宿舍一个名额n',l); m(l)=m(l)+1; nm(j)=0;endfprintf('分配结果：n');for i=1:k fprintf('第 %g 个宿舍 %g 个名额n',i,m(i);end7 函数weishufa3.mfunction weishufa3()n=input('输入3个宿舍人数 输入格式 number :');N=sum(n);M=input('输入总席位

20、数 :');ms,m=bili(n,N,M);s=ms-m;r=s./m;if s=0 for i=1:3 maxr,k=max(r); R(i,:)=r(k),s(k),k; r(k)=0; endendt=M-sum(m);for i=1:t j=R(i,3); m(j)=m(j)+1;endfprintf('nnn按相对尾数法分配的结果是 : n');for i=1:3 fprintf('第 %g 个宿舍名额为 : %gn',i,m(i);end输入及运行结果：1 表1结果>> biliguanli各宿舍人数 输入格式 number :

21、235 333 432输入总席位数 :10按比例分配的结果 : 第 1 个宿舍的人数为: 2 第 2 个宿舍的人数为: 3 第 3 个宿舍的人数为: 4 给第 1 个宿舍再分一个名额按比例加惯例法分配的结果是 : 第 1 个宿舍名额为 : 3第 2 个宿舍名额为 : 3第 3 个宿舍名额为 : 4>> biliguanli各宿舍人数 输入格式 number :235 333 432输入总席位数 :15按比例分配的结果 : 第 1 个宿舍的人数为: 3 第 2 个宿舍的人数为: 4 第 3 个宿舍的人数为: 6 给第 2 个宿舍再分一个名额给第 1 个宿舍再分一个名额按比例加惯例法分

22、配的结果是 : 第 1 个宿舍名额为 : 4第 2 个宿舍名额为 : 5第 3 个宿舍名额为 : 62 表2结果>> Qzhifa输入各宿舍人数 格式为： number :235 333 432输入总席位数 :10按比例分配的结果 : 第 1 个宿舍的人数为: 2 第 2 个宿舍的人数为: 3 第 3 个宿舍的人数为: 4 各宿舍的Q值为：9204.179240.759331.2按Q值分配的结果 : 给第 3 个宿舍再分一个名额按Q值法分配的结果是 : 第 1 个宿舍名额为 : 2第 2 个宿舍名额为 : 3第 3 个宿舍名额为 : 5>> Qzhifa输入各宿舍人数

23、格式为： number :235 333 432输入总席位数 :15按比例分配的结果 : 第 1 个宿舍的人数为: 3 第 2 个宿舍的人数为: 4 第 3 个宿舍的人数为: 6 各宿舍的Q值为：4602.085544.454443.43按Q值分配的结果 : 给第 2 个宿舍再分一个名额给第 1 个宿舍再分一个名额按Q值法分配的结果是 : 第 1 个宿舍名额为 : 4第 2 个宿舍名额为 : 5第 3 个宿舍名额为 : 63 表3结果>> dhondt各宿舍人数 输入格式 number :235 333 432输入总席位数 :10按 D'hondt分配顺序为：分给第 3 个

24、宿舍一个名额分给第 2 个宿舍一个名额分给第 1 个宿舍一个名额分给第 3 个宿舍一个名额分给第 2 个宿舍一个名额分给第 3 个宿舍一个名额分给第 1 个宿舍一个名额分给第 2 个宿舍一个名额分给第 3 个宿舍一个名额分给第 3 个宿舍一个名额分配结果：第 1 个宿舍 2 个名额第 2 个宿舍 3 个名额第 3 个宿舍 5 个名额>> dhondt各宿舍人数 输入格式 number :235 333 432输入总席位数 :15按 D'hondt分配顺序为：分给第 3 个宿舍一个名额分给第 2 个宿舍一个名额分给第 1 个宿舍一个名额分给第 3 个宿舍一个名额分给第 2 个宿舍一个名额分给第 3 个宿舍一个名额分给第 1 个宿舍一个名额分给第 2 个宿舍一个名额分给第 3 个宿舍一个名额分给第 3 个宿舍一个名额分给第