公平席位分配问题.ppt

系名甲乙丙总数学生数1036334200学生人数比例103/20063/20034/:惯例席位分配方法为:比例分配出现小数时,先按整数分配席位,余下席位按小数的大小依次分配之为改变总席位为偶数出现表决平局现象,决定增加一席,总席位变为21个学生代表席位,还按惯例分配席位,有系名甲乙丙总数学生数1036334200学生人数比例103/20063/20034/,丙系却少一席的情况,说明按惯例分配席位的方法有缺陷,试建立更合理的分配席位方法模型构成:讨论由两个单位公平分配席位的情况,设单位人数席位数每席代表人数单位Ap1n1p1/n1单位Bp2n2p2/n2要公平,应该有p1/n1=p2/n2但一般不成立,若p1/n1>p2/n2,则单位A吃亏(对单位A不公平)p1/n1<p2/n2,则单位B吃亏(对单位B不公平)因此可以用P=|p1/n1-p2/n2|来衡量分配不公平程度,但此公式有不足之处(绝对数的特点),如:n1=n2=10,p1=120,p2=100,p=2n1=n2=10,p1=1020,p2=1000,p=2采用相对标准,对公式给予改进,定义席位分配的相对不公平标准公式:对某方的不公平值越小,对某方越有利,因此可以用使不公平值尽量小的分配方案减少分配中的不公平确定分配方案:(使用不公平值的大小来确定分配方案)不妨设p1/n1>p2/n2,即对单位A不公平,再分配一个席位时,关于pi/ni的不等式可能有用不公平值的公式来决定席位的分配,此时应该有若rB(n1+1,n2)<rA(n1,n2+1),增加的一席应给A,反之应给B,它们对应的不等式为故可以令于是增加的席位分配由Qi的最小值决定,它可以推广到一般情况,即n个组模型求解先按应分配的整数部分分配,余下的部分按Q值分配。本问题的整数名额共分配了19席,具体为甲 =10乙 =6丙 =3第20席的分配由Q值决定第21席的分配由Q值决定为最后的席位分配为:甲 11席乙 6席丙 4席注:若一开始就用Q值分配,以n1=n2=n3=1逐次增加一席,也可以得到同样的结果。该方法可以推广到一般情况。