席位分配問題研究-論文答辯

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

2、究有著重要的理論價值。,席位分配的五條公理,公理1 (人口單調(diào)性)一個單位的人數(shù)增加不會導(dǎo)致該單位 席位數(shù)減少公理2 (無偏性)在整個時間上平均，每個單位應(yīng)得到它自 己應(yīng)分?jǐn)偟姆蓊~公理3 (席位單調(diào)性)總席位的增加不會使得某單位的席位 數(shù)減少公理4 (公平分?jǐn)傂?任何單位的席位數(shù)都不會偏離其比例 的份額數(shù)公理5 (接近份額性)沒有從一個單位到另一個單位的名額 轉(zhuǎn)讓會使得這兩個單位都接近于它們

3、應(yīng)得的份額,論文主要內(nèi)容,對幾種現(xiàn)有的席位分配方法進(jìn)行研究分析提出關(guān)于分配方法的最小遺憾度判斷標(biāo)準(zhǔn)提出最小遺憾度的席位分配方法提出余額延續(xù)分配法,幾種現(xiàn)有的分配方法,Hamilton 法經(jīng)典Q 值法、改進(jìn)Q 值法、新Q 值法最小極差法0-1 規(guī)劃法平均公平度法相對尾數(shù)法公平累加法,最小遺憾度判斷標(biāo)準(zhǔn),1.1 最小遺憾度標(biāo)準(zhǔn)的思想,所有的席位分配方法都是定義自己的一個標(biāo)準(zhǔn)，但是很少有席位分配方法本身優(yōu)劣性的判斷標(biāo)準(zhǔn)

4、。最小遺憾度標(biāo)準(zhǔn)旨在評判出某次席位分配的最佳分配方法。,1.2 遺憾度計算思路,設(shè)有A、B兩個部門，其中A部門分得最后一個席位，B部門為僅次于A能獲得最后一個席位的部門。B 部門只要再多出x 個人就能超過A 部門，獲得最后一個席位。而x即為B部門的遺憾度，且x越小遺憾度越大,1.3席位分配方法的遺憾度算法,,1.Hamilton 法,， 其中 為取 的小數(shù)部分,2.Q值法,3.新Q值法,（1）,（3）,（2）,4.相對尾

5、數(shù)法,，其中,5.公平累加法,（5）,（7）,（4）,（6）,例1：設(shè)某公司共有200人，該公司由A、B、C三個部門組成，其中A部門有103人，B部門有63人，C部門有34人，席位總數(shù)20。,Q值法遺憾度最大，相對尾數(shù)法遺憾度最小。故本次席位分配，相對尾數(shù)法最佳。最小遺憾度標(biāo)準(zhǔn)是針對某一次分配，根據(jù)各個分配方法的分配結(jié)果來判斷本次分配用那一種分配方法最佳。,表1,最小遺憾度的席位分配方法,2.1最小遺憾度法思想,,最小遺憾度法與最小遺憾

6、度標(biāo)準(zhǔn)相似。最小遺憾度法旨在使各部門中的最大遺憾度達(dá)到最小。即在k個分配方案中選出最大遺憾度中最小的方案。,代表 i 部門再有 個人就能再獲得一個席位,得,（8）,（9）,2.2最小遺憾度法的分配方法,step1.分配給各部門應(yīng)得席位份額中的整數(shù)部分，即,step2.將剩余下的席位分配給其中的某些部門,每個部門最多能得到一個席位，假設(shè)共有k種分配方案。,step3.計算 的值，取每種方案中的 min 然后從中選取最大值，即

7、max min ,亦即使最大遺憾度最小。,step4.最終的分配方案就是max min 對應(yīng)的分配方案。至此，分配結(jié)束。,例2：設(shè)某公司共有200人，該公司由A、B、C三個部門組成，其中A部門有103人，B部門有63人，C部門有34人,表2 20席位時最小遺憾度法與其他分配方法的分配結(jié)果,表3 21席位時最小遺憾度法與其他分配方法的分配結(jié)果,,由表2和表3可知，20席位時，最小遺憾度法與Hamilton法和新Q值法的分

8、配結(jié)果一致，21席位時，最小遺憾度法與Q值法和平均公平度法的分配結(jié)果一致。沒有出現(xiàn)因總席位數(shù)的增加而導(dǎo)致某個部門的席位數(shù)減少的不公平現(xiàn)象。,余額延續(xù)法,3.1余額延續(xù)法思想,基于多次相同的席位分配，記錄每次分配后各部門的余額。在下次席位分配時加上本次所記錄的余額，然后進(jìn)行分配。該方法追求在某一時間段內(nèi)各個部門的平均分配結(jié)果接近分配比例。,3.2余額延續(xù)法的分配方法,step1.計算各部門的分配比例 ，加上上次分配后的余額 ，得

9、,step2.基于 用Hamilton法對本次席位分配。,step3.記錄本次席位分配后的,（10）,例3：設(shè)某公司共有200人，該公司由A、B、C三個部門組成，其中A部門有103人，B部門有63人，C部門有34人，席位數(shù)20。,表4 前十次分配結(jié)果,從計算的結(jié)果知每個部門的平均席位數(shù)很接近應(yīng)得席位比例。余額延續(xù)法有效的利用了每次分配后的余額。該方法追求在某一時間段內(nèi)各個部門的平均分配結(jié)果接近分配比例。,對表4 以五年為一段求各