数学建模结课论文选区划分

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

- 1 -

摘要

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

第一步：我们用堆栈中背包问题求解算法（Knap）找出所有符合以下要求的“候选选区”。

1、：不相邻的街区不能划分成一个选区； 2、：选区内总选民数应在30,000到100,000之间； 3、：某个街区选民数如果超过（包括）50,000，此街区可单独作为一个选区； 4、：街区10不能单独作为一个选区。

这样分别对这14个街区进行选区的划分，得到48种可能的“候选选区”。 第二步：我们继续运用堆栈的方法从第一步求得的“候选选区”中选出可行的划分方案，选择的条件是候选选区间的街区号不能重复，并且组合起来就是1到14的街区号，这样48个可能的“候选选区”经过筛选得到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的支持率不超过50％外，其它均满足要求，即Mevo在其它的选区中得到席位。

然后我们对模型进行了优化，利用图论的方法建立的街区的邻接矩阵，然后结合堆栈的方法重新来求解该问题，使得算法速度得到显著提高：如本来第一步中需要逐个判断街区是否相邻的，现在利用邻接矩阵我们可以直接找到相邻的街区然后再进行下一个条件判断。在第二步中我们用表上作业法进行优化，直接把相交的候选选区去掉然后进行下一个条件判断。优化起到了对数字进行筛选的作用，使得算法的效率得到显著提高，可以解决相对规模更大的问题。

由于相关的文献表明，不同的国家对选举制中的的“绝对多数”有不同的定义，因此我们设变量K，对于不同的国家，只要改变K的值，我们的k值模型都是可以实现的。

本文建模的过程中，每一步都尽量考虑实际情况，所以模型的实际应用性和扩展性很强。

关键词：席位；栈；背包算法（Knap）；“绝对多数”参数K；邻接矩阵；筛选；候选选区

- 2 -

一、问题重述

在—个遥远的国家，Sark Mevo 所领导的政党最终击败了Reguel Tekris王子领导的联合党派。Mevo希望巩固他在首都地区的席位。首都由14个街区组成，这些街区将分组为多个选区。下图是首都地区的示意图。在图中用数字1到14对这些街区进行了编号。每个街区中的另外两个数字是预计该街区会投票给Mevo的选民数和该街区的选民总数。所有选民都必须投票，且选举胜出方必须得到绝对多数选票。一个选区可以由多个相邻的街区组成，且选区内总选民数应在30,000到100,000之间。如果两个街区不相邻，例如12和13，则它们不能组成一个选区。如果某个街区选民人数不少于50,000，则允许此街区单独作为一个选区。但是由于Mevo本人就居住在街区10内，因此迫于舆论压力，他不能将这个街区单独作为一个选区。

请设计出一个将首都划分为5个选区的方案，以使Mevo得到的席位数最多。如果这样做有困难，可以尝试划分为6个选区。

二、 问题分析

2.1 选区总数的分析

问题1：为什么要划分选区？

我们可以从表1看出，Mevo在各个街区获得选票的概率是有很大悬殊的，在第5街区可以获得最高的选票率0.9，在第6街区获得最低的选票率0.225。同时各个街区的总选民数也是不同的。由于我们在假定中已经认为：各选区选出议员的人数与该选区的总选民数成正比，这样就有可能削弱Mevo获得绝大多数议员支持的可能性。

如果将各个相近的街区按照Mevo的意愿连接成大的选区，直观地有：某些对Mevo持强烈反对意见的街区（如6街区），在大的选区中的抵制作用将可能被完全清除，同时该街区仍然按照与总选民数成比例地选出支持Mevo的议员，在最终的抉择上，他们将站在Mevo的立场上，而不是按以前那样选出对Mevo持反对意见的议员。

所以，将相近街区合并成大的选区，有利于Mevo获得绝大多数的选票。建立选区对Mevo是有利的。

表1 各个街区选民的统计情况 街区数j 1 2 3 4 5 6 7 选民数R0(j) 投票给Mevo的选民数R1(j) Mevo获得的选票率 17500 30000 0.583333 15000 50000 0.3 14200 20000 0.71 42000 18000 9000 12000 70000 20000 40000 30000 0.6 0.9 0.225 0.4 - 3 -

街区数j 选民数R0(j) 投票给Mevo的选民数R1(j) 8 10000 30000 9 26000 40000 10 34000 60000 11 12 13 14 2500 27000 29000 15000 10000 60000 40000 40000 0.45 0.725 0.375 Mevo获得的选票率 0.333333 0.65 0.566667 0.25 如果不划分选区，Mevo获得的支持率为 ?0.5R0(j)(sign(j?114R1(j)?0.5)?1)?0.5185 （1） R0(j)其中，

