数学建模选区划分的优化问题.pdf

发布时间：2022-06-10 发布人：admin 分类：说明书资料大小：0.14M 资料格式：pdf 举报版权申诉

chliangp-1700624-16359647539805370237.pdf-第1页.png

第1页 / 共16页

chliangp-1700624-16359647539805370237.pdf-第2页.png

第2页 / 共16页

chliangp-1700624-16359647539805370237.pdf-第3页.png

第3页 / 共16页

chliangp-1700624-16359647539805370237.pdf-第4页.png

第4页 / 共16页

chliangp-1700624-16359647539805370237.pdf-第5页.png

第5页 / 共16页

chliangp-1700624-16359647539805370237.pdf-第6页.png

第6页 / 共16页

chliangp-1700624-16359647539805370237.pdf-第7页.png

第7页 / 共16页

chliangp-1700624-16359647539805370237.pdf-第8页.png

第8页 / 共16页

文本预览

选区划分的优化问题摘要在—个遥远的国家，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

分享到：

赞收藏

资料库

数学建模选区划分的优化问题.pdf

相关推荐

课程资源

热门标签

最新资料