席位分配問題理論研究-畢業(yè)論文

1、<p>　　存檔編號 </p><p><b>　　畢 業(yè) 論 文</b></p><p>　　題目 席位分配問題理論研究 </p><p>　　學(xué) 院 數(shù)學(xué)與信息科學(xué) </p><p>　　專 業(yè) 數(shù)學(xué)與應(yīng)用數(shù)學(xué) </p>&

2、lt;p>　　姓 名 </p><p>　　學(xué) 號 </p><p>　　指導(dǎo)教師 </p><p>　　完成時間 </p><p><b>　　目 錄</b&g

3、t;</p><p>　　North China University of Water Resources and Electric PowerI</p><p><b>　　摘 要i</b></p><p>　　ABSTRACTii</p><p><b>　　第一章 緒論3</b>&l

4、t;/p><p>　　1.1 經(jīng)典席位分配問題的研究背景與意義1</p><p>　　第二章 公平席位分配方法及其性質(zhì)研究1</p><p>　　2.1節(jié) 幾種經(jīng)典席位分配方法的分析總結(jié)2</p><p>　　2.2節(jié) 幾種席位分配方法的實例比較20</p><p>　　第三章 最小遺憾度與余額延續(xù)法24<

5、/p><p>　　3.1幾個分配方法的最小遺憾度判斷標(biāo)準(zhǔn)25</p><p>　　3.1.1 最小遺憾度標(biāo)準(zhǔn)的思想25</p><p>　　3.1.2幾個席位分配方法的遺憾度算法25</p><p>　　3.1.3最小遺憾度標(biāo)準(zhǔn)的實例論證26</p><p>　　3.2最小遺憾度的席位分配方法27</p&g

6、t;<p>　　3.2.1最小遺憾度法的分配方法28</p><p>　　3.2.2最小遺憾度法的實例論證28</p><p>　　3.3 余額延續(xù)的席位分配法29</p><p>　　3.3.1余額延續(xù)法思想29</p><p>　　3.3.2余額延續(xù)法的分配方法30</p><p>　　3.

7、3.3余額延續(xù)法的實例論證30</p><p><b>　　參考文獻(xiàn)32</b></p><p><b>　　致 謝33</b></p><p><b>　　附 錄34</b></p><p>　　席位分配問題理論研究</p><p><

8、b>　　摘 要</b></p><p>　　本文第二章對Hamilton、經(jīng)典Q值法、CQ值法、改進(jìn)Q值法、新Q值法、最小極值法、0-1規(guī)劃法、平均公平度法、相對尾數(shù)法、公平累加法等席位分配方法問題進(jìn)行了研究，并通過具體例子分析了各個方法的優(yōu)劣性。</p><p>　　第一部分定義了關(guān)于席位分配方法的最小遺憾度標(biāo)準(zhǔn)，根據(jù)各個分配方法在某次分配中的分配結(jié)果，計算出哪種方法使

9、各部門的遺憾度最小，進(jìn)而確定哪種分配方法為本次分配的最佳分配方法。得出：某一種分配方法并不完全適合每一次席位分配。</p><p>　　第二部分根據(jù)最小遺憾度思想提出最小遺憾度法，該方法旨在使各部門的最大遺憾度最小，即計算各個分配方案中的最大遺憾度，進(jìn)而從中選出遺憾度最小的，遺憾度最小對應(yīng)的分配方案即為最佳方案。該方法解決了總席位數(shù)增加可能導(dǎo)致某部門席位數(shù)減少的問題。</p><p>　　

10、第三部分基于多次相同席位分配的情況下提出余額延續(xù)法，該方法運用Hamilton法分配席位，記錄每次席位分配后的余額。在下次席位分配時加上本次所記錄的余額，然后進(jìn)行分配。該方法追求在某一時間段內(nèi)各個部門的平均分配結(jié)果接近分配比例。</p><p>　　關(guān)鍵詞：席位分配 最小遺憾度法 余額延續(xù)法 公平分配</p><p>　　THE THEORETICAL STUDY OF SEAT AL

11、LOCATION</p><p><b>　　ABSTRACT</b></p><p>　　This paper mainly talks about the study of following questions：Hamilton, the classical Q value method, CQ value method, the improvement of

12、Q value method, the new Q value method, minimal extremum method, planning method, the average degree of fairness method, the relative mantissa method, fair accumulation method and seat allocation. The main tasks of this

13、paper are as follows.</p><p>　　The third chapter ,in the first part defines the standard of minimum regret about seat allocation methods, according to the results in a distribution of various allocation meth

14、ods, calculate what method the regret of all departments are the youngest, and determine what kind of allocation method is best for this assignment.Conclusion: a method of distribution is not suitable for every seat allo

15、cation.</p><p>　　The second part, according to minimum sorry thought least regret degree method, this method is aimed at minimum maximum regret degree between the various departments, namely calculating maxi

16、mum regret degree of each scheme, and then choose the smallest regret degree, regret degree minimum corresponding scheme is the best solution.The method solves the total seats increase may lead to a department in the num

17、ber of seats.</p><p>　　The third part is based on many times the same seats allocated under the condition of continued balance method is put forward, this method use the Hamilton method assigned seats, recor

18、d every time the balance of the distribution of seats.In the next seat allocation and recorded the balance, then allocated.The pursuit of this method in a certain period of time, the results of the average distribution o

19、f each department close to allocation proportion.</p><p>　　Key words:seat allocation, minimal regret method, The further balance method,Fair distribution</p><p><b>　　第一章 緒論</b></p

20、><p>　　1.1 經(jīng)典席位分配問題的研究背景與意義</p><p>　　經(jīng)典席位分配問題來源于美國眾議院按各州人口比例分配議員席位名額，該問題的研究在政治學(xué)、管理學(xué)和經(jīng)濟(jì)學(xué)領(lǐng)域均有重要應(yīng)用價值。比如很多大型企業(yè)均根據(jù)股份比例分配公司董事會席位，即可借鑒公平席位分配方面的研究成果。就席位分配問題而得來的公理化模型而言，其本身就是一個極具挑戰(zhàn)性的非線性數(shù)學(xué)問題，所以對它的研究有著重要的理論價值

