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

席位分配问题的D’hondt模型和相对尾数模型摘要：讨论公平席位分配的模型已有很多。本文首先用比例加惯例法、Q值法、D’hondt法对问题中名额进行了分配，再对D’hondt法的合理性进行了分析，并在Q值法对绝对尾数（绝对不公平度）的处理方式基础上，提出了相对尾数模型，并讨论了其满足Young公理的1，3，4条；在模型求解上，全部由MATLAB程序来实现名额分配。关键词：相对尾数 Balinsky&Young不可能定理 MATLAB正文1问题复述公平的席位分配问题是一个非常有趣而重要的问题，它在政治学、管理学和对策论等领域具有广泛的应用价值。处理这个问题的最早的方法是Hamilton法，即比例加惯例法；后来出现了Q值法；1974年M.L.Balinski和H.P.Young引入了席位分配问题的公理体系研究方法，并于1982年证明了同时满足五个公理的席位分配方法是不存在的；因此，我们只能根据实际建立在一定公平准则下成立并尽量多的满足Young公理的算法。这里，我们需要理解并运用比例加惯例法、Q值法、D’hondt法对宿舍委员会名额进行分配，继而提出更优的公平分配席位的方法。2模型假设2.1合理假设2.1.1比例加惯例法、Q值法等分配模型均为已知；2.1.2各个宿舍相互独立互不影响，人数保持不变；2.1.3委员分配以各宿舍人数为唯一权重。2.2符号约定符号意义Qi第i个宿舍的Q值ni第i个宿舍的人数mi第i个宿舍分配的名额n总人数m总名额数pi第i个宿舍的理想分配名额—pi总席位增加一个时第i个宿舍的理想分配名额qi第i个宿舍的分配比例，即nimnsi第i个宿舍的绝对尾数值ri第i个宿舍的相对尾数值—ri总席位增加一席时第i个宿舍的相对尾数值

