数学建模教案02选举.pdf

二二 选举问题选举问题 1 问题的提出问题的提出 代表委员会席位的公平分配是民主精神的体现 再更一般的情形下 代表委 员会是通过直接选举产生的 在参加选举的选民中 往往来自于不同的利益联盟 我们的选举办法如何较好地体现民主的精神 较好地保全本联盟的利益 设 p 选民总数 n 席位总数 A p 联盟 A 的选民数 A n 联盟 A 的席位数 1 多数选举法 每个选民最多投n票 对每个候选人只能投 1 票或 0 票 得票较多的个候 选人当选 n 问题 多数选举法是否能使各方得到与选民数相适应的席位数 例 1 81p 8n 41 A p 40 A p 候选人 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 1 b 2 b 3 b 得票数 41 41 41 41 4141414140 40 40 得n 8 A 0 A n 多数选举法的缺陷 选民超过半数的联盟可以操纵选举 少数人的利益得不 到确保 2 累积选举法累积选举法 对某个候选人可以投多票 甚至是分数票 但每个选民的投票总数不超过 得票较多的个候选人当选 n n 例2 81p 8n 41 A p 40 A p 问题 联盟A还能操纵选举吗 候选人 1 a 2 a 3 a 4 a 1 b 2 b 3 b 4 b 联盟 A 总票数8 41328 82 82 82 82 联盟A总票数84 0320 80 80 80 80 得 4 A n 4 A n 问题 联盟A可以得到更多席位吗 1 候选人 1 a 2 a 3 a 4 a 5 a 1 b 2 b 3 b 4 b A 总票数8 41328 65 65 66 66 66 A总票数8 4 0320 80 80 80 80 联盟A得不到5个席位 结论 选民数为结论 选民数为 A p的联盟 的联盟 A 获得获得 A pn p 席是可以确保的 席是可以确保的 x 不大于x的最大整数 3 联盟席位数的最大值联盟席位数的最大值 在例2中 联盟A可以得到4个席位 但不能得到5个席位 也就是说 4 是联盟A席位数的最大值 问题 能否获得比 A pn p 更多的席位呢 例3 81p 8n 46 A p 求 A n 46 8 4 544 81 A n 候选人 1 a 2 a 3 a 4 a 1 b 2 b 3 b 4 b A 总票数84 6368 92 92 92 92 A总票数8 3 5280 70 70 70 70 联盟A能否得到5个席位 候选人 1 a 2 a 3 a 4 a 5 a 1 b 2 b 3 b 4 b A 总票数84 6368 73 73 74 74 74 A总票数8 3 5280 70 70 70 70 A总票数8 3 5280 93 94 93 联盟A能得到5个席位 联盟A能否得到6个席位 不能 当时 联盟A不能得到5个席位 当 41 A p 46 A p 时 联盟A能得到5 个席位 但不能得到6个席位 2 例4 81p 8n 45 A p 求 A n 候选人 1 a 2 a 3 a 4 a 5 a 1 b 2 b 3 b 4 b A 总票数8 4 5360 72 72 72 72 72 A总票数8 3 6288 72 72 72 72 出现僵局 怎样确定联盟A最多能得到多少席 有例2和例3的分析可见 当联盟A取席时的席平均得票数大于非联盟 A取 1席时的席平均得票数 联盟A能得到席 即 A n n A n A n 当 1 A A AA ppnpn nnn 时 解得 1 A A pn n p A n的最大值是 1 max A A pn n p 说明 当 1 A A AA ppnpn nnn 时 1 A A pn n p 整数 可能会出现僵局 所以 1 max1 A A pn n p 例5 练习 求max 81p 8n A n 1 2 60 A p 55 A p 解 因为 60 9 6 666 81 55 9 6 1111 81 所以上述两种情况联盟A都可以最 多取得6席 4 最小联盟最小联盟 在例5中 和时 都取得6个席位 而后者的联盟比前者小 进一步的问题是 要取得6个席位 还存在更小的联盟吗 60 A p 55 A p 当时 54 A p 54 9 6 81 出现僵局 每个候选人72票 共9个候选人 55 A p 是6个席位的最小联盟的选民数 一般地 由于 1 A A pn n p 转化成 1 A A np p n 等号时会出现僵局 即 3 min 1 A A np p n 1 A np Z n 时会出现僵局 结论 min 1 1 A A np p n 因为 6 81 54 9 Z min55 A p 练习 分别求得确保席位数为1席 2席 3席 4席 5 席时的最小联盟选民数 8000p 5n 当时 1 2 3 4 5 A n 1 1 8000 11333 3311334 51 A p 2 2 8000 12