21、。</p><p>　　美國憲法規(guī)定按照各州人口比例給出公平的眾議院席位分配方案，1850年到1900年期間，美國眾議院采用Vinton 方法來分配各州議員名額。然而，1881年當(dāng)議會總席位由299席變?yōu)?00席時，再按相同的方法調(diào)整各州議員的名額，結(jié)果卻使得Alabama 州的議員席位從8個減到7個，這就是著名的Alabama 悖論。后來在1890年議會席位增加時又出現(xiàn)類似情況。1921年，哈佛大學(xué)數(shù)學(xué)家E.V

22、.Huntington 建立了基于名額分配不公平度的數(shù)學(xué)模型，提出了等比例方法，并于1941年將它寫入法律，且沿用至今。自1974年以來，M.L.Balinski 和 H.P.Young 對席位公平問題進(jìn)行了一系列的研究。他們提出了衡量公平度的一系列公理化原則，在此基礎(chǔ)上有提出了配額法，并論證了配額法滿足席位單調(diào)性的公理化準(zhǔn)則。1977年，Balinski等分析了此前提出的一系列公理化公平原則的合理性，并比較了多個席位分配方法的優(yōu)缺點，

23、其中包括美國眾議院沿用至今的等比例法、Wenster 方法和配額法等。Balinski 等簡潔地總結(jié)出公平席位分配方法應(yīng)該滿足的5條公理化原則，如下：</p><p>　　一：（人口單調(diào)性）一個單位的人數(shù)增加不會導(dǎo)致該單位席位數(shù)減少。</p><p>　　二：（無偏性）在整個時間上平均，每個單位應(yīng)得到它自己應(yīng)分?jǐn)偟姆蓊~。</p><p>　　三：（席位單調(diào)性）總席位

24、的增加不會使得某單位的席位數(shù)減少。</p><p>　　四：（公平分?jǐn)傂裕┤魏螁挝坏南粩?shù)都不會偏離其比例的份額數(shù)。</p><p>　　五：（接近份額性）沒有一個單位到另一個單位的名額轉(zhuǎn)讓會使得這兩個單位都接近他們應(yīng)得的份額。</p><p>　　但是在1980年Balinski 和Young 證明了同時滿足上述5條原則的席位分配方案是不存在的。這也就說明不存在一

25、個絕對公平的席位分配方案，只能根據(jù)不同的情況，做到相對的最大公平。</p><p>　　第二章 公平席位分配方法及其性質(zhì)研究</p><p>　　2.1節(jié) 幾種經(jīng)典席位分配方法的分析總結(jié)</p><p>　　公平席位分配問題的研究其實就是社會中普遍的資源分配問題，研究的結(jié)果是試圖對有限的資源的分配做到盡可能的公平。比較近的一個例子就是：我校為了召開學(xué)生代表會議，各系

26、只能分配到有限的名額，那么問題來了，怎么去分配這些有限的名額，才算合理，或者說讓各個系的人都滿意呢？</p><p>　　下面就對這一問題建立一個具體的數(shù)學(xué)模型，來比較清晰的討論這個問題：設(shè)某校由 m 個院系組成，其中第i 個系的學(xué)生人數(shù)為 (i=1,2...,m) 且該校總?cè)藬?shù)為p ，則 。若代表會議共有n個席位，那么就是將n個席位分配到m個院系中去。假設(shè)每個院系分配到的席位數(shù)為(i=1,2...m),則應(yīng)滿足

27、 ++...+ = n ，非負(fù)整數(shù)向量N = （,...）就為這次席位分配的方案。令 = (i=1,2...,m) 如果 = 則表明這次席位分配時完全公平的。但是在現(xiàn)實世界中 均為整數(shù)的情況是少之又少。也就是在大多數(shù)情況下(i=1,2...,m) 中 都存在著非整數(shù)。</p><p>　　在這里就有必要把前面所說到的，美國數(shù)學(xué)家 M.L.Balinski 和 H.P.Young 提出的五條公理給數(shù)學(xué)模式化。

28、即:</p><p>　　公理1）(人口單調(diào)性)一個單位的人數(shù)增加不會導(dǎo)致該單位席位數(shù)減少，即，</p><p>　　n 一定，<’,< '(i≠j)且p'='+'+…+'時，對</p><p>　　? f∈M,有=f(p,n,)≤f(p',n,)= '</p><p>　　

29、公理2）(無偏性)在整個時間上平均，每個單位應(yīng)得到它自己應(yīng)分?jǐn)偟姆蓊~</p><p>　　公理3）(席位單調(diào)性)總席位的增加不會使得某單位的席位數(shù)減少，即，</p><p>　　? f∈M ',有=f(p,n,)≤f(p,n+1,)='</p><p>　　公理4）(公平分?jǐn)傂?任何單位的席位數(shù)都不會偏離其比例的份額數(shù)，即</p>&

30、lt;p>　　? p,n, f∈M ',[] ≤≤[]+1（i=1,2，…,m）</p><p>　　公理5）(接近份額性)沒有從一個單位到另一個單位的名額轉(zhuǎn)讓會使得這</p><p>　　兩個單位都接近于它們應(yīng)得的份額，即對任意1≤i≠j≤m,不等式</p><p>　　|f(p,n, )+1-|<| f(p,n,)-|和|f(p,n,)-1-

31、|< |f(p,n, )-|</p><p>　　2.1.1 Hamilton (漢密爾頓) 法</p><p>　　設(shè)某校由 m 個院系組成，其中第i 個系的學(xué)生人數(shù)為 (i=1,2...,m) 且該校總?cè)藬?shù)為p ，則 。學(xué)生代表會議共n個成員，則第i個院系按照比例應(yīng)分得代表席位數(shù)為 = ,且++…+ = n</p><p>　　Hamilton 法也就

32、是慣例法，即首先分配各個院系應(yīng)得的份額中的整數(shù)部分[](這里設(shè)[]為不大于的最大整數(shù)),然后取得小數(shù)部分即 = -[],最后根據(jù)從大到小的排列順序，將剩余的席位數(shù)逐個分配，也就是說小數(shù)部分大的院系將優(yōu)先獲得剩下席位，即如果剩余k個席位(k < m) 那么就取前k個院系。這些院系將獲得另外一個席位。</p><p>　　Hamilton 法應(yīng)該是最早的席位分配方法了，也是最容易理解的。如果按人數(shù)的比例來分配到

