【5A版】學(xué)生建模報(bào)告-席位分配.doc

《【5A版】學(xué)生建模報(bào)告-席位分配.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、7A版優(yōu)質(zhì)實(shí)用文檔建模報(bào)告－－－－論文作者：雷楊，吳開強(qiáng)，李歐洲時(shí)間：20GG，5，7137A版優(yōu)質(zhì)實(shí)用文檔7A版優(yōu)質(zhì)實(shí)用文檔席位分配---------伯努利實(shí)驗(yàn)解決方案摘要：本文圍繞席位分配這一問(wèn)題采用了伯努利實(shí)驗(yàn)，采用了比較新型的方法和細(xì)致的算法分析，對(duì)分配過(guò)程中出現(xiàn)的種種情況都一一進(jìn)行了分析，并依此與其它的現(xiàn)有方法比較。我們認(rèn)為該分配方案較簡(jiǎn)便且比較優(yōu)越，很大程度上符合公平化原則關(guān)鍵詞：伯努利實(shí)驗(yàn)公平化原則時(shí)間復(fù)雜度最大成功次數(shù)一問(wèn)題重述：某學(xué)校有3個(gè)系共200名學(xué)生，其中甲系100名，乙系40名。若學(xué)

2、生代表會(huì)議設(shè)20個(gè)席位，公平而又簡(jiǎn)單的席位分配方法是按學(xué)生人數(shù)的比例分配，顯然甲乙丙三系分別應(yīng)占有10，6，4個(gè)席位?，F(xiàn)在丙系有6名學(xué)生轉(zhuǎn)入甲乙兩系，各系人數(shù)如表第二列所示。仍按比例分配時(shí)出現(xiàn)了小數(shù)，在將取得整數(shù)的19席分配完畢后，三系同意剩下的1席參照所謂慣例分配給比例中小數(shù)最大的丙系，于是三系仍分別占有10，6，4席。因?yàn)橛?0個(gè)席位的代表會(huì)議在表決提案時(shí)可能出現(xiàn)10：10的局面，會(huì)議決定下一屆增加1席。他們按照上述方法重新分配席位，計(jì)算結(jié)果見表。顯然這個(gè)結(jié)果對(duì)丙系太不公平了，因?yàn)榭傁辉黾?席，而丙系卻

3、由4席減為3席20個(gè)席位分配21個(gè)席位分配系別學(xué)生人數(shù)學(xué)生人數(shù)的比例比例分配的席位參照慣例的結(jié)果比例分配的席位參照慣例的結(jié)果甲10351.510.31010.81511乙6331.56.366.6157丙3417.03.443.5703137A版優(yōu)質(zhì)實(shí)用文檔7A版優(yōu)質(zhì)實(shí)用文檔總合200100.020.02021.0021理想化原則：設(shè)第i方人數(shù)為p,i=1,2,…,m,總?cè)藬?shù)P＝，待分配的席位為N，記q＝Np/P原則一，i=1，2，，m,即必須取，二者之一。原則二，i=1，2，，m,即總席位增加時(shí)不應(yīng)減少。二

4、模型假設(shè)我們把甲乙丙三系分配席位的這個(gè)事件看為要從有20個(gè)紅簽180個(gè)白簽（一共200=人數(shù)總和）的盒子里抽紅簽，對(duì)比抽得紅簽個(gè)數(shù)的概率大小來(lái)求得分配的名額。三模型的建立與求解解決方案公式i=1,2，…,s(抽得紅簽個(gè)的概率)是分配名額是總?cè)藬?shù)是第i組的人數(shù)k是紅簽的個(gè)數(shù)s是小組的個(gè)數(shù)是每人被抽到的概率由于抽簽的伯努利原理，二項(xiàng)分布的極值點(diǎn)在[],其中[]為向下取整函數(shù)，抽紅簽的個(gè)數(shù)實(shí)際上就是最大的成功次數(shù)，所以我們的分配方案取值從k137A版優(yōu)質(zhì)實(shí)用文檔7A版優(yōu)質(zhì)實(shí)用文檔=[](k為整數(shù)時(shí)取為k-1)開始，

5、首次計(jì)算出各個(gè)小組的k值，得出第一次要分配的人數(shù)為T=，則剩下的人為,,我們會(huì)得出以下情況：1.若T

6、……k(m)===m+1則T2再對(duì)不等式左邊證明：我們知道對(duì)一個(gè)數(shù)a>0,(a為有理數(shù))a=[a]+(a),0<(a)<1其中[a]表示a的整數(shù)部分，(a)表示a的小數(shù)部分.則由此出發(fā)137A版優(yōu)質(zhì)實(shí)用文檔7A版優(yōu)質(zhì)實(shí)用文檔由于k(m)==>=>m-s(0<<1)又因?yàn)槭钦麛?shù)，且值大于m-s所以最后的取值T，不等式左邊也得證l當(dāng)為整數(shù)時(shí)，k=[]-1，不等式右邊k(m)=>m-s(0<<1)又因?yàn)槭钦麛?shù)，且值大于m-s所以最后的取值T，不等式左邊仍成立定理證

7、明完畢對(duì)分配方案的解釋1.第一次分配137A版優(yōu)質(zhì)實(shí)用文檔7A版優(yōu)質(zhì)實(shí)用文檔我們分配名額時(shí)，讓三個(gè)小組進(jìn)行抽簽，一共有總?cè)藬?shù)個(gè)簽，其中有名額個(gè)紅簽，每組抽到幾個(gè)紅簽就分配幾個(gè)名額，然而這個(gè)方案肯定有人反對(duì)，因?yàn)橛锌赡苡械慕M一個(gè)也抽不到，所以我們給他們最有可能抽到的紅簽個(gè)數(shù)的名額。這個(gè)過(guò)程是伯努利實(shí)驗(yàn)，伯努利實(shí)驗(yàn)是服從二項(xiàng)分布的。這樣大家心理都比較平衡。1.第二次分配由于第一次抽簽有可能剩余，則原來(lái)各個(gè)小組被分到的人數(shù)就有可能加1，或保持不變。我們就比較多一個(gè)名額的概率的大小，因?yàn)?，假設(shè)都加1的情況下，概率大的

8、表示被抽到的機(jī)會(huì)大，就該分配給這組。所以第二次分配按概率大小，人數(shù)依次加上1，直到分配完畢。分配中的特殊情況：k=[]為整數(shù)時(shí)，在k和k-1同時(shí)達(dá)到最大，這時(shí)應(yīng)取k-1，因?yàn)槌晒Φ淖羁赡艽螖?shù)最先是在k-1次達(dá)到的。四模型的評(píng)價(jià)與算法分析1.對(duì)于Q值方法，算法執(zhí)行時(shí)間主要耗費(fèi)在對(duì)S個(gè)小組分別分配完1個(gè)之后，用Q值公式分配余下的M-S個(gè)人，時(shí)間復(fù)雜度為O（（M-S）S）。2.伯努利方法，算法執(zhí)行時(shí)間主要