排版论文

1选区划分的优化问题摘要在—个遥远的国家，SarkMevo所领导的政党最终击败了ReguelTekris王子领导的联合党派。Mevo希望巩固他在首都地区的席位。首都由14个街区组成，这些街区将分组为多个选区。对于想巩固自己政权的SarkMevo,如何将街区划分为有利于获得优势席位的选区变的至关重要。本文是以模拟的首都街区划分、预计得到的选票数以及选民总人数、选区划分的约束为基准，通过合理的假设和对模型输出数据的严密推理，得到了使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型选区划分，如下表所示：C型选区号123456所含街区号（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，约束61ixi=14我们可以6个由不同型号选区组成的划分方案，如下表：首都划分方案123所含选区类型[A，A，C，C，C，C][A，B，B，C，C，C][B，B，B，B，C，C]第二步，结合表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规划，匹配出唯一解，如下表所示：选区型号BBBBCC所含街区号（3，4）（9，12）（10，11）（13，14）（1，2，5）（6，7，8）关键词：四色原理0-1规划匹配问题上三角矩阵21、问题的背景众所周知，美国政治上的动向永远都吸引着全球亿万人的目光。民主党PK共和党，也被人们戏称为“驴象”之争。各党派对拥有优势席位的渴望，已达到了锱铢必争的程度，从布什政府在07年的中期选举时狂砸26亿（美国政府历届以来最高）之多可想而知。对优势席位的趋之若骛，无外乎想取得参众两院（参议院，众议院）的控制权。有了参众两院的控制劝，就有了政府各项举措实施的决定权。因此，选举的结果将对执政期间产生重大影响，选举的成败也就成为了执政生涯成败的风向标！政党之间，永远都在进行在权利之争。谁拥有了绝对优势的参众两院的代表席位，谁就拥有了参众两院的控制权，国家大事的发言权，政府各项举措实施的决定权！SarkMevo领导的政党虽然击败了对手，但并不能说自己的政权就得到了巩固，因为反动势力永远都存在着、观望着，一旦你在政权上稍微有些松懈的迹象，他们都会伺机而动，不惜一切地推翻你的政权，卷土重来！因此，SarkMevo还必须通过在首都地区取得席位上的优势，进一步控制议会发言权，举措决议权。2、问题的重述本文讲诉的就是SarkMevo领导的政党最终击败了ReguelTekris王子领导的联合政党，他希望通过把首都划分为不同选区，争取在其中更多的选区赢得绝对优势的选票，从而拥有席位上的优势，巩固自己在首都的统治。首都地区街区的详细情况如下面的示意图所示：图11-14分别是对这些街区进行的编号。每个街区中的另外两个数字是预计该街区会投票给Mevo的选民数和该街区的选民总数。所有选民必须投票，且选举胜出方必须得到绝对多数选票。选区可以由一个或多个街区组成，并且街区必须两两相临。选区总人数限定在30000到100000之间。像4号街区这样人数不小于50000的街区，则允许该街区单独作为一个街区。但由于Mevo本人就居住在10号街区，因此迫于舆论压力，他不能将10号街区单独划分为一个街区。现在要考虑的问题是：设计出一个将首都地区划分为5个选区，以使Mevo得到的席位数最多。如果这样做有困难，可以尝试划分为6个选区。3问题的假设及说明33.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所示4由此我们可以得到这样一个结论：在一个正规的地图中，比如首都的街区布局，一定不存在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）=0A：单个街区组成的选区，如4号街区就能组成A型选区。B：2个相邻的街区组成的选区，如1号和2号就能组成的B型选区。C：3个两两相邻的街区组成的选区，如1号，2号和5号就能组成的C型选区。6模型的建立与分析6．1讨论划分为5个选区的模型：在问题的分析前，我们通过四色原理得出了最多只考虑将3个两两相临的街区划分到一个选区的结论，因此只讨论将1到3个街区划分进一个选区的情况，建立如下正整数规划模型:1451ixi0xi4xiNxi表示第i选区所含的街区数，运用MATLAB软件求解,程序见附件1。由于是一个无向图，划分选区的结果只能是[2，3，3，3，3]。即在5个选区中，有1个是B型选区，其余4个选区由3个C型选区组成。首先，考虑有多少种能获得席位的C型选区存在：5我们建立如下模型：:A=0100100000000010101000000000010110000000000010100001000011110100010000000010110000000000010110000000000110111000000000110011000001100100101000000001110110000000001010010000000001100100000000000110U=3000050000200007000020000400003000030000400006000010000600004000040000V=175001500014200420001800090001200010000260003400002500270002900015000E(i,j)*E(j,k)*E(k,i)=130000=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，结果如下表所示：优势C型选区号12所含街区号（1，2，5）（2，3，5）同理，根据附件2.2程序结果，可以得出不能获得席位即劣势C型选区种数，如下表所示：劣势C型选区号1234所含街区号（6，7，8）（7，8，9）（9，11，12）（10，11，13）结合表4和表5可得所有C的型选区组成，如下表所示：6C型选区号123456所含街区号（1，2，5）（2，3，5）（6，7，8）（7，8，9）（8，10，11）（8，9，11）其中前2个选区都含有2号和5号街区，后4个选区都含有8号街区，即在前2个中最多只能存在1个选区，后4个选区最多也只能存在1个选区。然而划分为5个选区的模型必须含有4个由3个C街区组成的选区，因此5个选区的模型在现有的条件下不成立，固不于考虑。6．2划分为6个选区的模型建立：在划分为6个选区的方案下，可建立如下正整数规划模型:1461ixi0xi4xiNxi表示第i选区所含的街区数，运用MATLAB软件求解，程序见附件3对所得数据进行分析，由于是一个无向图，划分选区的结果如下表所示：首都划分方案123所含选区类型[A，A，C，C，C，C][A，B，B，C，C，C][B，B，B，B，C，C]由表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型