33、各院系的席位數(shù)恰好都是整數(shù)的話，那么就實現(xiàn)了完全公平的分配了，但是現(xiàn)實中絕大多數(shù)情況下是不可能出現(xiàn)這中特殊情況的。</p><p>　　Hamilton 法是最簡單的方法，但是它卻有自己的缺陷性。首先，要用這種分配方案的話，就要確保每個院系至少能夠分得一個席位，即是否具備分配資格。分配資格其實在生活中也不少見。如果席位數(shù)少于院系數(shù)，那么它當(dāng)然也就不適合了。還有就是這種分配方案有可能會造成：總的席位數(shù)增加了，但是某

34、個院系所分得的席位數(shù)卻減少了，這其實是極不合理的。所以有時候這種方案并不見得公平合理。</p><p>　　2.1.2 經(jīng)典Q值法</p><p>　　經(jīng)典Q值法是由兩方（A,B）公平席位分配的情況推廣到一般m方席位分配的。首先討論只有A、B兩方公平席位分配的情況。設(shè)兩方人數(shù)分別為和，兩方占有的席位分別為和，則雙方每個席位所代表的人數(shù)分別為/ 和 /。這時有/ = / 時A、B兩方的席位分

35、配才是公平的，但是因為人數(shù)以及席位數(shù)都是正整數(shù)，所以通常情況下都不能公平分配席位，并且一個席位所代表的人數(shù)多的，即對/(i=1,2)數(shù)值較大的一方較為不公平。為了衡量這一不公平度，引入了相對不公平度這個概念 。</p><p>　　若/ > /,則定義對A的相對不公平度為：</p><p>　　相反，若/ < /,則定義對B的相對不公平度為</p><p&

36、gt;　　現(xiàn)在根據(jù)相對不公平度來分配席位，假設(shè)現(xiàn)在A、B兩方分別已經(jīng)分得和個席位，那么下一個席位應(yīng)該分配給哪一方就要依據(jù)相對不公平度了。不失一般性可設(shè) /> /。</p><p>　　現(xiàn)在要達(dá)到公平分配，就要讓雙方的相對不公平度降到最低，即如果哪一方的相對不公平度大就分給哪一方。所以如果：</p><p>　　則這一席位應(yīng)該分配給A，反之則應(yīng)分配給B。而上式又等價于</p>

37、;<p>　　如果上式成立，則應(yīng)分配給A，否則分配給B。</p><p>　　由此式推廣到一般情況下時，就得到了Q值：</p><p><b>　　定義Q值為</b></p><p>　　，i = 1,2,...m</p><p>　　而應(yīng)用到一般的分配情況時，具體分配步驟如下：</p>&l

38、t;p>　　首先要給每一方分配一個席位（如果不分配一個席位則會導(dǎo)致上式分母為零），然后計算各方的Q值，Q值最大的分得下一個席位，之后再計算各方Q值，把下一個席位分配給Q值最大的一方，如此反復(fù)，直到席位分配完畢。</p><p>　　如上Q值法能在不公平的情況下，盡可能的把相對不公平度降到最低，也就是最大限度保持公平，但是它只考慮了各方的相對不公平度，而沒有考慮各方相對于整體的不公平度。而且比較大的缺陷就是沒

39、有解決首先要分配給各方一個席位的前提，如果席位數(shù)小于單位數(shù)的話，該方法同Hamilton 法一樣不能使用。最后，使用這種分配方案的前提是各方最少要分得一個席位，但是如果一方的人數(shù)非常少，或者說沒有分配資格的話，這對于其他方不也是另一種不公平么。故，雖然Q值法將相對不公平度降到了最低，但是其還是具有一定的局限性的。</p><p>　　2.1.3 CQ值法</p><p>　　CQ值法是岳林

40、改進(jìn)了Q值法，并引入了能夠滿足席位分配的理想化準(zhǔn)則1和準(zhǔn)則2的方法。</p><p>　　定義 1: 已知待分配的總席位為 N， m 方人數(shù)分別為,,…， 記總?cè)藬?shù)為P=++…+。理想情況下m 方分配的席位分別為,...。記= N /p (i=1,2,…,m).若 均為整數(shù)，顯然應(yīng)=,若不全為整數(shù)， 應(yīng)滿足如下準(zhǔn)則：</p><p>　　準(zhǔn)則1 []≤[]+ (i=1,2,…,m).,即

41、必取[]，[]+之一，其中 []=floor(),即向小于等于方向取整，[]+=ceil(),即向大于等于 方向取整.</p><p>　　準(zhǔn)則2 當(dāng)總席位增加時， 不應(yīng)減少</p><p>　　不難驗證Hamilton法滿足準(zhǔn)則1，但是不滿足準(zhǔn)則2，而Q值法滿足準(zhǔn)則2，但不滿足準(zhǔn)則1，而CQ值法綜合了這兩個分配方案的優(yōu)點，既滿足準(zhǔn)則1又滿足準(zhǔn)則2。</p><p

42、>　　接2.1.2中的例子，重新定義A的相對不公平度為：</p><p>　　同樣定義B的相對不公平度為：</p><p><b>　　易知 等價于</b></p><p>　　于是就定義CQ值 為 </p><p><b>　　，i = 1,2 </b></p><p&g

43、t;　　則下一個席位應(yīng)該分配給CQ值較大的一方，這樣推廣到m方時：</p><p>　　已知m 方的人數(shù)分別為（i=1,2，…，m），待分配的總席位數(shù)為 N，且N 為大于m 的正整數(shù)，首先計算= N /p (i=1,2,…,m)，然后第i方按比例分配[]個席位，設(shè)余下的席位數(shù)為k,k 為小正整數(shù)。最后剩余的k個席位按如下方法分配：</p><p>　　1、 計算 m 方的CQ值，將CQ值按

44、從大到小排序。</p><p>　　2、將剩余的k個席位依次分配給CQ值前k大的各方</p><p>　　顯然CQ值法滿足準(zhǔn)則1和準(zhǔn)則2。</p><p>　　CQ值法 較 Hamilton法 和 Q值法 更顯成熟和強健性，它滿足了五大公理中的其中兩條。而且分配方法較簡單，不像Q值法，反復(fù)計算Q值，計算一輪Q值只能分配出一個席位，與Q值法比較簡單，且更公平合理。而且

45、它沒有規(guī)定每方必須要至少分得一個席位，這是較前兩種方法更大的突破，降低了分配方案使用的門檻。</p><p>　　2.1.4 新Q值法</p><p>　　新Q值法通CQ值法大致相同，就是把相對于各方的不公平度變?yōu)榱讼鄬τ谡w的絕對不公平度。</p><p>　　設(shè)m 個單位共有p 人參與總席位為n 的席位分配，第i 個單位人數(shù)為,分配到的席位為,i=1,2，…，m

