数学建模结课论文关于选举分区划分的问题

《数学建模结课论文关于选举分区划分的问题》由会员分享，可在线阅读，更多相关《数学建模结课论文关于选举分区划分的问题（30页珍藏版）》请在金锄头文库上搜索。

1、- 1 - 数学建模结课论文：数学建模结课论文：关于选举分区划分的问题关于选举分区划分的问题- 2 - 摘要摘要本文针对选举分区问题建立了相应的数学模型。选举分区问题，可以抽象成经典的组 合优化模型：划分子集问题。在巩固地区席位的背景上，对街区的划分进行了研究，我们 首先提出了“绝对多数”的标准，设置了“绝对多数”参数 K，以便适合各种不同的实际 情况。首先，采取背包算法；然后，利用 c 语言程序设计，给出了所有可能选区的可能， 同时计算出席位；最后选择席位最大的选区作为最优的选区划分，使 Mevo 得到最多席位。已知首都的总人数为 ，每个选区人数不能超过 ，显然不能分为 5 个选区，以下讨论

2、 分 6 个区的情况。第一步：我们用堆栈中背包问题求解算法（Knap）找出所有符合以下要求的“候选选 区” 。 1、：不相邻的街区不能划分成一个选区； 2、：选区内总选民数应在 30,000 到 100,000 之间； 3、：某个街区选民数如果超过（包括）50,000，此街区可单独作为一个选区； 4、：街区 10 不能单独作为一个选区。 这样分别对这 14 个街区进行选区的划分，得到 48 种可能的“候选选区” 。 第二步：我们继续运用堆栈的方法从第一步求得的“候选选区”中选出可行的划分方 案，选择的条件是候选选区间的街区号不能重复，并且组合起来就是 1 到 14 的街区号，这 样 48 个可

3、能的“候选选区”经过筛选得到 36 个可行的选区。接着对这 36 种情况，分别计 算各个选区的选民对 Mewo 支持的情况，当 所对应的选区 Mewo 得到的支持率超过 50时 就表明 Mewo 获得该选区席位. 第三步：在第二步的划分方案下选择席位最大的选区作为最优的选区划分。这样，解 这个模型就可以得到问题的结果为（当 k 值设置为 0.5 时）：将 14 个街区分为 6 个选区， Mevo 得到的席位是 5.具体划分为 1、2、5 为一选区，3、4 为一选区，6、7、8 为一选区， 9、12 为一选区，10、11 为一选区，13、14 为一选区。除了 6、7、8 作为一个选区时对 Mev

4、 的支持率不超过 50外，其它均满足要求，即 Mevo 在其它的选区中得到席位。然后我们对模型进行了优化，利用图论的方法建立的街区的邻接矩阵，然后结合堆栈 的方法重新来求解该问题，使得算法速度得到显著提高：如本来第一步中需要逐个判断街 区是否相邻的，现在利用邻接矩阵我们可以直接找到相邻的街区然后再进行下一个条件判 断。在第二步中我们用表上作业法进行优化，直接把相交的候选选区去掉然后进行下一个 条件判断。优化起到了对数字进行筛选的作用，使得算法的效率得到显著提高，可以解决 相对规模更大的问题。 由于相关的文献表明，不同的国家对选举制中的的“绝对多数”有不同的定义，因此 我们设变量 K，对于不同的

5、国家，只要改变 K 的值，我们的 k 值模型都是可以实现的。 本文建模的过程中，每一步都尽量考虑实际情况，所以模型的实际应用性和扩展性很 强。关键词：席位；栈；背包算法（Knap） ；“绝对多数”参数 K；邻接矩阵；筛选；候选选区- 3 - 一、问题重述问题重述在个遥远的国家，Sark Mevo 所领导的政党最终击败了 Reguel Tekris 王子领导的 联合党派。Mevo 希望巩固他在首都地区的席位。首都由 14 个街区组成，这些街区将分组 为多个选区。下图是首都地区的示意图。在图中用数字 1 到 14 对这些街区进行了编号。每 个街区中的另外两个数字是预计该街区会投票给 Mevo 的选

6、民数和该街区的选民总数。所有 选民都必须投票，且选举胜出方必须得到绝对多数选票。一个选区可以由多个相邻的街区 组成，且选区内总选民数应在 30,000 到 100,000 之间。如果两个街区不相邻，例如 12 和 13，则它们不能组成一个选区。如果某个街区选民人数不少于 50,000，则允许此街区单独 作为一个选区。但是由于 Mevo 本人就居住在街区 10 内，因此迫于舆论压力，他不能将这 个街区单独作为一个选区。请设计出一个将首都划分为 5 个选区的方案，以使 Mevo 得到的席位数最多。如果这样 做有困难，可以尝试划分为 6 个选区。二、二、问题分析问题分析2.12.1 选区总数的分析选

7、区总数的分析 问题问题 1 1：为什么要划分选区？：为什么要划分选区？ 我们可以从表 1 看出，Mevo 在各个街区获得选票的概率是有很大悬殊的，在第 5 街区 可以获得最高的选票率 0.9，在第 6 街区获得最低的选票率 0.225。同时各个街区的总选民 数也是不同的。由于我们在假定中已经认为：各选区选出议员的人数与该选区的总选民数 成正比，这样就有可能削弱 Mevo 获得绝大多数议员支持的可能性。 如果将各个相近的街区按照 Mevo 的意愿连接成大的选区，直观地有：某些对 Mevo 持 强烈反对意见的街区（如 6 街区） ，在大的选区中的抵制作用将可能被完全清除，同时该街 区仍然按照与总选

