席位分配問題的Dhondt模型和相對(duì)尾數(shù)模型

席位分配問題的D’hondt模型和相對(duì)尾數(shù)模型摘要：討論公平席位分配的模型已有很多。本文首先用比例加慣例法、Q值法、D’hondt法對(duì)問題中名額進(jìn)行了分配，再對(duì)D’hondt法的合理性進(jìn)行了分析，并在Q值法對(duì)絕對(duì)尾數(shù)（絕對(duì)不公平度）的處理方式基礎(chǔ)上，提出了相對(duì)尾數(shù)模型，并討論了其滿足Young公理的1，3，4條；在模型求解上，全部由MATLAB程序來實(shí)現(xiàn)名額分配。關(guān)鍵詞：相對(duì)尾數(shù) Balinsky&Young不可能定理 MATLAB正文1問題復(fù)述公平的席位分配問題是一個(gè)非常有趣而重要的問題，它在政治學(xué)、管理學(xué)和對(duì)策論等領(lǐng)域具有廣泛的應(yīng)用價(jià)值。處理這個(gè)問題的最早的方法是Hamilton法，即比例加慣例法；后來出現(xiàn)了Q值法；1974年M.L.Balinski和H.P.Young引入了席位分配問題的公理體系研究方法，并于1982年證明了同時(shí)滿足五個(gè)公理的席位分配方法是不存在的；因此，我們只能根據(jù)實(shí)際建立在一定公平準(zhǔn)則下成立并盡量多的滿足Young公理的算法。這里，我們需要理解并運(yùn)用比例加慣例法、Q值法、D’hondt法對(duì)宿舍委員會(huì)名額進(jìn)行分配，繼而提出更優(yōu)的公平分配席位的方法。2模型假設(shè)2.1合理假設(shè)2.1.1比例加慣例法、Q值法等分配模型均為已知；2.1.2各個(gè)宿舍相互獨(dú)立互不影響，人數(shù)保持不變；2.1.3委員分配以各宿舍人數(shù)為唯一權(quán)重。2.2符號(hào)約定符號(hào)意義Qi第i個(gè)宿舍的Q值ni第i個(gè)宿舍的人數(shù)mi第i個(gè)宿舍分配的名額n總?cè)藬?shù)m總名額數(shù)pi第i個(gè)宿舍的理想分配名額—pi總席位增加一個(gè)時(shí)第i個(gè)宿舍的理想分配名額qi第i個(gè)宿舍的分配比例，即nimnsi第i個(gè)宿舍的絕對(duì)尾數(shù)值ri第i個(gè)宿舍的相對(duì)尾數(shù)值—ri總席位增加一席時(shí)第i個(gè)宿舍的相對(duì)尾數(shù)值