46、。稱</p><p><b>　　?</b></p><p>　　為第i 個單位的Q 值。</p><p>　　分配方法同CQ值法相似，先分配給各方應(yīng)得的按比例取整后的席位，即先分配給第i方 = [n /p]個席位，然后計算各方Q值，將Q值按從大到小的順序排序，將剩余的席位分配給Q值較大的幾方。</p><p>　

47、　2.1.5 改進(jìn)的Q值法</p><p>　　改進(jìn)的Q值法是針對于Q值法的不足給予相應(yīng)的改善，經(jīng)典Q 值法中定義的Q值為 該式所表示的相對不公平值只是反映了第i 方本身增加或不增加一席的情況，而并沒有把第i 方放到所有整體中去考慮，也沒有反映相對于本方每席位代表和人數(shù)比例關(guān)系與另外一方的每席位代表和人數(shù)比例關(guān)系是否一致或接近，由此提出了改進(jìn)的 Q 值法。</p><p>　　設(shè)m 方共

48、有p 方人參與總席位為N 的席位分配，第i 方的人數(shù)為pi（i=1,2，…，m），第i 方所分配的席位為(i=1,2,…,m)，則定義的改進(jìn)的Q值為：</p><p>　　,i=1,2,…，m</p><p>　　其具體的分配方法如下</p><p>　?。?） 初始化：每一方分配席位為零，即=0(i=1,2,…，m);</p><p>　　

49、（2） 終止判斷：若，即席位已分配完，結(jié)束；否則轉(zhuǎn)（3）；</p><p>　?。?） 計算 的值，i=1,2，…，m;</p><p>　?。?） 比較Qi(i=1,2…，m)的大小，對Q 最大的一方增加一個席位。并轉(zhuǎn)（2）</p><p>　　改進(jìn)的Q值法，解決了Q值法首先給每方分配一個席位的不合理規(guī)定。</p><p>　　2.1.6

50、最小極差法</p><p>　　最小極差法提出了一個更公平合理的衡量“公平度”的新標(biāo)準(zhǔn)，即“最小極差”以及相應(yīng)的數(shù)學(xué)規(guī)劃模型。與此同時又提出了一個“非完全分配”的新概念及其數(shù)學(xué)模型</p><p>　　設(shè)某校共有m 個系，第i 系學(xué)生數(shù)為( i = 1,2,...,m)，校學(xué)生會共設(shè)N 個席位，現(xiàn)在要把這些席位公平地分配給各系。顯然，m，( i =1,2,L,m)應(yīng)為正整數(shù)，全校學(xué)生數(shù)記為

51、。假設(shè)每個系至少應(yīng)分得一個席位（否則也就是不具備分配資格，則可以把其剔除），至多分得( i =1,2,...,m)個席位，n > N ≥ m 。全校而言，每個席位代表的學(xué)生數(shù)記為a = n/N 。第i 系按學(xué)生數(shù)比例應(yīng)分得的席位為=N /n ，最后實際分得的席位數(shù)為(1 ≤ ≤ ，整數(shù)）每個席位代表的學(xué)生數(shù)為=/(i=1,2,...,m)。另記 y = min , z = max。</p><p>　　依

52、據(jù)以上的標(biāo)準(zhǔn)，以及上述符號即可建立數(shù)學(xué)模型</p><p>　　min f = z - y </p><p><b>　?。?）</b></p><p>　　上述模型中，N,m, 均為已知數(shù)， ，y,z 為變量，( i =1,2,...,m)為正整數(shù)，就是各系最后得到的席位數(shù)。模型還具備以下性質(zhì)：</p><p>　　

53、性質(zhì)1：z ≥ a ≥ y ，說明 的兩極總在a的兩旁。</p><p>　　性質(zhì)2：若z > y,則z > a > y ，說明當(dāng) 的兩極不相等時，任一極 都不等于 a 。</p><p>　　性質(zhì)3：模型必有最優(yōu)解</p><p>　　性質(zhì)4：模型的最優(yōu)解為零的充要條件是( i =1,2,...,m)均為正整數(shù)</p>&l

54、t;p>　　關(guān)于上述性質(zhì)的證明：</p><p>　　性質(zhì)1：因，（i = 1,2,...,m）,故，（i = 1,2,...,m），兩邊對i求和就得到,即可得</p><p>　　性質(zhì)2：設(shè) z = max(/) = /,y=min(/) = /.由性質(zhì)1知z ≥ a ≥ y ，現(xiàn)證當(dāng)z>y時等號不成立。</p><p>　　用反證法。設(shè)z=a，則/=

55、a,/<a。其余/a，即:</p><p>　　=a,<a，a從而 n= < a = aN，這與a = n/N矛盾，這說明z > a。同理 a > y。</p><p>　　性質(zhì)3：由于模型（1）中，只能取有限個值，故只要證明模型（1）有可行解，則必有最優(yōu)解。 若全部≥1 (i = 1,2,...,m) ,則令</p><p>　　則=

56、+r = N,且1+1，而+1是大于的最小整數(shù)，又 = /a < ,故，即(i = 1,2,...,m)是模型（1）的可行解。</p><p>　　下面假設(shè)z = max(/)，y=min(/)</p><p>　　若有k個 = 0，則顯然應(yīng)有k < m，這是因為若k=m，即全部<1 (i = 1,2,...,m),則< m,但 = N，這與 N≥m不符。現(xiàn)在不妨設(shè)

57、前k個為0，即 = 0（1ik）, ≥ 1（k+1im）。</p><p><b>　　若k < r,則令</b></p><p><b>　　若k=r,則令</b></p><p>　　則都滿足1，(i = 1,2,...,m)是模型（1）的可行解。</p><p>　　若m >k &

58、gt;r,則要分兩種情況：</p><p>　　情形（1）當(dāng) >k - r時，則令</p><p>　　則1，(i = 1,2,...,m)，且=+r = N,即(i = 1,2,...,m)是模型（1）的可行解。</p><p>　　情形（2）當(dāng) k - r時，則找t(k+2tm)使 < k-r ,記w = k - r -,則w > 0,令&l

59、t;/p><p>　　因-1+ ≥ k - r,故-1≥ w,可得 - w ≥ 1，從而可知，1，(i = 1,2,...,m)，且 =t-1+-k+r++= r+= N。即(i = 1,2,...,m)是模型（1）的可行解。</p><p>　　性質(zhì)4：若模型（1）的最優(yōu)值為零，則由性質(zhì)1知z = a =y，其最優(yōu)解(i = 1,2,...,m)滿足/ = a(i = 1,2,...,m),

60、從而 =/a = (i = 1,2,...,m),故均為正整數(shù)。反之，若都是正整數(shù)，則令=，故=/=/=a(i = 1,2,...,m),從而z = a =y，即=(i= 1,2...m),是模型（1）的最優(yōu)解，且最優(yōu)值為0。</p><p>　　最小極差法還定義了“非完全分配法”</p><p>　　前面的幾種分配方法都是“要把N 各席位全部分配出去，如何分配更公平”這樣的問題。我們不妨

61、把這些分配方法稱為“完全分配法”。但有些情況，若采用“完全分配法”，則無論怎樣分，都總顯得不公平。但是如果舍棄其中的某些席位再來分配的話就能做到絕對公平，稱為了達(dá)到最公平而舍棄一些席位的分配方法稱為“非完全分配法”</p><p>　　而非完全分配法的數(shù)學(xué)模型只需要對模型（1）做稍加改動即可得到：</p><p>　　min f = z - y </p><p>

62、<b>　?。?）</b></p><p>　　則模型（2）必有最優(yōu)解，而且在公平度方面必有很大的改善</p><p>　　最小極差法能較完善地解決席位公平分配問題。當(dāng)愿意舍棄一些席位而追求“最公平”時，可使用模型(2)，當(dāng)不愿意浪費席位時，可使用模型(1)。當(dāng)然，后者的“公平度”就相對來說要差一些了</p><p>　　2.1.7 0-1規(guī)劃

63、模型</p><p>　　設(shè)共有m 方參加席位分配,第 i 方的人數(shù)為( i = 1 ,2 ,..., m) ,記 。又設(shè)共有N 個名額可供分配,第 i 方所分配的席位為ni ( i = 1 ,2 ,..., m) ,顯然有 ,且 為整數(shù)。則第 i 方每個席位代表人數(shù)為 / ,而整個分配方案平均每個席位代表人數(shù)為p/N,記第 i 方應(yīng)分得的席位為 =N /p 。 由此建立了如下整數(shù)規(guī)劃模型</p>

64、;<p>　　S.t ,均為整數(shù)，i = 1,2,...m</p><p>　　依照名額分配問題的公平分?jǐn)傇瓌t可將上述模型裝化為以下模型：</p><p>　　S.t. ， = 0 或 1 ，i = 1,2,...,m</p><p>　　其中[]為不大于的最大整數(shù)。</p><p>　　利用上述模型即可求出最優(yōu)解。0-1規(guī)

