最优选区划分方案.docx

最优选区划分方案.docx最优选区划分方案选区划分问题是人类社会牛活半屮相当普遍的一-类资源分配问题,处理这类问题的关键是建立正确的数学模型描述各个小集体的资源不公平度及其变化。本文在分析整理相关数据和信息资料的基础丄,建立了3个最优选区划分模型。在本文屮,我们根据鸽巢原理确定出首都地区允许划分的最小选区数为6。当考虑选区内街区两•两相邻时,以获得席位数为H标,我们建立了一•个0・1整数规划模型14maxZlZUjS—ESr7=16工/=!1,s1+1时,30,000<Y时><-XJb2Alw工/-II4X/-I时<ooo9o<-运用DNGO软件得到最多席位数Z.=5,最优选区的街区划分方案:M=[(1,2,5),(3,4),(6,7,8),(9,⑵,(10,11),(13,14)],相应选区的得票率:/?=[%,%,31%,53%,%,55%];为使政党获得的席位数具有稳定性,我们对H标函数屮的幺值进行了调整。当考虑选区内街区不必两两相邻,只要能合成一块吋,我们首先建立了一个启发式算法搜索模型,然后用编程求出所有满足条件的选区划分组合,最后从这些组合屮选出能连成一块且席位数最多的选区划分方案。由于此问题的特殊性,我们得到了与上述问题相同的结果。针对本文,我们提出了两个改进:对于H标函数的选择,建立一个能同时满足使获胜选区内平均得票率最大与标准差最小的H标函数;对于预计投票率的可信度是否为I,我们提出增加权重来解决此问题的改进方案。本文的最优选区划分方案可以推广到加个街区组成〃个选区的情形。问题二的第一个模型可用于在对每个街区会投票给政党的选民数和总选民数的预计结果很准确吋使用;问题二的第二个模型可以在预计结果不是很准确,但多数选区都能得到相对较大的投票率时使用。本模型在政治学、管理和对策论等领域都具有应用价值。问题重述在一次竞选屮,SarkMevo所领导的政党终于击败联合党派,Mevo希望叽固他在首都地区的席位。下图为首都地区示意图(图I)-在图屮用1・14对这14个街区进行了编号,每个街区屮的另两个数字是预计该街区会投票给政党Mevo的选民数和该街区的选民总数。所有选民都必须投票,且选举胜出方必须得到绝对多数选票。其屮,选区的划分规则如下:一个选区可以由多个相邻的街区组成。如果两个街区不相邻,例如12和13,则它们不能组成一个选区;选区内总选民数应在30,000到100,000之问;如果某街区选民人数大于或等于50,000,则允许此街区单独作为一个选区;4・由于政党Mevo就居住在街区10内,他不能将这个街区单独作为一个选区。设计出一个将首都划分为5个选区的方案,以使政党Mevo得到的席位数最多。如果这样做有困难,可以尝试划分为6个选区。117500/3000069000/40000712000/30000215000/50000314200/20000810000/30000926000/400001227000/60000518000/200001034000/60000112500/**********/700001329000/400001415000/40000图1问题分析仔细分析已知“相邻街区必须作为一个选区”的条件,有两种理解:划分的街区必须两两相邻;划分的街区不必两两相邻,只要能合成一-块即可。基于此,我们要解决如下三个问题:问题一:要使政党得到的席位数最多,该首都是否可划分为5个选区,若不行,则考虑6个选区是否可行。问题二:建立选区内街区必须两两相邻的模型。针对获胜席位的稳定性,我们乂可考虑对问题二建立两个不同的模型:1•设计一个将首都14个街区划分为最小选区的方案,以使政党得到的席位数最多。对于某街区八它只有两种可能,要么展于选区儿要么不属于选区这两种情况分别对应二进制数屮的1、0,所以可考虑采用0-1整数规划⑴模型来解决此步,显然H标函数即为该政党得到的最多席位数。然后依据已知列出约束条件(图2所有叶结点)。在处理相邻街区才能作为选区这个约束条件的时候,本文定义了一个邻接矩阵T=(^,)l4xl4,若第刃街区和第〃街区相邻,则他们能同属于一个选区八若不相邻,则选区i最多只含有其屮的一个街区,即有:札+卷Q+心Q=1,・・,6,加、n=1,…,14)图2分析上述模型所作出的方案是否绝对可行,能否找到更好的方案以使政党能巩固他在首都地区的席位,即使其获得的席位具有稳定性。问题三:建立划分的街区不必两两相邻,只要能合成一块的模型。(即有同等的选举权),只能投一票且投票的意愿不再改动,所有的选票都有效;每个选区内的选民总数在选举前是固定不变的,即不考虑人口的迁入、迁出和出生、死亡引起选民总数的变化;假设该政党在选举屮是否胜出只与其获得的席位数有关,而该政党在某选区