席位的公平分配数学模型

1、第23卷第3期1999年6月武汉交通科技大学学报JournalofWuhanTransportationUniversityVol.23No.3June1999席位的公平分配数学模型杨国武(武汉交通科技大学基础课部武汉430063)摘要:对席位公平分配问题提出了两个合理性限制条件,给出了分别满足这两个条件的方差最小数学模型及解法和同时满足这两个条件的数学模型及解法.关键词:数学模型;方差;非线性整数规划;动态规划中图法分类号:O290引言席位公平分配问题是在若干单位中如何只根据各单位人数的多寡来分配总席位,使之尽可能合理、公平.也就是:设有m个单位A1,A2,Am,各有p1,2m然该单位是不会

2、认为该分配方案是合理的.文献2还给了一种化为非线性整数规划的分配方案,即寻求合理的n1,n2,nm使得:mminJ(n1,n2mi=1(-qi2)qi,pm个人,共p=i=1pi人,mni1,且为整数,i=1,2,m表,问怎样合理、,m个12,nm个,样求合理、公平的n1,n2,nm.为叙述方便,引入以下记号:33qi=q,qi=qi(即qi的整数部分),p3mn=ii=1q,怎如果不加约束条件ni=qi或qi+1,则文献2中所提供的解法是不正确的.这两种方案都是以每个单位分配的席位数ni为分母作相对或绝对不公平的比较.当总席位数.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为整数,i=1,2,mDX=piki(0-i)+2)当式(1)有2组以上解时,人

4、数pi较少的单位Ai优先.这样做的目的是为了减少相对不公平值.3)当有两个单位人数一样多,又只能再分配一个席位时,只能协商解决.模型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为整数,i=1,2,m-DX2=-pj1+p1p1-该问题可以化为动态规划问题来求解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)所对应的最优决策序列1,2,m就是问题(2)的解,从而得到最优分配方案:ni=qi+i,i=1,2,m.如果最优决策序列不唯一,则按2)、3)来选取合理的分配方案.由于非线性整数规划问题(2)的特殊性,实际上有如下定理.ppi=1i(wi-i)wi=1i=n,wi0,且为整数,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)所确定的各根据该定理,显然由1单位分得的席位n1,n2,nm满足合理性约束条件B,同时也给了其算法.例3用模型2来求解例2的问题.列表如下:mi

8、nDX=)1s.t.mi=1(-ppi2)p表1pi值表p3i=1ni=q(4)nip1p2ni0,ni为整数,i=1,2,m),3)分别同2),3).2定理2用正奇数1,3,5,2k+1,分别除以各单位人数p1,p2,pm,将所得商从小到大排列,取前q个商,设为以pi为除数的最pi后一个商(若没有,则规定ni=0)即pjpi,对任意的i,j,1i,jm.则:n1,n2,nmm为非线性整数规划(4)的解.证明设yi0,yi为整数,myi=1i=q,zi=根据模型2,有:n1=11,n2=6,n3=4.yi-ni,i=1,2,m,则z=i=1i0.第3期杨国武:席位的公平分配数学模型3213同时

9、满足合理性约束条件A和B因为(i=1,2,m)是最小的q个商,所pi的数学模型计算:q3i=m(i=1,2,m)pipi中的较小的r个,从而n1,n2,nm为模型3的各以使i=1的相应的是33,q,qi=qi,i=qi-qi,ppi单位所分配得的席位.证毕.根据定理3,易知模型3的分配方案满足合理性约束条件B.该方案已经提供了算法,且当总席位q较小时,也可用与之等价的定理3的算法.pi个(若有相等者,取pi较小者,若分母相等,则协i=1r=,r1.i取(i=1,2,m)中较小的r商处理).则相应的ni=qi+1,其它的nj=qj,即得各单位的分配席位n1,n2,nm.由以上分配方法,显然该分配

10、方案满足合理性的约束条件A.定理3用正整数1,2,去除以各单位人数pi(i=1,2,m),从小到大排列,取前q个为以pi为分母后的最后一个商(若没有,pi则规定ni=0)(i=1,2,m),则:n1,n2,nm为4模型的优缺点本文给出了关于席位公平分配的三个数学模型,其优点是:操作简明(不需要用动态规划来求解非线整数规划问题),能适应总席位q较小的情况,有一定的合理性,第1,2个模型分别给出了满足合理性约束条件A和B的方差最小分配方案,第3A和B的.商,设按模型3各单位所分配得的席位.证明记i=ni-qi,因为q=qi+i+pipi-=-0pippi0pipi所以qi=niqi+p所以=p参考文献1姜启源.数学模型,北京:高等教育出版社,199812934连:大连海事大学出版社,19971143马振华,刘坤林,陆璇等.运筹学与最优化理论卷.从而=pi+,i=0或1.ppi北京:清华大学出版社,19981254278Mathematicalmodelforfairallotm