2022年网络优化作业资料 .pdf

《2022年网络优化作业资料 .pdf》由会员分享，可在线阅读，更多相关《2022年网络优化作业资料 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、作业土规 1101 班刘迈克 2011306200521 第一题： 在个遥远的国家， Sark Mevo 所领导的政党最终击败了 Reguel Tekris王子领导的联合党派。 Mevo希望巩固他在首都地区的席位。首都由14 个街区组成，这些街区将分组为多个选区。下图是首都地区的示意图。在图中用数字1 到 14 对这些街区进行了编号。每个街区中的另外两个数字是预计该街区会投票给Mevo的选民数和该街区的选民总数。 所有选民都必须投票， 且选举胜出方必须得到绝对多数选票。 一个选区可以由多个相邻的街区组成，且选区内总选民数应在 30,000 到 100,000 之间。如果两个街区不相邻，例如12

2、和 13，则它们不能组成一个选区。如果某个街区选民人数不少于50,000，则允许此街区单独作为一个选区。但是由于Mevo本人就居住在街区 10 内，因此迫于舆论压力，他不能将这个街区单独作为一个选区。请设计出一个将首都划分为5 个选区的方案，以使Mevo得到的席位数最多。如果这样做有困难，可以尝试划分为6 个选区。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - 解：（1）运用二部图的最大匹配。分别将街区划分为选票率大于0.5 的

3、 x 和小于 0.5 的 y 两部分，然后将x、y 相邻的街区进行连线，寻找最大匹配，使得票概率最大，但是结果可能不太准确。（2）运用 0-1 规划划分不同的选区，然后根据条件寻找最匹配区域。讨论该如何选区时， 运用着色原理， 考虑将 1 个、2 个或 3 个街区组成一个选区的可能性。 同时，定义单个街区组成的选区为A型选区，两个相邻街区组成的选区为 B型选区， 3 个两两相邻街区组成的选区为C型选区。假设划分为 6 个选区，根据整数规划，建立模型1461ixi 0 xi4 xiN xi 表示第 i 选区所含的街区数，运用MATLAB 程序：clc;clear; % 清除 matlab 界面的

4、数值 ,及其变量%x1,x2,x3,x4,x5,x6 表示 6 个席区for x1=1:3 %表示为 x1 每个席区的街区数的取值范围,以下类同for x2=1:3 for x3=1:3 for x4=2:3 for x5=2:3 for x6=2:3 if x1+x2+x3+x4+x5+x6=14 %每个席区所包含的街区的个数等于总街区数A=x1,x2,x3,x4,x5,x6; % 输出解B=sort(A) end end end end end end end % 由于 x1,x2,x3,x4,x5,x6 不存在有序性,故对于有序组只取其中一个即可得到结果： B =2 2 2 2 3 3

5、，定义 Xi 为第 i 个选区所含街区数， Xi 为 1、2或 3，约束61ixi=14我们可以 6 个由不同型号选区组成的划分方案，即B B B B C C。程序：n=14;A= 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - 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 00 1 0 1 1 0 0 0 0 0 0 0 0 00 0 1 0 1 0 0 0 0 1

6、 0 0 0 0 1 1 1 1 0 1 0 0 0 1 0 0 0 00 0 0 0 1 0 1 1 0 0 0 0 0 00 0 0 0 0 1 0 1 1 0 0 0 0 00 0 0 0 0 1 1 0 1 1 1 0 0 00 0 0 0 0 0 1 1 0 0 1 1 0 00 0 0 1 1 0 0 1 0 0 1 0 1 00 0 0 0 0 0 0 1 1 1 0 1 1 00 0 0 0 0 0 0 0 1 0 1 0 0 10 0 0 0 0 0 0 0 0 1 1 0 0 10 0 0 0 0 0 0 0 0 0 0 1 1 0; D=A; P= 30000 50000