65、劃模型將整體的不公平度和降到了最低，對于整體來說盡可能地做到了公平，但是卻沒有考慮每個個體的相對不公平度。盡管沒有做到這一點，但整體內(nèi)的絕大部分都相對公平，在另一方面也做到了盡可能保持公平。</p><p>　　2.1.8 平均公平度法</p><p>　　先來討論A , B 兩方公平分配席位時的情況, 設(shè)總?cè)藬?shù)為p,兩方人數(shù)分別為和, 總席位數(shù)為 N ,兩方分得的席位分別為 和 , 則A

66、、B兩方每個席位所代表的人數(shù)分別為 = /, = /. 顯然當(dāng)= 時, 席位的分配才是最公平的.但是因為人數(shù)和席位都是整數(shù), 所以通常 , 并且/ 值較大的一方吃虧, 或者說對這一方不公平.</p><p>　　而最公平的分配為每個席位代表的人數(shù)為q=p/N .則A 相對于總體的公平程度為= /p, B 相對于總體的公平程度為 =/p ,當(dāng) = 時, = = 1.定義第i方相對于總體的公平程度為,

67、 當(dāng)接近于1 時,則第i方的分配情況比較公平。</p><p>　　但是在絕大多數(shù)情況下雙方不可能同時是1, 所以只能尋找一種折中的方法, 讓兩者相對于1 的距離最小, 就是使雙方的分配方法達(dá)到使雙方都能滿意. 這時我們定義平均公平度Q：</p><p>　　易知，當(dāng)Q值小的時候說明對各方分配都相對公平。 </p><p>　　分配方法，先分配給各方按比例分配應(yīng)分

68、得的席位數(shù)的整數(shù)部分個席位，然后分配下一個席位，計算此席位分配到不同方時的Q值，使Q值最小的就是最佳分配方案。如此反復(fù)逐個分配余下的席位，直到席位分配完畢為止。 </p><p>　　2.1.9 相對尾數(shù)法</p><p>　　相對尾數(shù)法提出了一個能滿足五條公理中的兩條的分配方案，即滿足</p><p>　　一、每個部門的分配名額都是取按比例的向上或向下取整<

69、/p><p>　　二、總名額的增加不會使得某部門所得得名額減少</p><p>　　設(shè)有 m 個部門, 每個部門的人數(shù)分別為, (i = 1, 2,..., m), 總?cè)藬?shù)p = ++…+, 待分配的席位為 N , 理想化的席位分配結(jié)果為 ( i = 1, 2, ... , m ) , 滿足 記 = N /p ( i = 1, 2,..., m ). 顯然, 若 ( i = 1, 2,

70、..., k ) 全為整數(shù)時, 應(yīng)有 = ( i = 1, 2, ...,m) , 當(dāng) ( i = 1, 2, ... , k ) 不全為整數(shù)時, 需要確定同時滿足下列公理的公平分配方案:</p><p>　　公理1.[] [] + 1,i = 1,2,..., m,即取[]或[] + 1</p><p>　　公理2.(N,,,…,)(N+1,,,…,),i = 1,2,...,

71、m , 即總席位增加時,各個部門的席位數(shù)不會減少.</p><p>　　而解決這一問題的分配方案是：</p><p>　　令 = - [], 稱其為對第 i 個部門的絕對不公平度. 令 = /[], 稱其為對第i 個部門的相對不公平度, 或稱為相對尾數(shù).為使分配達(dá)到最大程度的公平, 需所有的 越小越好, 所以相對公平的分配方法應(yīng)該讓 max 達(dá)到最小,即所有的 達(dá)到最小。<

