5A版学生建模报告-席位分配

1、7A 版优质实用文档建模报告论文作者：雷杨，吴开强，李欧洲时间：20GG，5，77A 版优质实用文档7A 版优质实用文档席位分配- 伯努利实验解决方案摘要 ：本文围绕席位分配这一问题采用了伯努利实验， 采用了比较新型的方法和 细致的算法分析， 对分配过程中出现的种种情况都一一进行了分析， 并依此与其 它的现有方法比较。 我们认为该分配方案较简便且比较优越， 很大程度上符合公 平化原则关键词 ：伯努利实验公平化原则时间复杂度最大成功次数问题重述：某学校有 3 个系共 200 名学生，其中甲系 100 名，乙系 40 名。若学生代 表会议设 20 个席位，公平而又简单的席位分配方法是按学生人数的比

2、例分配， 显然甲乙丙三系分别应占有 10 ，6，4 个席位。现在丙系有 6 名学生转入甲乙两系， 各系人数如表第二列所示。 仍按比例分 配时出现了小数，在将取得整数的 19 席分配完毕后，三系同意剩下的 1 席参照 所谓惯例分配给比例中小数最大的丙系，于是三系仍分别占有 10，6，4 席。因为有 20 个席位的代表会议在表决提案时可能出现 10 ：10 的局面，会议 决定下一届增加 1 席。他们按照上述方法重新分配席位，计算结果见表。显然这个结果对丙系太不公平了，因为总席位增加 1 席，而丙系却由 4 席减为 3 席20 个席位分配21 个席位分配系别学生人数学生人数比例分配参照惯例比例分配参

3、照惯例的比例的席位的结果的席位的结果甲10351.510.31010.81511乙6331.56.366.6157丙3417.03.443.57037A 版优质实用文档27A 版优质实用文档总合200100.020.02021.0021理想化原则 ：m设第i方人数为 p i ,i=1,2, ,m,总人数 P pi ，待分配的席位为 N，i1记 q i Np i /P原则一 qi ni qi ，i=1 ，2， ，m,即ni必须取qi ，qi 二者之一。 原则二ni(N,pi, ,pm) ni(N 1,pi, , pm) ，i=1 ，2， ，m,即总席位增加时 ni 不应减少。二模型假设我们把甲乙

4、丙三系分配席位的这个事件看为要从有 20 个红签 180 个白签 (一共 200= 人数总和)的盒子里抽红签，对比抽得红签个数的概率大小来求得 分配的名额。三模型的建立与求解解决方案公式Xi B(ki,ni,pm,n) Ckniipm,nki(1 pm,n)ni ki i=1,2 ，,s(抽得红签ki个的概率) m 是分配名额n 是总人数ni 是第 i 组的人数ki 是红签的个数 s是小组的个数pm,n 是每人被抽到的概率由于抽签的伯努利原理，二项分布的极值点在 (ni 1)pm,n ,其中为向下取 整函数，抽红签的个数实际上就是最大的成功次数， 所以我们的分配方案取值从7A 版优质实用文档配

5、一个名额，由于T 的取值大于 m-s+1 所以分配完毕2.若 T=m 则第一次分配恰好满足3.若 T=m+1 则对 B(ki,ni,pm,n) 中最小的减 1，也分配完毕定理证明 ： m s 1 T m 1s已 知 T= ki k i = (ni 1)pm,n ( i1ki= (ni 1) pm,n 1( (ni 1)pm,n为整数时)，证明 1.先证不等式右边当 (ni 1)pm,n mpm,nsnii1不 为 整 数 时 )，ni i=1,2,3 s因k j (m)= (nj 1) smsni则k j(m) skj( nii11)= ni i(1nj 1) n1 i1 是关s 于 m 的单

6、增函数且 ( ni 1)(n j 1)i1ssmni 1i1k 1 (m)= 由于 0 1 ns1 1is1 ni1i11, 所以得出nik 1(m)= n1,同理i 1可得nni 1 n11n j 1 s1nii17A 版优质实用文档ki= (ni 1)pm,n (k i为整数时取为 k i-1)开始，首次计算出各个小组的 k i值，得出 ss第一次要分配的人数为 T= ki ，则剩下的人为 nki ,(m s 1 T m 1),i 1 i 1 我们会得出以下情况：1.若T0,(a 为有理数 )a=a+(a),0(a)1i 12snis= mi 1j1又因为m (n1 1)sni取值i T1

7、 m ssm(nij 1)i1 s ni im (nj 1)jm (n1 1)sm(i n1sni 1) m(n1 i 11n)im(nn1i 1)i 1sm(n ni j 1)si 1 ni mnssniim1 -s(01m (n2 1)snim (n2 1) m (ns 1)m(n2 1) isi 1mn(ins 1)i 1 ssni1m(ns 1)mi 1(n n2i 1)i1si1snii1m (ns 1)sni 1i) 1snii1snii1sni是整数，且值大于 m-s 所以最后的nis 1 ，i不1 等i 式左边也得证i 1当(ni 1)pm,n 为整数时， ki= (ni 1)

8、pm,n -1 ， skj ( ni 1)，证明仍成立 i1不等式右边 k j (m) s 1i 1 nis= mi 1t1 又因为t jm (n1 1)sni取值i T1 m smnssnisim1(nit 1)i1snii1m (n2 1)snim (ns 1)m(n2 1)i 1 nim(ns 1)m(i n1sni 1) m(n1 i 11n)i mi (1nn1i 1)im1(n ni2 1)i 1s i 1 snmi (nt 1)snii1s ni i 11m(ns 1)nini i11m-s(0 i 1ni i 11 )snii1m (ns 1)snininis 1 ，i不1 等

