公平的席位分配等四個(gè)數(shù)學(xué)模型例子

補(bǔ)例1賽程安排問(wèn)題方案1：設(shè)有n人報(bào)名參賽，下面對(duì)n為不同的值進(jìn)行討論。（2）若，則存在一個(gè)正整數(shù)k，使得（1）若，第一輪比賽有場(chǎng)，…1/4決賽有場(chǎng)，半決賽有2場(chǎng)，冠亞軍比賽1場(chǎng)，合計(jì)（場(chǎng)）：場(chǎng)數(shù)為第一輪的比賽次數(shù)是，人輪空，剩下的人數(shù)為，這樣之后的k－1輪比賽中的第一頁(yè)第二頁(yè)，共43頁(yè)。補(bǔ)例1賽程安排問(wèn)題所以一共要比賽：若本輪比賽的人數(shù)為偶數(shù)，則沒(méi)有輪空；若人數(shù)為奇數(shù)，則有1人輪空。從而比賽輪空的人數(shù)不大于k－1人方案2：設(shè)有n人報(bào)名參賽，每一輪允許有輪空現(xiàn)象。例1：某校有11位同學(xué)參加圍棋單淘汰賽，應(yīng)該進(jìn)行幾場(chǎng)比賽？則存在一個(gè)正整數(shù)k，使得第二頁(yè)第三頁(yè)，共43頁(yè)。補(bǔ)例1賽程安排問(wèn)題二、單循環(huán)賽：設(shè)有n隊(duì)參加比賽，則每隊(duì)都要與其余的n－1支隊(duì)分別比賽一場(chǎng)。當(dāng)n為偶數(shù)時(shí)，則要舉行n－1輪比賽；當(dāng)n為奇數(shù)時(shí)，則要舉行n輪比賽，且每輪有1隊(duì)輪空單循環(huán)賽就是參加比賽的每一個(gè)人都要和其他人比賽一次，然后根據(jù)總體成績(jī)排定名次。如果和其他人比賽兩次，則稱為雙循環(huán)賽。定理：設(shè)有n隊(duì)參加比賽，則比賽的總場(chǎng)數(shù)是場(chǎng)。例2：某校共有26個(gè)班，舉行排球比賽，在不同的賽制下各要比多少場(chǎng)？第三頁(yè)第四頁(yè)，共43頁(yè)。補(bǔ)例1賽程安排問(wèn)題優(yōu)缺點(diǎn)分析：（略）例3：參加排球比賽的26個(gè)班級(jí)，先分成3個(gè)小組，其中兩個(gè)組為9隊(duì)，另一個(gè)組為8隊(duì)，在小組中，先用單循環(huán)賽產(chǎn)生每個(gè)小組的前兩名，接下來(lái)，每小組的前兩名共6個(gè)隊(duì)再進(jìn)行單循環(huán)賽。以8支隊(duì)的小組為例，對(duì)賽程進(jìn)行合理安排。解：在第一階段：場(chǎng)在第二階段：場(chǎng)一共比賽的場(chǎng)數(shù)為100+15＝115場(chǎng)。第四頁(yè)第五頁(yè)，共43頁(yè)。補(bǔ)例1賽程安排問(wèn)題用表示八支代表對(duì)，則A1——A2A3——A4A5——A6A7——A8A1——A3A5——A2A7——A4A8——A6A1——A5A7——A3A8——A2A6——A4A1——A7A8——A5A6——A3A4——A2A1——A8A6——A7A4——A5A2——A3A1——A6A4——A8A2——A7A3——A5A1——A4A2——A6A3——A8A5——A7第五頁(yè)第六頁(yè)，共43頁(yè)。補(bǔ)例1賽程安排問(wèn)題A1A2A3A4A5A6A7A8A115259211317A2120166262311A3520224151027A4251621912722A596241932814A6212615123188A7132310728184A81711272214844+4+4+3+2+2＝192+4+4+4+3+2＝194+4+3+2+2+2＝172+2+4+4+4+3＝194+3+2+2+2+4＝172+2+2+4+4+4＝183+2+2+2+4+4＝17由以上表格可知該安排是合理的3+3+3+3+3+3＝18每?jī)蓤?chǎng)間隔場(chǎng)次第六頁(yè)第七頁(yè)，共43頁(yè)。

