數(shù)學(xué)模型 第二講 建模方法示例

第二講建模方法示例2.1商人怎樣安全過河2.2公平的席位分配2.3Fibonacci數(shù)列2.1

商人們?cè)鯓影踩^河問題(智力游戲)3名商人3名隨從隨從們密約,在河的任一岸,一旦隨從的人數(shù)比商人多,就殺人越貨.乘船渡河的方案由商人決定.商人們?cè)鯓硬拍馨踩^河?問題分析多步?jīng)Q策過程決策~每一步(此岸到彼岸或彼岸到此岸)船上的人員.要求~在安全的前提下(兩岸的隨從數(shù)不比商人多),經(jīng)有限步使全體人員過河.河小船(至多2人)模型構(gòu)成xk~第k次渡河前此岸的商人數(shù)yk~第k次渡河前此岸的隨從數(shù)xk,yk=0,1,2,3;

k=1,2,…sk=(xk,yk)~過程的狀態(tài)S={(x

,y)x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2}S~允許狀態(tài)集合uk~第k次渡船上的商人數(shù)vk~第k次渡船上的隨從數(shù)dk=(uk,vk)~過程的決策D~允許決策集合uk,vk=0,1,2;k=1,2,…sk+1=sk

dk+(-1)k~狀態(tài)轉(zhuǎn)移律D={(u

,v)u+v=1,2,u,v=0,1,2}狀態(tài)因決策而改變模型求解xy3322110

窮舉法~編程上機(jī)

圖解法狀態(tài)s=(x,y)~16個(gè)格點(diǎn)~10個(gè)點(diǎn)允許決策~移動(dòng)1或2格;k奇,左下移;k偶,右上移.s1sn+1d1,,d11給出安全渡河方案d1d11允許狀態(tài)S={(x

,y)x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2}求dkD(k=1,2,n),使skS,并按轉(zhuǎn)移律sk+1=sk+(-1)kdk

由s1=(3,3)到達(dá)sn+1=(0,0).模型構(gòu)成商人和隨從人數(shù)增加或小船容量加大;商人們?cè)鯓影踩^河智力游戲多步?jīng)Q策過程(數(shù)學(xué)模型)易于推廣:規(guī)格化方法考慮4名商人各帶一隨從的情況.多步?jīng)Q策模型:恰當(dāng)?shù)卦O(shè)置狀態(tài)和決策,確定狀態(tài)轉(zhuǎn)移律及目標(biāo)(目標(biāo)函數(shù)).便于求解(計(jì)算機(jī)編程等).每十年，美國聯(lián)邦政府進(jìn)行一次全國人口普查(census)。各州在聯(lián)邦眾議院的代表名額也據(jù)此重新確定。公平的席位分配問題（apportionment）2000年人口普查后，猶他州（Utah）向聯(lián)邦政府提出控訴，說分配給卡羅萊納州的名額應(yīng)該是他們的。問題的數(shù)學(xué)本質(zhì)是什么？事實(shí)上，過去200年來，美國國會(huì)在名額分配上打過多起法律官司，曾有過長期爭論并用過四種分配方案。2.2

公平的席位分配一個(gè)簡單例子系別學(xué)生比例20席的分配人數(shù)（%）比例結(jié)果甲10351.5

乙6331.5

丙3417.0總和200100.020.02021席的分配比例結(jié)果10.8156.6153.57021.00021問題三個(gè)系學(xué)生共200名(甲100，乙60，丙40)，代表會(huì)議共20席，按比例分配，三個(gè)系分別為10,6,4席.因?qū)W生轉(zhuǎn)系,三系人數(shù)為103,63,34,如何分配20席?若代表會(huì)議增加1席，如何分配21席?比例加慣例對(duì)丙系公平嗎？系別學(xué)生比例20席的分配人數(shù)（%）比例結(jié)果甲10351.510.310

乙6331.56.36

丙3417.03.44總和200100.020.02021席的分配比例結(jié)果10.815116.61573.570321.00021模型已知:m方人數(shù)分別為

p1,p2,…pm,記總?cè)藬?shù)為P=p1+p2+…+pm,待分配的總席位為N.

各方先分配qi的整數(shù)部分[qi],總余額為

