席位的公平分配數(shù)學模型

1、第23卷第3期1999年6月武漢交通科技大學學報JournalofWuhanTransportationUniversityVol.23No.3June1999席位的公平分配數(shù)學模型楊國武(武漢交通科技大學基礎課部武漢430063)摘要:對席位公平分配問題提出了兩個合理性限制條件,給出了分別滿足這兩個條件的方差最小數(shù)學模型及解法和同時滿足這兩個條件的數(shù)學模型及解法.關鍵詞:數(shù)學模型;方差;非線性整數(shù)規(guī)劃;動態(tài)規(guī)劃中圖法分類號:O290引言席位公平分配問題是在若干單位中如何只根據(jù)各單位人數(shù)的多寡來分配總席位,使之盡可能合理、公平.也就是:設有m個單位A1,A2,Am,各有p1,2m然該單位是不會

2、認為該分配方案是合理的.文獻2還給了一種化為非線性整數(shù)規(guī)劃的分配方案,即尋求合理的n1,n2,nm使得:mminJ(n1,n2mi=1(-qi2)qi,pm個人,共p=i=1pi人,mni1,且為整數(shù),i=1,2,m表,問怎樣合理、,m個12,nm個,樣求合理、公平的n1,n2,nm.為敘述方便,引入以下記號:33qi=q,qi=qi(即qi的整數(shù)部分),p3mn=ii=1q,怎如果不加約束條件ni=qi或qi+1,則文獻2中所提供的解法是不正確的.這兩種方案都是以每個單位分配的席位數(shù)ni為分母作相對或絕對不公平的比較.當總席位數(shù).q不大時(如qk,則kk+1,aj1aj1+m期望EX=pj1

3、,設aj2i=1=pippmmni=1i=p=minai,則j2j2+1;1im2)若r=k,則停,否則,kk+1,aj2aj2+pj2方差DX=i=1(-pp2)p,設aj3=minai,則j3j3+1.如此下去,1im合理的席位分配方案為:1)求n1,n2,nm使得:m直至r=k.停,這時i,i=1,2,m為所求問題(2)的解表示對A賦以B值).(注:“AB”)pminDX=mi=1i(-ppi證明用歸納法1)當r=1時,記DX1=(1)pj1(1-j1)p(0-ij1ii)+ni=1=qs.t.niqi,ni為整數(shù),i=1,2,mDX=piki(0-i)+2)當式(1)有2組以上解時,人

4、數(shù)pi較少的單位Ai優(yōu)先.這樣做的目的是為了減少相對不公平值.3)當有兩個單位人數(shù)一樣多,又只能再分配一個席位時,只能協(xié)商解決.模型1的求解:式:mpk(1-k,j1則X1-X2jk.n定理成立時,設pj1=min1impimminDX=mipi=1pi先證j11.對任一組y1,y2,ym,yj1=0,yii=1(i-i)=r,yi0,i=1,2,m.不妨設y11對應的DX記為DX1,取j1=1,1=y1-1,i=yi,i1,=i=1r(2)j1,對應的DX記為DX2,則DX1s.t.i0,且i為整數(shù),i=1,2,m-DX2=-pj1+p1p1-該問題可以化為動態(tài)規(guī)劃問題來求解3.其后向算法的

5、遞推關系式為:DXi(xi)=0ixi(j)2pj1=mini+1ppi(i-2)+-(3)1-2jpj1+p1+p10DXX(xi+1-i)0xir,i=n,n-1,1n+1所以j11.取j1=j1-1,wi=i;ij1,則j1j1-1m(xn+1)=0minDX=m利用這個遞推關系即求得問題(3)的解DX1(r)所對應的最優(yōu)決策序列1,2,m就是問題(2)的解,從而得到最優(yōu)分配方案:ni=qi+i,i=1,2,m.如果最優(yōu)決策序列不唯一,則按2)、3)來選取合理的分配方案.由于非線性整數(shù)規(guī)劃問題(2)的特殊性,實際上有如下定理.ppi=1i(wi-i)wi=1i=n,wi0,且為整數(shù),i=