作業(yè)：當(dāng)7支隊(duì)參加單循環(huán)賽的排球比賽時(shí)，試合理的安排其賽程。第七頁(yè)第八頁(yè)，共43頁(yè)。補(bǔ)例2洗衣節(jié)水問(wèn)題我國(guó)淡水資源有限，節(jié)約用水勢(shì)在必行。那么如何在洗衣服中合理地用水，使得既能把衣服洗干凈，又能節(jié)約用水的問(wèn)題就擺在我們的面前。一般洗衣服的過(guò)程是先將衣服用洗滌劑浸泡，然后一次次地用水漂洗。洗衣機(jī)的運(yùn)行過(guò)程分別為加水—>漂洗—>脫水—>加水—>漂洗—>脫水……這么一個(gè)循環(huán)過(guò)程。我們的問(wèn)題是在保證一定洗滌效果下，洗衣服分成多少次（或在洗衣機(jī)中應(yīng)循環(huán)幾次），每一次的用水量是否一致，使得總的用水量最為節(jié)??？問(wèn)題提出：第八頁(yè)第九頁(yè)，共43頁(yè)。

衣服潔凈的問(wèn)題實(shí)際上是比較復(fù)雜的，它不僅有物理原理，還有化學(xué)原理（如果是洗衣機(jī)，則與機(jī)械原理有關(guān)）。補(bǔ)例2洗衣節(jié)水問(wèn)題問(wèn)題分析：其基本原理就是將吸附在衣物上的污物溶于水中，通過(guò)脫水而蕩滌污物。節(jié)水目標(biāo)為在一定量的用水條件下，在洗衣過(guò)程中如何合理地分配這些水，使得能達(dá)到把衣服洗凈的目的。第九頁(yè)第十頁(yè)，共43頁(yè)。我們?cè)趩?wèn)題的分析中已經(jīng)知道了洗衣的原理是將吸附在衣物上的污物溶于水中，通過(guò)擰干（脫水）而蕩滌污物。因此我們有以下的兩個(gè)假設(shè)：

補(bǔ)例12洗衣節(jié)水問(wèn)題1）在漂洗時(shí)間足夠的前提下，衣服上的污物能被洗滌劑完全溶解在水中。2）每次擰干后衣服中殘留的水量是一致的。模型假設(shè)：第十頁(yè)第十一頁(yè)，共43頁(yè)。補(bǔ)例2洗衣節(jié)水問(wèn)題問(wèn)題歸結(jié)為：在水的總量為的條件下，將水分成次洗滌，每次用量分別為。問(wèn)經(jīng)過(guò)這次洗滌，衣服上還剩下多少污物？

模型建立與求解：設(shè)洗衣服一開始浸泡時(shí)的用水量為，按照問(wèn)題的分析，可看成是一個(gè)常量。經(jīng)擰干后殘留污物的質(zhì)量為，記第次擰干后殘留于衣服中的污物（還包含了洗滌劑的質(zhì)量）為，同時(shí)記衣服中殘留的水量為，再設(shè)洗衣服的總水量為，第十一頁(yè)第十二頁(yè)，共43頁(yè)。補(bǔ)例2洗衣節(jié)水問(wèn)題我們引入洗滌劑的濃度概念（單位質(zhì)量水中所含的污物質(zhì)量）（表示第次漂洗污物的濃度），第一次漂洗時(shí)的濃度為我們引入洗滌劑的濃度概念（單位質(zhì)量水中所含的污物質(zhì)量）（表示第次漂洗污物的濃度），第一次漂洗時(shí)的濃度為第十二頁(yè)第十三頁(yè)，共43頁(yè)。補(bǔ)例2洗衣節(jié)水問(wèn)題仿此，可得第二次漂洗時(shí)的濃度此時(shí)擰干殘留的污物為依此類推，可得第此漂洗之后，衣服上的殘留污物量為第十三頁(yè)第十四頁(yè)，共43頁(yè)。補(bǔ)例2洗衣節(jié)水問(wèn)題（2）式可化為（3）式為一遞推關(guān)系式，以下導(dǎo)出關(guān)于初始值的表達(dá)式。

因此由數(shù)學(xué)歸納法證得第十四頁(yè)第十五頁(yè)，共43頁(yè)。補(bǔ)例2洗衣節(jié)水問(wèn)題洗衣服的目的是要使污物越來(lái)越少，即在漂洗過(guò)程中洗滌劑濃度越來(lái)越少，轉(zhuǎn)化為數(shù)學(xué)語(yǔ)言就是在一定條件下，如何選取方能使達(dá)到最小。（5）式還可以改寫為我們將它總結(jié)為以下定理：定理：在總用水量一定的條件下，平均分配每次加水量，實(shí)現(xiàn)的洗滌效果最好。第十五頁(yè)第十六頁(yè)，共43頁(yè)。

