数学建模结课论文选区划分.docx
《数学建模结课论文选区划分.docx》由会员分享，可在线阅读，更多相关《数学建模结课论文选区划分.docx（48页珍藏版）》请在冰点文库上搜索。
数学建模结课论文选区划分
数学建模结课论文：
关于选举分区划分的问题
摘要
本文针对选举分区问题建立了相应的数学模型。
选举分区问题，可以抽象成经典的组合优化模型：
划分子集问题。
在巩固地区席位的背景上，对街区的划分进行了研究，我们首先提出了“绝对多数”的标准，设置了“绝对多数”参数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；邻接矩阵；筛选；候选选区
一、问题重述
在—个遥远的国家，SarkMevo所领导的政党最终击败了ReguelTekris王子领导的联合党派。
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各个街区选民的统计情况
街区数
1
2
3
4
5
6
7
选民数
17500
15000
14200
42000
18000
9000
12000
投票给Mevo的选民数
30000
50000
20000
70000
20000
40000
30000
Mevo获得的选票率
0.583333
0.3
0.71
0.6
0.9
0.225
0.4
街区数
8
9
10
11
12
13
14
选民数
10000
26000
34000
2500
27000
29000
15000
投票给Mevo的选民数
30000
40000
60000
10000
60000
40000
40000
Mevo获得的选票率
0.333333
0.65
0.566667
0.25
0.45
0.725
0.375
如果不划分选区，Mevo获得的支持率为
（1）
其中，
（2）
如果按照
的比例（比如
0.2‰）选举议员，首都的总选民数为
，那么Mevo获得的席位数为
。
即是，在首都的总选民数一定的情况下，讨论席位数与总的支持率是等效的。
另外，未划分选区时，Mevo的支持率已经达到0.5185。
划分选区后，Mevo的支持率会大于这个数值吗？
我们拭目以待。
问题2：
划分多少个选区才合适？
既然，分区对Mevo有利，分多少个区才合适呢？
从政治民主的角度来看，分的区不益过多；从另一个方面来看，要尽可能削弱反对力量，分区又不能过少。
题目给出了相关的约束条件，我们做如下的定量分析。
首都的总选民数为
（3）
题目认为，一个合理的分区方案应该满足：
选区内总选民数应在30,000到100,000之间。
那么，分区的总数
应该满足
（4）
所以，
，也即是说：
最少的分区数是6。
这样，我们将从6开始讨论分区方案。
2.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的数。
第三步：
在第二步的划分方案下选择最优方案。
对于题中所提到的“绝对多数选票”，并且这是一个发生在一个遥远国家的问题，不同的国家对于选举制中的“绝对多数”有不同的的定义。
因此我们在解题的第三步中将对“绝大多数”设置一个判断参数k。
k可以根据具体的情况取1/2或2/3等等。
三、问题假设
1.在每个街区的总人数上我们不考虑迁入、迁出、出生率、死亡率……对街区总人数的影响，即每个街区的人数在短时间内没有变化。
2.我们的划分都符合当地的选举法规，是合法的地划分。
3.选区的划分最后都与行政区域、地理环境、自治区域等因素想协调。
4.不存在弃权或一票多投的情况，所有选票都有效。
5.在任一选区，Mevo可以得到预计的选票数，即不出现临时更改投票决定的情况。
四、模型的建立和求解
选举分区问题，可以抽象成经典的组合优化模型：
划分子集问题，在本问题中即是将14个节点按照多个约束条件划分到6个集合中。
Mevo建立大的选区的目的就在于巩固他在首都地区的席位。
这些席位来自那些支持他的选区议员，而这些议员的产生直接缘于在某选区支持Mevo的选民占多数。
在某选区内，支持Mevo的选民占总选民的比例用
表示，则
（5）
自然地，有
（6）
为了表述的简洁我们列写如下的布尔变量
来描述Mevo在第i选区的胜负情况
（7）
其中，
为第j个街区被划分在第i个选区的示性变量，
。
表示j被划入i选区；
表示j未被划入i选区。
即
（8）
那么，第i选区的总选民数
与每个街区的选民数之间的关系为
（9）
假设，各选区选出议员的人数与该选区的总选民数成正比，比例系数为
。
Mevo只能够得到他获胜选区的议员的席位。
总的来说，他获得的总席位为
（10）
当然，Mevo希望获得最大的席位数，所以极大化目标为
（11）
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万）
若2不能单独作为一个选区2进栈满足条件输出{1，2}（街区1，2相邻，两街区总人数在三万和5万之间）
3不能单独作为一个选区3进栈，满足条件输出{1，2，3}（街区1，2，3相邻，两街区总人数在三万和5万之间）
若集合{1，2，3}不能作为一个选区2出栈，3进栈满足条件输出{1，3}
若集合{1，3}不能作为一个选区1出栈，满足条件输出{2,3}
每个街区进栈前都要判断是否能单独作为一个选区，若不能单独作为一个选区才能进栈。
我们可以这样来理解。
栈就像是一个背包，背包的体积是一定的，我们的选取选区的四个条件就是背包的体积。
现在有体积不等的一定数量的物品，那么我们需要选择一些物品的组合，使得这些组合物品的体积和等于背包的体积。
类似的现在我们有一些条件互异的14个街区，那么我们需要选择一些街区的组合，使得这些组合街区的条件满足选取选区的条件。
那满足条件的街区组合就是一个可行的划分区域。
算法流程图
用程序算出的结果为：
集合编号
街区编号
1
1
2
\
2
1
2
3
3
1
2
5
4
1
5
\
5
1
5
6
6
2
\
\
7
2
3
\
8
2
3
5
9
2
5
\
10
3
4
\
11
3
5
\
12
3
5
6
13
3
5
10
14
4
\
\
15
4
5
\
16
5
6
\
17
5
6
7
18
5
6
8
19
5
6
8
11
20
5
10
\
21
5
10
11
22
6
7
\
23
6
7
8
24
6
8
\
25
6
8
11
26
7
8
\
27
7
8
9
28
7
8
11
29
7
9
\
30
7
9
11
31
8
9
\
32
8
9
11
33
8
10
\
34
8
10
11
35
8
11
\
36
8
11
12
37
8
11
13
38
9
11
\
39
9
11
13
40
9
12
\
41
10
11
\
42
10
13
\
43
11
12
\
44
11
13
\
45
11
13
14
46
12
\
\
47
12
14
\
48
13
14
\
如集合45里面所含的街区编号为{11，13，14}则表示这三个街区是相邻的，三个街区的人数总和为3万到10万。
也就是满足第一步所要求的四个条件的一个可行的选区。
4．21模型建立（对于问题第二步的求解）
这一步我们所要达到的目的就是在第一步所求出的候选选区中选取6个。
选取的条件是这6个候选选区中的元素不能相交，，并且6个候选选区并起来里面的元素就是1到14的数。
4.22模型求解
在这一步我们也是使用了栈，并用一个1*14的矩阵P来辅助判断，如
我们先让第一个集合{1，2}进栈
则对应的矩阵P的第一列，第二列元素变为1
第二个集合进栈前我们先判断，如第二个集合是{1.5}，那么这时我们先看一下矩阵的第一列和第五列的元素是否为一，只要两者中有一个为一，则不进栈。
依次顺序选择候选选区，直到所选择的候选选区中的街区号对应矩阵P中相应的列元素都不为1时，则进栈。
如集合{5，7}，进栈，并改变矩阵p中相应的列元素。
然后再依次选择候选选区进栈，直至矩阵中所有元素都变成“1”。
则一个可行的划分区域已经找到，最后输出。
算法流程图
用程序算出最后的结果为：
方案序号
街区编号
方案序号
街区编号
方案序号
街区编号
1
1，11，18，33，43，47
13
2，15，18，34，40，47
25
2,16,24
39,43,47
2
1，11，18，34，40，47
14
2,15,18
34,41,46
26
2,16,24
41,42,48
3
1，11，18，35，41，46
15
2,15,18
35,41,48
27
2,16,25
31,43,47
4
1，11，18，35，41，48
16
2,15,19
31,43,47
28
2,16,26
30,43,47
5
1，11，19，31，43，47
17
2,15,20
30,43,47
29
3,11,23
33,43,47
6
1，11，20，30，43，47
18
2,15,21
24,40,47
30
3,11,23
34,40,47
7
1，11，21，24，40，47
19
2,15,21
24,41,46
31
3,11,23
34,41,46
8
1，11，21，24，41，46
20
2,15,22
24,41,48
32
3,11,23
35,41,48
9
1，11，22，24，21，48
21
2,16,23
33,43,47
33
3,11,24
39,43,47
10
1，14，15，24，40，47
22
2,16,23
34,40,47
34
3,11,24
41,42,48
11
1，14，15，24，41，46
23
2,16,23
34,41,46
35
3,11,25
31,43,47
12
2，15，18，33，43，47
24
2,16,23
35,41,48
36
3,11,26
30,43,47
如方案12表示一个可行的划分区域方案，方案12中包含集合：
2，15，18，33，43，47。
表示在第一步的结果的前提下可知这几个集合中所含的街区编号。
2{1，2，3}，15{4}，18{5，6，7}，33{8，9，11}，43{10，13}，47{12，14}。
可见这几个集合中所含的街区编号是没有交叉的，并且并起来里面所含的街区编号就是从1到14的数字。
4.31模型建立（第三步的求解）
第三步我们就是要在第二步可行的选区划分的方案中选取最优方案。
在第二步可行的选区划分方案中，Mevo获得席位有可能是最小值0，也有可能是最大值6.因此我们要在第二步的基础上选择最优的划分方案，使得Mevo获得席位数最多。
第三步模型解决的关键在于对题中所说的”绝对多数选票”的理解。
我们认为不同的国家在选举制中对“绝对多数”有不同的理解。
有的国家认为选举中所获的选票大于所有选票的1/2为胜，有的国家则认为所获的选票大于所有选票的2/3为胜。
题中所说的问题发生在一个遥远国家，因此对于“绝对多数”的理解具有不确定性。
因此我们设定变量k，k可以根据不同国家的不同情况取不同的值。
4.32模型的求解
在第二步所得的可行方案中我们可以编制一个程序，让可行方案中每个选区中投给Mevo的选民数和选民总数分别相加，然后在相除。
根据给定的k值判断Mevo能不能获得该选区的席位。
用此种方法分别对6个选区进行统计，最后得出在该方案下Mevo所获得席位总数。
或我们可以吧第二步的结果放到Excel表中，进行简单的加总则可以得出最后的结果。
五、结果分析
当k的取值为1/2时，Mevo所能获得的最多的席位书是5。
这时有一种可行的街区划分方案为{3，11，24，41，42，48}则对应的街区划分情况为：
{1，2，5}{3,4}{6，7，8}{9,12}{10,11}{13,14}
当k的取值为2/3，Mevo所能获得的最多的席位书是2。
这时有两种可行的划分方案.方案一为{2，16，24，39，43，47}则对应的街区划分情况为：
{1，2，3}{4，5}{6，7，8}{9,11}{10,13}{12,14}.方案二为{2，16，23，34，40，47}则对应的街区划分情况为：
{1，2，3}{4，5}{6，7}{8，10}{9，11，13}{12,14}
由结果可知，当“绝大多数”的k定义为1/2时，Mevo最多能获得5个席位。
这样的区域划分是有利于Mevo在首都地区执政地位的巩固的。
而当“绝大多数”的k定义为2/3时，Mevo在首都最多只能获得2个席位，这是不利于Mevo的执政地位的巩固的，因此此题取k为2/3来划分区域的概率是很小的。
六、模型的推广和评价
这个模型我们之所分三步来解决，就是为了推广这个模型。
就是当这个问题扩展到更大的范围.
如农民土地的划分，若某一个村子要将村子的土地承包给若干位承包人。
那么则要根据不同的承包人所愿意给承包费的多少，而对应给于承包商合适的土地。
如地图分块问题，如某一个跨国集团的董事长想要把他的企业扩张到全球的各个地方。
在进行市场攻略的时候他们不是以国家或城市为单位的。
为了节约经营成本和便于管理，他们会根据各个地方的不同特点将地图分为若干块，然后再在所分的快上设子公司……
其实只要涉及划分的问题，只要我们认真研读划分条件，然后在三步求解过程中分别改变相应的条件，最终则可以得出最优解。
由此也可以得知这个模型的最大有点就是易于扩展，依据具体的情况改变相应的选择条件则可以使用与很多种情况。
如当问题需要划分的区域是n（不同的题目有不同的n）时，我们只要在第二步的过程中据不同的n值设置n个栈即可。
因此此模型是具有很大的灵活性的。
其次这个模型简单易明，计算量很小，大部分都是用计算机来实现。
人们只要根据具体的情况改变相应的选择条件即可，具有很强的可行性。
这个模型的缺点是要根据具体的情况，对特定的划分条件改变时要在程序中人为的改变。
同时对于不同的情况，当要用此模型时都是要人为的在程序中输入数据的。
参考书目:
【1】韩大元，《外国宪法》，中国人名大学出版社，2005年9月第二版
【2】K.N.King，《C语言程序设计现代方法》，人民邮电出版社，2011年11月第2版
【3】王少波，孙夫雄，《数据结构教程》，清华大学出版社，2011年7月第一版
【4】王敬华，林萍，《C语言程序设计教程》，清华大学出版社，2011年7月第2版
附件
源代码：
#include
#include
//#include
#include
#include
typedefstruct
{
intpeople,vote,num;
}position;//选区的数据类型
structEtype
{
intnumble;
};//如果不重新定义一个类型会有问题
typedefstruct
{
Etype*element;
inttop;
intmaxsize;
}Stack;
typedefstructNode
{
intresult1[4];
Node*link;
}Node;//第一个问题结束得出的结果
typedefstruct
{
Node*first;
intlength;
}List1;
//函数声明
voidMenu_name（）;//作者信息
voidFunction1（Stack*S,position*w,List1*L1）;//第一个问题的解决
voidW（position*w）;//存入选区的信息
Stack*CreatStack（Stack*S,int&max）;//栈的相关操作函数
voidPush（Stack*S,Etypea）;
voidPop（Stack*S,Etype&x）;
boolIsEmpty（Stack*S）;
List1*CreatList（List1*L1）;//用于存放第一个问题解决后结果的链表
voidFunction2（Stack*S2,List1*L1,position*w,int
升级会员 