6、1,2,m由歸納假設,命題成立.由該定理,得到分配方案如下算法:1)計算:q3i=33i=qi-qi,i=q,qi=qi,p320武漢交通科技大學學報1999年第23卷1,2,m.m記r=i1,k=1r=1mDXDX21=pi=1pi(-pi2)p2)=p2)p計算ai=mpi=pm,i=1,2,mppi=1i(-pi2)設ajk=min,ai,則jkjk+11im3)如果k=r,則轉4),否則,ajkajk+pjki=1pi(-pi,k則mk+1,轉2)4)ni=qi+i,i=1,2,m.例2設有3個單位,各單位分別有103人、63人和34人,共分配21席位.問應如何分配?q1=10.815

7、,q2=6.615,q3=3.570r=2a1=-0.00612,a2=-0.00365,a3=-0.00412a1最小,所以1=1,a1a1+a3最小,所以3=1DX1-DX2=p-p(-i=1mzi)(pi-p)=zi=1ipi=pij-p(zi0zipii+zi0pizzj0i=-z,jj0i分配方案為:n1=11,n2=6,n3=4但是,該分配方案有缺點,不滿足合理性約束條件B.jDX1-DX202mn1,n2,nm為(4)的解.),2),3)所確定的各根據(jù)該定理,顯然由1單位分得的席位n1,n2,nm滿足合理性約束條件B,同時也給了其算法.例3用模型2來求解例2的問題.列表如下:mi

8、nDX=)1s.t.mi=1(-ppi2)p表1pi值表p3i=1ni=q(4)nip1p2ni0,ni為整數(shù),i=1,2,m),3)分別同2),3).2定理2用正奇數(shù)1,3,5,2k+1,分別除以各單位人數(shù)p1,p2,pm,將所得商從小到大排列,取前q個商,設為以pi為除數(shù)的最pi后一個商(若沒有,則規(guī)定ni=0)即pjpi,對任意的i,j,1i,jm.則:n1,n2,nmm為非線性整數(shù)規(guī)劃(4)的解.證明設yi0,yi為整數(shù),myi=1i=q,zi=根據(jù)模型2,有:n1=11,n2=6,n3=4.yi-ni,i=1,2,m,則z=i=1i0.第3期楊國武:席位的公平分配數(shù)學模型3213同時

9、滿足合理性約束條件A和B因為(i=1,2,m)是最小的q個商,所pi的數(shù)學模型計算:q3i=m(i=1,2,m)pipi中的較小的r個,從而n1,n2,nm為模型3的各以使i=1的相應的是33,q,qi=qi,i=qi-qi,ppi單位所分配得的席位.證畢.根據(jù)定理3,易知模型3的分配方案滿足合理性約束條件B.該方案已經(jīng)提供了算法,且當總席位q較小時,也可用與之等價的定理3的算法.pi個(若有相等者,取pi較小者,若分母相等,則協(xié)i=1r=,r1.i取(i=1,2,m)中較小的r商處理).則相應的ni=qi+1,其它的nj=qj,即得各單位的分配席位n1,n2,nm.由以上分配方法,顯然該分配

10、方案滿足合理性的約束條件A.定理3用正整數(shù)1,2,去除以各單位人數(shù)pi(i=1,2,m),從小到大排列,取前q個為以pi為分母后的最后一個商(若沒有,pi則規(guī)定ni=0)(i=1,2,m),則:n1,n2,nm為4模型的優(yōu)缺點本文給出了關于席位公平分配的三個數(shù)學模型,其優(yōu)點是:操作簡明(不需要用動態(tài)規(guī)劃來求解非線整數(shù)規(guī)劃問題),能適應總席位q較小的情況,有一定的合理性,第1,2個模型分別給出了滿足合理性約束條件A和B的方差最小分配方案,第3A和B的.商,設按模型3各單位所分配得的席位.證明記i=ni-qi,因為q=qi+i+pipi-=-0pippi0pipi所以qi=niqi+p所以=p參考文獻1姜啟源.數(shù)學模型,北京:高等教育出版社,199812934連:大連海事大學出版社,19971143馬振華,劉坤林,陸璇等.運籌學與最優(yōu)化理論卷.從而=pi+,i=0或1.ppi北京:清華大學出版社,19981254278Mathematicalmodelforfairallotm