證：補(bǔ)例2洗衣節(jié)水問(wèn)題第十六頁(yè)第十七頁(yè)，共43頁(yè)。補(bǔ)例2洗衣節(jié)水問(wèn)題第十七頁(yè)第十八頁(yè)，共43頁(yè)。補(bǔ)例2洗衣節(jié)水問(wèn)題模型分析：從殘留在衣服中污物量的濃度變化可知，即每多洗滌一次，污物就少一些。實(shí)際上在每次洗滌加水量相同的條件下，由(5)式得關(guān)于是單調(diào)遞減的函數(shù)。即漂洗衣服最好少量多次。下一個(gè)問(wèn)題：是否在用水量一定的條件下，洗滌的次數(shù)足夠多，便可以使趨向于零，即衣服的污物被完全清除呢？即當(dāng)趨向于無(wú)窮大時(shí)，是否趨向于無(wú)窮?。康谑隧?yè)第十九頁(yè)，共43頁(yè)。

(8)式說(shuō)明了當(dāng)水的總量一定的時(shí)候，無(wú)論你怎樣洗滌，不管次數(shù)多少，最后的結(jié)果是不可能一點(diǎn)污物都不殘留的。補(bǔ)例2洗衣節(jié)水問(wèn)題第十九頁(yè)第二十頁(yè)，共43頁(yè)。補(bǔ)例2洗衣節(jié)水問(wèn)題先引入一個(gè)清潔度的定義。設(shè)是洗凈衣服上的污物量與第一次浸泡后殘留在衣服上的污物量之比，即進(jìn)一步討論:如何確定洗滌的次數(shù)。我們用來(lái)反映衣物洗凈的清潔程度。第二十頁(yè)第二十一頁(yè)，共43頁(yè)。洗滌的次數(shù)大約為3，即洗滌3次可使衣服潔凈到一定程度，這一結(jié)果與我們生活實(shí)際情況也是相符的。補(bǔ)例2洗衣節(jié)水問(wèn)題第二十一頁(yè)第二十二頁(yè)，共43頁(yè)。一.比例代表制例：有A、B、C、D四個(gè)政黨，代表50萬(wàn)選民，各政黨的選民數(shù)為：A黨：199,000B黨：127,500C黨：124,000D黨：49,500要選出5名代表：A黨：2席B黨：1席C黨：1席D黨：0席缺少1席，如何分配這最后一席呢？補(bǔ)例3公平的席位分配第二十二頁(yè)第二十三頁(yè)，共43頁(yè)。最大余數(shù)法按每10萬(wàn)選民1席分配后，按余數(shù)大小排序，多余的席位分給余數(shù)較大的各黨。黨名代表選民數(shù)整數(shù)席余數(shù)余額席總席數(shù)A199,000199,00012B127,500127,50001C124,000124,00001D49,500049,50011補(bǔ)例3公平的席位分配第二十三頁(yè)第二十四頁(yè)，共43頁(yè)。洪德(d

Hondt)規(guī)則分配辦法是：把各黨代表的選民數(shù)分別被1、2、3、…除，按所有商數(shù)的大小排序，席位按此次序分配。即若A黨的人數(shù)比D黨的人數(shù)還多，那么給A黨3席、給D黨0席也是合理的。除數(shù)A黨B黨C黨D黨1199,000(1)127,500(2)124,000(3)49,500299,500(4)63,75062,00024,750366,333(5)42,50041,33316,500449,75031,875－－總席位3110補(bǔ)例3公平的席位分配第二十四頁(yè)第二十五頁(yè)，共43頁(yè)。北歐折衷方案作法與洪德規(guī)則類似，所采用的除數(shù)依次為1.4、3、5、7、…A黨B黨C黨D黨2210三種分配方案，得到了完全不同的結(jié)果，最大余數(shù)法顯然對(duì)小黨比較有利，洪德規(guī)則則偏向最大的黨，北歐折衷方案對(duì)最大和最小黨都不利補(bǔ)例3公平的席位分配第二十五頁(yè)第二十六頁(yè)，共43頁(yè)。二．份額分配法(QuotaMethod)一種以“相對(duì)公平”為標(biāo)準(zhǔn)的席位分配方法，來(lái)源于著名的“阿拉巴瑪悖論”(AlabamaParadox)。美國(guó)憲法第1條第2款對(duì)議會(huì)席位分配作了明確規(guī)定，議員數(shù)按各州相應(yīng)的人數(shù)進(jìn)行分配。最初議員數(shù)只有65席，因?yàn)樽h會(huì)有權(quán)改變它的席位數(shù)，到1910年，議會(huì)增加到435席。憲法并沒(méi)有規(guī)定席位的具體分配辦法，因此在1881年，當(dāng)考慮重新分配席位時(shí)，發(fā)現(xiàn)用當(dāng)時(shí)的最大余數(shù)分配方法，阿拉巴瑪州在299個(gè)席位中獲得8個(gè)議席，而當(dāng)總席位增加為300席時(shí)，它卻只能分得7個(gè)議席。這一怪事被稱為有名的“阿拉巴瑪悖論”。補(bǔ)例3公平的席位分配第二十六頁(yè)第二十七頁(yè)，共43頁(yè)。系別學(xué)生比例20席的分配人數(shù)（%）比例結(jié)果甲10351.5乙6331.5丙3417.0總和200100.020.02021席的分配比例結(jié)果10.8156.6153.57021.00021問(wèn)題三個(gè)系學(xué)生共200名（甲系100，乙系60，丙系40），代表會(huì)議共20席，按比例分配，三個(gè)系分別為10，6，4席。現(xiàn)因?qū)W生轉(zhuǎn)系，三系人數(shù)為103,63,34,問(wèn)20席如何分配。若增加為21席，又如何分配。比例加慣例對(duì)丙系公平嗎系別學(xué)生比例20席的分配人數(shù)（%）比例結(jié)果甲10351.510.3乙6331.56.3丙3417.03.4總和200100.020.020系別學(xué)生比例20席的分配人數(shù)（%）比例結(jié)果甲10351.510.310乙6331.56.36丙3417.03.44總和200100.020.02021席的分配比例結(jié)果10.815116.61573.570321.00021補(bǔ)例3公平的席位分配第二十七頁(yè)第二十八頁(yè)，共43頁(yè)。“公平”分配方法衡量公平分配的數(shù)量指標(biāo)人數(shù)席位A方p1

