1 选举分区问题的 0- 1 规划模型 选做的题号：B 编号：05007 组长：张晨昕 组员：周化 组员：曾磊 2 选举分区问题的 0- 1 规划模型 摘 要 模型的数学归类：本问题是一个以选举问题为背景包含数据分析拟合、0- 1 规划和 最优分区等内容的建模问题。 模型的建模思想：由于没有找到合适的一步解决原问题的方法，我们将原问题分为 两步，分别建立模型、，并分步进行求解。在模型中，我们先对各街区列出能使 其组成某一选区的约束条件 选区的总人数限制、组成选区的街区必相邻，利用完全 枚举法在数学软件 MATLAB 中进行求解，得出此街区能组成某一选区的所有可能的分 区情况。在模型中，我们运用 0- 1 规划，根据分区数目的限制，任一街区必须属于且 只能属于某一特定选区，最终获得的席位数必须过半这三个条件进行约束，通过数学软 件 LINGO 求解，从模型得到的所有可能的分区情况中，进行筛选并确定最终的分区 方案。 本题的结果：首都的14个街区无法划分为5个选区，应划分为6个选区。 各选区的组成街区如下： 选区1：街区1，街区2，街区5 选区2：街区3，街区4 选区3：街区6，街区7，街区8 选区4：街区10，街区11 选区5：街区9，街区12 选区6：街区13，街区14 其中选区1，2，4，5，6投票给Mevo的选民人数均达到了总选民人数的一半，因此Mevo 一共得到了5个席位，获得了首都地区的选举胜利。 关键字 分区问题 0- 1 规划 完全枚举法 选举 3 一 问题的简述和背景 某一国家的首都共有 14 个街区。现有一次选举，候选人 Mevo 希望在首都得到最 多的席位数以获得选举的最终胜利。我们知道一个席位即为一个选区，若此选区投票人 数过半即为获胜，得到此席位。而一个选区可以由一个或多个相邻的街区组成，且选区 内的总选民数应在 30000 到 100000 之间。 如果某个街区的选民人数不少于 50000， 则允 许此街区单独作为一个选区（例如：街区 4） 。如果两个街区不相邻，则他们不能组成一 个选区（例如：街区 1 和街区 6） 。街区 10 不能单独作为一个选区。 首都地区的示意图如下，图中用数字 1 到 14 对这些街区进行了编号。每个街区中 的另外两个数字分别是预计该街区会投票给 Mevo 的选民人数和该街区总的选民人数。 现在的问题是，如何找出一个将首都划分为 5 个选区的方案，以使 Mevo 得到的席 位数最多。如果这样做有困难，则可划分为 6 个选区。 二 问题的分析 由于将街区划分为选区的限制条件很多:每个选区的总选民人数应在 30000 到 100000 之间（条件 1） 。相邻的街区才能划分为一个选区（条件 2） 。当某街区的总选民 数大于 50000，并且不为 Mevo 所在的第 10 街区，则可单独划分为一个选区（条件 3） 。 因此，我们可先将满足上述条件的所有可能组成一个选区的街区分区情况求解出来，再 以 Mevo 要取得竞选的最终胜利，即要在所有选区中占有最多的席位为目标函数，以分 区数目的限制，即最后的选区数目为 5 或 6（条件 1） 。任一街区必须属于且只能属于某 一特定选区（条件 2） 。最终 Mevo 获得的席位数必须过半（条件 3）为约束条件，对上 面求出的分区情况进行筛选，从而求解出最优的分区方案。 三 问题的假设 1、分区方案完全由 Mevo 决定的，不受到其它条件如舆论等方面的影响. 2、各个选区之间相互独立，互不影响，且不受其它条件的影响. 3、总的选民数在一定时间内不发生变化。 4、所有的选民都投了票。 5、预计的选民投票情况与最终投票情况相同，且预计情况正确。 6、Reguel Tekris 王子对分区、投票不进行干预. 4 四 符号说明 1、A(i,j)：表示第 i 个街区与第 j 个街区的相邻关系，为一个 1414 的矩阵。 若 A（i，j）=1，则表示第 i个街区与第 j 个街区相邻； 若 A（i，j）=0，则表示第 i个街区与第 j 个街区不相邻。 2、rs(i)：表示第 i个街区的选民总数，为一个 114 的矩阵。 3、tprs(i)：表示第 i 个街区的投票给 Mevo 的选民数，为一个 114 的矩阵。 4、k：为一个计数字符，表示可能的分区情况的数目为 k 个。 5、zrs(i)：表示第 i个选区的选民总数，为一个 1k 的矩阵。 6、ztprs(i)：表示第 i 个选区所有投票给 Mevo 的选民人数，为一个 1k 的矩阵。 7、q(i,j)：表示序号为 i的选区与第 j 个街区的包含关系，是一个 k14 的矩阵。 若 q（i，j）=1，则表示序号为 i的选区中包含有第 j 个街区； 若 q（i，j）=0，则表示序号为 i的选区中不包含有第 j 个街区。 8、s(i)：表示序号为 i的选区中投票给 Mevo 的选民数在该选区的选民总数中所占的 比例，为一个 k1 的矩阵。 9、ss(i)：表示 Mevo 是否能在序号为 i 的选区中取得该席位，为一个 k1 的矩阵。 若 ss（i）=1，则表示 Mevo 在序号为 i 的选区中取得该席位； 若 ss（i）=0，则表示 Mevo 没有在序号为 i 的选区中取得该席位。 10、x（i） ：表示选择序号为 i的分区为最终的分区方案 若 x（i）=1，则表示第 i种分区情况包含在最终的分区方案中 若 x（i）=0，则表示第 i种分区情况不包含在最终的分区方案中 上述分区情况由矩阵 q 决定。 五 模型的建立与求解 模型 找出所有可能组成一个选区的分区情况 分析: 1、若某街区的选民总数不少于 50000，并且不为 Mevo 所在的第 10 街区，则可单 独划分为一个选区。 2、只有相邻的街区才能划分为一个选区，可以用矩阵 A 来表示任意两个街区 i、j 的相邻关系。 3、每个选区总的选民人数应在 30000 到 100000 之间（包含 30000 和 100000） 。 因此，每个选区的街区组成个数只能为 1，2，3. 对应建立约束条件： 首先选定某一街区 n 1、当选区由一个街区组成时： (rs(n)=50000) 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 1 0 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 ; rs=30000,50000,20000,70000,20000,40000,30000,30000,40000,60000,10000,60000,40000, 40000; k=1; q=zeros(45,14); for n=1:14 if (rs(n)=50000) k=k+1; end for i=n+1:14 if (A(n,i)=1) q(k,i)=1; k=k+1; end end for i=n+1:14 if (A(n,i)=1) q(k,i)=1; q(k,l)=1; k=k+1; end end end end 11 end k=k- 1 2模型的算法（LINGO） sets: hang/1.45/:x,s,ss,zrs,ztprs; lie/1.14/:rs,tprs; xishu(hang,lie):q; endsets data: q= 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 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 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 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 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 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 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 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 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 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 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 12 0 0 0 0 0 0 0 0 0 0 1 0 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 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 ; rs=30000,50000,20000,70000,20000,40000,30000,30000,40000,60000,10000,60000,40000,4 0000; tprs=17500,15000,14200,42000,18000,9000,12000,10000,26000,34000,2500,27000,29000,1 5000; enddata for(hang(I):zrs(I)=sum(l