72、;/p><p>　　首先考慮只有兩個部門的情況下的分配方案：</p><p>　　記（）= - [] ,即 （）為 的小數(shù)部分。</p><p>　　若 = , 且 > ,則取 = []+1, = []</p><p>　　若 > , 則取 = []+1, = []</p><p>　　若 &l

73、t; , 則取 = [], = []+1</p><p>　　易知，相對尾數(shù)的分配方案滿足公理1，下面證明亦滿足公理2</p><p>　　若總席位N 增加為N+1時，對應(yīng)的 記為 ，記為。</p><p>　　1)若 + 1, 則</p><p>　　= + = + 1 = </p><p><

74、b>　　= </b></p><p>　　若 + < 1, 則</p><p>　　當(dāng)r1 = r2，且 > 時，p1 = p2，而</p><p>　　p1 = p2 > p2 , 即 P1>P2 ,</p><p>　　于是： + < + < 1</p>

75、<p>　　故有： = + = </p><p><b>　　同理： = </b></p><p><b>　　由此得到：</b></p><p>　　= = - 1 = r1 + = (1+)r1 +</p><p>　　= (1+)r2 + = = </p>

76、<p><b>　　于是：</b></p><p>　　= + 1 = +1 = </p><p><b>　　= = = </b></p><p>　　當(dāng) > 時，有p1 > p2 ,從而有：</p><p>　　P1 p1 p2 =p2+p2= p2<

77、;/p><p><b>　　即有：> 此時</b></p><p>　　= + 1 = +1 = </p><p><b>　　= = = </b></p><p>　　同理 當(dāng) < 時，與 > 情況相對稱。</p><p>　　對于三個部門時的

78、分配方案為：</p><p><b>　　設(shè) ,,全不為零</b></p><p>　　1) 當(dāng) = = 時; 按比例取整后, 多余的席位分配給小數(shù)部分較大的部門</p><p>　　2) 當(dāng) > = 時; 按比例取整后, 若多余一個席位, 則分配給第一個部門, 若多余兩個席位, 則分配給第一個部門及第二、三部門中小數(shù)部分較大的部門

79、.</p><p>　　3) 當(dāng) = > 時; 按比例取整后, 若多余一個席位, 則分配給第一、二部門中小數(shù)部分較大的部門, 若多余兩個席位, 則分配給第一部門和第二部門.</p><p>　　4) 當(dāng) > > 時; 按比例取整后, 若多余一個席位, 則分配給第一部門; 若多余兩個席位, 則分配給第一部門和第二部門.</p><p><

80、;b>　　推廣到一般情況時：</b></p><p>　　對于m個部門，設(shè), , ..., 不全為零, 且 ..., 則當(dāng)≠ + 1 時, 將剩余的t = N - 個席位分配給第一至第t 個部門, 當(dāng) = + 1 時, t = N - 個席位分配給第一至第t- 1 個部門及 ( i = t 或t + 1) 較大的一個部門.</p><p>　　2.1.10 公平累

81、加席位法</p><p>　　設(shè)有m方參與席位分配，記總席位數(shù)為N，第i方的人數(shù)為，且設(shè)>0，（i = 1,2,...,m）,則各方人數(shù)相加的總和P=，第i方分得的席位數(shù)記為(N,,,...,),為簡單起見，記為(N)。顯然有關(guān)系式 N = ，依照人口比例的公平分配原則，分配給第i方的席位數(shù)為 =N/P，顯然如果均恰為整數(shù)，則有(N) = ，由于席位的不可分割性，需研究（i = 1,2,...,m）不

82、為整數(shù)時的情形。</p><p>　　設(shè)d為實數(shù)，[d]表示為d向下取整，即[d]為不超過d的最大整數(shù)，則有關(guān)系式0d-[d]<1成立，在此基礎(chǔ)上給出的公平分配方法應(yīng)滿足的3條公理的數(shù)學(xué)描述：</p><p>　　公理 1 [](N)[]+1（i = 1,2,...,m），即(N)必取[]，[]+1二者之一。</p><p>　　公理2 (N,,,...,)

83、 (N+1,,,...,)（i = 1,2,...,m），即各方人數(shù)不變的條件下，總席位增加時任何一方的席位都不減少。</p><p>　　公理 3 如果<,則必有(N)<(N),即若第j方人數(shù)多于第i方人數(shù)，則j方分得的席位不得少于第i方分得的席位。</p><p>　　顯然公理1對應(yīng)于Balinski提出的原則四，即個方應(yīng)得到他們的公平分?jǐn)偡蓊~。公理2則對應(yīng)了席位單調(diào)性原則

84、。公理3則部分對應(yīng)了Balinski的人口單調(diào)性原則，同事也是公理1的必要補充。下面將構(gòu)建滿足以上3條公理的席位分配方法，成為公平累加方法。</p><p>　　公平累加方法不同于一次性地給出各方席位數(shù)的方法，該方法是根據(jù)公平原則，按判斷給予的步驟逐步地分配每一個席位，直至所有的席位全部分配完畢，具體的分配方案如下：</p><p>　　第1步 設(shè)定各方分得席位數(shù)的初始值，當(dāng)總席為N=0時

85、，顯然第i方應(yīng)得席位數(shù)為=0，（i = 1,2,...,m）</p><p>　　第2步 考慮當(dāng)總席位數(shù)從g（g0且g為非負(fù)整數(shù)）變?yōu)間+1時（即總席位數(shù)加1）的情況。不妨設(shè)總席位數(shù)為g時的公平席位分配方案為（,,...,）,且有關(guān)系式 = g 和為非負(fù)整數(shù)。</p><p>　　必存在整數(shù)k且0km,使得</p><p>　　若上式中的k不唯一，為了確定起見，規(guī)定

86、取最小的k值，且令=+1，其余的當(dāng)ik時，令=（i = 1,2,...,m）。此外還有=+1 = g+1成立，且,,...,</p><p>　　,均為非負(fù)整數(shù)。由此得到總席位為g+1時的席位分配方案為（,,...,）。由于總席位增加會帶來新的不公平，所以累加法實質(zhì)上是將每個席位都分配給當(dāng)前最吃虧的一方。</p><p>　　第3步 如果g < N ,則再執(zhí)行第二步，直至g = N,