R1(j)?1?0.5,Mevo获胜R1(j)? 0.5(sign( （2） ?0.5)?1)??R0(j)R0(j)?0else?如果按照?的比例（比如??0.2?）选举议员，首都的总选民数为

?R(j)?540,000，

0j?114那么Mevo获得的席位数为540000?。即是，在首都的总选民数一定的情况下，讨论席位数与总的支持率是等效的。另外，未划分选区时，Mevo的支持率已经达到0.5185。划分选区后，Mevo的支持率会大于这个数值吗？我们拭目以待。 问题2：划分多少个选区才合适？

既然，分区对Mevo有利，分多少个区才合适呢？从政治民主的角度来看，分的区不益过多；从另一个方面来看，要尽可能削弱反对力量，分区又不能过少。题目给出了相关的约束条件，我们做如下的定量分析。

首都的总选民数为

?R(j)?540000 （3）

0j?114题目认为，一个合理的分区方案应该满足：选区内总选民数应在30,000到100,000之间。那么，分区的总数n应该满足

??14??14????R(j)R(j)R(j)?0???0?????0????j?1?j?1j?1?,1??n?min??,14? 30,000??100,000?max???? （4）

n??100,000????30,000??????????????????所以，6?n?14，也即是说：最少的分区数是6。这样，我们将从6开始讨论分区方案。

142.2依据条件把14个街区划分为6个选区称为一个划分方案。

则在所有的划分方案中Mevo所获得的席位数有能是0，也有可能是6。 2.3最后我们所要做的就是在此基础上选择最优的方案 使得Mevo在首都所获得席位书最多。 我们将这个问题划分为三步来求解： 第一步:我们只考虑四个条件：

1、：不相邻的街区不能划分成一个选区； 2、：选区内总选民数应在30,000到100,000之间； 3、：某个街区选民数如果超过（包括）50,000，此街区可单独作为一个选区； 4、：街区10不能单独作为一个选区。

我们把满足以上四个条件的街区并到一个集合中，这样我们就把14个街区划分成了48种可能的“候选选区”。

第二步：在第一步这些候选选区中任选6个候选选区作为一个划分方案。选择的条件是这6个候选选区中的元素不能相交，，并且这6个候选选区中的元素并起来就是1到14的数。

- 4 -

第三步：在第二步的划分方案下选择最优方案。

对于题中所提到的“绝对多数选票”，并且这是一个发生在一个遥远国家的问题，不同的国家对于选举制中的“绝对多数”有不同的的定义。因此我们在解题的第三步中将对“绝大多数”设置一个判断参数k。k可以根据具体的情况取1/2或2/3等等。

三、 问题假设

1. 在每个街区的总人数上我们不考虑迁入、迁出、出生率、死亡率??对街区总人数的影

响，即每个街区的人数在短时间内没有变化。

2. 我们的划分都符合当地的选举法规，是合法的地划分。

3. 选区的划分最后都与行政区域、地理环境、自治区域等因素想协调。 4. 不存在弃权或一票多投的情况，所有选票都有效。

5. 在任一选区，Mevo 可以得到预计的选票数，即不出现临时更改投票决定的情况。

四、 模型的建立和求解

选举分区问题，可以抽象成经典的组合优化模型：划分子集问题，在本问题中即是将14个节点按照多个约束条件划分到6个集合中。

Mevo建立大的选区的目的就在于巩固他在首都地区的席位。这些席位来自那些支持他的选区议员，而这些议员的产生直接缘于在某选区支持Mevo的选民占多数。在某选区内，支持Mevo的选民占总选民的比例用ri表示，则

?xR(j)ij114ri?自然地，有

?xR(j)ij0j?1j?114 （5）

Mevo在i选区失败为了表述的简洁我们列写如下的布尔变量b来描述Mevo在第i选区的胜负情况

14??xR(j)?ij1???1Mevo在i选区胜出j?1 （7） bi?0.5?sign(14?0.5)?1??????0Mevo在i选区失败xR(j)?ij0??j?1??其中，xij为第j个街区被划分在第i个选区的示性变量，xij?{0,1}。xij?1表示j

被划入i选区；xij?0表示j未被划入i选区。即

?ri?0.5??ri?0.5Mevo在i选区胜出 （6）

?1第j街区被化入第i选区 （8） xij???0第j街区未被化入第i选区那么，第i选区的总选民数pi与每个街区的选民数之间的关系为

pi??xijR0(j) （9）

j?114 假设，各选区选出议员的人数与该选区的总选民数成正比，比例系数为?。Mevo只能够得到他获胜选区的议员的席位。总的来说，他获得的总席位为

- 5 -