7、 20000 70000 20000 40000 30000 30000 40000 60000 10000 60000 40000 40000;Q=17500 15000 14200 42000 18000 9000 12000 10000 26000 34000 2500 27000 29000 15000; V=Q;U=P;for i=1:nfor j=1:nif ( D(i,j)& ( 30000=(U(i)+U(j)&(U(i)+U(j)0.5) )=1 B=i,j; C=sort(B) disp(*);endendend可得出所有能获得优势席位的B型选区组合情况，如下表所示：B 型

8、选区号1 2 3 4 5 6 7 所含街区号（1，5）（3， 4）（3， 5）（4，5）（5，10）（7，9）（8，9）B 型选区号8 9 10 11 12 13 所含街区号（9，11）（9， 12）（10， 11） （10， 13） （11， 13） （13， 14）不能组成优势席位 B型选区的街区输出，为 2号和6号街区，即 2号和6号只能组成名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - 为C 型选区。 2号街区组成的 C

9、型选区（ 1，2，5）和（2，3，5）这两种情况，由6号街区组成的 C型选区只有（ 6，7，8）这一种情况。因此两个 C型选区的组成为（1，2，5）+（6，7，8）或（ 2，3，5）+（6，7，8）这两种可能方案。MODEL : SETS: JIEQU/S3,S4,S9,S10,S11,S12,S13,S14/;!定义去除选定的六个点外的剩于的街区的编号，并且按照升序排列;PAIRS(JIEQU,JIEQU)|&2#GT#&1:LINGJIE,MATCH;! 街区 I到街区I,且 I大于 J,LINGJIE 表示当街区 I到街区 J相邻，且街区I和街区 J的人数在 30000在100000 且

10、街区 I和街区 J的预计选 mevo的总人数与街区I和街区 J的总人数之比大于0.5 这三个条件满足时 LINGJIE(I,J) 为1，否则为 A（I,J)为0.此矩阵为上三角的0-1矩阵 ;ENDSETSDATA: LINGJIE= 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 0 0 0 1; ENDDATAobjective MAX =SUM (PAIRS(I,J):LINGJIE(I,J)*MATCH(I,J);!每队存在，且满足邻接条件时，相乘为了 1，若 4队同时存在，则相加为4;FOR(JIEQU(I): SUM (PAIRS(J

11、,K)|J#EQ#I#OR#K#EQ#I:MATCH(J,K)=1); FOR(PAIRS(I,J):BIN (MATCH(I,J); END 运用 LINGO软件求解，搜索到存在与（ 1，2，5）+（6，7，8）匹配的 4 个 B型选区，并在这 4 个选区都能获得席位，即得到的最优解获得5 个席位 . 选区型号 B B B B C C 所含街区号（3，4）（9，12） （10，11）（13，14）（1，2，5） （6，7，8）最优解可能不唯一，讨论（2，3，5）+（6，7，8）的 C型选区组合情况，在表 5 中删除含有这 6 个街区的 B型选区号，结果如下表所示：B型选区号1 2 3 4 5

12、 6 所含街区号（9，11）（9，12）（10，11）（10，13）（11，13）（13，14）分析表 9 可知， 没有其它任何街区与1 号街区形成 B型选区。 因此该方案不可行，最优解唯一。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - 划分为 5 个选区的模型必须含有4 个由 3 个 C街区组成的选区，因此 5 个选区的模型在现有的条件下不成立，固不于考虑。第二题：如图在每一段容量不同的情况下得到最优的敷设。电缆沟用图表示，

13、每根电缆的敷设用节点表示。在一个田字型的电缆沟里面，敷设从A 到 B 的 6 条电缆，依次并排敷设。分别在以下情况下敷设1.每一段容量为3；2.A 相连的两端容量为3，其余容量为2；由于电缆较粗，在敷设中要减少交叉和转弯次数，试找到交叉和转弯次数最少的敷设方案。解：首先对每个节点标号125，按顺序编号，如图所示，方框代表各个节点：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 若是两点之间相差正负1 或者正负 5，则说明这两点在同一行或者同一列上，若是不满足以上条件说明存在转弯情况，每三个点判断是否存在转弯情况。例如节点 13，如果与周围相邻的四个节点8、12、14、18 相差分别为正负 1 或者正负 5，则存在交叉现象； 3、4、5 每三个节点考虑转弯问题。1、每一段容量为 3。要求减少交叉次数和转弯次数，有两种方法从A到 B：（1）节点： 5432161116. （2）节点： 510152019181716. A 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -