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

公平的席位分配问题数学建模报告20094865，陈天送20094862，陈铁忠20094854，朱海公平的席位分配问题席位分配在社会活动中经常遇到，如：人大代表或职工学生代表的名额分配和其他物质资料的分配等通常分配结果的公平与否以每个代表席位所代表的人数相等或接近来衡量符号设定：N:总席位数n:分配给第i系席位数（°€1,2,3分别为甲，乙，丙系）P:总人数P:第i系数（°€1,2,3分别为甲，乙，丙系）Qi:第i系Q值（°€1,2,3分别为甲，乙，丙系）Z:目标函数方法一，比例分配法:即:某单位席位分配数=某单位总人数比例X总席位如果按上述公式参与分配的一些单位席位分配数出现小数,则先按席位分配数的整数分配席位,余下席位按所有参与席位分配单位中小数的大小依次分配之这种分配方法公平吗？由书上给出的案例，我们可以很清楚的知道该方法是有缺陷的，是不公平的方法二，Q值法冬采用相对标准，定义席位分配的相对不公平标准公式：若冬，厶nnpnnn则称———=卫九卩厂1为对A的相对不公平值，记为r（"],，若1„2则称“2"2代€上1—1为对B的相对不公平值，记为r（n,n）由nnn2ppnB12定义有对某方的不公平值越小，某方在席位分配中越有利，因此可以用使不公平值尽量小的分配方案来减少分配中的1不公平。

确定分配方案:P1P2使用不公平值的大小来确定分配方案，不妨设n1>n2，即对单位A不公平，再分配一个席位时，关于n1,n2的关系可能有P1P21. n1+1>n2，说明此一席给A后，对A还不公平；E1E1旦Pi2. nl+1佩+1,说明此一席给+1后,0对+还不公平,不公平值为B'p1P1-n2n]+1P1P23. n1>n2+1,说明此一席给B后，对A不公平，不公平值为Pl€P2n]ng，1P2-n1P2n2,1P1P24. n1

i这种分配方法很容易编程处理用Q值法解书上的案例如下，先按应分配的整数部分分配，余下的部分按Q值分配本问题的整数名额共分配了19席，具体为：甲10.815n=10乙6.615n=612丙3.570n=33对第20席的分配，计算Q值Q]=1032/(10…11)=96.45;Q2=632/(6…7)=94.5;Q3=342/(3…4)=96.33因为Q1最大，因此第20席应该给甲系；对第21席的分配，计算Q值Q1=1032/(11€12)=80.37;Q2=632/(6€7)=94.5;Q3=342/(3€4)=96.33因为Q3最大，因此第21席应该给丙系最后的席位分配为：甲11席乙6席丙4席方法三,d'Hondt法：系学生人数10个名额分配21分配甲100511乙6036丙4024总和2001020将所得商数从大到小取前10个(10为席位数)，在数字下标以横线，表中甲，乙，丙横线的数分别为5，3，2是3个系分配席位方法四，最小方差法:将甲，乙，丙各系的人数用正整数n=1,2,3,…相除，即一次随自然数列求商，将所得商数从小到大取前十个，分别统计各系入围个数，即是最终学生代表名额分配结果。

将甲，乙，丙各系的人数用正整数n=1,2,3,…相除，其商数如下表：系123456甲1005033.33252016.66乙603020151210丙402013.331086.66最小方差原则的资(席位)公平分配整数：PPminZ=,(——i)2Ni(11)n其中i为整数，i=1,2,…,m可以认为最小方差原则是希望各单位每个席位代表的人数差异不要太大，特别地应该与整个分配方案中平均每个席位所代表的人数P/N差异不要太大因而对模型(11)的约束条件做进一步的合理限制，构成模型:P€NP€Nii-巴为int(P)或int(P)+1,i=1,2,…,m(12)nnnnn即i只能取i和i+1其中之一，如此可以避免出现席位名额i过分偏离巴的不合理状况在模型中可将目标函数Z改写为PPPPPPZ=工（肓—Q2+工[（—r）2，（—Q2]NnNn+1NniiiPP令礼述片，寸PPPPNn+1iZ€工[（_i—）2，（_右）2]1Nn+1NniZZZ0是一常数，要求Z最小也就是求Zi最小,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法不能解决不公平的大小问题。