9、i 式左边仍成立i 1 i定理证明完毕是整数，且值大于m-s 所以最后的对分配方案的解释1. 第一次分配我们分配名额时， 让三个小组进行抽签， 一共有总人数个签， 其中有名额个7A 版优质实用文档7A 版优质实用文档红签，每组抽到几个红签就分配几个名额， 然而这个方案肯定有人反对， 因为有 可能有的组一个也抽不到， 所以我们给他们最有可能抽到的红签个数的名额。 这 个过程是伯努利实验， 伯努利实验是服从二项分布的。 这样大家心理都比较平衡。 2. 第二次分配由于第一次抽签有可能剩余，则原来各个小组被分到的人数就有可能加1 ，或保持不变。我们就比较多一个名额的概率的大小，因为，假设都加 1 的情

10、况 下，概率大的表示被抽到的机会大， 就该分配给这组。 所以第二次分配按概率大 小，人数依次加上 1 ，直到分配完毕。分配中的特殊情况：ki= （ni 1） pm,n 为整数时， Cni pm,nki（1 pm,n）ni ki在 ki和ki-1 同时达到最大，这 时应取 ki-1 ，因为成功的最可能次数最先是在 ki-1 次达到的。四模型的评价与算法分析1. 对于 Q 值方法，算法执行时间主要耗费在对 S个小组分别分配完 1 个之后， 用Q 值公式分配余下的 M-S 个人，时间复杂度为 O （M-S ）S）。2. 伯努利方法， 算法执行时间主要耗费在用取整函数对 S个小组分配，基于最 坏情况考

11、虑，只分配 M-S+1 个人之后，剩余 S-1 个人，用C knii p ki（1 p ）n k 求出各小组各分配一人的概率， 将 S-1 个人分别分配给概率前 S-1 个最大的 小组，用简单排序算法比较概率大小，最坏时间复杂度为O（SGS）3. d Hondt 方法，算法执行时间主要耗费在基于最坏情况考虑， 除数 N 取到 M ，则计算得商数表， 语句频度为 SGM ，比较商数大小，由于只需 SGM 个 中的前 M 个，考虑用堆排序方法，最坏时间复杂度为 O （SGM （ SGM）基于公平性原则的评价7A 版优质实用文档1 原则一在nini比原则一 qi i 1多一。 i 1mnjs）且 T

12、m 时会有偏差，会达到mnjs+2,ninii1i1或当m (nj 1)s不是整数，多一。nii1而 ms nj 是整数且 Tk 1 (m-1), 很容易证明， k 1 (m) 最多比 k1 (m-1) 大 1，则对若 k 1 (m)=k 1 (m-1)+1 ，则对 m 的时候他们的剩下和 m-1 一样，则分配结果也一样。否则 k 1 (m)=k 1 (m-1), ，剩下的则要判断下一个，分 配过程如上面的分析过程。同样对 m-k 来说，按照这种规定的同样进行，则分 配的结果一样最可得出每组的名额随 m 的增大不减。所以符合原则 原则一的合理性有待证明例子检验红签数 =21甲组 113乙组 6

13、4丙组 50丁组 23K=1K=21K=30.203909K=40.1536470.342277K=50.2234860.286268K=60.229602K=70.16786K=80.1458097A 版优质实用文档10117A 版优质实用文档K=90.176915K=100.175231K=110.142116结果9642总人数 =250Bernoulli 法Q值超几何分布甲 131101111乙 64666应分配人丙 50555是 24丁 23322总人数 =250Bernoulli 法Q值超几何分布应分配人甲9109是 21乙556 ( 64.G21/250 5.376 )丙444丁3

14、22六参考文献：1概率论高教出版社2数据结构西安电子科技大学出版社3Mathematica4 教程电子工业出版社 20GG.3七附录：关于原则一条件的合乎性证明：7A 版优质实用文档7A 版优质实用文档因为mnjm (n j 1)snij 1) 为整i 数1 时，我们知道这时极值首先取到 s 1= ms njsm -1s s s mninini mnj而 is 1 的值在(i 10，1 )i 1故jni 向下i 1取整是1.当 i m (nj 1)nim (nj 1) -1snii1m (n j 1)jsni-1 ，i 1向上取整是定不是整数。m (n j 1)二轮分到即达到 i mni (n

15、 j 1)2.当 m (snj 1) 不是s ni 此时我们i 的1 分配有 3.当 m(nj 1) 3.当 m(nj 1)ni =i 1nni isj i 1 =ii11nii 31.1 当 m(nj 1) i-11nj m)时(ns j 1) -1 nini足ni 原则i 1 i m(nj 1) -1snii1jm1 满s 足 -1 且 Tm 时，原则一不满足) 不是i 1整ni 数，而 ms nj 是整数且 Tm 时，nii1mnj会有 s j1也nii1八 Mathematics 程序 1StatisticsDiscreteDistributionss=BinomialDistribu

16、tion8,50./250;Fori=0,i8,i+,Print,i+1,CDFs,i+1-CDFs,iGraphicsMultipleListPlot7A 版优质实用文档12li0s.t225=TM0.u1l5tipleListPlotlist1,list2,list3,list4,Ticks180,.211e0.00.57,Hue0.9,PlotLabel2 3 4 5 6 9n 1=50 ，n 2=64 ，n 3=113 ，n 4=231418 21137A 版优质实用文档(list1P=mT,nablei,CnD1F5s0,i+1n2-C6D4F, sn,i3,1i1,03,2, 1n,14;2 3ablei,CDFss,i+1-CDFss,i,i,0,21,1;list3=Tablei,CDFsss,i+1-CD0.F2sss,i,i,0,21,