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

1、席位分配問題的Dhondt模型和相對(duì)尾數(shù)模型摘要：討論公平席位分配的模型已有很多。本文首先用比例加慣例法、Q值法、Dhondt法對(duì)問題中名額進(jìn)行了分配，再對(duì)Dhondt法的合理性進(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法

2、，即比例加慣例法；后來出現(xiàn)了Q值法；1974年M.L.Balinski和H.P.Young引入了席位分配問題的公理體系研究方法，并于1982年證明了同時(shí)滿足五個(gè)公理的席位分配方法是不存在的；因此，我們只能根據(jù)實(shí)際建立在一定公平準(zhǔn)則下成立并盡量多的滿足Young公理的算法。這里，我們需要理解并運(yùn)用比例加慣例法、Q值法、Dhondt法對(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)意義第個(gè)宿舍的

3、Q值第個(gè)宿舍的人數(shù)第個(gè)宿舍分配的名額總?cè)藬?shù)總名額數(shù)第個(gè)宿舍的理想分配名額總席位增加一個(gè)時(shí)第個(gè)宿舍的理想分配名額第個(gè)宿舍的分配比例，即第個(gè)宿舍的絕對(duì)尾數(shù)值第個(gè)宿舍的相對(duì)尾數(shù)值總席位增加一席時(shí)第個(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.

4、2按Q值法模型分配首先用比例分配法對(duì)名額進(jìn)行初步分配，再根據(jù)表達(dá)式 對(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.3 Dhondt模型3.3.1 模型建立設(shè)，分別表示宿舍總?cè)藬?shù)和總分配席位數(shù)，()表示各宿舍人數(shù)，令()，則得到一個(gè)數(shù)列，將該數(shù)列按遞減順序重新排列，得

5、到，其中表示中第大的項(xiàng)。取中前項(xiàng)，則相應(yīng)得到()，,即為按Dhondt模型分配的結(jié)果。3.3.2 按Dhondt模型分配根據(jù)建立的Dhondt模型，編寫MATLAB程序求出結(jié)果（附件-程序6，附錄-輸入及運(yùn)行結(jié)果3）：表3（Dhondt模型分配結(jié)果）：宿舍人數(shù)10個(gè)名額的分配15個(gè)名額的分配A23523B33335C43257總數(shù)100010153.4 相對(duì)尾數(shù)模型3.4.1 模型準(zhǔn)備討論一般情況:個(gè)宿舍人數(shù)分別為,總?cè)藬?shù)為,待分配的席位為個(gè),理想化的分配結(jié)果是(),滿足,記()。顯然,若全為整數(shù),應(yīng)有=(),當(dāng)不全為整數(shù)時(shí),需要確定同時(shí)滿足下面公理的分配方案。公理一：(),即取或之一,其中=

6、,=,表示的整數(shù)部分。公理二：,即總席位增加時(shí),各宿舍的席位數(shù)不應(yīng)該減少。公理一顯然滿足Balinsky & Young不可能定理 (見附錄) 中的公理4（公平分?jǐn)傂裕?公理二滿足其的公理1（人口單調(diào)性）和公理3（名額單調(diào)性）。令,稱其為對(duì)第個(gè)宿舍的絕對(duì)尾數(shù)值。令,稱其為對(duì)第個(gè)宿舍的相對(duì)尾數(shù)值。3.4.2 模型建立與求解由于人數(shù)都是整數(shù),為使分配趨于公平,需所有的越小越好,所以趨于公平的分配方案應(yīng)該是最大的達(dá)到最小,即所有的達(dá)到最小。為方便起見,首先考慮只有兩個(gè)宿舍的情形,即,且,和不全是整數(shù)(實(shí)際上,他們同為整數(shù)或小數(shù))。記,為總席位增加一席時(shí)的分配結(jié)果和相對(duì)尾數(shù)。給出定理:定理:以

