公平的席位分配问题建模作业

1、公平的席位分配问题数学建模报告20094865,陈天送20094862,陈铁忠20094854,朱海公平的席位分配问题席位分配在社会活动中经常遇到，如：人大代表或职工学生代表的名额分配和其他物质资料的分配等。通常分配结果的公平与否以每个代表席位所代表的人数相等或接近来衡量。符号设定：N N:总席位数ni：分配给第 i i 系席位数（i=1, ,2, ,3分别为甲，乙，丙系）P：总人数P：第 i i 系数（i=1, ,2, ,3分别为甲，乙，丙系）Q：第 i i 系Q Q值（i i=123=123 分别为甲，乙，丙系）Z Z: :目标函数方法一，比例分配法：即：某单位席位分配数=某单位总人数比例

2、父总席位如果按上述公式参与分配的一些单位席位分配数出现小数，则先按席位分配数的整数分配席位， 余下席位按所有参与席位分配单位中小数的大小依次分配之。 这种分配方法公平吗？由书上给出的案例，我们可以很清楚的知道该方法是有缺陷的，是不公平的。方法二，册法:P2采用相对标准，定义席位分配的相对不公平标准公式：若nn,2为对 A 的相对不公平值，记为rA（n1,n2），若p2n1_1为对B的相对不公平值，记为山（代，必）由P1n2某方在席位分配中越有利，因此可以用使不公平值尽量小的分配方案来减少分配中的不公平。确定分配方案：P1P2使用不公平值也大/屋确定分配方案，不妨设n1n2,即对单位 A 不公平

3、，再分配一个席位时，关于n1,n2的关系可能有P1P21.n141n2,说明此一席给 A 后，对 A 还不公平；P1P2,P2pl2.n14n2+1,说明此一席给 B 后，对 A 不公平，不公平值为则称n1n2pP1n组1PiP2p2n2P2nn1贝n称=nn2n2p1定义有对某方的不公平值4小，P1P2n1n21(n21)P11rA(n1,n2=-1P1P24.n1n2刊，不可能上面的分配方法在第 1 和第 3 种情况可以确定新席位的分配，但在第 2 种情况时不好确定新席位的分配。用不公平值的公式来决定席位的分配，对于新的席位分配，若有“1,电)二17(5,%1)以得出对应不等式2Pl%(%

4、1)小1)QP2Qk(nk1)nk于是知道增加的席位分配可以由Q的最大值决定，且它可以推广到多个组的一般情况。用对多个组(m个组)的席位分配 Q 值法可以描述为:1.先计算每个组的Q值：Q,k=1,2,m2 .求出其中最大的Q值Q(若有多个最大值任选其中一个即可)3 .将席位分配给最大Q值Q对应白第i组。这种分配方法很容易编程处理。用 Q 值法解书上的案例如下，先按应分配的整数部分分配，余下的部分按Q值分配。本问题的整数名额共分配了19席，具体为:3.570对第2。席的分配，计算P2n21P2ni则增加的一席应给 A,反之应给 R 对不等式rB(ni+1,n2)rA(ni,n2+1)进行简单处

5、理，可2P2引入公式Q的最大值决定席位分配的方法称为Q值法。10.815n=10 乙 6.615n2=6n3=3222Q=103/(10 黑 11)=96.45;Q=63/(6 父 7)=94.5;Q=34/(3 黑 4)=96.33因为Q最大，因此第20席应该给甲系；对第21席的分配，计算Q值222Q=103/(11x12)=80.37;Q=63/(6x7)=94.5;Q3=34/(3x4)=96.33因为Q最大，因此第 21 席应该给丙系最后的席位分配为：甲11席乙6席丙4席方法三，dHondt法:将 甲 ， 乙 ， 丙 各 系 的 人 数 用 正 整 数 n = 1 , 2 , 3 ,

6、, 相 除 ， 即 一 次 随 自 然 数 列 求 商 ， 将所得商数从小到大取前十个，分别统计各系入围个数，即是最终学生代表名额分配结果。将甲，乙，丙各系的人数用正整数 n=1,2,3,相除，其商数如下表：系123456甲1005033.33252016.66乙603020151210丙402013.331086.66将所得商数从大到小取前 10 个(10 为席位数)， 在数字下标以横线， 表中甲， 乙， 丙横线的数分别为 5,3,2是 3 个系分配席位。系学生人数10 个名额分配21 分配甲100511乙6036丙4024总和2001020方法四，最小方差法:最小方差原则的资(席位)公平分

7、配整数：Z=Y马2%NminNni1(11)其中ni为整数，i=1,2,m可以认为最小方差原则是希望各单位每个席位代表的人数差异不要太大，特别地应该与整个分配方案中平均每个席位所代表的人数 P/N 差异不要太大。因而对模型(11)的约束条件做进一步的合理限制，构成模型：PMNPPMNP 父 N Nni为 intint(P P)或 intint(P P)+1,i=1,2,m(12)即ni只能取ni和ni+1 其中之一，如此可以避免出现席位名额ni过分偏离ni的不合理状况。在模型中可将目标函数 Z 改写为ZY-PP乙=（二一二1Nni1是Z=Z。+乙，Z。是一常数，要求 Z 最小也就是求乙最小,6.3 模型求解系学生人数10 个名额分配21 个名额分配比例分配各方 di 值分配结果比例分配各方 di 值分配结果甲100569.44510.5-31.2111乙60