87、得到公平累加法的分配方案（,,...,）.</p><p>　　公平累加法的公平度論證</p><p>　　定理3.1如果公平累加法分配席位方案的第二步中對每一個正整數(shù)g（1<g<N）,集合{i|1,i = 1,2,...,m}的元素個數(shù)不超過1，則該方案得到的分配結(jié)果（,,...,）滿足公理1和公理2。</p><p>　　首先由公平累加法顯然有關(guān)系式

88、：</p><p>　　...,i = 1,2,...,m</p><p>　　所以得到的分配方案滿足公理2.</p><p>　　下面證明由公平累加法得到的分配方案滿足公理1，即：</p><p>　　+1,i = 1,2,...,m</p><p>　　易知：設(shè)d為非負(fù)實數(shù)，而D為整數(shù)，則有如下等價關(guān)系：</

89、p><p>　　[d] D [d]+1-1 d-D < 1</p><p>　　而應(yīng)用到此處時，公平累加算法得到的分配方案（,,...,</p><p><b>　?。M足的不等式</b></p><p><b>　　+1</b></p><p><b>　

90、　等價于</b></p><p>　　-1- < 1,i = 1,2,...,m,</p><p>　　下面證明公平累加算法得到的分配方案滿足公理1.</p><p>　　引理1 如果公平累加法席位分配方案中的第2步對每一個整數(shù)g(1gN),集合{i|1,i = 1,2,...,m}的元素個數(shù)不超過1，則該方案得到的分配結(jié)果（,,...,）滿足的不

91、等式組</p><p>　　-1- < 1,i = 1,2,...,m, (1)</p><p><b>　　運用數(shù)學(xué)歸納法證明</b></p><p>　　1）當(dāng)g = 0時，由公平累加法的初始設(shè)定值知=0，（i = 1,2,...,m）顯然有如下關(guān)系</p><p>　　-1- < 1

92、,i = 1,2,...,m</p><p>　　假設(shè)總席位為g(g>0)時有</p><p>　　-1- < 1,i = 1,2,...,m(2)</p><p>　　下面證總席位變?yōu)間+1時有</p><p>　　-1- < 1,i = 1,2,...,m(3)</p><p>　　

93、不妨設(shè)存在k(1km)使得(4)</p><p>　　則由公平累加算法知=+1,其余的當(dāng)ik時，有=</p><p>　　（i = 1,2,...,m）。根據(jù)歸納法假設(shè)有- < 1，所以有：</p><p>　　= + - 1 < 1+ - 1=<1 (5)</p><p>　　再根據(jù)（4）式，不難得到</p&

94、gt;<p>　　M( ) = g+1-g=1</p><p><b>　　所以 ，所以有</b></p><p>　　= - 1 -1 > -1(6)</p><p>　　綜合（5）和（6）式得：</p><p>　　-1- < 1（7）</p>&

95、lt;p>　　再由[d] D [d]+1-1 d-D < 1 得：</p><p>　　+1（8）</p><p>　　下面分兩種情形證明當(dāng)ik時有關(guān)系式 -1- < 1</p><p>　　若 < 1,再根據(jù)（4）式，則當(dāng)ik時都有</p><p>　　= < 1（9）</

96、p><p>　　再根據(jù)歸納假設(shè)（2）式得</p><p>　　= =-1+ > -1（10）</p><p>　　結(jié)合（9）和（10），再注意有（7）式成立，總之，在此情況下有（3）式成立。</p><p>　　若 > 1則1- > 0所以>,既得</p><p>　　[],另有（2）式得知

97、<1,易得[]，最終可得</p><p><b>　　[]=。</b></p><p>　　因為 = +1=[]+1，再由1得</p><p><b>　　+1 = </b></p><p>　　結(jié)合（8）式與不等式 < +1得=</p><p>　　且有- =

98、 - = 1（11）</p><p>　　再根據(jù)定理條件如果公平累加法席位分配方案中的第2步對每一個整數(shù)</p><p>　　g(1gN),集合{i|1,i = 1,2,...,m}的元素個數(shù)不超過1，</p><p>　　以及（4）式，則當(dāng)ik時都有</p><p>　　= < 1(12)</p>

99、<p>　　再根據(jù)歸納假設(shè)（2）得</p><p><b>　　= = -1</b></p><p>　　結(jié)合（12）和（13）式則可得（3）式成立。</p><p>　　即： -1- < 1,i = 1,2,...,m</p><p>　　定理2 如果公平累加法席位分配方案中的第2步對每一個整數(shù)g(

100、1gN),集合{i|1,i = 1,2,...,m}的元素個數(shù)不超過1，若存在i使得為整數(shù)，則由公平累加法得到第i方席位數(shù)為=。</p><p>　　定理3 如果公平累加法席位分配方案中的第2步對每一個整數(shù)g(1gN),集合{i|1,i = 1,2,...,m}的元素個數(shù)不超過1，若<且1i,jm,則。</p><p>　　2.2節(jié) 幾種席位分配方法的實例比較</p>

101、<p>　　2.2.1 實例論證</p><p>　　例1 設(shè)某公司共有200人，該部門由A、B、C三個部門組成，其中A部門有103人，B部門有63人，C部門有34人。如果該部門要召開代表會議，代表會議成員有20人，那么怎么從三個部門中選出這20位代表來參加會議呢？并且還要對每個部門要公平。而如果會議代表成員增加到21位時，又該如何分配呢？</p><p>　　表1 代表會議由2

102、0個成員時的分配結(jié)果</p><p>　　由表1可知在只有20個席位時，Hamilton法、新Q值法和相對尾數(shù)法的分配結(jié)果相同，而其他的方法分配結(jié)果相同。從20個席位分配可以看出新Q 值法、0-1規(guī)劃法和相對尾數(shù)法確實有失偏頗.而平均公平度法和 Q值法結(jié)果相同, 雖說平均公平度法和0-1規(guī)劃法所定義的Q 值大體相同, 但是由于分配的方法不同, 導(dǎo)致了不同的結(jié)果. </p><p>　　表2

103、 代表會議由21個成員時的分配結(jié)果</p><p>　　對比表1和表2的數(shù)據(jù)，當(dāng)總席位數(shù)增加1時，發(fā)現(xiàn)Hamilton法的分配結(jié)果使C部門的名額反而減少1。也就是違反了公理三（總席位的增加不會使得某單位的席位數(shù)減少）。而此時Hamilton法、新Q值法和相對尾數(shù)法的分配結(jié)果又各不相同，可以看出三者之間的分配方案還是有差別的。對于其他的分配方法也不盡相同。</p><p>　　下面我們分別來