n1B方p2n2當(dāng)p1/n1=p2/n2時(shí)，分配公平

p1/n1–p2/n2~對(duì)A的絕對(duì)不公平度p1=150,n1=10,p1/n1=15p2=100,n2=10,p2/n2=10p1=1050,n1=10,p1/n1=105p2=1000,n2=10,p2/n2=100p1/n1–p2/n2=5但后者對(duì)A的不公平程度已大大降低!雖二者的絕對(duì)不公平度相同若p1/n1>p2/n2，對(duì)不公平A

p1/n1–p2/n2=5第二十八頁(yè)第二十九頁(yè)，共43頁(yè)。公平分配方案應(yīng)使rA

,rB

盡量小不妨設(shè)分配開始時(shí)p1/n1>p2/n2，即對(duì)A不公平~對(duì)A的相對(duì)不公平度將絕對(duì)度量改為相對(duì)度量類似地定義rB(n1,n2)將一次性的席位分配轉(zhuǎn)化為動(dòng)態(tài)的席位分配,即“公平”分配方法若p1/n1>p2/n2，定義設(shè)A,B已分別有n1,n2席，若增加1席，問(wèn)應(yīng)分給A,還是B第二十九頁(yè)第三十頁(yè)，共43頁(yè)。1）若p1/(n1+1)>p2/n2，則這席應(yīng)給A2）若p1/(n1+1)<p2/n2，3）若p1/n1>p2/(n2+1)，應(yīng)計(jì)算rB(n1+1,n2)應(yīng)計(jì)算rA(n1,n2+1)若rB(n1+1,n2)<rA(n1,n2+1),則這席應(yīng)給應(yīng)討論以下幾種情況初始p1/n1>p2/n2

問(wèn)：p1/n1<p2/(n2+1)