14??xR(j)?ij1??6614j?1bipi???0.5?xijR0(j)?sign(14?0.5)?1? （10） ???i?1i?1j?1xR(j)?ij0??j?1?? 当然，Mevo希望获得最大的席位数，所以极大化目标为

14??xR(j)?ij1??614j?10.5?xijR0(j)?sign(14?0.5)?1? （11） ????i?1j?1xR(j)?ij0??j?1??max

4.11 模型的建立（对于问题第一部的求解）

对于第一步的划分我们只考虑四个条件： （1）选区是由相邻的街区组成的

（2）选区内总选民数应在30,000到100,000之间

（3）某个街区选民人数不少于50,000，则允许此街区单独作为一个选区 （4）街区10不能单独作为一个选区

我们用堆栈的方法把满足以上四个条件的街区并到一个候选选区中，这样我们就把14个街区划分成了48个候选选区。 4.12模型的求解

首先我们把每个街区的总人数存储在一个数组w中，以后街区就用街区的编号来代替。另外算法的实现时，使用一个堆栈s。

算法思想：从1号街区开始开始顺序的选择街区，如果满足以上四个条件，则将该街区的编号进栈；如果当前选取的街区不满足条件则不进栈，继续选择下一个街区。

如果尚未得到一个划分方法，又已街区可选，则说明上一个进栈的街区不合适，就将堆栈退出一个街区编号，就从退出的编号的下一个编号街区开始尝试进栈。

每求得一组解，就输出堆栈中的所有街区的编号（这些编号的街区就是满足我们以上四个条件的一个划分选区），然后再退出栈顶数据，从当前退出的编号的下一个编号街区开始尝试，直至堆栈为空（无退栈数据），且达到最大编号。 如现在有街区1，2，3

若1不能单独作为一个选区1进栈 满足条件输出{1}（街区1的总人数不少于5万） 1 2 若2不能单独作为一个选区2进栈 满足条件输出{1，2}（街区1，2相邻，

1 两街区总人数在三万和5万之间）

- 6 -

3 3不能单独作为一个选区3进栈 ， 满足条件输出{1，2，3}（街区1，2，3相邻，

2 两街区总人数在三万和5万之间） 1

若集合{1，2，3}不能作为一个选区2出栈，3进栈 满足条件输出{1，3}

3 1 若集合{1，3}不能作为一个选区1出栈， 满足条件输出{2,3}

3 2

每个街区进栈前都要判断是否能单独作为一个选区，若不能单独作为一个选区才能进栈。我们可以这样来理解。栈就像是一个背包，背包的体积是一定的，我们的选取选区的四个条件就是背包的体积。现在有体积不等的一定数量的物品，那么我们需要选择一些物品的组合，使得这些组合物品的体积和等于背包的体积。类似的现在我们有一些条件互异的14个街区，那么我们需要选择一些街区的组合，使得这些组合街区的条件满足选取选区的条件。那满足条件的街区组合就是一个可行的划分区域。

算法流程图

- 7 -

开始 T>=0和T>=0&&k= 0 /*判断是否满足约束条件③*/ 进栈 /*待判断街区号入栈*/ T-=w[k] /*T减去待判断街区人数*/ 判断1（） /*判断是否满足约束条件①判断2（） /*判断是否满足 约束条件④②⑤*/ 保存可行街区组合，并显示 K＋＋ 出栈 T增加 !(IsEmpty(S)&&k==n) - 8 - /* 最外层循环判断条件 */

结束 用程序算出的结果为：

集合编号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 1 1 1 1 1 2 2 2 2 3 3 3 3 4 4 5 5 5 5 5 5 6 6 6 6 街区编号 2 2 2 5 5 \\ 3 3 5 4 5 5 5 \\ 5 6 6 6 6 10 10 7 7 8 8 8 \\ 11 \\ 8 \\ 11 \\ 3 5 \\ 6 \\ \\ 5 \\ \\ \\ 6 10 \\ \\ \\ 7 8 11 - 9 -

26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 7 7 7 7 7 8 8 8 8 8 8 8 9 9 9 10 10 11 11 11 12 12 13 8 8 8 9 9 9 9 10 10 11 11 11 11 11 12 11 13 12 13 13 \\ 14 14 \\ 9 11 \\ 11 \\ 11 \\ 11 \\ 12 13 \\ 13 \\ \\ \\ \\ \\ 14 \\ \\ \\

如集合45里面所含的街区编号为{11，13，14}则表示这三个街区是相邻的，三个街区的人数总和为3万到10万。也就是满足第一步所要求的四个条件的一个可行的选区。

- 10 -

本文来源：https://www.bwwdw.com/article/msxt.html