104、比較不同的分配方法。</p><p>　　利用表1和表2數(shù)據(jù)，另外再添加兩個席位，組成下表：</p><p>　　表3 Q值法與CQ值法比較</p><p>　　由表3數(shù)據(jù)可知，當(dāng)總席位數(shù)為20，23時，Q 值法和 CQ 值法分配結(jié)果相同;當(dāng)總席位數(shù)為21時，由分配比例中的小數(shù)部分可以得知CQ值法更為公平一點。而在總席位數(shù)為22時，可以得知Q值法更為公平一點。從中可

105、以得知，雖然有時候Q值法和CQ值法能得到相同的分配結(jié)果，但是兩者的分配結(jié)果不總是相同，而且Q值法和CQ值法在公平程度上各有優(yōu)劣，所以不能確定這兩個方法哪個更為公平。但是，CQ值法同時滿足了公理1和公理2，而Q值法只是滿足了公理2.</p><p>　　例2 還取例1中的模型，有A、B、C三個部門，總席位數(shù)N=11；總?cè)藬?shù)P=1000；其中A部門有235人，B部門有333人，C部門有432人，那么分別用Q值法和改進(jìn)

106、的Q值法來分配的結(jié)果是什么呢？如下表：</p><p>　　表4 Q值法與改進(jìn)的Q值法比較</p><p>　　從表4中可以看出，Q 值法每席位代表的人數(shù)最大值與最小值( 即A部門與B部門) 相差34.25, 改進(jìn)Q 值法每席位代表的人數(shù)最大值與最小值( 即C部門與B部門) 相差29.67, 這表明改進(jìn)的Q 值法更公平。</p><p>　　另一方面, 兩種方法與整

107、個分配方案平均每席位代表人數(shù)的偏差平方和分別為</p><p><b>　　?</b></p><p>　　從以上兩方面可以看出, 改進(jìn)Q 值法的確比Q 值法更公平、更合理。</p><p>　　例3 假設(shè)某公司有A、B、C、D、E五個部門，公司總?cè)藬?shù)為P=2500人，其中A部門有1105人，B部門有648人，C部門有362人，D部門有248人

108、，E部門有137人，可供分配的席位有N=25人，則對總體來說，每個席位代表的人數(shù)a=100人，則分別用Q值法，新Q值法,0-1規(guī)劃法和最小極差法來分配這25個名額，分配結(jié)果如下表：</p><p>　　表5 最小極差法與Q值法、新Q值法和0-1規(guī)劃法的比較</p><p>　　其中代表第i個部門的人數(shù)，代表按比例分配的比例，代表分得的席位數(shù)，每個席位代表的人數(shù)。</p>&l

109、t;p>　　由表5數(shù)據(jù)對比可見，除最小極差法外，其他三種方法分配結(jié)果的極差都比較大，也就是說公平度較差。但是從表中又可以看出，本來A部門按比例分配能分到11.05個名額，也就是說最少能分到11個名額的，但是用最小極差法來分配只能分配到10個名額，雖然達(dá)到了極差最小的目的，但是依然會引起A部門的極大不滿?？梢娫谧非笞钚O差的時候本身就放棄了一些原則。</p><p>　　例4 設(shè)某校5個系共872名學(xué)生,其中

110、A系375名,B系147名,C系56名,D系43名,E系251名.現(xiàn)需選出74個代表名額。下面分別用平均公平度法、Q值法、新Q值法、0-1規(guī)劃法和Hamilton法來進(jìn)行分配，其分配結(jié)果如下表：</p><p>　　表6 平均公平度法與Q值法、新Q值法、Hamilton法和0-1規(guī)劃法的比較</p><p>　　由表中數(shù)據(jù)可得，平均公平度法的分配結(jié)果與Q值法、0-1規(guī)劃法和Hamilton

111、法的分配結(jié)果相同，而新Q值法確實有失偏頗。而且平均公平度法可以使得個體相對總體的公平程度最接近于1, 即每個個體的滿意度都較高, 同時使得整體的不滿意度, 即平均公平程度最小. 和Hamilton法比較, 解決了由于席位增加而導(dǎo)致有一個甚至幾個個體分配的席位減少的情況, 從而使得這種分配方法能讓大眾接受和滿意. 與Q 值法, 新Q 值法相比, 這種利用方差的算法定義的公平原則更為合理,和0-1 規(guī)劃法相比, 將按整數(shù)部分分配后所剩下的席

112、位一個一個的分配, 保證每一個席位分配都是公平的, 而且使整體的不滿意度降到最小. 由此可見平均公平度法在Q值法、新Q值法、Hamilton法和0-1規(guī)劃法的基礎(chǔ)上得以改進(jìn), 使席位分配結(jié)果更加公平。</p><p>　　最小遺憾度與余額延續(xù)法</p><p>　　3.1幾個分配方法的最小遺憾度判斷標(biāo)準(zhǔn)</p><p>　　3.1.1 最小遺憾度標(biāo)準(zhǔn)的思想</

113、p><p>　　所有的席位分配方法都是定義自己的一個標(biāo)準(zhǔn)，然后根據(jù)這個標(biāo)準(zhǔn)來進(jìn)行席位分配，但是很少有席位分配方法本身優(yōu)劣性的判斷標(biāo)準(zhǔn)。而本文就是以最小遺憾度為一個標(biāo)準(zhǔn)，對幾個席位分配方法進(jìn)行檢驗，評判出席位分配方法的優(yōu)劣性。</p><p>　　這里先給出遺憾度的定義，遺憾度就是所有的席位分配完畢后，而i部門可能只需要再多出來x個人就可以再分得一個席位，這時該部門就會很遺憾，而x越小遺憾度越大

114、。這里只討論最接近再分得一個席位的部門，即再增加x個人在該席位分配方法所定義的標(biāo)準(zhǔn)下能超過最后一個分得席位的部門。</p><p>　　設(shè)有m方參與席位分配，記總席位數(shù)為N，第i方的人數(shù)為，且設(shè)>0，（i = 1,2,...,m）,則各方人數(shù)相加的總和P=，第i方分得的席位數(shù)記為（i = 1,2,...,m）。顯然有關(guān)系式 N = ，依照人口比例的公平分配原則，分配給第i方的席位數(shù)為 =N/P。不妨設(shè)最后