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

《公平席位分配问题建模作业》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、公平的席位分配问题——数学建模报告20094865，陈天送20094862，陈铁忠20094854，朱海公平的席位分配问题席位分配在社会活动中经常遇到，如：人大代表或职工学生代表的名额分配和其他物质资料的分配等。通常分配结果的公平与否以每个代表席位所代表的人数相等或接近来衡量。符号设定：：总席位数：分配给第系席位数（分别为甲，乙，丙系）：总人数：第系数（分别为甲，乙，丙系）：第系值（分别为甲，乙，丙系）：目标函数方法一，比例分配法：即：某单位席位分配数=某单位总人数比例´总席位如果按上述公式参与分配的一些单位席位分配数出现小数,则先按席位分配数的整数分配席位,余下席位按所有参与席位分配单位中小

2、数的大小依次分配之。这种分配方法公平吗？由书上给出的案例，我们可以很清楚的知道该方法是有缺陷的，是不公平的。方法二，Q值法：采用相对标准，定义席位分配的相对不公平标准公式：若则称为对A的相对不公平值，记为，若则称为对B的相对不公平值，记为由定义有对某方的不公平值越小，某方在席位分配中越有利，因此可以用使不公平值尽量小的分配方案来减少分配中的不公平。确定分配方案：使用不公平值的大小来确定分配方案，不妨设>，即对单位A不公平，再分配一个席位时，关于,的关系可能有1.       >,说明此一席给A后,对A还不公平;2.       <,说明此一席给A后,对B还不公平,不公平值为3.       >

3、,说明此一席给B后,对A不公平,不公平值为4.<,不可能上面的分配方法在第1和第3种情况可以确定新席位的分配，但在第2种情况时不好确定新席位的分配。用不公平值的公式来决定席位的分配，对于新的席位分配，若有则增加的一席应给A，反之应给B。对不等式rB(n1+1,n2)

4、即可）3．将席位分配给最大Q值Qi对应的第i组。这种分配方法很容易编程处理。用Q值法解书上的案例如下，先按应分配的整数部分分配，余下的部分按Q值分配。本问题的整数名额共分配了１９席，具体为：甲　　10.815n1=10乙6.615n2=6丙　　3.570n3=3对第２０席的分配，计算Q值Q1=1032/(10´11)=96.45;Q2=632/(6´7)=94.5;Q3=342/(3´4)=96.33因为Q1最大，因此第２０席应该给甲系;对第２１席的分配，计算Q值Q1=1032/(11´12)=80.37;Q2=632/(6´7)=94.5;Q3=342/(3´4)=96.33因为Q3最大，因

5、此第２1席应该给丙系最后的席位分配为：甲　１１席　　乙　　６席丙　　４席方法三，d’Hondt法：将甲，乙，丙各系的人数用正整数n=1，2，3，…相除，即一次随自然数列求商，将所得商数从小到大取前十个，分别统计各系入围个数，即是最终学生代表名额分配结果。将甲，乙，丙各系的人数用正整数n=1，2，3，…相除，其商数如下表：系123456甲1005033．33252016.66乙603020151210丙402013.331086.66将所得商数从大到小取前10个（10为席位数），在数字下标以横线，表中甲，乙，丙横线的数分别为5，3，2是3个系分配席位。系学生人数10个名额分配21分配甲10051

6、1乙6036丙4024总和20010 20方法四，最小方差法：最小方差原则的资（席位）公平分配整数：min                                 (11)其中 为整数，i=1,2,…,m可以认为最小方差原则是希望各单位每个席位代表的人数差异不要太大，特别地应该与整个分配方案中平均每个席位所代表的人数P/N差异不要太大。因而对模型(11)的约束条件做进一步的合理限制，构成模型:为()或()+1，i=1,2,…,m（12） 即只能取和+1其中之一，如此可以避免出现席位名额过分偏离的不合理状况。在模型中可将目标函数Z改写为     令         于是，是一常数，要求Z

7、最小也就是求最小，6.3模型求解系学生人数10个名额分配21个名额分配比例分配各方di值分配结果比例分配各方di值分配结果甲100569.44510.5-31.2111乙60328.7436.3-48.646丙40211.224.2-0.354总和20010102121席位分配模型中，按比例分配法存在较大缺陷，Q值法不能解决“分配资格”问题，D'Hondt法不能解决不公平的大小问题。最后一种则比较