资源描述：
《【精品】排版论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、选区划分的优化问题摘要在一个遥远的国家，SarkMevo所领导的政党最终击败了ReguelTekris王子领导的联合党派。Mevo希望巩固他在首都地区的席位。首都由14个街区组成，这些街区将分组为多个选区。对于想巩固自C政权的SarkMevo,如何将街区划分为有利于获得优势席位的选区变的至关重要。木文是以模拟的首都街区划分、预计得到的选票数以及选民总人数、选区划分的约束为基准，通过合理的假设和对模型输出数据的严密推理，得到了使Sevo获得多席位的选区划分方案。讨论该如何选区时，在了解四色原理后，我们只需
2、考虑将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
3、)<=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考虑6个选区的假设。定义Xi为第i个选区所含街区数,Xi为1、2或3,约U乞力二14/=1我们可以6个由不同型号选区组成的划分方案，如下表：首都划分方案123所含选区类型[A,A,
4、C,C,C,C][A,B,B,C,C,C][B,B,B,B,C,C]第二步，结合表1分析的结果，得岀首都划分方案只能为[13,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)。第四步，通过MTLAB筛选出2号和6号街区，不能组成获得优势席位的B型选区，即2和6号必定在C型选区中，进一步缩小两个C型选区组合方案为(1,2,5)+(6,7,8)或(2,3,5
5、)+(6,7,8)。第五步，运用Lingo软件，通过0-1规划，匹配出唯一解，如下表所示：选区型号BBBBCC所含街区号(3,4)(9,12)(10,11)(13,14)(1,2,5)(6,7,8)关键词：四色原理0-1规划匹配问题上三角矩阵1、问题的背景众所周知，美国政治上的动向永远都吸引着全球亿万人的目光。民主党PK共和党,也被人们戏称为“驴象”之争。各党派对拥有优势席位的渴望，已达到了铠铢必争的程度，从布什政府在07年的屮期选举时狂砸26亿（美国政府历届以来最高）之多可想而知。对优势席位的趋之若弩
6、，无外乎想取得参众两院（参议院，众议院）的控制权。有了参众两院的控制劝，就有了政府各项举措实施的决定权。因此，选举的结果将对执政期间产生重大影响，选举的成败也就成为了执政生涯成败的风向标！政党之间，永远都在进行•在权利之争。谁拥有了绝对优势的参众两院的代表席位，谁就拥有了参众两院的控制权，国家人事的发言权，政府各项举措实施的决定权！SarkMevo领导的政党虽然击败了对手，但并不能说自己的政权就得到了巩I舌I,因为反动势力永远都存在着、观望着，一旦你在政权上稍微有些松懈的迹象，他们都会伺机而动，不惜一切
7、地推翻你的政权，卷土重来！因此，SarkMcvo还必须通过在首都地区取得席位上的优势，进一步控制议会发言权，举措决议权。2、问题的重述本文讲诉的就是SarkMevo领导的政党最终击败了ReguelTekris王子领导的联合政党，他希舉通过把首都划分为不同选区，争取在其中更多的选区赢得绝对优势的选票,从而拥有席位上的优势，巩固己在首都的统治。首都地区街区的详细悄况如下面的示意图所示：117500/3000069000/40000712000/30000215000/50000314200/20000810
8、000/30000926000/400001227000/60000518000/200001034000/60000112500/10000442000/700001329000/400001415000/40000图11-14分别是对这些街区进行的编号。每个街区屮的另外两个数字是预计该街区会投票给Mevo的选民数和该街区的选民总数。所有选民必须投票，且选举胜出方必须得到绝对多数选票。选区可以由一个或多个街区组成，并且街区必须两两相临。选