8、民数成比例地选出支持 Mevo 的议员，在最终的抉择上，他们将站在 Mevo 的立场上，而不是按以前那样选出对 Mevo 持反对意见的议员。 所以，将相近街区合并成大的选区，有利于 Mevo 获得绝大多数的选票。建立选区对 Mevo 是有利的。 表表 1 1 各个街区选民的统计情况各个街区选民的统计情况 街区数j1234567选民数0( )Rj1750015000142004200018000900012000投票给 Mevo 的选民数1( )Rj30000500002000070000200004000030000- 4 - Mevo 获得的选票率0.0.30.710.60.90.2250.

9、4 街区数j891011121314选民数0( )Rj1000026000340002500270002900015000投票给 Mevo 的选民数1( )Rj30000400006000010000600004000040000 Mevo 获得的选票率0.0.650.0.250.450.7250.375 如果不划分选区，Mevo 获得的支持率为（1）14 1 0 10( )0.5( )(0.5) 1)0.5185( )jRjRj signRj其中，（2）1 1 0 0( )10.5,( )( )0.5(0.5) 1)( )0RjMevoRjRjsignRjelse 获胜如果按照的比例（比如0

10、.2）选举议员，首都的总选民数为，140 1( )540,000jRj那么 Mevo 获得的席位数为。即是，在首都的总选民数一定的情况下，讨论席位540000 数与总的支持率是等效的。另外，未划分选区时，Mevo 的支持率已经达到 0.5185。划分选 区后，Mevo 的支持率会大于这个数值吗？我们拭目以待。 问题问题 2 2：划分多少个选区才合适？：划分多少个选区才合适？ 既然，分区对 Mevo 有利，分多少个区才合适呢？从政治民主的角度来看，分的区不 益过多；从另一个方面来看，要尽可能削弱反对力量，分区又不能过少。题目给出了相关 的约束条件，我们做如下的定量分析。 首都的总选民数为（3）1

11、40 1( )540000jRj题目认为，一个合理的分区方案应该满足：选区内总选民数应在 30,000 到 100,000 之 间。那么，分区的总数应该满足n141414000 111( )( )( ) 30,000100,000max,1min,14100,00030,000jjjRjRjRj nn （4） 所以，也即是说：最少的分区数是 6。这样，我们将从 6 开始讨论分区方案。614n 2.22.2 依据条件把依据条件把 1414 个街区划分为个街区划分为 6 6 个选区称为一个划分方案。个选区称为一个划分方案。 则在所有的划分方案中 Mevo 所获得的席位数有能是 0，也有可能是 6。

12、 2.32.3 最后我们所要做的就是在此基础上选择最优的方案最后我们所要做的就是在此基础上选择最优的方案 使得 Mevo 在首都所获得席位书最多。 我们将这个问题划分为三步来求解：我们将这个问题划分为三步来求解： 第一步:我们只考虑四个条件： 1、：不相邻的街区不能划分成一个选区； 2、：选区内总选民数应在 30,000 到 100,000 之间； 3、：某个街区选民数如果超过（包括）50,000，此街区可单独作为一个选区； 4、：街区 10 不能单独作为一个选区。 我们把满足以上四个条件的街区并到一个集合中，这样我们就把 14 个街区划分成了 48 种可能的“候选选区” 。- 5 - 第二步

13、：在第一步这些候选选区中任选 6 个候选选区作为一个划分方案。选择的条件是这 6 个候选选区中的元素不能相交， ，并且这 6 个候选选区中的元素并起来就是 1 到 14 的数。第三步：在第二步的划分方案下选择最优方案。 对于题中所提到的“绝对多数选票” ，并且这是一个发生在一个遥远国家的问题，不同 的国家对于选举制中的“绝对多数”有不同的的定义。因此我们在解题的第三步中将对 “绝大多数”设置一个判断参数 k。k 可以根据具体的情况取 1/2 或 2/3 等等。三、问题假设问题假设1. 在每个街区的总人数上我们不考虑迁入、迁出、出生率、死亡率对街区总人数的 影响，即每个街区的人数在短时间内没有变

14、化。 2. 我们的划分都符合当地的选举法规，是合法的地划分。 3. 选区的划分最后都与行政区域、地理环境、自治区域等因素想协调。 4. 不存在弃权或一票多投的情况，所有选票都有效。 5. 在任一选区，Mevo 可以得到预计的选票数，即不出现临时更改投票决定的情况。 四、模型的建立和求解模型的建立和求解选举分区问题，可以抽象成经典的组合优化模型：划分子集问题，在本问题中即是将 14 个节点按照多个约束条件划分到 6 个集合中。 Mevo 建立大的选区的目的就在于巩固他在首都地区的席位。这些席位来自那些支持他 的选区议员，而这些议员的产生直接缘于在某选区支持 Mevo 的选民占多数。在某选区内， 支持 Mevo 的选民占总选民的比例用表示，则ir（5）141 1 140 1( )( )ij j iij jx Rj r x Rj自然地，有（6）0.50.5iirMevoirMevoi 在选区胜出在选区失败为了表述的简洁我们列写如下的布尔变量来描述 Mevo 在第 i 选区的胜负情况b（7）141 1 140 1( )10.5(0.5) 10( )ij j iij jx RjMevoibsignMevoix Rj 在选区胜出在选区失败其中，为第 j 个街区被划分在第 i 个选区的示性变量，。表示 jijx0,1ijx 1ijx 被划入 i 选区；表示 j 未被划入 i