記ri=qi-[qi],則第i方的分配名額ni為要求已知份額向量q=(q1,…,qm)>0,找一個(gè)非負(fù)整數(shù)分配向量n=(n1,…,nm),使n與q最接近.比例加慣例法記qi=Npi/P,稱為第i方的份額(i=1,2,…m)背景Hamilton(比例加慣例)方法A.Hamilton提出的這種辦法1792年被美國國會(huì)否決

1850-1900年被美國國會(huì)采用(稱為Vinton法)

又稱為最大剩余法（GR:GreatestRemainders）或最大分?jǐn)?shù)法（LF:LargestFractions），等等

席位悖論—總席位增加反而可能導(dǎo)致某州席位減少

1880年Alabama州曾遇到，又稱Alabama悖論

該方法的另一個(gè)重大缺陷：（下頁給例子）

人口悖論—某州人口增加較多反而可能該州席位減少

Hamilton方法的不公平性1.p1,p2,…pm不變,N的增加會(huì)使某個(gè)ni減少(上例).2.N不變,pi比pj的增長率大,會(huì)使ni減少nj增加(下例).pinii=110311i=2637i=3343和20021pi1146434212ni116421pini1031063634420020pi114(+10.6%)6338(+11.8%)215ni116320“公平”分配方法衡量公平分配的數(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īng)使rA

,rB

盡量小設(shè)A,B已分別有n1,n2席,若增加1席,問應(yīng)分給A,還是B?不妨設(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

，定義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

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

是否會(huì)出現(xiàn)？A否!若rB(n1+1,n2)>rA(n1,n2+1),則這席應(yīng)給B當(dāng)rB(n1+1,n2)<rA(n1,n2+1),該席給ArA,rB的定義該席給A否則,該席給B

定義該席給Q值較大的一方推廣到m方分配席位該席給Q值最大的一方相等比例法,即EP法(Huntington,1921)計(jì)算，三系用EP方法重新分配21個(gè)席位一席一席地將前19席分配完畢后的結(jié)果甲系：p1=103,n1=10乙系：p2=63,n2=6丙系：p3=34,n3=3與Hamilton法結(jié)果相同第20席第21席同上Q3最大，第21席給丙系甲系11席,乙系6席,丙系4席EP方法分配結(jié)果公平嗎？Q1最大，第20席給甲系1920年代哈佛大學(xué)數(shù)學(xué)家E.V.Huntington做了系統(tǒng)研究.EP法每增加1席地計(jì)算，不會(huì)出現(xiàn)席位悖論和人口悖論.

有沒有其他的不公平度衡量指標(biāo)？

當(dāng)總席位為s時(shí)第i方分配的席位記作fi(p,s),fi(p,0)=0除數(shù)法（Huntington，1921）

對(duì)于非負(fù)整數(shù)n定義一個(gè)非負(fù)單調(diào)增函數(shù)d(n)

讓s每次1席地遞增至N，按照以下準(zhǔn)則分配:

記ni=fi(p,s)，若則令fk(p,s+1)=nk+1,fi(p,s+1)=ni(i≠k)５種除數(shù)法Huntington除數(shù)法除數(shù)d(n)不公平度的度量指標(biāo)（設(shè)pi/ni≥pj/nj）以人名命名的稱謂最大除數(shù)法（GD：Greatestdivisors)n+1njpi/pj-niJefferson;Seaton;d?Hondt主要分?jǐn)?shù)法（MF：Majorfraction)n+1/2nj/pj-ni/piWebster相等比例法（EP：Equalproportions)njpi/nipj-1Hill調(diào)和平均法（HM：Harmonicmean)2n(n+1)/

(2n+1)pi/ni-pj/njDean最小除數(shù)法（SD：Smallestdivisors)nnj-nipi/pjAdamsEP(幾何平均)MF(算術(shù)平均)HM(調(diào)和平均)5種除數(shù)法：一個(gè)數(shù)值例子

piqiGDMFEPHMSDA90619.061109999B71797.17978777C52595.25955655D33193.31933343E11821.18211112總和26000262626262626一般情況下，偏向程度也按照表中的順序：

GD偏向人數(shù)pi較大的一方

SD偏向人數(shù)較小的一方公平的席位分配：優(yōu)化模型MF法：