7、下分配方案滿足公理一,二，1) 若,且,則取,即按比例加慣例法分配;2) 若,則取,;3) 若,則取,。定理證明見附錄。按照定理，對(duì)三個(gè)宿舍的情形進(jìn)行討論。設(shè),全部為零(實(shí)際上,如果有一個(gè)為零,即是按兩個(gè)宿舍分配),可以做以下分配:1) 當(dāng)時(shí),按比例分配取整后,剩余的席位分配給絕對(duì)尾數(shù)較大的宿舍,即按比例加慣例法分配;2) 當(dāng)時(shí),按比例分配后,若剩余一個(gè)席位,則分配給第一個(gè)宿舍,若剩余兩個(gè)席位,則分配一席給第一個(gè)宿舍,另外一席分配給第二三個(gè)宿舍中絕對(duì)尾數(shù)值較大者；3) 當(dāng)時(shí)，按比例分配后，若剩余一個(gè)席位分配給第一二個(gè)宿舍中絕對(duì)尾數(shù)值較大者，若剩余兩個(gè)席位，則分配給第一二宿舍各一席；4) 當(dāng)時(shí)，

8、按比例分配后,若剩余一個(gè)席位,則分配給第一個(gè)宿舍,若剩余兩個(gè)席位,則分配給第二個(gè)宿舍。一般地，對(duì)個(gè)宿舍，設(shè),，不全為零，且，則當(dāng)時(shí)，將剩余的個(gè)席位分配給第一至第個(gè)宿舍各一席，當(dāng)時(shí)， 個(gè)席位分配給第一至第個(gè)宿舍及和較大的宿舍各一席，當(dāng)（）時(shí)， 個(gè)席位分配給第一至第個(gè)宿舍及，中較大的宿舍各一席，當(dāng)（）， 個(gè)席位分配給第一至第個(gè)宿舍及，中個(gè)較大的所對(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é)

9、果分析席位分配的尾數(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

10、表示D'hondt法，R表示相對(duì)尾數(shù)法?！氨壤討T例”法用各團(tuán)體人數(shù)占團(tuán)體總?cè)藬?shù)的比例乘以總席位數(shù), 取其整數(shù)位為第一次分配, 再次分配時(shí), 則按小數(shù)位的大小分, 大的先分配, 直到席位分完。從表4看到，當(dāng)總席位數(shù)增加時(shí)，C宿舍分得的席位卻減少；Q值法利用相對(duì)不公平度建立了衡量不公平程度的數(shù)量指標(biāo), 進(jìn)而將席位分給最不公平的一方。 Dhondt方法將各團(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è)模型都有自身

11、的不足：比例加慣例法滿足公理一，卻不滿足公理二；Q值法滿足公理二但不滿足公理一；Dhondt法也不能解決對(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.2

12、427. 2 岳林 關(guān)于Q值法的一種新定義J. 系統(tǒng)工程.1995,13(4):7073. 3 高尚 席位分配的最大熵法J.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),1996,26(2):7375. 4 吳承禎,洪偉 資源公平分配的遺傳算法研究J.運(yùn)籌與管理,1998,7(2):2328. 5 吳黎軍 名額分配問題中的擬合法J.生物數(shù)學(xué)報(bào),1995,10(3):7781. 6 嚴(yán)余松 席位分配問題的0-1規(guī)劃模型J.系統(tǒng)工程,1996,14(5):5153. 7 林建良 席位分配的最小極差法J.華南理工大學(xué)學(xué)報(bào),2001,29(1):2123. 8 杜躍鵬 杜太生 席位分配的最大概率法J.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2003,

13、33(7):1519. 9 王秀蓮 席位分配問題的相對(duì)尾數(shù)法J.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2007,37(9):8185.附錄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)得的份額。程序：1 函數(shù)bili.mfunction me,m=bili(n,N,M)

