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

公平的席位分配问题数学建模报告20094865，陈天送20094862，陈铁忠20094854， 朱海公平的席位分配问题席位分配在社会活动中经常遇到，如：人大代表或职工学生代表的名额分配和其他物质资料的分配等。通常分配结果的公平与否以每个代表席位所代表的人数相等或接近来衡量。符号设定：总席位数 ：分配给第系席位数 （分别为甲，乙，丙系）：总人数 ：第系数 （分别为甲，乙，丙系）：第系值 （分别为甲，乙，丙系）：目标函数 方法一，比例分配法：即： 某单位席位分配数 = 某单位总人数比例总席位 如果按上述公式参与分配的一些单位席位分配数出现小数,则先按席位分配数的整数分配席位,余下席位按所有参与席位分配单位中小数的大小依次分配之。这种分配方法公平吗？由书上给出的案例，我们可以很清楚的知道该方法是有缺陷的，是不公平的。方法二，Q值法： 采用相对标准，定义席位分配的相对不公平标准公式：若 则称 为对A的相对不公平值， 记为 ，若 则称 为对B的相对不公平值 ，记为 由定义有对某方的不公平值越小，某方在席位分配中越有利，因此可以用使不公平值尽量小的分配方案来减少分配中的不公平。确定分配方案：使用不公平值的大小来确定分配方案，不妨设，即对单位A不公平，再分配一个席位时，关于,的关系可能有 1. ,说明此一席给A后,对A还不公平;2. ,说明此一席给B后,对A不公平,不公平值为4. ,不可能 上面的分配方法在第1和第3种情况可以确定新席位的分配，但在第2种情况时不好确定新席位的分配。用不公平值的公式来决定席位的分配，对于新的席位分配，若有则增加的一席应给A ，反之应给B。对不等式 rB(n1+1,n2)rA (n1,n2+1)进行简单处理，可以得出对应不等式引入公式 于是知道增加的席位分配可以由Qk的最大值决定，且它可以推广到多个组的一般情况。用Qk的最大值决定席位分配的方法称为Q值法。对多个组（m个组）的席位分配Q值法可以描述为： 1先计算每个组的Q值：Qk , k=1,2,m 2求出其中最大的Q值Qi（若有多个最大值任选其中一个即可） 3将席位分配给最大Q值Qi对应的第i组。这种分配方法很容易编程处理。用Q值法解书上的案例如下，先按应分配的整数部分分配，余下的部分按Q值分配。 本问题的整数名额共分配了席，具体为： 甲 10.815 n1 =10 乙 6.615 n2 =6 丙 3.570 n3 =3对第席的分配，计算Q值Q1=1032/(1011) = 96.45 ; Q2=632/(67)= 94.5; Q3 =342/(34)=96.33因为Q1最大，因此第席应该给甲系; 对第席的分配，计算Q值Q1=1032/(1112)=80.37 ; Q2 =632/(67)=94.5; Q3 =342/(34)=96.33因为Q3最大，因此第1席应该给丙系最后的席位分配为：甲席乙席 丙席方法三，dHondt法：将甲，乙，丙各系的人数用正整数n=1，2，3，相除，即一次随自然数列求商，将所得商数从小到大取前十个，分别统计各系入围个数，即是最终学生代表名额分配结果。 将甲，乙，丙各系的人数用正整数n=1，2，3，相除，其商数如下表：系123456甲100503333252016.66乙603020151210丙402013.331086.66将所得商数从大到小取前10个（10为席位数），在数字下标以横线，表中甲，乙，丙横线的数分别为5，3，2是3个系分配席位。系学生人数10个名额分配21分配甲100511乙6036丙4024总和2001020方法四，最小方差法：最小方差原则的资（席位）公平分配整数： min (11)其中为整数，i=1,2,m 可以认为最小方差原则是希望各单位每个席位代表的人数差异不要太大，特别地应该与整个分配方案中平均每个席位所代表的人数P/N差异不要太大。因而对模型(11)的约束条件做进一步的合理限制，构成模型: 为 ()或 ()+1，i=1,2,m （12）即只能取和+1其中之一，如此可以避免出现席位名额过分偏离的不合理状况。在模型中可将目标函数Z改写为 令 于是，是一常数，要求Z最小也就是求最小， 6.3 模型求解 系学生人数10个名额分配21个名额分配比例分配各方di值分配结果比例分配各方di值分配结果甲100569.44510.5-31.2111乙60328.7436.3-48.646丙4