文档介绍：数学建模结课论文:关于选举分区划分的问题摘要本文针对选举分区问题建立了相应的数学模型。选举分区问题,可以抽象成经典的纽•合优化模型:划分子集问题。在巩固地区席位的背景上,对街区的划分进行了研究,我们首先提出了“绝対多数”的标准,设置了“绝对多数”参数K,以便适合各种不同的实际情况。首先,采取背包算法;然后,利用c语言程序设计,给出了所有可能选区的可能,同时计算出席位;最后选择席位最大的选区作为最优的选区划分,使Mevo得到最多席位。己知首都的总人数为540000,每个选区人数不能超过100000,显然不能分为5个选区,以下讨论分6个区的情况。第一步:我们用堆栈中背包问题求解算法(Kn&p)找出所有符合以下要求的“候选选区。1、 :不相邻的街区不能划分成一个选区;2、 :选区内总选民数应在30,000到100,000之间;3、 :某个街区选民数如果超过(包括)50,000,此街区可单独作为一个选区;4、 :街区10不能单独作为一•个选区。这样分别对这14个街区进行选区的划分,得到48种可能的“候选选区”。第二步:我们继续运用堆栈的方法从第一步求得的"候选选区”中选出可行的划分方案,选择的条件是候选选区间的街区号不能重复,并且组合起来就是1到14的街区号,这样48个可能的“候选选区”经过筛选得到36个可行的选区。接着对这36种情况,分别计算各个选区的选民对Mewo支持的情况,当所对应的选区Mewo得到的支持率超过50%:在第二步的划分方案下选择席位最大的选区作为最优的选区划分。这样,解这个模型就可以得到问题的结果为(:将14个街区分为6个选区,Mev。、2、5为一选区,3、4为一-选区,6、7、8为一选区,9、12为一选区,10、11为一选区,13、14为一选区。除了6、7、8作为一个选区时对Mev的支持率不超过50%外,其它均满足要求,BPMevo在其它的选区中得到席位。然后我们对模型进行了优化,利用图论的方法建立的街区的邻接矩阵,然后结合堆栈的方法重新来求解该问题,使得算法速度得到显著提高:如本来第一步中需要逐个判断街区是否相邻的,现在利用邻接矩阵我们可以直接找到相邻的街区然后再进行下一个条件判断口在第二步中我们用表上作业法进行优化,直接把相交的候选选区去掉然后进行下一个条件判断。优化起到了対数字进行筛选的作用,使得算法的效率得到显箸提高,可以解决和対规模更大的问题。山于相关的文献表明,不同的国家对选举制屮的的“绝对多数”有不同的定义,因此我们设变量K,对于不同的国家,只要改变K的值,我们的』模型都是可以实现的。本文建模的过程中,每一步都尽量考虑实际情况,所以模型的实际应用性和扩展性很强。关键词:席位;栈;背血算法(Kn“p);“绝对多数”参数K;邻接矩阵;筛选;候选选区一、问题重述在一个遥远的位。首都山14个街区纽成,这些街区将分纽为多个选区。下图是首都地区的示意图。在图中用数字1到14对这些街区进行了编号。每个街区屮的另外两个数字是预计该街区会投票给Mevo的选民数和该街区的选民总数。所有选民都必须投票,U选举胜出方必须得到绝对多数选票。一个选区可以山多个相邻的街区纽•成,且选区内总选民数应在30,000到100,000之间。如果两个街区不相邻,例如12和13,则它们不能组成一个选区。如果某个街区选民人数不少于50,000,则允许此街区单独作为一个选区。但是山于Mevo本人就居住在街区10内,因此迫于舆论压力,他不能将这个街区单独作为一个选区。请设计出一个将首都划分为5个选区的方案,以使Mevo得到的席位数最多。如果这样做有困难,可以尝试划分为6个选区。117500/3000069000/40000712000/30000215000/50000810000/30000926000/400001034000/60000112500/1000018000/200001227000/60000314200/200001329000/400001415000/40000442000/70000二、:为什么要划分选区?我们可以从表1看出,Mev。在各个街区获得选票的概率是有很大悬殊的,,。同时各个街区的总选民数也是不同的。山于我们在假定屮已经认为:乞选区选出议员的人数与该选区的总选民数成止比,这样就有可能削弱Mevo获得绝大多数议员支持的可能性。如果将各个相近的街区按照Mev。的意愿连接成大的选区,直观地有:某些对Mevo