是否會(huì)出現(xiàn)？A否!若rB(n1+1,n2)>rA(n1,n2+1),則這席應(yīng)給B第三十頁(yè)第三十一頁(yè)，共43頁(yè)。當(dāng)rB(n1+1,n2)<rA(n1,n2+1),該席給ArA,rB的定義該席給A否則,該席給B定義該席給Q值較大的一方推廣到m方分配席位該席給Q值最大的一方Q值方法計(jì)算，第三十一頁(yè)第三十二頁(yè)，共43頁(yè)。三系用Q值方法重新分配21個(gè)席位按人數(shù)比例的整數(shù)部分已將19席分配完畢甲系：p1=103,n1=10乙系：p2=63,n2=6丙系：p3=34,n3=3用Q值方法分配第20席和第21席第20席第21席同上Q3最大，第21席給丙系甲系11席，乙系6席，丙系4席Q值方法分配結(jié)果公平嗎？Q1最大，第20席給甲系第三十二頁(yè)第三十三頁(yè)，共43頁(yè)。進(jìn)一步的討論Q值方法比“比例加慣例”方法更公平嗎？席位分配的理想化準(zhǔn)則已知:m方人數(shù)分別為p1,p2,…,pm,記總?cè)藬?shù)為P=p1+p2+…+pm,待分配的總席位為N。設(shè)理想情況下m方分配的席位分別為n1,n2,…,nm(自然應(yīng)有n1+n2+…+nm=N)，記qi=Npi/P,i=1,2,…,m,ni應(yīng)是N和p1,…,pm

的函數(shù)，即ni

=ni(N,p1,…,pm)若qi

均為整數(shù)，顯然應(yīng)ni=qi第三十三頁(yè)第三十四頁(yè)，共43頁(yè)。

qi=Npi/P不全為整數(shù)時(shí)，ni

應(yīng)滿足的準(zhǔn)則：記[qi]–=floor(qi)~向

qi方向取整；[qi]+=ceil(qi)~向

qi方向取整.1)[qi]–

ni

[qi]+(i=1,…,m),2)ni

(N,p1,…,pm)

ni

(N+1,p1,…,pm)(i=1,…,m)

即ni必取[qi]–,[qi]+之一即當(dāng)總席位增加時(shí)，ni不應(yīng)減少“比例加慣例”方法滿足1），但不滿足2）Q值方法滿足2）,但不滿足1）。令人遺憾！第三十四頁(yè)第三十五頁(yè)，共43頁(yè)。

作業(yè)：

學(xué)校共1000名學(xué)生，235人住在A宿舍,333人住在B宿舍,432人住在C宿舍.學(xué)生要組織一個(gè)10人的委員會(huì),使用下列辦法分配各宿舍的委員數(shù):

1)按比例分配取整數(shù)的名額后,剩下的名額按慣例分給小數(shù)部分較大者.

2)用Q值法進(jìn)行分配.

若委員會(huì)人數(shù)從10增至15人,又如何分配呢?請(qǐng)分別用上述兩種方法給出過(guò)程及結(jié)果.第三十五頁(yè)第三十六頁(yè)，共43頁(yè)。

補(bǔ)例4鋪地磚問(wèn)題地面被劃分為6×7的方格，方形地磚大小等同于方格的大小。問(wèn)題提出：某人買了20塊長(zhǎng)方形磚，其一塊大小等于方形地磚的兩塊。請(qǐng)問(wèn)：1.能否完整地鋪設(shè)如圖1所示的地面？2.若在圖1所示的地面中，有一格不用鋪設(shè)，問(wèn)長(zhǎng)方形地磚能否完整地鋪設(shè)地面？3.若在圖1所示的地面中，左上角和右上角的格不用鋪設(shè)，問(wèn)長(zhǎng)方形地磚能否完整地鋪設(shè)地面？（圖1）1234567123456第三十六頁(yè)第三十七頁(yè)，共43頁(yè)。

補(bǔ)例4鋪地磚問(wèn)題問(wèn)題分析：1塊長(zhǎng)方形地磚等于2塊方形地磚，即（圖1）1234567123456長(zhǎng)方形地磚恰好能覆蓋兩個(gè)相鄰的格子。問(wèn)題轉(zhuǎn)化為：在給定的圖形中，滿足條件的覆蓋是否存在。模型建立與求解：設(shè)有m×n的格子盤（m，n都是正整數(shù)），首先給出格子盤被完全覆蓋的充要條件。定理1：

m×n的格子盤被完全覆蓋的充要條件是：m、n中至少有一個(gè)為偶數(shù)第三十七頁(yè)第三十八頁(yè)，共43頁(yè)。