摘 要
本文针对选举分区问题建立了相应的数学模型。选举分区问题,可以抽象成经典
的组合优化模型:划分子集问题。同时,该问题也是 NP 难问题。
根据首都地区的实际情况,以 14 个街区为研究对象。首先,对为什么要划分选区
和对划分多少个选区做作了定量分析。
然后,将某街区是否被划分在一个特定的选区内记为 0—1 变量,以领导人获得的
席位数为优化目标,将相关约束予以转化,建立了 0—1 规划模型。利用 LINGO 进行
了求解。
最后,将问题进行转换,利用模拟退火算法求解,得到了在领导人获得的席位数
最多目标下的选区划分方案。
对结果分析表明:通过简单的划分选区策略,可以使领导人的席位从 0.5185 提高
近 1.6 倍,稳定储备系数提高约 17 倍。
对模型的优缺点给出了客观评价,对模型和问题的进一步深入提出了展望。
关键字:选举分区;组合优化;0—1 规划模型;LINGO;模拟退火算法
选举分区问题
1
1 问题重述
在—个遥远的国家,Sark Mevo 所领导的政党最终击败了 Reguel Tekris 王子领
导的联合党派。Mevo 希望巩固他在首都地区的席位。首都由 14 个街区组成,这些街
区将分组为多个选区。图 1 是首都地区的示意图。在图中用数字 1 到 14 对这些街区进
行了编号。每个街区中的另外两个数字是预计该街区会投票给 Mevo 的选民数和该街
区的选民总数。所有选民都必须投票,且选举胜出方必须得到绝对多数选票。一个选
区可以由多个相邻的街区组成,且选区内总选民数应在 30,000 到 100,000 之间。如
果两个街区不相邻,例如 12 和 13,则它们不能组成一个选区。如果某个街区选民人
数不少于 50,000,则允许此街区单独作为一个选区。但是由于 Mevo 本人就居住在街
区 10 内,因此迫于舆论压力,他不能将这个街区单独作为一个选区。
设计一个将首都划分为 5 个选区的方案,以使 Mevo 得到的席位数最多。如果这样
做有困难,可以尝试划分为 6 个选区。
图 1 首都地区示意图
2 基本假设
1、各选区选出议员的人数与该选区的总选民数成正比,比例系数为 。
2、该国采用美国现行的“选举团”制度作为其选举制度。
3、每个选民均必须投票,且不存在弃权或选择两个候选人的选票。
4、各街区内支持 Mevo 的选民数在讨论问题期间是恒定不变的常数。
3 符号说明
:选区选出议员的比例;
:划分选区的总数;
:第 j 个街区被划分在第 i 个选区的示性变量, 。 表示 j 被划入 i 选区;
表示 j 未被划入 i 选区 ;
:第 j 街区的总选民数;
:第 j 街区支持 Mevo 的人数;
:第 i 选区的总选民数;
:第 i 个选区所含有街区的矩阵;
:第 j 个街区的相容矩阵;
:街区之间的邻接矩阵;
2
:稳定储备系数,用来描述 Mevo 领导人地位的稳定程度。
注:还有一些局部变量,在使用时将作相关说明。
4 问题分析
4.1 选举制度的猜想
从问题的描述来看,这个遥远的国家以两个政党(包含联合政党)之间的角逐,
最终由一个政党来统领国家政权的方式来实现国家的政治制度。这与美国的政治制度
极其相似。这里,我们不妨假定该国的政治制度与美国现行的政治制度相当。所以,
在选举制度问题上,我们认为该国采用美国的选举团制度。
选举团(Electoral College):当某国选民前往投票站投票选举领导人时,很多
人认为自己是在直接选举领导人。采用“选举团制度”时,情况并非如此。选举团是一
组"选举人"的总称,他们由各选区政党成员在选区内提名产生。在大选日,选民实际
是把票投给承诺支持某位领导人候选人的"选举人"。哪位候选人赢得的选民票数最多,
支持这位候选人的"选举人"就将作为这个选区的代表,出席于确定时间分别在各选区
举行的选举领导人的投票。领导人候选人必须在总的选区中获得至少半数的“选举人”票
才可当选。出于方便起见,下文称这些“选举人”为议员。
4.2 选区总数的分析
4.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
150
00
14200
420
00
180
00
900
0
120
00
投票给 Mevo 的选民数
30000
500
00
20000
700
00
200
00
400
00
300
00
Mevo 获得的选票率
0.5833
33
0.3 0.71 0.6 0.9
0.22
5
0.4
街区数
8 9 10 11 12 13 14
选民数
10000
260
00
34000
250
0
270
00
290
00
150
00
投票给 Mevo 的选民数
30000
400
00
60000
100
00
600
00
400
00
400
00
Mevo 获得的选票率
0.3333
33
0.65
0.5666
67
0.25 0.45
0.72
5
0.37
5
如果不划分选区,Mevo 获得的支持率为
3
(1)
其中,
(2)
如果按照 的比例(比如 0.2‰)选举议员,首都的总选民数为 ,
那么 Mevo 获得的席位数为 。即是,在首都的总选民数一定的情况下,讨论席
位数与总的支持率是等效的。另外,未划分选区时,Mevo 的支持率已经达到 0.5185。
划分选区后,Mevo 的支持率会大于这个数值吗?我们拭目以待。
4.2.2 问题 2:划分多少个选区才合适?
既然,分区对 Mevo 有利,分多少个区才合适呢?从政治民主的角度来看,分的区
不益过多;从另一个方面来看,要尽可能削弱反对力量,分区又不能过少。题目给出
了相关的约束条件,我们做如下的定量分析。
首都的总选民数为
(3)
题目认为,一个合理的分区方案应该满足:选区内总选民数应在 30,000 到
100,000 之间。那么,分区的总数 应该满足
(4)
所以, ,也即是说:最少的分区数是 6。这样,我们将从 6 开始讨论分区方案。
5 模型的建立与求解
5.1 0—1 规划模型的建立与求解
选举分区问题,可以抽象成经典的组合优化模型:划分子集问题,在本问题中即
是将 14 个节点按照多个约束条件划分到 6 个集合中。同时,该问题也是 NP 难问题。
由于,该问题的规模不大,我们首先尝试建立简单的 0—1 规划模型,如果模型不能够
圆满地解决问题,我们再考虑对模型进行转化,该用其他的近似算法来求解。
5.1.1 优化目标的确立
Mevo 建立大的选区的目的就在于巩固他在首都地区的席位。这些席位来自那些支
持他的选区议员,而这些议员的产生直接缘于在某选区支持 Mevo 的选民占多数。在某
选区内,支持 Mevo 的选民占总选民的比例用 表示,则
(5)
自然地,有
4
评论0