选区划分的优化问题
摘要
在—个遥远的国家,Sark Mevo 所领导的政党最终击败了 Reguel Tekris 王子领导
的联合党派。Mevo 希望巩固他在首都地区的席位。首都由 14 个街区组成,这些街区将
分组为多个选区。对于想巩固自己政权的 Sark Mevo,如何将街区划分为有利于获得优势
席位的选区变的至关重要。
本文是以模拟的首都街区划分、预计得到的选票数以及选民总人数、选区划分的约
束为基准,通过合理的假设和对模型输出数据的严密推理,得到了使 Sevo 获得多席位
的选区划分方案。
讨论该如何选区时,在了解四色原理后,我们只需考虑将 1 个、2 个或 3 个街区组
成一个选区的可能性。同时,我们定义单个街区组成的选区为 A 型选区,两个相邻街区
组成的选区为 B 型选区,3 个两两相邻街区组成的选区为 C 型选区。
对于划分为 5 个选区的假设,根据整数规划,运用 MATLAB 软件得出划分方案[2,3,
3,3,3],即这种假设有 2 个 B 型选区和 4 个 C 型选区组成。定义 E(i,j)表示街区 i
与街区 j 相邻,U(i)表示 i 街区的总人数,V(i)表示 i 街区预计 Mvoe 选票数,根据约
束条件 E(i,j)*E(j,k)*E(k,i)=1 和 30000<=U(i)+U(j)+U(k)〈=100000,得出所有可能
的 C 型选区划分,如下表所示:
表 1
2
3
1
C 型选区号
所含街区号 (1,2,5) (2,3,5) (6,7,8) (7,8,9) (8,10,11) (8,9,11)
在表中 1 和 2 选区包含相同街区,表中 3、4、5、6 四个选区同样如此,因此最多只能
同时存在两个 C 型选区,不满足 5 个选区的假设方案,固舍去此假设方案。
考虑 6 个选区的假设。定义 Xi 为第 i 个选区所含街区数,Xi 为 1、2 或 3,约束
4
5
6
xi =14
6
=
1i
我们可以 6 个由不同型号选区组成的划分方案,如下表:
表 2
首都划分方案
所含选区类型
1
[A,A,C,C,C,C]
2
[A,B,B,C,C ,C] [B,B,B,B,C,C]
3
第二步,结合表 1 分析的结果,得出首都划分方案只能为[B,B,B,B,C,C]这种
类型组合。 第三步,推出获得优势席位的 C 选区组合(1,2,5)、(2,3,5)和不能
获得优势席位的 C 型选区组合(6,7,8)、(7,8,9)、(8,10,11)、(8,9,11)。第
四步,通过 MATLAB 筛选出 2 号和 6 号街区,不能组成获得优势席位的 B 型选区,即 2
和 6 号必定在 C 型选区中,进一步缩小
两个 C 型选区组合方案为(1,2,5)+(6,7,8)或(2,3,5)+(6,7,8)。
第五步,运用 Lingo 软件,通过 0-1 规划,匹配出唯一解,如下表所示:
表 3
选区型号
所含街区号 (3,4) (9,12) (10,11) (13,14) (1,2,5) (6,7,8)
B
B
C
C
B
B
关键词:四色原理 0-1 规划 匹配问题 上三角矩阵
1
1、问题的背景
众所周知,美国政治上的动向永远都吸引着全球亿万人的目光。民主党 PK 共和党,
也被人们戏称为“驴象”之争。各党派对拥有优势席位的渴望,已达到了锱铢必争的程
度,从布什政府在 07 年的中期选举时狂砸 26 亿(美国政府历届以来最高)之多可想而
知。
对优势席位的趋之若骛,无外乎想取得参众两院(参议院,众议院)的控制权。有
了参众两院的控制劝,就有了政府各项举措实施的决定权。因此,选举的结果将对执政
期间产生重大影响,选举的成败也就成为了执政生涯成败的风向标!
政党之间,永远都在进行在权利之争。谁拥有了绝对优势的参众两院的代表席位,
谁就拥有了参众两院的控制权,国家大事的发言权,政府各项举措实施的决定权!
Sark Mevo 领导的政党虽然击败了对手,但并不能说自己的政权就得到了巩固,因
为反动势力永远都存在着、观望着,一旦你在政权上稍微有些松懈的迹象,他们都会伺
机而动,不惜一切地推翻你的政权,卷土重来!因此,Sark Mevo 还必须通过在首都地
区取得席位上的优势,进一步控制议会发言权,举措决议权。
2、问题的重述
本文讲诉的就是 Sark Mevo 领导的政党最终击败了 Reguel Tekris 王子领导的联合
政党,他希望通过把首都划分为不同选区,争取在其中更多的选区赢得绝对优势的选票,
从而拥有席位上的优势,巩固自己在首都的统治。
首都地区街区的详细情况如下面的示意图所示:
图 1
1-14 分别是对这些街区进行的编号。每个街区中的另外两个数字是预计该街区会投
票给 Mevo 的选民数和该街区的选民总数。所有选民必须投票,且选举胜出方必须得到
绝对多数选票。选区可以由一个或多个街区组成,并且街区必须两两相临。选区总人数
限定在 30000 到 100000 之间。像 4 号街区这样人数不小于 50000 的街区,则允许该街
区单独作为一个街区。但由于 Mevo 本人就居住在 10 号街区,因此迫于舆论压力,他不
能将 10 号街区单独划分为一个街区。现在要考虑的问题是:设计出一个将首都地区划
分为 5 个选区,以使 Mevo 得到的席位数最多。如果这样做有困难,可以尝试划分为 6
个选区。
3 问题的假设及说明
2
3. 1 选区内某政党得到的选票数超过该选区的选民总数一半以上时,则认为
该政党得到了绝对多的选票数。
3.2 每个选区只能产生一个席位,得到绝对多选票数的政党拥有席位。
3.3 执政党拥有的席位数超过总席位的一半时,则认为该执政党巩固了其执政地位,
如分为 5 个选区,则该执政党必须拥有 3 个或 3 个以上的席位才能巩固其执政地
位,如分为 6 个选区,则该执政党必须拥有 3 个以上的席位才能巩固其执政地位。
3.4 执政党拥有的席位比例越重,其执政地位越牢固。
3.5 有公共边的街区即为相邻街区,如图 1 所示 1 和 2 即为相邻街区,而 6 和 10 为对
角街区,就不为相邻街区。
3.6 在首都地区排除了如图 2 所示
的这种一个街区包含三个或三个以上街区
的不正规地图,只含如图 3 所示
的这种正规地图。
3.7 假设选举期间无影响选民意愿的突发事件发生,题中所做选民选票估计与真实投票
结果无太大的波动,一切正常进行。
3.8 假设 Mevo 的任何符合题意的分区方案都能得到通过
3.9 假设选举期间各街区无大的人口流动,且各街区间相互组合后选民的意愿不受其影
响.
4 问题的分析
我们需要通过将首都的 14 个街区划分为 5 个或 6 个选区,以使 Mevo 能在这些选区
中获得优势的席位。首先,我们来讨论最多能把多少个街区划分进一个选区。
考虑这个问题时,我们先来了解以下什么是四色问题。四色问题的内容是:“任何
一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”如图 4 所示
,用数学语言表示,即“将平面任意地细分为不相重叠的区域,每一个
区域总可以用 1,2,3,4 这四个数字之一来标记,而不会使相邻的两个区域得到相同
的数字。”如图 5 所示
3
由此我们可以得到这样一个结论:在一个正规的地图中,比如首都的街区布局,一
定不存在 4 个或 4 个以上的、两两相临的街区。因此我们在划分首都选区时,最多只考
虑将 3 个两两相临的街区即 C 型选区划分到一个选区中。
由问题的假设我们得知,Mevo 在一个选区获得的票数占绝对优势,那么他将在这个
选区将获得席位,否则不获得席位。对于这个问题,我们可以用 MATLAB 软件来求解。
考虑首都选区组成情况是,必须先求出符合首都街区分布的不同类型选区有哪些。
对于这个问题,我们可以在严密的约束条件限制下,运用 MATLAB 软件搜索的 A,B,C
三种类型的选区的所有可能情况。然后通过数学模型推理,进一步缩小对这三种类型的
选区的考虑范围。可能的不同类型的选区确定后,就剩下匹配问题了,我们很容易想到
用 LINGO 软件 0-1 规划来解决。
5 模型的符号说明
符号说明:模型符号的说明:
Xi: Xi 表示为第 i 选区所拥有的街区个数。
U(i): U(i)为第 i 街区的选民总数。
V(i): V(i)为第 i 街区预计会投票给 mevo 的选票数。
E(i,j):当 E(i,j)=1 表示 i 街区与 j 街区相邻;
当 E(i,j)=0 表示 i 街区与 j 街区不相邻。
MATCH(j,k): 当 MATCH(j,k)=1 表示 j 街区与 k 街区组成一个选区。
LINJIE(i,j): 当 LINJIE(i,j)=1,表示 i 街区 j 街区能组成 B 型选区,且 i 街区 j
街区选民总数在 30000 到 100000,且票数具有绝对优势
否则 LINJIE(I,j)=0
A:单个街区组成的选区,如 4 号街区就能组成 A 型选区。
B:2 个相邻的街区组成的选区,如 1 号和 2 号就能组成的 B 型选区。
C: 3 个两两相邻的街区组成的选区,如 1 号,2 号和 5 号就能组成的 C 型选区。
6 模型的建立与分析
6.1 讨论划分为 5 个选区的模型:
在问题的分析前,我们通过四色原理得出了最多只考虑将 3 个两两相临的街区划分
到一个选区的结论,因此只讨论将 1 到 3 个街区划分进一个选区的情况,建立如下正整
数规划模型:
5
=i
1
=
xi
14
0< xi<4
xi˛ N
xi 表示第 i 选区所含的街区数,运用 MATLAB 软件求解,程序见附件 1。
由于是一个无向图,划分选区的结果只能是[2,3,3,3,3]。即在 5 个选区中,
有 1 个是 B 型选区,其余 4 个选区由 3 个 C 型选区组成。
首先,考虑有多少种能获得席位的 C 型选区存在:
4
我们建立如下模型::
A=
0 1 0 0 1 0 0 0 0 0 0 0 0 0
1 0 1 0 1 0 0 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0 0 1 0 0 0 0
1 1 1 1 0 1 0 0 0 1 0 0 0 0
0 0 0 0 1 0 1 1 0 0 0 0 0 0
0 0 0 0 0 1 0 1 1 0 0 0 0 0
0 0 0 0 0 1 1 0 1 1 1 0 0 0
0 0 0 0 0 0 1 1 0 0 1 1 0 0
0 0 0 1 1 0 0 1 0 0 1 0 1 0
0 0 0 0 0 0 0 1 1 1 0 1 1 0
0 0 0 0 0 0 0 0 1 0 1 0 0 1
0 0 0 0 0 0 0 0 0 1 1 0 0 1
0 0 0 0 0 0 0 0 0 0 0 1 1 0
U=
30000 50000 20000 70000 20000 40000 30000 30000 40000 60000
10000 60000 40000 40000
V=
17500 15000 14200 42000 18000 9000 12000 10000 26000 340000 2500
27000 29000 15000
E(i,j)*E(j,k)*E(k,i)=1
30000<=U(i)+U(j)+U(k)
U(i)+U(j)+U(k)<=100000
(V(i)+V(j)+V(k))>0.5(U(i)+U(j)+U(k))
E(i,j)为 1,表示街区 i 与 j 相邻;为 0 则不相邻,U(i)表示 i 街区投票总人数,
V(i)表示 i 街区预的票总数。A 是根据街区相邻情况建立的邻接矩阵。运用 MATLAB
软件求解,程序见附件 2.1,结果如下表所示:
表 4
优势 C 型选区号
所含街区号
1
(1,2,5)
2
(2,3,5)
同理,根据附件 2.2 程序结果,可以得出不能获得席位即劣势 C 型选区种数,如下
表所示:
表 5
2
(7,8,9)
劣势 C 型选区号
所含街区号
1
(6,7,8)
3
(9,11,12) (10,11,13)
4
结合表 4 和表 5 可得所有 C 的型选区组成,如下表所示:
5
表 1
C 型选区号
所含街区号 (1,2,5) (2,3,5) (6,7,8) (7,8,9) (8,10,11) (8,9,11)
1
3
2
4
5
6
其中前 2 个选区都含有 2 号和 5 号街区,后 4 个选区都含有 8 号街区,即在前 2 个
中最多只能存在 1 个选区,后 4 个选区最多也只能存在 1 个选区。然而划分为 5 个选区
的模型必须含有 4 个由 3 个 C 街区组成的选区,因此 5 个选区的模型在现有的条件下不
成立,固不于考虑。
6.2 划分为 6 个选区的模型建立:
在划分为 6 个 选区的方案下,可建立如下正整数规划模型:
6
=i
1
=
xi
14
0< xi<4
xi˛ N
xi 表示第 i 选区所含的街区数,运用 MATLAB 软件求解,程序见附件 3
对所得数据进行分析,由于是一个无向图,划分选区的结果如下表所示:
表 2
首都划分方案
所含选区类型
1
[A,A,C,C,C,C]
2
[A,B,B,C,C ,C] [B,B,B,B,C,C]
3
由表 2 可知,划分为 6 个选区的方案中,最少含有 2 个 C 型选区。在分析表 1 时,
我们选区中最多只有 2 个 C 街区组成的选区同时存在。因此,划分选区的结果为[B,B,
B,B,C,C],即有 4 个为 B 型选区,2 个 C 型选区,在接下来的讨论中就可排除所有单
独街区组成 A 型选区的可能性。
由表 4 中数据可知,优势 C 型选区号 1 和 2 中都含相同的街区 2 和 5,因此最终只
能在其中选择一个作为选区。同理,劣势 C 型选区号 1,2,3,4 中都有 8 号街区,同
样也只能取其中一种。所以,最终的 2 个 C 型选区,一个在优势 C 型选区号中取得,另
一个在劣势 C 型选区号中取得。
由此,我们可推出这样一个结论:划分为 6 个选区的方案下,必含的两个 C 型选区
号,一个在表 4 中取得,它能获得优势席位,另一个在表 5 中取得,它将不能获得优势
席位,那么 6 个选区不可能都获得席位。
问题的假设及说明 3.5 中以指出,执政党拥有的席位比例越重,其执政地位越牢固。
在不可能 6 个选区都获得席位的情况下,假如 5 个选区胜出的可能性成立,即为最优解。
在对表 2 的分析中,我们得知首都地区应该划分为 4 个 B 型选区和 2 个 C 型选区。
从附件 4 可得出所有能获得优势席位的 B 型选区组合情况,如下表所示:
表 6
B 型选区号
1
2
3
4
所含街区号 (1,5) (3,4) (3,5) (4,5)
6
5
(5,10) (7,9) (8,9)
7
B 型选区号
所含街区号 (9,11) (9,12) (10,11) (10,13) (11,13) (13,14)
10
12
13
8
9
11
在附件 5 中,我们通过搜索获得优势席位的 B 型选区后,将不能组成优势席位 B 型
选区的街区输出,为 2 号和 6 号街区,即 2 号和 6 号只能组成为 C 型选区。由表 3 可知
6
2 号街区组成的 C 型选区(1,2,5)和(2,3,5)这两种情况,由表 4 可知 6 号街区
组成的 C 型选区只有(6,7,8)这一种情况。因此两个 C 型选区的组成为(1,2,5)
+(6,7,8)或(2,3,5)+(6,7,8)这两种可能方案。先讨论(1,2,5)+(6,
7,8)组合的方案,即先确定了 6 个街区。在表 5 中删除含有这 6 个街区的 B 型选区号,
结果如下表所示:
表 7
B 型选区号
所含街区号 (3,4) (9,11) (9,12) (10,11) (10,13) (11,13) (13,14)
1
4
2
3
5
6
7
在剩余的 8 个街区中,找出 4 个 B 型选区,.与即定的组合方案进行匹配,找出可行解。
把上表所有的 B 型选区编成 linjie 矩阵,(由于对称性,这个矩阵只有严格上三角部分共
28 个 0-1 值)如下表所示:
街区号 S3
S4
S9
S10
S11 S12
S13
S14
S3
S4
S9
S10
S11
S12
S13
S14
-
-
-
-
-
-
-
-
1
-
-
-
-
-
-
-
0
0
-
-
-
-
-
-
0
0
0
-
-
-
-
-
0
0
1
1
-
-
-
-
0
0
1
0
0
-
-
-
0
0
0
1
1
0
-
-
0
0
0
0
0
0
1
-
用 MATCH(Si,Sj)=1 表示街区 Si,Sj 组成一个选区,而 MATCH(Si,Sj)=0 表示 Si,Sj
不组成一个选区,由于对称性,只需考虑 i