数学建模席位分配问题PPT课件

1、2020个席位的分配结果个席位的分配结果现丙系有6名学生分别转到甲、乙系各3名。10641064现象现象1 1 丙系少了6 6人，但席位仍为4 4个。( (不公平！）Halmiton(1790)先按整数分配再按余数较大者分配第1页/共19页由于在表决提案时可能出现由于在表决提案时可能出现1010：1010的平局，再设一的平局，再设一个席位。个席位。2121个席位的分配结果（HalmitonHalmiton方法）1173现象现象2 2 总席位增加一席，丙系反而减少一席。（不公平！）惯例分配方法惯例分配方法（Halmiton方法） ：按比例分配完取整数的名额后，剩下的名额按惯例分给小数部分较大者。

2、存在不公平现象（Alabama悖论），能否给出更公平的分配席位的方案？第2页/共19页2 建模分析目标：建立公平的分配方案。目标：建立公平的分配方案。反映公平分配的数量指标可用每席位代表的人数来衡量反映公平分配的数量指标可用每席位代表的人数来衡量。第3页/共19页一般地一般地，1p2p1n2n11np22np当当2211npnp席位分配公平席位分配公平第4页/共19页但通常不一定相等，席位分配的不公平程度用以但通常不一定相等，席位分配的不公平程度用以下标准来判断。下标准来判断。准。称为“绝对不公平”标 ) 12211npnp此值越小分配越趋于公平，但这并不是一个好的衡量标准。此值越小分配越趋于

3、公平，但这并不是一个好的衡量标准。C,D的不公平程度大为改善！的不公平程度大为改善！第5页/共19页2 2） 相对不公平相对不公平np表示每个席位代表的人数，总人数一定时，表示每个席位代表的人数，总人数一定时，此值越大，代表的人数就越多，分配的席位此值越大，代表的人数就越多，分配的席位就越少。就越少。2211npnp则则A A吃亏吃亏, ,或对或对A A是不公平的。是不公平的。定义定义“相对不公平度相对不公平度”则称，若 2211npnp11221211( ,)Ap npnr n np n对对A A的相对不公平值；的相对不公平值；则称，若 2211npnp22111222( ,)Bpnp nr

4、 n npn对对B B的相对不公平值；的相对不公平值；第6页/共19页建立了衡量分配不公平程度的数量指标建立了衡量分配不公平程度的数量指标BArr ,制定席位分配方案的原则是使它们的尽可能的小。制定席位分配方案的原则是使它们的尽可能的小。3 3 模型构成模型构成若若A A、B B两方已占有席位数为两方已占有席位数为,21nn用相对不公平值讨论当席位增加讨论当席位增加1 1个时，个时，应该给应该给A A还是还是B B方。方。不失一般性不失一般性， 2211，若npnp有下面三种情形。有下面三种情形。第7页/共19页情形情形1 1 1 2211，npnp说明即使给说明即使给A A单位增加单位增加1

5、 1席，仍对席，仍对A A 不公平，所增这一席必须给不公平，所增这一席必须给A A单位。单位。情形情形2 2 1 2211，npnp说明当对说明当对A A不公平时，给不公平时，给A A单单位增加位增加1 1席，对席，对B B又不公平。又不公平。计算对计算对B B的相对不公平值的相对不公平值221112122221(1)(1,)1(1)Bpnpnp nr nnpnp n 情形情形3 3 1 2211，npnp说明当对说明当对A A不公平时，给不公平时，给B B单单位增加位增加1 1席，对席，对A A不公平。不公平。计算对计算对A A的相对不公平值的相对不公平值11222 1121112(1)(

6、,1)1(1)Ap npnp nr n np np n 第8页/共19页),1,(), 1(2121nnrnnrAB若则这一席位给则这一席位给A A单位，否则给单位，否则给B B单位。单位。121221(1,)1(1)Bp nr nnp n 211212( ,1)1(1)Ap nr n np n 122 12112(1)(1)p np np np n(*) ) 1() 1(11222212nnpnnp结论结论：当（当（* *）成立时，增加的一个席位应分配给）成立时，增加的一个席位应分配给A A单位，反之，应分配给单位，反之，应分配给B B单位。单位。),1,(), 1(2121nnrnnrAB

7、第9页/共19页记记21 ) 1(2, innpQiiii则增加的一个席位应分配给则增加的一个席位应分配给Q Q值较大的一方。值较大的一方。这样的分配席位的方法称为这样的分配席位的方法称为Q Q值法值法。若若A A、B B两方已占有席位数为两方已占有席位数为,21nn第10页/共19页4 4 推广推广 有有mm方方分配席位的情况分配席位的情况设设iA方人数为方人数为ip，已占有已占有in个席位，个席位，mi,2, 1当总席位增加当总席位增加1 1席时，计算席时，计算m, innpQiiii, 21 ) 1(2则则1 1席应分给席应分给QQ值最大的一方。值最大的一方。1in开始，即每方至少应得到

8、开始，即每方至少应得到1 1席，席，（如果有一方（如果有一方1 1席也分不到，则把它排除在外。）席也分不到，则把它排除在外。）从第11页/共19页5 举例甲、乙、丙三系各有人数甲、乙、丙三系各有人数103103，6363，3434，有，有2121个个席位，如何分配？席位，如何分配？按Q值法：3 , 21 ) 1(2, innpQiiii1, 1, 1321nnn785) 11 ( 134, 5 .9841) 11 ( 163 5304.5,) 11 ( 1103232221QQQ785) 11 ( 134, 5 .9841) 11 ( 1632 .7681) 12(2103232221QQQ第

9、12页/共19页785) 11 ( 1345 .661) 12(2632 .7681) 12(2103232221QQQ785) 11 ( 1345 .661) 12(2634 .888) 13(3103232221QQQ45678910111213141516 1718192021甲：11，乙：6，丙：4第13页/共19页模型分析存在公平的分配方法么？ 1）比例加惯例法（H法）悖论 2）Q值法存在不合理 3）其它方法：Dhondt方法 理想化原则不存在完全“合理”的分配方法第14页/共19页练习第15页/共19页dHondt方法方法有有k个单位，每单位的人数为个单位，每单位的人数为 pi ，总席位数为，总席位数为n。做法：做法：用自然数用自然数1,2,3,分别除以每单位的人数，分别除以每单位的人数，从所得的数中由大到小取前从所得的数中由大到小取前 n 个，（这个，（这n 个数来自各个单位人数用自然数相除个数来自各个单位人数用自然数相除的结果），这的结果），这n 个数中哪个单位有几个个数中哪