最大剩余法(GR)實(shí)際上解決了以下優(yōu)化問題：你能證明這些結(jié)論嗎？任意lt范數(shù)(t≥1),如：1,2,∞范數(shù)EP法：模型的公理化研究關(guān)鍵性質(zhì)1)[qi]ni

[qi]+1

(i=1,2,…m)

~份額性2)fi

(p,s)fi

(p,s+1)

~席位單調(diào)性~人口單調(diào)性3)若pi'

/pj'

≥

pi/pj,則fi(p',s)

≥

fi(p,s),

或fj(p',s)

fj(p,s)模型的公理化研究EP方法比最大剩余法(GR)更公平嗎？已知總席位數(shù)s,人口向量p=(p1,p2,…pm),P=Σpi份額向量q

=

(q1,…,qm)，qi=spi/Pni＝fi(p,s)表示人數(shù)為p、總席位為s時(shí)分配給第i方席位(參見教材注釋)

GR方法滿足性質(zhì)1，但不滿足性質(zhì)2,3.

除數(shù)方法滿足性質(zhì)2,3,但不滿足性質(zhì)1.模型的公理化研究ipiqiGDMFEPHMSDGR19149091.49949390898892216601.66122222314601.46112222414501.45112221514401.44112221614001.40111221711001.10111121100000100100100100100100100模型的公理化研究可以找到同時(shí)滿足份額性和席位單調(diào)性的方法.已經(jīng)證明：對(duì)于m≥4,N≥m+3,不存在滿足3條性質(zhì)(份額性、席位單調(diào)性、人口單調(diào)性)的分配方法.關(guān)于席位分配問題的歷史發(fā)展?fàn)顩r、數(shù)學(xué)研究方法的完整敘述：M.L.Balinski&H.P.Young,FiarRepresentation2001年第2版席位分配問題評(píng)述

建立“公平分配席位”模型的關(guān)鍵是建立衡量公平程度的數(shù)量指標(biāo).

對(duì)各種方法違反某條公理的概率也有研究（仿真）

如果采用公理化方法——提出公平分配席位的理想化原則，那么該問題尚未徹底解決——已證明不存在滿足一組公理的席位分配方法.

人們提出過上百種方法，還研究、比較過方法的相容性、穩(wěn)定性、無偏性等.MF無偏！

上述討論可推廣到m變化的情形、有上下限的情形等.歷史資料及權(quán)力指標(biāo)

美國國會(huì)實(shí)際采用過的方法：1830年前采用GD1840年采用MF1850-1900年采用GR（有時(shí)輔以調(diào)整）1910年采用MF1920年沒有重新分配席位1930年后采用EP相關(guān)問題：得到席位，就意味著有權(quán)力嗎？投票規(guī)則；權(quán)力指標(biāo)計(jì)量政治學(xué)問題描述1228年,意大利的數(shù)學(xué)家斐波那契(Fibonacci)提出了一個(gè)有趣的問題：如果最初有一對(duì)剛出生的小兔，一個(gè)月后就成熟，成熟后每月生一對(duì)（一雌一雄），且所生的小兔都能成活，而且按同樣方法繁殖，則一年后共有多少對(duì)兔?2.3Fibonacci數(shù)列示意圖生成數(shù)列該數(shù)列{Fn}稱為斐波那契(Fibonacci)數(shù)列.直到1634年，才有數(shù)學(xué)家奇拉特發(fā)現(xiàn)此數(shù)列具有非常簡單的遞推關(guān)系：F1=F2=1,Fn=Fn-2+Fn-1月n

12345678910111213Fn1123581321345589144233遞推公式的不便欲求F100=？則要先計(jì)算F99與F98又要先算F97與F96…

…

…最后還是要從F1與F2算起最好能直接從n算出Fn，這種公式叫通式探索斐波那契數(shù)列通式的實(shí)驗(yàn)已知Fn:1,1,2,3,5,8,13,21,34,55,89,144，…

F1=F2=1遞推關(guān)系式Fn+2=Fn+1+Fn

(1)觀察初步猜想

{Fn}的圖象指數(shù)曲線，猜測：Fn=an

(2)

推理由(1)式得an+2=an+1+an，即a2-a-1=0，解出兩根：分析

無論a=a1或a=a2,由(2)式定義的數(shù)列{Fn}都能滿足遞推式(1).