14、me=n.*(M/N);m=floor(me);i=length(n);fprintf('按比例分配的結(jié)果 : n');for j=1:i fprintf('第 %g 個(gè)宿舍的人數(shù)為: %g n',j,m(j);end 2 函數(shù)guanli.mfunction guanli(e,m,M)maxe,j=max(e);fprintf('給第 %g 個(gè)宿舍再分一個(gè)名額',j);m(j)=m(j)+1;e(j)=0;if sum(m)=M fprintf('nnn按比例加慣例法分配的結(jié)果是 : n'); for i=1:length(m)

15、 fprintf('第 %g 個(gè)宿舍名額為 : %gn',i,m(i); endelse guanli(e,m,M);end3 函數(shù)biliguanli.mfunction biliguanli()n=input('各宿舍人數(shù) 輸入格式 number :');N=sum(n);M=input('輸入總席位數(shù) :');me,m=bili(n,N,M);e=me-m;if e=0guanli(e,m,M);else fprintf('nnn按比例加慣例法分配的結(jié)果是 : n'); for i=1:length(m) fprintf(&

16、#39;第 %g 個(gè)宿舍名額為 : %gn',i,m(i); endend4 函數(shù)qzhi.mfunction qzhi(q,m,M)maxq,j=max(q);fprintf('給第 %g 個(gè)宿舍再分一個(gè)名額n',j);m(j)=m(j)+1;q(j)=0;if sum(m)=M fprintf('nnn按Q值法分配的結(jié)果是 : n'); for i=1:length(m) fprintf('第 %g 個(gè)宿舍名額為 : %gn',i,m(i); endelse qzhi(q,m,M);end5 函數(shù)Qzhifa.mfunction Qz

17、hifa()n=input('輸入各宿舍人數(shù) 格式為： number :');N=sum(n);M=input('輸入總席位數(shù) :');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值分配的結(jié)果 : n');if me=mqzhi(q,m,M);else fprintf('nnn按Q值法分配的結(jié)果是 : n'); fo

18、r i=1:length(m) fprintf('第 %g 個(gè)宿舍名額為 : %gn',i,m(i); endend6 函數(shù) dhondt.mfunction dhondt()n=input('各宿舍人數(shù) 輸入格式 number :');N=sum(n);M=input('輸入總席位數(shù) :');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分配順序?yàn)椋簄n')f

19、or i=1:M maxd,j=max(nm); l=mod(j,k); if l=0 l=k; end fprintf('分給第 %g 個(gè)宿舍一個(gè)名額n',l); m(l)=m(l)+1; nm(j)=0;endfprintf('分配結(jié)果：n');for i=1:k fprintf('第 %g 個(gè)宿舍 %g 個(gè)名額n',i,m(i);end7 函數(shù)weishufa3.mfunction weishufa3()n=input('輸入3個(gè)宿舍人數(shù) 輸入格式 number :');N=sum(n);M=input('輸入總席位

20、數(shù) :');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按相對(duì)尾數(shù)法分配的結(jié)果是 : n');for i=1:3 fprintf('第 %g 個(gè)宿舍名額為 : %gn',i,m(i);end輸入及運(yùn)行結(jié)果：1 表1結(jié)果>> biliguanli各宿舍人數(shù) 輸入格式 number :

21、235 333 432輸入總席位數(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 :235 333 432輸入總席位數(shù) :15按比例分配的結(jié)果 : 第 1 個(gè)宿舍的人數(shù)為: 3 第 2 個(gè)宿舍的人數(shù)為: 4 第 3 個(gè)宿舍的人數(shù)為: 6 給第 2 個(gè)宿舍再分一個(gè)名額給第 1 個(gè)宿舍再分一個(gè)名額按比例加慣例法分

22、配的結(jié)果是 : 第 1 個(gè)宿舍名額為 : 4第 2 個(gè)宿舍名額為 : 5第 3 個(gè)宿舍名額為 : 62 表2結(jié)果>> Qzhifa輸入各宿舍人數(shù) 格式為： number :235 333 432輸入總席位數(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ù)

23、格式為： number :235 333 432輸入總席位數(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 :235 333 432輸入總席位數(shù) :10按 D'hondt分配順序?yàn)椋悍纸o第 3 個(gè)

24、宿舍一個(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è)名額>> dhondt各宿舍人數(shù) 輸入格式 number :235 333 432輸入總席位數(shù) :15按 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è)名額分給第