按比例分配后剩余名额3模型的建立与求解3.1按比例加惯例模型分配根据比例加惯例分配模型的原理，编写MATLAB程序实现（附录-程序1,2,3,附录-输入及运行结果1）,结果如表所示：表1（比例加惯例法分配结果）:宿舍学生人数10个席位的分配15个席位的分配比例分配的席位惯例分配的结果比例分配的席位惯例分配的结果A2352334B3333345C4324466总数100091013153.2按Q值法模型分配n2首先用比例分配法对名额进行初步分配，再根据表达式Q=mm+Di=A，B，Cii对剩下的名额进行分配，编写MATLAB程序实现求解（附录-程序4,5，附录-输入及运行结果2）：表2（Q值法分配结果）：宿舍学生人数10个席位的分配15个席位的分配比例分配名额Q值最终分配名额比例分配名额Q值最终分配名额A23529204.17234602.084B33339240.75345544.455C43249331.2564443.436总数100091013153.3D’hondt模型3.3.1模型建立设n，m分别表示宿舍总人数和总分配席位数， 七（i=1,2,3）表示各宿舍人数，令七=nj（i=1,2,3,j=1,2,...），则得到一个数列J,将该数列按递减顺序重新排列，得(a(k(a(k)}中第k大的项。取

j=^a(k)}(k=1,2,...,m)中i=p的元素的个数"p=1,2,3),mij 1其中ajk）表示«）｝中前m项，则相应得到m2,m3即为按D’hondt模型分配的结果。3.3.2按D’hondt模型分配根据建立的D’hondt模型，编写MATLAB程序求出结果（附件-程序6，附录-输入及运行结果3）：表3（D’hondt模型分配结果）:宿舍人数10个名额的分配15个名额的分配A23523B33335C43257总数100010153.4 相对尾数模型3.4.1模型准备讨论一般情况：k个宿舍人数分别为n,i=1,2,...,k，总人数为n=n+...+n，待分配TOC\o"1-5"\h\zi 1 k的席位为m个，理想化的分配结果是Pi（i=1,2,...,k）,满足m=YPj，记i=1q=Lm（i=1,2,...,k）。显然，若q全为整数，应有q=p（i=1,2,...,k）,当q不全为整数in i ii i时,需要确定同时满足下面公理的分配方案。公理一：lq]<p<[q]（i=1,2,...,k）,即p取[q]或[q]之一，其中i-ii+ i i- i+[q]=[q],[q]=[q.]+1,[q]表示q的整数部分。i-ii+I i i公理二：P（m,n,n，…，n）<p（m+1,n,n，…，n）,i=1,2,...,k，即总席位增加时，各i1 2ki 1 2k宿舍的席位数不应该减少。公理一显然满足Balinsky&Young不可能定理（见附录）中的公理4（公平分摊性），公理二满足其的公理1（人口单调性）和公理3（名额单调性）。令s=2m—二m=q-[q],in |_n _| ii——s称其为对第l个宿舍的绝对尾数值。令r=由，称其为对第I个宿舍的相对尾数值。i—3.4.2模型建立与求解由于人数都是整数，为使分配趋于公平，需所有的r越小越好，所以趋于公平的分配方案i应该是最大的r达到最小，即所有的r达到最小。i i为方便起见，首先考虑只有两个宿舍的情形，即k=2,n=n+n，且n丰n,q和q1 2 12 12 ---.^^一一一--一一--.——一..、 .一.一一一一^^^一不全是整数（实际上,他们同为整数或小数）。记p,,r为总席位增加一席时的分配结果和相对尾数。给出定理：定理：以下分配方案满足公理一,二，

「n ]+1,p=「n]TmTmLn」2Ln」,即按比例加惯例且*>%，则取P1=1）法分配;1）2）3）定理证明见附录。按照定理，对三个宿舍的情形进行讨论。设二，r,七全部为零（实际上，如果有一个为零,即是按两个宿舍分配），可以做以下分配：1）当[=r2=七时，按比例分配取整后，剩余的席位分配给绝对尾数较大的宿舍,即按比例加惯例法分配；2） 当二>r=r3时,按比例分配后，若剩余一个席位，则分配给第一个宿舍，若剩余两个席位，则分配一席给第一个宿舍，另外一席分配给第二三个宿舍中绝对尾数值较大者；3） 当二=r>七时，按比例分配后，若剩余一个席位分配给第一二个宿舍中绝对尾数值较大者，若剩余两个席位，则分配给第一二宿舍各一席；TOC\o"1-5"\h\z4）当r>r>r时，按比例分配后，若剩余一个席位,则分配给第一个宿舍,若剩余两1 2 3个席位，则分配给第二个宿舍。一般地，对k个宿舍，设r,r，…，r不全为零，且r>r>...>r，1 2 n 1 2 k将剩余的t=m—£Lm 个席位分配给第一至第t个宿舍各一席，当r>r=r>r\o"CurrentDocument"n t—1 t t+1 t+2i=1L 」—当r>r-r=r（1<s<k一t）时，t=m—Et+1i当r>r-r=r（1<s<k一t）时，t=m—Et+1i=1n—i~mn个席位分配给第一至第t—1个宿舍及st,st+1…%中较大的宿舍各一席，当"一s>"一函=r^（1<s,s'<k一t），个席位分配给第一至第t—s个宿舍及st,七+1，…s心中s个较大的所i=1对应的宿舍各一席。最后，编写出尾数法的MATLAB程序，实现3本题中的名额分配（附录-程序7，附录-

输入及运行结果4）。表4（尾数法分配结果）:宿舍人数10个名额的分配15个名额的分配A23534B33335C43246总数100010154模型检验及结果分析席位分配的尾数模型满足Young公理的1、3、4条，是以严格证明了的定理形式给出。对按上述四种分配模型分配的结果列表比较。表5（各方法分配结果的比较1）：宿舍学生人数20个席位的分配21个席位的分配BQDRBQDRA1031011111011111110B6366667677C3443343434总数2002020202021212121表6（各方法分配结果的比较2）：宿舍学生人数10个席位的分配15个席位的分配BQDRBQDRA23532234434B33333335555C43245546676总数10001010101015151515表格中，B表示比例加惯例法，Q表示Q值法，D表示D,hondt法，R表示相对尾数法。“比例加惯例”法用各团体人数占团体总人数的比例乘以总席位数取其整数位为第一次分配，再次分配时，则按小数位的大小分，大的先分配，直到席位分完。从表4看到，当总席位数增加时，C宿舍分得的席位却减少；Q值法利用相对不公平度建立了衡量不公平程度的数量指标，进而将席位分给最不公平的一方。D’hondt方法将各团体的人数用正整数相除，其商数组成一个表，将数从大到小取，直到取得的商数的个数等于总席位数，统计出每个团体被取到的商数的个数，即为该团体分得的席位数。5优缺点分析及改进从对模型的检验与分析可以看到，上面讨论的三个模型都有自身的不足：比例加惯例法满足公理一，却不满足公理二；Q值法满足公理二但不满足公理一；D’hondt法也不能解决对每个宿舍成员公平的大小问题；尾数法虽然满足公理一和二，但由于两个公理本身只满足Young公理体系的部分，也不尽完美。优点：尾数模型打破Q值法的对绝对尾数的比较方法，以相对尾数来讨论，使得模型满足了Young公理体系中更多的公理，虽不尽完善，但相比之前的四种方法是很大的改进。并且，这种对已有方法改进的思想很有启发意义。改进：本文中只给出了尾数法对3个宿舍的名额分配程序，对不定数量宿舍的分配没能程序实现，是可以改进的。参考文献[1]姜启源等数学建模[M](第三版)北京高等教育出版社,2004.24—27.[2]岳林关于Q值法的一种新定义[J].系统工程.1995,13(4):70—73.[3]高尚席位分配的最大熵法[J].数学的实践与认识,1996,26(2):73—75.[4]吴承祯，洪伟资源公平分配的遗传算法研究[J].运筹与管理,1998,7(2):23—28.[5]吴黎军名额分配问题中的2拟合法[J].生物数学报,1995,10(3):77—81.[6]严余松席位分配问题的0-1规划模型[J].系统工程,1996,14(5):51—53.[7]林建良席位分配的最小极差法[J].华南理工大学学报,2001,29(1):21—23.[8]杜跃鹏杜太生席位分配的最大概率法[J].数学的实践与认识,2003,33(7):15—19.[9]王秀莲席位分配问题的相对尾数法[J].数学的实践与认识,2007,37(9):81—85.附录Balinsky&Young不可能定理公理1(份额单调性)一个州人口的增加不会导致它失去席位。公理2(无偏性)在整个时间上平均，每个州应得到它自己应分摊的份额。公理3(席位单调性)总席位增加不会导致某个州名额减少。公理4(公平分摊性)任何州的席位数都不会偏离其比例的份额数。公理5(接近份额性)没有从一个州到另一个州的名额转让会使得这两个州都接近它们应得的份额。程序：函数bili.mfunction[me,m]=bili(n,N,M)me=n.*(M/N);m=floor(me);i=length(n);fprintf('按比例分配的结果：\n');forj=1:ifprintf(第%g个宿舍的人数为:%g\n',j,m(j));end函数guanli.mfunctionguanli(e,m,M)[maxe,j]=max(e);fprintf('给第%g个宿舍再分一个名额',j);m(j)=m(j)+1;e(j)=0;ifsum(m)==Mfprintf('\n\n\n按比例加惯例法分配的结果是：\n');fori=1:length(m)

fprintf('第%g个宿舍名额为：%g\n',i,m(i));elseendelseguanli(e,m,M);end函数biliguanli.mfunctionbiliguanli()n=input('各宿舍人数输入格式[number]:');N=sum(n);M=input(输入总席位数:');[me,m]=bili(n,N,M);e=me-m;ife〜=0guanli(e,m,M);elsefprintf('\n\n\n按比例加惯例法分配的结果是：\n');fori=1:length(m)fprintf('第%g个宿舍名额为：％g\n',i,m(i));endend函数qzhi.mfunctionqzhi(q,m,M)[maxq,j]=max(q);fprintf('给第%g个宿舍再分一个名额\n',j);m(j)=m(j)+1;q(j)=0;ifsum(m)==Mfprintf('\n\n\n按Q值法分配的结果是：\n');fori=1:length(m)fprintf('第%g个宿舍名额为：％g\n',i,m(i));endelseqzhi(q,m,M);end函数Qzhifa.mfunctionQzhifa()n=input('输入各宿舍人数格式为：[number]:');N=sum(n);M=input(输入总席位数:');[me,m]=bili(n,N,M);fprintf('各宿舍的Q值为：\n')fori=1:length(n)q(i)=n(i)A2/(m(i)*(m(i)+1));fprintf('%g\n',q(i));endfprintf('按Q值分配的结果：\n');ifme~=mqzhi(q,m,M);elsefprintf('\n\n\n按Q值法分配的结果是：\n');fori=1:length(m)fprintf('第%g个宿舍名额为：%g\n',i,m(i));endend函数dhondt.mfunctiondhondt()n=input('各宿舍人数输入格式[number]:');N=sum(n);M=input(输入总席位数:');nm=0;k=length(n);m(k)=0;s=0;fori=1:Mforj=1:ks=(i-1)*k+j;nm(s)=n(j)/i;endendfprintf('按D''hondt分配顺序为：\n\n')fori=1:M[maxd,j]=max(nm);l=mod(j,k);ifl==0l=k;endfprintf('分给第%g个宿舍一个名额赤,】)；m(l)=m(l)+1;nm(j)=0;endfprintf('分配结果：\n');fori=1:kfprintf(第%g个宿舍%g个名额\n',i,m(i));end函数weishufa3.mfunctionweishufa3()n=input('输入3个宿舍人数输入格式[number]:');N=sum(n);M=input(输入总席位数:');[ms,m]=bili(n,N,M);s=ms-m;r=s./m;ifs~=0fori=1:3[maxr,k]=max(r);R(i,:)=[r(k),s(k),k];r(k)=0;endendt=M-sum(m);fori=1:tj=R(i,3);m(j)=m(j)+1;endfprintf('\n\n\n按相对尾数法分配的结果是：\n');fori=1:3fprintf(第%g个宿舍名额为：％g\n',i,m(i));end输入及运行结果：1表1结果>>biliguanli各宿舍人数输入格式[number]:[235333432]输入总席位数:10按比例分配的结果：第1个宿舍的人数为:2第2个宿舍的人数为:3第3个宿舍的人数为:4给第1个宿舍再分一个名额按比例加惯例法分配的结果是：第1个宿舍名额为：3第2个宿舍名额为：3第3个宿舍名额为：4>>biliguanli各宿舍人数输入格式[number]:[235333432]输入总席位数：15按比例分配的结果：第1个宿舍的人数为:3第2个宿舍的人数为:4第3个宿舍的人数为:6给第2个宿舍再分一个名额给第1个宿舍再分一个名额按比例加惯例法分配的结果是：第1个宿舍名额为：4第2个宿舍名额为：5第3个宿舍名额为：62表2结果>>Qzhifa输入各宿舍人数格式为：[number]:[235333432]输入总席位数：10按比例分配的结果：第1个宿舍的人数为:2第2个宿舍的人数为:3第3个宿舍的人数为:4各宿舍的Q值为：9204.179240.759331.2按Q值分配的结果：给第3个宿舍再分一个名额按Q值法分配的结果是：第1个宿舍名额为：2第2个宿舍名额为：3第3个宿舍名额为：5>>Qzhifa输入各宿舍人数格式为：[number]:[235333432]输入总席位数：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]:[235333432]输入总席位数：10按D,hondt分配顺序为：分给第3个宿舍一个名额分给第2个宿舍一个名额分给第1个宿舍一个名额分给第3个宿舍一个名额分给第2个宿舍一个名额分给第3个宿舍一个名额分给第1个宿舍一个名额分给第2个宿舍一个名额分给第3个宿舍一个名额分给第3个宿舍一个名额分配结果：第1个宿舍2个名额第2个宿舍3个名额第3个宿舍5个名额>>dh