数学建模席位分配问题精品文稿.ppt

《数学建模席位分配问题精品文稿.ppt》由会员分享，可在线阅读，更多相关《数学建模席位分配问题精品文稿.ppt（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学建模席位分配问题第1页，本讲稿共18页2020个席位的分配结果个席位的分配结果系别系别系别系别人数人数人数人数所占比例所占比例所占比例所占比例分配方案分配方案分配方案分配方案席位数席位数席位数席位数甲甲100100100/200100/200(50/100)(50/100)20=1020=10乙乙606060/20060/200(30/100)(30/100)20=620=6丙丙40 40 40/20040/200(20/100)(20/100)20=420=4现丙系有现丙系有6名学生分别转到甲、乙系各名学生分别转到甲、乙系各3名。名。系别系别系别系别人数人数人数人数所占比例所占比例所占比

2、例所占比例分配方案分配方案分配方案分配方案席位数席位数席位数席位数甲甲103103103/200=51.5%103/200=51.5%51.5%51.5%20 20=10.3=10.3乙乙636363/200=31.5%63/200=31.5%31.5%31.5%20=6.320=6.3丙丙34 34 34/200=17.0%34/200=17.0%17.0%17.0%20=3.420=3.410641064现象现象1 1 丙系少了丙系少了6 6人，但席位仍为人，但席位仍为4 4个。个。(不公平！）不公平！）Halmiton(1790)先按整数分配再按余数较大者分配第2页，本讲稿共18页由于在

3、表决提案时可能出现由于在表决提案时可能出现1010：1010的平局，再设一个席位。的平局，再设一个席位。2121个席位的分配结果（个席位的分配结果（HalmitonHalmiton方法）方法）系别系别人数人数所占比例所占比例分配方案分配方案席位数席位数甲甲103103103/200=51.5%103/200=51.5%51.5%51.5%21 21=10.815=10.815乙乙636363/200=31.5%63/200=31.5%31.5%31.5%21=6.61521=6.615丙丙34 34 34/200=17.0%34/200=17.0%17.0%17.0%21=3.21=3.570

4、5701173现象现象2 2 总席位增加一席，丙系反而减少一席。（不公平！）总席位增加一席，丙系反而减少一席。（不公平！）惯例分配方法惯例分配方法（Halmiton方法）方法）：按比例分配完取整数的名按比例分配完取整数的名额后，剩下的名额按惯例分给小数部分较大者。额后，剩下的名额按惯例分给小数部分较大者。存在不公平现象（存在不公平现象（Alabama悖论），能否给出更公平的分配悖论），能否给出更公平的分配席位的方案？席位的方案？第3页，本讲稿共18页2 建模分析建模分析目标：建立公平的分配方案。目标：建立公平的分配方案。反映公平分配的数量指标可用每席位代表的人数来衡量反映公平分配的数量指标可用

5、每席位代表的人数来衡量。系别系别系别系别 人数人数人数人数 席位数席位数席位数席位数每席位代表的人数每席位代表的人数每席位代表的人数每席位代表的人数公平程度公平程度公平程度公平程度甲甲1031031010103/10=10.3103/10=10.3中中中中乙乙63636 663/6=10.563/6=10.5差差差差丙丙34 34 4 434/4=8.534/4=8.5好好好好系别系别系别系别人数人数人数人数席位数席位数席位数席位数每席位代表的人数每席位代表的人数每席位代表的人数每席位代表的人数甲甲甲甲1001001010100/10=10100/10=10乙乙乙乙60606 660/6=10

6、60/6=10丙丙丙丙40 40 4 440/4=1040/4=10第4页，本讲稿共18页系别系别系别系别人数人数人数人数席位数席位数席位数席位数每席位代表的人数每席位代表的人数每席位代表的人数每席位代表的人数公平程度公平程度公平程度公平程度甲甲1031031111103/11=9.36103/11=9.36中中中中乙乙63637 763/7=963/7=9好好好好丙丙34 34 3 334/3=11.3334/3=11.33差差差差一般地一般地，单位单位单位单位人数人数人数人数席位数席位数席位数席位数每席位代表的人数每席位代表的人数每席位代表的人数每席位代表的人数A AB B当当席位分配公平

7、席位分配公平第5页，本讲稿共18页但通常不一定相等，席位分配的不公平程度用以下标准来但通常不一定相等，席位分配的不公平程度用以下标准来判断。判断。此值越小分配越趋于公平，但这并不是一个好的衡量标准。此值越小分配越趋于公平，但这并不是一个好的衡量标准。单位单位单位单位人数人数人数人数p p席位数席位数席位数席位数n n每席位代每席位代每席位代每席位代表的人数表的人数表的人数表的人数绝对不公绝对不公绝对不公绝对不公平标准平标准平标准平标准A A1201201010121212-10=212-10=2B B10010010101010C C102010201010102102102-100=2102

8、-100=2D D100010001010100100C,D的不公平程度大为改善！的不公平程度大为改善！第6页，本讲稿共18页2 2）相对不公平相对不公平表示每个席位代表的人数，总人数一定时，此值表示每个席位代表的人数，总人数一定时，此值越大，代表的人数就越多，分配的席位就越少。越大，代表的人数就越多，分配的席位就越少。则则A A吃亏吃亏,或对或对A A是不公平的。是不公平的。定义定义“相对不公平度相对不公平度”对对A A的相对不公平值；的相对不公平值；对对B B的相对不公平值；的相对不公平值；第7页，本讲稿共18页建立了衡量分配不公平程度的数量指标建立了衡量分配不公平程度的数量指标制定席位分

9、配方案的原则是使它们的尽可能的小。制定席位分配方案的原则是使它们的尽可能的小。3 3 模型构成模型构成若若A A、B B两方已占有席位数为两方已占有席位数为用相对不公平值用相对不公平值讨论当席位增加讨论当席位增加1 1个时，个时，应该给应该给A A还是还是B B方。方。不失一般性不失一般性，有下面三种情形。有下面三种情形。第8页，本讲稿共18页情形情形1 1说明即使给说明即使给A A单位增加单位增加1 1席，仍对席，仍对A A 不公平，所增这一席必须给不公平，所增这一席必须给A A单位。单位。情形情形2 2说明当对说明当对A A不公平时，给不公平时，给A A单单位增加位增加1 1席，对席，对B

10、 B又不公平。又不公平。计算对计算对B B的相对不公平值的相对不公平值情形情形3 3说明当对说明当对A A不公平时，给不公平时，给B B单单位增加位增加1 1席，对席，对A A不公平。不公平。计算对计算对A A的相对不公平值的相对不公平值第9页，本讲稿共18页则这一席位给则这一席位给A A单位，否则给单位，否则给B B单位。单位。结论结论：当（当（*）成立时，增加的一个席位应分配给）成立时，增加的一个席位应分配给A A单位，反单位，反之，应分配给之，应分配给B B单位。单位。第10页，本讲稿共18页记记则增加的一个席位应分配给则增加的一个席位应分配给QQ值较大的一方。值较大的一方。这样的分配席

11、位的方法称为这样的分配席位的方法称为QQ值法值法。若若A A、B B两方已占有席位数为两方已占有席位数为第11页，本讲稿共18页4 4 推广推广 有有mm方方分配席位的情况分配席位的情况设设方人数为方人数为，已占有已占有个席位，个席位，当总席位增加当总席位增加1 1席时，计算席时，计算则则1 1席应分给席应分给QQ值最大的一方。值最大的一方。开始，即每方至少应得到开始，即每方至少应得到1 1席，席，（如果有一方（如果有一方1 1席也分不到，则把它排除在外。）席也分不到，则把它排除在外。）从从第12页，本讲稿共18页5 举例举例甲、乙、丙三系各有人数甲、乙、丙三系各有人数103103，6363，

12、3434，有，有2121个席个席位，如何分配？位，如何分配？按按Q值法：值法：第13页，本讲稿共18页甲甲1 1乙乙1 1丙丙1 1456789101112131415161718192021甲：11，乙：6，丙：4第14页，本讲稿共18页模型分析模型分析存在公平的分配方法么？存在公平的分配方法么？1）比例加惯例法（）比例加惯例法（H法）法）悖论悖论 2）Q值法值法存在不合理存在不合理 3）其它方法：）其它方法：Dhondt方法方法 理想化原则理想化原则不存在完全不存在完全“合理合理”的分配的分配方法方法第15页，本讲稿共18页练习系系系系人数人数人数人数P Pi i比例分配比例分配比例分配比

13、例分配参照惯例分配参照惯例分配参照惯例分配参照惯例分配QQ值法值法值法值法A A9215921592.1592.1592929292B B1591591.591.592 22 2C C1581581.581.582 22 2D D1571571.571.572 22 2E E1561561.561.561 11 1F F1551551.551.551 11 1总和总和总和总和 1000010000 100100100100100100第16页，本讲稿共18页dHondt方法方法有有k个单位，每单位的人数为个单位，每单位的人数为 pi，总席位数为，总席位数为n。做法：做法：用自然数用自然数1,2

14、,3,分别除以每单位的人数，从分别除以每单位的人数，从所得的数中由大到小取前所得的数中由大到小取前 n 个，（这个，（这n 个数个数来自各个单位人数用自然数相除的结果），来自各个单位人数用自然数相除的结果），这这n 个数中哪个单位有几个所分席位就为几个数中哪个单位有几个所分席位就为几个。个。第17页，本讲稿共18页/1/1/2/2/3/3/4/4/5/5/6/6/7/7/8/8/9/9/10/10A A103103 61.561.5 34.334.325.7525.7520.620.617.217.2 14.714.7 12.87512.875 11.411.4 10.310.3B B636331.531.5 212115.7515.7512.612.610.510.5 9 9C C3434171711.311.38.58.56.86.82121席席位位第18页，本讲稿共18页