按比例分配后剩余名額3模型的建立與求解3.1按比例加慣例模型分配根據(jù)比例加慣例分配模型的原理，編寫MATLAB程序?qū)崿F(xiàn)（附錄-程序1,2,3,附錄-輸入及運(yùn)行結(jié)果1）,結(jié)果如表所示：表1（比例加慣例法分配結(jié)果）:宿舍學(xué)生人數(shù)10個(gè)席位的分配15個(gè)席位的分配比例分配的席位慣例分配的結(jié)果比例分配的席位慣例分配的結(jié)果A2352334B3333345C4324466總數(shù)100091013153.2按Q值法模型分配n2首先用比例分配法對(duì)名額進(jìn)行初步分配，再根據(jù)表達(dá)式Q=mm+Di=A，B，Cii對(duì)剩下的名額進(jìn)行分配，編寫MATLAB程序?qū)崿F(xiàn)求解（附錄-程序4,5，附錄-輸入及運(yùn)行結(jié)果2）：表2（Q值法分配結(jié)果）：宿舍學(xué)生人數(shù)10個(gè)席位的分配15個(gè)席位的分配比例分配名額Q值最終分配名額比例分配名額Q值最終分配名額A23529204.17234602.084B33339240.75345544.455C43249331.2564443.436總數(shù)100091013153.3D’hondt模型3.3.1模型建立設(shè)n，m分別表示宿舍總?cè)藬?shù)和總分配席位數(shù)， 七（i=1,2,3）表示各宿舍人數(shù)，令七=nj（i=1,2,3,j=1,2,...），則得到一個(gè)數(shù)列J,將該數(shù)列按遞減順序重新排列，得(a(k(a(k)}中第k大的項(xiàng)。取

j=^a(k)}(k=1,2,...,m)中i=p的元素的個(gè)數(shù)"p=1,2,3),mij 1其中ajk）表示?）｝中前m項(xiàng)，則相應(yīng)得到m2,m3即為按D’hondt模型分配的結(jié)果。3.3.2按D’hondt模型分配根據(jù)建立的D’hondt模型，編寫MATLAB程序求出結(jié)果（附件-程序6，附錄-輸入及運(yùn)行結(jié)果3）：表3（D’hondt模型分配結(jié)果）:宿舍人數(shù)10個(gè)名額的分配15個(gè)名額的分配A23523B33335C43257總數(shù)100010153.4 相對(duì)尾數(shù)模型3.4.1模型準(zhǔn)備討論一般情況：k個(gè)宿舍人數(shù)分別為n,i=1,2,...,k，總?cè)藬?shù)為n=n+...+n，待分配TOC\o"1-5"\h\zi 1 k的席位為m個(gè)，理想化的分配結(jié)果是Pi（i=1,2,...,k）,滿足m=YPj，記i=1q=Lm（i=1,2,...,k）。顯然，若q全為整數(shù)，應(yīng)有q=p（i=1,2,...,k）,當(dāng)q不全為整數(shù)in i ii i時(shí),需要確定同時(shí)滿足下面公理的分配方案。公理一：lq]<p<[q]（i=1,2,...,k）,即p取[q]或[q]之一，其中i-ii+ i i- i+[q]=[q],[q]=[q.]+1,[q]表示q的整數(shù)部分。i-ii+I i i公理二：P（m,n,n，…，n）<p（m+1,n,n，…，n）,i=1,2,...,k，即總席位增加時(shí)，各i1 2ki 1 2k宿舍的席位數(shù)不應(yīng)該減少。公理一顯然滿足Balinsky&Young不可能定理（見附錄）中的公理4（公平分?jǐn)傂裕矶M足其的公理1（人口單調(diào)性）和公理3（名額單調(diào)性）。令s=2m—二m=q-[q],in |_n _| ii——s稱其為對(duì)第l個(gè)宿舍的絕對(duì)尾數(shù)值。令r=由，稱其為對(duì)第I個(gè)宿舍的相對(duì)尾數(shù)值。i—3.4.2模型建立與求解由于人數(shù)都是整數(shù)，為使分配趨于公平，需所有的r越小越好，所以趨于公平的分配方案i應(yīng)該是最大的r達(dá)到最小，即所有的r達(dá)到最小。i i為方便起見，首先考慮只有兩個(gè)宿舍的情形，即k=2,n=n+n，且n豐n,q和q1 2 12 12 ---.^^一一一--一一--.——一..、 .一.一一一一^^^一不全是整數(shù)（實(shí)際上,他們同為整數(shù)或小數(shù)）。記p,,r為總席位增加一席時(shí)的分配結(jié)果和相對(duì)尾數(shù)。給出定理：定理：以下分配方案滿足公理一,二，

「n ]+1,p=「n]TmTmLn」2Ln」,即按比例加慣例且*>%，則取P1=1）法分配;1）2）3）定理證明見附錄。按照定理，對(duì)三個(gè)宿舍的情形進(jìn)行討論。設(shè)二，r,七全部為零（實(shí)際上，如果有一個(gè)為零,即是按兩個(gè)宿舍分配），可以做以下分配：1）當(dāng)[=r2=七時(shí)，按比例分配取整后，剩余的席位分配給絕對(duì)尾數(shù)較大的宿舍,即按比例加慣例法分配；2） 當(dāng)二>r=r3時(shí),按比例分配后，若剩余一個(gè)席位，則分配給第一個(gè)宿舍，若剩余兩個(gè)席位，則分配一席給第一個(gè)宿舍，另外一席分配給第二三個(gè)宿舍中絕對(duì)尾數(shù)值較大者；3） 當(dāng)二=r>七時(shí)，按比例分配后，若剩余一個(gè)席位分配給第一二個(gè)宿舍中絕對(duì)尾數(shù)值較大者，若剩余兩個(gè)席位，則分配給第一二宿舍各一席；TOC\o"1-5"\h\z4）當(dāng)r>r>r時(shí)，按比例分配后，若剩余一個(gè)席位,則分配給第一個(gè)宿舍,若剩余兩1 2 3個(gè)席位，則分配給第二個(gè)宿舍。一般地，對(duì)k個(gè)宿舍，設(shè)r,r，…，r不全為零，且r>r>...>r，1 2 n 1 2 k將剩余的t=m—￡Lm 個(gè)席位分配給第一至第t個(gè)宿舍各一席，當(dāng)r>r=r>r\o"CurrentDocument"n t—1 t t+1 t+2i=1L 」—當(dāng)r>r-r=r（1<s<k一t）時(shí)，t=m—Et+1i當(dāng)r>r-r=r（1<s<k一t）時(shí)，t=m—Et+1i=1n—i~mn個(gè)席位分配給第一至第t—1個(gè)宿舍及st,st+1…%中較大的宿舍各一席，當(dāng)"一s>"一函=r^（1<s,s'<k一t），個(gè)席位分配給第一至第t—s個(gè)宿舍及st,七+1，…s心中s個(gè)較大的所i=1對(duì)應(yīng)的宿舍各一席。最后，編寫出尾數(shù)法的MATLAB程序，實(shí)現(xiàn)3本題中的名額分配（附錄-程序7，附錄-

輸入及運(yùn)行結(jié)果4）。表4（尾數(shù)法分配結(jié)果）:宿舍人數(shù)10個(gè)名額的分配15個(gè)名額的分配A23534B33335C43246總數(shù)100010154模型檢驗(yàn)及結(jié)果分析席位分配的尾數(shù)模型滿足Young公理的1、3、4條，是以嚴(yán)格證明了的定理形式給出。對(duì)按上述四種分配模型分配的結(jié)果列表比較。表5（各方法分配結(jié)果的比較1）：宿舍學(xué)生人數(shù)20個(gè)席位的分配21個(gè)席位的分配BQDRBQDRA1031011111011111110B6366667677C3443343434總數(shù)2002020202021212121表6（各方法分配結(jié)果的比較2）：宿舍學(xué)生人數(shù)10個(gè)席位的分配15個(gè)席位的分配BQDRBQDRA23532234434B33333335555C43245546676總數(shù)10001010101015151515表格中，B表示比例加慣例法，Q表示Q值法，D表示D,hondt法，R表示相對(duì)尾數(shù)法。“比例加慣例”法用各團(tuán)體人數(shù)占團(tuán)體總?cè)藬?shù)的比例乘以總席位數(shù)取其整數(shù)位為第一次分配，再次分配時(shí)，則按小數(shù)位的大小分，大的先分配，直到席位分完。從表4看到，當(dāng)總席位數(shù)增加時(shí)，C宿舍分得的席位卻減少；Q值法利用相對(duì)不公平度建立了衡量不公平程度的數(shù)量指標(biāo)，進(jìn)而將席位分給最不公平的一方。D’hondt方法將各團(tuán)體的人數(shù)用正整數(shù)相除，其商數(shù)組成一個(gè)表，將數(shù)從大到小取，直到取得的商數(shù)的個(gè)數(shù)等于總席位數(shù)，統(tǒng)計(jì)出每個(gè)團(tuán)體被取到的商數(shù)的個(gè)數(shù)，即為該團(tuán)體分得的席位數(shù)。5優(yōu)缺點(diǎn)分析及改進(jìn)從對(duì)模型的檢驗(yàn)與分析可以看到，上面討論的三個(gè)模型都有自身的不足：比例加慣例法滿足公理一，卻不滿足公理二；Q值法滿足公理二但不滿足公理一；D’hondt法也不能解決對(duì)每個(gè)宿舍成員公平的大小問題；尾數(shù)法雖然滿足公理一和二，但由于兩個(gè)公理本身只滿足Young公理體系的部分，也不盡完美。優(yōu)點(diǎn)：尾數(shù)模型打破Q值法的對(duì)絕對(duì)尾數(shù)的比較方法，以相對(duì)尾數(shù)來討論，使得模型滿足了Young公理體系中更多的公理，雖不盡完善，但相比之前的四種方法是很大的改進(jìn)。并且，這種對(duì)已有方法改進(jìn)的思想很有啟發(fā)意義。改進(jìn)：本文中只給出了尾數(shù)法對(duì)3個(gè)宿舍的名額分配程序，對(duì)不定數(shù)量宿舍的分配沒能程序?qū)崿F(xiàn)，是可以改進(jìn)的。參考文獻(xiàn)[1]姜啟源等數(shù)學(xué)建模[M](第三版)北京高等教育出版社,2004.24—27.[2]岳林關(guān)于Q值法的一種新定義[J].系統(tǒng)工程.1995,13(4):70—73.[3]高尚席位分配的最大熵法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),1996,26(2):73—75.[4]吳承禎，洪偉資源公平分配的遺傳算法研究[J].運(yùn)籌與管理,1998,7(2):23—28.[5]吳黎軍名額分配問題中的2擬合法[J].生物數(shù)學(xué)報(bào),1995,10(3):77—81.[6]嚴(yán)余松席位分配問題的0-1規(guī)劃模型[J].系統(tǒng)工程,1996,14(5):51—53.[7]林建良席位分配的最小極差法[J].華南理工大學(xué)學(xué)報(bào),2001,29(1):21—23.[8]杜躍鵬杜太生席位分配的最大概率法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2003,33(7):15—19.[9]王秀蓮席位分配問題的相對(duì)尾數(shù)法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2007,37(9):81—85.附錄Balinsky&Young不可能定理公理1(份額單調(diào)性)一個(gè)州人口的增加不會(huì)導(dǎo)致它失去席位。公理2(無偏性)在整個(gè)時(shí)間上平均，每個(gè)州應(yīng)得到它自己應(yīng)分?jǐn)偟姆蓊~。公理3(席位單調(diào)性)總席位增加不會(huì)導(dǎo)致某個(gè)州名額減少。公理4(公平分?jǐn)傂?任何州的席位數(shù)都不會(huì)偏離其比例的份額數(shù)。公理5(接近份額性)沒有從一個(gè)州到另一個(gè)州的名額轉(zhuǎn)讓會(huì)使得這兩個(gè)州都接近它們應(yīng)得的份額。程序：函數(shù)bili.mfunction[me,m]=bili(n,N,M)me=n.*(M/N);m=floor(me);i=length(n);fprintf('按比例分配的結(jié)果：\n');forj=1:ifprintf(第%g個(gè)宿舍的人數(shù)為:%g\n',j,m(j));end函數(shù)guanli.mfunctionguanli(e,m,M)[maxe,j]=max(e);fprintf('給第%g個(gè)宿舍再分一個(gè)名額',j);m(j)=m(j)+1;e(j)=0;ifsum(m)==Mfprintf('\n\n\n按比例加慣例法分配的結(jié)果是：\n');fori=1:length(m)

fprintf('第%g個(gè)宿舍名額為：%g\n',i,m(i));elseendelseguanli(e,m,M);end函數(shù)biliguanli.mfunctionbiliguanli()n=input('各宿舍人數(shù)輸入格式[number]:');N=sum(n);M=input(輸入總席位數(shù):');[me,m]=bili(n,N,M);e=me-m;ife?=0guanli(e,m,M);elsefprintf('\n\n\n按比例加慣例法分配的結(jié)果是：\n');fori=1:length(m)fprintf('第%g個(gè)宿舍名額為：％g\n',i,m(i));endend函數(shù)qzhi.mfunctionqzhi(q,m,M)[maxq,j]=max(q);fprintf('給第%g個(gè)宿舍再分一個(gè)名額\n',j);m(j)=m(j)+1;q(j)=0;ifsum(m)==Mfprintf('\n\n\n按Q值法分配的結(jié)果是：\n');fori=1:length(m)fprintf('第%g個(gè)宿舍名額為：％g\n',i,m(i));endelseqzhi(q,m,M);end函數(shù)Qzhifa.mfunctionQzhifa()n=input('輸入各宿舍人數(shù)格式為：[number]:');N=sum(n);M=input(輸入總席位數(shù):');[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值分配的結(jié)果：\n');ifme~=mqzhi(q,m,M);elsefprintf('\n\n\n按Q值法分配的結(jié)果是：\n');fori=1:length(m)fprintf('第%g個(gè)宿舍名額為：%g\n',i,m(i));endend函數(shù)dhondt.mfunctiondhondt()n=input('各宿舍人數(shù)輸入格式[number]:');N=sum(n);M=input(輸入總席位數(shù):');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分配順序?yàn)椋篭n\n')fori=1:M[maxd,j]=max(nm);l=mod(j,k);ifl==0l=k;endfprintf('分給第%g個(gè)宿舍一個(gè)名額赤,】)；m(l)=m(l)+1;nm(j)=0;endfprintf('分配結(jié)果：\n');fori=1:kfprintf(第%g個(gè)宿舍%g個(gè)名額\n',i,m(i));end函數(shù)weishufa3.mfunctionweishufa3()n=input('輸入3個(gè)宿舍人數(shù)輸入格式[number]:');N=sum(n);M=input(輸入總席位數(shù):');[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按相對(duì)尾數(shù)法分配的結(jié)果是：\n');fori=1:3fprintf(第%g個(gè)宿舍名額為：％g\n',i,m(i));end輸入及運(yùn)行結(jié)果：1表1結(jié)果>>biliguanli各宿舍人數(shù)輸入格式[number]:[235333432]輸入總席位數(shù):10按比例分配的結(jié)果：第1個(gè)宿舍的人數(shù)為:2第2個(gè)宿舍的人數(shù)為:3第3個(gè)宿舍的人數(shù)為:4給第1個(gè)宿舍再分一個(gè)名額按比例加慣例法分配的結(jié)果是：第1個(gè)宿舍名額為：3第2個(gè)宿舍名額為：3第3個(gè)宿舍名額為：4>>biliguanli各宿舍人數(shù)輸入格式[number]:[235333432]輸入總席位數(shù)：15按比例分配的結(jié)果：第1個(gè)宿舍的人數(shù)為:3第2個(gè)宿舍的人數(shù)為:4第3個(gè)宿舍的人數(shù)為:6給第2個(gè)宿舍再分一個(gè)名額給第1個(gè)宿舍再分一個(gè)名額按比例加慣例法分配的結(jié)果是：第1個(gè)宿舍名額為：4第2個(gè)宿舍名額為：5第3個(gè)宿舍名額為：62表2結(jié)果>>Qzhifa輸入各宿舍人數(shù)格式為：[number]:[235333432]輸入總席位數(shù)：10按比例分配的結(jié)果：第1個(gè)宿舍的人數(shù)為:2第2個(gè)宿舍的人數(shù)為:3第3個(gè)宿舍的人數(shù)為:4各宿舍的Q值為：9204.179240.759331.2按Q值分配的結(jié)果：給第3個(gè)宿舍再分一個(gè)名額按Q值法分配的結(jié)果是：第1個(gè)宿舍名額為：2第2個(gè)宿舍名額為：3第3個(gè)宿舍名額為：5>>Qzhifa輸入各宿舍人數(shù)格式為：[number]:[235333432]輸入總席位數(shù)：15按比例分配的結(jié)果：第1個(gè)宿舍的人數(shù)為:3第2個(gè)宿舍的人數(shù)為:4第3個(gè)宿舍的人數(shù)為:6各宿舍的Q值為：4602.085544.454443.43按Q值分配的結(jié)果：給第2個(gè)宿舍再分一個(gè)名額給第1個(gè)宿舍再分一個(gè)名額按Q值法分配的結(jié)果是:第1個(gè)宿舍名額為：4第2個(gè)宿舍名額為：5第3個(gè)宿舍名額為：63表3結(jié)果>>dhondt各宿舍人數(shù)輸入格式:number]:[235333432]輸入總席位數(shù)：10按D,hondt分配順序?yàn)椋悍纸o第3個(gè)宿舍一個(gè)名額分給第2個(gè)宿舍一個(gè)名額分給第1個(gè)宿舍一個(gè)名額分給第3個(gè)宿舍一個(gè)名額分給第2個(gè)宿舍一個(gè)名額分給第3個(gè)宿舍一個(gè)名額分給第1個(gè)宿舍一個(gè)名額分給第2個(gè)宿舍一個(gè)名額分給第3個(gè)宿舍一個(gè)名額分給第3個(gè)宿舍一個(gè)名額分配結(jié)果：第1個(gè)宿舍2個(gè)名額第2個(gè)宿舍3個(gè)名額第3個(gè)宿舍5個(gè)名額>>dh